成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	林勇傑 Lin, Yung-Chieh
論文名稱：	以區段樹為基礎之動態路由查詢演算法 Dynamic Routing Lookup Algorithms Based on Segment Trees
指導教授：	張燕光 Chang, Yeim-Kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2005
畢業學年度：	93
語文別：	英文
論文頁數：	148
中文關鍵詞：	網際網路位址查詢、動態路由表、最長前綴比對、區段樹、紅黑樹、B樹
外文關鍵詞：	B-trees, red-black trees, segment trees, longest-prefix matching, dynamic routing table, IP address lookup
相關次數：	點閱：108 下載：1
分享至:	分享至facebook 分享至twitter

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

　　在最近幾年當中，網際網路位址(路由)查詢已經受到廣泛的注意，許多高效能的路由查詢演算法相繼被提出。這些演算法大致可被分為兩類︰ㄧ類是透過「事先計算」來加快路由查詢的速度及減低記憶體的需求。這類的演算法通常是禁止路由表做更新的；另一類則是強調能有效率地支援動態路由表更新。儘管「事先計算」可以簡化由路由查詢演算法所建立的資料結構，因而在查詢速度及記憶體需求上有較佳的效能。然而，當欲加入或刪除一筆路由資訊時，整個資料結構可能因此必須重新建立。另ㄧ方面，由於骨幹網路會因不同的原因而有多筆的路由更新[12]。因此，可以支援快速更新的路由查詢演算法是有必要的。

　　在本論文中，我們著重在開發新的資料結構以便能有效地支援動態路由更新。我們以segment trees[1]為基礎，提出兩個動態路由查詢演算法，第一個稱為DST (Dynamic Segment Tree) 另一個則稱為MDST (Multiway Dynamic Segment Tree)。DST是一棵以平衡二元搜尋樹為架構的segment tree而MDST則是一棵以B-trees為架構的segment tree。對一個有n個路由資訊的動態路由表而言，藉由使用我們提出的資料結構，此動態路由表的三種運算「插入」、「刪除」及「搜尋」皆可在O(logn)時間內完成。且每一筆路由資訊，在每一樹的階層中，只會儲存在常數個節點內。實驗數據指出我們的MDST在各方面都比其他兩個一樣也是以B-tree為架構的資料結構PIBT[17]和MRT[32]擁有更好的效能。而DST則是在路由查詢速度上遠勝過ㄧ個以更新見長的資料結構PBOB[16]。

　The problem of IP address lookup has received much attention recently and several high performance algorithms and data structures have been proposed. Current IP lookup algorithms can be broadly classified into two categories: those focus on improving the lookup speeds and reducing the memory requirement by using precomputation (these schemes usually prohibit doing updates), and those can support the dynamic update without any precomputation. Although precomputation can simplify the data structures built by routing lookup algorithms and thus improve the performance of the lookup speed and memory requirement, the entire data structure may need to be rebuilt when a single prefix is added or deleted. Besides, since instabilities in the backbone protocols [12] can lead to rapid insertion and deletion of prefixes, algorithms that can support fast updates are desirable.

　In this thesis, we focus on efficient data structures that can support the dynamic update. We propose two data structures, which are called the DST (Dynamic Segment Tree) and MDST (Multiway Dynamic Segment Tree) respectively, based on segment trees for dynamic routing tables. The DST is a balanced binary search tree structure while the MDST is a B-tree structure. For a routing table of n prefixes, all dynamic routing table operations (query, insertion, and deletion) can be accomplished in O(logn) time and each prefix is stored in O(1) nodes per tree level both for our proposed data structures. Experiments using five real IPv4 routing tables indicate that, our proposed MDST outperforms the other two B-tree structural schemes PIBT [17] and MRT [32] in all aspects, and the query operation of our DST is considerably faster than a fast update data structure PBOB [16].

Chapter 1 Introduction	1
1 The need and importance of fast IP lookup algorithm with fast update	1
2 Classless Inter-Domain Routing (CIDR) and longest prefix match	2
3 Goals and metrics for IP lookup algorithms	3
4 Besides the longest prefix match problem	6
5 Outline of the thesis	6
Chapter 2 Previous Works on IP Lookup Problem	7
1 Ternary CAMs	8
2 Algorithmic approaches that use pre-computation	10
2.1 The Lulea algorithm	10
2.2 Binary search on prefix lengths	12
2.3 Binary search on intervals	13
3 Algorithmic approaches that do not use pre-computation	16
3.1 Binary trie	16
3.2 Path-compressed trie	18
3.3 Priority search trees	20
3.4 CRBT	23
3.5 Enhanced interval trees	26
3.6 Multiway range trees	28
3.7 PIBT	31
4 Complexity comparison of previous works	33
Chapter 3 Segment Trees	34
1 Prefixes and ranges	34
1.1 Prefixes and longest-prefix matching	34
1.2 Ranges	35
1.3 Properties of ranges	36
1.4 Properties of prefix ranges	39
2 Elementary intervals	41
2.1 The definition of the elementary interval	41
2.2 Some observations on elementary intervals	42
3 Segment trees	43
3.1 What is the segment tree	44
3.2 Properties of segment trees	46
3.3 How to construct the segment tree	47
3.3.1 Traditional approach to construct the segment trees	48
3.3.2 Constructing segment trees by using our approach	52
Chapter 4 Our proposed Dynamic Segment Tree (DST)	56
1 The skeleton of our Dynamic Segment Tree (DST)	56
2 Inserting a prefix	61
2.1 Inserting a node into the DST	61
2.2 The DST prefix allocation rule	65
3 Rotations of the DST	68
3.1 Left rotations and right rotations	68
3.2 A complete example of the DST insertion	72
4 Querying the DST	79
5 Deleting a prefix	81
5.1 The DST node deletion rule	82
5.2 Deleting a node from the DST	85
6 The data structures for canonical sets	99
Chapter 5 Our proposed Multiway Dynamic Segment Tree (MDST)	100
1 The structure of the MDST	100
2 Finding the longest matching prefix	102
3 Inserting a prefix	103
3.1 Inserting a point	104
3.2 Update interval vectors	108
4 Deleting a prefix	110
4.1 Deleting a point	111
5 Cache-miss analysis	118
6 Differences between the MDST and the PIBT	119
7 Using the MDST to solve the range matching problem	123
Chapter 6 Experimental Results	125
1 Level s expansion	125
2 Simulation environment	127
3 Test data	128
4 Memory requirement	128
5 Build time	136
6 Search time	139
7 Update time	142
Chapter 7 Conclusion	145
References	146

                                    

[1] M.D. Berg, M.V. Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. Springer Verlag, 1997.
[2] BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
[3] H. Chao, “Next Generation Routers,” Proceeding of the IEEE, vol. 90, no. 9, pages 1518-1558, September 2002.
[4] T. Cormen, C. Lieserson, R. Rivest, and C. Stein, Introduction to Algorithms, second edition MIT Press, 2001.
[5] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small forwarding tables for fast routing lookups,” Proceeding of ACM SIGCOMM, pages 3-14, September 1997.
[6] A. Feldman and S. Muthukrishnan, “Tradeoffs for packet classification,” Proceeding of IEEE INFOCOM, vol. 3, pages 1193-1202, March 2000.
[7] S. Fuller, T. Li, J. Yu, and K. Varadhan, “Classless inter-domain routing (CIDR): An address assignment and aggregation strategy,” RFC 1519, September 1993.
[8] P. Gupta, S Lin, and N. McKeown, “Routing lookups in hardware at memory access speeds,” Proceeding of IEEE INFOCOM, pages 1240-1247, April 1998.
[9] P. Gupta and N. McKeown, “Algorithms for packet classification,” IEEE Network Special Issue, vol. 15, no. 2, pages 24-32, March/April 2001.
[10] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of data structures in C++. New York: W.H. Freeman, 1995.
[11] N. Huang, S. Zhao, J. Pan, and C. Su, “A fast IP routing lookup scheme for gigabit switching routers,” Proceeding of IEEE INFOCOM, pages 1429-1436, March 1999.
[12] C. Labovitz, G. Malan and F. Jahabnian, “Internet routing instability,” Proceeding of ACM SIGCOMM, pages 115-126, September 1997.
[13] B. Lampson, V. Srinivasan, and G. Varghese, “IP lookups using multiway and multicolumn search,” Proceeding of IEEE INFOCOM, page 1248-1256, April 1998.
[14] H. Lu, K. Kim, and S. Sahni, “Prefix and interval-partitioned dynamic IP router-tables,” IEEE Transactions on Computers, vol. 54, no. 5, pages 545-557, May 2005.
[15] H. Lu and S. Sahni, “O(logn) dynamic router-tables for prefixes and ranges,” IEEE Transactions on Computers, vol. 53, no. 10, pages 1217-1230, October 2004.
[16] H. Lu and S. Sahni, “Enhanced interval trees for dynamic IP router-tables,” IEEE Transactions on Computers, vol. 53, no. 12, pages 1615-1628, December 2004.
[17] H. Lu and S. Sahni, “A B-tree dynamic router-table design,” IEEE Transactions on Computers, vol. 54, no. 7, pages 813-824, July 2005.
[18] C. Matsumoto, “Cam vendors consider algorithmic alternatives,” EETimes, May 2002.
[19] A. McAuley and P. Francis, “Fast Routing Table Lookups Using Cams,” Proceeding of IEEE INFOCOM, pages 1382-1391, March 1993.
[20] E. McCreight, “Priority Search Trees,” SIAM Journal on Computing, vol. 14, no. 1, pages 257-276, 1985.
[21] D. Meyer, University of Oregon Route Views Archive Project, at http://archive.routeviews.org/.
[22] S. Nilsson and G. Karlsson, “IP-Address lookup using LC-trie,” IEEE Journal of Selected Areas in Communications, vol. 17, no. 6, pages 1083-1092, June 1999.
[23] C. Partridge, P.P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway, P. Herman, A. King, S. Kohalmi, T. Ma, J. Mcallen, T. Mendez, W.C. Milliken, R. Pettyjohn, J. Rokosz, J. Seeger, M. Sollins, S. Storch, B. Tober, G.D. Troxel, D. Waitzman and S. Winterble, “A 50-Gb/s IP router,” IEEE/ACM Transactions on Networking, vol. 6, no. 3, pages 237-248, June 1998.
[24] M. Ruiz-Sanchez, E. Biersack, and W. Dabbous, “Survey and taxonomy of IP address lookup algorithms,” IEEE Network, vol. 15, no. 2, pages 8-23, March/April 2001.
[25] S. Sahni, Data Structures, Algorithms, and Applications in Java, second edition Silicon Press, 2005.
[26] S. Sahni and K. Kim, “An O(logn) dynamic router-table design,” IEEE Transactions on Computers, vol. 53, no. 3, pages 351-363, March 2004.
[27] 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, pages 337-358, 2003.
[28] D. Shah and P. Gupta, “Fast updating algorithms for TCAMs,” IEEE Micro, vol. 21, pages 36-47, January-February 2001.
[29] K. Sklower, “A Tree-Based Packet Routing Table for Berkely UNIX,” Technical report, University of California, Berkeley, 1993.
[30] V. Srinivasan and G. Varghese, “Fast IP lookups using controlled prefix expansion,” ACM Transactions on Computer Systems, pages 1-40, February 1999.
[31] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable high-speed IP routing lookups,” Proceeding of ACM SIGCOMM, pages 25-36, September 1997.
[32] Priyank Warkhede, Subhash Suri, and George Varghese, “Multiway range trees: scalable IP lookup with fast updates,” Computer Networks: The International Journal of Computer and Telecommunications Networking, vol. 44, no. 3, pages 289-303, February 2004.

校內：2006-08-29公開
校外：2006-08-29公開

簡易檢索 / 詳目顯示

相關論文