Longest-Prefix-Match Routing Lookup

1. Background Knowledge

CIDR (Classless Inter-Domain Routing) notation expresses an IP network as address/prefix_length. The prefix length indicates how many leading bits of the 32-bit IPv4 address are fixed; the remaining bits are the host portion. For example, 10.1.0.0/16 fixes the first 16 bits, meaning any address from 10.1.0.0 through 10.1.255.255 belongs to that network. The special route 0.0.0.0/0 matches every possible destination and serves as the default gateway.

Longest-prefix match is the fundamental routing lookup rule: when multiple routes match a destination, the router selects the one with the largest prefix length because it is the most specific. This mirrors how a trie (prefix tree) naturally stores routes—deeper nodes represent more specific prefixes. In practice, hardware uses TCAMs or compressed tries, but for software-level problems, a linear scan with bit-level comparison is sufficient.

To test whether a destination IP falls within a CIDR block, you compare the first prefix_length bits of both the network address and the destination. If they are identical, the destination is inside that network. This is equivalent to applying a bitmask: mask = (0xFFFFFFFF << (32 - prefix_length)) & 0xFFFFFFFF, then checking (dest_int & mask) == (network_int & mask).

2. Algorithm Approach

The problem is a linear scan with best-candidate selection. Iterate through every entry in the routing table, test whether the destination matches that CIDR, and track the matching entry with the greatest prefix length. Because ties on prefix length are resolved by table order (earliest wins), you only update your best candidate when the current prefix length is strictly greater than the stored one.

The core sub-problem is CIDR membership testing, which reduces to integer bit manipulation:

import ipaddress

def matches(cidr: str, dest: str) -> bool:
 net = ipaddress.ip_network(cidr, strict=False)
 return ipaddress.ip_address(dest) in net

Alternatively, for performance, parse both addresses to 32-bit integers once and use bitwise AND with a computed mask.

3. Step-by-Step Strategy

• Parse the destination IP into a 32-bit integer (or keep it as a string if using the ipaddress module).
• Initialize best_hop = "drop" and best_prefix = -1.
• Loop over each (cidr, next_hop) in table:
• Extract the prefix length from the CIDR string (split on /).
• Test whether dest falls within that CIDR using bitmask comparison or ipaddress membership.
• If it matches and the prefix length is strictly greater than best_prefix, update best_prefix and best_hop.
• Return best_hop after the loop.

A bitmask-based match check looks like:

def cidr_match(network_str: str, dest_int: int) -> int:
 """Return prefix length if dest is in network, else -1."""
 addr_part, prefix_str = network_str.split("/")
 prefix = int(prefix_str)
 net_int = int(ipaddress.IPv4Address(addr_part))
 mask = (0xFFFFFFFF << (32 - prefix)) & 0xFFFFFFFF
 if (dest_int & mask) == (net_int & mask):
 return prefix
 return -1

4. Common Pitfalls

• Off-by-one in mask construction: Shifting by 32 - prefix when prefix = 0 gives 0xFFFFFFFF << 32, which in Python produces a 64-bit value. Always mask with & 0xFFFFFFFF to stay in 32-bit space.
• Using >= instead of > for prefix comparison: The problem states that on a tie, the earliest entry wins. If you update on >=, a later duplicate-prefix entry would incorrectly overwrite the earlier one.
• Forgetting the default route: 0.0.0.0/0 has prefix length 0. It should match everything, but only if no more specific route exists. Ensure your initial best_prefix is -1 (or less than 0) so the default route can win when nothing else matches.
• Strict vs. non-strict network parsing: ipaddress.ip_network("10.1.2.3/16", strict=True) raises an error because 10.1.2.3 is not a valid network address for /16. Use strict=False or parse the address and prefix separately.
• Assuming IPv6: The problem specifies IPv4 (32-bit). Do not over-engineer for 128-bit addresses unless stated.

5. Time & Space Complexity

• Time: $O(n)$ where $n$ is the number of routes in the table. Each route requires $O(1)$ bit operations for the match test, and you scan all $n$ entries once.
• Space: $O(1)$ auxiliary space beyond the input. You store only two scalar variables (best_prefix, best_hop) regardless of table size.

This linear approach is optimal for a single lookup against an unsorted, unindexed table. In production routers with millions of routes, data structures like radix trees or compressed tries achieve $O(32) = O(1)$ lookups, but that is beyond the scope of this problem.