Coded and scalar prefix trees: Prefix matching using the novel idea of double relation chains

Mohammad Behdadfar*, Hossein Saidi, Massoud Reza Hashemi, Ying-Dar Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

In this paper, a model is introduced named double relation chains (DRC) based on ordered sets. It is proved that using DRC and special relationships among the members of an alphabet, vectors of this alphabet can be stored and searched in a tree. This idea is general; however, one special application of DRC is the longest prefix matching (LPM) problem in an IP network. Applying the idea of DRC to the LPM problem makes the prefixes comparable like numbers using a pair of w-bit vectors to store at least one and at most w prefixes, where w is the IP address length. This leads to good compression performance. Based on this, two recently introduced structures called coded prefix trees and scalar prefix trees are shown to be specific applications of DRC. They are implementable on balanced trees which cause the node access complexity for prefix search and update procedures to be O(log n) where n is the number of prefixes. As another advantage, the number of node accesses for these procedures does not depend on w. Additionally, they need fewer number of node accesses compared to recent range-based solutions. These structures are applicable on both IPv4 and IPv6, and can be implemented in software or hardware.

Original languageEnglish
Pages (from-to)344-354
Number of pages11
JournalETRI Journal
Volume33
Issue number3
DOIs
StatePublished - 1 Jun 2011

Keywords

  • Coded prefix
  • DRC
  • LMP
  • LPM
  • Prefix
  • Scalar prefix
  • Totally ordered set

Fingerprint Dive into the research topics of 'Coded and scalar prefix trees: Prefix matching using the novel idea of double relation chains'. Together they form a unique fingerprint.

Cite this