11Shortest-Path RoutingEE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Guest lecturer next Wednesday: Brighten Godfrey• I will have office hours as usual next Friday, butnot next Wednesday– Send email for an appointment M/Tu/Th• Section next week will cover Spanning Treealgorithm (plus questions re routing algorithms)– Do attend (as usual!)23Goals of Today’s Lecture• Routing vs. forwarding–“Control plane” vs. “Data plane”• Link-state routing (Dijkstra’s algorithm)–Suitable as Interior Gateway Protocol (IGP)o i.e., used within a single ISP• Topology change - detection & convergence• Distance-vector routing (Bellman-Ford)≈Suitable as Exterior Gateway Protocol (EGP)o Between ISPso Though really need something more• BGP - next lecture4Forwarding vs. Routing• Forwarding: “data plane”–Directing a data packet to an outgoing link–Individual router using a forwarding table• Routing: “control plane”–Computing paths the packets will follow–Routers talking amongst themselves–Individual router creating a forwarding table35Why Does Routing Matter?• We need good end-to-end performance–Find the shortest/best patho Propagation delay, throughput, packet loss• Ensure efficient use of network resources–Balance traffic over the routers and links–Avoid congestion by directing traffic to lightly-loaded links• Withstand disruptions–Failures, maintenance, load balancing–Limit packet loss and delay during changes6• Routing requires knowledge of the network structure• Centralized global state– Single entity knows the complete network structure– Can calculate all routes centrally– Problems with this approach?• Distributed global state– Every router knows the complete network structure– Independently calculates routes– Problems with this approach?• Distributed no-global state– Every router knows only about its neighboring routers– Independently calculates routes– Problems with this approach?Know Thy NetworkLink State RoutingE.g. Algorithm: DijkstraE.g. Protocol: OSPFDistance Vector RoutingE.g. Algorithm: Bellman-FordE.g. Protocol: RIP47Modeling a Network• Modeled as a graph– Routers ⇒ nodes– Link ⇒ edgeso Possible edge costs• delay• congestion level• Goal of Routing– Determine a “good” path through the network from source todestination– Good usually means the shortest pathAEDCBF22131125358• Each router has a complete picture of thenetwork• How does each router get the global state?–Each router reliably floods information about itsneighbors to every other router (more later)• Each router independently calculates theshortest path from itself to every other router–Dijkstra’s Shortest Path Algorithm– INPUT:o Network topology (graph), link costs known to all nodes– OUTPUT:o Least cost paths from one node (“source”) to all other nodesLink State Routing59Notation• c(i,j): link cost from node ito j; cost infinite if notdirect neighbors; ≥ 0• D(v): current value of costof path from source todestination v• p(v): predecessor nodealong path from source tov, that is next to v• S: set of nodes whoseleast cost path definitivelyknownAEDCBF2213112535Source10Dijsktra’s Algorithm1 Initialization:2 S = {A};3 for all nodes v4 if v adjacent to A5 then D(v) = c(A,v);6 else D(v) = ;78 Loop9 find w not in S such that D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in S:12 if D(w) + c(w,v) < D(v) then // w gives us a shorter path to v than we’ve found so far13 D(v) = D(w) + c(w,v); p(v) = w;14 until all nodes in S;!• c(i,j): link cost from node i to j• D(v): current cost source → v• p(v): predecessor node alongpath from source to v, that isnext to v• S: set of nodes whose leastcost path definitively known611Example: Dijkstra’s AlgorithmStep012345start SAD(B),p(B)2,AD(C),p(C)5,AD(D),p(D)1,AD(E),p(E)D(F),p(F)AEDCBF2213112535!!1 Initialization:2 S = {A};3 for all nodes v4 if v adjacent to A5 then D(v) = c(A,v);6 else D(v) = ;…!12Example: Dijkstra’s AlgorithmStep012345start SAD(B),p(B)2,AD(C),p(C)5,A…8 Loop9 find w not in S s.t. D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in S:12 If D(w) + c(w,v) < D(v) then13 D(v) = D(w) + c(w,v); p(v) = w;14 until all nodes in S;AEDCBF2213112535D(D),p(D)1,AD(E),p(E)D(F),p(F)!!713Example: Dijkstra’s AlgorithmStep012345start SAADD(B),p(B)2,AD(C),p(C)5,AD(D),p(D)1,AD(E),p(E)D(F),p(F)AEDCBF2213112535!!…8 Loop9 find w not in S s.t. D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in S:12 If D(w) + c(w,v) < D(v) then13 D(v) = D(w) + c(w,v); p(v) = w;14 until all nodes in S;14Example: Dijkstra’s AlgorithmStep012345start SAADD(B),p(B)2,AD(C),p(C)5,A4,DD(D),p(D)1,AD(E),p(E)2,DD(F),p(F)AEDCBF2213112535!!…8 Loop9 find w not in S s.t. D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in S:12 If D(w) + c(w,v) < D(v) then13 D(v) = D(w) + c(w,v); p(v) = w;14 until all nodes in S;815Example: Dijkstra’s AlgorithmStep012345start SAADADED(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,E!!AEDCBF2213112535…8 Loop9 find w not in S s.t. D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in S:12 If D(w) + c(w,v) < D(v) then13 D(v) = D(w) + c(w,v); p(v) = w;14 until all nodes in S;16Example: Dijkstra’s AlgorithmStep012345start SAADADEADEBD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,E!!AEDCBF2213112535…8 Loop9 find w not in S s.t. D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in S:12 If D(w) + c(w,v) < D(v) then13 D(v) = D(w) + c(w,v); p(v) = w;14 until all nodes in S;917Example: Dijkstra’s AlgorithmStep012345start SAADADEADEBADEBCD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,E!!AEDCBF2213112535…8 Loop9 find w not in S s.t. D(w) is a minimum;10 add w to S;11 update D(v) for all v adjacent to w and not in S:12 If
View Full Document
Unlocking...