11Shortest-Path RoutingReading: Sections P&D 4.2EE122: Intro to Communication NetworksFall 2006 (MW 4:00-5:30 in Donner 155)Vern PaxsonTAs: Dilip Antony Joseph and Sukun Kimhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica and colleagues atPrinceton and UC Berkeley2What we have learnt so far …• Sending IP packets from source to destinationthrough a series of routers– Router looks up destination IP address in a table– Forwards the packet to the corresponding next hop• Sending Ethernet frames from source todestination through a series of switches– Switch looks up destination MAC address in a table– Forwards the frame on the corresponding port• What important task did we NOT talk about?– How are these forwarding tables filled with information?– Routing• What about self-learning in switches?3What is Routing?• A famous quotation from RFC 791 “A name indicates what we seek.An address indicates where it is.A route indicates how we get there.” -- Jon Postel4Why Does Routing Matter?• We need good end-to-end performance–Find the shortest/best path 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, and load balancing–Limit packet loss and delay during changes5• 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 only local 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: RIP6Modeling a Network• Modeled as a graph– Routers nodes– Link edges Edge cost• delay• congestion level• Goal of Routing– Determine a “good” path through the network from source todestination– Good means usually the shortest pathAEDCBF221311253527• Each router has a complete picture of the network• How does each router get the global state?– Each router reliably floods information about its neighbors to everyother router (more later)• Each router independently calculates the shortest path fromitself to every other router– Dijkstra’s Shortest Path AlgorithmLink State RoutingHost AHost BHost EHost DHost CN1N2N3N4N5N7N6ABEDCABEDCABEDCABEDCABEDCABEDCABEDC8Dijkstra’s Shortest Path Algorithm• Named after Edsger W. Dijkstra (1930-2002)• INPUT– Net topology, link costs known to all nodes• OUTPUT– Least cost paths from one node (“source”) to all other nodes9Notation• c(i,j): link cost from node ito j; cost infinite if notdirect neighbors• 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 D(v) = min( D(v), D(w) + c(w,v) ); // new cost to v is either old cost to v or known // shortest-path cost to w plus cost from w to v13 until all nodes in S;!11Example: 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 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 D(v) = min( D(v), D(w) + c(w,v) );13 until all nodes in S;313Example: 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 D(v) = min( D(v), D(w) + c(w,v) );13 until all nodes in S;14Example: 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 D(v) = min( D(v), D(w) + c(w,v) );13 until all nodes in S;15Example: 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 D(v) = min( D(v), D(w) + c(w,v) );13 until all nodes in S;16Example: Dijkstra’s AlgorithmStep012345start SAADADEADEBADEBCADEBCFD(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 D(v) = min( D(v), D(w) + c(w,v) );13 until all nodes in S;17• Running Dijkstra at node A gives the shortest path from A to alldestinations• We then construct the forwarding table• Why have separate routing and forwarding tables?The Forwarding TableAEDCBF2213112535(A,D)F(A,D)E(A,D)D(A,D)C(A,B)BLinkDestination18Complexity• How much processing does running the Dijkstraalgorithm take?• Assume a network consisting of n nodes– Each iteration: need to check all nodes, w, not in S– n*(n+1)/2 comparisons: O(n2)– More efficient implementations possible: O(n*log(n))419Oscillations• Assume link cost = amount of carried trafficADCB11+ee0e1100initiallyADCB2+e0001+e1… recomputeroutingADCB02+e1+e100… recomputeADCB2+e0e01+e1… recompute How can you avoid
View Full Document
Unlocking...