A fast table update scheme for high-performance IP forwarding

Pi Chung Wang*, Chia Tai Chan, Yaw-Chung Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In the previous work, Lampson et al. proposed an IP lookup algorithm which performs binary search on prefixes (BSP) [1]. The algorithm is attractive, even for IPv6, because of its bounded worst-case memory requirement. To achieve fast forwarding, it may need to slow down the insertion speed. Although this can be justified, the routing-table reconstruction in BSP is too time-consuming to handle the frequent route updates. In this work, we propose a fast forwarding-table construction algorithm which can accomplish more than 4,000 route updates per second. Moreover, it is simple enough to fulfill the need of fast packet forwarding. With the enhanced multiway search tree, we further reduced the depth of the tree and eliminated the pointer storage; this reduces the forwarding table size and shortens the lookup time.

Original languageEnglish
Pages (from-to)318-324
Number of pages7
JournalIEICE Transactions on Communications
VolumeE85-B
Issue number1
DOIs
StatePublished - 1 Jan 2002

Keywords

  • IP route lookup
  • L3 switching
  • Multiway search tree
  • Route flap

Fingerprint Dive into the research topics of 'A fast table update scheme for high-performance IP forwarding'. Together they form a unique fingerprint.

Cite this