A Simple and Scalable Algorithm for the IP Address Lookup Problem

Issue title: Computing Patterns in Strings

Article type: Research Article

Authors: Lee, Inbok | Park, Kunsoo | Choi, Yanghee | Chung, Sung Kwon

Affiliations: School of Computer Science and Engineering, Seoul National University, Seoul 151-742, Korea | Ubiquix Co. Ltd, Seoul 135-010, Korea

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.

Keywords:

Journal: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 181-190, 2003