EE 122: Intra-domain routingInternet RoutingExampleIntra-domain Routing ProtocolsRoutingA Link State Routing AlgorithmDijsktra’s AlgorithmExample: Dijkstra’s AlgorithmSlide 9Slide 10Slide 11Slide 12Slide 13Dijkstra’s Algorithm: DiscussionDistance Vector Routing AlgorithmExample: Distance (Routing) TableRouting Table Forwarding TableDistance Vector Routing: OverviewDistance Vector AlgorithmDistance Vector Algorithm (cont’d)Example: Distance Vector AlgorithmSlide 22Slide 23Example: Distance Vector AlgorithmDistance Vector: Link Cost ChangesSlide 26Distance Vector: Poisoned ReverseLink State vs. Distance VectorEE 122: Intra-domain routingIon StoicaSeptember 30, 2002(* this presentation is based on the on-line slides of J. Kurose & K. Rose)[email protected] 2Internet RoutingInternet organized as a two level hierarchyFirst level – autonomous systems (AS’s)-AS – region of network under a single administrative domainAS’s run an intra-domain routing protocols-Distance Vector, e.g., RIP-Link State, e.g., OSPFBetween AS’s runs inter-domain routing protocols, e.g., Border Gateway Routing (BGP)-De facto standard today, [email protected] 3ExampleAS-1AS-2AS-3Interior routerBGP [email protected] 4Intra-domain Routing ProtocolsBased on unreliable datagram deliveryDistance vector-Routing Information Protocol (RIP), based on Bellman-Ford-Each neighbor periodically exchange reachability information to its neighbors-Minimal communication overhead, but it takes long to converge, i.e., in proportion to the maximum path lengthLink state-Open Shortest Path First Protocol (OSPF), based on Dijkstra-Each network periodically floods immediate reachability information to other routers-Fast convergence, but high communication and computation [email protected] 5RoutingGoal: determine a “good” path through the network from source to destination-Good means usually the shortest pathNetwork modeled as a graph-Routers nodes-Link edges•Edge cost: delay, congestion level,…[email protected] 6A Link State Routing Algorithm Dijkstra’s algorithmNet topology, link costs known to all nodes-Accomplished via “link state broadcast” -All nodes have same infoCompute least cost paths from one node (‘source”) to all other nodesIterative: after k iterations, know least cost path to k closest destinationsNotationsc(i,j): link cost from node i to j; cost infinite if not direct neighborsD(v): current value of cost of path from source to destination vp(v): predecessor node along path from source to v, that is next to vS: set of nodes whose least cost path definitively [email protected] 7Dijsktra’s Algorithm1 Initialization: 2 S = {A};3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v); 6 else D(v) = ;7 8 Loop 9 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) );13 // new cost to v is either old cost to v or known 14 // shortest path cost to w plus cost from w to v 15 until all nodes in S; [email protected] 8Example: 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[email protected] 9Example: 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[email protected] 10Example: 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[email protected] 11Example: 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[email protected] 12Example: 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[email protected] 13Example: 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[email protected] 14Dijkstra’s Algorithm: DiscussionAlgorithm complexity: n nodes-Each iteration: need to check all nodes, w, not in S-n*(n+1)/2 comparisons: O(n**2)-More efficient implementations possible: O(n*log(n))Oscillation possible-E.g., link cost = amount of carried traffic ADCB11+ee0e1100initiallyADCB2+e0001+e1… recomputeroutingADCB02+e1+e100… recomputeADCB2+e0e01+e1… [email protected] 15Distance Vector Routing AlgorithmIterative: continues until no nodes exchange infoAsynchronous: nodes need not exchange info/iterate in lock step!Distributed: each node communicates only with directly-attached neighborsRouting (distance) table data structure – each router maintains-Row for each possible destination-Column for each directly-attached neighbor to node-Entry in row Y and column Z of node X distance from X to Y, via Z as next hop)},({min),(),( wZDZXcZYDZwX[email protected] 16Example: Distance (Routing) TableAEDCB681212D ()ABCDA1764B148911D5542Ecost to destination viadestinationD (C,D)Ec(E,D) + min {D (C,w)}Dw==2+2 = 4D (A,D)Ec(E,D) + min {D (A,w)}Dw==2+3 = 5D (A,B)Ec(E,B) + min {D (A,w)}Bw==8+6 = [email protected] 17Routing Table Forwarding Table D ()ABCDA1764B148911D5542Ecost to destination viadestination ABCD A,1D,5D,4D,2Outgoing link to use, costdestinationDistance (routing) tableForwarding [email protected] 18Distance Vector Routing: OverviewEach local iteration caused by: -Local link cost change -Message from neighbor: its least cost path change from neighborEach node notifies neighbors only when its least cost path to any destination changes-Neighbors then notify their neighbors if necessarywait for (change in local link cost of msg from neighbor)recompute distance tableif least cost path to any dest has changed, notify neighbors Each node:[email protected] 19Distance Vector Algorithm1 Initialization: 2 for all adjacent nodes v: 3 D (*,v) = /* the * operator means "for all rows" */ 4 D (v,v) = c(X,v) 5 for all destinations, y 6 send min D (y,w) to each neighbor /* w over all X's neighbors */ XXXwAt all nodes, X:[email protected]
View Full Document
Unlocking...