Routing Algorithms (Distance Vector)

The routing problem

When a packet arrives, a router must decide which neighbour to forward it to so that it reaches its destination along a good path (fewest hops, lowest delay, cheapest cost). Each router keeps a routing table: for every destination, the best known cost and the next hop.

How do routers fill these tables without a central map? Two classic families:

• Distance vector — talk only to your neighbours (RIP).
• Link state — learn the whole map and run Dijkstra (OSPF, IS-IS).

Distance-vector routing

Each router x keeps a vector D(x, y) = its best known cost to every destination y.

1. Start: x knows the cost to itself (0) and to its direct neighbours. Everything else is ∞.
2. Every round, each router sends its vector to its neighbours.
3. Each router updates with the Bellman–Ford equation:

D(x, y) = min over neighbours v of [ cost(x, v) + D_v(y) ]

“My best route to y is: pick the neighbour v for which (cost to reach v) + (v’s distance to y) is smallest — and use v as my next hop.”

4. Repeat until no table changes — the network has converged.

In the 3D model, the table on the right has one row per router. Watch the ∞ entries disappear round by round as good news spreads.

Good news travels fast, bad news slowly

When a link gets cheaper or a new route appears, it spreads in a few rounds. When a link gets worse or fails, routers may keep believing stale routes learned from each other, increasing their costs step by step — the count-to-infinity problem. Try Raise cost of C–D to 9 to see routers re-learn their routes.

Fixes used in practice:

• Split horizon: don’t advertise a route back to the neighbour you learned it from.
• Poison reverse: advertise it back with cost ∞.
• Maximum hop count: RIP treats 16 as infinity.

Link-state routing (for comparison)

Every router floods information about its own links to all routers, so everyone builds the complete map and runs Dijkstra’s algorithm locally.

Between organisations on the internet, BGP (a path-vector protocol) is used.

Code

INF = float("inf")
links = {("A","B"): 1, ("B","C"): 2, ("A","C"): 5, ("C","D"): 1,
         ("B","D"): 4, ("D","E"): 3, ("C","E"): 6}
routers = sorted({r for l in links for r in l})
cost = lambda a, b: 0 if a == b else links.get((a, b), links.get((b, a), INF))
nbrs = {x: [v for v in routers if v != x and cost(x, v) < INF] for x in routers}

D = {x: {y: cost(x, y) for y in routers} for x in routers}       # round 0
for rnd in range(1, len(routers)):
    new = {x: {y: 0 if x == y else min(cost(x, v) + D[v][y] for v in nbrs[x])
               for y in routers} for x in routers}
    if new == D:
        break
    D = new
print(D["A"])   # {'A': 0, 'B': 1, 'C': 3, 'D': 4, 'E': 7}

Common mistakes

• Using the new vectors of other routers within the same round (real routers use what they received last).
• Forgetting to record the next hop — the cost alone doesn’t tell you where to send packets.
• Confusing distance vector (neighbours only) with link state (everyone floods).