Exam Results Average 73 5 ROUTING PART 1 F D Max 94 C Min 39 Curve 7 B A Midterm Score 100 0 90 0 Internet Protocols 80 0 70 0 60 0 CSC ECE 573 50 0 Midterm Score 40 0 Fall 2005 30 0 20 0 N C State University 10 0 0 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 copyright 2005 Douglas S Reeves Distribution of Scores Today s Lecture I Interior Gateway Protocols 8 II RIPv2 6 III Improving Convergence Frequency IV OSPF 9 4 9 More 8 6 9 9 0 9 7 8 9 8 2 9 7 4 9 7 0 9 6 2 9 6 6 9 VI Message and link types 5 4 9 5 8 9 0 5 0 9 V 4 2 9 4 6 9 2 3 4 9 3 8 9 Frequency Histogram 4 2 Use of Hierarchy Bin copyright 2005 Douglas S Reeves copyright 2005 Douglas S Reeves 3 4 RIP v1 RFC1058 v2 RFC2453 Distance Vector interior gateway protocol with split horizon and poison reverse ROUTING INFORMATION PROTOCOL RIP Messages are transported over UDP unreliable delivery Initialization send request to all neighbors asking them for their complete routing table Neighbor discovery none just broadcast updates and hope they are being received copyright 2005 Douglas S Reeves 6 1 RIP Optimization Metric RIPv2 Message Format Metric minimum hop count Must be zero maximum allowable value 15 16 infinity consequences of network Administrators may set hopcount of a slow link to more than 1 consequences Distance to network No route will be installed unless it is strictly lower cost smaller hop count than the route it replaces prevents oscillation between equal cost routes copyright 2005 Douglas S Reeves RIP commands Request for routes 7 RIPv2 Message Contents Response i e distance vectors copyright 2005 Douglas S Reeves 8 Policy Controls Route Tag origin of a route Policy controls not supported by RIPv2 must be transmitted when route is propagated instead administrators manually configure route filters used by exterior gateway routing protocols i e which routing destinations are allowed to be installed in your routing table which routes will be propagated to other routers Next hop address used to eliminate extra forwarding hops at the edge of a RIP domain prevents loops and improves convergence time Subnet Mask supports variable length subnetbased routing copyright 2005 Douglas S Reeves 9 Other copyright 2005 Douglas S Reeves 10 RIP Timers Security v2 Periodic approximately randomly every 30 seconds optional 16 byte cleartext password in request response commands send complete routing table to your neighbors trivial to break Expiration if a route has not been updated or renewed for 180 seconds set its metric to infinity send this update to neighbors copyright 2005 Douglas S Reeves 11 copyright 2005 Douglas S Reeves 12 2 RIP Timers cont d RIP Timers cont d Garbage collection after another 120 seconds actually delete route from the routing table Triggered updates changes to route metric are propagated immediately instead of being required to wait until next broadcast interval ensures route invalidation is propagated throughout network before route stops being used another name Hold down period Propagates throughout network immediately disadvantages small delay before propagating to avoid generating excessive network traffic copyright 2005 Douglas S Reeves copyright 2005 Douglas S Reeves 13 14 Reliability Consistency in RIPv2 Reliability based solely on periodic frequent complete retransmission since routers do not have complete network topology cannot easily detect inconsistencies or loops copyright 2005 Douglas S Reeves 15 Split Horizon Algorithm N1 R1 Distance to network N1 link fails N2 IMPROVING CONVERGENCE Split Horizon with Poison Reverse SH with poison reverse router can advertise a route with distance N3 N4 N5 R2 R3 R4 R5 1 2 3 4 Initially 3 2 3 4 After 1 exchanges 7 6 7 6 After 5 exchanges i e poisons the route to N1 through R1 eliminates timer based slow timeout of route Assessment prevents routing loops involving only two routers Split horizon a router should not advertise to a neighbor a route for which that neighbor is the next hop drawback larger routing update messages must advertise all networks that can t be reached Example R3 does not advertise N1 to R2 copyright 2005 Douglas S Reeves 17 copyright 2005 Douglas S Reeves 18 3 Split Horizon cont d Does this completely eliminate loops OPEN SHORTEST PATH FIRST PROTOCOL OSPF copyright 2005 Douglas S Reeves 19 OSPF v2 RFC2328 OSPF v2 RFC2328 cont d Possible optimization metrics Recommended interior intra domain routing protocol for TCP IP hop count delay link state routing using Dijkstra s algorithm throughput etc Goals Load balancing possible 1 converges faster than RIP when several equal cost routes exist can send traffic along each of them 2 exchange less information than RIP 3 scale to larger networks just make sure all the packets for one TCP connection follow the same path Runs directly over IP not over UDP or TCP why not widely used copyright 2005 Douglas S Reeves 21 The LS Routing Algorithm copyright 2005 Douglas S Reeves 22 The LS Routing Algorithm cont d Each router does the following 1 Discovers the immediately adjacent neighbors 2 Builds an LSA containing distance to each of its neighbors 5 Creates a map of the network topology from these LSAs 6 Computes routes forwarding table from its map of the network topology 3 Broadcasts the LSA to all routers in the network using flooding 4 Stores the most recent LSA from every router in the network copyright 2005 Douglas S Reeves 23 copyright 2005 Douglas S Reeves 24 4 Flooding LSA to All Other Routers Flooding Example How get LSAs to all routers if the forwarding tables are not yet correct solution don t use forwarding tables use flooding Flooding from F to rest of network A B Inefficient method keep broadcasting until sure everyone has the information D C Efficient method broadcast only one time have to remember what you ve already broadcast E F every node sends information once to neighbors but not out the interface on which the information arrived copyright 2005 Douglas S Reeves 25 Link State Advertisement LSA Header 1 Link type later copyright 2005 Douglas S Reeves 26 LSA Sequence Number Originating router 2 Link ID starts LSA Sequence Number at smallest possible value 3 Advertising router increments Sequence Number of successive LSAs Non originating routers discard earlier LSA in favor of latest LSA from the originating router 4 Sequence number 5 Checksum 6 Age copyright 2005 Douglas S Reeves 27 LSA Age Field copyright 2005 Douglas S Reeves 28 LSA Age Field cont d Number of seconds