Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 79 ยท Routing

Distance-Vector Routing

Learn how distance-vector routers share tables with neighbors, why Bellman-Ford works, how count to infinity happens, and how split horizon and RIP fix it.

Link-state routing gives every router the full map. Distance-vector routing takes the opposite approach: a router knows almost nothing about the network except what its neighbors tell it. It does not know the topology. It only knows, for each destination, "how far" and "in which direction".

That sounds like gossip, and it is. Each router periodically tells its neighbors "here are the destinations I can reach and what each costs me". Each neighbor adds the cost of the link to me and keeps whichever offer is cheapest. After a few rounds of gossip, everyone has a good route to everything. The approach is simple and uses little memory and CPU, which is why the Internet's first routing protocol (RIP) was so easy to implement. It also has a famous weakness, which this lesson shows in action.

The distance vector and the Bellman-Ford equation

A distance vector is a list of pairs (destination, cost). Every router keeps one table with a row per destination: the best known cost and the next hop, the neighbor to send packets to. Every router also remembers the latest vector that each neighbor sent.

When router X receives a vector from neighbor Y, it updates its table with the Bellman-Ford equation:

TEXT
cost(X, D) = min over all neighbors Y of ( link_cost(X, Y) + cost(Y, D) )

In words: the best way to reach D is to pick the neighbor whose offer (my cost to reach it, plus its claimed cost to D) is the smallest. If the winner changes the table, X sends its new vector to its neighbors, and they repeat the calculation. The process stops when a full round changes nothing, which is called convergence.

flowchart LR
    A["A<br/>to D: ?"] -- "1" --> B["B<br/>to D: 3"]
    A -- "4" --> C["C<br/>to D: 1"]
    B -- "2" --> C
    C -- "1" --> D["D"]

A compares two offers for reaching D: via B costs 1 + 3 = 4, via C costs 4 + 1 = 5. B wins, so A's next hop for D is B.

Three properties set distance-vector apart from link-state:

  • Neighbors only. A router talks only to routers it is directly connected to.
  • Whole table. A router shares its entire table, not just facts about its own links.
  • Second-hand information. What a neighbor claims is taken on trust. The router cannot check it against a map, because there is no map. This is why distance-vector is sometimes called "routing by rumor".

Watching a network converge

The simulation below runs the algorithm on four routers. Every round, each router looks at the vectors its neighbors sent in the previous round and recomputes its table with the Bellman-Ford equation. It stops when nothing changes.

Python Distance-vector routers converge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The direct link between A and C costs 4, but A's best route to C is through B at a total cost of 3, and the table says via B. Notice that A never saw the link between C and D. It learned about D only because C told B and B told A, which is why information needs several rounds to travel across the network. Roughly speaking, a change needs one round for every hop it has to travel.

The count-to-infinity problem

Good news travels fast in distance-vector routing: a new, cheaper route spreads in a few rounds. Bad news travels slowly. Take a simple line A - B - C where every link costs 1. A reaches C through B, with cost 2. Now the link B-C breaks.

  1. B notices at once that it has lost its direct route to C.
  2. Before B can tell anybody, A's regular update arrives: "I can reach C with cost 2".
  3. B has no other idea how to reach C, so it believes A: "C is 3 away, via A".
  4. B tells A its new cost. A's next hop for C is B, so A follows B and updates to 4.
  5. B hears the new offer from A: C is now 5 away. And so on.

The two routers trade packets for C back and forth, each raising its cost by 2 every round. That is a routing loop, and the cost "counts to infinity" slowly. Meanwhile real packets for C bounce between A and B until their TTL runs out. Protocols limit the damage by defining a small infinity; RIP uses 16, so counting stops at 16.

sequenceDiagram
    participant A
    participant B
    Note over B: Link B-C fails
    A->>B: C costs 2
    Note over B: C costs 3 via A
    B->>A: C costs 3
    Note over A: C costs 4 via B
    A->>B: C costs 4
    Note over B: C costs 5 via A
    Note over A,B: ...until infinity

B adopts A's stale route, which goes through B itself. The loop continues until the cost reaches infinity.

Split horizon and poison reverse

The root cause is that A advertised to B a route that goes through B. That information is useless to B and harmful. Two simple rules fix the common case:

  • Split horizon. A router never advertises a route back out of the interface it learned it from. A learned C from B, so A stays silent about C when talking to B.
  • Split horizon with poison reverse. Instead of staying silent, A actively advertises that route with an infinite cost: "I cannot reach C through you, it costs 16." This is more explicit and clears wrong routes faster, because silence could simply mean the update was lost.

Both rules are cheap. The next example compares them with plain distance-vector on the broken line A - B - C.

Python Count to infinity and its fixes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With plain distance-vector the two routers need eight rounds, and while they count, traffic for C ping-pongs between them. With split horizon or poison reverse, B never hears the bogus route, so both routers agree after one round.

Split horizon only stops loops between two neighbors. A loop through three or more routers can still form, because the stale route reaches its origin from a different direction. Real protocols add more tools: triggered updates (send a changed route immediately, without waiting for the timer), hold-down timers (ignore worse offers for a route that just failed, for a while) and the small maximum metric.

RIP: distance-vector in practice

RIP (Routing Information Protocol) is the classic distance-vector protocol. Its main characteristics:

Property RIPv2
Metric Hop count: each router crossed adds 1
Infinity 16 (so the longest usable path is 15 hops)
Transport UDP port 520
Update timer Full table every 30 seconds
Timeout A route not refreshed for 180 seconds is marked invalid
Destination of updates Multicast 224.0.0.9 (RIPv1 used broadcast)
Subnet masks Carried in each route in RIPv2; RIPv1 was classful and had none
IPv6 RIPng, on UDP port 521

RIP's hop-count metric ignores bandwidth: a path of two slow links beats a path of three gigabit links. The 15-hop limit makes RIP unsuitable for large networks, and the slow convergence after a failure (minutes in the worst case) is a problem for anything time-sensitive. Today RIP is mostly found in small networks, labs and old equipment. EIGRP, a Cisco protocol, is an advanced distance-vector design that uses a composite metric and a loop-free algorithm (DUAL) to converge quickly.

The same idea also lives outside classic routing. BGP, which routes between organizations, is a path-vector protocol: it carries the full list of networks a route has crossed, and a router rejects any route that already contains its own name. That removes count to infinity completely.

EIGRP: an advanced distance-vector protocol

EIGRP (Enhanced Interior Gateway Routing Protocol) began as a Cisco protocol and was published as an informational RFC (7868) in 2016. It still shares tables with neighbors like RIP does, but it fixes RIP's biggest problems with four ideas:

  • Neighbors and reliable updates. EIGRP routers find each other with small hello packets (multicast 224.0.0.10, IP protocol 88, every 5 seconds on fast links with a 15-second hold time) and then exchange updates reliably. After the first full exchange they send only changes, not the whole table every 30 seconds.
  • A composite metric. Instead of hops, the classic metric combines the lowest bandwidth on the path and the total delay. With the default "K values" (only bandwidth and delay count), metric = 256 x (10,000,000 / lowest bandwidth in kbit/s + total delay in microseconds / 10). A 15-hop path of fast links can beat a 2-hop path through a slow one. (Newer "wide metrics" use larger numbers for very fast links.)
  • DUAL, the Diffusing Update Algorithm, guarantees loop-free paths. A router only accepts a backup route if it provably cannot loop (the feasibility condition, below).
  • Fast failover. When the best route fails and a safe backup exists, the router switches to it immediately with no waiting and no query.

The next program computes classic EIGRP metrics for two paths and then applies DUAL's rules.

Python EIGRP metric and feasible successors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The feasibility condition is the heart of DUAL: a neighbor can be a feasible successor only if its own distance to the destination (its reported distance) is smaller than my best distance (the feasible distance). A neighbor that is that close to the destination cannot be routing through me, so using it can never create a loop. N3 above fails the test because it reports 500, which is larger than 400, so it might be sending traffic back through R. When no feasible successor exists, the router sends queries to its neighbors and waits for replies before choosing a new route; during that time the route is "active". This approach is what removes count to infinity without relying on a hop limit.

IS-IS (Intermediate System to Intermediate System) is a link-state protocol like OSPF: every router floods its links, builds the same database and runs Dijkstra. It comes from the OSI protocol suite, and its great difference is that it runs directly over layer 2, not over IP. That makes it independent of the IP version: the same protocol carries IPv4 and IPv6 routes (OSPF needed a separate version 3 for IPv6). Many large ISPs and data-center networks use it because it scales well and is simple to extend.

Topic OSPF IS-IS
Carried over IP (protocol 89) Directly in layer 2 frames
Area border Inside the router, between interfaces in different areas On the link: each link belongs to a level
Hierarchy Backbone area 0 plus other areas Level 1 (inside an area) and Level 2 (between areas)
Router addresses IPv4 router IDs A NET (an OSI address), for example 49.0001.0000.0000.0001.00
LAN leader Designated router and a backup Designated IS (no backup; it can be replaced at any time)
Extensibility New LSA types Flexible TLV (type-length-value) fields

A Level 1 router knows only its own area and sends everything else toward the nearest Level 2 router. A Level 1/2 router sits on the border. The Level 2 routers form a contiguous backbone that connects all the areas.

Each protocol also has an administrative distance (a Cisco-style trust rating, lower is preferred) used when several protocols offer a route to the same network: connected 0, static 1, internal EIGRP 90, OSPF 110, IS-IS 115, RIP 120. The router installs the route from the most trusted protocol first, and compares metrics only within one protocol, because a RIP hop count and an EIGRP number cannot be compared.

Question Distance-vector Link-state
Knowledge Distance and next hop Whole topology
Messages Whole table, to neighbors, periodically Own links, to everybody, on change
Computation Light Heavier (Dijkstra)
Convergence Slower, loops possible Faster
Scale Small networks Large networks
Examples RIP, EIGRP OSPF, IS-IS

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which statement describes distance-vector routing?

    Distance-vector routers exchange their tables with directly connected neighbors and apply the Bellman-Ford equation. There is no central server and no full map.
  2. 2. In the first example, why does A reach C through B at cost 3 instead of using the direct link of cost 4?

    Bellman-Ford adds the link cost to the neighbor's advertised cost: A-B is 1 and B-C is 2, a total of 3, which beats the direct cost of 4.
  3. 3. What does split horizon do?

    Telling B about a route that goes through B only invites B to adopt a stale loop, so split horizon suppresses it. Poison reverse sends it with infinite cost instead.
  4. 4. Why does RIP define 16 as infinity?

    Without a limit, two routers would keep raising a dead route's cost forever. A small infinity bounds the loop, at the cost of a maximum network diameter of 15 hops.

Summary

  • Distance-vector routers share their whole table with neighbors and update with the Bellman-Ford equation: the cost is the minimum, over all neighbors, of link cost plus the neighbor's cost.
  • They know distances and next hops, not the topology, so they trust second-hand information.
  • Bad news spreads slowly, and routers can count to infinity in a routing loop.
  • Split horizon, poison reverse, triggered updates, hold-down timers and a small infinity reduce the problem.
  • RIP uses hop count, infinity = 16, UDP port 520 and 30-second updates; it suits only small networks.
  • EIGRP is an advanced distance-vector protocol: a bandwidth-and-delay metric, partial updates, and DUAL, which accepts a backup route (a feasible successor) only when its reported distance is below the best distance, so it cannot loop.
  • IS-IS is a link-state protocol like OSPF that runs directly over layer 2 with Level 1 and Level 2 routing; administrative distance ranks protocols (EIGRP 90, OSPF 110, IS-IS 115, RIP 120).
  • Link-state converges faster and scales better; distance-vector is simpler and lighter.

Next, see how routing works between organizations in BGP and Inter-Domain Routing.