Distance vector Routing: overview Iterative, asynchronous Each node: each local iteration caused 口| ocal link cost change wait for(change in local link o message from neighbor its cost of msg from neighbor) least cost path change from neighbor Distributed: recompute distance table 口 each node notifies neighbors only when its least cost path to any if least cost path to any dest destination changes has changed, notify o neighbors then notify neighbors their neighbors if necessary Network Layer 4-21
Network Layer 4-21 Distance Vector Routing: overview Iterative, asynchronous: each local iteration caused by: local link cost change message from neighbor: its least cost path change from neighbor Distributed: each node notifies neighbors only when its least cost path to any destination changes neighbors then notify their neighbors if necessary wait for (change in local link cost of msg from neighbor) recompute distance table if least cost path to any dest has changed, notify neighbors Each node:
Distance Vector Algorithm At all nodes x initialization: 2 for all adjacent nodes v 3 DX( ) infinity /* the *operator means"for all rows"*/ 4 DX(V,v)=c(X, v) 5 for all destinations, y 6 send min DX(y, w) to each neighbor /*w over all X's neighbors*/ Network Layer 4-22
Network Layer 4-22 Distance Vector Algorithm: 1 Initialization: 2 for all adjacent nodes v: 3 D (*,v) = infinity /* 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 */ X X X w At all nodes, X:
Distance Vector Algorithm(cont: 8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor v) 11 12 if(c(X,) changes by d 13 / change cost to all dest's via neighbor v byd*/ 14/note: d could be positive or negative */ 15 for all destinations y: DX(y,v=DXy,V)+d 16 17 else if (update received from V wrt destination Y) 18/ shortest path from V to some Y has changed * 19 /*V has sent a new value for its min DVY,w)*/ 20/ call this received new value is newal 21 for the single destination y: DXY, =cX,V)+ newval 22 23 if we have a new min dX( Y, w for any destination Y 24 send new value of min DX(Y,w) to all neighbors 25 26 forever Network Layer 4-23
Network Layer 4-23 Distance Vector Algorithm (cont.): 8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 12 if (c(X,V) changes by d) 13 /* change cost to all dest's via neighbor v by d */ 14 /* note: d could be positive or negative */ 15 for all destinations y: D (y,V) = D (y,V) + d 16 17 else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its min DV(Y,w) */ 20 /* call this received new value is "newval" */ 21 for the single destination y: D (Y,V) = c(X,V) + newval 22 23 if we have a new min D (Y,w)for any destination Y 24 send new value of min D (Y,w) to all neighbors 25 26 forever w X X X X X w w
Distance Vector Algorithm: example cost via cost via cost via Z Y Z dest 2) ②8 ⑦ t 21(3 cost via cost via cost via X X X Z des d x|8 des X t z 9 1 cost via cost via cost via X Y X Y X Y eX7(3 X eyl∞⑥ty|9① Network Layer 4-24
Network Layer 4-24 Distance Vector Algorithm: example X Z 2 1 7 Y
Distance Vector Algorithm: example cost via cost via Y Z Y Z des (2 dest ②8 tz|。。 cost via D(Y, Z)= c(X, 2 )+ minD Y, w) X Z des X(2)a 7+1=8 D(Z,Y)=c(,Y)+ minD(Z,w)] 2+1=3 D cost via X Y des x⑦ ① Network Layer 4-25
Network Layer 4-25 Distance Vector Algorithm: example X Z 2 1 7 Y D (Y,Z) X c(X,Z) + min {D (Y,w)} = w = 7+1 = 8 Z D (Z,Y) X c(X,Y) + min {D (Z,w)} = w = 2+1 = 3 Y