1ROUTING, PART 1Internet ProtocolsCSC / ECE 573Fall, 2005N. C. State Universitycopyright 2005 Douglas S. Reeves2Exam ResultsMidterm Score0.010.020.030.040.050.060.070.080.090.0100.01 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43Midterm Score7399473.5+ CurveMinMaxAverageAABBCCDDFFcopyright 2005 Douglas S. Reeves3Distribution of ScoresHistogram0246834.938.942.946.950.954.958.962.966.970.974.978.982.986.990.994.9MoreBinFrequencyFrequencycopyright 2005 Douglas S. Reeves4Today’s LectureI. Interior Gateway ProtocolsII. RIPv2III. Improving ConvergenceIV. OSPFV. Use of HierarchyVI. Message and link typesROUTING INFORMATIONPROTOCOL (RIP)copyright 2005 Douglas S. Reeves6RIP (v1:RFC1058, v2: RFC2453)• Distance-Vector, interior gateway protocol– with split horizon and poison reverse• Messages are transported over UDP– unreliable delivery• Initialization– send request to all neighbors asking them for theircomplete routing table• Neighbor discovery: none!– just broadcast updates and hope they are beingreceived2copyright 2005 Douglas S. Reeves7RIP Optimization Metric• Metric = minimum hop count– maximum allowable value = 15 (16=“infinity”)– consequences?• Administrators may set hopcount of a slow link tomore than 1– consequences?• No route will be installed unless it is strictly lowercost (smaller hop-count) than the route it replaces– prevents oscillation between equal cost routescopyright 2005 Douglas S. Reeves8RIPv2 Message FormatMust be zeroof networkDistance to network• RIP commands– Request for routes– Response (i.e., distance vectors)copyright 2005 Douglas S. Reeves9RIPv2 Message Contents• Route Tag: origin of a route– must be transmitted when route is propagated– (used by exterior gateway routing protocols)• Next-hop address: used to eliminate extraforwarding hops at the edge of a RIP domain– prevents loops and improves convergence time• Subnet Mask supports variable-length subnet-based routingcopyright 2005 Douglas S. Reeves10Policy Controls• Policy controls not supported by RIPv2– instead, administrators manually configure route “filters”– i.e., which routing destinations are allowed to beinstalled in your routing table, which routes will bepropagated to other routerscopyright 2005 Douglas S. Reeves11Other• Security (v2)– optional 16 byte cleartext password in request /response commands– trivial to break copyright 2005 Douglas S. Reeves12RIP Timers• Periodic: approximately (randomly) every 30seconds…– send complete routing table to your neighbors• Expiration: if a route has not been updated orrenewed for 180 seconds…– set its metric to infinity– send this update to neighbors3copyright 2005 Douglas S. Reeves13RIP Timers (cont’d)• Garbage collection: after another 120 seconds…– actually delete route from the routing table– ensures route invalidation is propagated throughoutnetwork before route stops being used– another name: “Hold-down” period– disadvantages?copyright 2005 Douglas S. Reeves14RIP Timers (cont’d)• Triggered updates: changes to route metric arepropagated immediately– instead of being required to wait until next broadcastinterval• Propagates throughout network immediately– small delay before propagating, to avoid generatingexcessive network trafficcopyright 2005 Douglas S. Reeves15Reliability / Consistency in RIPv2• Reliability– based solely on periodic (frequent) completeretransmission– since routers do not have complete network topology,cannot easily detect inconsistencies or loopsIMPROVING CONVERGENCEcopyright 2005 Douglas S. Reeves17Split Horizon Algorithm• Split horizon: a router should not advertise to aneighbor a route for which that neighbor is the nexthop• Example: R3 does not advertise N1 to R2Distance tonetwork N1 N1 N2 N3 N4 N5R1 R2 R3 R4 R5After 1 exchanges4323Initially4321After 5 exchanges6767link fails…....…....…....copyright 2005 Douglas S. Reeves18Split Horizon with Poison Reverse• SH with poison reverse: router can advertise aroute with distance ∞– i.e., “poisons” the route to N1 through R1– eliminates timer-based (slow) timeout of route• Assessment– prevents routing loops involving only two routers– drawback: larger routing update messages (mustadvertise all networks that can't be reached)4copyright 2005 Douglas S. Reeves19Split Horizon (cont'd)• Does this completely eliminate loops?OPEN SHORTEST PATH FIRSTPROTOCOL (OSPF)copyright 2005 Douglas S. Reeves21OSPF (v2:RFC2328)• “Recommended” interior (intra-domain) routingprotocol for TCP/IP– link state routing using Dijkstra's algorithm• Goals1.converges faster than RIP2.exchange less information than RIP3.scale to larger networks• Runs directly over IP (not over UDP or TCP)copyright 2005 Douglas S. Reeves22OSPF (v2:RFC2328) (cont’d)• Possible optimization metrics– hop-count– delay– throughput, etc.• Load-balancing possible– when several equal-cost routes exist, can send trafficalong each of them– just make sure all the packets for one TCP connectionfollow the same path• why?– (not widely used)copyright 2005 Douglas S. Reeves23The LS Routing AlgorithmEach router does the following1. Discovers the (immediately adjacent) neighbors2. Builds an LSA containing distance to each of itsneighbors3. Broadcasts the LSA to all routers in the network(using flooding)4. Stores the most recent LSA from every router inthe networkcopyright 2005 Douglas S. Reeves24The LS Routing Algorithm (cont’d)5. Creates a “map” of the network topology fromthese LSAs6. Computes routes (forwarding table) from itsmap of the network topology5copyright 2005 Douglas S. Reeves25Flooding LSA to All Other Routers• How get LSAs to all routers if the forwarding tablesare not (yet) correct?– solution: don’t use forwarding tables, use flooding• Inefficient method: keep broadcasting until sureeveryone has the information• Efficient method: broadcast only one time– have to remember what you’ve already broadcast– every node sends information once to neighbors• but not out the interface on which the information arrivedcopyright 2005 Douglas S. Reeves26“Flooding” ExampleACBFDE• Flooding from F to rest of networkcopyright 2005 Douglas S. Reeves27Link State Advertisement (LSA) Header1. Link type (later)2. Link ID3. Advertising router4. Sequence number5. Checksum6. Agecopyright 2005 Douglas S. Reeves28LSA Sequence Number•