Loading learning content...
Every time you visit a website, send an email, or stream a video, your data packets traverse the internet through a series of routers. Each router faces a critical question: "Where should I send this packet next?"
The answer lies in IP routing—and at its heart is a longest prefix matching (LPM) problem. Routers maintain routing tables with thousands to millions of entries, and they must make forwarding decisions in nanoseconds. The data structure powering this? A specialized form of the trie.
This is one of the most impactful real-world applications of prefix-based data structures. Understanding IP routing gives you insight into:
By the end of this page, you will understand: (1) How IP addresses and prefixes work, (2) Why routers need longest prefix matching, (3) How tries solve the routing lookup problem, (4) Specialized trie variants for IP routing, and (5) Performance requirements and optimizations.
Before diving into routing algorithms, let's understand the data we're working with.
IPv4 Addresses:
An IPv4 address is a 32-bit number, typically written as four decimal octets: 192.168.1.100
192 . 168 . 1 . 100
│ │ │ │
11000000 10101000 00000001 01100100
│ │ │ │
└──────────┴──────────┴──────────┴──────────► 32 bits total
IP Prefixes (CIDR Notation):
Routing doesn't work with individual addresses—it works with prefixes. A prefix represents a range of addresses sharing the same leading bits.
192.168.0.0/16 means:
192.168 (fixed)192.168.0.0 to 192.168.255.255CIDR Notation Examples:━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 10.0.0.0/8 (Class A)├── Prefix length: 8 bits├── Fixed bits: 00001010├── Variable bits: 24 bits└── Covers: 10.0.0.0 – 10.255.255.255 (16M addresses) 192.168.1.0/24 (Typical home/office network)├── Prefix length: 24 bits ├── Fixed bits: 11000000.10101000.00000001├── Variable bits: 8 bits└── Covers: 192.168.1.0 – 192.168.1.255 (256 addresses) 0.0.0.0/0 (Default route - matches everything)├── Prefix length: 0 bits├── Fixed bits: none└── Covers: All addresses (4.3 billion) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Binary Representation: Address: 192.168.1.100Binary: 11000000.10101000.00000001.01100100 Does it match 192.168.0.0/16? 11000000.10101000.????????.???????? └──────────────┬─────────────────┘ First 16 bits match? Address[0:16] = 11000000.10101000 ✓ Prefix[0:16] = 11000000.10101000 ✓ YES - Address matches prefix!The internet would be unmanageable if routers needed an entry for every individual IP address (~4 billion for IPv4). Instead, routers use prefixes to aggregate routes. A single entry for '10.0.0.0/8' covers 16 million addresses!
When a packet arrives at a router, the router examines the destination IP address in the packet header and consults its routing table to determine the next hop (the next router to forward the packet to).
The Routing Table:
A routing table is a collection of entries, each containing:
192.168.1.0/24)The Challenge: Multiple Matches
An IP address often matches multiple prefixes in the routing table. The rule is: use the longest (most specific) matching prefix.
Routing Table:┌────────────────────┬──────────────┐│ Prefix │ Next Hop │├────────────────────┼──────────────┤│ 0.0.0.0/0 │ Default GW │ ← Matches everything│ 10.0.0.0/8 │ Router A │ ← Matches 10.x.x.x│ 10.1.0.0/16 │ Router B │ ← Matches 10.1.x.x │ 10.1.1.0/24 │ Router C │ ← Matches 10.1.1.x│ 10.1.1.128/25 │ Router D │ ← Matches 10.1.1.128-255└────────────────────┴──────────────┘ Query: Where should packet for 10.1.1.200 go? Matching prefixes:✓ 0.0.0.0/0 (length 0) → Default GW✓ 10.0.0.0/8 (length 8) → Router A✓ 10.1.0.0/16 (length 16) → Router B✓ 10.1.1.0/24 (length 24) → Router C✓ 10.1.1.128/25 (length 25) → Router D ← LONGEST MATCH! Answer: Router D (most specific match wins) ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Why longest prefix? 10.1.1.200 in binary:00001010.00000001.00000001.11001000 10.1.1.128/25 matches first 25 bits:00001010.00000001.00000001.1_______ The 25th bit is '1', which matches 10.1.1.200 (≥128).10.1.1.100 would NOT match (25th bit='0', falls in 10.1.1.0/25 range).Why Longest Prefix Match?
Longest prefix matching enables hierarchical routing:
0.0.0.0/0 sends to the internet gateway10.0.0.0/8 routes to your ISP's network10.1.0.0/16 routes to your company10.1.1.0/24 routes to your department10.1.1.128/25 routes to a specific subnetMore specific prefixes (longer) override less specific ones. This allows fine-grained control at any level without changing higher-level routes.
Core internet routers process millions of packets per second. Each lookup must complete in ~100 nanoseconds. A simple linear scan through a routing table with 800,000+ entries is completely infeasible!
The trie is a natural fit for longest prefix matching. An IP address is a 32-bit string; a trie over these bits enables efficient prefix lookup.
Binary Trie for IP Routing:
Each node has at most 2 children (for bits 0 and 1). The path from root to a node represents a prefix. Nodes are marked with routing information if they correspond to a prefix in the routing table.
Routing entries:• 10.0.0.0/8 → Router A (binary: 00001010/8)• 10.1.0.0/16 → Router B (binary: 00001010.00000001/16)• 10.1.1.0/24 → Router C (binary: 00001010.00000001.00000001/24) Binary Trie (showing first 24 bits of 10.1.1.0/24 path): (root) / \ 0 1 / 0 / 0 / 0 / 1 ← bit 4 = 1 / 0 ← bit 5 = 0 / 1 ← bit 6 = 1 / 0 ← bit 7 = 0 / \ │ (Router A) ← prefix /8 ends here 0 \ 0 ...continuing to bit 16 (Router B) and bit 24 (Router C) Lookup algorithm:1. Start at root2. For each bit in the destination IP: - Follow the corresponding child (0 or 1) - If current node has routing info, remember it3. Return the last routing info found (longest prefix)12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
class TrieNode: """Binary trie node for IP routing.""" __slots__ = ['children', 'next_hop'] def __init__(self): self.children = [None, None] # [0-child, 1-child] self.next_hop = None # Routing info if this is a prefix endpoint class IPRoutingTable: """ Trie-based IP routing table. This is a conceptual implementation for understanding. Real routers use more sophisticated hardware-optimized structures. """ def __init__(self): self.root = TrieNode() def ip_to_bits(self, ip_str: str) -> list[int]: """Convert IP string to list of 32 bits.""" octets = ip_str.split('.') bits = [] for octet in octets: val = int(octet) for i in range(7, -1, -1): bits.append((val >> i) & 1) return bits def add_route(self, prefix: str, prefix_len: int, next_hop: str) -> None: """ Add a routing entry. Args: prefix: IP prefix (e.g., "192.168.1.0") prefix_len: Prefix length in bits (e.g., 24 for /24) next_hop: Where to forward matching packets """ bits = self.ip_to_bits(prefix) node = self.root # Traverse/build trie for prefix_len bits for i in range(prefix_len): bit = bits[i] if node.children[bit] is None: node.children[bit] = TrieNode() node = node.children[bit] # Mark this node with routing info node.next_hop = next_hop def lookup(self, ip: str) -> str | None: """ Find the next hop for an IP address using longest prefix match. Time: O(W) where W = address width (32 for IPv4, 128 for IPv6) """ bits = self.ip_to_bits(ip) node = self.root best_match = None # Traverse trie, remembering the longest matching prefix for bit in bits: if node.next_hop is not None: best_match = node.next_hop if node.children[bit] is None: break node = node.children[bit] # Check final node if node.next_hop is not None: best_match = node.next_hop return best_match # Example usage:router = IPRoutingTable() # Build routing tablerouter.add_route("0.0.0.0", 0, "Default Gateway")router.add_route("10.0.0.0", 8, "Internal Network")router.add_route("10.1.0.0", 16, "Department A")router.add_route("10.1.1.0", 24, "Subnet 1")router.add_route("192.168.0.0", 16, "Branch Office") # Perform lookupsprint(router.lookup("10.1.1.50")) # "Subnet 1" (longest: /24)print(router.lookup("10.1.2.50")) # "Department A" (longest: /16)print(router.lookup("10.2.1.50")) # "Internal Network" (longest: /8)print(router.lookup("8.8.8.8")) # "Default Gateway" (longest: /0)print(router.lookup("192.168.1.1")) # "Branch Office" (longest: /16)The lookup algorithm maintains best_match throughout traversal. Every time we pass a node with routing info, we update it. If we can't continue (child doesn't exist), we return the last match found. This naturally implements longest prefix matching!
Let's analyze the basic binary trie approach:
| Operation | Time | Space | Notes |
|---|---|---|---|
| Insert route | O(W) | W = 32 (IPv4) or 128 (IPv6) | |
| Lookup | O(W) | 32 memory accesses max | |
| Delete route | O(W) | With cleanup of empty nodes | |
| Total space | O(N × W) | N = number of routes |
Comparison with Naive Approaches:
| Approach | Lookup Time | Space | Practical? |
|---|---|---|---|
| Linear scan | O(N) | O(N) | No (N = 800K+ entries) |
| Hash table | O(W) per length | O(N) | Tricky (need to check all prefix lengths) |
| Binary trie | O(W) | O(N × W) | Yes, but memory-intensive |
Why O(W) = O(32) is Acceptable:
For IPv4, W = 32 means at most 32 memory accesses per lookup. At 100ns per access, that's ~3μs—still too slow for line-rate forwarding (10 Gbps = ~15 million packets/second = 67ns per packet).
This is why specialized trie variants and hardware acceleration are needed.
At router scale, the limiting factor isn't CPU operations—it's memory latency. Each trie node access may require a cache miss (~100ns). Reducing tree depth directly improves performance.
Real routers use sophisticated trie variants to achieve required performance:
Multi-bit Trie (4-bit stride):━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Binary Trie (1 bit per level):Depth = 32 levels for IPv4Each node: 2 children vs 4-bit Stride Trie:Depth = 8 levels for IPv4 (32 ÷ 4)Each node: 16 children (2^4) Memory access reduction: 32 → 8 = 4x fewer memory accesses! Trade-off: Each node is larger (16 pointers vs 2) Patricia Trie (Path Compression):━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Before (simple binary trie for prefix 10.1.0.0/16): root → 0 → 0 → 0 → 0 → 1 → 0 → 1 → 0 → 0 → 0 → 0 → 0 → 0 → 0 → 1 → [end] (16 single-child nodes!) After (Patricia trie): root → [0000.1010.0000.0001] → [end] (Single node with "skip 16 bits, check value = 10.1") Massive space savings for sparse prefix sets!Build vs. Lookup Trade-offs:
Modern software routers (like Linux kernel routing) typically use Patricia/Radix tries. Hardware routers often combine multi-bit tries with TCAM for the most critical prefixes.
IPv6 addresses are 128 bits—4× larger than IPv4. This significantly impacts routing data structures.
IPv6 Address Example:2001:0db8:85a3:0000:0000:8a2e:0370:7334 Structure:┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐│ 2001 │ 0db8 │ 85a3 │ 0000 │ 0000 │ 8a2e │ 0370 │ 7334 │└────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘│ 16 bits per group × 8 groups = 128 bits total │ Typical prefix lengths:• /48 - Site allocation (common for organizations)• /64 - Subnet (standard LAN size)• /128 - Host route (single address) Impact on routing:• Binary trie depth: 128 levels (vs 32 for IPv4)• Multi-bit trie with 4-bit stride: 32 levels• Multi-bit trie with 8-bit stride: 16 levels Memory and time scale proportionally!Despite the larger address space, IPv6 routing tables are currently smaller than IPv4 (hundreds of thousands vs. millions of entries). This is due to better address allocation planning and less historical fragmentation. However, this may change as IPv6 adoption grows.
IP routing happens at two very different scales:
The Linux Kernel Approach:
Linux uses the LPC (Longest Prefix Cache) Trie, a variant of the Patricia trie with optimizations for the specific patterns found in routing tables:
This achieves millions of lookups per second on commodity hardware—sufficient for most edge/access scenarios.
IP routing exemplifies a broader pattern: hierarchical prefix matching. This pattern appears in many domains:
/api/users/123 to route handlers using longest prefix (/api/users/:id beats /api).Whenever you have hierarchical data where more specific rules override less specific ones, longest prefix matching via tries is likely the right approach. This pattern is fundamental to how we organize routing information at every layer of the networking stack.
We've explored how tries enable the fundamental operation of internet routing:
Congratulations! You've completed the Common Trie Patterns & Problem Types module. You now have a comprehensive pattern library for trie applications—from word search in grids to spell checking to internet routing. These patterns are fundamental tools in any engineer's algorithm toolkit.