1Routing Routing algorithms Link state Distance Vector1230111value in arrivingpacket’s headerrouting algorithmlocal forwarding tableheader value output link01000101011110013221Interplay between routing andforwardinguyxwvz2213112535Graph: 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 connectionsGraph 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 pathRouting Algorithm classificationGlobal or decentralizedinformation?Global: all routers have completetopology, link cost info “link state” algorithmsDecentralized: router knows physically-connected neighbors, linkcosts to neighbors iterative process ofcomputation, exchange ofinfo with neighbors “distance vector” algorithmsStatic or dynamic?Static: routes change slowlyover timeDynamic: routes change morequickly periodic update in response to linkcost changesA Link-State Routing Algorithm Dijkstra’s algorithm net topology, link costsknown to all nodes accomplished via “linkstate broadcast” all nodes have same info computes least cost pathsfrom one node (‘source”) toall other nodes gives forwarding table forthat node iterative: after k iterations,know least cost path to kdest.’s Notation: c(x,y): link cost from node xto y; = ∞ if not directneighbors D(v): current value of costof path from source to dest.v p(v): predecessor nodealong path from source to v N': set of nodes whoseleast cost path definitivelyknown2Dijsktra’s Algorithm1. Confirmed = {}2. for all neighbors N of thesource S1. add (N, cost(S,N), N) to Tentativelist3. while Tentative not empty1. Let (M,C,N) = node in Tentativewith smallest cost2. Move (M,C,N) to Confirmed3. For all neighbors N’ of M1. Add (N’, C+cost(M,N’), N) toTentative list unless a smallerentry for N’ already exists Two lists Confirmed Tentative Each listcontains: (Destination,Cost,NextHop)Dijkstra’s algorithm: exampleuyxwvz2213112535Confirmed Tentative(v,2,v)(w,5,w)(x,1,x)(x,1,x)(w,4,x)(v,2,v)(y,2,x)(y,2,x)(w,3,x)(z,4,x)(w,3,x)(z,4,x)Dijkstra’s algorithm, discussionAlgorithm complexity: n nodes each iteration: need to check all nodes, w, not in N n(n+1)/2 comparisons: O(n2) more efficient implementations possible: O(nlogn)Oscillations possible: e.g., link cost = amount of carried trafficADCB11+ee0e1100ADCB2+e0001+e1ADCB02+e1+e100ADCB2+e0e01+e1initially… recomputerouting… recompute… recomputeLink State Routing Requires global view of all links How do nodes learn this information?Flooding Loops Broadcast stormsA BD CControlled Flooding Ignore duplicate messages Cache to remember what’s been sent before Special case: sequence numbers Used with broadcast updates Source assigns increasing seq no to broadcast Record latest seq no from each source Discard messages with old seq no’s Ensures always use the latest update3Distance 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 xBellman-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:Distance Vector Algorithm (3) Dx(y) = estimate of least cost from x to y Distance 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 vectors For each neighbor v, x maintainsDv = [Dv(y): y є N ]Distance vector algorithm (4)Basic idea: Each node periodically sends its owndistance vector estimate to neighbors When node a node x receives new DVestimate from neighbor, it updates its ownDV 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)Distance Vector Algorithm (5)Iterative,asynchronous: eachlocal iteration causedby: local link cost change DV update messagefrom neighborDistributed: each node notifiesneighbors only whenits DV changes neighbors then notifytheir neighbors ifnecessarywait for (change in local linkcost of msg from neighbor)recompute estimatesif DV to any dest haschanged, notify neighborsEach node:uyxwvz2213112535u’s DV∞z∞y1x5w2v0uv’s DV∞z∞y2x3w0v2uw’s DV5z1y3x0w3v5ux’s DV∞z1y0x3w2v1uy’s DV2z0y1x1w∞v∞uz’s DV0z2y∞x5w∞v∞u4uyxwvz2213112535u’s DV∞z∞y1x5w2v0uv’s DV∞z∞y2x3w0v2uw’s DV5z1y3x0w3v5ux’s DV∞z1y0x3w2v1uy’s DV2z0y1x1w∞v∞uz’s DV0z2y∞x5w∞v∞uu’s updated DVzyxwvu23+51+2253+21+34Distance Vector: link cost changesLink cost changes:node detects local link cost changeupdates routing info, recalculatesdistance vectorif DV changes, notify neighbors“goodnews travelsfast”xz1450y1At time t0, y detects the link-cost change, updates its DV, and informs its neighbors.At time t1, z receives the update from y and updates its table. It computes a new least cost to x and sends its neighbors its DV.At time t2, y receives z’s update and updates its distance table. y’s least costs do not change and hence y does not send any message to z. Distance Vector: link cost changesLink cost changes:good news travels fastbad news travels slow - “count toinfinity” problem!44 iterations before algorithmstabilizes: see textPoisoned reverse:If Z routes through Y to get to X :Z tells Y its (Z’s) distance to X isinfinite (so Y won’t route to X via Z)will this completely solve count toinfinity problem?xz1450y60Count-to-infinity Problemxz1450y605z4yx’s DV1z4xy’s DV1y5xz’s DVdist=60dist=5+1Count-to-infinity Problemxz1450y605z4yx’s DV1z6xy’s DV1y5xz’s DVdist=50dist=6+1Count-to-infinity
View Full Document
Unlocking...