Fast trie-based routing lookup with tiny searchable core

Pi Chung Wang*, Chia Tai Chan, Wei Chun Tseng, Yaw-Chung Chen

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations

Abstract

We present a novel solution to the problem of best matching prefix (BMP) which is required in the IP routing lookup. Our approach is based on the trie-based algorithm. The idea is to prune the trie so that the main-searchable portion of the trie can be fit into the small on-chip SRAM. The algorithm consists of two parts: Level Smart-Compression Trie and Trie Pruning. In the first part, we presents the new trie-based algorithm which can provide flexibility, storage efficiency and incremental update. Moreover, the fix-size data structure eliminates the complexity of the memory management. Secondly, we define the "core" and present how to apply the concept "trie pruning" to achieve fast IP routing lookup. With the currently popular platform, the proposed scheme can provide 40 MPPS without any assumption. While considering route flaps, the performance will degrade by only 0.01% with 4,000 BGP updates per 30 seconds.

Original languageEnglish
Pages2328-2332
Number of pages5
StatePublished - 1 Dec 2002
EventGLOBECOM'02 - IEEE Global Telecommunications Conference - Taipei, Taiwan
Duration: 17 Nov 200221 Nov 2002

Conference

ConferenceGLOBECOM'02 - IEEE Global Telecommunications Conference
CountryTaiwan
CityTaipei
Period17/11/0221/11/02

Fingerprint Dive into the research topics of 'Fast trie-based routing lookup with tiny searchable core'. Together they form a unique fingerprint.

Cite this