Address lookup is an essential function in the Internet routers that should be performed in wire-speed. A lot of address lookup algorithms have been widely studied. Among them, we have thoroughly investigated the binary-search-based address lookup algorithms. Most of the existing binary search schemes perform binary search on prefix values, and hence the lookup speed is proportional to the length of prefixes or the log function of the number of prefixes. The previous algorithm based on binary search on prefix lengths has superior lookup performance than others. However, the algorithm requires very complicated pre-computation of markers and best matching prefixes for internal nodes. This complicated pre-computation makes the composition of the routing table and the incremental update difficult. In this letter, a new IP address lookup scheme based on binary search on prefix lengths is proposed. The performance evaluation results show that the proposed scheme has very good performance in the lookup speed and the scalability.
Bibliographical noteFunding Information:
Manuscript received December 23, 2005. The associated editor coordinating the review of this letter and approving it for publication was Prof. Christos Douligeris. This research was supported by the Ministry of Information and Communications, Korea, under a HNRC-ITRC support program supervised by IITA.
- Binary search
- Binary search on prefix length
- Binary trie
- IP address lookup
- Leaf pushing