Routing Algorithms: Distance Vector, Link State, OSPF

A packet crossing the internet passes through a dozen or more routers, and each one makes a decision on its own: which neighbour should get this packet next? Routing is how those decisions are prepared. Routers run algorithms that learn the network's shape, compute good paths and write the results into routing tables; forwarding then uses those tables, packet by packet. This note covers the table itself, the two families of routing algorithm with worked examples, and the three protocols interviewers name: RIP, OSPF and BGP.

Routing vs forwarding

The routing table and longest prefix match

Each entry says: for destinations in this prefix, send to this next hop through this interface. A router may hold overlapping entries and picks the longest matching prefix, the most specific route.

1. 10.1.2.5 matches 4 entries (/8, /16, /24, /0). The longest prefix, 10.1.2.0/24, is the most specific route and wins: next hop 192.168.3.2 on eth3.
2. 10.1.9.9 matches 3 entries (/8, /16, /0). The longest prefix, 10.1.0.0/16, is the most specific route and wins: next hop 192.168.2.2 on eth2.
3. 10.9.9.9 matches 2 entries (/8, /0). The longest prefix, 10.0.0.0/8, is the most specific route and wins: next hop 192.168.1.2 on eth1.
4. 8.8.8.8 matches only the default route, 0.0.0.0/0, which matches every address with zero bits. Nothing more specific exists, so it goes to the ISP at 203.0.113.1.

The default route (0.0.0.0/0) matches everything with a prefix length of zero, so it is used only when nothing more specific matches. A home router's table is little more than its LAN plus a default route to the ISP. The prefixes themselves come from IP addressing and subnetting.

Static vs dynamic routing

On Cisco routers, when two sources offer a route to the same prefix, the one with the lower administrative distance wins: directly connected 0, static 1, eBGP 20, OSPF 110, RIP 120. The prefix length is compared first, so a more specific route always beats a more trusted but shorter one.

Distance vector routing (Bellman-Ford)

Each router keeps a distance vector: its best-known cost to every destination and the next hop for it. Periodically, and whenever something changes, it sends this vector to its neighbours only. On receiving vectors, router x recomputes, for every destination y:

D(x, y) = min over each neighbour v of [ cost(x, v) + D(v, y) ]

This is the Bellman-Ford equation, run in a distributed way: no router ever sees the whole map.

Worked example

Four routers with these link costs: A–B 2, A–C 5, B–C 1, C–D 2. In each round, every router recomputes its vector from its neighbours' vectors of the round before.

1. Round 0: each router knows only its own links. B's vector is (A 2, B 0, C 1, D ∞) and C's is (A 5, B 1, C 0, D 2); D is unreachable from A and B because neither touches it.
2. Round 1: every router adds its link cost to each neighbour's round-0 vector and keeps the minimum. A finds C cheaper through B, 2 + 1 = 3, than over its own link (5), and reaches D for the first time at 5 + 2 = 7 via C. 6 entries change.
3. Round 2: B learned D at cost 3 in round 1, and that news reaches A now: 2 + 3 = 5 via B beats 7 via C, so A switches its route to D. 2 entries change.
4. Round 3: recomputing from round 2's vectors changes nothing anywhere, so the network has converged. No router ever saw the whole map, only its neighbours' distances.

A's vector as the rounds go by, the numbers to write on paper:

A third round changes nothing: the network has converged. Notice that A's best route to D needed two rounds, because B had to learn D before it could tell A.

The count-to-infinity problem

Good news travels fast in distance vector routing; bad news travels slowly. Take a line A–B–C with every link cost 1, and let the B–C link fail.

1. Before the failure, every link costs 1: B reaches C directly at cost 1, and A reaches C through B at cost 2.
2. The B–C link fails. B drops its direct route, but A is still advertising cost 2 to C, and nothing in that number says the path runs through B itself.
3. B believes A's advertisement and sets its cost to C to 1 + 2 = 3 via A — a route that loops straight back through B.
4. A hears B's 3 and raises its own cost to 4. Each exchange adds one link's cost, and each router's route points at the other.
5. B hears A's 4 and raises its own cost to 5. Each exchange adds one link's cost, and each router's route points at the other.
6. They keep counting, one exchange at a time, until the cost reaches RIP's infinity, 16: 15 exchanges in all before both routers finally agree that C is unreachable.
7. With split horizon, A never advertises C to B, because B is A's next hop for it. B has no route the moment the link fails, and A hears that C is unreachable in the next exchange: 2 exchanges instead of 15.

B believes A's advertisement, not knowing that A's route goes through B itself, and the two count upwards until the cost reaches "infinity", which RIP defines as 16. The fixes:

• Split horizon: never advertise a route back to the neighbour you learned it from. A would not tell B about C at all.
• Poison reverse: advertise it back, but with cost ∞, so B knows at once that A has no independent path.
• Hold-down timers ignore new information about a failed route for a while, and triggered updates send bad news immediately instead of waiting for the next periodic update.

Split horizon fixes two-router loops but not every loop among three or more routers; the hop limit is the final backstop.

Link state routing (Dijkstra)

In link state routing each router:

1. discovers its neighbours (with hello messages) and measures the cost of each link;
2. builds a link state advertisement (LSA) describing its own links;
3. floods the LSA to every router in the area, so all routers hold an identical link state database, a full map;
4. runs Dijkstra's shortest path first algorithm with itself as the source and installs the resulting next hops.

Worked example

Five routers with these link costs: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2. Router A runs Dijkstra: at each step it settles the unsettled node with the smallest tentative distance and relaxes that node's links. On paper, write one row per step: the node settled, then every other node's current distance and predecessor.

1. Router A holds the full map from the flooded link state advertisements and runs Dijkstra with itself as the source: its own distance is 0, every other router starts at ∞.
2. Settle A at 0 and relax its links: B gets 4, C gets 2.
3. The smallest unsettled distance is C at 2, so it is settled. Relaxing its links: B improves from 4 to 2 + 1 = 3, D gets 10, E gets 12.
4. The smallest unsettled distance is B at 3, so it is settled. Relaxing its links: D improves from 10 to 3 + 5 = 8.
5. The smallest unsettled distance is D at 8, so it is settled. Relaxing its links: E improves from 12 to 8 + 2 = 10.
6. Settle E at 10, the last router. Every distance is now final: a settled node is never improved, because all links have non-negative cost.
7. The shortest paths form a tree rooted at A, and A installs only the first hop of each: every destination goes via C. The links on no shortest path at all are A–B (4), C–D (8) and C–E (10), the direct A–B link among them.

A's routing table:

Every next hop is C, and the direct A–B link (cost 4) is not used at all. The algorithm itself is covered in depth in the Dijkstra's algorithm lesson.

Distance vector vs link state

Interior and exterior gateway protocols

The internet is made of autonomous systems (ASes): networks run by one organisation under one routing policy, each with an AS number. Routing works at two levels:

• Interior gateway protocols (IGPs) route inside one AS and look for the best path by a metric: RIP, OSPF, IS-IS and Cisco's EIGRP.
• Exterior gateway protocols route between ASes. The only one in use is BGP (version 4). It is a path vector protocol: each route carries the list of ASes it has passed through, so a router that sees its own AS number in the list rejects the route, which prevents loops. Routes are chosen by policy (business relationships, preferences) rather than by shortest distance. BGP between ASes is eBGP; BGP carrying those routes inside one AS is iBGP.

RIP vs OSPF vs BGP

OSPF's areas keep flooding and Dijkstra runs local: routers in one area hold the full map only of that area, plus summaries of the others through the backbone.

Common mistakes

• Choosing a route by administrative distance before prefix length: the longest prefix is compared first.
• Saying distance vector routers know the topology: they know only distances and next hops.
• Saying RIP's limit is 16 hops: 15 is the maximum usable; 16 means unreachable.
• Calling BGP a distance vector protocol: it is path vector, and it chooses by policy.
• In Dijkstra, settling a node before it has the smallest tentative distance, or forgetting to update a neighbour that improves.
• Assuming split horizon prevents every routing loop: it fixes only loops between two routers.

Interview questions

How does a router choose between overlapping routes to a destination? First by longest prefix match: the most specific matching entry wins. If two sources offer the same prefix, the lower administrative distance wins (on Cisco, static 1 beats OSPF 110, which beats RIP 120). Within one protocol, the lower metric wins.

Explain count-to-infinity and how split horizon helps. After a link fails, two distance vector routers can each believe the other still has a path, and they raise their costs by one link at a time until they hit the protocol's infinity. Split horizon stops a router from advertising a route back to the neighbour it learned it from, which removes the false path between two routers.

Why does OSPF converge faster than RIP? OSPF floods link changes to every router at once and each router recomputes its paths from a complete map, so news spreads in one flooding wave. RIP passes changes only between neighbours, often on a 30-second timer, and can count to infinity before settling.

Why does OSPF divide a network into areas? In a large network, flooding every change everywhere and rerunning Dijkstra on a huge map costs bandwidth, memory and CPU. Areas confine detailed link state to each area and exchange only summaries through backbone area 0, which keeps databases small and contains instability.

What is BGP, and why is it called a path vector protocol? BGP is the protocol autonomous systems use to exchange reachability across the internet. Each advertisement carries the full list of ASes on the path, which lets routers detect loops and apply policies, such as preferring a customer's routes or avoiding a particular network.

Why does RIP limit paths to 15 hops? To bound count-to-infinity: with 16 defined as unreachable, a counting loop ends after a limited number of exchanges. The cost is that RIP cannot serve networks wider than 15 hops, one reason larger networks use OSPF.

What is a default route, and when is it used? A default route, 0.0.0.0/0, matches every destination with the shortest possible prefix, so it is used only when no more specific route matches. Edge networks use it to send all internet-bound traffic to their ISP without holding the full internet routing table.

Next, read the data link layer, and test the algorithms with the Computer Networks (Intermediate) skill test.