Routing algorithms: link state and distance vector

Routers find paths by talking to each other. Think of the network as a graph: routers are nodes, links are edges, and each link has a cost (its delay, or a value set by the operator). Two families of algorithms find the cheapest paths.

Link state (OSPF)

Every router floods a small message to all others: "I am A; my links go to B with cost 1 and to C with cost 5". Soon every router has the whole map, and each one runs Dijkstra's algorithm to find the cheapest path to every destination. OSPF, used inside most company and ISP networks, works this way. (See Dijkstra step by step in the DSA Lab.)

Distance vector (RIP)

Here nobody has the map. Each router keeps a distance vector: its best known cost to every destination. Again and again, every router sends its vector to its neighbours, and updates its own with the Bellman-Ford rule:

cost to D = the smallest, over neighbours N, of (link cost to N + N's cost to D)

cost = {"A": {"B": 1, "C": 5}, "B": {"A": 1, "C": 2}, "C": {"A": 5, "B": 2, "D": 1}, "D": {"C": 1}}
routers = ["A", "B", "C", "D"]
INF = 99

# At first each router knows only its own links.
dist = {r: {d: 0 if r == d else cost[r].get(d, INF) for d in routers} for r in routers}

changed, rounds = True, 0
while changed:
    changed, rounds = False, rounds + 1
    new = {r: dict(dist[r]) for r in routers}
    for r in routers:
        for n, c in cost[r].items():          # every neighbour's vector
            for d in routers:
                if c + dist[n][d] < new[r][d]:
                    new[r][d] = c + dist[n][d]
                    changed = True
    dist = new
    print("after round", rounds, "A knows:", dist["A"])

After a few rounds nothing changes: the tables have converged. Each router only ever talks to its neighbours and never knows the whole map.

Bad news travels slowly

Good news (a new cheap link) spreads fast. Bad news does not. Suppose the link from B to C breaks. B no longer reaches C directly, but A still says "I can reach C at cost 2" (through B itself!). B believes it and uses cost 3 via A; then A updates to 4 via B, and so on: the count-to-infinity problem. RIP limits it by treating 16 as infinity, and with split horizon: never tell a neighbour about a route you learned from that neighbour.

Between the networks of different companies, the internet uses BGP, which also sends routes to neighbours but chooses them by policy (business agreements) as well as by length.

Mark lesson complete