Efficient binary search for IP address lookup

Author

Yim, Changhoon ; Lee, Bomi ; Lim, Hyesook

Author_Institution

Dept. of Internet & Multimedia Eng., Konkuk Univ., Seoul, South Korea

Volume

9

Issue

7

fYear

2005

fDate

7/1/2005 12:00:00 AM

Firstpage

652

Lastpage

654

Abstract

As an essential function in Internet routers, address lookup determines overall router performance. The most important performance metric in software-based address lookup is the number of memory accesses since it is directly related to lookup time. This letter proposes an algorithm to perform efficient binary search for IP address lookup. The depth of the proposed binary tree is very close to the minimum bound, and hence it results in much smaller number of worst case memory accesses compared to previous schemes. The proposed algorithm requires comparably small size of memory, and it can be used for software-based address lookup in practical Internet routers.

Keywords

Internet; software architecture; table lookup; telecommunication network routing; transport protocols; tree data structures; tree searching; trees (mathematics); Internet routers; binary search; binary tree; binary tries; longest prefix matching; software-based IP address lookup; Application specific integrated circuits; Associative memory; Binary trees; Costs; Hardware; Internet; Routing; Scalability; Switches; Time measurement;

fLanguage

English

Journal_Title

Communications Letters, IEEE

Publisher

ieee

ISSN

1089-7798

Type

jour

DOI

10.1109/LCOMM.2005.1461694

Filename

1461694