Distance Vector Algorithm
Bellman-Ford Equation (dynamic programming)
• Define
dx(y) := cost of least-cost path from x to y
• Then
dx(y) = min {c(x,v) + dv(y) }
where min is taken over all neighbors v of x
Distance Vector Algorithm
• 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 maintains
Dv = [Dv(y): y є N ]
Basic idea:
• Each node periodically sends its own distance vector estimate to
neighbors
• When 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 ε N
• Under minor, natural conditions, the estimate Dx(y) converge to the
actual least cost dx(y)
Stan Kurkovsky
Distance Vector Algorithm
Iterative, asynchronous: each
local iteration caused by:
• local link cost change
• DV update message from
neighbor
Distributed:
• each node notifies neighbors only
when its DV changes
• neighbors then notify their
neighbors if necessary
Each node:
wait for (change in local link
cost of msg from neighbor)
recompute estimates
if DV to any dest has
changed, notify neighbors
8
Stan Kurkovsky
Distance Vector: link cost changes
Link cost changes:
• node detects local link cost change
• updates routing info, recalculates
distance vector
• if DV changes, notify neighbors
• “Good news travels fast”
• At 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.
x z
4 1
50
y
1
Stan Kurkovsky
Distance Vector: link cost changes
Link cost changes:
• good news travels fast
• bad news travels slow - “count to infinity” problem!
• 44 iterations before algorithm stabilizes
Poissoned reverse:
• If Z routes through Y to get to X :
• Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z)
• will this completely solve count to infinity problem?