High-speed IP address lookup using balanced multi-way trees

Hyesook Lim; Wonjung Kim; Bomi Lee; Changhoon Yim

doi:10.1016/j.comcom.2005.12.002

High-speed IP address lookup using balanced multi-way trees

Hyesook Lim, Wonjung Kim, Bomi Lee, Changhoon Yim

Electronic and Electrical Engineering

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

7 Scopus citations

Abstract

Rapid growth of the Internet traffic requires more bandwidth and high-speed packet processing in the Internet routers. As one of the major packet processing performed in routers, address lookup determines an output port using the destination IP address of incoming packets. Since routers should perform address lookups in real-time for hundred millions of incoming packets per second referring a huge routing table, address lookup is one of the most challenging operations. In this paper, we propose a multi-way search architecture for IP address lookup which shows very good performance in search speed. The performance evaluation results show that the proposed scheme requires a single 282 kbyte SRAM to store about 40,000 routing entries, and an address lookup is achieved by 5.9 memory accesses in average.

Original language	English
Pages (from-to)	1927-1935
Number of pages	9
Journal	Computer Communications
Volume	29
Issue number	11
DOIs	https://doi.org/10.1016/j.comcom.2005.12.002
State	Published - 26 Jul 2006

Bibliographical note

Funding Information:
This research was supported by the Ministry of Information and Communications, Korea, under HNRC-ITRC support program supervised by IITA.

Keywords

Balanced tree
Binary prefix tree
IP address lookup
Memory access
Multi-way tree
Router

Access to Document

10.1016/j.comcom.2005.12.002

Cite this

@article{b0d8f9a33a0341c183e3940483cde49e,

title = "High-speed IP address lookup using balanced multi-way trees",

abstract = "Rapid growth of the Internet traffic requires more bandwidth and high-speed packet processing in the Internet routers. As one of the major packet processing performed in routers, address lookup determines an output port using the destination IP address of incoming packets. Since routers should perform address lookups in real-time for hundred millions of incoming packets per second referring a huge routing table, address lookup is one of the most challenging operations. In this paper, we propose a multi-way search architecture for IP address lookup which shows very good performance in search speed. The performance evaluation results show that the proposed scheme requires a single 282 kbyte SRAM to store about 40,000 routing entries, and an address lookup is achieved by 5.9 memory accesses in average.",

keywords = "Balanced tree, Binary prefix tree, IP address lookup, Memory access, Multi-way tree, Router",

author = "Hyesook Lim and Wonjung Kim and Bomi Lee and Changhoon Yim",

note = "Funding Information: This research was supported by the Ministry of Information and Communications, Korea, under HNRC-ITRC support program supervised by IITA. ",

year = "2006",

month = jul,

day = "26",

doi = "10.1016/j.comcom.2005.12.002",

language = "English",

volume = "29",

pages = "1927--1935",

journal = "Computer Communications",

issn = "0140-3664",

publisher = "Elsevier B.V.",

number = "11",

}

TY - JOUR

T1 - High-speed IP address lookup using balanced multi-way trees

AU - Lim, Hyesook

AU - Kim, Wonjung

AU - Lee, Bomi

AU - Yim, Changhoon

N1 - Funding Information: This research was supported by the Ministry of Information and Communications, Korea, under HNRC-ITRC support program supervised by IITA.

PY - 2006/7/26

Y1 - 2006/7/26

N2 - Rapid growth of the Internet traffic requires more bandwidth and high-speed packet processing in the Internet routers. As one of the major packet processing performed in routers, address lookup determines an output port using the destination IP address of incoming packets. Since routers should perform address lookups in real-time for hundred millions of incoming packets per second referring a huge routing table, address lookup is one of the most challenging operations. In this paper, we propose a multi-way search architecture for IP address lookup which shows very good performance in search speed. The performance evaluation results show that the proposed scheme requires a single 282 kbyte SRAM to store about 40,000 routing entries, and an address lookup is achieved by 5.9 memory accesses in average.

AB - Rapid growth of the Internet traffic requires more bandwidth and high-speed packet processing in the Internet routers. As one of the major packet processing performed in routers, address lookup determines an output port using the destination IP address of incoming packets. Since routers should perform address lookups in real-time for hundred millions of incoming packets per second referring a huge routing table, address lookup is one of the most challenging operations. In this paper, we propose a multi-way search architecture for IP address lookup which shows very good performance in search speed. The performance evaluation results show that the proposed scheme requires a single 282 kbyte SRAM to store about 40,000 routing entries, and an address lookup is achieved by 5.9 memory accesses in average.

KW - Balanced tree

KW - Binary prefix tree

KW - IP address lookup

KW - Memory access

KW - Multi-way tree

KW - Router

UR - http://www.scopus.com/inward/record.url?scp=33745726119&partnerID=8YFLogxK

U2 - 10.1016/j.comcom.2005.12.002

DO - 10.1016/j.comcom.2005.12.002

M3 - Article

AN - SCOPUS:33745726119

SN - 0140-3664

VL - 29

SP - 1927

EP - 1935

JO - Computer Communications

JF - Computer Communications

IS - 11

ER -

High-speed IP address lookup using balanced multi-way trees

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this