TDC375 Winter 2002 John Kristoff DePaul University Routing Network Protocols 1 TDC375 Winter 2002 John Kristoff DePaul University 2 Route determined by destination IP address Forwarding decision on a hop by hop basis Table information base driven Performed by routers IP routing TDC375 Winter 2002 John Kristoff DePaul University Send datagram to F Create layer 2 information 3 Extract fowarding address F for next hop Find best match for D in the routing table Extract destination IP address D Remove layer 2 information For an IP datagram received on an interface Basic IP forwarding process TDC375 Winter 2002 John Kristoff DePaul University 4 Since each entry in a routing table represents an IP network the size of the routing table is proportional to the number of IP networks known throughout the entire internetwork IP routing tables TDC375 Winter 2002 John Kristoff DePaul University IP routing table illustrated 5 Generating routing tables TDC375 Winter 2002 John Kristoff DePaul University 6 Catastrophic distributed failures are possible Useful for large multi path networks Allows quick re routing around failed nodes links Dynamically Useful for permanent route entries Does not scale well Simple for small single path networks Manually TDC375 Winter 2002 John Kristoff DePaul University IP routing illustrated 7 TDC375 Winter 2002 John Kristoff DePaul University 8 IP routing illustrated continued TDC375 Winter 2002 John Kristoff DePaul University Policy decisions Best worst latency Lowest highest reliability Lowest highest cost path Shortest longest hop path Routing metrics 9 Some terminology TDC375 Winter 2002 John Kristoff DePaul University Routing protocol used between ASes Exterior gateway protocols EGP Routing protocol used within an AS Interior gateway protocols IGP A network or set of networks that is administrated by a single entity Autonomous system AS 10 Distance vector routing TDC375 Winter 2002 John Kristoff DePaul University 11 Also known as Bellman Ford after inventors of the algorithm Advertise learned routes Learn from other router advertisements Periodically advertise attached networks out each link e g 4 hops to network XYZ 2 hops to ABC Each node maintains distance to destination TDC375 Winter 2002 John Kristoff DePaul University Distance vector illustrated 12 TDC375 Winter 2002 John Kristoff DePaul University Distance vector illustrated continued 13 TDC375 Winter 2002 John Kristoff DePaul University Distance vector illustrated converged 14 TDC375 Winter 2002 John Kristoff DePaul University What happens when link to A fails 15 Also known as the count to infinity problem Convergence time can be slow Problems with distance vector Solving count to infinity TDC375 Winter 2002 John Kristoff DePaul University 16 Do not advertise route to a neighbor if you received route from that neighbor Not foolproof Split horizon Guarantees no loops but expensive Report the entire path Advertise infinity for route and wait a period of time before switching routes Hope that news of the downed link will spread fast enough Kludge Hold down Other distance vector improvements TDC375 Winter 2002 John Kristoff DePaul University 17 Somewhat like hold down Can switch paths if new distance is lower Sufficiently complex DUAL Used with split horizon advertise infinity rather than nothing at all Poison reverse Advertise changes immediately May cause route flapping but generally a good thing to do Triggered updates TDC375 Winter 2002 John Kristoff DePaul University 15 hop limit any greater equals infinity 18 Widely used as an IGP RIPv2 particulary Route times out after 180 seconds default UDP broadcast every 30 seconds default Slow convergence time Very simple The later defines RIPv2 for improvements Standardized in RFC 1058 and 2453 Routing information protocol RIP RIP version 2 RIPv2 TDC375 Winter 2002 Next hop router associated with advertisement John Kristoff DePaul University 19 Next hop option For interaction with external gateway protocols Route tag option Uses IP multicast destination address Support for authentication Needed to support classless addressing Most important new feature was to include the subnet mask with the advertised route TDC375 Winter 2002 John Kristoff DePaul University 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 address family identifier 2 must be zero 2 IPv4 address 4 must be zero 4 A RIPv1 entry has the following format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 command 1 version 1 must be zero 2 RIP Entry 20 Packet format RIPv1 packet format 20 TDC375 Winter 2002 John Kristoff DePaul University 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 Command 1 Version 1 unused Authentication uses one entry of the format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 Address Family Identifier 2 Route Tag 2 IP Address 4 Subnet Mask 4 Next Hop 4 Metric 4 Packet format is the same RIPv2 entry format is RIPv2 packet format 21 Link state routing TDC375 Winter 2002 John Kristoff DePaul University Ensures a loop free environment Protocol complexity is high Convergence time is very short 22 Each router computes its own optimal path to a destination network Link state packets are flooded to all area routers All routers have complete network topology information database within their area TDC375 Winter 2002 John Kristoff DePaul University Link state routing illustrated 23 Link state routing databases TDC375 Winter 2002 John Kristoff DePaul University Contains ID and forwarding direction Forwarding database Same structure as PATH its entries may be candidates to move into PATH TENT tentative database 24 Contains router ID path cost forwarding direction triples PATH permanent database Contains latest link state packet from each router Link state database Dijkstra s algorithm TDC375 Winter 2002 John Kristoff DePaul University 25 If TENT is empty exit otherwise find ID with lowest path cost and in TENT and move it to PATH For each node in PATH examine its LSP and place those neighbors in TENT if not already in PATH or TENT my ID path cost 0 forwarding direction 0 in PATH Start with self as root of the tree TDC375 Winter 2002 6 TENT is empty terminate John Kristoff DePaul University 5 E is lowest path cost in TENT place E in PATH examine E s LSP no better paths 4 C is lowest path cost in TENT place C in PATH exame C s LSP found better E path again 3 D is lowest path cost in TENT place D
View Full Document