跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/27 10:37
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:黃怡玲
研究生(外文):Yi-Ling Huang
論文名稱:使用SuffixB-Tree之動態路由表設計與實作
論文名稱(外文):Design and Implementation of a New Dynamic Router-table Using Suffix B-Tree
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:68
中文關鍵詞:位址查詢動態路由表格最長筆對前綴無類別領域路由
外文關鍵詞:Dynamic router tablesIP address lookupCIDRlongest matching prefix
相關次數:
  • 被引用被引用:0
  • 點閱點閱:110
  • 評分評分:
  • 下載下載:7
  • 收藏至我的研究室書目清單書目收藏:0
位址查詢會影響一個進入封包決定出口的速度,因此位址查詢是路由表格設計的一個重要角色,由於網路的千變萬化,路由表格必須是動態支援快速地新增與刪除,在這篇論文中,我們為了動態路由表格,設計出一個快速位址查詢與更新的資料結構,命名為Suffix B-tree,我們的資料結構Suffix B-tree特色是一個結點可以儲存不只一個前綴,此機制可以減少記憶體連結的次數,並且在位址查詢時,一個結點可以搜尋多個前綴,除此之外,當找尋最長前綴筆對時,可能不需要筆對到葉子,即可找到最佳的答案;當執行更新時,不需要重新建立路由表格外,路由表格的建立時間快速,我們所提出的資料結構Suffix B-tree,不但運算速度快,而且記憶體的連結次數少,位址查訊與位址新增的運算時間複雜度為O((2^m-1)
(floor(W/m))),W是位址的長度,m是步幅,而位址刪除的運算時間複雜度為O((2^m)(floor(W/m))),此外,以Suffix B-tree為基礎,我們也提出了一個延伸的資料結構,命名為Index Suffix B-tree,更能加快運算。
IP lookup effects 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
O((2^m-1)(floor(W/m))), where W is the length of IP address and m is stride. The deletion takes O((2^m)(floor(W/m))). Furthermore, based on Suffix B-Tree, we also introduce another extended structure called Index Suffix B-tree which outperforms Suffix B-tree.
Abstract(in Chinese) i
Abstract(in English) ii
Acknowledge iii
Contents iv
List of Tables vi
List of Figures vii
1 Introduction 1
1.1 Motivation 1
1.2 Overview of the Thesis 4
2 Related Work 5
2.1 Trie Base Scheme 5
2.1.1 1-bit (Binary) Trie 6
2.1.2 Patricia Trie 7
2.1.3 LC-trie 8
2.1.4 Modified LC-trie 10
2.1.5 Multibit Trie 12
2.1.6 Prefix Tree 14
2.2 Search Tree Base Scheme 15
2.2.1 Multiway Range Tree: Scalable IP Lookup with Fast Updates 15
2.2.2 An O(log n) Dynamic Router-table Design 16
2.2.3 Enhanced Interval Trees for Dynamic IP Router-tables 18
2.2.4 A B-tree Dynamic Router-table Design 20
3 Dynamic router-table based on suffix B-tree 22
3.1 The suffix B-tree (SBT) 22
3.2 Lookup 25
3.2.1 Creating an empty m-SBT 28
3.3 Insertion 29
3.4 Deletion 36
3.5 Index Suffix B-Tree 44
4 Experimental Results 46
4.1 Selecting m for SBT and ISBT 47
4.2 Comparison of Various Data Structures 59
5 Concluding Remarks 64
[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, June 2003.
[3] Y. K. Chang, "Simple and fast IP lookups using binomial spanning trees", Computer Communications, vol. 28, no. 5, pp. 529-539, Mar. 2005.
[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, June 2007.
[5] P. Crescenzi, L. Dardini, and R. Grossi, "IP Address Lookup Made Fast and Simple," in Proceedings of Seventh Ann. European Symp. Algorithms, Technical Report TR-99-01, Univ. of Pisa, 1999.
[6] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, "Small forwarding tables for fast routing lookups," in Proceedings of ACM SIGCOMM, pp. 3-14, Sep. 1997.
[7] S. Deering and R. Hinden, "Internet protocol version 6 (IPv6) specification", RFC 1883, Dec. 1995.
[8] S. Dharmapurikar, P. Krishnamurthy and D. E. Taylor,"Longest prefix matching using bloom filters", IEEE/ACM Transactions Networking, vol. 14, no. 2, pp.
397-409, Apr. 2006
[9] W. Doeringer, G. Karjoth, and M. Nassehi, "Routing on longest-matching prefixes," IEEE/ACM Transactions Networking, vol. 4, no. 1, pp. 86-97, Feb. 1996.
[10] V. Fuller, T. Li, J. Yu and K.Varadhan, "Classless inter-domain routing (CIDR): an address assignment and aggregation strategy," RFC 1519, Sep. 1993.
[11] N. F. Huang and S. M. Zhao, "A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers," IEEE Journal on Selected Areas
in Communications, vol. 17, no. 6, pp. 1093-1104, June 1999.
[12] H. Lu, K. S. Kim and S. Sahni, "Prefix and interval-partitioned dynamic IP router-tables" IEEE Transactions on Computers, vol. 54, no. 5, pp. 545-557, May 2005.
[13] J. H. Mun, H. Lim and C. Yim, "Binary search on prefix lengths for IP address lookup", IEEE Communications Letters, vol. 10, no. 6, pp. 492-494, June 2006.
[14] S. Nilsson and G. Karlsson, "Fast address lookup for Internet routers," IEEE Broadband Comm., pp. 11-22, 1998.
[15] 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, June 1999.
[16] J. Postel, "Internet protocol darpa internet program protocol specification," RFC791, Sep. 1981.
[17] V.C. Ravikumar, R. Mahapatra, J.C. Liu, "Modified LC-trie based efficient routing lookup," in Proceedings of the 10th IEEE International Symp. on Modeling,
Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), pp. 177-182, Oct. 2002.
[18] M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, "Survey and taxonomy of IP address lookup algorithms," IEEE Network, vol. 15, no. 2, pp. 8-23, Mar./Apr. 2001.
[19] S. Sahni and K. Kim, "Efficient construction of fixed-stride multibit tries for IP lookup," in Proceedings of the 8th IEEE Workshop on Future Trends of Distributed
Computing Systems, pp. 178-184, 2001.
[20] S.Sahni and K. Kim, "Efficient construction of variable-stride multibit tries for IP lookup", in Proceedings of IEEE Symp. Applications and the Internet (SAINT), pp. 220-227, 2002.
[21] S.Sahni and K. Kim, "An O(logn) dynamic router-table design", IEEE Transactions on Computers, vol. 53, no. 3, pp. 351-363, Mar. 2004.
[22] S. Sahni, K. Kim, and H. Lu, "Data structures for one- dimensional packet classification using most-specific-rule matching," International Journal of Foundations
of Computer Science, vol. 14, no. 3, pp. 337-358, 2003.
[23] S.Sahni and H.Lu, "Enhanced interval trees for dynamic IP router-tables", IEEE Transactions on Computers, vol. 53, no. 12, pp. 1615-1628, Dec. 2004
[24] S.Sahni and H. Lu, "A B-tree dynamic router-table design", IEEE Transactions on Computers, vol. 54, no. 7, pp. 813-824, July 2005.
[25] K. Sklower, "A tree-based packet routing table for Berkeley unix," in Proceedings of Winter Usenix Conf, pp. 93-99, 1991.
[26] S. Soh, L. Hiryanto and S. Rai,"Efficient prefix updates for IP router using lexicographic ordering and updatable address set," IEEE Transactions on Computers,
vol. 57, no. 1, pp. 110-125, Jan. 2008.
[27] V. Srinivasan and G.Varghese, "Faster IP lookups using controlled prefix expansion," ACM Transactions on Computer Systems, pp. 1-40, Feb. 1999.
[28] 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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top