• Jun 01, 2020 News!Papers published in Vol.10, No.2 have all received dois from Crossref.
  • May 15, 2020 News!Papers published in Vol.9, No.1-Vol.10, No.1 have all received dois from Crossref.
  • May 15, 2020 News!IJIEE Vol. 10, No. 2 issue has been published online!   [Click]
General Information
    • ISSN: 2010-3719 (Online)
    • Abbreviated Title: Int. J. Inf. Electron. Eng.
    • Frequency: Quarterly
    • DOI: 10.18178/IJIEE
    • Editor-in-Chief: Prof. Chandratilak De Silva Liyanage
    • Executive Editor: Jennifer Zeng
    • Abstracting/ Indexing : Google Scholar, Electronic Journals Library, Crossref and ProQuest,  INSPEC (IET), EBSCO, CNKI.
    • E-mail ijiee@ejournal.net
Editor-in-chief

 
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, The value of IJIEE will be well 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-2021. International Journal of Information and Electronics Engineering. All rights reserved.
E-mail: ijiee@ejournal.net