Distance Vector Routing

Distance vector routing is a distributed, iterative, asynchronous algorithm based on the Bellman-Ford equation. Each router maintains a table (a "vector") giving the best-known distance to every destination and the next hop towards it, and exchanges this vector only with its immediate neighbours. No router ever learns the full topology. Example protocol: RIP (uses hop count, max 15 hops).

Principle

$$D_x(y) = \min_v \left\{ c(x,v) + D_v(y) \right\}$$

The least cost from x to y is the cheapest of: the direct cost to a neighbour v plus v's currently known least cost to y. Each router repeatedly advertises its vector, applies the equation to the neighbours' advertisements, and updates its table until no entry changes (convergence).

Network diagram

           2                3
      A --------- B --------------- C
       \                       /
        \                     /
         4                   5
          \                 /
           \               /
             ------ D ----

   (A-B = 2, B-C = 3, A-D = 4, D-C = 5)

Operation at router A

1. Initialisation (only direct links): A knows A = 0, B = 2 (via B), D = 4 (via D), C = ∞.
2. First exchange: A receives vectors from neighbours B and D.
   • B advertises: "I can reach C in 3 hops, D in ∞, myself 0."
   • D advertises: "I can reach C in 5 hops, B in ∞, myself 0."
3. Apply Bellman-Ford:
   • C: min(∞, 2 + 3, 4 + 5) = 5 via B
   • B: min(2, 4 + ∞) = 2 (unchanged) — D: min(4, 2 + ∞) = 4 (unchanged)
4. Table now stable (converged).

Final distance table at A:

Destination	Cost	Next hop
A	0	—
B	2	B
C	5	B
D	4	D

The same computation runs simultaneously in every router, each building its own table from its neighbours' vectors.

Properties

Aspect	Detail
Knowledge	Local — only neighbours' vectors, no global topology
Communication	Periodic (RIP: every 30 s) and on-change updates to neighbours only
Advantages	Simple, minimal computation, very low overhead, little memory
Disadvantages	Count-to-infinity problem, transient routing loops, slow convergence after a failure
Remedies	Split horizon, poison reverse, triggered updates, hold-down timers
Cost metric	Must be additive (hop count, delay) — unlike link state, which can use any metric

Summary: each router "believes" its neighbours about destinations it does not know directly, so a bad or stale advertisement propagates slowly and can drive the cost to infinity during a failure — the main weakness compared with link state routing.