Self-checkedTier 1 8 min readcn.routing-distance-vector

Distance vector routing

Routing as the problem of choosing next hops, the distance vector (Bellman-Ford) algorithm run by neighbouring routers exchanging vectors, the update rule D(x,y) = min over neighbours of c(x,v) + D(v,y), round-by-round convergence (after k rounds paths of at most k+1 links are known), the count-to-infinity problem when a link fails, and the partial cures split horizon and poison reverse (which fix two-router loops but not loops of three); RIP as the protocol example; every table is the output of a synchronous simulation checked against Floyd-Warshall.

Why it exists

A router that receives a packet has to decide which neighbour should get it next. It can do this only with a routing table that says, for each destination, the next hop. Nobody types these tables in on a large network, so the routers compute them themselves by exchanging information. The distance vector method is the simplest: each router tells its neighbours its current estimate of the cost to every destination, and learns the rest from them. It is the distributed form of the Bellman-Ford algorithm and the basis of RIP.

Prerequisites

You need destinations given as prefixes and forwarding by next hop (CIDR). The algorithm is the Bellman-Ford shortest path computation (Bellman-Ford), done in a distributed way.

Precise definitions

Model the network as a graph: routers are nodes, links are edges with a cost $c(x, v)$ (hop count, delay or any metric). Let $D_x(y)$ be router $x$ 's current estimate of the least cost from $x$ to $y$ . Each router $x$ maintains the distance vector $D_x = [D_x(y) : y \in N]$ and the cost $c(x, v)$ to each direct neighbour $v$ , and stores the latest vectors it received from its neighbours.

The update rule (Bellman-Ford equation):

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

The neighbour $v$ that gives the minimum is the next hop for $y$ .

The algorithm. Each router starts knowing only $D_x(x) = 0$ and the costs of its direct links ( $\infty$ for everything else). Whenever the vector of a neighbour arrives, or a link cost changes, the router recomputes its vector by the rule above; if its own vector changed, it sends it to all its neighbours. The process is distributed, iterative and asynchronous. When no vector changes any more, the tables have converged.

In the synchronous rounds used on this page, every router in every round uses the vectors its neighbours had at the end of the previous round.

How it works

Convergence

Distance vector routing, round by round: start

Computed by a script, not typed

router	to A	to B	to C	to D	to E
router A
router B
router C
router D
router E

Step 0

Five routers A … E with link costs A-B 2, A-C 5, B-C 1, B-D 4, C-D 2, C-E 6, D-E 1. Round 0: every router knows only the cost to itself (0) and to its neighbours; each entry shows cost via next hop.

0 / 4

computed by script: fragments are cut and reassembled, routing tables are computed round by round, flooding is simulated. python3 scripts/gen-cn3-traces.py

Five routers, costs A-B $2$ , A-C $5$ , B-C $1$ , B-D $4$ , C-D $2$ , C-E $6$ , D-E $1$ . In round $0$ a router knows only its direct neighbours (A-C costs $5$ and A-D is unknown). In round $1$ , A learns from B that C is $1$ from B, so C costs $3$ via B instead of $5$ directly. After $k$ rounds every entry equals the cheapest path of at most $k + 1$ links (a fact the checks of this site confirm). The tables stop changing after at most $N - 1$ rounds for $N$ routers, here after $3$ .

Cost of the algorithm: each router sends its vector (size proportional to $N$ ) to each neighbour; messages go only to neighbours, which suits small networks. Each router sees only costs and next hops, never the whole map.

Good news fast, bad news slow

If a link gets cheaper or appears, the information spreads in about the number of hops it must travel: "good news travels fast". If a link fails or becomes more expensive, a router may believe a neighbour's old advertisement that actually depended on the failed link. This gives the count-to-infinity problem:

Count to infinity: the link A–B fails: start

Computed by a script, not typed

time	plain	split horizon	poison reverse
after round 0
after round 1
after round 2
after round 3
after round 4
after round 5
after round 6
after round 7
after round 8
after round 9
after round 10
after round 11
after round 12
after round 13
after round 14
after round 15

Step 0

Line A – B – C – D with all costs 1 and 'infinity' = 16 (as in RIP). Before the failure B, C, D are at distance 1, 2, 3 from A. All three versions are run from the same state. All costs reach infinity after 15 rounds (plain), 3 (split horizon), 3 (poison reverse).

0 / 16

computed by script: fragments are cut and reassembled, routing tables are computed round by round, flooding is simulated. python3 scripts/gen-cn3-traces.py

Line A – B – C – D with unit costs and "infinity" $=16$ . The link A-B fails. B no longer reaches A directly, but C still says "A is $2$ away" (via B). B concludes "A is $1 + 2 = 3$ away via C"; then C hears $3$ from B and says $4$ ; and so on: the two routers keep raising each other's estimates by $2$ per two rounds until the value reaches the infinity ( $16$ in RIP). Meanwhile packets for A bounce between B and C (a routing loop). It takes $15$ rounds in the simulation. Defining a small value for infinity bounds the damage.

Split horizon and poison reverse

Split horizon: a router does not advertise a route back to the neighbour from which it learned it (C does not tell B about A, because C reaches A through B).
Poison reverse: it advertises the route back with cost infinity ("I reach A only through you, so for you the cost is $\infty$ ").

In the line example both cut the count from $15$ rounds to $3$ . But they only break loops between two routers:

Rounds until the lost destination is declared unreachable: start

Computed by a script, not typed

scenario	plain	split horizon	poison reverse
line A–B–C–D, link A–B fails
triangle A–B–C with D behind C, link C–D fails

Step 0

The number of rounds until every router has cost 16 (infinity) to the lost destination.

0 / 2

computed by script: fragments are cut and reassembled, routing tables are computed round by round, flooding is simulated. python3 scripts/gen-cn3-traces.py

In a triangle A-B-C with D behind C, after C-D fails, A and B can each believe D is reachable through the other and through C in a circle of three routers; split horizon and poison reverse do not help (the run needs $15$ rounds in all three cases). Other cures (triggered updates, hold-down timers, path vectors as in BGP) are outside the syllabus.

RIP

The Routing Information Protocol uses hop count as the metric, infinity $=16$ (so the longest path is $15$ hops), sends the vector every $30$ s to neighbours and uses split horizon with poison reverse (quoted). It is an interior gateway protocol (protocols overview).

Worked examples

EX 1One update

Easy

Router A has neighbours B (cost $2$ ) and C (cost $5$ ). B advertises $D_B(D) = 4$ and C advertises $D_C(D) = 2$ . $D_A(D) = \min(2 + 4,\ 5 + 2) = 6$ via B. If C's advertisement changes to $D_C(D) = 1$ then $\min(6, 6) = 6$ (a tie).

EX 2Rounds to converge

Medium

In a chain of $N$ routers with unit costs, the router at one end knows its neighbour at the start (round $0$ ) and learns one link further in every round, so it learns the cost to the router at the other end, $N - 1$ links away, after $N - 2$ rounds. After $k$ rounds it knows all routers within $k + 1$ links. The general bound for any network is that the tables stop changing after at most $N - 1$ rounds.

EX 3Count to infinity

Medium

Line A-B-C, unit costs, B and C at distances $1$ and $2$ from A. The link A-B fails. B receives C's old vector ( $2$ to A) and sets $3$ ; C receives $3$ and sets $4$ ; B sets $5$ ; ... The values alternate B: $3, 5, 7, \dots$ and C: $4, 6, 8, \dots$ until $16$ . With infinity $=16$ the process ends after about $8$ exchanges each. With split horizon C does not tell B about A (it learned it from B), B sees no route and sets $\infty$ at once.

EX 4Typical questions

GATE level

(a) "Which algorithm does distance vector routing use?" Bellman-Ford. (b) "What does each router send, and to whom?" Its distance vector to its neighbours. (c) "What is count to infinity, and which technique solves part of it?" Bad news travels slowly; split horizon / poison reverse (two-node loops only). (d) "After $k$ rounds, which paths does a table reflect?" The best paths of at most $k + 1$ links (round $0$ holds the direct neighbours). (e) "Why is RIP's infinity $16$ ?" So that count to infinity stops quickly and the network diameter is limited to $15$ hops.

Cheat box

$D_x(y) = \min_v \{c(x, v) + D_v(y)\}$ ; next hop = the minimising neighbour.
Routers exchange vectors with neighbours only; converges in at most $N - 1$ rounds.
Good news fast, bad news slow: count to infinity; infinity $=16$ in RIP.
Split horizon: do not advertise a route to the neighbour it came from; poison reverse: advertise it as $\infty$ . Both fail for loops of $3$ or more routers.
RIP: hop count, updates every $30$ s, interior protocol.

Traps and GATE patterns

Connections

Builds on

CIDR and subnetting

Unlocks

CIDR and subnettingimplemented by Link state routingcontrasts with RIP, OSPF and BGP overviewPrerequisite of RIP, OSPF and BGP overviewimplemented by

Across subjects

Bellman-Fordimplemented-by

Within this subject

Link state routingcontrasts-with CIDR and subnettinguses RIP, OSPF and BGP overviewimplemented-by

The algorithm is Bellman-Ford with the relaxation spread over the routers (Bellman-Ford). The alternative that sends the whole map to everyone and runs Dijkstra locally is link state routing (link state routing). Real networks use both inside an autonomous system and a path-vector protocol between them (protocols overview); the destinations in the tables are CIDR prefixes (CIDR).

PYQs

8 previous year questions from your book. I re-solved each one myself (6 by running or simulating, 2 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2025 · MCQQ11 · page 548 of the book

Consider the routing protocols given in List-I and the
names given in List-II:

List-I
List-II
(i) Distance vector routing (a) Bellman-Ford
(ii) Link state routing
(b) Dijkstra

For matching of items in List-I with those in List-II,
which ONE of the following options is CORRECT?

(a)(i) - (a) and (ii) - (b)
(b)(i) - (a) and (ii) - (a)
(c)(i) - (b) and (ii) - (a)
(d)(i) - (b) and (ii) - (b) COMPUTER NETWORK

GATE 2022 · NAT · 2 marksQ27 · page 551 of the book

Consider a network with three routers P, Q, R shown
in the figure below. All the links have cost of unity.

The routers exchange distance vector routing
information and have converged on the routing tables,
after which the link Q-R fails. Assume that P and Q
send out routing updates at random times, each at the
same average rate. The probability of a routing loop
formation (rounded off to one decimal place) between
P and Q, leading to the count-to-infinity problem, is
___________.

GATE 2021 · MSQQ31 · page 552 of the book

Consider a computer network using the distance
vector routing algorithm in its network layer. The
partial topology of the network is as shown below.

The objective is to find the shortest-cost path from
the router R to routers P and Q.

Assume that R does not initially know the shortest
routes to P and Q.

Assume that R has three neighbouring routers
denoted as X, Y, and Z.

During one iteration, R measures its distance to its
neighbours X, Y, and Z as 3, 2, and 5, respectively.
Router R gets routing vectors from its neighbours
that indicate that the distance to router P from
routers X, Y, and Z are 7, 6, and 5, respectively.
The routing vector also indicates that the distance
to router Q from routers X, Y, and Z are 4, 6, and 8,
respectively. Which of the following statement(s)
is/are correct with respect to the new routing table of
R, after update during this iteration?

(a)The distance from R to Q will be stored as 7.
(b)The distance from R to P will be stored as 10.
(c)The next hop router for a packet from R to Q is Z.
(d)The next hop router for a packet from R to P is Y.

GATE 2014 · MCQQ62 · page 557 of the book

Consider the following three statements about link
state and distance vector routing protocols for a large
network with 500 network nodes and 4000 links.

S1: The computational overhead in link state
protocols is higher than in distance vector protocols.
S2: A distance vector protocol (with split horizon)
avoids persistent routing loops, but not a link state
protocol.
S3: After a topology change, a link state protocol will
converge faster than a distance vector protocol.

Which one of the following is correct about S1, S2,
and S3?

(a)S1, S2, and S3 are all true.
(b)S1, S2, and S3 are all false.
(c)S1 and S2 are true, but S3 is false.
(d)S1 and S3 are true, but S2 is false COMPUTER NETWORK

GATE 2011 · MCQ · 2 marksQ75 · page 559 of the book

Consider a network with five nodes, N1 to N5, as
shown as below.

The network uses a Distance Vector Routing
protocol. Once the routes have been stabilized, the
distance vectors at different nodes are as follows.
N1: ( 0,1,7,8,4 )
N2: ( 1,0,6,7,3 )
N3: (7,6,0,2,6)
N4: (8, 7, 2, 0,4)
N5: (4, 3, 6, 4, 0)
Each distance vector is the distance of the best
known path at that instance to nodes, N1 to N5,

COMPUTER NETWORK
where the distance to itself is 0 . Also, all links are
symmetric and the cost is identical in both
directions. In each round, all nodes exchange their
distance vectors with their respective neighbors.
Then all nodes update their distance vectors. In
between two rounds, any change in cost of a link
will cause the two incident nodes to change only
that entry in their distance vectors.
The cost of link N2 -N3 reduces to 2 (in both
directions). After the next round of updates, what
will be the new distance vector at node, N3 ?

(a)(3,2,0,2,5)
(b)(3,2,0,2,6)
(c)(7,2,0,2,5)
(d)(7,2,0,2,6)

GATE 2011 · MCQ · 2 marksQ76 · page 560 of the book

Consider a network with five nodes, N1 to
                     N5, as shown as below.

The network uses a Distance Vector Routing
protocol. Once the routes have been stabilized, the
distance vectors at different nodes are as follows.

N1: ( 0,1,7,8,4 )

N2: (1,0,6,7,3)

N3: (7,6,0,2,6)

N4: (8,7,2,0,4)

N5: (4, 3, 6, 4, 0)
Each distance vector is the distance of the best
known path at that instance to nodes, N1 to N5,
where the distance to itself is 0 . Also, all links
are symmetric and the cost is identical in both
directions. In each round, all nodes exchange
their distance vectors with their respective
neighbors. Then all nodes update their distance
vectors. In between two rounds, any change in
cost of a link will cause the two incident nodes
to change only that entry in their distance
vectors.
The cost of link N2 -N3 reduces to 2 (in both
directions). After the next round of updates, the
link N1 -N2 goes down. N2 will reflect this
change immediately in its distance vector as cost,
∞. After the NEXT ROUND of update, what will
be the cost to N1 in the distance vector of N3 ?

(a)3
(b)9
(c)10
(d)∞

GATE 2010 · MCQ · 2 marksQ77 · page 560 of the book

Consider a network with 6 routers R1 to R6
connected with links having weights as shown
in the following diagram.

All the routers use the distance vector based
routing algorithm to update their routing
tables. Each router starts with its routing table
initialized to contain an entry for each
neighbor with the weight of the respective
connecting link. After all the routing tables
stabilize, how many links in the network will
never be used for carrying any data?

(a)4
(b)3
(c)2
(d)1

GATE 2010 · MCQ · 2 marksQ78 · page 560 of the book

Consider a network with 6 routers R1 to R6
connected with links having weights as shown in
the following diagram.

COMPUTER NETWORK

Suppose the weights of all unused links are
changed to 2 and the distance vector algorithm is
used again until all routing tables stabilize. How
many links will now remain unused?

(a)0
(b)1
(c)2
(d)3

Self-check

Question 1

Router X has neighbours P (cost $1$ ) and Q (cost $3$ ). P says it reaches Z with cost $7$ , Q says $4$ . What are X's cost and next hop to Z?

Show answer

$\min(1 + 7,\ 3 + 4) = 7$ via Q.

Question 2

Why does the count to infinity happen?

Show answer

A router accepts a neighbour's old advertisement that depends on the failed link itself, and the two keep increasing each other's estimates.

Question 3

Does poison reverse remove the loop in a triangle of three routers?

Show answer

No; it only prevents a route from being advertised back to the neighbour it came from, which cannot catch a loop passing through three routers.

Revision card

One-screen revision

$D_x(y) = \min_v \{c(x, v) + D_v(y)\}$ using neighbours' vectors; Bellman-Ford distributed.
Converges in at most $N - 1$ rounds; bad news travels slowly (count to infinity).
Split horizon / poison reverse: two-router loops only. RIP: hop count, infinity $16$ .

References

·Kurose, Ross, Computer Networking: A Top-Down Approach (8th edition), Chapter 5, Sections 5.1 and 5.2 (Routing algorithms: the distance-vector algorithm)
·Tanenbaum, Wetherall, Computer Networks (5th edition), Chapter 5, Section 5.2.4 (Distance vector routing)
·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd edition), Chapter 24, Section 24.1 (The Bellman-Ford algorithm)

Verification

scripts/enum-checks/cn_route_check.py on 600 random connected graphs of 3 to 8 routers (link costs 1 to 5, 0 to 6 extra links): the synchronous distance vector simulation converges within N - 1 rounds, its converged costs equal Floyd-Warshall distances for plain DV, split horizon and poison reverse, next hops are consistent (cost = link cost + the neighbour's cost), and after k rounds every entry is exactly the best path of at most k + 1 links (checked against a bounded Bellman-Ford); count to infinity: on the line A-B-C-D with unit costs, after the link A-B fails the plain algorithm needs 15 rounds to reach the infinity value 16 at all routers (the costs climb by 2 every two rounds), split horizon and poison reverse need 3; on a triangle A-B-C with D behind C, after the link C-D fails ALL THREE versions need 15 rounds (split horizon and poison reverse do not help). MODEL: synchronous rounds, infinity = 16 as in RIP, every router sends its whole vector every round, link failures are noticed instantly; real RIP uses 30-second periodic updates, triggered updates and timers, so real convergence times differ. The statement that a vector for k rounds of RIP reflects paths of k + 1 links follows from the model (round 0 holds the direct neighbours). QUOTED, not verified: RIP parameters (hop-count metric, maximum 15, infinity 16, 30 s updates, 180 s timeout), the classification of RIP as an interior gateway protocol, and the textbook claim that loops of three or more routers are not removed by split horizon. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (CRC remainders, binomial tail, checksums); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose). No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Network address translation

Link state routing