IP lookup by scalable multi-way search on prefix lengths

Pau Chuan Ting*, Tsern-Huei Lee

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

IP routing table lookup is an essential technology for supporting high-speed routers. To achieve high speed IP routing table lookup, in this paper, we propose an efficient and scalable algorithm, called multi-way search on prefix lengths. The multi-way search scheme is derived from binary search on prefix lengths which groups route prefixes of identical lengths into individual tables and applies hashing technique in these tables to find matching prefixes. However, the multi-way search scheme significantly improves the average lookup performance of binary search scheme without any loss of its worst-case lookup performance. Further, the proposed scheme is so simple that it basically does not increase the complexity in constructing the search tree and in memory requirement. Through experiments on real backbone routing tables, we found that the improvement can be more than 37% for all routing tables.

Original languageEnglish
Title of host publicationProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 200
EditorsH.R. Arabnia, Y. Mun, H.R. Arabnia, Y. Mun
Pages430-436
Number of pages7
StatePublished - 1 Dec 2003
EventProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications - Las Vegas, NV, United States
Duration: 23 Jun 200326 Jun 2003

Publication series

NameProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications
Volume1

Conference

ConferenceProceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications
CountryUnited States
CityLas Vegas, NV
Period23/06/0326/06/03

Keywords

  • Binary search on prefix lengths
  • IP lookup
  • Marker
  • Pre-computation

Fingerprint Dive into the research topics of 'IP lookup by scalable multi-way search on prefix lengths'. Together they form a unique fingerprint.

Cite this