Multiprefix trie: A new data structure for designing dynamic router-tables

Sun Yuan Hsieh, Yi Ling Huang, Ying Chi Yang

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

Abstract

IP lookup affects the speed of an incoming packet and the time required to determine which output port the packet should be sent to; hence, it plays an important role in the design of router-tables. In this paper, we propose a new data structure, called a multiprefix trie, for use in designing dynamic router-tables. One key feature of our data structure is that each node can store more than one prefix, which reduces the number of memory accesses. When performing lookup, the structure can search more prefixes in one node and may find the longest matching prefix in an internal node rather than on a leaf. Moreover, when updating the router-table, it does not need to reconstruct the table. As a by-product, the proposed data structure minimizes the time required for dynamic router-table operations, including lookup, insertion, and deletion, and also reduces the number of memory accesses. We report the results of experiments conducted to compare the proposed data structure with other structures using the benchmark IPv4 prefix database AS4637 with 219,581 prefixes.

Original languageEnglish
Article number5487496
Pages (from-to)693-706
Number of pages14
JournalIEEE Transactions on Computers
Volume60
Issue number5
DOIs
Publication statusPublished - 2011 Apr 4

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Multiprefix trie: A new data structure for designing dynamic router-tables'. Together they form a unique fingerprint.

Cite this