Multi-way search on prefix lengths for IP routing table lookup

Pau Chuan Ting*, Tsern-Huei Lee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

IP' routing table lookup has been considered as a major bottleneck for high-speed routers. In the past few years, several data structures and related algorithms have been developed to accomplish high-speed routing table lookup. In particular, an efficient algorithm, called binary search on prefix lengths, was designed by grouping prefixes of identical lengths into individual tables and applying hashing technique in these tables to find matching prefixes. The time complexity of binary search on prefix lengths is [log(W +1)] assuming W-bit address. In this paper, we propose a multi-way search algorithm on prefix lengths to improve the average lookup performance of the binary search scheme without sacrificing its worst-case search performance. 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 most tables and 21% for one table.

Original languageEnglish
Pages (from-to)11-18
Number of pages8
JournalJournal of the Chinese Institute of Electrical Engineering, Transactions of the Chinese Institute of Engineers, Series E/Chung KuoTien Chi Kung Chieng Hsueh K'an
Volume11
Issue number1
StatePublished - 1 Feb 2004

Keywords

  • Binary search on prefix lengths
  • Marker
  • Pre-computation
  • Routing table lookup

Fingerprint Dive into the research topics of 'Multi-way search on prefix lengths for IP routing table lookup'. Together they form a unique fingerprint.

Cite this