Interconnections: Bridges, Routers, Switches, and Internetworking Protocols

PREFACE: \ Interconnections, Second Edition is about what goes on inside the boxes that move data around the Internet. These boxes are variously called bridges, routers, switches, and hubs. The book also describes the devices that connect to the network.\ There is considerable confusion in this area. Most of the terminology is ill defined and is used in conflicting ways. The terminology and the specifications tend to be daunting. Some knowledge is spread among many different documents; much is unwritten folk wisdom. Adding to the confusion is dogma. Beliefs are accepted as truth, and questioning any of the dogma is often greeted with hostility. But good engineering demands that we understand what we're doing and why, keep an open mind, and learn from experience.\ In Interconnections, Second Edition, instead of diving right into the details of one protocol, I first focus on the problems to be solved. I examine various solutions to each of these problems and discuss the engineering trade-offs involved. Then I look at a variety of solutions that have been deployed and compare the approaches. I give technical arguments for any opinions, and if you think I have missed any arguments I welcome email discussion. My email address is at the back of the book, which I hope you will find after having read the book cover to cover.\ In the first edition, my intention was to help people understand the problems and the general types of solutions, assuming that they would read the specifications to get the details of specific protocols. But people used the book as a reference in addition to using it to understand the issues. So in this edition Ihave documented many more of the protocols in detail.\ I believe that to understand something deeply you need to compare it to something else. The first edition was "minimalist" in that I always used only two examples: two types of bridges, bridges versus routers, connection-oriented versus connectionless network layer protocols, and two examples of connectionless protocols (CLNP and IP). In this edition I add a lot more examples, including ATM, IPv6, IPX, AppleTalk, and DECnet. I did this in part because these protocols exist, and it is hard to get information about them. But mostly I did it because the protocols embody interesting ideas that should not be lost. When we design new protocols, we should learn from previous ideas, both good and bad. Also, it takes very little additional effort, after the problem is described generically, to describe several examples.\ Roadmap to the Book\ The first four chapters are not significantly different from their counterparts in the first edition, but the rest of the book has been largely rewritten. Chapters 1 through 4 cover general networking concepts, data link issues such as addressing and multiplexing, transparent bridges and the spanning tree algorithm, and source routing bridges. Chapter 5 is completely new and explains how the notion of a switch evolved into a rediscovery of the bridge. It also covers VLANs and fast Ethernet.\ The remainder of the book concentrates on layer 3 (the network layer). Chapter 6 gives an overview of the network layer. Chapter 7 covers connection-oriented networks, including ATM and X.25. Chapter 8 discusses the issues in a generic connectionless network layer. Chapter 9 covers layer 3 addressing generically and gives a detailed comparison of IP, IPv6, CLNP, DECnet, AppleTalk, and IPX. Chapter 10 covers the information that should appear in a network layer header and contrasts the headers of several protocols.\ Chapter 11 covers autoconfiguration and neighbor discovery, including protocols such as ARP and DHCP. Chapter 12 covers routing algorithms generically.\ Chapter 13 discusses the problem of doing longest-prefix matching, which is required in order to forward IP packets quickly. Chapter 14 discusses the specifics of various routing protocols including RIP, IS-IS, OSPF, PNNI, NLSP, and BGP. Chapter 15 covers network layer multicast. Chapter 16 explains how to design a network that is invulnerable to sabotage, an idea whose time may come.\ The final two chapters summarize the book, and I hope they will be mostly light and entertaining reading. Chapter 17 probes the mystery of what, if anything, distinguishes a router from a bridge. Chapter 18 attempts to capture folk wisdom about how to design a protocol.\ Finally, there is an extensive glossary. I try to define terms when I first use them, but if I ever fail to do that, you will probably find them in the glossary.\ Acknowledgments\ Writing this section is scary because I am afraid I will leave people out. I'd like to thank the people who reviewed all or part of the book: Peter Memishian, Paul Koning, Tony Lauck, Craig Partridge, Dan Pitt, Brian Kernighan, Paul Bottorff, Joel Halpern, Charlie Kaufman, Mike Speciner, Andy Tanenbaum, Phil Rosenzweig, Dan Senie, William Welch, Craig Labovitz, Chase Bailey, George Varghese, and Suchi Raman. Other people who have been helpful by answering questions are Ariel Hendel, Rich Kubota, Stuart Cheshire, Tom Maufer, Steve Deering, and John Moy. The first time I sent an email question in the middle of the night (when I did most of my work on this book) to Craig Partridge, the co-series editor for this book, the beep indicating incoming mail happened so immediately that I assumed it was an automatic mail responder informing me he was on vacation. But it was an answer to my question. I assume he doesn't have an automatic mail responder so clever that it can answer technical questions, so I thank him for being so prompt and available. Brian Kernighan, the other series editor, also had detailed and helpful comments on the entire book.\ The people at Addison-Wesley have been amazingly patient with me for the many years in which I've been working on this edition. I'm not sure they had any alternative besides patience, but it was nice that they believed I'd finish even when I wasn't so sure. So thank you to Mary Hart, Karen Gettman, Jacquelyn Doucette, and Jason Jones. And I'd also like to thank my copy editor, Betsy Hardinger. She of all people will have read every word of the book, while maintaining the concentration to note inconsistencies and ways of removing excess words here and there. I know it's her job, but I'm still impressed.\ Mike Speciner helped me figure out the mysteries of Framemaker. Ray Perlner made sure that I maintained some humor in the book and watched over my shoulder while I typed the last chapter to see that I had enough funny bad real-life protocols. Dawn Perlner has been terrifically supportive, convincing her friends and even strangers in bookstores to buy my books. She used to be my child. Now she's a wonderful friend.\ \ \ 0201634481P04062001

Preface. Roadmap to the Book. Acknowledgments. 1. Essential Networking Concepts. Layers. Service Models. Important Properties of a Network. Reliable Data Transfer Protocols. 2. Data Link Layer Issues. Generic LANs. IEEE 802 LANs. Names, Addresses, Routes. LAN Addresses. Multicast versus Unicast Addresses. The Broadcast Address. Multiplexing Field. Bit Order. Logical Link Control. Issues in 802.3. Issues in 802.5. Packet Bursts. Reasons for Bridges. Point-to-Point Links. 3. Transparent Bridges. The No-Frills Bridge. The Learning Bridge. Spanning Tree Algorithm. Spanning Tree Algorithm Refinements. Bridge Message Formats. Other Bridge Issues. Remote Bridges. 4. Source Routing Bridges. Pure Source Routing. SR-TB Bridges. SRT Bridges. End-system Algorithms. Source Routing versus Transparent Bridging. Ideas for Improving Source Route Bridging. 5. Hubs, Switches, Virtual LANs, and Fast Ethernet. Hubs. Faster LANs. Virtual LANs (VLANs). 6. Network Interface: Service Models. What Is the Network Layer? Network Service Types. 7. Connection-oriented Nets: X.25 and ATM. Generic Connection-oriented Network. X.25: Reliable Connection-oriented Service. Implementing X.25 Inside the Net. AsynchronousTransfer Mode. 8. Generic Connectionless Service. Data Transfer. Addresses. Hop Count. Service Class Information. Network Feedback. Fragmentation and Reassembly. Maximum Packet Size Discovery. 9. Network Layer Addresses. Hierarchical Addresses with Fixed Boundaries. Hierarchical Addresses with Flexible Boundaries. Owning versus Renting Addresses. Types of Addresses. IP. IPX. IPX+. IPv6. CLNP Network Layer Addresses. AppleTalk Network Layer Addresses. DECnet Phases III and IV. NAT/NAPT. 10. Connectionless Data Packet Formats. Pieces of a Connectionless Network Layer. Data Packets. Summary of Packet Formats for Easy Reference. Technical Issues and Comparisons in Data Packet Formats. Source Routing. The Great IPX Frame Format Mystery. Error Reports and Other Network Feedback to the Endnode. 11. Neighbor Greeting and Autoconfiguration. Endnodes Attached via Point-to-Point Links. Endnodes Attached via LANs. Endnodes Attached via Nonbroadcast Multiaccess Media. Finding Things. 12. Routing Algorithm Concepts. Distance Vector Routing. Link State Routing. Comparison of Link State and Distance Vector Routing. Load Splitting. Link Costs. Migrating Routing Algorithms. LANs. Types of Service. Partition Repair: Level 1 Subnetwork Partition. 13. Fast Packet Forwarding. Using an Additional Header. Address Prefix Matching. Longest Prefix Match with Trie. Binary Search. 14. Specific Routing Protocols. A Brief History of Intradomain Routing Protocols. RIP. RTMP, IPX-RIP, and DECnet. IS-IS, OSPF, NLSP, and PNNI. Interdomain Routing Protocols. 15. WAN Multicast. Introduction. Multicast in IP. 16. Sabotage-proof Routing. The Problem. All You Need to Know about Cryptography. Overview of the Approach. Detailed Description of the Approach. Summary. For Further Reading. 17. To Route, Bridge, or Switch: Is That the Question? Switches. Bridges versus Routers. Extensions to Bridges. Extensions to Routers. 18. Protocol Design Folklore. Simplicity versus Flexibility versus Optimality. Knowing the Problem You're Trying to Solve. Overhead and Scaling. Operation Above Capacity. Compact IDs versus Object Identifiers. Optimizing for the Most Common or Important Case. Forward Compatibility. Migration: Routing Algorithms and Addressing. Parameters. Making Multiprotocol Operation Possible. Running over Layer 3 versus Layer. Robustness. Determinism versus Stability. Performance for Correctness. In Closing. Glossary. Index. 0201634481T04062001

\ BooknewsA text on networking theory and practice, providing information on general networking concepts, routing algorithms and protocols, addressing, and mechanics of bridges, routers, switches, and hubs. Describes all major network algorithms and protocols in use today, and explores engineering trade-offs that each different approach represents. Includes chapter homework problems and a glossary. This second edition is expanded to cover recent developments such as VLANs, Fast Ethernet, and AppleTalk. The author is a Distinguished Engineer at Sun Microsystems, Inc., and holds some 50 patents. Annotation c. Book News, Inc., Portland, OR (booknews.com)\ \