成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林東俊 Lin, Dung-Jiun
論文名稱：	動態路由表的設計與實作 Design and Implementation of Dynamic Routing Tables
指導教授：	張燕光 Chang, Yeim-Kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2005
畢業學年度：	93
語文別：	中文
論文頁數：	66
中文關鍵詞：	動態路由表、事先計算、路由位址查詢
外文關鍵詞：	IP address lookup, dynamic routing table, precomputation
相關次數：	點閱：115 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

　　在過去幾年中，許多具備高效能的路由位址查詢方式相繼被提出。這些方法大致上可被分為兩種類型：一種是透過事先計算的方式所建構的靜態路由表，另ㄧ種則是可支援動態路由表的方式。事先計算通常可以簡化路由位址查詢演算法所建立的資料結構而在查詢速度和記憶體需求上達到較佳的效能。然而其缺點便是當欲加入或刪除ㄧ筆路由資訊時，整個資料結構可能必須重新建立。這重建的過程便會大大嚴重的影響骨幹路由器路由更新的效能，因此那些可以以動態的方式來建立路由表的路由查詢方法是較合適的。

　　在本論文當中，我們發展了一個可支援動態路由表的MSPT資料結構。MSPT是利用路由表中所有最顯著的路由資訊所建立的一個二元搜尋平衡樹，而其餘非最顯著的路由資訊則分配至該二元平衡樹的節奌中。透過MSPT，對一個真實路由表所做的查詢、加入和刪除的運作皆可在O(log N)時間下完成，N為路由資訊的個數。與PBOB、MRT也支援動態路由表的方式以及數個採用事先計算的路由查詢演算法比較起來，MSPT具有比PBOB和MRT較佳的效能且在路由查詢速度和記憶體需求上也和那些以事先計算為基礎的路由查詢演算法相近。此外，我們所提出的方式也能簡單和成功的轉移至下ㄧ代的網際網路協定(IPv6)或較大的路由表上而得到不錯的效能。

　　In the last couple of years, various schemes for high-performance IP address lookups have been proposed. Those schemes can be broadly classified into two categories: the schemes that use precomputation to build static routing tables, and the schemes that build dynamic routing tables. The precomputation usually can simplify the entire data structure of the routing tables and thus improve the performance of the lookup speed and memory requirement. However, a disadvantage of the precomputation is that when a single prefix is added or deleted, the entire data structure may need to be rebuilt. Rebuilding the routing tables seriously affects the update performance of a backbone router. Thus, those schemes that can build the routing tables dynamically are suitable.

　　In this thesis, we develop a data structure called Most Specific Prefix Tree (MSPT) that is suitable for dynamic routing tables. MSPT is a balanced binary search tree which is constructed by the most specific prefixes that do not cover any other prefixes in the routing table. The rest of prefixes (non-most specific prefixes) are allocated to the enclosure set of each most specific prefix node in MSPT. Based on MSPT, the search, insertion, and deletion operations can be performed in O(log N) time, where N is the number of prefixes in the routing table. Comparing with the schemes that also build dynamic routing tables such as PBOB (prefix binary tree on binary tree) and MRT (multiway range tree), and several precomputation-based schemes, MSPT gets better performance than PBOB and MRT and the performance of lookup speed and memory requirement is near to those precomputation-based schemes. Moreover, our proposed scheme also scales well to IPv6 and large routing tables.

Chapter 1 Introduction..........................................1
1 Motivation..................................................1
2 Overview of the Thesis......................................5

Chapter 2 Background............................................6
1 The Challenges to IP Address Lookup.........................6
2 IPv6 Addressing Architecture................................7
2.1 IPv6 Address Syntax.......................................7
2.2 Type of IPv6 Address......................................8
2.2.1 Unicast Address.........................................8
2.2.2 Anycast Address.........................................9
2.2.3 Multicast Address......................................10

Chapter 3 Review of the Previous Works.........................11
1 Trie base scheme...........................................11
1.1 1-bit ( Binary ) trie....................................11
1.2 Patricia Trie............................................12
1.3 Multibit Trie............................................13
1.4 Level Compressed Trie....................................15
2 End-Point Array Scheme.....................................17
2.1 IP Lookups Using Multiway and Multicolumn Search.........17
2.2 An Efficient IP Routing Lookup by Using Routing Interval.18
3 Sets of Equal-Length Prefixes Scheme.......................19
3.1 Scalable high-speed IP routing lookups...................19
4 Search Tree Base Scheme....................................20
4.1 Enhanced Interval Tree for Dynamic IP Router-Tables......20
4.2 An O(log n) Dynamic Router-Table Design..................21
4.3 Multiway Range Tree......................................22
5 Hybrid Base Scheme.........................................24
5.1 Lulea compressed trie....................................24
5.2 Huang’s Compact Algorithms..............................24
6 Summary....................................................26

Chapter 4 Propose IP Lookup Scheme.............................29
1 Preliminaries..............................................29
2 Most Specific Prefix Tree – MSPT..........................30
2.1 Most Specific Prefix Tree................................30
2.2 Data Structure for MSPT..................................32
3 Finding the Longest Prefix Match...........................35
4 Update.....................................................38
4.1 Inserting a Prefix.......................................38
4.2 Deleting a Prefix........................................39
4.3 Rotations Problem........................................43
5 Enhance Our IP Address Lookup Scheme.......................47
6 Migrate to IPv6............................................49

Chapter 5 Performance..........................................51
1 Simulation Environment.....................................51
2 Simulation Result for IPv4.................................51
3 Simulation Result for IPv6.................................60

Chapter 6 Conclusion...........................................64
References.....................................................65

                                    

[1] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
[2] A. Brodnik, S. Carlsson, M. Degermark, S. Pink, "Small Forwarding Tables for Fast Routing Lookups," ACM SIGCOMM, pp. 3-14, Sept. 1997.
[3] Y. K. Chang, "Fast Binary and Multiway Prefix Searches for Packet Forwarding," Submitted for publication.
[4] S. Deering and R. Hinden, RFC 2460 Internet Protocol, Version 6 (IPv6) Specification.
[5] A. Durand and C. Huitema, RFC 3194 The H-Density Ratio for Address Assignment Efficiency An Update on the H ratio.
[6] V. Fuller, T. Li, J. Yu and K. Varadhan, "Classless inter-domain routing (CIDR): an address assignment and aggregation strategy," RFC 1519, Sept. 1993.
[7] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of Data Structure in C++. New York: W.H. Freeman, 1995.
[8] N. F. Huang, S. M. Zhao, J. Y. Pan, and C. A. Su, "A Fast IP Routing Lookup Scheme for Gigabit Switching Routers," in Proc. INFOCOM, pp. 1429-1436, Mar. 1999.
[9] IPv6 Forum, http://www.ipv6forum.com.
[10] K. Kim, S Sahni, "An O(logn) Dynamic Router-Table Design," IEEE Transactions on Computers, pp. 351-363, Mar. 2004.
[11] B. Lampson, V. Srinivasan and G. Varghese, "IP Lookups Using Multiway and Multicolumn Search," IEEE/ACM Transactions on Networking, Vol. 3, No. 3, pp. 324-334, Jun.1999.
[12] H. Lu, S. Sahni, "Enhanced Interval Tree for Dynamic IP Router-Tables," IEEE Transactions on Computers, pp. 1615-1628, Dec. 2004.
[13] X. Meng, Z. Xu, B. Zhang, G.. Huston, S. Lu, L. Zhang, "IPv4 Address Allocation and the BGP Routing Table Evolution," ACM SIGCOMM, pp. 71-80, Jan. 2005.
[14] D. Meyer, "University of Oregon Route Views Archive Project", at http://archive.routeviews.org/.
[15] S. Nilsson and G. Karlsson "IP-Address Lookup Using LC-trie," IEEE Journal on selected Areas in Communications, 17(6):1083-1092, June 1999.
[16] K. Sklower, "A Tree-based Packet Routing Table for Berkeley Unix," Proc. Winter Usenix Conf, pp. 93-99, 1991.
[17] M. A. Ruiz-Sanchez, Ernst W. Biersack, and Walid Dabbous, "Survey and Taxonomy of IP Address Lookup Algorithms," IEEE Network Magazine, 15(2):8--23, March/April 2001.
[18] M. Waldvogel, G. Varghese, J. Turner and B. Plattner, "Scalable High-Speed IP Routing Lookups," ACM SIGCOMM, pp. 25-36, Sept. 1997.
[19] P. C. Wang, C. T. Chan and Y. C. Chen, "An Efficient IP Routing Lookup by Using Routing Interval," Journal of Communication and Networks, pp. 374-382, Mar. 2001.
[20] M. Wang, S. Deering, T. Hain, L. Dunn, "Non-random Generator for IPv6 Tables," in Proc. 12th Annual IEEE Symposium of High Performance Interconnects, pp. 35-40, Aug. 2004.
[21] P. Warkhede, S. Suri, G.. Varghese, "Multiway Range Trees: Scalable IP Lookup with Fast Updates," The International Journal of Computer and Telecommunications Networking, pp. 289-303, Feb. 2004.

校內：2006-07-05公開
校外：2006-07-05公開

簡易檢索 / 詳目顯示

相關論文