Skip to content
Telecom Networks

Routing: Dijkstra, Bellman-Ford, OSPF and BGP

The network as a weighted graph, Dijkstra's algorithm with proof of correctness, OSPF, the Bellman-Ford equation and distance vectors, count to infinity, autonomous systems and BGP, RPKI.

4 min read 0 comments

A router must know, for every destination, which neighbour to pass a packet to. Nobody writes the tables by hand: the routers compute them themselves, exchanging information through routing protocols. Behind them are two classic graph algorithms. In this lesson we look at Dijkstra’s algorithm with the proof of its correctness, link-state protocols such as OSPF, the Bellman-Ford algorithm and distance-vector protocols with the count-to-infinity problem, and BGP, which holds the networks of the Internet together.

The network as a graph

The network is represented as a graph: routers are the nodes, links the edges, each with a positive cost chosen by the administrator (often inversely proportional to the link speed). The best path between two nodes is the one with minimum total cost.

Dijkstra’s algorithm

In link-state protocols every router floods to all the others the list of its neighbours and costs. In the end every router knows the whole graph and computes by itself the shortest paths to all destinations with Dijkstra’s algorithm (1959):

  1. the source node has distance 0, all others infinite distance; no node is “final”;
  2. among the non-final nodes, choose the one with the minimum tentative distance and make it final;
  3. for each of its neighbours v check whether going through it shortens the route: if d(u) + c(u, v) \lt d(v), update d(v) and record that the predecessor of v is u;
  4. go back to step 2 until all nodes are final.
Weighted graph with the shortest-path tree computed from node A
The numbers in white circles are link costs, the red ones the shortest distances from A. The green links form the shortest-path tree: for instance C is reached through B with cost 3, instead of the direct link of cost 5.

Theorem. If all costs are non-negative, when a node is made final its tentative distance is the shortest distance from the source.

Proof. By contradiction, let u be the first node made final with a distance d(u) greater than the true shortest distance \delta(u). Consider a shortest path from the source to u. It starts at a final node (the source) and ends at u, not yet final: along the path there is therefore a first non-final node y, preceded by a final node x. When x was made final its distance was correct (u is the first error), and step 3 set d(y) \le \delta(x) + c(x, y) = \delta(y), i.e. d(y) = \delta(y). Since costs are non-negative, \delta(y) \le \delta(u), y lying on a shortest path to u. So d(y) = \delta(y) \le \delta(u) \lt d(u): the algorithm should have chosen y before u, contrary to the hypothesis. ∎

With negative costs the argument fails, but in networks costs are always positive. The predecessors form the shortest-path tree: from it the router derives, for every destination, the first hop to use. OSPF (Open Shortest Path First), the most widespread link-state protocol inside company and operator networks, does exactly this, and recomputes the tree in milliseconds when a link changes state.

Bellman-Ford and distance vectors

The alternative does not require knowing the whole graph. Each router x knows only the costs to its neighbours and the distance vectors that the neighbours send it periodically, and applies the Bellman-Ford equation:

    \[ d_x(y) = \min_{v\ \text{neighbour of}\ x}\big(c(x, v) + d_v(y)\big) \]

that is: my distance to y is the best of “cost to reach the neighbour plus the distance the neighbour declares”. Repeating the exchanges, the estimates converge to the true distances. It is the principle of RIP, one of the oldest protocols, simple but slow.

Count to infinity. Bad news travels badly. Take three routers in a line, A, B and C, with costs 1. A is at distance 2 from C via B. If link B-C fails, B looks for an alternative and finds that A declares distance 2 to C: it then thinks it can go through A with cost 3, not knowing that A’s path goes through B itself. A receives B’s new vector and raises its own estimate to 4, B to 5, and so on: distances grow by one at every exchange, while packets for C bounce between A and B. RIP limits the damage by setting infinity at 16 hops; techniques such as split horizon with poisoned reverse (A declares to B infinite distance to destinations it reaches through B) fix the simple cases but not all of them.

BGP and the Internet

The Internet is made of about 75 000 autonomous systems (ASes): networks of operators, universities, companies, each with its own policy. Inside an AS, OSPF or a similar protocol is used; between different ASes BGP (Border Gateway Protocol) is used. BGP is a path-vector protocol: an announcement carries not just a distance but the list of ASes to cross to reach a prefix. This eliminates loops (an AS discards announcements already containing itself) and enables policies: an operator may prefer a longer but cheaper path, or refuse to carry traffic between two competitors.

BGP rests on trust in announcements, and therein lies its weakness: an AS that announces, by mistake or by malice, a prefix that is not its own can attract traffic meant for someone else. Such episodes have made global services unreachable for hours. The countermeasure being rolled out is RPKI, which cryptographically signs which ASes are authorised to announce which prefixes.

Related articles

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x