NETWORK COMPUTING · DISTANCE-VECTOR ROUTING · MESSAGE PASSING

Distributed Bellman–Ford
Network Laboratory

Every router knows only its direct links, exchanges a distance vector with neighbours and independently discovers shortest routes. Step through synchronous rounds to inspect messages, routing-table changes and convergence.

Dₓ(y) = minᵥ{c(x,v)+Dᵥ(y)}distance vectorneighbour-to-neighbour messagesnext-hop routingdistributed convergencelink-cost change
Synchronous round0
Messages this round0
Table entries changed0
Network stateINIT

Routers and vector messages

SELECT A ROUTER TO INSPECT

Router A

LOCAL KNOWLEDGE

Routing table

DestinationCostNext hop

Last received inbox

Convergence history

GLOBAL BARRIER AFTER EACH ROUND
RoundVectors sentEntries changedRouters updatedMax finite costStatus
Ready. Each router initially knows cost 0 to itself, direct-link costs to neighbours, and infinity to every other destination.

1. Local knowledge

Router x never receives a global graph. It stores a vector Dₓ and the cost of each adjacent link. Initially it can route only to itself and direct neighbours. This is why the same algorithm fits decentralized networks.

D[x][x] = 0
D[x][neighbor] = linkCost
D[x][other] = infinity

2. Exchange and relax

At a round boundary, each router sends its previous vector to neighbours. Router x tests every destination y through every neighbour v. Updates use only messages from the same completed round, making causality visible.

candidate = cost(x,v) + Dv[y]
if candidate < Dx[y]:
    Dx[y] = candidate
    nextHop[x][y] = v

3. Routing convergence

When a complete round changes no table entry, every router has converged for the current topology. Raising a link cost invalidates old knowledge and starts a new exchange. This lab recomputes from direct links so students can inspect reconvergence without hiding stale routes.

repeat synchronousRound()
until changedEntries == 0

message complexity per round:
O(|E| · |V|)