Computer Networking › Section E · The network layer: control plane › Topic E.1
Routing algorithms: link state and distance vector
Forwarding tables do not fill themselves. Behind every table is a routing algorithm that treats the network as a graph and finds good paths through it. Two families dominate: link state, where every router sees the whole map, and distance vector, where routers learn only from their neighbours.
The control plane's job
The control plane must fill each router's forwarding table so that datagrams follow good paths. It can be organised in two ways, as Forwarding, routing, and network service explained: each router runs a routing algorithm and talks to its neighbours, or a logically centralised controller computes tables and installs them. Either way, the heart of the job is a routing algorithm. Its input is a picture of the network; its output is, for each router and each destination, the next hop that lies on a least-cost path. This topic covers the two classic algorithms; the protocols built on them follow in the next topics.
Networks as graphs
Model the network as a graph: routers are nodes, and links are edges, each with a cost. The cost may be set by an operator, perhaps inversely to bandwidth so that fast links are preferred, or it may reflect delay. The cost of a path is the sum of its link costs, and a routing algorithm seeks a least-cost path between each pair of nodes; when all costs are 1, that is simply the path with fewest hops. Algorithms are classified three ways. Centralised (global) algorithms know the whole graph; decentralised ones compute iteratively from neighbours. Static algorithms change routes rarely, dynamic ones as the topology changes. Load-sensitive ones let costs follow congestion.
Link-state routing and Dijkstra
In link-state (LS) routing, every router broadcasts the costs of its own links to all other routers, so each ends up with an identical, complete map. Each router then runs Dijkstra's algorithm from itself. Dijkstra keeps a set of finished nodes whose least-cost distance is known, starting with the source at distance 0. In each step it adds the unfinished node with the smallest current estimate, then checks that node's neighbours: if going through the new node is cheaper than a neighbour's current estimate, it lowers the estimate and records the predecessor. After as many steps as there are nodes, every distance is final, and following predecessors back gives each path.
Worked example: Dijkstra from A
Links: A–B 4, A–C 1, B–C 2, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3. 1. Finish A (0); estimates B 4, C 1. 2. Finish C (1); via C, B drops to 3, D becomes 9, E 11. 3. Finish B (3); via B, D drops to 8. 4. Finish D (8); via D, E drops to 10 and F becomes 14. 5. Finish E (10); via E, F drops to 13. 6. Finish F (13). Least-cost paths: A–C–B (3), A–C–B–D (8), A–C–B–D–E (10), A–C–B–D–E–F (13). Check: every path starts A–C, so A's forwarding table sends traffic for all five destinations to C, even B, whose direct link costs 4.
Costs of link state
With n routers, the simple form of Dijkstra examines up to n nodes in each of n steps, so its work grows like \(n^2\); heap-based versions are faster. Each router must also receive every other router's link-state message, so a change floods the whole network. In return, every router has full information and recomputes quickly. One hazard affects load-sensitive costs: if link costs track the traffic on them, all routers may move traffic off a busy path at once, making the other path busy, and swing back next round. Avoiding this oscillation is one reason real networks use fixed costs or stagger their recomputations.
Distance-vector routing and Bellman-Ford
Distance-vector (DV) routing is decentralised, iterative and asynchronous. Each router x keeps a distance vector, its estimate \(D_x(y)\) of the least cost to every destination y, and sends it only to its directly attached neighbours. When a vector arrives, x applies the Bellman-Ford equation:
where v ranges over x's neighbours and \(c(x,v)\) is the link cost. The neighbour achieving the minimum becomes the next hop. If x's vector changes, it sends the new one on. Without any router seeing the whole map, the estimates settle on the true least costs.
Worked example: one Bellman-Ford update
Router A has neighbours B (link cost 3), C (cost 1) and D (cost 6). Their latest vectors give these costs to destination T: B 4, C 5, D 2. 1. Via B: \(3 + 4 = 7\). 2. Via C: \(1 + 5 = 6\). 3. Via D: \(6 + 2 = 8\). 4. So \(D_A(T) = 6\), with next hop C, even though D is closest to T. 5. A sends its neighbours a vector with cost 6 to T. Check: the choice depends on the sum of link cost and the neighbour's distance, never on either alone. If C later reports 9, A would switch to B at cost 7.
Count to infinity
Good news spreads fast in DV; bad news can crawl. Take a line X–Y–Z with link costs 1, so Y's cost to Z is 1 and X's is 2 via Y. Now the Y–Z link fails. Y sees that X claims cost 2 to Z, not realising that path runs back through Y, so Y picks 1 + 2 = 3 via X. X then updates to 1 + 3 = 4 via Y, and the two keep raising each other by 2. A packet for Z bounces between them meanwhile. Simulating synchronous rounds, both reach 16, the value RIP treats as infinity, after 15 rounds. Poisoned reverse helps: X, routing to Z through Y, tells Y its cost is infinite, so Y learns at once there is no route, though loops of three or more routers can still count up.
Comparing the two
Messages: LS floods each link's cost to every router; DV exchanges vectors only between neighbours, but a change may trigger several rounds. Speed: LS recomputes from full information, while DV can loop and count to infinity while converging. Robustness: in LS a faulty router can only lie about its own links, and each router computes its own table; in DV one router's wrong distance spreads to everyone who uses it. Both are used in practice: OSPF and IS-IS are link state, and the Routing Information Protocol (RIP) is a distance-vector protocol. The internet's inter-domain protocol, BGP, descends from the distance-vector idea.
Common mistakes to avoid
First, picking the next hop by the shortest link alone; least cost means the sum along the whole path. Second, finalising a node in Dijkstra before it has the smallest estimate among unfinished nodes. Third, forgetting to record predecessors, which you need to read off paths and next hops. Fourth, in Bellman-Ford, using a neighbour's distance without adding the link cost to that neighbour. Fifth, thinking DV routers know the topology; they know only neighbours' vectors. Sixth, believing poisoned reverse solves every count-to-infinity case; it fails for loops of three or more.
Key takeaways
Routing algorithms find least-cost paths in a graph whose edge costs are set by operators or measured. Link-state routing floods every link cost so each router has the full map and runs Dijkstra, adding the closest unfinished node each step; it costs about \(n^2\) work and can oscillate with load-based costs. Distance-vector routing exchanges vectors with neighbours and applies \(D_x(y) = \min_v \{c(x,v) + D_v(y)\}\). DV spreads good news fast but can count to infinity after failures; poisoned reverse helps only for two-router loops. OSPF and IS-IS use link state; RIP uses distance vector.
Flashcards
Flashcard
The path whose summed link costs are smallest
Test your understanding
Question 1 of 5
Links: S–T cost 5, S–U cost 2, U–T cost 1, T–V cost 1, U–V cost 6. What is the least cost from S to V?
Question 2 of 5
In each step of Dijkstra's algorithm, which node is added to the finished set?
Question 3 of 5
Router X has neighbours P (link cost 2), Q (cost 5) and R (cost 1). They report costs to destination W of 9, 3 and 10. What is X's cost to W, and its next hop?
Question 4 of 5
In a line X–Y–Z, the Y–Z link fails. Why can Y wrongly choose a path to Z through X?
Question 5 of 5
Which is an advantage of link-state over distance-vector routing?
