Kurose and Ross, Computer Networking: A Top-Down Approach, section 4.2.1 (destination-based forwarding) and section 4.3 (IPv4 addressing and route aggregation), cross-checked against RFC 4632 (Classless Inter-domain Routing). Every match and aggregate on this page was recomputed with Python’s ipaddress module.
Write the destination in binary first, then line each table entry’s prefix up under it. Never guess from the dotted-decimal: prefixes rarely end on a byte boundary, and that is exactly where the traps are.
The picture: sorting the mail#
Picture a mail sorter with two signs on the wall. One says: “Anything for Canada goes in bin 1.” The other says: “Anything for Toronto goes in bin 2.”
A letter for Toronto fits both signs. Toronto is in Canada, after all. The sorter puts it in bin 2, because that sign is more specific. Someone wrote it for exactly this case. A letter for Ottawa only fits the first sign, so it goes in bin 1.
A router does the same thing with addresses. When more than one entry in its forwarding table fits a destination, it uses the most specific one: the entry with the longest prefix.
Vocabulary, before anything uses it#
| Term | What it means |
|---|---|
| Prefix | The leftmost bits of an address that a table entry cares about, written a.b.c.d/x. The x is how many bits. |
| Forwarding table | The router’s list of entries: “destinations starting with this prefix go out of that link”. |
| Match | An entry matches a destination when the destination’s first x bits equal the entry’s x prefix bits. |
| Longest prefix matching | When several entries match, use the one with the largest x. Also called longest prefix match. |
| Default route | The entry 0.0.0.0/0. Its prefix has zero bits, so it matches everything, and it is used only when nothing longer matches. |
| Advertise | For a network to tell other networks, through a routing protocol, “send traffic for this prefix to me”. |
| Route aggregation | Advertising one short prefix that covers many longer ones. Also called route summarization or supernetting. |
| More specific route | A longer prefix that sits inside a shorter one, such as a /23 inside a /20. |
| ISP | Internet service provider: a network that sells Internet connectivity to customers. |
A forwarding table is a list of prefixes#
A router has to choose an output link for every datagram, in nanoseconds. One table line per destination address would mean 232, about 4.3 billion lines. Instead, each line covers a whole range of addresses that share a prefix. Here is the table we will use, for a router with five output links:
| Entry | Covers | Prefix bits | Link |
|---|---|---|---|
| 145.64.0.0/16 | 145.64.0.0 to 145.64.255.255 | 10010001 01000000 | 0 |
| 145.64.96.0/19 | 145.64.96.0 to 145.64.127.255 | 10010001 01000000 011 | 1 |
| 145.64.100.0/22 | 145.64.100.0 to 145.64.103.255 | 10010001 01000000 011001 | 2 |
| 145.64.101.128/25 | 145.64.101.128 to 145.64.101.255 | 10010001 01000000 01100101 1 | 3 |
| 0.0.0.0/0 (default) | everything | (none) | 4 |
Notice that the ranges nest. The /25 sits inside the /22, which sits inside the /19, which sits inside the /16. That nesting is why a destination can match several entries at once.
Real routers do this lookup in special hardware. A common choice is a TCAM, ternary content-addressable memory, which compares the destination against every entry at once and returns the answer in essentially constant time, whatever the table size.
Matching, step by step in binary#
The method is the same every time:
- Write the destination address in binary.
- For each entry, compare its x prefix bits with the destination’s first x bits. Equal means it matches.
- Of the entries that match, pick the one with the largest x.
Destination 145.64.101.200 = 10010001 01000000 01100101 11001000.
/16: first 16 bits 10010001 01000000: equal. Match.
/19: the next 3 bits are 011, and the entry wants 011. Match.
/22: the first 6 bits of the third byte are 011001, and the entry wants 011001. Match.
/25: all of the third byte, 01100101, plus the first bit of the fourth, 1. The entry wants 01100101 1. Match.
The default matches too, as it always does. Longest match: /25, so the datagram leaves on link 3.
Destination 145.64.101.20 = 10010001 01000000 01100101 00010100.
The /16, /19 and /22 match exactly as before. But the fourth byte starts with 0, and the /25 wants a 1. No match. Longest match: /22, so link 2.
These two addresses differ only in the last byte, yet they leave on different links. That is why you must work in binary.
| Destination | Entries that match | Longest | Link |
|---|---|---|---|
| 145.64.120.5 | /0, /16, /19 | /19 | 1 |
| 145.64.200.1 | /0, /16 | /16 | 0 |
| 145.65.0.1 | /0 only | /0 | 4 |
The third one is a near miss: 145.65 differs from 145.64 in the last bit of the second byte (01000001 against 01000000), so even the /16 fails.
Why the longest match wins#
A longer prefix covers fewer addresses, so it carries more exact information. It is usually there on purpose, as an exception carved out of a bigger range. In our table, someone added 145.64.101.128/25 precisely because those 128 addresses should not follow the /22 to link 2.
The effect is that each link really receives its own range minus every longer range inside it. A brute-force count over all 65,536 addresses in 145.64.0.0/16 gives:
| Link | Entry | Addresses in the entry | Addresses that actually go there |
|---|---|---|---|
| 3 | /25 | 128 | 128 |
| 2 | /22 | 1,024 | 1,024 − 128 = 896 |
| 1 | /19 | 8,192 | 8,192 − 1,024 = 7,168 |
| 0 | /16 | 65,536 | 65,536 − 8,192 = 57,344 |
Route aggregation: one advertisement for many networks#
Longest prefix matching inside one router has a big payoff across the Internet. Because addresses are handed out in a hierarchy (registry to ISP to customer), an ISP’s customers all sit inside the ISP’s own block. So the ISP can tell the world about one short prefix instead of every customer.
ISP Alpha holds 84.112.32.0/20 (84.112.32.0 to 84.112.47.255, 4,096 addresses). It has given eight customers one /23 each: 84.112.32.0/23, 84.112.34.0/23, 84.112.36.0/23, and so on up to 84.112.46.0/23.
In binary the third bytes are 00100000, 00100010, ... , 00101110. All eight share the first four bits 0010 of the third byte. With the 16 bits of the first two bytes, that is 20 shared bits: the /20.
So Alpha advertises one route, 84.112.32.0/20, instead of eight. Every other network’s table needs one line for Alpha, not eight.
Blocks can only be merged into one advertisement when three things are true:
- The blocks must be contiguous: no gaps between them.
- Together they must form one aligned block: a power-of-two size, starting on a multiple of that size.
- The blocks must all be reached through the same next hop.
So 84.112.32.0/23 and 84.112.34.0/23 merge into 84.112.32.0/22. But 84.112.34.0/23 and 84.112.36.0/23 do not merge, even though they touch. A /22 must start at a multiple of 4 in the third byte (32, 36, 40, ...), and 34 is not one. The pair straddles two /22 blocks.
When a customer moves to another ISP#
Suppose the customer with 84.112.40.0/23 leaves Alpha for a second ISP, Beta, and keeps its addresses. Renumbering every machine would be painful, so it does not.
Alpha keeps advertising 84.112.32.0/20, because it still serves the other seven customers. Beta now advertises 84.112.40.0/23. Other routers end up with both entries: the /20 pointing toward Alpha and the /23 pointing toward Beta.
| Destination | Matches | Longest | Goes to |
|---|---|---|---|
| 84.112.41.77 | /20 (Alpha) and /23 (Beta) | /23 | Beta |
| 84.112.39.5 | /20 (Alpha) only | /20 | Alpha |
| 84.112.47.200 | /20 (Alpha) only | /20 | Alpha |
No one had to change Alpha’s advertisement. The more specific /23 quietly wins for the customer that moved, and everything else still follows the /20. This is the same rule as the Toronto letter, at Internet scale.
A router forwards each datagram on the table entry whose prefix matches the most leading bits of the destination address, and because the most specific route always wins, networks can advertise one aggregated prefix for all their customers while a customer that moves away is still reached through its own longer prefix.
Practice#
Convert each destination to binary before you look at the table. Write the byte where the prefix ends in full.
- Using the five-link table in this guide, which link does each destination leave on? (a) 145.64.103.7 (b) 145.64.99.255 (c) 145.64.128.0
- A router has these entries: 192.0.2.0/24 → A, 192.0.2.64/26 → B, 192.0.2.96/27 → C, 0.0.0.0/0 → D. Where does each destination go? (a) 192.0.2.100 (b) 192.0.2.70 (c) 192.0.2.200 (d) 192.0.3.1
- In the table of question 2, how many of the 256 addresses in 192.0.2.0/24 actually go to B?
- In the five-link table, the entry 145.64.100.0/22 is deleted. Which link does 145.64.101.20 use now?
- Can 57.20.8.0/24, 57.20.9.0/24, 57.20.10.0/24 and 57.20.11.0/24 be advertised as one prefix? If so, which?
- Can 57.20.9.0/24, 57.20.10.0/24, 57.20.11.0/24 and 57.20.12.0/24 be advertised as one prefix without also claiming addresses outside them?
- The customer with 84.112.44.0/23 moves from ISP Alpha to ISP Beta. What does each ISP advertise for it, and where do datagrams for 84.112.45.9 and 84.112.47.200 go?
Solutions#
Find the first line where your working split from the solution, and redo the problem from that line. Do not just read the answer and nod.
- (a) Link 2. (b) Link 1. (c) Link 0. (a) Third byte 103 =
01100111: starts011001, so the /22 matches, and 103 is not 101, so the /25 does not. (b) 99 =01100011: starts011(the /19) but not011001. (c) 128 =10000000: does not start011, so only the /16 matches. - (a) C. (b) B. (c) A. (d) D. (a) 100 =
01100100matches /24, /26 (01) and /27 (011); longest is C. (b) 70 =01000110starts01but not011: B. (c) 200 =11001000matches only the /24: A. (d) 192.0.3.1 differs in the third byte, so only the default matches: D. - 32. B’s /26 covers 64 addresses (.64 to .127), but C’s /27 takes .96 to .127, which is 32 of them. 64 − 32 = 32 addresses, .64 to .95, go to B.
- Link 1. With the /22 gone, the matching entries are /0, /16 and /19. The /25 still does not match, because the fourth byte, 20 =
00010100, starts with 0. - Yes: 57.20.8.0/22. The third bytes 8 to 11 are
000010|00to000010|11: they share the first 6 bits, and the four blocks fill exactly one aligned block of 4, starting at 8, a multiple of 4. - No. 9 to 12 is not aligned. The smallest single prefix covering all four is 57.20.8.0/21, which is 2,048 addresses against the 1,024 owned. Without over-claiming, the best is three entries: 57.20.9.0/24, 57.20.10.0/23 and 57.20.12.0/24.
- Alpha keeps advertising 84.112.32.0/20; Beta advertises 84.112.44.0/23. 84.112.45.9 goes to Beta; 84.112.47.200 goes to Alpha. The /23 needs the third byte to start
0010110. 45 =00101101does, and /23 is longer than /20: Beta. 47 =00101111starts0010111, so only the /20 matches: Alpha.
Test-readiness checklist#
- ☐ I can explain why a forwarding table holds prefixes rather than single addresses.
- ☐ I can test whether an entry matches a destination by comparing bits in binary.
- ☐ I can pick the longest matching prefix from a table, including the default route.
- ☐ I can work out how many addresses each link really receives when entries nest.
- ☐ I can decide whether a set of blocks can be aggregated, and name the aggregate.
- ☐ I can explain what happens when a customer keeps its addresses and moves to another ISP.
Always find the byte where the prefix ends and write that one byte in full binary. Every other byte is either all network or all host, so the whole question is decided in that single byte.
Frequently asked questions#
What is longest prefix matching?
It is the rule a router uses when several forwarding table entries match a destination address. It uses the entry with the longest prefix, the one that matches the most leading bits, because that entry is the most specific.
Does the order of entries in a forwarding table matter?
No. Longest prefix matching looks at every entry that matches and picks the longest one, wherever it appears. This is different from rule lists that stop at the first match.
What is the default route?
The entry 0.0.0.0/0. Its prefix length is zero, so it matches every address, but it is the shortest possible match, so it is used only when no other entry fits.
What is route aggregation?
Route aggregation, also called route summarization or supernetting, is advertising one shorter prefix that covers many longer ones. An ISP whose customers all sit inside its block can advertise the block once instead of every customer separately.
What happens if a customer moves to a different ISP but keeps its addresses?
The new ISP advertises the customer's own longer prefix, and the old ISP keeps advertising its aggregate. Routers see both, and longest prefix matching sends the customer's traffic to the new ISP while everything else in the aggregate still goes to the old one.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written.
Test yourself on this topic
The free networking practice app has 10 questions on this guide and 500 across the whole course, each with an explanation for every answer. Offline, no ads, no account.
Practise this topic →