A Simple and Scalable Algorithm for the IP Address Lookup Problem

• Autorzy: Lee I. , Park K. , Choi Y. , Chung S.K.
• Języki publikacji: EN

Abstrakty

EN

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(logn) time. It also handles the insertion and deletion of IP prefixes efficiently without rebuilding the whole data structure.

Słowa kluczowe

EN

algorithm; dynamic segment tree; IP address

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 56, nr 1,2
• Strony: 181--190
• Opis fizyczny: bibliogr. 24 poz.

Twórcy

autor

Lee I.

autor

Park K.

autor

Choi Y.

autor

Chung S.K.

• School of Computer Science and Engineering, Seoul National University, Seoul 151-742, Korea,

Bibliografia

• [1] Andersson, A.: General Balanced Trees, Journal of Algorithms, 30, 1999, 1 - 18.
• [2] Bentley, J. L., Wood, D.: An optimal worst case algorithm for reporting intersections of rectangles, IEEE Transactions on Computers, 29(7), July 1980, 571-577.
• [3] Cormen, T. H., Leiserson, C. E., Rivest, R. L.: Introduction to Algorithms, MIT Press, 1990.
• [4] Crescenzi, P., Dardini, L., Grossi, R.: IP Address Lookup Made Fast and Simple, Proceedings of European Symposium on Algorithms (ESA ’99), 1999.
• [5] Deering, S. E., Hinden, R. M.: Internet Protocol, Version 6 (IPv6), RFC 1883, 1996.
• [6] Degermark, M., Brodnik, A., Carlsson, S., Pink, S.: Small Forwarding Tables for Fast Routing Lookups, Proceedings of ACM SIGCOMM ’97, 1997.
• [7] Donnelly, A., Deegan, T.: IP Route Lookups as String Matching, Proceedings of the 25th Annual IEEE Conference on Local Computer Networks (LCN ’00), 2000.
• [8] Fuller, V., Li, T., Yu, J., Varadhan, K.: Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy, RFC1519, 1993.
• [9] Galperin, I., Rivest, R. L.: Scapegoat trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms (SODA ’93), ACM Press, 1993.
• [10] Kreveld, M. J. V., Overmars, M. H.: Union-copy structures and dynamic segment trees, Journal of the ACM, 40(3), 1993, 635-652.
• [11] Labovitz, C., Malan, G. R., Jahanian, F.: Internet routing instability, Proceedings of the ACM SIGCOMM ’97, ACM Press, 1997.
• [12] Lampson, B., Srinivasan, V., Varghese, G.: IP lookups using multiway and multicolumn search, IEEE/ACM Transactions on Networking, 7(3), 1999, 324-334.
• [13] Lee, I., Park, K., Choi, Y., Chung, S. K.: IP address lookup using segment tree (in Korean), Journal of Korean Information Science Society, 28(11-12), 2001, 613-619.
• [14] Lee, I., Park, K., Choi, Y., Chung, S. K.: A Simple and Scalable Algorithm for the IP address lookup problem, Proceedings of the Thirteenth Australasian Workshop on Combinatorial Algorithms (AWOCA’02), 2002.
• [15] McAuley, A. J., Francis, P.: Fast Routing Table Lookup Using CAMs, Proceedings of IEEE INFOCOM, 1993.
• [16] Mehlhorn, K.: Data Structures and Efficient Algorithms Vol. III : Multi-dimensional Searching and Computational Geometry, Springer-Verlag, 1984.
• [17] Merit Network: Internet performance measurement and analysis project (IPMA), http://www.merit.edu/ipma
• 18] Nilsson, S., Karlsson, G.: Fast Address Look-Up for Internet Routers, Proceedings of IEEE Broadband Communications, 1998.
• [19] Pei, T.-B., Zukowski, C.: Putting Routing Tables in Silicon, IEEE Network Magazine, January 1992, 42-49.
• [20] Preparata, F. P., Shamos, M. I.: Computational Geometry - An Introduction, Springer-Verlag, 1995.
• [21] Sedgewick, R.: Algorithms in C++, Addison-Wesley, 1992.
• [22] Srinivasan, V., Varghese, G.: Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems (TOCS), 17(1), 1999, 1-40, ISSN 0734-2071.
• [23] Suri, S., Varghese, G., Warkhede, P. R.: Multiway range trees: scalable IP lookup with fast updates, Proceedings of GLOBECOM ’01, 2001.
• [24] Waldvogel, M., Varghese, G., Turner, J., Plattner, B.: Scalable High Speed IP Routing Lookups, Proceedings of ACM SIGCOMM ’97, September 1997