A simple and scalable algorithm for the IP address lookup problem

被引：0
作者：
Lee, I
Park, K [1 ]
Choi, Y
Chung, SK
机构：
[1] Seoul Natl Univ, Sch Comp Sci & Engn, Seoul 151742, South Korea
[2] Ubiquix Co Ltd, Seoul 135010, South Korea
来源：
FUNDAMENTA INFORMATICAE | 2003年 / 56卷 / 1-2期
关键词：
D O I：
暂无
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
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.
引用
收藏
页码：181 / 190
页数：10
相关论文
共 50 条
  • [31] Efficient hardware architecture for fast IP address lookup
    Pao, D
    Liu, C
    Wu, A
    Yeung, L
    Chan, KS
    IEEE INFOCOM 2002: THE CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-3, PROCEEDINGS, 2002, : 555 - 561
  • [32] The design of efficient hashing techniques for IP address lookup
    Pandya, Devang
    Martinez, Chris
    Lin, Wei-Ming
    Patel, Parimal
    31ST IEEE CONFERENCE ON LOCAL COMPUTER NETWORKS, PROCEEDINGS, 2006, : 531 - +
  • [33] Binary search in a balanced tree for IP address lookup
    Lim, H
    Kim, W
    Lee, B
    2005 WORKSHOP ON HIGH PERFORMANCE SWITCHING AND ROUTING, 2005, : 490 - 494
  • [34] Binary search on prefix lengths for IP address lookup
    Mun, Ju Hyoung
    Lim, Hyesook
    Yim, Changhoon
    IEEE COMMUNICATIONS LETTERS, 2006, 10 (06) : 492 - 494
  • [35] Scalable IP routing lookup in next generation network
    Chan, CT
    Wang, PC
    Hu, SC
    Lee, CL
    Chen, RC
    INFORMATION NETWORKING: NETWORKING TECHNOLOGIES FOR ENHANCED INTERNET SERVICES, 2003, 2662 : 46 - 55
  • [36] Flexible and fast IP lookup algorithm
    Pak, WG
    Bahk, SW
    2001 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, VOLS 1-10, CONFERENCE RECORD, 2001, : 2053 - 2057
  • [37] An efficient IP address lookup algorithm based on a small balanced tree using entry reduction
    Park, Hyuntae
    Hong, Hyejeong
    Kang, Sungho
    COMPUTER NETWORKS, 2012, 56 (01) : 231 - 243
  • [38] A multi-thread based approach for IP Address Lookup
    Zhian, Hootan
    Jokar, Ali
    Farrokhi, Navid
    Sabaei, Masoud
    2013 21ST IRANIAN CONFERENCE ON ELECTRICAL ENGINEERING (ICEE), 2013,
  • [39] An Improvement of IP Address Lookup based on Rule Filter Analysis
    Perez, K. Guerra
    Yang, X.
    Sezer, S.
    2014 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS WORKSHOPS (ICC), 2014, : 688 - 693
  • [40] Binary searches on multiple small trees for IP address lookup
    Lim, HS
    Lee, B
    Kim, N
    IEEE COMMUNICATIONS LETTERS, 2005, 9 (01) : 75 - 77
12345