Efficient hardware architecture for fast IP address lookup

Abstract

A multi-gigabit internet protocol (IP) router may receive several million packets per second from each input link. For each packet, the router needs to find the longest matching prefix in the forwarding table in order to determine the packet's next-hop. An efficient hardware solution for the IP address lookup problem is presented. The problem is modelled as a searching problem on a binary-trie. The binary-trie is partitioned into fixed size non-overlapping subtrees. Each subtree is represented using a bit-vector and can be searched in parallel for the best matching prefix in a few nanoseconds. The address lookup is implemented using a hardware pipeline with a throughput of one lookup per memory access. A distinguishing feature of the design is that forwarding table entries are not replicated in the data structure. Hence, table updates can be done in constant time with only a few memory accesses. The approach can be extended to IPv6. By applying path compression, the amount of memory required is upper bounded by O(N) where N is the number of prefixes in the routing table.