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.
|Number of pages||5|
|State||Published - 1 Dec 2002|
|Event||GLOBECOM'02 - IEEE Global Telecommunications Conference - Taipei, Taiwan|
Duration: 17 Nov 2002 → 21 Nov 2002
|Conference||GLOBECOM'02 - IEEE Global Telecommunications Conference|
|Period||17/11/02 → 21/11/02|