Routing Protocols

Routing is the process of deciding paths; forwarding is the act of moving a packet according to that decision.

The organising fact is that a routing algorithm is defined by what a router knows and when it learns it.

A distance vector router knows only what its neighbours tell it, which is a summary of their distances with no explanation. A link state router knows the entire topology and computes paths itself.

Every behavioural difference follows from that single distinction. Count-to-infinity happens because a distance vector router cannot tell whether a neighbour's advertised route passes through itself. A link state router cannot make that mistake, because it can see the whole path.

The second organising fact is that routing tables must be kept small enough to search and to store, which is why hierarchy exists. Without it, every router would need an entry for every network on the internet.

The third is that between organisations, the cheapest path is not the wanted path. Interdomain routing is decided by policy and business relationships, which is why BGP carries paths rather than distances.

1. Routing and Forwarding

Forwarding is a local, per-packet action: look up the destination and move the packet to an output port, in nanoseconds.

Routing is a global, ongoing computation that fills the table forwarding consults, running on a timescale of seconds.

Static routing uses manually configured entries, which is fine for small or stub networks and does not adapt to failure.

Dynamic routing computes entries from exchanged information and adapts, at the cost of protocol traffic and convergence delay.

A routing metric assigns a cost to each link. Hop count is simplest; bandwidth, delay and administrative preference are common alternatives, and OSPF conventionally uses inverse bandwidth.

2. Shortest Path and Flooding

Dijkstra's algorithm computes shortest paths from one source to all destinations when all link costs are non-negative.

It maintains a set of finalised nodes and repeatedly moves the nearest unfinalised node into it, relaxing the edges out of that node.

Its complexity is $O(n^2)$ with a simple array and $O(E\log n)$ with a binary heap.

Flooding sends an incoming packet out on every link except the one it arrived on.

It needs no routing information at all and always finds the shortest path, because some copy of the packet travels it.

Its cost is enormous duplication, controlled by a hop counter, by sequence numbers so a node discards packets it has already seen, or by selective flooding along roughly correct directions.

Flooding is used where robustness matters more than efficiency, notably to distribute link state advertisements, and its guarantee of reaching every node is exactly what that job needs.

3. Distance Vector Routing

Each router maintains a vector of distances to every destination and periodically sends it to its neighbours.

On receiving a neighbour's vector, a router updates its own using the Bellman-Ford relation: the distance to a destination through a neighbour is the cost to that neighbour plus the neighbour's advertised distance.

Good news travels fast. A newly available shorter route propagates one hop per exchange round.

Bad news travels slowly, and this is the algorithm's defining flaw.

Count-to-infinity occurs when a link fails. A router loses its route, but a neighbour still advertises a distance to that destination, a distance that was computed through the very router now asking. Each accepts the other's stale advertisement, and the distances climb one step at a time.

Setting infinity to a small number, 16 in RIP, bounds the damage by declaring a destination unreachable once the count reaches it.

Split horizon does not advertise a route back to the neighbour it was learned from, which fixes the two-node loop.

Poison reverse advertises such a route with infinite cost instead of omitting it, which propagates the bad news actively rather than passively.

Neither fixes loops of three or more routers, where the stale information circulates around the cycle rather than bouncing between two nodes, and this limitation is a favourite examination point.

4. Link State Routing

Each router discovers its neighbours and the cost to each, then floods that information to every other router.

The advertisement is small, listing only the router's own links, but every router receives every advertisement.

Once a router holds all advertisements, it has the complete topology and runs Dijkstra locally to compute its own shortest path tree.

Convergence is fast and loops are transient, because every router computes from the same map rather than from second-hand summaries.

Sequence numbers and ages on advertisements prevent old information from overwriting new, and are the fiddly part of any real implementation.

5. Hierarchy and Interdomain Routing

Hierarchical routing groups routers into regions or areas. A router keeps detailed entries for its own area and a single summary entry for each other area.

The table shrinks dramatically and the paths get slightly worse, since a summary cannot express which specific router inside a distant area is nearest.

OSPF implements this with areas connected through a backbone area, and all inter-area traffic passes through the backbone.

An autonomous system is a network under one administration, and routing splits into interior and exterior protocols.

Interior gateway protocols such as RIP and OSPF optimise a technical metric.

The exterior protocol, BGP, optimises policy instead. An operator may prefer a longer path over a customer link to a shorter path over an expensive transit link, and no cost metric can express that.

BGP is a path vector protocol: an advertisement carries the full sequence of autonomous systems the route traverses.

Carrying the path serves two purposes. It permits loop detection, since a router discards any advertisement already containing its own number, and it permits policy decisions based on who is on the path.

RIP and OSPF in Practice

RIP is the classic distance vector protocol. Its metric is hop count, its infinity is 16, and it broadcasts its whole table every 30 seconds, declaring a neighbour dead after 180 seconds of silence.

Those timers are the reason RIP converges slowly, quite apart from count-to-infinity, and they cap the usable network diameter at 15 hops.

OSPF is the standard link state protocol. It uses inverse bandwidth as its metric, floods advertisements only when something changes, and supports areas, authentication and equal-cost multipath.

Equal-cost multipath is worth noting, since it lets a router split traffic across several paths of identical cost, which distance vector protocols cannot express.

Multicast Routing

Unicast delivers to one destination and broadcast to all; multicast delivers to a group whose membership changes over time.

The routing problem becomes building a delivery tree rather than a path, so that each link carries at most one copy of a packet.

A source-based tree is built per sender, giving short paths and much router state. A shared tree uses one tree per group rooted at a rendezvous point, giving less state and longer paths.

Reverse path forwarding is the standard trick: a router accepts a multicast packet only if it arrived on the interface it would use to send unicast traffic back to the source, which prunes duplicates cheaply.

6. Worked Examples

Example 1. Run Dijkstra from node A on this graph: edges A-B cost 4, A-C cost 2, B-C cost 1, B-D cost 5, C-D cost 8, C-E cost 10, D-E cost 2.

Initialise. Distance to A is 0; all others are infinite. The finalised set is empty.

Step 1. The nearest unfinalised node is A at 0. Finalise A and relax its edges: B becomes 4, C becomes 2.

Step 2. The nearest unfinalised node is C at 2. Finalise C and relax: B via C is $2+1=3$, which improves on 4, so B becomes 3. D via C is $2+8=10$. E via C is $2+10=12$.

Step 3. The nearest is B at 3. Finalise B and relax: D via B is $3+5=8$, improving on 10, so D becomes 8.

Step 4. The nearest is D at 8. Finalise D and relax: E via D is $8+2=10$, improving on 12, so E becomes 10.

Step 5. Finalise E at 10.

Final distances from A: B is 3, C is 2, D is 8, E is 10.

The shortest path to E is A, C, B, D, E, which is worth tracing, since it uses four hops where a two-hop path A-C-E exists at cost 12.

That is the point of a cost metric. Hop count would have chosen A-C-E; the cost metric chose the longer path because it is genuinely cheaper.

Example 2. Three routers A, B and C in a line, with A-B and B-C each cost 1. Show count-to-infinity when the link from C to a destination network fails.

Before the failure, C reaches the network at cost 1, B at cost 2 through C, and A at cost 3 through B.

The link fails. C now has no route and sets its distance to infinity.

But before C can tell anyone, B advertises its own table, which still says it can reach the network at cost 2.

C accepts this. It reasons that B claims distance 2, so C can reach the network at $2+1=3$ through B.

C does not know that B's route goes through C itself, because a distance vector advertisement carries no path information. This is the entire cause of the problem.

Now C advertises 3. B updates its own route through C to $3+1=4$.

B advertises 4, C goes to 5, and the count climbs.

It stops only when the distance reaches the protocol's infinity, which RIP sets at 16, after which the destination is declared unreachable.

Split horizon fixes this two-node case. B would not advertise the route back to C, since it learned it from C, so C would never adopt the bogus path.

But split horizon fails on a three-node loop. Suppose A, B and C are mutually connected and the destination lies beyond C.

When C's link fails, A can learn a stale route from B, and B can learn one from A, so the obsolete information circulates around the triangle rather than bouncing between two nodes.

Neither split horizon nor poison reverse prevents this, because in each individual exchange the route is being advertised to a router other than the one it was learned from, which is precisely what the rules permit.

Link state routing has no analogue of this failure, because every router computes from the full topology and can see that the failed link is gone.

Example 3. Compare the message complexity of distance vector and link state routing on a network of $n$ routers and $E$ links.

In link state routing, each router originates one advertisement listing its own links.

That advertisement is flooded, traversing every link, so one advertisement costs $O(E)$ transmissions.

With $n$ routers each originating one, the total is $O(nE)$ per full round of flooding.

In distance vector routing, each router sends its whole vector to each neighbour.

A vector has $n$ entries, and the number of neighbour pairs is $E$, so one round costs $O(nE)$ as well.

The totals match, which is why the choice is not made on message volume.

The real differences lie elsewhere.

Convergence time favours link state, since flooding plus a local computation completes in roughly the network diameter, while distance vector needs many rounds and can count to infinity.

Memory favours distance vector, which stores one number per destination, against link state's full topology database.

Computation favours distance vector, whose per-update work is trivial, against Dijkstra's $O(E\log n)$.

Robustness to bad data differs sharply. A distance vector router that advertises wrong distances corrupts its neighbours silently; a link state router advertising a wrong topology is at least advertising something every router can inspect.

Example 4. A network has 900 routers. Compare table sizes under flat routing and under a two-level hierarchy of 30 regions of 30 routers each.

Under flat routing, every router needs an entry for every other router, so each table has 899 entries.

Under the hierarchy, a router keeps detailed entries for the 29 other routers in its own region.

It also keeps one summary entry per other region, which is 29 more.

Total is $29+29=58$ entries, against 899.

The reduction is more than fifteen-fold, and it grows with network size, which is why hierarchy is not optional at internet scale.

The cost is path quality. A summary entry names one way into a distant region, and packets for any router in that region follow it, even when a different entry point would have been closer.

The optimal number of levels for $n$ routers is $\ln n$, with $e\ln n$ entries per router, a classical result worth knowing though rarely applied literally.

With 900 routers that suggests about 7 levels, which no real network uses, because each level adds administrative complexity and further degrades path quality.

Example 5. Why is BGP a path vector protocol rather than a distance vector protocol?

Two reasons, and both matter.

First, loop detection. In distance vector routing, a router cannot tell whether an advertised route passes through itself, which is exactly what causes count-to-infinity.

Carrying the full autonomous system path makes the check trivial: a router discards any advertisement whose path already contains its own number.

At internet scale this matters more than in a small network, since convergence delays measured in minutes would be intolerable and the count-to-infinity bound cannot simply be set to 16.

Second, and more fundamentally, policy cannot be expressed as a distance.

An operator may prefer a five-hop path through a customer to a two-hop path through an expensive transit provider, because the first earns revenue and the second costs money.

No scalar metric can encode that preference, since the decision depends on who is on the path, not on how long it is.

The path vector makes the decision expressible. A router can apply rules referring to specific autonomous systems on the advertised path, preferring, avoiding or refusing routes by identity.

A consequence worth noting: BGP does not compute shortest paths at all. It selects among advertised paths by a sequence of policy rules, with path length appearing only as a tie-breaker some way down the list.

That is why the internet's routes are frequently not the shortest ones available, and why the phrase routing policy describes real commercial relationships rather than a technical optimisation.

Summary

A routing algorithm is defined by what a router knows and when it learns it, and every behavioural difference follows from that.

Routing computes tables on a timescale of seconds; forwarding consults them per packet in nanoseconds.

Dijkstra needs non-negative costs and runs in $O(n^2)$ with an array or $O(E\log n)$ with a heap. Flooding needs no information at all, always finds the shortest path, and is controlled by hop counts or sequence numbers, which is why it distributes link state advertisements.

Distance vector routers exchange whole vectors with neighbours and apply Bellman-Ford. Good news travels one hop per round; bad news causes count-to-infinity, because an advertisement carries no path. Bounded infinity limits the damage, split horizon fixes two-node loops, poison reverse announces them actively, and neither fixes loops of three or more.

Link state routers flood their own link costs and run Dijkstra on the complete map, converging in about the network diameter with only transient loops.

Message complexity is $O(nE)$ for both, so the choice turns on convergence speed, memory and computation instead.

Hierarchy cuts a 900-router table from 899 entries to 58 with two levels, at the cost of path quality, with the theoretical optimum at $\ln n$ levels.

BGP is a path vector protocol because carrying the full autonomous system path gives trivial loop detection and, more importantly, allows decisions based on who is on the path, which no scalar metric can express. BGP does not compute shortest paths; it applies policy.

RIP uses hop count with infinity 16 and broadcasts every 30 seconds, which caps its diameter at 15 hops. OSPF uses inverse bandwidth, floods only on change, and supports areas and equal-cost multipath.

Multicast routing builds a delivery tree rather than a path, choosing between per-source trees with more state and shorter paths and shared trees with less state and longer ones, with reverse path forwarding used to suppress duplicates.