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 条
  • [21] A fast and updatable IP address lookup scheme
    Chung, SH
    Jean, S
    Yoon, H
    Cho, JW
    2001 INTERNATIONAL CONFERENCE ON COMPUTER NETWORKS AND MOBILE COMPUTING, PROCEEDINGS, 2001, : 419 - 424
  • [22] Ternary CAM Compaction For IP Address Lookup
    Fang, Yi-Ting
    Huang, Tzung-Chian
    Wang, Pi-Chung
    2008 22ND INTERNATIONAL WORKSHOPS ON ADVANCED INFORMATION NETWORKING AND APPLICATIONS, VOLS 1-3, 2008, : 1462 - 1467
  • [23] Efficient binary search for IP address lookup
    Yim, C
    Lee, B
    Lim, H
    IEEE COMMUNICATIONS LETTERS, 2005, 9 (07) : 652 - 654
  • [24] Scalable pipelined IP lookup with prefix tries
    Wu, Yi
    Nong, Ge
    Hamdi, Mounir
    COMPUTER NETWORKS, 2017, 120 : 1 - 11
  • [25] Towards Dynamic and Scalable High-Speed IP Address Lookup Based on B plus Tree
    Wang, Gang
    Lin, Yaping
    Li, Rui
    Li, Jinguo
    Yao, Xin
    Liu, Peng
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2012, E95D (09): : 2277 - 2287
  • [26] GENETIC-ALGORITHM MEMORY MINIMISATION FOR DESIGNING RECONFIGURABLE IP ADDRESS LOOKUP ENGINE
    Shamshiri, Saeed
    Fakhraie, S. Mehdi
    INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE AND APPLICATIONS, 2005, 5 (01) : 69 - 90
  • [27] IP address lookup with the visualizable biased segment tree
    Lee, I
    Mun, JS
    Kim, SR
    FUZZY SYSTEMS AND KNOWLEDGE DISCOVERY, PT 1, PROCEEDINGS, 2005, 3613 : 1137 - 1140
  • [28] Adaptive hashing for IP address lookup in computer networks
    Martinez, Christopher
    Lin, Wei-Ming
    ICON: 2006 IEEE INTERNATIONAL CONFERENCE ON NETWORKS, VOLS 1 AND 2, PROCEEDINGS: NETWORKING -CHALLENGES AND FRONTIERS, 2006, : 198 - +
  • [29] Binary search on prefix lengths for IP address lookup
    Information Electronics Engineering Dept., Ewha W. University, Seoul, Korea, Republic of
    不详
    IEEE Commun Lett, 2006, 6 (492-494): : 492 - 494
  • [30] Efficient hardware architecture for fast IP address lookup
    Pao, D
    Liu, C
    Wu, A
    Yeung, L
    Chan, KS
    IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, 2003, 150 (01): : 43 - 52
12345