Distance-Vector Routing: short notes (Computer Networks)

Revision mode

Introduction

A router forwards each packet by looking up its destination in a forwarding table; routing is the process that fills that table. Routing algorithms come in two families. In link-state routing every router learns the whole topology and runs Dijkstra's algorithm itself (Link-State Routing). In distance-vector (DV) routing a router knows only the costs of its own links and the distance vectors its neighbours send: lists of "destination, my current cost to it". From these it computes its own best costs and next hops, and tells its neighbours when they change.

Distance-vector routing is a distributed, asynchronous form of the Bellman-Ford algorithm. It is simple and needs no global view, but it reacts slowly to bad news: when a link fails or its cost rises, routers can keep pointing at each other while their costs climb step by step, the count-to-infinity problem. RIP is the classic DV protocol.

The shortest-path theory (relaxation, the Bellman-Ford recurrence and its correctness) is in Single-Source Shortest Paths; the protocol, its message exchange and its failure modes are the remaining facts.

Prerequisites

IPv4 Addressing and Header: routers, destination networks, forwarding tables.
Single-Source Shortest Paths: the Bellman-Ford recurrence and relaxation.

Core concepts

What each router stores

Item	Meaning
$c(x, v)$	Cost of the direct link from router $x$ to neighbour $v$ ( $\infty$ if no link)
$D_x(y)$	$x$ 's current estimate of its least cost to destination $y$
$\mathbf{D}_x$	$x$ 's distance vector: $D_x(y)$ for every destination $y$
$\mathbf{D}_v$ for each neighbour $v$	The latest vector received from $v$
Next hop to $y$	The neighbour $v$ that achieves the minimum below

The Bellman-Ford equation

D_x(y) = \min_{v \in \text{neighbours}(x)} \big\{ c(x, v) + D_v(y) \big\}, \qquad D_x(x) = 0 .

The neighbour achieving the minimum is the next hop. A router never needs to know the path beyond its neighbour: only the neighbour's claimed cost.

The protocol

Text

DV-ROUTER(x)
    initialise: D_x(x) <- 0; D_x(y) <- c(x, y) for neighbours y; D_x(y) <- infinity otherwise
    send D_x to every neighbour
    loop forever
        wait until a link cost to a neighbour changes or a vector D_v arrives from a neighbour v
        D_x(x) <- 0; next_hop[x] <- NONE
        for each destination y != x
            D_x(y) <- min over neighbours v of ( c(x, v) + D_v(y) );  record the argmin as next hop
        if any D_x(y) changed then send D_x to every neighbour

Each recomputation costs $O(\deg(x) \cdot n)$ for $n$ destinations. Real protocols also send vectors periodically (RIP every 30 seconds) so that lost updates are repaired.

Synchronous-rounds convention used in these notes. Unless a problem says otherwise, all routers exchange vectors at the same instants: in round $k$ , every router recomputes from the vectors its neighbours had at the end of round $k - 1$ . After round $k$ , every $D_x(y)$ equals the least cost over paths of at most $k + 1$ links (counting the initial direct-link vector as round 0), so with nonnegative costs the tables are correct after at most $n - 2$ rounds and stop changing.

How it works: a converging example

Four routers with link costs A-B 1, A-C 4, B-C 2, B-D 6, C-D 1. Round 0 vectors hold only direct links.

Router	Round 0 (A, B, C, D)	Round 1	Round 2
A	0, 1, 4, $\infty$	0, 1, 3, 5	0, 1, 3, 4
B	1, 0, 2, 6	1, 0, 2, 3	1, 0, 2, 3
C	4, 2, 0, 1	3, 2, 0, 1	3, 2, 0, 1
D	$\infty$ , 6, 1, 0	5, 3, 1, 0	4, 3, 1, 0

In round 1, A learns from B that C is 2 away from B, so $D_A(C) = \min(4, 1 + 2) = 3$ via B, and from C that D is 1 away, so $D_A(D) = \min(1 + 6, 4 + 1) = 5$ via C. In round 2, B's improved $D_B(D) = 3$ reaches A, giving $D_A(D) = 1 + 3 = 4$ via B. Round 3 changes nothing. A's final next hops: B for B, C and D.

Four routers A, B, C, D with links A-B cost 1, A-C cost 4, B-C cost 2, B-D cost 6, C-D cost 1. Beside the graph, three stacked tables show router A's distance vector after rounds 0, 1 and 2: round 0 is 0, 1, 4, infinity; round 1 is 0, 1, 3, 5 with next hops B and C for destinations C and D; round 2 is 0, 1, 3, 4 with next hop B for every destination. Below, a second panel shows the line A-B-C after the A-B link fails: the pair of costs to A at B and at C climbs 3 and 2, 3 and 4, 5 and 4, up to 16 and 16 after 15 rounds. — Figure 1. Distance-vector rounds: router A's vector converges in two rounds (0, 1, 3, 4), while after the A-B link fails on the line A-B-C the costs to A count up to the RIP infinity 16 in 15 rounds.

Mathematical explanation: good news and bad news

Good news travels fast. If a link cost falls, the router at its end sees a lower sum at once, and the improvement spreads one hop per round: at most (number of hops on the new path) rounds.

Bad news travels slowly. If a link cost rises or the link fails, a router may find that a neighbour still advertises an old, cheap cost, which was computed through the router itself. It adopts that route, advertises the new, slightly higher cost back, and the two routers raise each other's costs by the cost of the link between them in every exchange. The loop ends only when the costs exceed the cost of the best real alternative route, or reach the protocol's infinity.

Count to infinity on a line. Routers A, B, C in a line with A-B cost 1 and B-C cost 1, so $D_B(A) = 1$ and $D_C(A) = 2$ via B. The A-B link fails. In the next round B has no direct route, sees C advertising 2, and sets $D_B(A) = 1 + 2 = 3$ via C; C, using B's old value 1, keeps 2. Then C sets $1 + 3 = 4$ , B sets $1 + 4 = 5$ , and so on, each value rising by 2 every two rounds. With RIP's infinity of 16 the pair $(D_B(A), D_C(A))$ runs $(3, 2), (3, 4), (5, 4), \ldots, (15, 16), (16, 16)$ and both routers declare A unreachable after 15 rounds.

Split horizon and poisoned reverse

Split horizon: do not advertise a route back to the neighbour it was learned from. On the line, C learned its route to A from B, so it does not tell B about it. After the failure, B finds no route at once (round 1) and C sees B's "no route" in round 2.
Poisoned reverse: advertise such a route back with cost $\infty$ . It has the same reach as split horizon, but the explicit $\infty$ makes the neighbour drop a stale route at once instead of waiting for it to time out.
Limitation: both stop loops between two neighbours only. A loop of three or more routers can still count to infinity; RIP keeps its infinity small (16) so that such a count ends quickly.

Worked examples

Example 1: one update step

Router X has neighbours A (link cost 2), B (link cost 5) and C (link cost 1). Their latest vectors for destinations P, Q and R are A: (4, 9, 3), B: (1, 2, 6), C: (6, 7, 1).

Destination	Via A	Via B	Via C	New $D_X$	Next hop
P	6	6	7	6	A or B (tie)
Q	11	7	8	7	B
R	5	11	2	2	C

X ignores its own old values: the new vector depends only on link costs and the neighbours' vectors.

Example 2: count to infinity on a line, round by round

The A-B link of the line A-B-C fails just before round 1; before the failure $D_B(A) = 1$ and $D_C(A) = 2$ via B. RIP's infinity is 16.

Round	No split horizon: $D_B(A)$ , $D_C(A)$	Split horizon or poisoned reverse: $D_B(A)$ , $D_C(A)$
1	3 (via C), 2	16, 2
2	3, 4	16, 16
3	5, 4
4	5, 6
5	7, 6
6	7, 8
7 to 12	each value rises by 2 every two rounds
13	15, 14
14	15, 16
15	16, 16

Without split horizon, B takes C's stale 2 in round 1 (a route that runs back through B), and the two routers feed each other ever larger costs until both reach 16 after 15 rounds. With split horizon C never advertises its route to A back to B, from whom it learned it, so B has no route at once; with poisoned reverse C advertises 16 to B, with the same effect here. C still uses B's old value 1 in round 1 and learns of the loss in round 2.

Example 3: a cost increase with an alternative route

Triangle X, Y, Z with costs X-Y 3, Y-Z 1, X-Z 30. Converged: $D_Y(X) = 3$ direct, $D_Z(X) = 4$ via Y. The X-Y cost rises to 40.

Without poisoned reverse: Y sees Z offering 4 (a route that runs back through Y) and switches to $1 + 4 = 5$ via Z; Z then raises to 6 via Y, and so on, two units every two rounds. The costs climb until Z's route through Y costs more than its direct link of 30: the tables stop changing after 27 rounds with $D_Z(X) = 30$ direct and $D_Y(X) = 31$ via Z.
With poisoned reverse: Z tells Y that its cost to X is $\infty$ (because Z routes through Y), so Y takes the direct link, 40; Z then sees its direct 30 is better than $1 + 40$ ; Y then switches to $1 + 30 = 31$ via Z. Settled after 3 rounds.
If instead the X-Y cost falls to 1: Y uses 1 at once and Z uses 2 one round later: 2 rounds.

RIP uses hop count as the metric, treats 16 as infinity (so it suits networks of diameter at most 15), sends its whole vector to neighbours every 30 seconds, and runs over UDP port 520. Split horizon with poisoned reverse is part of the protocol.

Important properties and observations

Only neighbours talk. Each message goes one hop; a router's knowledge of far destinations is only what its neighbours claim.
Iterative and asynchronous. Routers need not run in lock step; the algorithm still converges with nonnegative, fixed costs.
Self-terminating. A router sends only when its vector changes (plus periodic refreshes in practice).
Next hop is not the path. The table gives the first hop only; the full path follows from the tables of every router along it.
Negative costs do not occur in routing; the negative-cycle detection of Bellman-Ford plays no role here.

Common misconceptions.

"DV routers know the topology." They know only neighbours' vectors and their own link costs.
"Split horizon solves count to infinity." Only for loops of two routers.
"Each router runs Bellman-Ford over the whole graph." It applies one Bellman-Ford step over its neighbours each time.

GATE examination perspective

One update step. Add each neighbour's advertised cost to the link cost, take the minimum per destination, record the next hop; ignore the router's previous values.
Rounds to converge. Use the synchronous-rounds convention unless told otherwise; good news needs about one round per hop.
Count to infinity. Trace two routers raising each other by the link cost between them per exchange; stop at the alternative route's cost or at infinity (16 for RIP).
Split horizon versus poisoned reverse. Omit the route back, or send it with $\infty$ .
DV versus LS. DV: neighbour-only messages, slow bad-news convergence, possible routing loops. LS: flooding of link states, Dijkstra at every router.

Summary

Sources

A. S. Tanenbaum, D. J. Wetherall, Computer Networks, 5th ed., Pearson, 2011: Section 5.2.4 (Distance Vector Routing).
J. F. Kurose, K. W. Ross, Computer Networking: A Top-Down Approach, 8th ed., Pearson, 2021: Section 5.2.2 (The Distance-Vector (DV) Routing Algorithm).
B. A. Forouzan, Data Communications and Networking, 5th ed., McGraw-Hill, 2013: Chapter 20 (Unicast Routing).
G. Malkin, RFC 2453, RIP Version 2, 1998, Section 3.4 (Distance Vector Algorithms: infinity of 16, counting to infinity, 3.4.3 Split horizon with poisoned reverse) and Section 3.6 (Message Format: UDP port 520), (consulted 2026-11-11).