Coded and Scalar Prefix Trees: Prefix Matching Using the Novel Idea of Double Relation Chains

ETRI Journal

关键词: scalar prefix;    coded prefix;    DRC;    LMP;    LPM;    prefix;    Totally ordered set;   

Others  :  1186103
DOI  :  10.4218/etrij.11.0110.0381

【 摘 要 】

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.

   

【 参考文献 】

• [1]T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, 1990.
• [2]D.R. Morrison, "PATRICIA Practical Algorithm to Retrieve Information Coded in Alphanumeric," J. ACM, vol. 15, no. 14, Oct. 1968, pp. 514-534.
• [3]S. Nilson and G. Karlsson, "IP Address Lookup Using LC-Tries," IEEE JSAC, vol. 17, June 1999, pp. 1083-1092.
• [4]V. Srinivasan and G. Varghese, "Fast Address Lookups Using Controlled Prefix Expansion," ACM Trans. Computer Syst., vol. 17, no. 1, Feb. 1999, pp. 1-40.
• [5]L.C. Wuu, K.M. Chen, and T.J. Liu, "A Longest Prefix First Search Tree for IP Lookup," Proc. ICC, May 2005, pp. 989-993.
• [6]P. Gupta, S. Lin, and N. McKeown, "Routing Lookups in Hardware at Memory Access Speeds," Proc. IEEE INFOCOM, 1998.
• [7]W. Eatherton, G. Varghese, and Z. Dittia, "Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates," Proc. ACM SIGCOMM, 2004, pp. 97-122.
• [8]B. Lampson, V. Srinivasan, and G. Varghese, "IP Lookups Using Multiway and Multicolumn Search," IEEE/ACM Trans. Networking, vol. 7, no. 3, June. 1999, pp. 324-334.
• [9]P.R. Warkhede, S. Suri, and G. Varghese, "Multiway Range Trees: Scalable IP Lookup with Fast Updates," Computer Netw., vol. 44, no. 3, 2004, pp. 289-303.
• [10]H. Lu and S. Sahni, "A B-Tree Dynamic Router-Table Design," IEEE Trans. Computers, vol. 54, no. 7, 2005, pp. 813-824.
• [11]Q. Sun et al., "A Scalable Exact Matching in Balance Tree Scheme for IPv6 Lookup," ACM SIGCOMM Data Communication Festival, IPv6, Aug. 2007.
• [12]N. Yazdani and P. Min, "Prefix Trees: New Efficient Data Structures for Matching Strings of Different Lengths," Proc. Int. Database Eng. Appl. Symp., July 2001, pp. 76-85.
• [13]M. Behdadfar and H. Saidi, "The CPBT: A Method for Searching the Prefixes Using Coded Prefixes in B-Tree," Proc. IFIP Networking, May, 2008, pp. 562-573.
• [14]M. Behdadfar et al., "Scalar Prefix Search: A New Route Lookup Algorithm for Next Generation Internet." Proc. IEEE INFOCOM, Apr. 2009.
• [15]M. Behdadfar et al., "IP Lookup Using the Novel Idea of Scalar Prefix Search with Fast Table Updates," IEICE Trans. Inf. & Syst., vol. E93-D, no. 11, Nov. 2010, pp. 2932-2943.
• [16]H. Lim, H. Kim, and C. Yim, "IP Address Lookup for Internet Routers Using Balanced Binary Search with Prefix Vector," IEEE Trans. Commun., vol. 57, no. 3, Mar. 2009, pp. 618-621.
• [17]K.H. Rosen and J.G. Michaels, Handbook of Discrete and Combinatorial Mathematics, CRC Press, 2000.
• [18]http://bgp.potaroo.net