Bellman-Ford Example Suppose that u's neighboring nodes,x,v,w,know that for destination z: D.(z)=5 Dw(z)=3 Bellman-Ford equation says: 5 D.(Z) min cuv+Dy(Z), Cux+Dx②D Cu.w+Dw(z)} =min{2+5, 1+3, 5+3X =4 D2)=3 node achieving minimum (x)is next hop on estimated least- cost path to destination (z) Network Layer:5-21
Bellman-Ford Example Network Layer: 5-21 u y z 2 2 1 3 1 1 2 5 3 5 Suppose that u’s neighboring nodes, x,v,w, know that for destination z: Du (z) = min { cu,v + Dv (z), cu,x + Dx (z), cu,w + Dw(z) } Dv Bellman-Ford equation says: (z) = 5 v Dw(z) = 3 w Dx (z) = 3 x = min {2 + 5, 1 + 3, 5 + 3} = 4 node achieving minimum (x) is next hop on estimated leastcost path to destination (z)
Distance vector algorithm key idea: from time-to-time,each node sends its own distance vector estimate to neighbors when x receives new DV estimate from any neighbor,it updates its own DV using B-F equation: D.(y)<min,fcxv+D.(y)}for each node yEN under minor,natural conditions,the estimate D(y)converge to the actual least cost d,(y) Network Layer:5-22
Distance vector algorithm Network Layer: 5-22 key idea: ▪ from time-to-time, each node sends its own distance vector estimate to neighbors ▪ under minor, natural conditions, the estimate Dx (y) converge to the actual least cost dx (y) Dx (y) ← minv {cx,v + Dv (y)} for each node y ∊ N ▪ when x receives new DV estimate from any neighbor, it updates its own DV using B-F equation:
Distance vector algorithm: each node: iterative,asynchronous:each local iteration caused by: wait for (change in local link local link cost change cost or msg from neighbor) DV update message from neighbor recompute DV estimates using distributed,self-stopping:each DV received from neighbor node notifies neighbors only when its DV changes neighbors then notify their if DV to any destination has neighbors-only if necessary changed,notify neighbors no notification received,no actions taken! Network Layer:5-23
Distance vector algorithm: Network Layer: 5-23 iterative, asynchronous: each local iteration caused by: ▪ local link cost change ▪ DV update message from neighbor wait for (change in local link cost or msg from neighbor) each node: distributed, self-stopping: each node notifies neighbors only when its DV changes ▪ neighbors then notify their neighbors – only if necessary ▪ no notification received, no actions taken! recompute DV estimates using DV received from neighbor if DV to any destination has changed, notify neighbors
Distance vector:example DVin a: D.(a=0 D(b)=8 D(c)=∞ .a b Da(d)=1 D(el=∞ t=0 D(0=∞ D(g)=∞ All nodes have D(h)=∞ distance estimates D(0=∞ to nearest A few asymmetries: neighbors(only) missing link larger cost All nodes send their local distance vector to their neighbors Network Layer:5-24
DV in a: Da (a)=0 Da (b) = 8 Da (c) = ∞ Da (d) = 1 Da (e) = ∞ Da (f) = ∞ Da (g) = ∞ Da (h) = ∞ Da (i) = ∞ Distance vector: example Network Layer: 5-24 g h i 1 1 1 1 1 1 1 1 1 8 1 t=0 ▪ All nodes have distance estimates to nearest neighbors (only) A few asymmetries: ▪ missing link ▪ larger cost d e f a b c ▪ All nodes send their local distance vector to their neighbors
Distance vector example:iteration a C t=1 All nodes: receive distance vectors from neighbors compute their new local distance vector send their new local distance vector to neighbors h Network Layer:5-25
Distance vector example: iteration Network Layer: 5-25 All nodes: ▪ receive distance vectors from neighbors ▪ compute their new local distance vector ▪ send their new local distance vector to neighbors t=1 g h i 1 1 1 1 1 1 1 1 1 8 1 d e f a b c