Fast trie-based routing lookup with tiny searchable core

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

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

National Chiao Tung University

Research output: Contribution to conference › Paper › peer-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 language	English
Pages	2328-2332
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

Conference	GLOBECOM'02 - IEEE Global Telecommunications Conference
Country	Taiwan
City	Taipei
Period	17/11/02 → 21/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

@conference{a9796cddbe26416e8859acc2bdc9bcb5,

title = "Fast trie-based routing lookup with tiny searchable core",

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.",

author = "Wang, {Pi Chung} and Chan, {Chia Tai} and Tseng, {Wei Chun} and Yaw-Chung Chen",

year = "2002",

month = dec,

day = "1",

language = "English",

pages = "2328--2332",

note = "null ; Conference date: 17-11-2002 Through 21-11-2002",

}

TY - CONF

T1 - Fast trie-based routing lookup with tiny searchable core

AU - Wang, Pi Chung

AU - Chan, Chia Tai

AU - Tseng, Wei Chun

AU - Chen, Yaw-Chung

PY - 2002/12/1

Y1 - 2002/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036971773&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0036971773

SP - 2328

EP - 2332

Y2 - 17 November 2002 through 21 November 2002

ER -