Distance Vector Algorithm

 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?
If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE

Post a Comment

Previous Post Next Post