Distance vector routing — RIP, Bellman-Ford, count-to-infinity: Question bank

Definition Markup legend & symbols used on this page

Bold marks the verdict word (True / False) at the start of every justification — one consistent convention throughout, no == used for verdicts.
==double equals== is reserved only for a key term the reader should be able to recall as a cloze, never for emphasis.
Symbols, defined once here and used everywhere below:
- $x, y, v$ = network nodes (routers). $y$ is the destination, $x$ the router doing the thinking, $v$ one of $x$ 's neighbours.
- $N (x)$ = the set of $x$ 's directly connected neighbours.
- $c (x, v)$ = cost of the direct link from $x$ to neighbour $v$ (what $x$ can measure itself).
- $d_{x} (y)$ = the true cheapest cost from $x$ to $y$ (the ideal answer).
- $D_{x} (y)$ = $x$ 's current estimate of that cost — the number actually stored and advertised. It converges toward $d_{x} (y)$ but may be temporarily wrong (that gap is what count-to-infinity exploits).
The Bellman-Ford update every claim refers to is: $D_{x} (y) = min_{v \in N (x)} {c (x, v) + D_{v} (y)}, D_{x} (x) = 0, D_{x} (y) = \infty if unknown$ where the minimisation runs over every neighbour $v \in N (x)$ , for one fixed destination $y$ , and $D_{v} (y)$ is the estimate neighbour $v$ advertised to $x$ .

The three topologies these traps keep returning to are drawn once below — refer back to them as you answer.

Figure — Distance vector routing — RIP, Bellman-Ford, count-to-infinity

True or false — justify

Each line is a claim. Decide True or False, and — this is the point — say why.

TF1. A router running distance vector routing knows the full network topology.

False. It only knows the direct-link cost

c (x, v)

to its neighbours plus whatever estimates

D_{v} (\cdot)

those neighbours advertise; it never sees the whole map — that is link-state's job.

TF2. In DV, a router sends its distance vector to every other router in the network.

False. It sends its vector to directly connected neighbours in

N (x)

only; information ripples outward one hop per exchange, it is not flooded everywhere.

TF3. The Bellman-Ford update

D_{x} (y) = min_{v \in N (x)} {c (x, v) + D_{v} (y)}

needs node

x

to compute each

D_{v} (y)

itself.

False. Node

x

does not compute its neighbours' costs; each neighbour

v

tells

x

its current estimate

D_{v} (y)

inside the advertised vector. That messaging is exactly the "distributed" part.

TF4. RIP measures link cost by bandwidth.

False. RIP's metric is hop count — every link costs exactly 1, so

c (x, v) = 1

regardless of speed. That simplicity is deliberate: no bandwidth probing is needed.

TF5. In RIP a route with cost 15 is treated as unreachable.

False. 15 is the maximum valid cost; 16 is defined as

\infty

(unreachable). A path of 15 hops is fine.

TF6. Split horizon completely eliminates count-to-infinity.

False. It only kills the two-node loop (A↔B). In a loop of three or more routers, stale bad news can still travel the long way around, so RIP still needs the 16-cap and triggered updates.

TF7. Good news and bad news both propagate at the same speed in DV.

False. Good news (a shorter route) is adopted the instant one advertisement arrives, because the

min

immediately picks the smaller number. Bad news (a lost route) is different: a router that lost its path can still see a neighbour's stale small estimate and adopt it, so instead of jumping to

\infty

the estimate only crawls up one link-cost per exchange — "good news travels fast, bad news travels slowly."

TF8. Bellman-Ford and Dijkstra can be swapped freely for routing.

False. Dijkstra needs the whole graph and non-negative weights (link-state); Bellman-Ford works from local neighbour info and converges asynchronously — which is exactly why only DV suffers count-to-infinity.

TF9. RIP runs directly over IP with its own transport reliability.

False. RIP is an application-layer protocol running over UDP port 520 — no reliability; a lost update is simply corrected by the next 30-second broadcast.

TF10. Because links are physical wires,

c (x, v)

always equals

c (v, x)

in every DV network.

False. Costs can be asymmetric (directed): the

x \to v

direction may be configured cheaper than

v \to x

(see figure, red arrows). DV handles this fine — each direction is a separate advertised number — but asymmetry can lengthen convergence and change which way a loop forms.

Spot the error

Each statement contains one flaw. Name it and correct it.

SE1. "After a link breaks, node

B

correctly reroutes to

C

via

A

because

A

advertised cost 2."

The error:

A

's cost-2 route to

C

went through $B$ itself. Believing it creates the loop

B \to A \to B

; the "2" is a stale

D_{A} (C)

, not a real alternative path.

SE2. "The Bellman-Ford equation minimises over all destinations."

It minimises over all neighbours

v \in N (x)

for a fixed destination

y

, not over destinations. Each destination gets its own independent minimisation.

SE3. "Poison reverse silently drops the route toward the neighbour it was learned from."

Silent dropping is plain split horizon. Poison reverse actively advertises that route back as cost 16 (

\infty

), removing the ambiguity of a missing entry.

SE4. "With

n

nodes, DV needs

n

exchanges to converge in the worst case."

It needs at most

n - 1

exchanges — after

k

exchanges all nodes within

k

hops of a destination know the truth, and the longest loop-free path has

n - 1

edges.

SE5. "In the update

D_{x} (x) = \infty

until

x

hears from a neighbour."

The base case is

D_{x} (x) = 0

(zero cost to reach yourself). Only unknown destinations start at

\infty

SE6. "Split horizon is applied per-router:

A

hides all its routes from

B

It is applied per-route:

A

hides from

B

only the routes it learned via

B

. Routes learned elsewhere are still advertised to

B

normally.

Why questions

WQ1. Why does DV share with neighbours only, never with distant routers directly?

A router can physically measure only its direct link costs

c (x, v)

; everything farther must be learned second-hand. So facts must ripple, one hop per exchange, from source outward.

WQ2. Why is the Bellman-Ford update guaranteed to find the true shortest path?

By the Principle of Optimality, which says: if the shortest route from $x$ to $y$ passes through $v$ , then the portion from $v$ to $y$ must itself be $v$ 's own shortest route to $y$ — otherwise you could swap in a cheaper tail and beat your supposed shortest path (a contradiction). That is precisely why the update may safely reuse the neighbour's estimate

D_{v} (y)

instead of re-deriving the whole tail.

WQ3. Why does RIP define 16 to mean infinity instead of allowing unlimited costs?

Without a ceiling the count-to-infinity loop increments forever. Capping at 16 bounds the worst-case looping to ~16 steps — a deliberate band-aid, at the cost of limiting network diameter to 15 hops.

WQ4. Why does count-to-infinity increment slowly, step by step, instead of jumping to

\infty

at once?

Each router only nudges its estimate up by one link cost per exchange as it "trusts" a neighbour's slightly-too-high number. No single router ever sees the whole loop, so nobody can jump straight to

\infty

WQ5. Why is DV called "distributed asynchronous Bellman-Ford"?

The same

min

equation is solved, but no central node runs it — each router computes its own

D_{x} (\cdot)

whenever a neighbour's advertisement arrives, on its own schedule, not in lockstep.

WQ6. Why does RIP tolerate lost updates despite using unreliable UDP?

Because the full vector is rebroadcast every 30 seconds; a dropped packet is simply overwritten by the next periodic update, so reliability is unnecessary.

WQ7. Why does the route timeout (180 s) equal six update periods rather than one?

A single missed 30-second update could be mere packet loss. Waiting six periods avoids declaring a live route dead over one unlucky drop, while still detecting genuinely failed neighbours.

Edge cases

EC1. What is

D_{x} (y)

when

x

has never heard of

y

It is

\infty

(in RIP, encoded as 16). The minimisation has no finite candidate yet, so the estimate stays at the "unknown/unreachable" sentinel.

EC2. What does the update give for

D_{x} (x)

, the cost to reach yourself?

Exactly

0

— the fixed base case. You are already there, so no path cost applies.

EC3. In A—B—C, if the B–C link cost were

0

instead of

1

, could count-to-infinity still occur if the link breaks?

Yes. The bug is triggered by the link failing (cost jumping to

\infty

), not by its original value. A stale advertisement bounced back still climbs step by step.

EC4. If a network has exactly 2 routers, can count-to-infinity happen with split horizon on?

No. Split horizon perfectly stops the two-node loop, and two routers cannot form a longer loop — so the two-node case is fully cured.

EC5. What happens in a three-router triangle under split horizon when one link dies?

Bad news can still circulate the long way around the triangle, so count-to-infinity can still occur. Only the 16-cap plus triggered updates/hold-down bound it.

EC6. If two neighbours advertise the same cost to a destination, which does

x

pick?

The

min

ties;

x

may pick either (implementation-defined, often first-seen or lowest next-hop). Correctness of the cost is unaffected — only the chosen next-hop differs.

EC7. What is the effect of a negative link cost on Bellman-Ford routing?

Bellman-Ford's math permits negatives, but a negative cycle makes costs decrease without bound, so no shortest path exists. Real routing metrics (RIP hop counts) are kept non-negative to avoid this.

EC8. When a better (shorter) route appears, how many exchanges before all affected routers adopt it?

It spreads at one hop per exchange, so a node

k

hops away adopts it after

k

exchanges — this is the "good news travels fast" direction, monotonically decreasing costs.

EC9. If the

A \to B

link costs 1 but

B \to A

costs 5 (asymmetric), does DV still converge?

Yes — DV treats each direction as its own advertised number, so

D_{A}

and

D_{B}

each converge to their own true costs. But the asymmetry can make one direction's loop count-to-infinity through more steps than the other, and it can change which route each router prefers, so the two directions need not use the same physical path.

Recall Quick self-test

Root cause of count-to-infinity in one phrase? ::: A router advertises a route back to the very neighbour it learned that route from. Difference between split horizon and poison reverse in one phrase? ::: Split horizon stays silent about such routes; poison reverse actively advertises them as cost 16. Why can't Dijkstra-based OSPF count to infinity? ::: It uses global topology, so no router is ever fooled by a stale second-hand estimate that loops back through itself.