成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李紹楷 Li, Shuao-Kai
論文名稱：	使用二元完美碼之有效率的路由查詢演算法 Efficient Routing Lookup Algorithms Using Binary Perfect Codes
指導教授：	張燕光 Chang, Yeim-Kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2006
畢業學年度：	94
語文別：	英文
論文頁數：	100
中文關鍵詞：	戈萊碼、BGP更新、事先計算、動態路由表、路由位址查詢、漢明碼、二元完美碼、二項展開樹
外文關鍵詞：	dynamic routing table, precomputation, BGP update, binomial spanning tree, Hamming code, binary perfect codes, Golay code, IP address lookup
相關次數：	點閱：187 下載：1
分享至:	分享至facebook 分享至twitter

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

高效能的路由器需要有效率的路由位址查詢演算法來處理每秒百萬個封包。各式各樣的資料結構被應用在以軟體為基礎的路由器。根據這些資料結構，我們可以將路由位址查詢法區分成兩大類：以過去幾年中，許多具備高效能的路由位址查詢方式相繼被提出。這些方法大致上可被分為兩種類型：一種是以事先計算為基礎的方式來建構的靜態路由表，另ㄧ種則是可支援動態路由表的方式。事先計算的主要想法是減少記憶體需求以及加快查詢速度。因此，以事先計算為基礎的方法可以減化資料結構來縮短查詢時間，但是當插入一筆路由資訊時，以事先計算為基礎的方法通常要重建整個資料結構。重建路由表會嚴重影響核心路由器。就目前而言，網路每秒會有上百個BGP的更新。因此擁有快速更新的路由位址查詢演算法是期望能避免網路的不穩定性。因此，不需事先計算為基礎的方法更適用於現今的路由器。
在本論文當中，我們發展了一個以二項展開樹以及三種二元完美碼((7,4)漢明碼、(15,11)漢明碼以及(23,12)戈萊碼)為基礎且可支援動態路由表的PCT資料結構。根據此三種二元完美碼所能解碼的資料位元數，我們建立Hamming7樹, Hamming15樹以及Golay樹共三個獨立的資料結構。當找尋最長前綴筆對時，我們依序搜尋這三棵樹。當用PCT來做路由位址查詢時，其搜尋、插入以及刪除所需的記憶體參照數趨近於五。與PBOB、MRT也支援動態路由表的方式以及數個採用事先計算的路由查詢演算法比較起來，PCT具有比PBOB和MRT較佳的效能在路由查詢速度和記憶體需求上。此外，我們所提出的方式也能簡單和成功的轉移至下ㄧ代的網際網路協定(IPv6)或較大的路由表上而得到不錯的效能。
除了PCT之外，我們也利用二元完美碼發展出幾個名為SPL、LPL以及MPLPL的平行路由查詢方法。在這些平行路由查詢系統中，Hamming7樹, Hamming15樹以及Golay樹被建立成搜尋單元。因此我們可以平行的搜尋並且強化路由查詢的效能

High performance Internet routers require an efficient IP address lookup algorithm to forward millions of packets per second. Various kinds of data structures are normally used in software-based routers. According to those data structures, we can classify the IP lookup schemes into two categories: the pre-computation based schemes which build static routing tables and the non pre-computation based schemes which build dynamic routing tables. The main idea of pre-computation schemes is to improve lookup speed and reduce memory requirement. Hence, they can simplify the data structure of routing tables to shorten the search time but often need to rebuild whole data structure when inserting a single prefix. Rebuilding the routing tables seriously affects the update performance of a backbone router. Currently, the Internet has a peak of a few hundred BGP updates per second. Thus, the address lookup schemes with fast update time are desirable to avoid routing instabilities. Therefore, non pre-computation based schemes are more suitable for modern routers.
In this thesis, we propose a new non pre-computation scheme called Perfect Code Tree (PCT) based on binomial spanning trees [25] and three kinds of binary perfect codes which are (7, 4) Hamming code, (15, 11) Hamming code and (23, 12) Golay code. In light of data bit length which binary perfect codes can decode, we build three independent data structures which are Hamming7 tree, Hamming15 tree and Golay tree. When finding the longest prefix match, we search these three trees in the order of Golay tree, Hamming15 tree and Hamming7 tree. Based on PCT, the number of memory access of search, insertion, and deletion operations is almost equal to 5 in the average case. Comparing with the schemes building dynamic routing tables such as PBOB (prefix binary tree on binary tree) and MRT (multiway range tree), PCT gets better performance than PBOB and MRT, and memory requirement of PCT is near to those pre-computation based schemes. Moreover, PCT also scales well to IPv6 and large routing tables.
Besides PCT, we also propose several parallel lookup schemes named Simple Parallel Lookup (SPL), Length-based Parallel Lookup (LPL), Multi-Packet and Length-based Parallel Lookup (MPLPL) by using binary perfect codes. In these parallel lookup systems, Hamming7 tree, Hamming15 tree and Golay tree are built as search units. Thus, we can do the search operation on search units in parallel to improve the performance of lookup speed.

Chapter 1 Introduction	1
1 MOTIVATION	1
2 OVERVIEW OF THE THESIS	6
Chapter 2 Background	7
1 THE CHALLENGES TO IP ADDRESS LOOKUP	7
2 IPV6 ADDRESSING ARCHITECTURE	8
2.1 IPv6 Address Syntax	8
2.2 Type of IPv6 Address	9
2.2.1 Unicast Address	9
2.2.2 Anycast Address	10
2.2.3 Multicast Address	11
Chapter 3 Review of the Previous Works	12
1 TRIE BASE SCHEME	12
1.1 1-bit ( Binary ) trie	12
1.2 Patricia Trie	13
1.3 Multibit Trie	14
1.4 Level Compressed Trie	16
2 END-POINT ARRAY SCHEME	18
2.1 IP Lookups Using Multiway and Multicolumn Search	18
2.2 An Efficient IP Routing Lookup by Using Routing Interval	19
3 SETS OF EQUAL-LENGTH PREFIXES SCHEME	20
3.1 Scalable high-speed IP routing lookups	20
4 SEARCH TREE BASE SCHEME	21
4.1 Enhanced Interval Tree for Dynamic IP Router-Tables	21
4.2 An O(log n) Dynamic Router-Table Design	22
4.3 Multiway Range Tree	24
5 HYBRID BASE SCHEME	25
5.1 Lulea compressed trie	25
5.2 Huang’s Compact Algorithms	26
6 SUMMARY	28
Chapter 4 Binary Perfect Codes	31
1 CODING THEORY AND LINEAR BLOCK CODE	31
1.1 Coding Theory	31
1.2 Linear Block Code	32
2 ENCODING AND DECODING OF LINEAR BLOCK CODE	34
2.1 Encoding steps	35
2.2 Decoding steps	36
3 UTILIZING BINARY PERFECT CODES	38
3.1 Error-detecting capability of a block code	38
3.2 Error-correcting capability of a block code	39
3.3 Binary perfect codes	40
Chapter 5 Binomial Spanning Tree	42
1 BRIEF INTRODUCTION OF BINOMIAL SPANNING TREE	42
2 PRELIMINARIES	43
3 IP LOOKUP USING BINOMIAL SPANNING TREE	45
3.1 Use binomial spanning tree for IP lookup	45
3.2 Insertion of binomial spanning tree	46
3.3 Search of binomial spanning tree	48
4 BINOMIAL SPANNING TREE USED IN OUR LOOKUP SCHEME	49
Chapter 6 Our proposed IP lookup scheme	51
1 ORIGIN OF OUR PROPOSED IP LOOKUP SCHEME	51
2 SEQUENTIAL VERSION OF OUR PROPOSED IP LOOKUP SCHEME	53
2.1 Insertion of perfect code tree	53
2.2 Deletion of perfect code tree	60
2.3 Search of perfect code tree	62
2.4 Improvement in our sequential scheme	64
3 PARALLEL VERSION OF OUR PROPOSED IP LOOKUP SCHEME	67
3.1 Basic parallel lookup architecture	69
3.2 Improvement on our parallel lookup architecture	71
3.2.1 The Lookup Mechanism	73
3.2.2 The Conflict resolver	74
3.3 Design of decoder	75
4 MIGRATE TO IPV6	76
Chapter 7 Performance Evaluation	78
1 SIMULATION ENVIRONMENT	78
2 SIMULATION RESULT OF OUR SEQUENTIAL SCHEME	78
2.1 Total Memory Requirement	80
2.2 Search Time	83
2.3 Update Time	86
3 SIMULATION RESULT OF OUR PARALLEL SCHEME	89
3.1 Memory Requirements	89
3.2 Search Time	91
3.3 Update Time	93
3.4 The number of Memory access	95
Chapter 8 Conclusion	97
References …………………………….…………………………………………………. 98

                                    

[1] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
[2] D. Meyer, "University of Oregon Route Views Archive Project", at http://archive.routeviews.org/
[3] A. Brodnik, S. Carlsson, M. Degermark, S. Pink, "Small Forwarding Tables for Fast Routing Lookups," ACM SIGCOMM, pp. 3-14, Sept. 1997.
[4] Y. K. Chang, "Fast Binary and Multiway Prefix Searches for Packet Forwarding," Submitted for publication.
[5] S. Deering and R. Hinden, RFC 2460 Internet Protocol, Version 6 (IPv6) Specification.
[6] A. Durand and C. Huitema, RFC 3194 The H-Density Ratio for Address Assignment Efficiency An Update on the H ratio.
[7] V. Fuller, T. Li, J. Yu and K. Varadhan, "Classless inter-domain routing (CIDR): an address assignment and aggregation strategy," RFC 1519, Sept. 1993.
[8] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of Data Structure in C++. New York: W.H. Freeman, 1995.
[9] 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.
[10] IPv6 Forum, http://www.ipv6forum.com.
[11] K. Kim, S Sahni, "An O(logn) Dynamic Router-Table Design," IEEE Transactions on Computers, pp. 351-363, Mar. 2004.
[12] 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.
[13] H. Lu, S. Sahni, "Enhanced Interval Tree for Dynamic IP Router-Tables," IEEE Transactions on Computers, pp. 1615-1628, Dec. 2004.
[14] 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.
[15] D. Meyer, "University of Oregon Route Views Archive Project", at http://archive.routeviews.org/.
[16] S. Nilsson and G. Karlsson "IP-Address Lookup Using LC-trie," IEEE Journal on selected Areas in Communications, 17(6):1083-1092, June 1999.
[17] K. Sklower, "A Tree-based Packet Routing Table for Berkeley Unix," Proc. Winter Usenix Conf, pp. 93-99, 1991.
[18] 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.
[19] M. Waldvogel, G. Varghese, J. Turner and B. Plattner, "Scalable High-Speed IP Routing Lookups," ACM SIGCOMM, pp. 25-36, Sept. 1997.
[20] 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.
[21] 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.
[22] 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.
[23] Yeim-Kuan Chang, "Simple and fast IP lookups using binomial spanning trees,” Computer Communications, 1-11, February 2005.
[24] S. Lin and D.J. Costello, Error Control Coding Fundamentals and Applications. Englewood Cliffs, N.J.: Prentice Hall, 1983.
[25] S.L. Johnsson and C.-T. Ho “Optimum Broadcasting and Personalized Communication in Hypercubes”, IEEE Transactions on Computers Vol. 38, No. 9, Sept. 1989.
[26] http://www-03.ibm.com/chips/products/asics/products/ememory.html ,2003
[27] http://netflow.internet2.edu, “Internet2 NetFlow Statistics,” 2004

校內：2008-08-09公開
校外：2010-08-09公開

簡易檢索 / 詳目顯示

相關論文