跳到主要內容

臺灣博碩士論文加值系統

(3.236.124.56) 您好!臺灣時間:2021/07/31 04:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:許家胤
研究生(外文):Chia-YinHsu
論文名稱:使用多重索引混和鍵樹實作路由表查詢與更新
論文名稱(外文):Multi-Index Hybrid Trie for IP lookup and Updates
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:61
中文關鍵詞:無類別領域路由動態路由表格網路位址查詢最長比對前綴
外文關鍵詞:Classless inter domain routingdynamic router tablesIP address lookuplongest matching prefix
相關次數:
  • 被引用被引用:0
  • 點閱點閱:111
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
高效能路由器必須能夠提供高速的網路位址查詢。在這篇論文中,我們提出
了一個動態的路由表資料結構,我們稱之為 Multi-Index Hybrid Trie (MIHT)。藉由賦予每筆前綴一個鍵值,使得我們能夠在平衡的搜尋樹上有效率地實施網路位址查詢。此外,由於樹高和需被比對的前綴數量同時減少了,使得動態路由表的各項運作變得更有效率。為了減少對記憶體容量大小的需求,我們只儲存後綴在我們的MIHT中而非整個的前綴字串。我們的實驗使用實際的網際網路通訊協定第四版(IPv4)的路由資料庫。透過實驗結果顯示,我們所提出的資料結構不但提供更小的記憶體需求,且在路由表的查詢以及更新運作的效能表現良好。在我們的實驗中所使用的四個前綴資料庫是AS1221、AS4637、AS6447和AS65000,它們分別有407,067、219,581、417,995和406,973筆前綴資料。
High performance routers require high-speed IP address lookup to achieve wire speed packet forwarding. In this thesis, a new data structure of dynamic router table is proposed for IP lookup and updates, called Multi-Index Hybrid Trie (MIHT). By associating each prefix with a key value, we can perform an IP lookup operation efficiently in a balanced search tree. Furthermore, because the tree height and the number of prefixes that need to be compared is reduced, the dynamic router-table operations can also be performed efficiently. To reduce the memory requirement, for each prefix we store its corresponding suffix in a node of MIHT instead of storing a full binary string. Experiments using real IPv4 routing databases indicate that, the proposed data structure is e±cient in memory usage and performs well in terms of lookup, insert and delete operations. We report the results of experiments conducted to compare the proposed data structure with other structures using the benchmark IPv4 prefix databases AS1221, AS4637, AS6447, and AS65000 with 407,067, 219,581, 417,995, and 406,973 prefixes, respectively.
1 Introduction 1
2 Related works 6
2.1 Binary Trie . . . . . . . . . . . . . . . . . . . . . .8
2.2 Patricia Trie . . . . . . . . . . . . . . . . . . . . .9
2.3 Multibit Trie . . . . . . . . . . . . . . . . . . . . 10
2.4 LC-Trie . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Pre¯x Tree . . . . . . . . . . . . . . . . . . . . . .14
2.6 Priority Trie . . . . . . . . . . . . . . . . . . . . 16
2.7 Dynamic Tree Bitmap . . . . . . . . . . . . . . . . . 18
2.8 Multi-Pre¯x Trie . . . . . . . . . . . . . . . . . . .21
3 The Proposed Data Structure 23
3.1 Priority Tries . . . . . . . . . . . . . . . . . . . .23
3.2 Multi-Index Hybrid Tries . . . . . . . . . . . . . . .25
4 Dynamic router-table operations 29
4.1 Construction . . . . . . . . . . . . . . . . . . . . .29
4.2 Insertion operation . . . . . . . . . . . . . . . . . 29
4.3 Lookup operation . . . . . . . . . . . . . . . . . . .34
4.4 Deletion operation . . . . . . . . . . . . . . . . . .37
5 Partitioned Multi-Index Hybrid Trie 43
6 Experimental Results 45
6.1 Selecting k and m for MIHT and PMIHT . . . . . . . . .46
6.2 Comparison with other data structures . . . . . . . . 51
7 Conclusion 56
Bibliography 58
[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 Fast binary and multiway pre¯x searches for packet forwarding, in Computer Networks, vol. 51, no. 3, pp. 588{605, Feb. 2007.
[4] Y. K. Chang and Y. C. Lin, Dynamic segment trees for ranges and pre¯xes, 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 Communications, vol. 28, no. 5, pp. 529{539, Mar. 2005.
[6] Y. K. Chang and Y. C. Lin A Fast and Memory E±cient 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.
[7] Y. K. Chang, Y. C. Lin, and K. Y. Ho Update-aware Controlled Pre¯x Expansion for Fast IP Lookups, in Proceedings of International Conference on High
Performance Switching and Routing, pp. 1{6, 2009.
[8] Y. K. Chang, Y. C. Lin, and C. C. Su, Dynamic multiway segment tree for IP lookups and the fast pipelined search engine, IEEE Transactions on Computers, vol. 59, no. 4, pp. 492{506, Apr. 2010.
[9] S. Deering and R. Hinden, Internet protocol version 6 (IPv6) speci¯cation, RFC 1883, Dec. 1995.
[10] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, Small forwarding tables for fast routing lookups, in Proceedings of ACM SIGCOMM Computer Communication Review, pp. 3-14, 1997.
[11] 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.
[12] V. Fuller, T. Li, J. Yu, and K. Varadhan, Classless inter-domain routing (CIDR): an address assignment and aggregation strategy, RFC 1519, Sep. 1993.
[13] S. Y. Hsieh, Y. L. Huang, Y. C. Yang, Multi-Pre¯x Trie: a New Data Structure for Designing Dynamic Router-Tables, IEEE Transactions on Computers, 09
Junary 2010. IEEE computer Society Digital Library. IEEE Computer Society, http://doi.ieeecomputersociety.org/10.1109/TC.2010.133i.
[14] S. Y. Hsieh, Y. C. Yang, A Classi¯ed Multisu±x Trie for IP Lookup and Update, IEEE Transactions on Computers, vol. 61, no. 5, pp. 726{731, May. 2012.
[15] 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.
[16] H. Lim, W. Kim and B. Lee, Binary Search in a Balanced Tree for IP Address Lookup, Proceedings of IEEE workshop high performance switching and routing, pp. 490{494, 2005.
[17] 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.
[18] 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.
[19] H. Lu, K. S. Kim, and S. Sahni, Pre¯x and interval-partitioned dynamic IP router-tables, IEEE Transactions on Computers, vol. 54, no. 5, pp. 545{557, May 2005.
[20] 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.
[21] 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.
[22] 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.
[23] J. Postel, Internet protocol darpa internet program protocol speci¯cation, RFC791, Sep. 1981.
[24] V. C. Ravikumar, R. Mahapatra, and J. C. Liu, Modi¯ed LC-trie based e±cient routing lookup, in Proceedings of the 10th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems
(MASCOTS), pp. 177{182, Oct. 2002.
[25] 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, 2001.
[26] S. Sahni and K. S. Kim, An O(log n) dynamic router-table design, IEEE Transactions on Computers, vol. 53, no. 3, pp. 351{363, Mar. 2004.
[27] S. Sahni and K. S. Kim, E±cient construction of multibit tries for IP lookup, IEEE/ACM Transactions on Networking, vol. 11, no. 3, pp. 650{662, 2003.
[28] S. Sahni and H. Lu, Dynamic tree bitmap for IP lookup and update, in Proceedings of the Sixth International Conference on Networking, pp. 79{84, 2007.
[29] K. Sklower, A tree-based packet routing table for Berkeley unix, in Proceedings of Winter Usenix Conference, pp. 93{99, 1991.
[30] V. Srinivasan and G. varghese, Fast address lookups using controlled pre¯x expansion, ACM Transactions on Computer Systems, vol. 17, no. 1, pp. 1-40, 1999.
[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] C. Yim, B. Lee and H. Lim, E±cient Binary Search for IP Address Lookup, IEEE comunications letters, vol. 9, no. 7, pp. 652{654, Jul. 2005.
[33] N. Yazdani and P. S. Min, Fast and Scalable schemes for the IP address Lookup Problem, Proceedings of IEEE workshop high performance switching and routing, pp. 83{92, 2000.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top