DocumentCode :
1494097
Title :
A Classified Multisuffix Trie for IP Lookup and Update
Author :
Hsieh, Sun-Yuan ; Yang, Ying-Chi
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Cheng Kung Univ., Tainan, Taiwan
Volume :
61
Issue :
5
fYear :
2012
fDate :
5/1/2012 12:00:00 AM
Firstpage :
726
Lastpage :
731
Abstract :
In this paper, a new data structure, called the classified multisuffix trie (CMST), is proposed for designing dynamic router-tables. CMST achieves a better performance than existing data structures because each node can store more than one prefix and the longest matching prefix may be found in an internal node rather than on a leaf. Furthermore, with the classification in each node, the dynamic router-table operations can be performed efficiently. To reduce the memory requirement, we store each prefix´s corresponding suffix in a CMST node, instead of storing a full binary string. Based on the CMST, we also propose another data structure, called the Partitioning Classified Multisuffix Trie (PCMST) to reduce the height of the trie and expedite router-table operations. Experiments using real IPv4 routing databases demonstrate that the proposed data structures are efficient in terms of memory usage and it performs well in terms of the average times of the lookup, insert, and delete operations. We report the results of experiments conducted to compare the performance of the proposed data structure with that of other structures using the benchmark IPv4 prefix databases AS4637, AS6447, and AS65000 with 219,581, 296,552, and 226,847 prefixes, respectively.
Keywords :
IP networks; data structures; telecommunication network routing; AS4637; AS6447; AS65000; IP lookup; IP update; IPv4 prefix database; IPv4 routing database; PCMST; data structure; dynamic router-table; matching prefix; memory usage; partitioning classified multisuffix trie; Data structures; Databases; Heuristic algorithms; IP networks; Internet; Memory management; Routing; Classless inter domain routing; IP address lookup; classified multisuffix trie.; dynamic router tables; longest matching prefix; multiprefix trie;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.2011.86
Filename :
5750004
Link To Document :
بازگشت