Why this matters
Every device on the internet sends data in small packets. Each packet has a destination address. A router, which is a device that passes packets on toward their destination, looks at that address and decides which way to send the packet next.
A router keeps a routing table. This is a list of rules. Each rule says: "if the destination starts with these digits, send the packet to this next hop." The next hop is the neighbouring device the packet goes to next. A router may have many rules that match the same address. For example, a rule for all of 10.x.x.x and a rule for only 10.1.2.x both match 10.1.2.7. The router must pick the more specific rule, the one with more fixed digits. This choice is called the longest prefix match.
The simplest method checks every rule for every packet. That works for a few rules. When a table has many rules and a router must handle many packets each second, checking every rule for every packet is too slow. This lesson shows a method that checks at most 33 steps, no matter how many rules the table has. It uses a binary trie, a tree that stores addresses one bit at a time. Lesson 04 of this module used bits in a trie too, for the XOR problem. This lesson uses bits to match prefixes.
Terms used in this lesson
A bit is a single digit, either 0 or 1. A binary number is written only with bits. The number 5 is 101 in binary.
An IPv4 address is a 32-bit number. People write it as four parts from 0 to 255 separated by dots, such as 10.1.2.7. Each part is 8 bits, so the whole address has 32 bits.
A prefix is the first few bits of an address that a rule fixes. In the notation 10.1.2.0/24, the number after the slash is the prefix length. It says that the first 24 bits are fixed, and the last 8 bits can be anything. This notation is called CIDR, which stands for Classless Inter-Domain Routing. You only need to know the slash form.
A route is one rule in the table. It has a prefix and a next hop. In this lesson the next hops are plain names such as gw-A.
A binary trie is a tree where each node has two possible children, one for bit 0 and one for bit 1. A path from the root spells a sequence of bits. A node at depth d has read d bits.
A node is one box in the tree. In this lesson a node stores a route's next hop if a route ends there, or None if none does.
Depth is how far a node is from the root. The root has depth 0. A node at depth 24 has read 24 bits.
The default route, written 0.0.0.0/0, has prefix length 0. It matches every address, so it is the rule of last resort.
Four bit operators are used in the code. << shifts bits left, and | joins the bits of two numbers. >> shifts all bits to the right, so the bit at a chosen position moves to the last place. & with 1 keeps only the last bit.
Addresses are 32 bits
Each part of an address is one byte, 8 bits. Here is 10.1.2.7 with each part written as 8 bits:
10 = 00001010
1 = 00000001
2 = 00000010
7 = 00000111Put together, the address has 32 bits: 00001010 00000001 00000010 00000111. A trie reads these bits from left to right. The first bit decides whether to go to child 0 or child 1 of the root. The second bit decides at the next level, and so on.
The code turns the dotted text into one integer. Each part is shifted into place:
def parse_address(text):
value = 0
for part in text.split("."):
value = (value << 8) | int(part)
return valueTo read bit number depth from the left, the code shifts the value right by 31 - depth and keeps the last bit:
bit = (addr >> (31 - depth)) & 1For depth 0 the shift is 31, which moves the leftmost bit to the last place. For depth 31 the shift is 0, which leaves the rightmost bit in place.
Worked example 1: a small routing table
Here is a table with four routes:
prefix bits that are fixed next hop
0.0.0.0/0 none, matches everything gw-A
10.0.0.0/8 00001010 gw-B
10.1.0.0/16 00001010 00000001 gw-C
10.1.2.0/24 00001010 00000001 00000010 gw-DEach route's bits form a path from the root. The default route stores its next hop at the root itself. The route for 10.0.0.0/8 stores its next hop at the node reached after 8 bits. The route for 10.1.0.0/16 stores its next hop after 16 bits, and so on. The route for 10.1.2.0/24 sits on the same path as the other 10.x routes, but 24 steps down.
Here is the path for 10.1.2.0/24. Each bit is one step down the tree, and the marked node holds gw-D.
root (gw-A)
-> 0 0 0 0 1 0 1 0 (node for 10, holds gw-B)
-> 0 0 0 0 0 0 0 1 (node for 10.1, holds gw-C)
-> 0 0 0 0 0 0 1 0 (node for 10.1.2, holds gw-D)Now look up the address 10.1.9.9. Its bits in the first three parts are:
10 = 00001010
1 = 00000001
9 = 00001001The walk goes like this:
- At the root, the default route gw-A is a match, so remember gw-A.
- Follow the 8 bits of 10. The node after 8 bits holds gw-B, so remember gw-B.
- Follow the next 8 bits, of 1. The node after 16 bits holds gw-C, so remember gw-C.
- Follow the bits of 9 in the third part. The trie has the bits 00000010 at this level, but the address has 00001001. The first four bits match, 0000. At the fifth bit the address has 1 and the trie branch has 0, so the trie does not go that way. The walk has no node for this address, so it stops.
The answer is gw-C, the last route remembered. The rule for 10.1.2.0/24 was never reached, because 10.1.9.9 does not start with 10.1.2.
The lookup keeps the last route seen, not the first. A route found early is a shorter prefix. A route found deeper in the walk is a longer prefix, and a longer prefix is more specific.
Two shorter walks show the same rule.
For 10.9.9.9, the walk starts at the root and remembers gw-A. It follows the 8 bits of 10 to the node that holds gw-B, and remembers gw-B. The second part of the address is 9, which is 00001001 in binary. The trie below the 10 node has the bits 00000001 for the 10.1 branch. The first four bits, 0000, match. The fifth bit of the address is 1, but the trie branch has 0 at that point, so the walk goes to a child that does not exist in that direction. The walk stops after 12 bits. The answer is gw-B.
For 192.0.2.1, the first bit of 192 is 1. Every route in the table starts with the bit 0, because 10 is 00001010. The root has no child for bit 1, so the walk stops at depth 1. The root held the default route, so the answer is gw-A.
Adding a route
To add a route, follow its prefix bits from the root. Create any missing node on the way. At the node reached after the last prefix bit, store the next hop.
def add_route(self, cidr, next_hop):
address, length = cidr.split("/")
network = parse_address(address)
prefix_length = int(length)
node = self.root
for depth in range(prefix_length):
bit = (network >> (31 - depth)) & 1
if node.child[bit] is None:
node.child[bit] = Node()
node = node.child[bit]
node.next_hop = next_hopThe bits after the prefix length are ignored. The route 10.1.2.7/24 stores the same node as 10.1.2.0/24, because only the first 24 bits matter. The loop stops at prefix_length, so the rest of the address is never read.
The lookup
The lookup walks as far as the bits allow. At each node it checks whether a route ends there. If one does, it remembers that next hop, then moves on to the child for the next bit. When there is no child, the walk ends. The answer is the last remembered next hop.
def lookup(self, addr):
node = self.root
best = None
depth = 0
while node is not None:
if node.next_hop is not None:
best = node.next_hop
if depth == 32:
break
bit = (addr >> (31 - depth)) & 1
node = node.child[bit]
depth += 1
return bestThe loop can visit at most 33 nodes: the root at depth 0, and one node for each depth up to 32. A route with prefix length 32 stores its next hop at depth 32, so the check depth == 32 must come after the match check and before the bit read.
The full program
The program below has the node class, the parser, the route insert, the lookup and a small main part. Save it as ip_route_trie.py.
Save the file and run it with python3 ip_route_trie.py. The output below was produced with Python 3.14.4:
10.1.2.7 -> gw-D
10.1.9.9 -> gw-C
10.9.9.9 -> gw-B
192.0.2.1 -> gw-AEach answer matches the table. 10.1.2.7 matches all four routes and the longest is gw-D. 192.0.2.1 matches only the default route.
Worked example 2: a route that splits a block
Add one more route to the table: 10.1.2.128/25. A prefix of 25 bits fixes the first three parts and the first bit of the fourth part. The first bit of the fourth part is 1 for every address from 128 to 255. So this route covers 10.1.2.128 through 10.1.2.255.
table = IpRouteTrie()
table.add_route("0.0.0.0/0", "gw-A")
table.add_route("10.0.0.0/8", "gw-B")
table.add_route("10.1.0.0/16", "gw-C")
table.add_route("10.1.2.0/24", "gw-D")
table.add_route("10.1.2.128/25", "gw-E")Now look up four addresses with table.lookup(parse_address(...)). The output is:
10.1.2.127 -> gw-D
10.1.2.128 -> gw-E
10.1.2.200 -> gw-E
10.1.2.7 -> gw-DThe address 10.1.2.127 has a fourth part of 127, which is 01111111 in binary. Its first bit is 0, so the walk does not follow the new branch, and gw-D is the answer. The address 10.1.2.200 has a fourth part of 200, which is 11001000 in binary. Its first bit is 1, so the walk follows the new branch and finds gw-E at depth 25. The address 10.1.2.7 has 00000111 in the fourth part, so it does not match the new route either.
This example shows how routes of different lengths share the tree. The /25 route is a child of the /24 route's node. Addresses that follow the new branch reach the /25 node and get gw-E. Addresses that do not follow it keep the /24 answer.
Worked example 3: large addresses in Python
Java's int type is signed, so it holds numbers only up to 2,147,483,647 and it wraps around past that. An address whose first part is 128 or more has its top bit set, and in a Java int that makes the value negative. The bit reading code still works there, but comparing two addresses with < gives the wrong order.
Python does not have that limit. Its integers grow as large as needed, so the value of an address is always the positive number it stands for. Here is 192.168.1.20 in the program above:
192.168.1.20 -> 3232235796In Python, parse_address("192.0.2.1") > parse_address("10.1.2.7") gives True, because 192.0.2.1 is the larger address. The address still has 32 bits, and the trie still reads only 32 bits. A longer value, such as one with five parts, would not be rejected by the parser, so check the input before you parse it.
Common mistakes
Returning the first match
A common error is to return as soon as any route matches. Then the default route at the root always wins. I made a copy of the program that returns on the first match and ran the same four lookups. The output was:
10.1.2.7 -> gw-A
10.1.9.9 -> gw-A
10.9.9.9 -> gw-A
192.0.2.1 -> gw-AThe correct answers are gw-D, gw-C, gw-B and gw-A. Remember the last match, and keep walking until there is no child.
Forgetting to create the child nodes
add_route must create a node when a child is missing. I made a copy of the program where the missing child was set to None instead of a new Node. Python then fails when the loop reads the next child:
AttributeError: 'NoneType' object has no attribute 'child'The message names the type, NoneType, and the attribute that could not be read. The fix is the line node.child[bit] = Node(), which gives the missing child a node of its own.
Reading more bits than the prefix length
add_route stops at prefix_length. If the loop ran to 32 for every route, the route would be stored at the end of a 32-bit path taken from the route's own address. I made that copy and added the route 10.1.2.0/24 to an empty table. The lookup for 10.1.2.7 returned None, and so did 10.1.2.9. Only the exact address 10.1.2.0 would match such a route, and a /24 route would stop matching the other 255 addresses in its block. Keep the loop bound equal to the prefix length.
Practice
Exercise 1
Using the first four routes in worked example 1, find the next hop for 10.1.2.200. List every route that matches it.
Show the answer: Four routes match: the default route gw-A, the 10.0.0.0/8 route gw-B, the 10.1.0.0/16 route gw-C and the 10.1.2.0/24 route gw-D. The address starts with 10.1.2, so all three 10.x routes match. The longest is /24, so the answer is gw-D. Adding the /25 route from worked example 2 would change this answer to gw-E.
Exercise 2
Add the route 10.1.2.128/25 with next hop gw-E to the table. Which addresses now go to gw-E that went to gw-D before?
Show the answer: The addresses 10.1.2.128 through 10.1.2.255 now go to gw-E. Before the change, every address from 10.1.2.0 through 10.1.2.255 went to gw-D. The run in worked example 2 confirms the change for 10.1.2.128 and 10.1.2.200, and shows that 10.1.2.127 and 10.1.2.7 still go to gw-D.
Exercise 3
A lookup can walk down to depth 32 and stop. Why is the lookup time not affected by the number of routes in the table?
Show the answer: The loop reads one bit per depth, and it stops at depth 32 at the latest. So it visits at most 33 nodes. Adding more routes adds nodes to the trie, but it does not make a single lookup walk further than 32 bits. The time depends on the address length, not on the table size.
Exercise 4
Write a method remove_route(self, cidr) that stops a route from matching, without deleting any nodes. Explain why deleting nodes is not needed for correct answers.
Show the answer: Walk to the node for the prefix without creating any nodes, and set its next_hop to None:
def remove_route(self, cidr):
address, length = cidr.split("/")
network = parse_address(address)
prefix_length = int(length)
node = self.root
depth = 0
while depth < prefix_length and node is not None:
node = node.child[(network >> (31 - depth)) & 1]
depth += 1
if node is not None:
node.next_hop = NoneThe nodes stay in place, but a node with None as its next hop does not produce a match, so lookups skip it. Deleting empty nodes would save memory, but the answers would be the same. A removal that leaves nodes behind only costs some memory.
Exercise 5
Why does lookup keep walking after it finds a match? Give an address and a table where stopping at the first match gives the wrong answer.
Show the answer: A longer prefix that also matches may be deeper in the tree. Stopping early would return a shorter, less specific route. Using the table from worked example 1, the address 10.1.2.7 matches gw-A at the root, gw-B at depth 8, gw-C at depth 16 and gw-D at depth 24. Stopping at the root gives gw-A, which is the wrong answer. The correct answer is gw-D.
Summary
- A router picks the most specific route, the one with the longest prefix, that matches a destination address.
- An IPv4 address is 32 bits, and a binary trie reads one bit per level from the root.
- Each route's next hop is stored at the node reached after its prefix length bits.
- A lookup walks down the trie and remembers the last next hop it passed, so it finds the longest match.
- A lookup visits at most 33 nodes, so its time does not depend on how many routes the table has.
- Python integers hold any size, so an address with a first part of 128 or more is a positive number and comparisons work.