Four rows match, and only one of them gets the packet

01 The idea

Two jobs that share one table

Students use routing and forwarding as if they were the same word. They are two different jobs, running on two different clocks, and separating them is the first thing an interviewer checks.

Routing is building the table. A person types a route in, or a protocol talks to the routers next door and works one out. It happens when the network is configured and again when something changes, so its natural unit is seconds and minutes. It burns CPU on the router’s general-purpose processor and it happens whether or not a single packet is flowing. This half is called the control plane.

Forwarding is using the table. One packet arrives, the router reads its destination address, looks the address up, and pushes the packet out of one interface. That happens once per packet, so on a busy link it happens millions of times a second and the budget for each lookup is tens of nanoseconds in dedicated hardware. Nothing is negotiated and nothing is decided here; the decision was made earlier and this step is a lookup and nothing more. This half is called the data plane.

The table in the middle is what joins them, and it is a plain list. Each row says: for destinations that look like this, hand the packet to that neighbour, out of this interface. There is no path in a row, no map, and no idea of the far end. A row never stores the route to anywhere. It stores one hop, and the router trusts that the next router knows one more.

That leaves one question, and it is the question this whole lesson turns on. Rows overlap on purpose. A row for a whole company can sit beside a row for one department inside it and a row for one rack inside that department, and a destination can satisfy all three at once. So which row wins? Not the first one in the list, because the list has no meaningful order. Not the one with the best metric, because metrics from different protocols are not comparable. The winner is the row whose prefix is longest, meaning the row that constrains the most leading bits. That is longest prefix match, and RFC 1812 requires every IPv4 router to behave that way.

02 Worked example

One packet, four rows, one winner

This table is the scene for the rest of the lesson, including the console in section 04 and every number in the cheat sheet. Four rows on one router, deliberately not written in order of prefix length, because the order is going to turn out to be irrelevant and it is easier to believe that when you can see it.

A packet arrives on eth0 with destination 172.16.5.130. Read left to right, and watch which of the two jobs each box is doing.

The highlighted node is the one to slow down on, so here it is bit by bit. Write the destination out in binary first, once: 172.16.5.130 is 10101100.00010000.00000101.10000010. Now AND it with each row’s mask and compare with that row’s network.

Row 3 is the only one worth checking by hand, because it is the only one where the AND touches a partial octet. The last octet of the destination is 130 = 10000010. The last octet of the mask is 240 = 11110000. AND them bit by bit and every one of the low four bits is cleared: 10000010 AND 11110000 = 10000000, which is 128. So the result is 172.16.5.128, which is exactly row 3’s network, so the row matches.

Three things in that trace are worth naming, because each one is a question waiting to be asked. First, all four rows matched and the router still forwarded out one interface: matching is not winning. Second, the winner was found in row 3 of 4, and the router still examined row 4 — there is no early exit, because a longer prefix could always be sitting further down. Third, row 1 has metric 20 and row 3 has metric 1, and that had no bearing on anything. A metric only ever compares two paths to the same prefix learned from the same protocol. Comparing OSPF’s cost 20 with a static route’s 1 is comparing two numbers in unrelated units.

Finally, size that /28, because subnet arithmetic is where these questions usually turn. A /28 constrains 28 of the 32 bits, so 32 − 28 = 4 host bits are left, which is 2⁴ = 16 addresses: 172.16.5.128 through 172.16.5.143. Of those, the all-zeros host part 172.16.5.128 is the network address and the all-ones host part 172.16.5.143 is the broadcast address, and neither can be given to a machine. Usable hosts are 2⁴ − 2 = 14, from .129 to .142, and our destination .130 is one of them. That general form, 2^h − 2 for h host bits, is the single most common off-by-one in this subject, and the whole reason a /24 holds 254 usable hosts and not 256.

03 Mechanics

The five columns, and the two ways rows get written

Start with the row itself, column by column, because every rule below is a rule about one of these five fields. The right-hand column is the specific thing that gets marked wrong, not a general warning.

Longest prefix match, and the three things it is not. It is not first match: the router does not stop at the first row that matches, because a longer prefix may be anywhere in the table. It is not most specific by accident of ordering: sorting the table differently changes nothing, and a real router stores the table as a trie or in TCAM where there is no order to speak of. It is not the best metric: a /28 with a terrible metric still beats a /16 with a perfect one. The rule exists because CIDR (RFC 4632) lets an operator advertise one big aggregate and then punch specific exceptions out of it. Announce 172.16.0.0/16 once, and then add 172.16.5.128/28 when those sixteen addresses need to go somewhere else. The exception is written as a longer prefix, and longest prefix match is the rule that makes the exception mean what it looks like it means. Interviewers also like the order of the full decision: longest prefix first, then, only if two rows tie on prefix length and come from different protocols, administrative distance, and only then metric. Administrative distance is a Cisco-style trust ranking — connected 0, static 1, eBGP 20, OSPF 110, RIP 120, iBGP 200 — and it never gets consulted at all unless two prefixes are the same length.

So much for reading the table. The other half of the topic is who writes it, and there are exactly two answers.

Static routing is a person typing a row. On Cisco IOS that is one line, ip route 0.0.0.0 0.0.0.0 203.0.113.1; on Linux it is ip route add default via 203.0.113.1 dev eth0. There is no protocol, so no bandwidth is spent on updates, no CPU is spent on an algorithm, and nothing can be learned by an attacker listening to the wire. It is completely predictable, which for a small network is a virtue rather than a limitation. It is also completely blind. A static row is withdrawn only when the router’s own interface on that row goes down; a failure one hop further away is invisible to it, and the router will keep cheerfully forwarding into a hole. That trade is fine for a stub network, a site with exactly one way out, because when there is only one path there is nothing for a protocol to choose between.

Dynamic routing is a protocol filling the table by talking to other routers, and it splits into two families that differ in what one router is allowed to know.

Distance vector, and the loop it is famous for. Each router periodically hands its neighbours a list of every destination it knows and its distance to each. It never says how it gets there, so a receiving router learns “B can reach network N in 1 hop” and concludes “then I can reach N in 2 hops, via B”. That is Bellman-Ford, run in a distributed way, and it is sometimes called routing by rumour because a router believes a distance without ever seeing the path behind it. The failure follows directly. Take A − B − C with network N attached to C. B knows N at 1 hop via C; A knows N at 2 hops via B. Now C loses N. If B advertises N back towards C, C hears “B can reach N in 1”, believes it, and installs N at 2 hops via B — pointing straight back at the router that just told it. C then advertises 2, B raises its own to 3, A to 4, and the metric climbs one per round forever. That is count to infinity, and RIP stops it with a blunt instrument: infinity is defined as 16. A route at 16 hops is unreachable, so the counting terminates after a bounded number of rounds. The price is the well-known limit that RIP cannot span a network more than 15 hops wide.

The mitigations, and what each one actually fixes. Split horizon is the rule that a router never advertises a route back out of the interface it learned that route on, which stops the two-router loop above at the source. Route poisoning means that when a route dies you advertise it with metric 16 rather than silently dropping it, so neighbours are told it is dead instead of being left to time out. Poison reverse combines the two: advertise the route back to your neighbour, but with metric 16, which is louder than silence and harder to misread. Triggered updates send the bad news immediately instead of waiting for the next 30-second tick. Hold-down makes a router ignore new news about a route that just died, for long enough that the whole domain hears about the death first. None of these is a proof of correctness. Split horizon closes loops between two routers and does nothing about a loop that goes the long way round through three, which is precisely why link state exists.

Link state, and what the extra work buys. Every OSPF router (RFC 2328) describes only what it can see for itself — its own links, their costs, and who is on the other end — and floods that description to every other router in the area. Each router stores every description it receives, so once flooding settles, every router in the area holds a byte-identical link state database: the same graph of the same network. Then each router independently runs Dijkstra over that graph with itself as the root, and keeps the first hop of each shortest path as a routing table row. Convergence is fast because a change triggers a flood immediately rather than waiting for a timer, and correct because routers computing on identical data cannot disagree about the shortest path. The costs are real: memory for the database, CPU for every recomputation, and design work, because that database has to be kept small. OSPF does that with areas, all of which attach to the backbone area 0, so flooding is contained inside an area and only summaries cross the boundary. Two more numbers get asked. Neighbours exchange a hello every 10 seconds on an Ethernet segment and declare each other dead after 40 seconds of silence. And on a shared segment OSPF elects a designated router plus a backup, so n routers form adjacencies with the DR rather than with each other, turning n(n−1)/2 adjacencies into n. Cisco’s default cost is 10⁸ ÷ bandwidth in bps, so a 100 Mbps link costs 1 and a 10 Mbps link costs 10; the well-known trap is that a 1 Gbps link also costs 1, because the minimum cost is 1, unless someone raises the reference bandwidth.

Interior versus exterior, in one paragraph. Everything above optimises inside one administrative domain, one autonomous system: one company, one campus, one ISP, under one authority that can decide what “best” means. Protocols that work inside an AS are interior gateway protocols, and RIP, OSPF, EIGRP and IS-IS are all IGPs. Between autonomous systems the question changes completely. The Internet is roughly a hundred thousand autonomous systems belonging to competing companies, and there is no shared authority to define a metric, no willingness to publish an internal topology, and no scale at which flooding every link to everybody would work. So the systems are glued together by exactly one exterior gateway protocol, BGP (RFC 4271), which runs over TCP port 179 and advertises reachability as an AS path: a list of the autonomous systems a prefix has travelled through. BGP is a path vector protocol — distance vector that carries the path, so a router seeing its own AS number in the list can discard the announcement and loops are ruled out by inspection rather than by counting. And crucially BGP is policy driven, not shortest path. A network prefers the route it has a commercial reason to prefer, and a longer AS path through a partner routinely beats a shorter one through somebody who has to be paid. That is the sentence to have ready: IGPs answer “what is fastest”, BGP answers “what is allowed and what does it cost”.

And that is why the default route exists. Your laptop holds a handful of rows and one of them is 0.0.0.0/0. It matches every address with zero bits of constraint, so it matches everything and loses to everything else, which makes it the perfect “none of the above”. A host does not need a map of the Internet to reach it; it needs a direction and one neighbour who knows more than it does. The same argument scales upward. A branch office router keeps specific routes for the branch and a default towards head office. Head office keeps a default towards its ISP. Only in the core, in what operators call the default-free zone, does a router finally have to hold the full table, because there is nobody left to pass the question to. Everyone else is aiming, not navigating.

05 Cheat sheet

Twelve answers to have ready

Every row is something you can be asked to state or compute in under ten seconds. The right-hand column is the specific wrong answer that gets given, not a general caution.

06 Where & why

Every table in this lesson is one command away

None of this is a teaching abstraction. The table is live state you can print on the machine in front of you, and the rule you just learned decided a global outage in 2008.

07 Interview questions

What they ask, and where they push

This topic separates recital from understanding with one move: the interviewer adds a row to your table halfway through your answer and watches whether you re-run the rule or reach for the metric. Answer the rule first, then the mechanism.

08 Practice problems

Six to work out on paper

For every one of these: write the destination in binary first, then write each candidate mask under it, and only then start comparing. Keep prefix lengths in their own column, because half of these are decided before any other field is read.