Fast and scalable schemes for the IP address lookup problem

Routers forward a packet based on the packet destination address. To do this, they must find the longest matching prefix with the packet destination address in the IP lookup tables. Expanding the size of the global network increases the size of the lookup tables. Increasing the communication line speed reduces the processing and search time since the packets must be switched at wire speed. This implies the forwarding engines need more efficient IP lookup techniques. We believe the fundamental issue preventing applying the usual tree structures such as m_way trees to the IP lookup problem is the lack of a systematic method to compare and sort strings of different lengths when some of them are prefixes of others. Therefore, a simple scheme for comparing and sorting IP address prefixes is first introduced. Then, we manipulate the prefix data and tune the well known data structures in order to apply them to the IP lookup problem. We propose a binary prefix tree and devise procedures to sort the prefixes and build the index structure. It uses O(N) memory space and works well for the longest prefix matching problem. The binary search tree is extended to m_way trees in order to get better search performance in the next steps. Two versions of m_way trees are proposed, a static m_way prefix tree and a dynamic m_way prefix tree. The first one is more suitable for an environment with lower transaction and expected to give better memory usage and more compact tree structure. The later one, the dynamic m_way prefix tree, is built bottom up like B-tree and is more suitable for an environment with higher transactions. All data structures share a common property that no data prefix can be in a higher level than its prefix(es). We believe the proposed schemes are simple, well defined, easy to implement in hardware or software and scalable compared to the previously proposed methods while having efficient memory usage and search performance.