Abstract
The IP address lookup problem is to find the longest matching IP prefix from a routing table for a given IP address and it has been a central bottleneck in speeding up the Internet. In this paper we propose a new algorithm for this problem based on the segment tree data structure. Given n IP prefixes, our algorithm does the IP address lookup in O(log n) time. It also handles the insertion and deletion of IP prefixes efficiently without rebuilding the whole data structure.
Get full access to this article
View all access options for this article.