IEICE TRANSACTIONS on Communications
A Fast Table Update Scheme for High-Performance IP Forwarding
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Communications Vol.E85-B No.1 pp.318-324
- Publication Date
- 2002/01/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Internet
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Pi-Chung WANG, Chia-Tai CHAN, Yaw-Chung CHEN, "A Fast Table Update Scheme for High-Performance IP Forwarding" in IEICE TRANSACTIONS on Communications,
vol. E85-B, no. 1, pp. 318-324, January 2002, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e85-b_1_318/_p
Copy
@ARTICLE{e85-b_1_318,
author={Pi-Chung WANG, Chia-Tai CHAN, Yaw-Chung CHEN, },
journal={IEICE TRANSACTIONS on Communications},
title={A Fast Table Update Scheme for High-Performance IP Forwarding},
year={2002},
volume={E85-B},
number={1},
pages={318-324},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - A Fast Table Update Scheme for High-Performance IP Forwarding
T2 - IEICE TRANSACTIONS on Communications
SP - 318
EP - 324
AU - Pi-Chung WANG
AU - Chia-Tai CHAN
AU - Yaw-Chung CHEN
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E85-B
IS - 1
JA - IEICE TRANSACTIONS on Communications
Y1 - January 2002
AB - 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.
ER -
English
