A fast table update scheme for high-performance IP forwarding

Abstract

There has been an extensive study in constructing the routing tables during the past few years. Although the existing works have certain advantages, ho,vel er, those approaches either use complicated data structures which result in large storage requirement and high complexity updating/building the forwarding table, or they are not scalable refit 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 insertion. Although this can be justified, the performance of routing-table reconstruction in BGP is too time-consuming,ring 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 fufil 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 fowarding table size and shorten the lookup time.