Fast IP Lookups Using Binomial Spanning Trees

Abstract

High performance Internet routers require an efficient IP lookup algorithm to forward millions of packets per second. Various data structures based on binary trie are normally used in software-based IP router design, including network processor-based routers. Binary trie based lookup algorithms have not only simple and easy IP address search process but also the routing entry update process. In this paper, we propose a new IP lookup algorithm based on binomial spanning tree. The proposed algorithm has the same advantages of simple search and update processes as the binary trie-based algorithms. However, the performance of the proposed algorithm is better than the schemes based on binary tries, such as pathcompression and level-compression.