115-441 Computer NetworkingLecture 10: Intra-Domain RoutingRIP (Routing Information Protocol) & OSPF (Open Shortest Path First)IP Forwarding• The Story So Far… • IP addresses are structure to reflect Internet structure• IP packet headers carry these addresses• When Packet Arrives at Router• Examine header to determine intended destination• Look up in table to determine next hop in pathRouter9/28/2006Lecture 10: Intra-Domain Routing 2in path• Send packet out appropriate port• This/next lecture• How to generate the forwarding tableGraph Model• Represent each router as node• Direct link between routers represented by edgeStilikdi t d h•Symmetric links ⇒ undirected graph• Edge “cost” c(x,y) denotes measure of difficulty of using link• delay, $ cost, or congestion level• Task• Determine least cost path from every node to every other node• Path cost d(x,y) = sum of link costsE C39/28/2006Lecture 10: Intra-Domain Routing 3AFDB23641113Routes from Node AE C31Forwarding Table for ADest Cost Next HAFDB264113HopA0AB4BC6ED7BE2EF5E9/28/2006Lecture 10: Intra-Domain Routing 4• Properties• Some set of shortest paths forms tree• Shortest path spanning tree• Solution not unique• E.g., A-E-F-C-D also has cost 72Ways to Compute Shortest Paths• Centralized• Collect graph structure in one placeUse standard graph algorithm•Use standard graph algorithm• Disseminate routing tables• Distance-vector• No one has copy of graph• Nodes construct their own tables iteratively• Each sends information about its table to neighbors9/28/2006Lecture 10: Intra-Domain Routing 5• Link-state• Every node collects complete graph structure• Each computes shortest paths from it• Each generates own routing tableOutline•Distance Vector•Distance Vector• Link State• Routing Hierarchy9/28/2006Lecture 10: Intra-Domain Routing 6Distance-Vector MethodE C31Initial Table for ADest Cost Next HopIdAFDB264113pA0AB4BC ∞ –D ∞ –E2EF6F9/28/2006Lecture 10: Intra-Domain Routing 7•Idea• At any time, have cost/next hop of best known path to destination• Use cost ∞ when no path known• Initially• Only have entries for directly connected nodesDistance-Vector Updatezc(x z)d(z,y)• Update(x,y,z)d ← c(x,z) + d(z,y)# Cost of path from x to y with first hop zxyc(x,z)d(x,y)9/28/2006Lecture 10: Intra-Domain Routing 8() (y)if d < d(x,y)# Found better pathreturn d,z # Updated cost / next hopelsereturn d(x,y), nexthop(x,y) # Existing cost / next hop3Algorithm• Bellman-Ford algorithm•Repeat•RepeatFor every node xFor every neighbor zFor every destination yd(x,y) ← Update(x,y,z)•Until converge9/28/2006Lecture 10: Intra-Domain Routing 9•Until convergeStartE C31Table for ADst Cst HopTable for BDst Cst HopOptimum 1-hop pathsAFDB264113A0AB4BC∞–D∞–E2EF6FA4AB0BC∞–D3DE∞–F1FTable for CDstCstHopTable for DDstCstHopTable for EDstCstHopTable for FDstCstHop9/28/2006Lecture 10: Intra-Domain Routing 10DstCstHopA∞–B∞–C0 CD1 DE∞–F1 FDstCstHopA∞–B3BC1CD0DE∞–F∞–DstCstHopA2AB∞–C∞–D∞–E0EF3FDstCstHopA6AB1BC1CD∞–E3EF0FIteration #1Table for ADst Cst HopTable for BDst Cst HopOptimum 2-hop pathsE C31A0AB4BC 7FD 7BE2EF 5EA4AB0BC 2FD3DE 4FF1FTable for CDstCstHopTable for DDstCstHopTable for EDstCstHopTable for FDstCstHopAFDB2641139/28/2006Lecture 10: Intra-Domain Routing 11DstCstHopA 7FB 2FC0CD1DE 4FF1FDstCstHopA 7BB3BC1CD0DE∞–F 2CDstCstHopA2AB 4FC 4FD∞–E0EF3FDstCstHopA 5BB1BC1CD 2CE3EF0FIteration #2Table for ADst Cst HopTable for BDst Cst HopOptimum 3-hop pathsE C31A0AB4BC 6ED7BE2EF5EA4AB0BC2FD3DE4FF1FTable for CDstCstHopTable for DDstCstHopTable for EDstCstHopTable for FDstCstHopAFDB2641139/28/2006Lecture 10: Intra-Domain Routing 12DstCstHopA 6 FB2FC0CD1DE4FF1FDstCstHopA7BB3BC1CD0DE 5CF2CDstCstHopA2AB4FC4FD 5FE0EF3FDstCstHopA5BB1BC1CD2CE3EF0F4Distance Vector: Link Cost ChangesLink cost changes:• Node detects local link cost change 14Y1• Updates distance table • If cost change in least cost path, notify neighborsXZ1450algorithmterminates“goodnews 9/28/2006Lecture 10: Intra-Domain Routing 13travelsfast”Distance Vector: Link Cost ChangesLink cost changes:• Good news travels fast 14Y60• Bad news travels slow -“count to infinity” problem!XZ1450algorithmcontinueson!9/28/2006Lecture 10: Intra-Domain Routing 14Distance Vector: Split HorizonIf Z routes through Y to get to X :• Z does not advertise its route to X back to Y14Y60algorithmterminatesXZ50? ? ?9/28/2006Lecture 10: Intra-Domain Routing 15Distance Vector: Poison ReverseIf Z routes through Y to get to X :• Z tells Y its (Z’s) distance to X is infinite (so Y won’t ttXiZ)14Y60route to X via Z)• Eliminates some possible timeouts with split horizon• Will this completely solve count to infinity problem? XZ50algorithmterminates9/28/2006Lecture 10: Intra-Domain Routing 165Poison Reverse FailuresTable for ADst Cst HopC7FTable for BDst Cst HopC8ATable for FDst Cst HopC1CTable for DDst Cst HopC9B•Iterations don’t convergeTable for FDst Cst HopC ∞ –Table for ADst Cst HopC ∞ –ForcedUpdateTable for BDtCtHForcedF C6111BDA4∞∞ForcedUpdateTable for ADst Cst HopC 13 DBetterRoute9/28/2006Lecture 10: Intra-Domain Routing 17•Iterations don t converge• “Count to infinity”• Solution• Make “infinity” smaller• What is upper bound on maximum path length?DstCstHopC14AUpdateTable for DDst Cst HopC15BTable for ADst Cst HopC 19 DForcedUpdate•••ForcedUpdateRouting Information Protocol (RIP)• Earliest IP routing protocol (1982 BSD)•Current standard is version 2 (RFC 1723) which Current standard is version 2 (RFC 1723) which includes CIDR• Features• Every link has cost 1• “Infinity” = 16• Limits to networks where everything reachable within 15 hops9/28/2006Lecture 10: Intra-Domain Routing 1815 hops• Sending Updates• Every router listens for updates on UDP port 520• RIP message can contain entries for up to 25 table entriesRIP Updates• Initial• When router first starts, asks for copy of table for every neighborpy y g• Uses it to iteratively generate own table• Periodic• Every 30 seconds, router sends copy of its table to each neighbor• Neighbors use to iteratively update their tables• Triggered•When every entry changes, send copy of entry to neighbors9/28/2006Lecture 10: Intra-Domain Routing 19When every entry changes, send copy of entry to neighbors• Except for one causing update
View Full Document
Unlocking...