Routing

What routing is about

The previous lesson gave every host an address. This one answers the next question: how does a packet from your laptop in Hyderabad find its way through dozens of routers, owned by several companies, to a server in Frankfurt? At every router the packet reaches, a decision is made: which interface should it leave by? The router makes that decision in nanoseconds using a table, and the table is built in the background by routing protocols that talk to other routers.

Routing is where networking meets graph algorithms, so interviewers love it. Expect to be asked to apply longest-prefix match to a routing table, to simulate distance-vector updates and explain count-to-infinity, to run Dijkstra on a small graph, to compare RIP and OSPF, and to explain why the internet between organisations uses BGP. This lesson works through each with numbers you can check.

Forwarding vs routing

These two words are often mixed up, and separating them is the first thing to get right.

• Forwarding is the local, per-packet action: a packet arrives on an input port, the router looks up its destination address in the forwarding table, and moves it to the right output port. It happens in hardware, in nanoseconds, for every single packet. This is the data plane.
• Routing is the network-wide process of computing the paths that fill those forwarding tables. It runs in software, on timescales of seconds, and involves routers exchanging information. This is the control plane.

An analogy: routing is planning a road trip with a map; forwarding is reading the sign at each junction and turning.

  Control plane   +--------------------------------+
  (routing)       | routing protocol (OSPF, BGP)   |
                  | builds the routing table (RIB) |
                  +---------------+----------------+
                                  | installs best routes
  Data plane      +---------------v----------------+
  (forwarding)    | forwarding table (FIB)         |
  in -->  port -->| lookup dest -> output port     |--> port --> out
                  +--------------------------------+

The routing table (RIB, routing information base) holds all routes learned from all sources. The best ones are installed into the forwarding table (FIB, forwarding information base), which the hardware uses.

In software-defined networking (SDN), the control plane is moved off the routers to a central controller that computes tables and pushes them down, but the split is the same.

Routing tables and longest-prefix match

A routing table entry has, at minimum:

• Destination prefix (network and mask), such as 10.1.2.0/24.
• Next hop: the IP address of the neighbouring router to send to (or "directly connected").
• Outgoing interface.
• Metric: the cost of the route, used to choose between routes from the same protocol.
• Administrative distance (on many routers): how trustworthy the source is, used to choose between routes from different sources. On Cisco, for example, directly connected is 0, static 1, OSPF 110, RIP 120.

Because prefixes can overlap, a destination may match several entries. The rule is longest-prefix match: choose the matching entry with the longest prefix (most specific mask). A /25 beats a /24, which beats a /16, which beats the default route /0.

Worked example: longest-prefix match

A router has this table:

Where does each destination go?

1. 10.1.2.200. It matches /0, /8, /16 and /24. For the /25, the last octet 200 is in 128 to 255, so it matches too. Longest is /25: R4.
2. 10.1.2.5. Matches /0, /8, /16, /24. The /25 covers .128 to .255 only, so no. Longest: /24, R3.
3. 10.1.9.9. Third octet 9 is not 2, so the /24 and /25 fail. Longest: /16, R2.
4. 10.200.0.1. Second octet is 200, not 1, so the /16 fails. Longest: /8, R1.
5. 8.8.8.8. Only the default route matches: ISP.

You can check this with Python:

import ipaddress as ip

table = {"0.0.0.0/0": "ISP", "10.0.0.0/8": "R1", "10.1.0.0/16": "R2",
         "10.1.2.0/24": "R3", "10.1.2.128/25": "R4"}

def lookup(dest: str) -> str:
    addr = ip.ip_address(dest)
    matches = [ip.ip_network(p) for p in table if addr in ip.ip_network(p)]
    best = max(matches, key=lambda n: n.prefixlen)
    return table[str(best)]

for d in ["10.1.2.200", "10.1.2.5", "10.1.9.9", "10.200.0.1", "8.8.8.8"]:
    print(d, lookup(d))   # R4, R3, R2, R1, ISP

Real routers do not scan the whole table; they use tries (prefix trees) or TCAM (ternary content-addressable memory) hardware that compares against all entries at once.

Why longest-prefix match is so useful: an ISP can advertise one big aggregate (10.0.0.0/8) while a few customers inside it have more specific routes that go elsewhere. The specific route wins automatically.

Default routes

A default route 0.0.0.0/0 (IPv6 ::/0) matches every address, so it is used when nothing more specific matches: "if you don't know, send it here." Your laptop's routing table is mostly one default route pointing at the home router, plus a directly connected route for the local subnet. Edge routers of small organisations have a default route to their ISP.

Routers at the core of the internet have no default route at all; they carry the full table, which is the default-free zone, roughly a million IPv4 prefixes today. If a destination is not in it, it is unreachable.

Static vs dynamic routing

Static routes are typed in by an administrator: "to reach 10.5.0.0/16, send to 192.168.1.2."

Dynamic routing uses protocols where routers exchange information and compute routes automatically, adapting when links fail.

A stub network has only one way out, so a single static default route is the right answer; running a protocol there would only add complexity.

Dynamic protocols come in two main families: distance vector and link state. A third, path vector, is used by BGP.

Distance-vector routing

In distance-vector (DV) routing, each router knows only:

• the cost of the links to its direct neighbours, and
• the distance vector each neighbour last advertised: the neighbour's best known cost to every destination.

Each router periodically (or when something changes) sends its own distance vector to its neighbours. No router sees the whole map. It is sometimes summed up as "tell your neighbours what you know about the world."

The Bellman-Ford equation

The best cost from router x to destination y is:

D_x(y) = min over neighbours v of  [ c(x, v) + D_v(y) ]

In words: try every neighbour v; the cost via v is the link cost to v plus v's advertised cost to y; take the minimum. The neighbour that gives the minimum becomes the next hop. Running this repeatedly at every router is the distributed Bellman-Ford algorithm. It converges to correct shortest paths as long as costs are not negative.

Worked example: distance-vector tables

Three routers with link costs X to Y = 2, Y to Z = 1, X to Z = 7.

        X
      2/ \7
      Y---Z
        1

Time 0. Each router knows only its direct links. Each row is "my cost to X, Y, Z".

Time 1. Each router receives its neighbours' vectors and applies Bellman-Ford.

Router X, destination Z:

• via Y: c(X,Y) + D_Y(Z) = 2 + 1 = 3
• via Z: c(X,Z) + D_Z(Z) = 7 + 0 = 7
• Minimum is 3 via Y. X updates its cost to Z from 7 to 3, next hop Y.

Router Z, destination X:

• via Y: 1 + 2 = 3
• via X: 7 + 0 = 7
• Z updates to 3, next hop Y.

Router Y, destination X: via X 2 + 0 = 2; via Z 1 + 7 = 8. Stays 2. To Z: stays 1.

Time 2. X and Z advertise their new vectors. Recomputing changes nothing, so no further updates are sent: the network has converged. The direct X to Z link (cost 7) is not used, because going through Y costs 3.

Good news travels fast, bad news slowly

When a link gets cheaper, the improvement spreads in a few rounds: every router immediately prefers the better offer. When a link fails or gets more expensive, routers can keep believing stale, cheaper routes advertised by neighbours who themselves depended on the broken link. This leads to the count-to-infinity problem.

Worked example: count to infinity

Three routers in a line, each link cost 1:

  A ---1--- B ---1--- C

Converged state: B reaches C at cost 1 (direct); A reaches C at cost 2 (via B).

Now the B to C link fails. B's direct route is gone. But A is still advertising "I can reach C at cost 2." B does not know that A's route goes through B itself, so B computes: via A = 1 + 2 = 3. B now thinks it reaches C at 3 via A. Then A hears B's new vector and updates: via B = 1 + 3 = 4. And so on:

Packets for C bounce between A and B in a routing loop while the costs creep up. Without a limit, this never stops. RIP defines 16 as infinity, so after enough rounds both routers mark C unreachable. That is why RIP only works on networks with at most 15 hops.

Fixes: split horizon and poison reverse

• Split horizon: do not advertise a route back to the neighbour you learned it from. A learned its route to C from B, so A does not tell B about C at all. In the example above, when the B to C link fails, B hears nothing from A about C and correctly marks C unreachable.
• Split horizon with poison reverse: instead of staying silent, advertise the route back to that neighbour with an infinite cost: A tells B "my cost to C is 16." This actively kills any chance that B uses A for C. It costs a larger update message but converges faster.
• Triggered updates: send an update immediately when a route changes, instead of waiting for the next periodic timer.
• Hold-down timers: after a route goes bad, ignore offers of a worse route to it for a while, to let the bad news spread.

Link-state routing

In link-state (LS) routing, every router learns the complete map of the network and computes shortest paths itself.

1. Discover neighbours by sending hello packets on each link.
2. Measure link costs (configured, often based on bandwidth).
3. Build a link-state advertisement (LSA): "I am router R; my neighbours are S (cost 2) and T (cost 5)."
4. Flood the LSA to every router in the area. Each router forwards new LSAs out all other interfaces. Sequence numbers and ages stop old LSAs from overriding new ones.
5. Every router now has the same link-state database, a graph of the whole area.
6. Each router runs Dijkstra's algorithm with itself as the source to build a shortest-path tree, then fills its forwarding table with the first hop of each path.

It is summed up as "tell the world about your neighbours."

Dijkstra's algorithm

Dijkstra finds the cheapest path from one source to every node in a graph with non-negative edge costs.

• Keep a set of finished nodes whose shortest cost is known, starting with just the source (cost 0).
• Keep a tentative cost and predecessor for every other node (infinity at first).
• Repeat: pick the unfinished node with the smallest tentative cost; mark it finished; for each of its neighbours, if going through it is cheaper, update that neighbour's tentative cost and predecessor.

With a binary heap it runs in O((V + E) log V) for V nodes and E edges.

Worked example: Dijkstra step by step

Find the shortest paths from A in this network:

               4             5
        A ----------- B ----------- D
         \            |            /|\
        2 \         1 |         8 / | \ 6
           \          |          /  |  \
            +-------- C --------+  2|   F
                      |             |  /
                      +----- 10 ----E-+ 3

Edges: A-B 4, A-C 2, B-C 1, B-D 5, C-D 8, C-E 10, D-E 2, D-F 6, E-F 3.

Each row shows the tentative (cost, predecessor) after finishing that node. A dash means the node is already finished.

Walk through it:

1. Start at A. Neighbours: B costs 4, C costs 2. Smallest unfinished: C (2).
2. Finish C. Through C: B = 2 + 1 = 3, better than 4, so update B to (3, C). D = 2 + 8 = 10. E = 2 + 10 = 12. Smallest unfinished: B (3).
3. Finish B. Through B: D = 3 + 5 = 8, better than 10, so update D to (8, B). Smallest: D (8).
4. Finish D. Through D: E = 8 + 2 = 10, better than 12; F = 8 + 6 = 14. Smallest: E (10).
5. Finish E. Through E: F = 10 + 3 = 13, better than 14. Smallest: F (13).
6. Finish F. Done.

Follow predecessors backward to read each path:

So A's forwarding table sends every destination to C. Notice that the direct A to B link (cost 4) is not used; A, C, B costs only 3.

import heapq

def dijkstra(graph, src):
    dist = {n: float("inf") for n in graph}
    prev = {}
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u].items():
            if d + w < dist[v]:
                dist[v], prev[v] = d + w, u
                heapq.heappush(heap, (dist[v], v))
    return dist, prev

edges = [("A","B",4),("A","C",2),("B","C",1),("B","D",5),("C","D",8),
         ("C","E",10),("D","E",2),("D","F",6),("E","F",3)]
g = {}
for u, v, w in edges:
    g.setdefault(u, {})[v] = w
    g.setdefault(v, {})[u] = w
print(dijkstra(g, "A"))
# ({'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 13},
#  {'B': 'C', 'C': 'A', 'D': 'B', 'E': 'D', 'F': 'E'})

Distance vector vs link state

RIP vs OSPF

RIP (Routing Information Protocol) is the classic distance-vector protocol. OSPF (Open Shortest Path First) is the most common link-state protocol inside enterprises.

OSPF areas

OSPF scales by splitting the network into areas. Each router floods full LSAs only within its area, so the database and Dijkstra runs stay small. All areas must attach to the backbone area 0. Area border routers (ABRs) summarise one area's routes into others. On broadcast segments like Ethernet, OSPF elects a designated router (DR) and a backup to reduce the number of neighbour relationships and flooded messages.

       +---------- Area 0 (backbone) ----------+
       |  [ABR1]                      [ABR2]   |
       +----|----------------------------|-----+
            |                            |
      +-- Area 1 --+              +-- Area 2 --+
      | R  R  R    |              |  R  R      |
      +------------+              +------------+

Autonomous systems and the internet's two levels of routing

The internet is not one network run by one routing protocol. It is tens of thousands of autonomous systems (AS): networks under a single administrative control with a single routing policy, such as an ISP, a cloud provider, a large company or a university. Each has a globally unique AS number (ASN).

Routing is split into two levels:

• Interior gateway protocols (IGPs) route within one AS. The goal is efficiency: find the shortest path. RIP, OSPF, IS-IS and EIGRP are IGPs. One administrator controls all routers, so they can trust each other.
• Exterior gateway protocols (EGPs) route between ASes. The only one in use is BGP (Border Gateway Protocol, version 4). Here, the goal is policy: which neighbours to use and whom to carry traffic for, often driven by business contracts.

   +----- AS 64500 -----+         +----- AS 64510 -----+
   |  OSPF inside       |  eBGP   |  IS-IS inside      |
   |  [R]--[R]--[Border]|=========|[Border]--[R]--[R]  |
   |   iBGP among       |         |                    |
   |   border routers   |         |                    |
   +--------------------+         +--------------------+

(64500 and 64510 are from the range reserved for documentation.)

BGP basics

BGP is a path-vector protocol. Like distance vector, routers tell neighbours what they can reach. But instead of a single cost, each advertisement carries the full list of ASes the route passes through, the AS_PATH.

Key ideas:

• Sessions over TCP port 179. Two BGP routers (peers) open a TCP connection and exchange routes. eBGP runs between routers in different ASes; iBGP distributes externally learned routes among routers inside one AS.
• Advertisements are a prefix plus attributes, for example: "203.0.113.0/24, AS_PATH 64510 64520, NEXT_HOP 198.51.100.1."
• Loop prevention: a router rejects any route whose AS_PATH already contains its own ASN. That one rule removes the count-to-infinity problem at internet scale.
• Route selection follows a long ordered list. The most important steps, in typical order, are: highest LOCAL_PREF (the local network's own preference, set by policy), then shortest AS_PATH, then lowest origin type and MED (a neighbour's hint about which entry point to use), then prefer eBGP over iBGP, then lowest IGP cost to the next hop (hot-potato routing: hand the packet off as soon as possible), then tie-breakers.
• Policy decides what to accept and what to advertise. A common business pattern: an AS advertises customer routes to everyone, but advertises routes learned from one provider or peer only to its customers. That way it never carries traffic between two other networks for free.

Why the internet uses BGP rather than OSPF

1. Scale. No router could hold or recompute a link-state map of the entire internet, and flooding every link change worldwide would be impossible. BGP routers only exchange reachability of prefixes.
2. Policy over shortest path. Companies choose routes for cost, contracts and politics, not just hop counts. BGP lets each AS apply its own rules; OSPF has no concept of this.
3. Privacy and autonomy. An AS does not want to reveal its internal topology. BGP shares only which prefixes are reachable through which ASes.
4. Loop freedom without global agreement on costs. AS_PATH detects loops even though every AS measures "cost" differently.

BGP risks

BGP trusts what neighbours announce. A misconfigured or malicious AS can announce someone else's prefixes (prefix hijacking) or leak routes it should not, drawing traffic towards itself. More specific prefixes win by longest-prefix match, so a hijacker announcing a /24 inside someone's /22 attracts that traffic. RPKI (resource public key infrastructure) lets networks cryptographically check that an AS is authorised to originate a prefix; adoption has grown but is not universal.

Reading traceroute output

traceroute (Linux, macOS) and tracert (Windows) show the routers on the path to a destination. The addressing lesson explained the mechanism: probes with TTL 1, 2, 3, and so on, each answered by ICMP Time Exceeded. Here is how to read the output.

Example output (addresses are from documentation ranges):

$ traceroute example.org
traceroute to example.org (198.51.100.20), 30 hops max, 60 byte packets
 1  192.168.1.1     1.2 ms   0.9 ms   1.0 ms
 2  10.20.0.1       6.8 ms   7.1 ms   6.5 ms
 3  203.0.113.9     8.4 ms   8.0 ms   9.2 ms
 4  * * *
 5  203.0.113.77   41.5 ms  40.9 ms  42.0 ms
 6  198.51.100.1  142.3 ms 141.8 ms 143.0 ms
 7  198.51.100.20 143.1 ms 142.6 ms 142.9 ms

How to read it:

• Each line is one hop (one router), numbered by TTL. The three times are three separate probes' RTTs.
• Hop 1 is your home router: about 1 ms over the LAN or Wi-Fi.
• Hop 2 is a private 10.x address: the ISP's internal network or carrier-grade NAT. Private addresses appearing inside an ISP are normal.
• Hop 4, * * *: no reply within the timeout. That router probably rate-limits or ignores ICMP. Since later hops answer, the path is fine. Asterisks only matter if they continue to the end.
• Jump at hop 6 (41 ms to 142 ms): about 100 ms extra in one hop usually means a long-distance link, such as a submarine cable between continents. Propagation delay, not congestion.
• A latency spike at one middle hop that disappears later is not a problem: routers answer traceroute in slow software paths with low priority, while forwarding real traffic in hardware. Only latency that persists to the destination is real.
• The same router repeating in a cycle (A, B, A, B) shows a routing loop; the trace runs until the hop limit.
• Hops can show different addresses on different probes when there are equal-cost multiple paths (ECMP) and load balancing.

Tools such as mtr combine ping and traceroute and run continuously, showing per-hop loss over time.

Interview questions

Q1. What is the difference between routing and forwarding?

Forwarding is the per-packet data-plane action of looking up the destination and moving the packet to an output port, done in hardware in nanoseconds. Routing is the control-plane process of computing paths, by running protocols that exchange information, and filling the forwarding table. Routing runs over seconds; forwarding happens for every packet.

Q2. Explain longest-prefix match with an example.

When several table entries match a destination, the router uses the one with the longest mask, because it is the most specific. With entries 10.0.0.0/8 to R1 and 10.1.2.0/24 to R3, the destination 10.1.2.5 goes to R3, while 10.5.0.1 goes to R1. The default route /0 matches everything and is used only when nothing else does.

Q3. What is the Bellman-Ford equation used by distance-vector routing?

D_x(y) = min over neighbours v of c(x,v) + D_v(y). Each router computes its cost to every destination as the cheapest link-cost-plus-advertised-cost among its neighbours, and the neighbour that achieves it becomes the next hop. Routers repeat this as neighbours send new vectors until nothing changes.

Q4. What is count-to-infinity and how is it mitigated?

After a link fails, routers can keep believing stale routes from neighbours that actually depended on the failed link, so costs grow step by step while packets loop. RIP caps it by treating 16 as infinity. Split horizon, poison reverse, triggered updates and hold-down timers reduce or prevent it, though loops of three or more routers can still occur.

Q5. How does split horizon with poison reverse work?

A router advertises a route back to the neighbour it learned it from with an infinite metric. That neighbour will then never route back through it for that destination, killing two-node loops immediately. Plain split horizon just omits the route instead.

Q6. How does link-state routing work?

Each router discovers its neighbours, floods a link-state advertisement describing its links to every router in the area, and builds an identical map. Each router then runs Dijkstra from itself to get a shortest-path tree and installs first hops into its forwarding table. OSPF and IS-IS work this way.

Q7. What is the time complexity of Dijkstra and what is its main limitation?

With a binary heap it is O((V + E) log V). It requires non-negative edge weights, which link costs always are. Bellman-Ford handles negative weights and is naturally distributed, which is why distance-vector protocols use it.

Q8. Compare RIP and OSPF.

RIP is distance vector, uses hop count, limits paths to 15 hops, sends full tables every 30 seconds over UDP 520 and converges slowly. OSPF is link state, uses bandwidth-based cost, has no hop limit, floods changes directly over IP protocol 89, converges quickly and scales with areas. OSPF is preferred for anything but very small networks.

Q9. What is an autonomous system?

A network or group of networks under one administrative authority with one routing policy, identified by an AS number. ISPs, cloud providers and large enterprises run their own ASes. IGPs route inside an AS; BGP routes between them.

Q10. Why is BGP called a path-vector protocol, and how does it avoid loops?

Each route advertisement carries the full list of ASes it has passed through, the AS_PATH. A router rejects any route that already contains its own AS number, which prevents loops without needing a common cost metric.

Q11. Why does the internet use BGP between networks instead of OSPF?

OSPF would require flooding a full map of the internet to every router, which does not scale, and it only optimises for shortest paths. BGP exchanges only prefix reachability, hides internal topology and lets each AS apply business policy, such as preferring a cheaper provider.

Q12. What is a default route and when would you use a static one?

A default route, 0.0.0.0/0, matches every destination and is used when nothing more specific matches. A stub network with a single exit should use a static default route to its ISP, since there is no alternative path to learn and a routing protocol would add complexity.

Q13. In traceroute output, hop 5 shows * * * but hops 6 to 10 respond. Is something broken?

Probably not. The router at hop 5 is forwarding traffic, since later hops respond, but it does not send ICMP Time Exceeded messages or rate-limits them. Only consistent timeouts through to the destination point to a real problem.

Q14. What is administrative distance?

It is a router's ranking of how trustworthy each route source is, used when two sources offer routes to the same prefix. On Cisco routers, for example, a connected route is 0, static 1, OSPF 110 and RIP 120, so OSPF wins over RIP. Metrics compare routes from the same protocol; administrative distance compares different protocols.

Q15. What is BGP hijacking?

An AS announces prefixes it does not own, or more specific parts of them, so other networks route that traffic to it. Because BGP trusts announcements and longest-prefix match prefers specific routes, this can redirect or black-hole traffic. RPKI origin validation and filtering of customer announcements are the main defences.

Key takeaways

• Forwarding is the per-packet data plane; routing is the control plane that builds the tables.
• Longest-prefix match picks the most specific matching prefix; the default route /0 is the fallback.
• Static routes suit stub networks; dynamic protocols adapt to failures.
• Distance vector uses Bellman-Ford, D_x(y) = min_v c(x,v) + D_v(y); it suffers count-to-infinity, eased by split horizon, poison reverse and a hop limit of 16 in RIP.
• Link state floods LSAs so every router has the full map and runs Dijkstra; it converges faster and scales with OSPF areas.
• Inside an AS, IGPs (OSPF, IS-IS, RIP) optimise paths; between ASes, BGP applies policy.
• BGP is path vector over TCP 179; AS_PATH prevents loops; LOCAL_PREF and AS_PATH length drive selection.
• In traceroute, isolated * or slow middle hops are usually harmless; look at whether delay persists to the destination.

Next lesson

Continue with the transport layer: TCP and UDP.