• Jun 16, 2017 News!Vol.6, No.3 has been indexed by EI (Inspec).   [Click]
  • Jun 15, 2017 News!Vol.6, No.2 has been indexed by EI (Inspec).   [Click]
  • Jun 14, 2017 News!Vol.6, No.1 has been indexed by EI (Inspec).   [Click]
General Information
Editor-in-chief

 
Faculty of Science, University of Brunei Darussalam, Brunei Darussalam   
" It is a great honor to serve as the editor-in-chief of IJIEE. I'll work together with the editorial team. Hopefully, IJIEE will be recognized among the readers in the related field."
IJIEE 2012 Vol.2(5): 656-660 ISSN: 2010-3719
DOI: 10.7763/IJIEE.2012.V2.182

Enhanced Patricia Tree with Reordering and Fast Incremental and Decremental Update Functions

Shin-ichi Ishida, Koji Ikehara, and Hiroaki Nishi

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)

[PDF]

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.

Copyright © 2008-2016. International Journal of Information and Electronics Engineering. All rights reserved.
E-mail: ijiee@ejournal.net