Efficient hardware architecture for fast IP address lookup

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

24 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)43-52
Journal / PublicationIEE Proceedings: Computers and Digital Techniques
Volume150
Issue number1
Publication statusPublished - Jan 2003

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.