IP address lookup for internet routers using balanced binary search with prefix vector

Hyesook Lim; Hyeong Gee Kim; Changhoon Yim

doi:10.1109/TCOMM.2009.03.070146

IP address lookup for internet routers using balanced binary search with prefix vector

Hyesook Lim
, Hyeong Gee Kim
, Changhoon Yim

Electronic and Electrical Engineering

Research output: Contribution to journal › Article › peer-review

20 Scopus citations

Abstract

We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.

Original language	English
Pages (from-to)	618-621
Number of pages	4
Journal	IEEE Transactions on Communications
Volume	57
Issue number	3
DOIs	https://doi.org/10.1109/TCOMM.2009.03.070146
State	Published - 2009

Bibliographical note

Funding Information:
Paper approved by T.-S. P. Yum, the Editor for Packet Access and Switching of the IEEE Communications Society. Manuscript received October 25, 2007. This research was supported by the Ministry of Information and Communications under a HNRC-ITRC support program supervised by IITA. H. Lim and H. G. Kim are with the Department of Electronics Engineering, Ewha W. University, Seoul, Korea (e-mail: [email protected]). C. Yim is with the Department of Internet and Multimedia Engineering, Konkuk University, Seoul, Korea (e-mail: [email protected]). Digital Object Identifier 10.1109/TCOMM.2009.03.070146

Keywords

Binary search tree
Binary trie
IP address lookup
Internet
Router

Access to Document

10.1109/TCOMM.2009.03.070146

Cite this

@article{79534950e3694e4c9a5492f8f075b693,

title = "IP address lookup for internet routers using balanced binary search with prefix vector",

abstract = "We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.",

keywords = "Binary search tree, Binary trie, IP address lookup, Internet, Router",

author = "Hyesook Lim and Kim, \{Hyeong Gee\} and Changhoon Yim",

note = "Funding Information: Paper approved by T.-S. P. Yum, the Editor for Packet Access and Switching of the IEEE Communications Society. Manuscript received October 25, 2007. This research was supported by the Ministry of Information and Communications under a HNRC-ITRC support program supervised by IITA. H. Lim and H. G. Kim are with the Department of Electronics Engineering, Ewha W. University, Seoul, Korea (e-mail: [email protected]). C. Yim is with the Department of Internet and Multimedia Engineering, Konkuk University, Seoul, Korea (e-mail: [email protected]). Digital Object Identifier 10.1109/TCOMM.2009.03.070146",

year = "2009",

doi = "10.1109/TCOMM.2009.03.070146",

language = "English",

volume = "57",

pages = "618--621",

journal = "IEEE Transactions on Communications",

issn = "0090-6778",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - IP address lookup for internet routers using balanced binary search with prefix vector

AU - Lim, Hyesook

AU - Kim, Hyeong Gee

AU - Yim, Changhoon

N1 - Funding Information: Paper approved by T.-S. P. Yum, the Editor for Packet Access and Switching of the IEEE Communications Society. Manuscript received October 25, 2007. This research was supported by the Ministry of Information and Communications under a HNRC-ITRC support program supervised by IITA. H. Lim and H. G. Kim are with the Department of Electronics Engineering, Ewha W. University, Seoul, Korea (e-mail: [email protected]). C. Yim is with the Department of Internet and Multimedia Engineering, Konkuk University, Seoul, Korea (e-mail: [email protected]). Digital Object Identifier 10.1109/TCOMM.2009.03.070146

PY - 2009

Y1 - 2009

N2 - We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.

AB - We propose an efficient binary search algorithm for IP address lookup in the Internet routers. While most of the previous binary search algorithms do not provide a balanced search, the proposed algorithm provides a perfectly balanced search, and hence it provides excellent search performance and scalability toward large routing tables.

KW - Binary search tree

KW - Binary trie

KW - IP address lookup

KW - Internet

KW - Router

UR - https://www.scopus.com/pages/publications/63649121111

U2 - 10.1109/TCOMM.2009.03.070146

DO - 10.1109/TCOMM.2009.03.070146

M3 - Article

AN - SCOPUS:63649121111

SN - 0090-6778

VL - 57

SP - 618

EP - 621

JO - IEEE Transactions on Communications

JF - IEEE Transactions on Communications

IS - 3

ER -

IP address lookup for internet routers using balanced binary search with prefix vector

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this