Enhanced Patricia Tree with Reordeing and Fast Incremental and Decremental Update Functions
Routing-table lookup function is formed as a tree structure. In particular, backbone router of the Internet manages a huge tree structure of the routing table in order to store all routing information brought by routing protocols, such as BGP. Though high-speed lookup is desirable for the backbone router, the tree-based lookup requires multiple memory accesses and it degrades the throughput of the lookup. Aggregation of redundant nodes and elimination of useless nodes are necessary for the high-throughput lookup. Enhanced Patricia Tree (EPT) and Enhanced Patricia Tree with Reordering (EPT-R) were studied for the high-throughput lookup. In this paper, the incremental and decremental update algorithms for EPT-R are proposed and evaluated. These incremental and decremental update algorithms for EPT and EPT-R are effective in quick update time.
component routing lookup internet router enhanced patricia tree with reordering
Koji Ikehara Hiroaki Nishi
Graduate School of Science and Technology Keio University Yokohama, Japan Department of System Design Keio University Yokohama, Japan
国际会议
2010 International Conference on Future Information Technology(2010年未来信息技术国际会议 ICFIT 2010)
长沙
英文
57-62
2010-12-14（万方平台首次上网日期，不代表论文的发表时间）