IP Routing (Ravi Malhotra) (z-library.sk, 1lib.sk, z-lib.sk)

IP Routing ,TITLE.23706 Page i Wednesday, January 9, 2002 12:29 PM

IP Routing by Ravi Malhotra Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. Printed in the United States of America. Published by O’Reilly & Associates, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472. O’Reilly & Associates books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles (safari.oreilly.com). For more information contact our corporate/institutional sales department: (800) 998-9938 or corporate@oreilly.com. Editor: Jim Sumser Production Editor: Rachel Wheeler Cover Designer: Ellie Volckhausen Interior Designer: Melanie Wang Printing History: January 2002: First Edition. Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered trademarks of O’Reilly & Associates, Inc. The association between the image of a zebu and the topic of IP routing is a trademark of O’Reilly & Associates, Inc. Cisco IOS and and all Cisco-based trademarks are registered trademarks of Cisco Systems, Inc. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and O’Reilly & Associates, Inc. was aware of a trademark claim, the designations have been printed in caps or initial caps. While every precaution has been taken in the preparation of this book, the publisher assumes no responsibility for errors or omissions, or for damages resulting from the use of the information contained herein. ISBN: 0-596-00275-0 [C] ,COPYRIGHT.23443 Page iv Wednesday, January 9, 2002 12:29 PM

IP Routing Ravi Malhotra Beijing • Cambridge • Farnham • Köln • Paris • Sebastopol • Taipei • Tokyo ,TITLE.23706 Page iii Wednesday, January 9, 2002 12:29 PM

About the Author Ravi Malhotra (iparch@yahoo.com) began working for AT&T Bell Labs in 1986, doing R&D work. Since then he has taught data communications at universities, managed IP networks for several large financial houses, and written several maga- zine assignments. Mr. Malhotra possesses degrees in Electrical Engineering and Computer Science. Colophon Our look is the result of reader comments, our own experimentation, and feedback from distribution channels. Distinctive covers complement our distinctive approach to technical topics, breathing personality and life into potentially dry subjects. The animal on the cover of IP Routing is a zebu. Zebus are a type of Bos indicus cattle, characterized by a large fatty hump over the top of the shoulder and neck, loose skin under the throat, and large, drooping ears. They are an intermediate size for beef cattle—bulls generally weigh from 1,600 to 2,200 pounds and cows from 1,000 to 1,400 pounds—but have comparatively long legs and are extremely hardy. Zebu cattle breeds include Gyr, Guzerat, Indu-Brazil, Nelore, Red Zebu, and Gray Zebu. They originated in India and are thought to be the world’s oldest domesti- cated cattle. Zebus were introduced into the U.S. (where they are called Brahman cattle) in the mid-19th century as draft animals, but they later interbred with other cattle breeds and produced hybrids that were bigger, grew faster, and were better suited for milk and beef production. These hybrids exhibited greater resistance to heat, disease, and cattle ticks than ordinary domestic cattle and consequently tended to fare better than the cattle the colonists had brought from Europe. Rachel Wheeler was the production editor and copyeditor for IP Routing. Tatiana Apandi Diaz was the proofreader. Matt Hutchinson provided quality control, and Camilla Ammirati provided production assistance. John Bickelhaupt wrote the index. Ellie Volckhausen designed the cover of this book, based on a series design by Edie Freedman. The cover image is a 19th-century engraving from the Dover Pictorial Archive. Emma Colby and Melanie Wang produced the cover layout with Quark- XPress 4.1 using Adobe’s ITC Garamond font. Melanie Wang designed the interior layout, based on a series design by David Futato. Neil Walls converted the files from Microsoft Word to FrameMaker 5.5.6 using tools created by Mike Sierra. The text font is Linotype Birka; the heading font is Adobe Myriad Condensed; and the code font is LucasFont’s TheSans Mono Condensed. The illustrations that appear in the book were produced by Robert Romano and Jessamyn Read using Macromedia FreeHand 9 and Adobe Photoshop 6. The tip and warning icons were drawn by Christopher Bing. This colophon was written by Rachel Wheeler. Whenever possible, our books use a durable and flexible lay-flat binding. ,AUTHOR.COLO.23272 Page 1 Wednesday, January 9, 2002 12:28 PM

vii Table of Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1. Starting Simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 What Is IP Routing? 1 Directly Connected Networks 2 Static Routing 3 Dynamic Routing 5 The Routing Table 6 Underlying Processes 9 Summing Up 9 2. Routing Information Protocol (RIP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Getting RIP Running 10 How RIP Finds Shortest Paths 13 Convergence 19 Subnet Masks 26 Route Summarization 27 Default Route 28 Fine-Tuning RIP 29 Summing Up 31 3. Interior Gateway Routing Protocol (IGRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Getting IGRP Running 33 How IGRP Works 37 Speeding Up Convergence 55 Route Summarization 56 Default Routes 57 ,p_ip_routingTOC.fm.23063 Page vii Wednesday, January 9, 2002 12:27 PM

viii | Table of Contents Classful Route Lookups 60 Summing Up 61 4. Enhanced Interior Gateway Routing Protocol (EIGRP) . . . . . . . . . . . . . . . . . . 63 Getting EIGRP Running 64 EIGRP Metric 67 How EIGRP Works 68 Variable Length Subnet Masks 82 Route Summarization 84 Default Routes 88 Troubleshooting EIGRP 90 Summing Up 93 5. Routing Information Protocol Version 2 (RIP-2) . . . . . . . . . . . . . . . . . . . . . . . . 94 Getting RIP-2 Running 95 RIP-2 Packet Format 98 RIP-1/RIP-2 Compatibility 99 Classful Versus Classless Routing Protocols 101 Classful Versus Classless Route Lookup 103 Authentication 103 Route Summarization 105 Summing Up 106 6. Open Shortest Path First (OSPF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Getting OSPF Running 109 OSPF Metric 113 Definitions and Concepts 114 How OSPF Works 121 Route Summarization 137 Default Routes 140 Virtual Links 141 Demand Circuits 143 Stub, Totally Stubby, and Not So Stubby Areas 144 NBMA Networks 148 OSPF Design Heuristics 150 Troubleshooting OSPF 153 Summing Up 156 ,p_ip_routingTOC.fm.23063 Page viii Wednesday, January 9, 2002 12:27 PM

Table of Contents | ix 7. Border Gateway Protocol 4 (BGP-4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Background 158 Getting BGP Running 163 How BGP Works 166 Load Balancing 191 Route-Filtering 192 Connecting to the Internet 194 Choosing an ISP 199 Troubleshooting BGP 200 Summing Up 202 8. Administrative Controls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Filter Routing Information 204 Rate the Trustworthiness of a Routing Information Source 207 Redistribute Routes 207 Maximum Number of Paths 211 Summing Up 211 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 ,p_ip_routingTOC.fm.23063 Page ix Wednesday, January 9, 2002 12:27 PM

This book is dedicated to my grandfather, the late P.D. Gandhi, who taught me the love of learning. ,DEDICATION.23573 Page v Wednesday, January 9, 2002 12:29 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. xi Preface Ants, single-celled creatures such as the cellular slime mold, plants and animals in ecosystems, and (even) human beings can congregate and display miraculously com- plex behaviors.* Say a colony of ants in a tree needs to move to another tree, perhaps in search of food. Some ants build a bridge by joining their bodies in a chain stretch- ing from one limb in one tree to another limb in another tree. Other ants cross over this ant structure, walking over their peers. Once all the ants have crossed over, the ants in the bridge begin to gracefully undo the structure, crossing one by one. Each ant only repeats simple actions, over and over again; the net result of thousands of ants working together is the miracle of the bridge, which allows the ant colony to migrate. In our own human society we hope to emulate this level of cooperation. Each one of us is useful to others in some way: we write, lay bricks, act in the theater, farm, drive buses, repair helicopters, tend to the sick, make coffee... As individuals, we repeat the same acts again and again, whether it be making coffee cup after coffee cup or seeing patient after patient. The net result of all these acts is our complex, wonderful society. So, what does all this have to do with IP routing? Each router in a network repeats simple processes over and over again, as described in the specification of the routing protocol it is executing. The net result of all the routers in a network repeating these simple processes is IP routing, or the movement of IP packets in a network. * The New York Times has reported some intriguing examples of such behavior, quoting research work from the Santa Fe Institute in New Mexico (“Mindless Creatures Acting Mindfully,” The New York Times, March 23, 1999, Science Times). ,ch00.21432 Page xi Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. xii | Preface My advice to you, the student of IP routing, is this: study the simple behaviors of each ant, and make sure you understand them in detail. There is no other way to understand how IP networks behave as ordered organisms. Audience This text assumes that the reader has knowledge of basic networking concepts—the ISO/OSI model, bridging versus routing, IP addressing, TCP/IP, etc. This text is not meant to replace Cisco manuals. Use this text to build concepts. IP routing commands are described as they are used to illustrate concepts; however, this text does not contain an exhaustive list of all IP routing commands. Use Cisco documentation for details on commands, to find out which IOS release supports new features, and for the (inevitable) bug lists. Most of the time I have used addresses from the private address pool. However, sometimes I have had to dip into the registered address pool, especially when talking about BGP. If you use the examples in this book, be careful that you do not choose addresses that conflict with existing addresses in your environment. Organization This book is comprised of eight chapters: Chapter 1, Starting Simple This chapter introduces the basic concepts of IP routing. It will show you the simplest method of creating entries in a routing table—by defining static routes. Chapter 2, Routing Information Protocol (RIP) RIP is the earliest dynamic routing protocol. This chapter describes RIP in detail, including a discussion of the Distance Vector (DV) algorithms that are the foun- dation of RIP and other routing protocols. Since RIP is the simplest dynamic routing protocol, it is a great tool from which to learn. It may be a good idea to study this chapter even if you do not intend to use RIP. Chapter 3, Interior Gateway Routing Protocol (IGRP) IGRP is Cisco’s proprietary routing protocol, which directly descended from RIP. IGRP contains some features that make it much more useful than RIP. This chapter focuses on these new features (study Chapter 2 to learn about the foun- dations of IGRP—the DV protocols). Chapter 4, Enhanced Interior Gateway Routing Protocol (EIGRP) The DV algorithms employed by RIP and IGRP have inherent limitations. EIGRP is Cisco’s proprietary routing protocol, which interworks seamlessly with IGRP but attempts to overcome these limitations. EIGRP supports classless networks and Variable Length Subnet Masks (VLSM). ,ch00.21432 Page xii Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. Preface | xiii Chapter 5, Routing Information Protocol Version 2 (RIP-2) RIP-2 is an attempt to bring RIP back into vogue. RIP-2 is really RIP with sup- port for classless networks and VLSM. RIP-2 still has all the limitations of DV protocols, such as long convergence times. Chapter 6, Open Shortest Path First (OSPF) OSPF is an open routing protocol. It is most commonly used to build large IP networks. The standards bodies are focusing their work on OSPF, and it is con- stantly evolving. OSPF is not a DV protocol: OSPF is based on the Dijkstra algo- rithm. This chapter explains Dijkstra in detail and lays the foundation of how to build hierarchical networks using OSPF. Chapter 7, Border Gateway Protocol 4 (BGP-4) BGP is the glue that binds the thousands of networks that comprise the Internet. Routing in the Internet is quite different from routing in intranets. There are sev- eral new concepts in this chapter. Chapter 8, Administrative Controls This chapter describes the administrative tools available to all the routing proto- cols. These tools are used to block the advertisement of routing updates, set up preferences for one routing protocol over another, and more. Conventions Used in This Book Italic Used for emphasis and the first use of technical terms, as well as for the names of networks and routers used in the examples. Constant Width Used for IP addresses. Constant width italic Used for replaceable parameter names in command syntax. Code blocks are used throughout the text to make concepts concrete. Line numbers in the lefthand margins are used to refer to specific pieces of the code block. To avoid confusion, within each chapter the line numbers used in the code blocks start at 1 and continue consecutively through the end of the chapter. Code lines that are in bold but are not numbered are also of particular relevance to the surrounding text. NewYork#sh ip ospf interface ... Ethernet0 is up, line protocol is up 1 Internet Address 172.16.1.1/24, Area 0 2 Process ID 10, Router ID 172.16.251.1, Network Type BROADCAST, Cost: 10 ... Serial0 is up, line protocol is up Internet Address 172.16.250.1/24, Area 0 Process ID 10, Router ID 172.16.251.1, Network Type POINT_TO_POINT, Cost: 64 ,ch00.21432 Page xiii Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. xiv | Preface The use of “…” in the code block indicates that some lines (which were not useful in the discussion) have been omitted. Indicates a tip, suggestion, or general note. Indicates a warning or caution. How to Contact Us Please address comments and questions concerning this book to the publisher: O’Reilly & Associates, Inc. 1005 Gravenstein Highway North Sebastopol, CA 95472 (800) 998-9938 (in the United States or Canada) (707) 829-0515 (international/local) (707) 829-0104 (fax) There is a web page for this book, which lists errata, examples, or any additional information. You can access this page at: http://www.oreilly.com/catalog/iprouting/ To comment or ask technical questions about this book, send email to: bookquestions@oreilly.com For more information about books, conferences, Resource Centers, and the O’Reilly Network, see the O’Reilly web site at: http://www.oreilly.com Acknowledgments I would like to thank Andrew Sun for suggesting this book. Andrew’s work on PPP was not only an inspiration but also a model for my endeavors on this text. Mark H. Degner, Edgar Danielyan, and especially Elsa Lankford made some key suggestions on improving the technical content. Rachel Wheeler served as a very gracious Production Editor, coordinating the details that were essential to producing the book on time. Thanks also to Jessamyn Read, the O’Reilly Illustrator who transformed my rough sketches into the figures you’ll find in this book. ,ch00.21432 Page xiv Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. Preface | xv As the first editor, Mike Loukides helped define the organization and content of the book. Jim Sumser took over from Mike partway through the project. Jim helped me see the work in perspective and led me through the mire of the detailed work. I want to thank Jim for the patience with which he worked with me. Everything that could prevent me from getting to the book seemed to happen: even I did not believe it would get done, but somehow Jim believed in it. I must have worked through two summers with him, for I remember him talking about two very sweet crops from his cherry tree. Writing this book was a long, winding road that led me away from my loved ones on many an evening. I have missed Char, my wife, all those evenings when I was locked away somewhere, rewriting a chapter. I am not sure how much Char missed me, but she certainly missed having me around to look after Lucas and Theo, who are quite young and absolutely adorable to be around. This last piece of this book is being written in the weeks after September 11, 2001. Much of this book was written around the World Trade Center: in it, under it, in its shadow, looking up at it, in a bus traveling to it, in a subway moving away from it, under the influence of coffee bought there, while waiting to meet my family in a nearby park. The Towers symbolize a time of freedom and innocence. We live in a different era now, and I have come to think of this book as belonging to that era of freedom and happiness and innocence. ,ch00.21432 Page xv Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. 1 Chapter 1 In this chapter: • What Is IP Routing? • Directly Connected Networks • Static Routing • Dynamic Routing • The Routing Table • Underlying Processes • Summing Up CHAPTER 1 Starting Simple What Is IP Routing? A young woman boards a commuter train in a small town in Quebec, changes trains a couple of times, and, a day later, arrives in New York City. She walks up the stairs from the platform into Grand Central Terminal, looks up above her head, and, for the first time, sees the constellations, hundreds of feet above on the ceiling. A high school student in New Zealand downloads maps of Sri Lanka from a local (Sri Lankan) web site. The maps show the natural features, the political boundaries, the flora and fauna, rainfall, ancient kingdoms, languages, and religions. The download takes thousands of IP packets that find their way from Sri Lanka to the student’s PC in New Zealand. Just as our Canadian friend changed trains at several stations along the way, the IP packets from the Sri Lankan web site may have bounced through dozens of routers before arriving at the student’s machine. The routing of IP packets in an IP network is the set of tasks required to move an IP packet from router to router to its destination, as specified in the IP header field. This book is about the set of tasks that accomplish IP routing. There are similarities in routing concepts between IP networks, transportation sys- tems, and mail delivery operations. Throughout this text, we will often illustrate IP routing concepts by comparison with these other systems. ,ch01.21583 Page 1 Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. 2 | Chapter 1: Starting Simple Directly Connected Networks When our Canadian visitor finally picks up her bags and is ready to head out of Grand Central Terminal, she looks around for the exit signs. On one end, below a row of immense windows, is a sign saying “Vanderbilt Avenue.” Below the opposite row of tall windows is a sign saying “Lexington Avenue.” Under the large stone arches is a sign reading “42nd Street” (Figure 1-1). Just as the streets around Grand Central Terminal are immediately accessible to any traveler, a router has directly attached networks that are immediately accessible (in other words, that do not require any specific routing mechanism to discover). Con- sider router R, in the following example. Networks 1.0.0.0, 10.1.1.0, and 10.1.2.0 are directly connected to the router: hostname R ! interface Ethernet0 ip address 1.1.1.1 255.0.0.0 ! interface Ethernet1 ip address 10.1.1.4 255.255.255.0 ! interface Ethernet2 ip address 10.1.2.4 255.255.255.0 ... In fact, the moment these networks are connected to the router they are visible in R’s routing table. Note in the following output that the command to display the routing table is show ip route (in EXEC mode). Also note the “C” that is prepended to the entries in the routing table, indicating that the routes were discovered as directly connected to the router: R#show ip route Codes: C - connected, S - static, I - IGRP, R - RIP, M - mobile, B - BGP Figure 1-1. Grand Central Terminal and the adjoining streets Park Ave. East 42nd St. Vanderbilt Ave. Madison Ave. Lexington Ave. Grand Central Terminal ,ch01.21583 Page 2 Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. Static Routing | 3 D - EIGRP, EX - EIGRP external, O - OSPF, IA - OSPF inter area N1 - OSPF NSSA external type 1, N2 - OSPF NSSA external type 2 E1 - OSPF external type 1, E2 - OSPF external type 2, E - EGP i - IS-IS, L1 - IS-IS level-1, L2 - IS-IS level-2, * - candidate default Gateway of last resort is 0.0.0.0 to network 0.0.0.0 C 1.0.0.0/8 is directly connected, Ethernet0 10.0.0.0/8 is subnetted, 2 subnets C 10.1.1.0/24 is directly connected, Ethernet1 C 10.1.2.0/24 is directly connected, Ethernet2 Directly connected networks are automatically installed in the routing table if the interface to the network is up. Figure 1-2 shows router R with its directly connected networks. (The EXEC command show interface will show the state of the interfaces). In the previous example, it is assumed that all three interfaces to the directly con- nected networks are up. If an interface to a directly connected network goes down, the corresponding route is removed from the routing table. If multiple IP addresses are attached to an interface (using secondary addresses), all the associated networks are installed in the routing table. Static Routing Our Canadian friend has always wanted to see the New York Public Library. She gets directions at the information booth: “Make a right on 42nd Street; walk three blocks; look for the lions in front of the library.” The information-booth attendant may have no idea that the library is closed that day, or that the sidewalk on 42nd Street is blocked just then because of fire trucks and 41st Street may be the preferable route. The information booth has given the same directions to the library for the last hun- dred years and hopefully will for hundreds more—the route from Grand Central Sta- tion to the library, in other words, is static. In a similar vein, a network administrator can create a static route. So, to reach net- work 146.1.0.0, we may add the command: ip route 146.1.0.0 255.255.0.0 1.1.1.2 Figure 1-2. Router R with its directly connected networks Router R 1.0.0.0/8 10.1.1.0/24 10.1.2.0/24 ,ch01.21583 Page 3 Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. 4 | Chapter 1: Starting Simple which says to get to network 146.1.0.0/16, go to the next hop of 1.1.1.2. This speci- fies a fixed path to 146.1.0.0/16, as shown here, where the contents of the routing table are displayed using the EXEC command show ip route: R#sh ip route ... 1 S 146.1.0.0/16 [1/0] via 1.1.1.2 Even if 1.1.1.2 goes down, an alternate path—shown via R2 in Figure 1-3—cannot be used until a second static route is specified: ip route 146.1.0.0 255.255.0.0 1.1.1.3 The syntax of the static route command is: ip route network [mask] {address | interface} [distance] where network and mask specify the IP address and mask of the destination. The next hop may be specified by its IP address or by the interface on which to send the packet. To point a static route to an interface (Ethernet0 in this case), use: ip route 146.1.0.0 255.255.0.0 interface Ethernet0 Static routes are smart to the extent that if the next hop (interface or IP address) specified goes down, the router will remove the static route entry from the routing table. In line 1, the static route in the routing table is accompanied by “[1/0]”. This speci- fies the administrative distance and the metric associated with the route. We’ll dis- cuss distance and metrics in the next section. As should be obvious, static routing does not scale well. As the network grows, the task of maintaining static routes becomes more and more horrendous. Figure 1-3. Router R’s connectivity to 146.1.0.0 1.0.0.0/8 10.1.1.0/24 10.1.2.0/24 1.1.1.1 1.1.11.1.1.2 R2R1 R 146.1.0.0/16 ,ch01.21583 Page 4 Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. Dynamic Routing | 5 Dynamic Routing After the public library, our Canadian visitor jumps into a taxi to go crash at a friend’s place in Brooklyn. “Go over the Brooklyn Bridge,” she tells the driver. They head downtown. Suddenly, the driver slams on his brakes and makes an abrupt turn. Cars all around jam on their brakes, and pedestrians run hither and thither. “The radio said it is an hour to go over the bridge! We will take the tunnel!” the driver shouts to the back seat. This is an example of dynamic routing in a transportation system. What is dynamic routing in IP networks? Dynamic routing protocols allow each router to automatically discover one or more paths to each destination in the network. When the network topology changes, such as when new paths are added or when paths go out of service, dynamic routing protocols automatically adjust the contents of the routing table to reflect the new network topology. Dynamic routing relies on (frequent!) updates to discover changes in network topol- ogy. In the example in Figure 1-3, when the path R3 ➝ R4 is added to the network it can be automatically discovered by a routing protocol, such as RIP, EIGRP, or OSPF. The routing protocols in use today are based on one of two algorithms: Distance Vec- tor or Link State. Distance Vector (DV) algorithms broadcast routing information to all neighboring routers. In other words, each router tells all of its neighbors the routes it knows. When a router receives a route (from a neighbor) that is not in its routing table, it adds the route to its table; if the router receives a route that is already in its routing table, it keeps the shorter route in its table. DV algorithms are sometimes also described as routing by rumor: bad routing information propagates just as quickly as good information. Link State algorithms operate on a different par- adigm. First, each router constructs its own topological map of the entire network, based on updates from neighbors. Next, each router uses Dijkstra’s algorithm to compute the shortest path to each destination in this graph. Both DV and Link State algorithms are described in further detail in the chapters that follow. In the previous paragraph, we spoke of the “shorter” or “shortest” path in the con- text of both DV and Link State algorithms. Since a router may know of multiple paths to a destination, each routing protocol must provide a mechanism to discover the “shorter” or “shortest” path based on one or more of the following criteria: num- ber of hops, delay, throughput, traffic, reliability, etc. A metric is usually attached to this combination; lower metric values indicate “shorter” paths. For each routing pro- tocol discussed in the chapters that follow, we will describe how the route metric is computed. A network under a single administrative authority is described as an autonomous sys- tem (AS) in routing parlance. Interior gateway protocols (IGPs) are designed to sup- port the task of routing internal to an AS. IGPs have no concept of political boundaries ,ch01.21583 Page 5 Wednesday, January 9, 2002 12:23 PM

This is the Title of the Book, eMatter Edition Copyright © 2002 O’Reilly & Associates, Inc. All rights reserved. 6 | Chapter 1: Starting Simple between ASs or the metrics that may be used to select paths between ASs. RIP, IGRP, EIGRP, and OSPF are IGPs. Exterior gateway protocols (EGPs) are designed to sup- port routing between ASs. EGPs deploy metrics to select one inter-AS path over another. BGP is the most commonly used EGP. Routing architectures may be broadly classified as flat or hierarchical. Flat routing implies that all routes are known to all peers—all routers in the network are equal, possessing the same routing information. Hierarchical routing implies that some routers possess only local routes, whereas others possess a little bit more informa- tion, and still others possess even more. Let’s draw an analogy to the postal system. When I write a letter to a friend in India, the postman in the U.S. may have no idea where India is. He forwards all foreign mail to a designated post office in his state. That designated post office must know every postal system in the world. Such a system, in which some post offices are regional and some handle foreign mail, could be described as hierarchical. In large IP networks, only a few routers need to know every route in the network. These routers are sometimes described as core routers. Around the core routers is a layer of distribution routers that need not possess the complete routing table. When a distribution router receives a packet whose destination IP address does not appear in its local routing table, the distribution router simply forwards the packet to a core router. In the earlier example of the high school student in New Zealand accessing a web site in Sri Lanka, the small router in the high school in New Zealand probably has only a tiny routing table, with no routing entries for Sri Lanka. The high school router will forward all traffic for unknown destinations to another router, which in turn may for- ward the traffic to another one. Large IP networks exhibit several layers of hierarchy. As we will see in the chapters that follow, some routing protocols have features that make it easier to build hierarchies. These features include route aggregation, class- lessness, the use of default routes, and the flexibility with which routes can be exchanged with other routing protocols. RIP is an example of an almost completely flat routing protocol. OSPF exhibits sev- eral features that permit the design of hierarchical networks. As with any other algorithm, routing algorithms may also be categorized based on their complexity, flexibility, overhead, memory and CPU utilization, robustness, and stability. These properties of routing algorithms are of interest to the routing engi- neer, since he provides the (router) infrastructure to execute these algorithms. The Routing Table At Grand Central Terminal, a big wall lists all the destinations and their correspond- ing track numbers (see Figure 1-4). Passengers find their destination on this wall and ,ch01.21583 Page 6 Wednesday, January 9, 2002 12:23 PM