Understanding Routing Table Lookup Algorithm: Network Algorithm

Introduction and Core Concepts

The routing table lookup algorithm is one of the most fundamental networking algorithms powering the modern Internet. Every time a packet traverses the network, each router along the path must decide where to forward that packet next. This decision is made by consulting a routing table — a database that maps destination network prefixes to outgoing interfaces or next-hop addresses — and selecting the most specific matching entry. The algorithm that performs this selection is known as the Longest Prefix Match (LPM) algorithm.

Unlike a simple exact-match lookup in a hash table, routing table lookup is an approximate matching problem. IP addresses are hierarchical, and routing tables contain entries of varying prefix lengths. For example, a table might contain entries for 10.0.0.0/8, 10.1.0.0/16, and 10.1.1.0/24 simultaneously. When a packet destined for 10.1.1.5 arrives, all three entries match, but the algorithm must choose 10.1.1.0/24 because it is the longest and therefore most specific prefix. This longest prefix semantics is what makes the problem algorithmically interesting and challenging at scale.

Why does this matter? The performance of the lookup algorithm directly determines router throughput, latency, and scalability. A core Internet router today may hold over 900,000 IPv4 prefixes and more than 180,000 IPv6 prefixes, and it must perform lookups at line rates of 100 Gbps to 800 Gbps, which translates to hundreds of millions of packets per second. A naive linear scan is completely infeasible at this scale. Even a few extra memory accesses per lookup can become a bottleneck. Understanding how this algorithm works, its complexity trade-offs, and its optimized variants is therefore essential for network engineers, systems programmers, and anyone preparing for networking or systems design interviews.

Key Terminology

Before diving deeper, it is important to define the core terms. A prefix is a network address combined with a mask length, written in CIDR notation such as 192.168.1.0/24. The /24 indicates that the first 24 bits are the network portion. The routing table or Forwarding Information Base (FIB) is the data structure derived from the Routing Information Base (RIB) that is optimized for fast lookup. The next hop is the IP address or interface identifier to which the packet should be forwarded. Finally, Longest Prefix Match is the rule that the matching entry with the greatest prefix length wins.

Conceptually, the routing table can be viewed as a set of intervals in the IP address space. A /8 prefix covers 16 million addresses, while a /24 covers only 256. The lookup problem is thus a stabbing query: given a point (the destination IP), find the smallest interval that contains it. This geometric interpretation helps explain why trie-based data structures, which recursively partition the address space by bits, are the natural solution.

How It Works

At its core, the routing table lookup algorithm solves the Longest Prefix Match problem. The naive approach would compare the destination address against every prefix in the table and keep track of the longest match. While correct, this requires O(N) comparisons per packet, where N is the number of prefixes, and each comparison involves bit masking. This is far too slow for high-speed routers.

The dominant approach used in both software and hardware is based on the trie (pronounced "try"), a tree-like data structure where each edge represents a bit (0 or 1) and each node corresponds to a prefix. For IPv4, a binary trie has a maximum depth of 32, and for IPv6, 128. To insert a prefix like 192.168.1.0/24, the algorithm traverses the trie following the bits of the prefix for 24 levels, creating nodes as needed, and marks the final node as a valid prefix with its associated next-hop information. Lookup then becomes a simple walk: starting from the root, follow bits of the destination IP one by one, remembering the last node encountered that was marked as a valid prefix. When the walk cannot continue or reaches a leaf, the last remembered prefix is the longest match.

This trie traversal elegantly handles the longest prefix semantics without any backtracking. Because the search proceeds from the shortest to the longest prefix along the path, the deepest marked node on the path is automatically the longest match. The algorithm also naturally supports default routes (0.0.0.0/0), which are simply stored at the root node and serve as the match of last resort.

From Binary Trie to Optimized Structures

A pure binary trie, while conceptually simple, is memory-inefficient and requires up to 32 memory accesses per IPv4 lookup. Real implementations therefore use several optimizations. Path compression collapses chains of nodes with a single child, forming a Patricia trie or compressed trie, which dramatically reduces memory and depth. Multibit tries expand multiple bits at once by using a stride. For example, a stride of 4 means each node has up to 16 children and the depth is reduced to 8 for IPv4. This trades memory for speed, as fewer levels need to be traversed.

Another major optimization is the Level-Compressed Trie (LC-Trie) and variations like Tree Bitmap. These structures combine multibit expansion with bitmap compression to achieve both high lookup speed and compact memory representation. In hardware, routers often use Ternary Content-Addressable Memory (TCAM), which can perform a longest prefix match in a single clock cycle by searching all entries in parallel. However, TCAM is expensive, power-hungry, and limited in capacity, so algorithmic trie-based solutions remain critical for software routers, virtual switches, and cost-effective hardware.

Updates are also a key part of the mechanism. Routing protocols like BGP and OSPF constantly add and withdraw prefixes. The data structure must support incremental insertion and deletion without rebuilding the entire trie. In a binary trie, an update affects only the nodes along the path of the prefix, making it O(W) where W is the prefix length (32 or 128), which is very efficient.

Implementation

Implementing a routing table lookup algorithm in software requires careful attention to bit manipulation, memory layout, and longest prefix semantics. Below are four progressively optimized Python implementations that illustrate the core ideas. Note that production routers are typically implemented in C, C++, or P4 with cache-aware structures, but Python is excellent for understanding the logic.

1. Naive Linear Search (Baseline)

This baseline implementation stores prefixes in a list and scans them all for each lookup. It is easy to understand but scales poorly, serving as a performance reference point.

import ipaddress

class NaiveRoutingTable:
    def __init__(self):
        # Each entry is (network_int, mask_len, mask_int, next_hop)
        self.entries = []

    def add_route(self, prefix, next_hop):
        # prefix example: "10.1.0.0/16"
        net = ipaddress.IPv4Network(prefix)
        mask_int = int(net.netmask)
        net_int = int(net.network_address)
        mask_len = net.prefixlen
        self.entries.append((net_int, mask_len, mask_int, next_hop))

    def lookup(self, ip_str):
        ip_int = int(ipaddress.IPv4Address(ip_str))
        best_hop = None
        best_len = -1
        # Linear scan: check every entry
        for net_int, mask_len, mask_int, next_hop in self.entries:
            if (ip_int & mask_int) == net_int:
                # Longer mask_len means more specific prefix
                if mask_len > best_len:
                    best_len = mask_len
                    best_hop = next_hop
        return best_hop

# Example usage
table = NaiveRoutingTable()
table.add_route("0.0.0.0/0", "default")
table.add_route("10.0.0.0/8", "eth0")
table.add_route("10.1.0.0/16", "eth1")
print(table.lookup("10.1.1.5"))  # Expected: eth1

2. Binary Trie for Longest Prefix Match

This is the canonical data structure. Each node has two children (0 and 1) and an optional next-hop value. Lookup walks the trie and remembers the last valid next hop.

class TrieNode:
    def __init__(self):
        self.next_hop = None  # None means not a valid prefix end
        self.children = [None, None]  # children[0] for bit 0, children[1] for bit 1

class BinaryTrie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, prefix, next_hop):
        net = ipaddress.IPv4Network(prefix)
        ip_int = int(net.network_address)
        length = net.prefixlen
        node = self.root
        # Handle default route /0 which stays at root
        if length == 0:
            node.next_hop = next_hop
            return
        for i in range(length):
            # Extract i-th bit from the most significant side
            bit = (ip_int >> (31 - i)) & 1
            if node.children[bit] is None:
                node.children[bit] = TrieNode()
            node = node.children[bit]
        node.next_hop = next_hop

    def lookup(self, ip_str):
        ip_int = int(ipaddress.IPv4Address(ip_str))
        node = self.root
        best_hop = node.next_hop  # default route if present
        for i in range(32):
            if node is None:
                break
            if node.next_hop is not None:
                best_hop = node.next_hop
            bit = (ip_int >> (31 - i)) & 1
            node = node.children[bit]
        # Check final node as well
        if node is not None and node.next_hop is not None:
            best_hop = node.next_hop
        return best_hop

3. Multibit Trie with Stride Optimization

A multibit trie reduces depth by consuming k bits per level. With stride=4, depth drops from 32 to 8. This is a classic time-memory trade-off used in high-performance software routers like DPDK and Click.

class MultiBitTrieNode:
    def __init__(self):
        self.next_hop = None
        self.children = {}  # key: k-bit chunk -> node

class MultiBitTrie:
    def __init__(self, stride=4):
        self.root = MultiBitTrieNode()
        self.stride = stride
        assert 32 % stride == 0, "Stride must divide 32"

    def insert(self, prefix, next_hop):
        net = ipaddress.IPv4Network(prefix)
        ip_int = int(net.network_address)
        length = net.prefixlen
        node = self.root
        # Number of full stride chunks to traverse
        chunks = length // self.stride
        remainder = length % self.stride

        for c in range(chunks):
            shift = 32 - (c + 1) * self.stride
            chunk = (ip_int >> shift) & ((1 << self.stride) - 1)
            if chunk not in node.children:
                node.children[chunk] = MultiBitTrieNode()
            node = node.children[chunk]

        # Handle remainder bits by expanding into multiple entries
        if remainder > 0:
            shift = 32 - (chunks + 1) * self.stride
            # The prefix covers a range of chunks at the next level
            base_chunk = (ip_int >> shift) & ((1 << self.stride) - 1)
            # Mask for the valid bits within the chunk
            # Example: /22 with stride 8, remainder 6, covers 4 chunks
            num_covered = 1 << (self.stride - remainder)
            for i in range(num_covered):
                chunk = base_chunk + i
                if chunk not in node.children:
                    node.children[chunk] = MultiBitTrieNode()
                # For simplicity, store next_hop at expanded leaf
                # Real implementation uses controlled prefix expansion
                node.children[chunk].next_hop = next_hop
        else:
            node.next_hop = next_hop

    def lookup(self, ip_str):
        ip_int = int(ipaddress.IPv4Address(ip_str))
        node = self.root
        best_hop = node.next_hop
        for c in range(32 // self.stride):
            if node.next_hop is not None:
                best_hop = node.next_hop
            shift = 32 - (c + 1) * self.stride
            chunk = (ip_int >> shift) & ((1 << self.stride) - 1)
            if chunk not in node.children:
                break
            node = node.children[chunk]
        if node is not None and node.next_hop is not None:
            best_hop = node.next_hop
        return best_hop

4. Patricia Trie (Compressed Binary Trie)

Path compression removes nodes that have only one child and no next-hop, storing a skip value. This implementation shows the core lookup logic for a compressed trie, which is widely used for its memory efficiency.

class PatriciaNode:
    def __init__(self, bit_index=0):
        self.bit_index = bit_index  # Position of bit to branch on
        self.next_hop = None
        self.children = [None, None]
        self.prefix = None  # Store full prefix for leaf validation

class PatriciaTrie:
    def __init__(self):
        self.root = PatriciaNode(bit_index=-1)

    def insert(self, prefix, next_hop):
        net = ipaddress.IPv4Network(prefix)
        ip_int = int(net.network_address)
        length = net.prefixlen
        node = self.root
        parent = None
        bit_pos = -1

        # Find insertion point based on bit_index ordering
        while node is not None and node.bit_index > bit_pos and node.bit_index < length:
            parent = node
            bit_pos = node.bit_index
            bit = (ip_int >> (31 - node.bit_index)) & 1
            node = node.children[bit]

        # Create new node for this prefix
        new_node = PatriciaNode(bit_index=length)
        new_node.next_hop = next_hop
        new_node.prefix = (ip_int, length)

        if node is None or length < node.bit_index:
            # Insert above current node
            bit = (ip_int >> (31 - length)) & 1 if length < 32 else 0
            new_node.children[bit] = new_node if node is None else node
            # This simplified logic illustrates the concept;
            # a full implementation handles prefix vs. branching nodes
            if parent is not None:
                p_bit = (ip_int >> (31 - parent.bit_index)) & 1
                parent.children[p_bit] = new_node
        else:
            # Insert as child
            bit = (ip_int >> (31 - node.bit_index)) & 1
            node.children[bit] = new_node

    def lookup(self, ip_str):
        ip_int = int(ipaddress.IPv4Address(ip_str))
        node = self.root
        best_hop = None
        # Walk following bit_index pointers, tracking best match
        visited = set()
        while node is not None and id(node) not in visited:
            visited.add(id(node))
            if node.next_hop is not None:
                # Verify that ip matches the node's prefix
                if node.prefix is not None:
                    p_ip, p_len = node.prefix
                    mask = ((0xFFFFFFFF << (32 - p_len)) & 0xFFFFFFFF) if p_len > 0 else 0
                    if (ip_int & mask) == (p_ip & mask):
                        best_hop = node.next_hop
                else:
                    best_hop = node.next_hop
            if node.bit_index >= 31:
                break
            # Move to next child based on next bit_index
            # Find child with smallest bit_index > current
            next_bit = node.bit_index + 1
            # Simplified traversal for illustration
            bit = (ip_int >> (31 - next_bit)) & 1 if next_bit < 32 else 0
            if node.children[bit] is None or node.children[bit] == node:
                break
            node = node.children[bit]
        return best_hop

Step-by-Step Example

Let us walk through a concrete example to solidify the algorithm. Consider a small routing table with four entries, which is typical for an edge router connecting a corporate network to an ISP:

• 0.0.0.0/0 → Default gateway (next hop: 203.0.113.1)
• 192.168.0.0/16 → Internal network (next hop: 10.0.0.1, interface eth0)
• 192.168.1.0/24 → Engineering subnet (next hop: 10.0.0.2, interface eth1)
• 192.168.1.128/25 → Engineering servers (next hop: 10.0.0.3, interface eth2)

Now suppose a packet arrives with destination IP 192.168.1.200. The router must perform a lookup. In dotted binary, this address is 11000000.10101000.00000001.11001000. The prefixes in binary are: /16 is 11000000.10101000.xxxxxxxx.xxxxxxxx, /24 is 11000000.10101000.00000001.xxxxxxxx, and /25 is 11000000.10101000.00000001.1xxxxxxx. The address 192.168.1.200 has the last octet 11001000, which starts with 1, so it falls within the /25.

Using a binary trie, the lookup proceeds as follows. Start at the root, which holds the default route 0.0.0.0/0, so best_hop is initially 203.0.113.1. Traverse bit by bit: the first 16 bits 11000000.10101000 lead to a node marked with 192.168.0.0/16, so best_hop updates to 10.0.0.1. Continue traversing bits 17-24 (00000001), reaching the node for 192.168.1.0/24, updating best_hop to 10.0.0.2. Continue to bit 25, which is 1, reaching the node for 192.168.1.128/25, updating best_hop to 10.0.0.3. Bits 26-32 are 1001000, but after the /25 node there may be no further marked nodes. The walk ends and returns 10.0.0.3 via eth2, which is indeed the longest match.

If the destination had been 192.168.1.10 (last octet 00001010, starting with 0), the walk would have diverged at bit 25 to the 0-branch, where no /25 node exists. The last remembered valid prefix would remain 192.168.1.0/24, so the packet would be forwarded to 10.0.0.2. If the destination had been 8.8.8.8, the walk would fail very early, never finding the 192.168.x.x branches, and would return the default route. This example demonstrates how the algorithm naturally prefers specificity without needing to compare all entries.

Visualizing the Trie Path

Imagine the trie as a binary tree where left edges are 0 and right edges are 1. The path for 192.168.1.200 is a sequence of rights and lefts determined by its bits. Marked nodes along this path act as checkpoints. The algorithm does not need to explore other branches; it only follows the single path defined by the destination IP. This single-path property is what makes trie lookup O(W) rather than O(N), where W is the address length. Even if the table had a million prefixes, the lookup for this address would still only traverse at most 32 nodes.

Complexity Analysis

Complexity analysis is crucial for understanding whether a routing lookup algorithm can meet line-rate requirements. The key metrics are lookup time, update time, and memory consumption. Lookup time determines packet forwarding rate, update time affects convergence after routing changes, and memory determines how many prefixes can be stored in fast memory like SRAM or CPU cache.

For the naive linear search, lookup is O(N * W) in the worst case, where N is the number of prefixes and W is the cost of a prefix comparison. With N = 900,000, this is catastrophic. Binary trie lookup is O(W) = O(32) for IPv4 and O(128) for IPv6, independent of N, which is a massive improvement. However, 32 memory accesses per packet is still expensive when each access may miss the CPU cache. Multibit tries reduce this to O(W/k) where k is the stride, for example 8 accesses with stride 4, but at the cost of increased memory due to prefix expansion.

Space complexity also varies dramatically. A binary trie in the worst case uses O(N * W) nodes, but path compression reduces this to O(N). A multibit trie with stride k can use O(N * 2^k) in the worst case due to expansion, though techniques like Tree Bitmap keep it near O(N). TCAM provides O(1) lookup time but O(N) space with very high cost per bit and power consumption. Understanding these trade-offs is essential for selecting the right structure for a given deployment.

For software routers on general-purpose CPUs, the bottleneck is often not instruction count but memory latency. A binary trie lookup that incurs 32 random memory accesses will be cache-unfriendly. Modern optimizations therefore focus on cache efficiency: compressing nodes to fit in cache lines, using level compression to reduce depth, and employing techniques like DXR (Direct eXecution Routing) that use range tables. In practice, a well-tuned Tree Bitmap can achieve < 5 memory accesses per IPv4 lookup on average, enabling 100+ million lookups per second per core.

Variations and Optimizations

The basic binary trie is only the starting point. Decades of research have produced a rich family of optimized variants, each targeting a different trade-off between speed, memory, and update cost.

Path-Compressed Tries (Patricia): These eliminate single-child chains. If a node has only one child and is not a valid prefix, it is removed and its parent points directly to its child, storing the skipped bits. This can reduce node count by 50-70% for real BGP tables, which are sparse.

Multibit and Fixed-Stride Tries: By expanding k bits at a time, depth is reduced by a factor of k. A common configuration for IPv4 is strides of 16-8-8 (first level 16 bits, next two levels 8 bits each), which matches the historical classful boundaries and keeps the root table at 64K entries. Variable-stride tries optimize the stride per level based on prefix distribution to minimize memory.

Tree Bitmap: This is the state-of-the-art for software. It represents a multibit node's children with two bitmaps: an internal bitmap indicating which nodes in the expanded subtree are valid prefixes, and an external bitmap indicating which children exist. Child pointers are stored contiguously, allowing a single memory access to fetch the bitmaps and compute the child index via population count (popcount). This is extremely cache-efficient.

Level-Compressed Trie (LC-Trie): LC-Trie dynamically replaces dense subtrees with a single multibit node. If a subtree is fully populated at a certain depth, it is collapsed, reducing depth adaptively. This is particularly effective for routing tables with many contiguous prefixes.

DXR and SAIL: More recent algorithms like DXR (Direct eXecution Routing) split the lookup into a direct lookup table for the first 16-20 bits (covering most prefixes) and a sorted range table for the remainder, using binary search. This achieves very fast lookups with excellent cache behavior and is used in high-performance virtual switches.

On the hardware side, TCAM remains dominant for core routers, but algorithmic TCAM alternatives like Tuple Space Search and HiCuts/HyperCuts use decision trees to achieve TCAM-like performance with SRAM. Updates are another optimization dimension: incremental update algorithms ensure that a BGP flap affecting one prefix does not require rebuilding the entire structure, which is critical for stability.

Real-World Applications

Routing table lookup is not confined to core Internet routers; it appears in many layers of modern infrastructure, often under different names but solving the same longest prefix match problem.

Core and Edge Routers: This is the classic application. Tier-1 ISP routers from vendors like Cisco, Juniper, and Arista use a combination of TCAM and algorithmic tries to forward packets at terabit rates. Edge routers in enterprises and data centers use software implementations in operating systems like Linux (FIB trie), FreeBSD, and in NOS like SONiC.

Software-Defined Networking (SDN) and Virtual Switches: In cloud data centers, virtual switches such as Open vSwitch (OVS), VPP, and DPDK-based switches perform millions of LPM lookups per second to implement overlay networks, tenant isolation, and service chaining. The performance of the LPM algorithm directly impacts VM-to-VM latency and throughput.

Firewalls and Access Control Lists (ACLs): Packet filtering rules are often expressed as prefixes (e.g., block 192.168.1.0/24). Matching a packet against a large ACL is a generalization of LPM to multi-dimensional classification, but the underlying trie and decision-tree techniques are the same.

Load Balancers and CDNs: Global load balancers use prefix matching to map client IPs to the nearest data center (geolocation by prefix). CDNs use it to select the optimal edge cache. Even DNS-based routing can involve LPM for subnet-aware responses.

Operating System Kernels: Every Linux, Windows, or macOS machine has a routing table. When you run `ip route show`, you see the FIB. The kernel's `fib_trie` or `fib6_trie` is consulted for every outgoing packet to decide which interface to use, including for VPNs and containers.

Beyond networking, the same algorithm appears in surprising places: IP geolocation databases, telephone number routing (longest prefix of digits), and even URL routing in web frameworks where routes like /api/v1/* and /api/v1/users/* require longest prefix semantics.

Comparison with Alternatives

While tries are the standard for LPM, several alternative approaches exist, each with distinct strengths. Choosing the right one depends on whether the workload is lookup-heavy, update-heavy, or memory-constrained.

Linear Search is simple and has zero preprocessing, but is only viable for tiny tables (< 50 prefixes) such as on an end host. Hash-based schemes use hash tables per prefix length and probe from longest to shortest length (e.g., check /32, then /31, etc.). With perfect hashing, average lookup can be O(1), but worst-case is O(W) hash probes and prefix expansion can explode memory. Binary Search on Prefix Length (e.g., Waldvogel's binary search on trie levels) performs binary search over prefix lengths using hash tables, achieving O(log W) probes, but requires careful handling of markers to ensure correctness.

TCAM offers deterministic O(1) hardware lookup but is costly, power-intensive, and suffers from limited capacity and complex update semantics (entries must be kept sorted by prefix length). Decision-tree algorithms like HiCuts partition the address space geometrically and are excellent for multi-field classification (ACLs) but are more complex to build for pure LPM.

In practice, most high-performance systems use a hybrid: a direct array for the first 16 bits (covering ~90% of lookups that hit a /16 or shorter), plus a trie or hash for the remaining bits. This combines the O(1) speed of an array with the scalability of a trie.

For interview and system design contexts, the key takeaway is: never propose linear search for a router, understand that binary trie is the baseline, and be able to explain why multibit/Tree Bitmap is preferred for software and TCAM for hardware. Mentioning the trade-off between lookup speed and update cost will demonstrate depth.

Common Mistakes and Best Practices

Implementing routing table lookup correctly is trickier than it appears. Several common pitfalls can lead to incorrect forwarding, poor performance, or security vulnerabilities.

Mistake 1: Forgetting Longest Prefix Semantics. A frequent error is returning the first match instead of the longest. For example, matching 10.0.0.0/8 and immediately returning without checking for a more specific 10.1.0.0/16. The correct pattern is to track the best match while traversing and only return after the walk completes. Always test with overlapping prefixes.

Mistake 2: Incorrect Bit Ordering and Masking. IP addresses are in network byte order (big-endian), with the most significant bit first. Extracting bits from the wrong end or using an incorrect mask (e.g., shifting by 32 which is undefined in some languages) leads to subtle bugs. Use a well-tested library like Python's `ipaddress` for parsing and explicitly test edge cases like /0, /31, /32, and 0.0.0.0.

Mistake 3: Ignoring Default Route and Missing Match Handling. If no prefix matches, the packet should be dropped or sent to a default route, not cause a null pointer exception. Ensure the root node can hold a default next hop and that lookup returns a clear "no route" signal when appropriate. In production, a missing route should increment a counter and trigger an ICMP unreachable message.

Mistake 4: Inefficient Memory Layout. Naively allocating a Python object per trie node will be extremely slow and memory-heavy. In performance-critical code, use arrays of structs, pool allocators, or libraries like `pytricia` that store nodes in contiguous memory. Avoid recursion for lookup; use iterative loops to avoid stack overflow on deep tries (especially for IPv6).

Best Practices: First, always validate and normalize prefixes on insertion — reject invalid lengths and ensure the host bits are zeroed (e.g., 192.168.1.5/24 should be stored as 192.168.1.0/24). Second, implement incremental updates correctly: when deleting a prefix, do not delete nodes that are still needed by other prefixes; only prune nodes that have no children and no next hop. Third, benchmark with real BGP table dumps (available from RouteViews) rather than synthetic random prefixes, as real tables have distinct distributions. Fourth, consider concurrency: lookups happen on the data plane at high frequency while updates happen on the control plane. Use RCU (Read-Copy-Update) or double-buffering to allow lock-free lookups during updates. Finally, add comprehensive tests for overlapping prefixes, duplicate inserts, and deletion of non-existent prefixes.

Security Considerations

A poorly implemented lookup can be exploited. An attacker could advertise many specific prefixes to cause memory exhaustion (route bloat) or craft packets that trigger worst-case lookup paths. Implement prefix limits, validate prefix lengths, and ensure lookup time is independent of attacker-controlled input to avoid algorithmic complexity attacks.

Interview Questions

Routing table lookup is a favorite topic in networking and systems interviews. Here are common questions and how to approach them:

Q1: How would you implement Longest Prefix Match for a router with 1 million prefixes? What data structure would you use and why?

Answer Approach: Start by rejecting linear search due to O(N) lookup. Propose a binary trie as the baseline with O(W) lookup, then optimize to a multibit trie or Tree Bitmap for better cache performance and fewer memory accesses. Mention path compression for memory savings. If hardware is allowed, mention TCAM for O(1) but note cost/power trade-offs. Discuss update cost O(W) and memory O(N). Bonus points for mentioning DXR or variable stride optimization and IPv6 considerations (128-bit depth).

Q2: What is the time complexity of lookup in a binary trie for IPv4 and IPv6? How does a multibit trie with stride k improve it?

Answer Approach: Binary trie is O(W) where W=32 for IPv4 and 128 for IPv6, requiring up to W memory accesses. A multibit trie with stride k reduces this to O(W/k) accesses. For example, stride 4 gives 8 accesses for IPv4. Explain the trade-off: larger k reduces depth but increases node fanout (2^k children) and memory due to prefix expansion, so k=4 or 8 is typical. Mention Tree Bitmap as a way to keep memory O(N) while retaining O(W/k) speed.

Q3: Walk through the lookup for IP 10.1.2.3 in a table containing 10.0.0.0/8, 10.1.0.0/16, and 10.1.2.0/24.

Answer Approach: Describe the trie walk bit by bit, tracking the best match. Start at root (no match), after 8 bits match 10.0.0.0/8, after 16 bits match 10.1.0.0/16 (more specific, update best), after 24 bits match 10.1.2.0/24 (longest, final answer). Emphasize that all three match but the longest wins, and that the algorithm follows a single path defined by the destination IP bits.

Q4: How do you handle insertion and deletion of prefixes without rebuilding the whole trie? What are the complexities?

Answer Approach: Insertion traverses the trie creating nodes as needed for the prefix length, O(W) time. Deletion traverses to the node, clears its next_hop, and then prunes nodes bottom-up if they have no children and no next hop, also O(W). Mention that updates must be incremental and concurrent with lookups, so use RCU or copy-on-write to avoid locking the data plane. Discuss the need to handle overlapping prefixes correctly — deleting 10.1.0.0/16 should not delete nodes needed for 10.1.2.0/24.

Q5: Compare TCAM vs. algorithmic trie solutions for routing lookup. When would you choose one over the other?

Answer Approach: TCAM gives deterministic O(1) single-cycle lookup via parallel search but is expensive, power-hungry (~100x SRAM), limited capacity (~500K entries), and has slow, complex updates requiring sorted order. Algorithmic tries (Tree Bitmap, LC-Trie) use cheap SRAM/DRAM, scale to millions of prefixes, have fast incremental updates, but require multiple memory accesses (5-10) and are cache-sensitive. Choose TCAM for core routers needing guaranteed line rate at 400G+ and deterministic latency; choose algorithmic tries for software routers, virtual switches, edge routers, and cost-sensitive designs where flexibility and scale matter more than single-cycle guarantee.

Preparing for these questions with both conceptual understanding and the ability to sketch code (like the binary trie above) will demonstrate strong systems and networking fundamentals.