13 –Routing ProtocolsSlide 2Interplay between routing and forwardingGraph abstractionGraph abstraction: costsA Link-State Routing AlgorithmDijsktra’s AlgorithmDijkstra’s algorithm: exampleDijkstra’s algorithm, discussionDistance Vector Algorithm (1)Bellman-Ford example (2)Distance Vector Algorithm (3)Distance vector algorithm (4)Distance Vector Algorithm (5)Example using DVsSlide 16Slide 17Slide 18Comparison of LS and DV algorithms13 –Routing ProtocolsNetwork Layer 4-1Network Layer 4-2Chapter 4Network LayerComputer Networking: A Top Down Approach Featuring the Internet, 3rd edition. Jim Kurose, Keith RossAddison-Wesley, July 2004. A note on the use of these ppt slides:We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, we’d like people to use our book!) If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material.Thanks and enjoy! JFK/KWRAll material copyright 1996-2004J.F Kurose and K.W. Ross, All Rights ReservedNetwork Layer 4-31230111value in arrivingpacket’s headerrouting algorithmlocal forwarding tableheader valueoutput link01000101011110013221Interplay between routing and forwardingNetwork Layer 4-4uyxwvz2213112535Graph: G = (N,E)N = set of routers = { u, v, w, x, y, z }E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }Graph abstractionRemark: Graph abstraction is useful in other network contextsExample: P2P, where N is set of peers and E is set of TCP connectionsNetwork Layer 4-5Graph abstraction: costsuyxwvz2213112535• c(x,x’) = cost of link (x,x’) - e.g., c(w,z) = 5• cost could always be 1, or inversely related to bandwidth,or inversely related to congestionCost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) Question: What’s the least-cost path between u and z ?Routing algorithm: algorithm that finds least-cost pathNetwork Layer 4-6A Link-State Routing AlgorithmDijkstra’s algorithmnet topology, link costs known to all nodesaccomplished via “link state broadcast” all nodes have same infocomputes least cost paths from one node (‘source”) to all other nodesgives forwarding table for that nodeiterative: after k iterations, know least cost path to k dest.’sNotation:c(x,y): link cost from node x to y; = ∞ if not direct neighborsD(v): current value of cost of path from source to dest. vp(v): predecessor node along path from source to vN': set of nodes whose least cost path definitively knownNetwork Layer 4-7Dijsktra’s Algorithm1 Initialization: 2 N' = {u} 3 for all nodes j 4 if j adjacent to u 5 then D(j) = c(u,j) 6 else D(j) = ∞ 7 8 Loop 9 find m not in N' such that D(m) is a minimum 10 add m to N' 11 update D(j) for all j adjacent to m and not in N' : 12 D(j) = min( D(j), D(m) + c(m,j) ) 13 /* new cost to j is either old cost to j or known 14 shortest path cost to m plus cost from m to j */ 15 until all nodes in N' uyxwvz2213112535Network Layer 4-8Dijkstra’s algorithm: exampleStep012345N'uuxuxyuxyvuxyvwuxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)∞2,xD(z),p(z)∞ ∞ 4,y4,y4,yuyxwvz2213112535Network Layer 4-9Dijkstra’s algorithm, discussionAlgorithm complexity: n nodeseach iteration: need to check all nodes, w, not in Nn(n+1)/2 comparisons: O(n2)more efficient implementations possible: O(nlogn)Network Layer 4-10Distance Vector Algorithm (1)Bellman-Ford Equation (dynamic programming)Definedx(y) := cost of least-cost path from x to yThendx(y) = min {c(x,v) + dv(y) }where min is taken over all neighbors of xNetwork Layer 4-11Bellman-Ford example (2)uyxwvz2213112535Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4Node that achieves minimum is nexthop in shortest path ➜ forwarding tableB-F equation says:Network Layer 4-12Distance Vector Algorithm (3)Dx(y) = estimate of least cost from x to yDistance vector: Dx = [Dx(y): y є N ]Node x knows cost to each neighbor v: c(x,v)Node x maintains Dx = [Dx(y): y є N ]Node x also maintains its neighbors’ distance vectorsFor each neighbor v, x maintains Dv = [Dv(y): y є N ]Network Layer 4-13Distance vector algorithm (4)Basic idea: Each node periodically sends its own distance vector estimate to neighborsWhen a node x receives new DV estimate from neighbor, it updates its own DV using B-F equation:Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ NUnder minor, natural conditions, the estimate Dx(y) converge the actual least cost dx(y)Network Layer 4-14Distance Vector Algorithm (5)Iterative, asynchronous: each local iteration caused by: local link cost change DV update message from neighborDistributed:each node notifies neighbors only when its DV changesneighbors then notify their neighbors if necessarywait for (change in local link cost or msg from neighbor)recompute estimatesif DV to any dest has changed, notify neighbors Each node:Network Layer 4-15Example using DVsxz127yx y zxyz0 2 7∞ ∞ ∞∞ ∞ ∞fromcost tonode x tableNetwork Layer 4-16x y zxyz0 2 7∞ ∞ ∞∞ ∞ ∞fromcost tofromfromx y zxyz∞ ∞∞ ∞ ∞cost tox y zxyz∞ ∞ ∞7 1 0cost to∞2 0 1∞ ∞ ∞timexz127ynode x tablenode y tablenode z tableNetwork Layer 4-17x y zxyz0 2 7∞ ∞ ∞∞ ∞ ∞fromcost tofromfromx y zxyz0 2 3fromcost tox y zxyz∞ ∞∞ ∞ ∞cost to cost tocost tox y zxyz∞ ∞ ∞7 1 0cost to∞2 0 1∞ ∞ ∞2 0 17 1 0x y zxyz0 2 7from2 0 17 1 0timexz127ynode x tablenode y tablenode z tabley2 0 1x y zxz0 2 7from3 1 0Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2Network Layer 4-18x y zxyz0 2 7∞ ∞ ∞∞ ∞ ∞fromcost tofromfromx y zxyz0 2 3fromcost tox y zxyz0 2
View Full Document