A multi-index hybrid trie for lookup and updates

Chia Hung Lin, Chia Yin Hsu, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


High-performance routers require high-speed IP address lookup to achieve wire-speed packet forwarding. This study proposes a new data structure, the Multi-Index Hybrid Trie (MIHT), for dynamic router table designs. This data structure was constructed by combining the useful characteristics of the ${\rm B}+tree and priority trie. IP lookup operations can be performed efficiently by associating each prefix with a key value in the MIHT. Furthermore, because the required tree height and number of prefixes were reduced, dynamic router table operations were performed efficiently using the MIHT. To reduce the memory requirement, each prefix stored its corresponding suffix in a node of the MIHT, rather than storing a full prefix. Experiments using IPv4 and IPv6 routing databases indicated that the proposed data structure has efficient memory usage and performs well for lookup, insertion, deletion operations. This study reports the results of the experiments performed to compare the proposed data structure with other structures using the benchmark IPv4 and IPv6 prefix databases AS1221, AS4637, AS6447, AS65000, AS1221∗, and AS6447∗ with 407,067, 219,581, 417,995, 406,973, 12,155, and 12,278 prefixes, respectively, where AS1221∗ and AS6447∗ are IPv6 BGP routing tables.

Original languageEnglish
Article number6585242
Pages (from-to)2486-2498
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number10
Publication statusPublished - 2014 Oct 1

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'A multi-index hybrid trie for lookup and updates'. Together they form a unique fingerprint.

Cite this