跳到主要內容

臺灣博碩士論文加值系統

(18.208.126.232) 您好!臺灣時間:2022/08/12 01:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳佩君
研究生(外文):Pei-Chun Chen
論文名稱:以快取記憶體為基礎之高效能路由器選徑查詢設計
論文名稱(外文):Cache-based IP Routing Lookups for High-Performance Routers
指導教授:紀新洲
指導教授(外文):Hsin-Chou Chi) 
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:61
中文關鍵詞:快取記憶體
外文關鍵詞:cache
相關次數:
  • 被引用被引用:0
  • 點閱點閱:152
  • 評分評分:
  • 下載下載:14
  • 收藏至我的研究室書目清單書目收藏:0
隨著科技的發展,人與人之間的互動日益頻繁,藉著網路日漸的普及化,縮短彼此間的距離,而網路上的流量以每三個月倍增的速度成長[18],如何使網路達到更快的效能,正是我們所關心和努力的目標。廣域網路 (wide area network) 間封包的傳遞是以透過路由器 (router)媒介的橋樑,經由路由器選擇下一個所欲傳遞的路徑。然而網路上的主機 (host)以每兩年增加三倍的趨勢成長[20],使得路由表 (routing table)變大,封包選徑所要花費的時間也相對的變長,所以路由器儼然成為一個限制網路效能的因素。
有許多提高路由器選徑效能的方法,軟體方面有[2][14][21]等幾種方法,而硬體的方法有[6][8][9][12][15][17]。快取記憶體 (cache)已經被證實是一個有效的方法來增進記憶體 (memory)存取的速度,最近的幾篇研究報告[1][4][5][10][19]指出,快取IP的位址 (internet protocol address) 可增進路由器選徑的效能,但是基於CIDR (classless inter domain routing)和可變動長度之子網路遮罩 (variable length subnet mask VLSM)的機制被提出和使用,路由器內存放的資料不再是IP位址,而是以IP prefix length為依據查詢路由表中Longest Prefix Matching尋找下一個主機的資訊。基於Huan Lin提出routing prefix caching[11]的架構,本篇論文將利用全關聯式搜尋(fully associative)快取記憶體的演算法 (cache scheme)針對所需快取記憶體的大小和三種不同的快取記憶體演算法 (FIFO、 LRU和Clock)來評估和增進routing prefix caching方法的效能。所提出的架構僅需一個clock cycle的時間來完成,快取記憶體演算法中最好的效能可高達80%以上。這些模擬的結果,將可提供路由器選徑的設計和製作的參考。
Nowadays the bandwidth of the network is increasing and the number of hosts is tripling approximately every two years. The current size and growth rate of the route table is growing and makes a great impact of network engineering techniques on the limited resources available inside routers in the Internet core. IP address lookups have become one of the limited factors to keep the speed of the Internet Protocol routers down.
Various algorithms have been proposed to efficiently perform longest prefix matching operation, including software based schemes and hardware based schemes. Cache has been proven to be a very efficient technique to improve memory access speed. Since CIDR (Classless Inter Domain Routing) and VLSM (Variable Length Subnet Mask) were proposed, table lookups have become an essential factor of bottleneck in the router. The IP router looks in its table for the longest prefix that matches the destination address of the packet instead of finding exact IP address.
According to recent studies on packet traces, it has shown the efficiency of IP address lookups using caching algorithm, especially routing prefix cache algorithm. In this thesis, we evaluate the performance of routing prefix cache algorithms in hardware designs for network processors to improve the efficiency of IP routers. Our results show that the cache algorithm may achieve the hit rate at about 80%.
摘要 ii
ABSTRACT iii
第一章 1
導論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 背景介紹 2
1.3.1 網路結構 2
1.3.2 區域網路與廣域網路 3
1.4 路由器選逕與轉送 4
1.4.1選擇最佳路徑 4
1.4.2 傳送資料封包 4
1.5 路由器架構 6
1.5.1 ICM、PAR和PRARP 6
1.5.2 RIP和OSPF 6
1.6 IP PREFIX 革新 8
1.7 最近似解問題 9
1.8 論文架構 9
第二章 10
轉送表查詢問題的相關研究 10
2.1導論 10
2.2以Trie為基礎的結構 12
第三章 30
以快取記憶體結構為基礎的選徑架構 30
3.1 快取記憶體架構 31
3.2 快取記憶體替換法則 34
3.2.1 FIFO 替換法 34
3.2.2 LRU 替換法 34
3.2.3 Clock替換法則 35
3.3 Prefix選取 36
3.3.1 Caching Prefix選取架構 36
3.3.2 快取記憶體配置 38
第四章 40
模擬與分析 40
4.1選徑資料來源 41
4.2 快取記憶體記憶體需求 43
4.3 快取記憶體效能分析 44
4.3.1 Caching Prefix選取架構 44
4.3.2 快取記憶體配置分析 53
第五章 58
結論與未來研究 58
參考文獻 60
[1] E. Besson, and P. Brown, “Performance Evaluation of Hierarchical Caching in High-Speed Routers”, Proc. Globecom, 1998, pp. 2640-45
[2] A. Brodnik, S. Carlsson, M. Degermark, S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” Proc. ACM SIGCOMM 1997, pp.3-14, Cannes, France.
[3] Cooperative Association for Internet Data Analysis (CAIDA),
http://www.caida.org/
[4] G. Cheung, and S. McCanne, “Optimal Routing Table Design for IP Address Lookups Under Memory Constraints”, Proc. Infocom, 1999, pp. 1437-44.
[5] T.C. Chiueh and P. Pradhan, “Cache Memory Design for Network Processors,” Proc. High Performance Computer Architecture, pp. 409-418, 1999.
[6] P. Gupta, S. Lin and N. McKeown, “Routing Lookups in Hardware at Memory Access Speeds,” Proc. Infocom, April 98, San Francisco.
[7] Sheng-Chin Hsu, “Efficient IP Routing Lookups for High-Performance Routers” Department of Computer Science and Information Engineering National Dong-Hwa University, Hualien, Taiwan, R.O.C
[8] T. Hayashi and T. Miyazaki, “High-Speed Table Lookup Engine for IPv6 Longest Prefix Match,” Proc. Globecom, 1999, vol. 2, pp 1576-1581
[9] M. Kobayashi, T. Murase and A. Kuriyama, “A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing”, Proc. ICC 2000, June 2000.
[10] H. Liu, “Reducing Routing Table Size using Ternary-CAM”, Proc. Hot Interconnect 9, Stanford, 2001
[11] Huan Liu, “Routing Prefix Caching in Network Processor Design,” Department of Electrical Engineering, Stanford University, CA 305, huanliu@stanford.edu,2001.
[12] A. McAuley and P. Francis, “Fast Routing Table Lookup Using CAMs”, Proc. Infocom 93, Vol. 3, pp. 1382-91, Mar. 1993.
[13] McGary Massachussetts Institute of Technology. Internet Growth Summary. http://www.mit.edu/people/mgray/net/internet-growth-summary.html.
[14] S. Nilsson, G. Karlsson, “IP-address lookup using LC-tries,” IEEEJournal on Selected Areas in Communications, vol. 17, no. 6, pp.1083-1092, 1999.
[15] T.B. Pei and C. Zukowski, “VLSI Implementation of Routing Tables: Tries and CAMs,” Proc. Infocom 91
[16] V. Srinivasan and G. Varghese, “Fast Address Lookups Using Controlled Prefix Expansion,” ACM Transactions on Computer Systems, Vol. 17, no. 1, pp. 1-40, Oct. 1999
[17] D. Shah and P. Gupta, “Fast Updates on Ternary-CAMs for Packet Lookups and Classification,” Proc. Hot Interconnects VIII, August 2000, Stanford.
[18] A. Tam, “How to Survive as an ISP,” in Proc. Networld Interop 97, 1997.
[19] B. Talbot, T. Sherwood, and B. Lin, “IP Caching for Terabit Speed Routers”, Globecom, 1999.
[20] University of Oregon Route Views Project,
http://www.antc.uoregon.edu/route-views/
[21] M. Waldvogel, G. Varghese, J. Turner, B. Plattner, “Scalable High-Speed IP Routing Lookups,” Proc. ACM SIGCOMM 1997, pp. 25-36,Cannes, France.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文