Skip to content

Routing (Distance Vector and Link State)

Routing Information Protocol (Bellman Ford)

It maintains a table (a vector) indexed by the destination. - The best known distance to the destination.

  • The outgoing line (neighbor) to use to get there.

The Algorithm

  • Initialization - Each router starts knowing only the distance to its immediate neighbours (often measured as 1 hop). The distance to itself is 0, and to unreachable routers in infinity.
  • Periodically, the routers sends it entire distance vector table to its directly connected neighbours.

  • Update - When a router receives a vector from a neighbor (say, Neighbor X), it calculates new routes using the formula:

  • Distance to Dest D via X = Cost to reach X + X's distance to D

  • The router performs this calculation for every destination via every neighbor and keeps the smallest value.

The Problem: Count-to-Infinity The major weakness of Distance Vector routing is that it reacts rapidly to good news but leisurely to bad news.

  • Good News: If a new short path appears, it propagates 1 hop per exchange, reaching everyone quickly.

  • Bad News: If a router (A) disconnects, its neighbor (B) doesn't immediately know A is gone. B might hear from C that "I have a path to A (which actually goes through B)." B foolishly updates its table to route to A via C. They bounce the packet back and forth, slowly incrementing the distance count until it reaches "infinity" (a value defined as unreachable). Pasted image 20251124002147.png

  • Distance Vector failed in large networks because of the count-to-infinity problem.
  • Each router must discover the entire network topology graph and then independently compute the shortest path to each other router.

1) Discover Neighbours

When a router boots, it sends a special HELLO packet on each point-to-point connection. The routers on the other end send back their names.

2) Measure Line Cost

The router must determine the cost to each neighbour. This is often inversely proportional to the bandwidth. To measure the delay, the router sends an ECHO packet that the neighbour replies immediately. The delay is calculated by division by 2.

3) Build State Packets

The router builds a packet containing its own identity, a sequence number, an age and a list of its neighbours with the associated costs.

4) Distribute Packets The router broadcasts this packet to all other routers. To prevent loops or outdated data, the text emphasises using a 32 bit sequence number, and the age is decremented once per second.

5) Compute New Routes Once a router has a full set of Link State packets, it has a complete map of the network. It runs Djikstra'a Algorithm locally to construct a "Sink Tree" (shortest path tree) from itself to each other node.