(3.238.240.197) 您好!臺灣時間:2021/04/12 02:27
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:涂嘉良
論文名稱:依實際IP長度有效分配記憶體之路由器設計
論文名稱(外文):Design of Router Memory with Efficient Distribution for Prefix Length
指導教授:張振豪
指導教授(外文):Robert C. Chang
學位類別:碩士
校院名稱:國立中興大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:54
中文關鍵詞:路由器跳躍陣列
外文關鍵詞:RouterSkip array
相關次數:
  • 被引用被引用:0
  • 點閱點閱:132
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
現今在高執行的路由器中,網路位址的查尋是主要的瓶頸,尤其是當網路速度高達每秒數十億位元時。IP的位址查尋是一種挑戰,因為它需要最長前端吻合。除此之外,路由表容量的大量増加和高速網路的連接都增加了路由器的困難度。在這個論文中對於查尋、新增和刪除,我們利用了以前基本的架構,再參考實際網路的IP位址分佈圖,將記憶體有效的放在IP位址所佔據的長度內。再者我們擴大跳躍的功能,利用這些技術更進一步節省記憶體的空間,在此我們使用硬體描述語言進行此方法的硬體設計,並且以同步的0.35μm之SRAM做為其位址存放的記憶體,在硬體管線方式下於每次的記憶體存取後即有查尋結果的輸出。經由記憶體分配的模擬結果,雖然增加14%的體憶體空間,但卻增加了62%可使用的輸出埠。

With high-speed multi-gigabit links required in the Internet , the lookup becomes a great bottleneck. The routing table lookup needing longest prefix matching is a challenge. Beside, the large capacity of lookup table and high-speed links increase the difficulty of IP router. In this thesis, a lookup scheme based on a previous structure and the real IP address length is proposed, which can efficiently handle IP routing lookup, insertion, and deletion inside the routing table. We use the skip function to reduce the memory space. Hardware design of the routing table was carried out using the Verilog hardware description language. It uses the synchronous 0.35μm SRAM as the router memory. In a hardware pipeline configuration, the output port is obtained in every memory access. We increase 62% of usable output port, with increase of 14% memory space.

中文摘要 i
Abstract ii
內容 iii
圖目錄 vi
表目錄 ix
第一章 序論
1.1 TCP/IP的分層架構 1
1.2 網際網路的封包和位址 2
1.3 IP路由器的功能 5
1.4 動機 7
1.5 概要 7
第二章 各種路由表的查尋方法 8
2.1 直接位址查尋 8
2.2 調整式二元位址查尋 9
2.3 補償位址查尋 10
2.4 區塊位址查尋 11
2.5 補償和區塊查尋的結合 13
第三章 路由表記憶體之有效應用 16
3.1 硬體管線式的快速查尋路由表 16
3.1.1 硬體管線式結構 16
3.1.2路由表之基本結構 17
3.2 實際有效長度的分佈 20
3.3 跳躍陣列的應用 21
3.4 記憶體的有效分怖 25
3.5 模擬的結果與分析 26
第四章 路由器查尋之硬體實現 28
4.1 路由器的基礎結構 28
4.2 控制器的內部結構 31
4.3 查尋模組 34
4.3.1 12位元的查尋模組 35
4.3.2 有跳躍陣列的4位元查尋模組 38
4.3.3沒有跳躍陣列的4位元查尋模組 40
4.4 查尋模組的操作流程 42
第五章 模擬結果 47
5.1 Cell_based 的設計流程 47
5.2 模擬結果 48
第六章 結論 50
參考文獻 51

[1] W. Richard Stevens, “TCP/IP Illustrated, Volume1 — The Protocols,” Addison Wesley Lngman, Inc., 1994.
[2] F. Baker, Ed. “Requirements for IP version 4 routers,” RFC 1812, Jun. 1995.
[3] V. Fuller, T. Li, J. Yu, and K. Varadhan, “Classless inter-domain routing (CIDR): An address assignment and aggregation strategy,” RFC 1519, Internet Engineering Task Force, 1993.
[4] R. Hinden and S. Deering, “IP version 6 addressing architecture,” RFC 1884, Dec. 1995.
[5] C. Partridge, P. P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway, P. Herman, A. King, S. Kohalmi, T. Ma, J. McCallen, 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 Trans. Networking, vol. 6, pp. 237-248, Jun. 1998.
[6] S. Keshav and R. Sharma, “Issues and trends in router design,” IEEE Communication Magazine, vol 36, pp. 144-151, May 1998.
[7] V. Kumar, T. V. Lakshman, and D. Stiliadis, “Beyond best effort: Router architectures for the differentiated services of tomorrow’s Internet,” IEEE Communication Magazine, vol. 36, pp. 152-164, May 1998.
[8] N.-F. Huang and 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, pp. 1093-1104, June 1999.
[9] B. Lampson, V. Srinivasan, and G. Varghese, “IP lookups using multiway and multicolumn search” in Proc. IEEE INFOCOM, pp. 1248-1256, San Francisco, CA, 1998.
[10] D. R. Morrison, “Patricia — Practical algoritm to retrieve information coded in alphanumeric,” J. ACM, vol. 15, pp. 515-534, Oct. 1968.
[11] W. Doeringer, G. Karjoth, and M. Nassehi, “Routing on longest-matching prefixes,” IEEE/ACM Trans. Networking, vol. 4, pp. 86-97, Feb. 1996.
[12] V. Srinivasan and G. Varghese, “Fast address lookups using controlled prefix expansion,” in Proc. ACM Sigmetrics Conference, pp. 1-11, Madison, WI, 1998.
[13] S. Nilsson and G. Karlsson, “IP-address lookup using LC-tries,” IEEE Journal on Selected Areas in Communications, vol. 17, no. 6, pp. 1083-1092, June 1999.
[14] A. McAulley and P. Francis, “Fast routing table lookup using CAM’s,” in Proc. IEEE INFOCOM Conference, vol. 3, pp. 1382-1391, 1993.
[15] D. Feldmeier, “Improving gateway performance with a routing table cache,” in Proc. IEEE INFOCOM Conference, New Orleans, LA, 1988.
[16] P. Gupta, S. Lin, and N. Mckeown, “Routing Lookups in Hardware at Memory Access Speeds,” in Proc. IEEE INFOCOM, pp. 1240-1247, San Francisco, CA, 1998.
[17] C. A. Zukowski and T. Pe, “Putting routing tables into silicon,” IEEE Network, pp. 42-50, Jan. 1992.
[18] M. Degermark, A. Bodik, S. Carlsson, and S. Pink, “Small forwarding tables for fast routing lookups,” in Proc. ACM SIGCOMM Conference, pp. 3-14, Cannes, France, 1997.
[19] H.-Y. Tzeng and T. Przygienda, “On Fast Address-Lookup Algorithms”, IEEE Journal on Selected Area in Communications, vol. 17, no. 6, pp. 1067-1082, June 1999.
[20] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable high speed IP routing lookups,” in Proc. ACM SIGCOMM, pp. 25-36, France, 1997.
[21] Michigan University and Merit Network, Internet Performance Measurement and analysis (IPMA) Project [Online], available WWW: http://nic.merit.edu/~ipma/.
[22] P-A, Yilmaz, A. Belenkiy, N.Uzun, “A Trie-based Algorithm for IP Lookup Problem,” Global Telecommunications Conference, 2000. GLOBECOM '00. IEEE , Volume: 1 , 27 Nov.-1 Dec. 2000 ,Page(s): 593 -598 vol.1

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔