A fast table update scheme for high-performance IP forwarding

P. C. Wang, C. T. Chan, Yaw-Chung Chen

Research output: Contribution to conferencePaper

4 Scopus citations

Abstract

There has been an extensive study in constructing the routing tables during the past few years. Although the existing works have certain advantages, however, those approaches either use complicated data structures which result in large storage requirement and high complexity for updating/building the forwarding table, or they are not scalable to fit in IPv6. Lampson et al. proposed an IP lookup algorithm which performs binary search on prefixes (BSP) [11]. The algorithm is attractive, even for IPv6, because of its bounded worst-case memory requirement. For achieving fast forwarding, the cost paid is the slowing down of insertion. Although this can be justified, the performance of routing-table reconstruction in BGP is too time-consuming to handle the frequent route updates. In this work, we propose a fast forwarding-table construction algorithm which can handle more than 4,000 route updates per second. Moreover, it is simple enough to fulfill the need of fast packet forwarding. With the modified multiway search tree, we can further reduce the depth of the tree and eliminate the storage for pointers, this reduces the forwarding table size and shorten the lookup time.

Original languageEnglish
Pages592-597
Number of pages6
DOIs
StatePublished - 1 Jan 2001
Event8th International Conference on Parallel and Distributed Systems - Kyongju, Korea, Republic of
Duration: 26 Jun 200129 Jun 2001

Conference

Conference8th International Conference on Parallel and Distributed Systems
CountryKorea, Republic of
CityKyongju
Period26/06/0129/06/01

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

    Wang, P. C., Chan, C. T., & Chen, Y-C. (2001). A fast table update scheme for high-performance IP forwarding. 592-597. Paper presented at 8th International Conference on Parallel and Distributed Systems, Kyongju, Korea, Republic of. https://doi.org/10.1109/ICPADS.2001.934871