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 条
  • [41] IP address lookup using bit-shuffled trie
    Pao, Derek
    Lu, Ziyan
    Poon, Yat Hang
    [J]. COMPUTER COMMUNICATIONS, 2014, 47 : 51 - 64
  • [42] Multiway range trees: scalable IP lookup with fast updates
    Warkhede, P
    Suri, S
    Varghese, G
    [J]. COMPUTER NETWORKS-THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNICATIONS NETWORKING, 2004, 44 (03): : 289 - 303
  • [43] Architecture and Performance Models for Scalable IP Lookup Engines on FPGA
    Yang, Yi-Hua E.
    Qu, Yun
    Haria, Swapnil
    Prasanna, Viktor K.
    [J]. 2013 IEEE 14TH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE SWITCHING AND ROUTING (HPSR), 2013, : 156 - 163
  • [44] High speed IP address lookup architecture using hashing
    Lim, H
    Seo, JH
    Jung, YJ
    [J]. IEEE COMMUNICATIONS LETTERS, 2003, 7 (10) : 502 - 504
  • [45] Binary Search On Prefix Covered Levels For IP Address Lookup
    Zhu, Guosheng
    Yu, Shaohua
    Dai, Jinyou
    [J]. 2009 5TH INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS, NETWORKING AND MOBILE COMPUTING, VOLS 1-8, 2009, : 3859 - +
  • [46] Compact Trie Forest: Scalable architecture for IP Lookup on FPGAs
    Erdem, Oguzhan
    Carus, Aydin
    Hoang Le
    [J]. 2012 INTERNATIONAL CONFERENCE ON RECONFIGURABLE COMPUTING AND FPGAS (RECONFIG), 2012,
  • [47] IP-address lookup using LC-tries
    Nilsson, S
    Karlsson, G
    [J]. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 1999, 17 (06) : 1083 - 1092
  • [48] Multiway range trees: Scalable IP lookup with fast updates
    Suri, S
    Varghese, G
    Warkhede, PR
    [J]. GLOBECOM '01: IEEE GLOBAL TELECOMMUNICATIONS CONFERENCE, VOLS 1-6, 2001, : 1610 - 1614
  • [49] Dynamic pipelining: Making IP-lookup truly scalable
    Hasan, J
    Vijaykumar, TN
    [J]. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2005, 35 (04) : 205 - 216
  • [50] A parallel IP lookup algorithm for terabit router
    Zheng, K
    Lu, HB
    Liu, B
    [J]. 2003 INTERNATIONAL CONFERENCE ON COMMUNICATION TECHNOLOGY, VOL 1 AND 2, PROCEEDINGS, 2003, : 478 - 481
12345