跳到主要內容

臺灣博碩士論文加值系統

(3.236.84.188) 您好!臺灣時間:2021/08/03 10:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳國民
研究生(外文):Kuo-Ming Chen
論文名稱:次世代網路之高效能IP搜尋與更新機制
論文名稱(外文):An efficient IP lookup and update scheme for next generation network
指導教授:伍麗樵伍麗樵引用關係
指導教授(外文):Lih-Chyau Wuu
學位類別:碩士
校院名稱:國立雲林科技大學
系所名稱:電子與資訊工程研究所碩士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:56
中文關鍵詞:轉送表IP搜尋路由表
外文關鍵詞:routing tableIPv6forwarding tableIP lookupprefix tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:144
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
IP搜尋為目前路由器效能上最主要的瓶頸,對於每一個進入路由器的封包,都必須使用該封包上的目的位址(Destination address,DA)與forwarding table做比對,並選出prefix最長且符合DA的entry (longest prefix matching),以決定該封包的next-hop。

在本篇論文中,我們提出最長前置位元先搜尋樹(Longest Prefix First Search Tree,LPFST)的架構來建立forwarding table,其執行longest prefix matching時可不必搜尋至樹的終端節點,使記憶體的存取次數最小化。此外,本架構中使用包含(containing)的技術,讓有些節點可涵蓋routing table 2筆的prefix 資訊,以減少樹節點的產生。例如,一routing table包含138286筆entries,以LPFST建構只需132050個節點。總之,我們提出的LPFST架構具有以下的特性:記憶體的存取次數最小化、低記憶體儲存需求、快速更新forwarding table、無預先處理時間、可擴充性等。最後經由效能比較分析後,證明LPFST要比trie、path-compressed trie與prefix-tree有較低的記憶體存取次數與記憶體儲存需求。
IP lookup is a major bottleneck for router performance. For each incoming packet, a router decides the next-hop of the packet by performing IP lookup in its routing table. That is, to find a routing entry having the longest prefix matching with the packet’s destination address.

In this paper, we present a longest prefix first search tree(LPFST) scheme to minimize the number of memory accesses while a router executes IP lookup operation. Our IP lookup does not need to search to the leaf of the tree while other schemes[5, 17, 21] do. Besides, to reduce the number of tree nodes, we propose a containing technique to let some nodes can cover 2 entries of the routing table. For example, a 138286 of a routing table can be stored in 132050 nodes of our LPFST. In summary, as compared with trie[5], patricia[17] and prefix tree[21], our LPFST comes with the following metrics: minimizing the number of memory accesses, lower memory requirement, fast forwarding table updating, no preprocessing, and IPv6 adaptability.
目 錄

中文摘要 ………………………………………………………………………… i
英文摘要 ……………………………………………………………………….. ii
誌謝 ……………………………………………………………………. iii
目錄 ………………………………………………………………………. iv
圖目錄 ……………………………………………………………………… vi
表目錄 ……………………………………………………………………… vii

一、緒論 1
1.1研究動機 1
1.2何謂IP搜尋(IP LOOKUP) 1
1.3 IP LOOKUP之相關工作 2
1.4研究目的 3
1.5論文架構 4
二、相關研究 5
2.1 TRIE的架構 5
2.2 PATH-COMPRESSED TRIE (PATRICIA)的架構 6
2.3 PREFIX TREE的架構 8
三、最長前置位元先搜尋樹 11
3.1 資料結構 11
3.2 LPFST的建構方法 13
3.2.1 建立LPFST的演算法 16
3.2.2 LPFST節點插入演算法 17
3.2.3 LPFST節點插入演算法的特性 18
3.3 IP搜尋流程 21
3.3.1 LPFST的IP搜尋流程 21
3.3.2 IP搜尋演算法 23
3.4 LPFST的更新流程 24
3.4.1 LPFST節點刪除流程 24
3.4.2 LPFST節點刪除演算法 27
3.5 LPFST高度分析 30
3.6 LPFST的效能改善 32
3.6.1 建構PLPFST的方法 33
3.6.2 建立PLPFST的演算法 35
3.6.3 PLPFST的IP搜尋流程 37
3.6.4 PLPFST的IP搜尋演算法 38
四、效能評估 39
4.1 模擬環境 39
4.2 分析結果 39
4.2.1 AS4637 routing table 40
4.2.2 AS286 routing table 42
4.2.3 Mae-West routing table 44
4.3 更新FORWARDING TABLE的模擬 46
五、IPV6的擴充性 47
5.1 IPV6的UNICAST位址格式 48
5.2 IPV6環境下建構PLPFST的方法 48
5.3 IPV6 ROUTING TABLE 49
六、結論 53
參考文獻 54
1.F. Baker, “Requirements for IP version 4 routers,” RFC 1812, Jun. 1995.
2.Y. Rekhter and T. Li, “An architecture for IP address allocation with CIDR,” RFC 1518, Sep. 1993.
3.V. Fuller, T. Li, J. Yu, K. Varadhan, "Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy," RFC 1519, Sep. 1993.
4.A. J. McAuley, P. Francis, “Fast routing table lookup using CAMs,” In Proc. INFOCOM ''93, vol. 3, Mar.-Apr. 1993, pp. 1382 -1391.
5.H. Liu, “Routing table compaction in ternary CAM,” IEEE Micro, vol. 22, no. 1, Jan.-Feb. 2002, pp. 58-64.
6.Z. Liang, J. Wu, K. Xu, “A TCAM-based IP lookup scheme for multi-nexthop routing,” In Proc. IEEE ICCNMC 2003, Oct. 2003, pp. 128-135.
7.K. Sklower, A Tree-Based Routing Table for Berkeley Unix, Tchnical report, University of California, Berkeley, 1993.
8.P. Gupta, S. Lin, and N. McKeown, “Routing Lookups in Hardware at Memory Access Speeds,” In Proc. IEEE INFOCOM ’98, Mar. 1998, pp. 1240-1247.
9.J. Jia, C. Lin, W. Liu, “A fast two-way IP lookup algorithm based multibit-trie,” In Proc. IEEE ICCNMC 2003, Oct. 2003, pp. 136-142.
10.P. Mehrotra, P. D. Franzon, “Novel hardware architecture for fast address lookups,” IEEE Communications Magazine, vol. 40, no. 11, Nov. 2002, pp. 66-71.
11.D. E. Taylor, J. S. Turner, J. W. Lockwood, T. S. Sproull, D. B. Parlour,” Scalable IP lookup for Internet routers,” IEEE Journal on Selected Areas in Communications, vol. 21, no. 4, May 2003, pp. 522-534.
12.S. Sahni, K. S. Kim, “Efficient construction of multibit tries for IP lookup,” IEEE/ACM Transactions on Networking, vol. 11, no. 4, Aug. 2003, pp. 650-662.
13.D. Pao, C. Liu, A. Wu, L. Yeung, K.S. Chan, “Efficient hardware architecture for fast IP address lookup,” In Proc. IEEE Computers and Digital Techniques, vol. 150, no. 1, Jan. 2003, pp. 43-52.
14.M. Degermark, A. Brodnik, S.Carlsson, S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” In Proc. ACM SIGCOMM ’97, Sep. 1997, pp. 3-14.
15.N.-F. Huang, 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, Jun. 1999, pp. 1093-1104.
16.L.-C. Wuu, S.-Y Pin, “A fast IP lookup scheme for longest-matching prefix,” In Proc. IEEE Computer Networks and Mobile Computing, 2001, pp. 407-412.
17.D. R. Morrison, “PATRICIA-Practical Algorithm to Retrieve Information Coded in Alphanumeric, “ Journal of the ACM, vol. 15, no. 4, Oct. 1968, pp. 514-34.
18.S. Nilsson, G. Karlsson, “IP-address lookup using LC-tries,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 6 , Jun. 1999, pp.1083-1092.
19.S. Suri, G. Varghese, P. R. Warkhede, “Multiway range trees: scalable IP lookup with fast updates,” In Proc. IEEE GLOBECOM ''01, vol. 3, Nov. 2001, pp. 1610-1614.
20.P. Mehrotra, P.D. Franzon, ”Binary search schemes for fast IP lookups,” In Proc. IEEE GLOBECOM ''02 , vol. 2, Nov. 2002, pp. 2005-2009.
21.M. Berger, “IP lookup with low memory requirement and fast update,” In Proc. IEEE High Performance Switching and Routing, Jun. 2003, pp. 287-291.
22.S. Deering and R. Hinden, “Internet Protocol, Version 6 (IPv6) Specification, Request for Comments (Proposed Standard),“ RFC 1883, Jan. 1996.
23.Internet Systems Consortium, Internet Domain Survey. http://www.isc.org/.
24.Merit Networks, Inc. Internet Performance Measurement and Analysis (IPMA) Statistics and Daily Reports. http://www.merit.edu/ipma/routing_table/.
25.The Routing Arbiter Project, Internet routing and network statistic. http://www.re.net/statistics/.
26.BGP Table Data, BGP Routing Table Analysis Reports, http://bgp.potaroo.net/.
27.M.A Ruiz-Sanchez, E.W. Biersack, W. Dabbous , “Survey and taxonomy of IP address lookup algorithms,” IEEE Network, vol. 15, no. 2, Mar.-Apr. 2001, pp. 8-23.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top