Abstract—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.
Index Terms—Enhanced patricia tree with reordering, internet router, routing lookup.
The authors are with the Graduate School of Science and Technology, Keio University, Yokohama, Kanagawa, 223-8522, Japan (e-mail:sin@west.sd.keio.ac.jp, ikehara@west.sd.keio.ac.jp, west@sd.keio.ac.jp)
Cite: Shin-ichi Ishida, Koji Ikehara, and Hiroaki Nishi, "Enhanced Patricia Tree with Reordering and Fast Incremental and Decremental Update Functions," International Journal of Information and Electronics Engineering vol. 2, no. 5, pp. 656-660, 2012.