Multi-inherited search tree for dynamic IP router-tables

Po Cheng Hsu, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


IP lookup and routing table update affect the speed at which a router forwards packets. This study proposes a new data structure for dynamic router tables used in IP lookup and update, called the Multi-inherited Search Tree (MIST). Partitioning each prefix according to an index value and removing the relationships among prefixes enables performing IP lookup operations efficiently. Because a prefix trie is used as a substructure, memory can be consumed and dynamic router-table operations can be performed efficiently. Experiments using real IPv4 routing databases indicated that the MIST uses memory efficiently and performs lookup, insert, and delete operations effectively.

Original languageEnglish
Article number7480793
Pages (from-to)114-126
Number of pages13
JournalIEEE Transactions on Computers
Issue number1
Publication statusPublished - 2017 Jan 1

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Multi-inherited search tree for dynamic IP router-tables'. Together they form a unique fingerprint.

Cite this