Binary search on prefix lengths for IP address lookup

摘要

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.