A Fast Table Update Scheme for High-Performance IP Forwarding

Pi-Chung WANG  Chia-Tai CHAN  Yaw-Chung CHEN  

IEICE TRANSACTIONS on Communications   Vol.E85-B   No.1   pp.318-324
Publication Date: 2002/01/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Internet
IP route lookup,  route flap,  L3 switching,  multiway search tree,  

Full Text: PDF(686.5KB)>>
Buy this Article

In the previous work, Lampson et al. proposed an IP lookup algorithm which performs binary search on prefixes (BSP). 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.