Volume 27 Issue 7 - October 10, 2014 PDF
Multi-prefix trie: a new data structure for designing dynamic router-tables
Sun-Yuan Hsieh1,2,3,*, Yi-Ling Huang1, Ying-Chi Yang1
1 Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan
2 Institute of Manufacturing Information and Systems, National Cheng Kung University, Tainan
3 Institute of Medical Informatics, National Cheng Kung University, Tainan
Font Enlarge
IP lookup affects the speed of the incoming packet to which output port, which is an important role in the router-table design. Since the Internet is changeable, the router-table must be dynamic for supporting insertion and deletion quickly. In this thesis, we propose Suffix B-Tree data structures for dynamic router-tables design to speed up IP lookup and update. The unique feature of our data structure is that one node can store more than one prefixes to reduce the number of memory access. When lookup, it may search more prefixes in one node and find the longest matching prefix not matching until the leaf. When update, it needs not to reconstruct the table and also works quickly. As a byproduct, the proposed data structure not only minimizes operating time but also reduces the number of memory access. The lookup and insertion take , where W is the length of IP address and m is stride. The deletion takes . Furthermore, based on Suffix B-Tree, we also introduce another extended structure called Index Suffix B-tree which outperforms Suffix B-tree.
< Previous
Next >
Copyright National Cheng Kung University