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 条
  • [1] Fast and scalable schemes for the IP address lookup problem
    Yazdani, N
    Min, PS
    ATM 2000: PROCEEDINGS OF THE IEEE CONFERENCE 2000 ON HIGH PERFORMANCE SWITCHING AND ROUTING, 2000, : 83 - 92
  • [2] Fast and scalable schemes for the IP address lookup problem
    Yazdani, Nasser
    Min, Paul S.
    2000, IEEE, Piscataway, NJ, United States
  • [3] IP address lookup made fast and simple
    Crescenzi, P
    Dardini, L
    Grossi, R
    ALGORITHMS - ESA'99, 1999, 1643 : 65 - 76
  • [4] An on-chip IP address lookup algorithm
    Sun, XH
    Zhao, YQQ
    IEEE TRANSACTIONS ON COMPUTERS, 2005, 54 (07) : 873 - 885
  • [5] Advanced CC Algorithm for IP Address Lookup
    Wang, Junfeng
    Qiao, Lufeng
    Shao, Shilei
    Chen, Qinghua
    PROCEEDINGS OF 2012 2ND INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND NETWORK TECHNOLOGY (ICCSNT 2012), 2012, : 10 - 14
  • [6] An Efficient IP Address Lookup Algorithm Using a Priority Trie
    Lim, Hyesook
    Mun, Ju Hyoung
    GLOBECOM 2006 - 2006 IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, 2006,
  • [7] A Truly Scalable IP Lookup Algorithm for Next Generation Internet
    Dai, Yi
    Xiao, Li-quan
    Wang, Ke-fei
    Zhang, He-ying
    Zhao, Bao-kang
    Wang, Shao-gang
    2013 IEEE SYMPOSIUM ON COMPUTERS AND COMMUNICATIONS (ISCC), 2013,
  • [8] Trie-based algorithm for IP lookup problem
    Yilmaz, PA
    Belenkiy, A
    Uzun, N
    GLOBECOM '00: IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, VOLS 1- 3, 2000, : 593 - 598
  • [9] A fast and scalable IPv4 and 6 address lookup algorithm
    Leu, Seiven
    Chang, Ruay-Shiung
    COMPUTER COMMUNICATIONS, 2006, 29 (16) : 3020 - 3036
  • [10] On Memory Management of Tree-bitmap Algorithm for IP Address Lookup
    Wang, Yagang
    Du, Huimin
    Yang, Kangping
    PROCEEDINGS OF INTERNATIONAL SYMPOSIUM ON COMPUTER SCIENCE AND COMPUTATIONAL TECHNOLOGY (ISCSCT 2009), 2009, : 418 - 422
12345