For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Fast Table Update Scheme for High-Performance IP Forwarding
Pi-Chung WANG Chia-Tai CHAN Yaw-Chung CHEN
IEICE TRANSACTIONS on Communications
Publication Date: 2002/01/01
Print ISSN: 0916-8516
Type of Manuscript: PAPER
IP route lookup, route flap, L3 switching, multiway search tree,
Full Text: PDF(686.5KB)>>
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.