臺灣博碩士論文加值系統

良好的資料結構設計和高效率演算法可以有效地提升網路位址查詢和更新
的速度。在這篇論文中，我們提出一個動態的路由表資料結構，稱之為
Multilevel Length-Based-Classified Index Table (MLIT)。在路由表中前綴長度分布不平均的情形下，發現某些長度前綴數量相對其他長度前綴數量比較多，對於這些數量較多的前綴進行特別的處理來提升其平均搜尋速度。另外，藉由多層的架構及索引表的幫助可以加快更新路由表的資料、在資料結構上作一些巧思的設計來增進記憶體使用率。我們的實驗使用真實世界中的路由資料庫，這些資料庫包含網際網路通訊協定中IPv4 和IPv6。透過實驗結果顯示，我們所提出的資料結構不但提供更小的記憶體需求，且在路由表的查詢以及更新運作的效能表現良好。所使用的四個前綴資料庫有AS1221、AS4637、AS6447和AS1221*，它們分別有407,067、219,581、417,995 和21402 筆前綴資料。

A good data structure design can provide high-speed IP lookups and updates. In this paper, a new data structure of dynamic router table is proposed for IP lookups
and updates, called Multilevel Length-Based-Classified Index Table (MLIT). The prefix length distribution of a routing table is uneven situation. There is a large prefix number in certain prefix length. In MLIT, special operation for these prefixes is used to accelerate the average lookup speed. In addition, the multilevel structure with index tables can provide faster updates. And memory requirement utilization is improved by the ingenuity design in data structure. We experimented using real-world routing databases. Our experiments compare the proposed data structure with other structures using the benchmark IPv4 and IPv6 prefix databases AS1221, AS4637, AS6447, AS1221* with 407067, 219581, 417995, 20142 prefixes respectively, where AS1221* is a IPv6 BGP routing table. Both the average lookup time and the average update time are outstanding with other data structures, and the memory requirement less than the
simple structure, like prefix trie and priority trie.

Contents
Contents v
List of Figures vii
List of Tables ix
1 Introduction 1
2 Related Work 5
2.1 Binary Trie........... 5
2.2 Multibit Trie............ 6
2.3 Prefix Tree............ 8
2.4 Multi-Prefix Trie.......... 9
2.5 Priority Trie(PT).......... 11
2.6 Multi-Index Hybrid Trie(MIHT)........ 12
3 The Proposed Data Structure 15
3.1 Index Table........... 15
3.2 B+ tree............. 16
3.3 Sorted Chunk List(SCL).......... 17
3.4 Multilevel Length-Based-Classified Index Table (MLIT)... 21
3.5 Draw aMILT............ 24
4 Dynamic Router Table Operations 26
4.1 Construction............ 26
v
4.2 Insertion............. 27
4.3 Search............ 28
4.4 Deletion............. 29
5 Experimental Results 31
5.1 Select the proper parameter α for MIST....... 31
5.2 Comparison with other data structures...... 34
6 Conclusion 41
Bibliography 42

Bibliography
[1] BGP Table obtained from http://bgp.potaroo.net/.
[2] M. Berger, “IP lookup with low memory requirement and fast update, in Proceedings
of IEEE High Performance Switching and Routing, pp. 287–291, Jun.
2003.
[3] Y. K. Chang and Y. C. Lin “A Fast and Memory Ecient Dynamic IP Lookup Algorithm
Based on B-Tree, in proceedings of the 23rd IEEE International Conference
on Advanced Information Networking and Applications, pp. 278–284, 2009.
[4] Y. K. Chang and Y. C. Lin, “Dynamic segment trees for ranges and prefixes,
IEEE Transactions on Computers, vol. 56, no. 6, pp. 769–784, Jun. 2007.
[5] Y. K. Chang, “Simple and fast IP lookups using binomial spanning trees, Computer
Communi- cations, vol. 28, no. 5, pp. 529–539, Mar. 2005.
[6] S. Dharmapurikar, P. Krishnamurthy and D. E. Taylor “Longest prefix matching
using bloom filters, IEEE/ACM Transactions on Networking, vol. 14, no.2, pp.
397–409, Apr. 2006.
[7] D. Comer, “Ubiquitous B-Tree, ACM Journal Computing Surveys, vol. 11, no.
2, pp. 121–137, Jun. 1979.
[8] W. Eatherton, G. Varghese, and Z. Dittia, “Tree bitmap: hardware/ software IP
lookup with incremental updates, in Proceedings of ACM SIGCOMM Computer
Communication Review, 34, 2, Apr. 2004.
[9] F. C. Kuo, Y. K. Chang, and C.C. Su, “A Memory-Efficient TCAM Coprocessor
for IPv4 IPv6 Routing Table Update, IEEE Transactions on Computers, vol. 63,
no. 9, pp. 2110–2121, Sept. 2014.
42
[10] S. Y. Hsieh, and Y. C. Yang, “A Classified Multisuffix Trie for IP Lookup and
Update, IEEE Transactions on Computers, vol. 61, no. 5, pp. 726–731, May.
2012.
[11] S. Y. Hsieh, Y. L. Huang, and Y. C. Yang, “Multi-Prefix Trie: a New Data Structure
for Designing Dynamic Router-Tables, IEEE Transactions on Computers,
vol. 60, no. 5, pp. 693–706, May 2011.
[12] B. Lampson, V. Srinivasan, and G. Varghese, “IP lookups using multiway and
multicolumn search, IEEE/ACM Transactions on Networking, vol. 7, no. 3, pp.
324–334, Jun. 1999.
[13] H. Lim, K. Lim, N. Lee and K. H. Park, “On Adding Bloom Filters to Longest
Prefix Matching Algorithms, IEEE Transactions on Computers, vol. 63, no. 2,
pp. 411–423 Feb. 2014.
[14] H. Lim, N. Lee, “Survey and Proposal on Binary Search Algorithms for Longest
Prefix Match, IEEE Communications Surveys ＆ Tutorials, vol. 14, no. 3, pp.
681–697, Jul. 2012.
[15] H. Lim, C. Yim and E. E. Swart, “Priority trie for IP address lookup, IEEE
Transactions on Computers, vol. 59, no. 6, pp. 784–794, Jun. 2010.
[16] H. Lim, W. Kim and B. Lee, “Binary Searches on Multiple Small Trees for IP
Address Lookup, IEEE comunications letters, vol. 9, no. 1, pp. 75–77, Jan. 2005.
[17] C. H. Lin, C. Y. Hsu, and S. Y. Hsieh, “A Multi-index Hybrid Trie for IP Lookup
and Updates, in IEEE Transactions on Parallel and Distributed Systems, vol. 25,
no. 10, pp. 2486–2498 Oct. 2014.
[18] H. Lu and S. Sahni, “A B-tree dynamic router-table design, IEEE Transactions
on Computers, vol. 54, no. 7, pp. 813–824, Jul. 2005.
[19] H. Lu and S. Sahni, “Enhanced interval trees for dynamic IP router-tables, IEEE
Transactions on Computers, vol. 53, no. 12, pp. 1615–1628, Dec. 2004.
[20] T. B. Mishra and S. Sahni “A Power Efficient TCAM Architecture for Forwarding
Tables, IEEE Computers and Communications, vol. 61, no. 1, pp. 224–229, Jul.
2009.
43
[21] S. Nilsson and G. Karlsson, “IP-address lookup using LC-trie, IEEE Journal on
selected Areas in Communications, vol. 17, no. 6, pp. 1083–1092, Jun. 1999.
[22] K. Pagiamtzis and A. Sheikholeslami, “Content-addressable memory (CAM) circuits
and architectures: a tutorial and survey, IEEE Journal of Solid-State Circuits,
vol. 41, no. 3, pp. 712–727, Mar. 2006.
[23] D. Pao, , Z. Lu , and Y. H. Poon, “IP address lookup using bit-shuffled trie,
Computer Communications, vol. 47, no. 1, pp. 51–64, July 2014.
[24] M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, “Survey and taxonomy of
IP address lookup algorithms, IEEE Network, vol. 15, pp. 8–23, Mar. 2001.
[25] S. Sahni and K. S. Kim, “An O(log n) dynamic router-table design, IEEE Transactions
on Com- puters, vol. 53, no. 3, pp. 351–363, Mar. 2004.
[26] S. Sahni and K. S. Kim, “Efficient construction of multibit tries for IP lookup,
IEEE/ACM Transactions on Networking, vol. 11, no. 3, pp. 650–662, 2003.
[27] D. Shah and P. Gupta, “Fast Updating Algorithms for TCAMs, IEEE Micro
archive, vol. 21, no 1, pp. 36–47, Jan 2001.
[28] V. Srinivasan and G. varghese, “Fast address lookups using controlled prefix expansion,
ACM Transactions on Computer Systems, vol. 17, no. 1, pp. 1–40, 1999.
[29] M. Waldvogely, G. Varghesez, J. Turnerz, and B. Plattner, “Scalable high-speed
prefix matching, ACM Journal Transactions on Computer Systems, vol. 19, no.
4, pp 440–482, Nov. 2001.
[30] Y. Wang, Y. Lin, S. Huang, G. Wang and R. Li, “Scalable high-speed prefix
matching, Information Technology Journal, vol. 10, no. 10, pp 1964–1970, 2011.
[31] P. R. Warkhede, S. Suri, and G. Varghese, “Multiway range tree: scalable IP
lookup with fast updates, Computer Network, vol. 44, no. 3, pp. 289–303, Feb.
2004.
[32] Lih-Chyau Wuu, Tzong-Jye Liu, and Kuo-Ming Chen, “A longest prefix first
search tree for IP lookup, Journal Computer Networks, vol. 51, no. 12, pp. 3354–
3367, Feb. 2007.
44
[33] C. Yim, B. Lee and H. Lim, “Efficient Binary Search for IP Address Lookup,
IEEE comunications letters, vol. 9, no. 7, pp. 652–654, Jul. 2005.