標題: Coded and Scalar Prefix Trees: Prefix Matching Using the Novel Idea of Double Relation Chains
作者: Behdadfar, Mohammad
Saidi, Hossein
Hashemi, Massoud Reza
Lin, Ying-Dar
資訊工程學系
Department of Computer Science
關鍵字: Totally ordered set;prefix;LPM;LMP;DRC;coded prefix;scalar prefix
公開日期: 1-Jun-2011
摘要: 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 implementhble 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.
URI: http://dx.doi.org/10.4218/etrij.11.0110.0381
http://hdl.handle.net/11536/23025
ISSN: 1225-6463
DOI: 10.4218/etrij.11.0110.0381
期刊: ETRI JOURNAL
Volume: 33
Issue: 3
起始頁: 344
結束頁: 354
Appears in Collections:Articles


Files in This Item:

  1. 5bb678ca0ad0b77cf802b8839b484c38.pdf