臺灣博碩士論文加值系統

對於現今的IP網路而言，路由器的設計著重於三個方向：鏈接速度，路由器的效能，封包轉送速度。而其中以封包轉送速度為目前路由器的速度的瓶頸，也因此路由查找問題為本論文所要解決的問題。伴隨著網際網路的迅速發展，傳統的IPv4網路位址將消耗殆盡。近程的解決方式為CIDR，而遠程的解決方式為IPv6。
本論文以IPv6為設計重點，提出一個路由查找系統。系統裡面涵誘F一個路由查表ASIC和外部晶片的 IPv6路由查找表。外部晶片的 IPv6路由查找表是由兩層的階層式記憶體架構所構成，並且是根據6Net路由器路由表的prefix 長度分佈所設計的。第一層外部晶片路由表可以容納150,000筆routing entries的91.89%，第二層則剩下的8.11%。ASIC裡面包含了一個Function unit和一個Binary CAM。Binary CAM被當成快取記憶體來使用，其可容納1024 個entries，並且保證80%的hit ratio。Binary CAM中的換方式演算法使用FIFO。此路由查表系統可達160Mlps的速度，其已超過目前網路上的需求，未來更大的頻寬亦可使用。系統中用了 20.04 KB的TCAM ，10.24KB BCAM以及 29.29MB RAM，並可容納150,000的routing entries。

For the IP-based network today, there are three main issues of router design— link speed, router performance, and routing lookup. Routing lookup is a bottleneck inside a router. With the growth of Internet users and services, IP address has been exhaustedly used. In order to solve this problem of exhaustion, the quick solution like CIDR is presented, and the future will be IPv6.
In this paper, a routing lookup system for IPv6 is presented. The system is composed of routing lookup ASIC and off-chip memory set. The off-chip memory set is a two-level hierarchical memory architecture. 91.89% routing entries of the routing table can be searched in one memory access, and the worst case about 10% in this system is two-memory accesses .The ASIC includes a function unit and a Binary CAM . The Binary CAM is used as cache memory with FIFO replacement algorithm .There are 1024 cache entries in the CAM with 80% hit ratio. The routing lookup system approaches 160Mlps (81.92Gb/s), and now it has overwhelmed the basic necessity. In the future, the bigger requirement will be available. In the system, routing table only needs 20.04KB TCAM, 10.24KB BCAM, and 29.29MB SRAM for a 150000 entries.

第一章：緒論 11
第二章：相關研究 15
2.1 IPV6 15
2.1.1 IPv6 位址的表示： 15
2.1.2 IPv6的定址 15
2.1.3 IPv6位址空間指定 19
2.2相關論文研討 20
2.2.1 緖論 20
2.2.2 軟體作法 21
2.2.3硬體作法 22
2.2.4 CAM相關作法 24
第三章：本論文提出的方法 25
3.1 系統架構 25
3.2 6 NET PREFIX長度的分布 26
3.3 IPV6 GLOBAL UNICAST ADDRESS 27
3.4路由查找弁?27
3.4.1插入 27
3.4.2搜尋 29
3.4.3更新 29
3.4.4刪除 29
第四章：ASIC硬體實踐 31
4.1 緒論 31
4.2 路由查表ASIC 31
4.3 資料路徑(DATAPTAH) 32
4.3.1 Hash function 32
4.3.2快取記憶體設計 33
4.4 控制單元(CONTROL UNIT) 35
4.2.1 搜尋流程圖 36
4.2.2插入流程圖 38
4.2.3刪除流程圖 41
4.2.4 更新流程圖 45
4.5路由查找系統I/O 規格 47
4.5.1 路由查找ASIC的規格 48
4.5.2 快取記憶體規格 50
4.6 CELL-BASED 硬體實踐 52
4.6.1 緒論 52
4.6.2 IC Layout 52
第五章：外部記憶體架構配置 53
5.1路由表架構 53
5.2 SIX NET PREFIX長度的分布 53
5.3 雜湊表設計 54
5.4雜湊表的大小 55
5.5 外部記憶體架構配置 路由表格式 57
第六章：效能分析與結論 61
6.1效能分析 61
6.1.1路由查表速率 61
6.1.2記憶體大小需求 62
6.2結論 63
第七章：REFERENCE 65
第八章：附錄 69
8.1邏輯閘層次模擬結果波形圖 69
8.1.1 搜尋模擬結果波形圖 69
8.1.2 插入模擬結果波形圖 69
8.1.3 刪除模擬結果波形圖 70
8.1.4 更新模擬結果波形圖 70

[1] Y. Rekhter and T. Li, RFC1518: An Architecture for IP Address Allocation with
CIDR, Internet Engineering Task Force (IETF), Sept. 1993.
[2] J. Yu V. Fuller, T. Li and K. Varadhan, RFC1519: Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy, Internet Engineering Task Force (IETF), Sept. 1993.
[3]W.Doeringer ,G .Karjoth ,and M.Nassehi, “Routing on Longest-Matching Prefixes.” IEEE/ACM Trans.Networking, vol. 4,Feb.1996,pp. 86-97.
[4] R. Hinden and S. Deering, RFC3513: Internet Protocol Version 6 (IPv6) ddressing Architecture, Internet Engineering Task Force (IETF), April. 2003.
[5] S. Deering R. Hinden and E. Nordmark, RFC3587: IPv6 Global Unicast Address
Format, Internet Engineering Task Force (IETF), August. 2003.
[6] A.K. Somani R. Sangireddy, “High-speed ip routing with binary decision diagrams based hardware address lookup engine,” IEEE Journal on Selected Areas in Communications, vol. 21, pp. 513 – 521, May 2003.
[7] G. Varghese B. Lampson, V. Srinivasan, “Ip lookups using multiway and multicolumn search,” IEEE/ACM Transactions on Networking, vol. 7, pp. 324 – 334,
June 1999.
[8] J. Turner M. Waldvogel, G. Varghese and B. Plattner, “Scalable high speed ip
routing lookups,” ACM SIGCOMM’97, vol. 27, pp. 25–36, 18-22 Oct. 1999.62 63
[9] S. Lin P. Gupta and N. McKeown, “Routing lookups in hardware at memory access speeds,” in IEEE INFOCOM’98, 29 March-2 April 1998, vol. 3, pp. 1240– 1247.
[10] Nen-Fu Huang and Shi-Ming Zhao, “A novel ip-routing lookup scheme and
hardware architecture for multigigabit switching routers,” IEEE Journal on Selected Areas in Communications, vol. 17, pp. 1093 – 1104, 1999.
[11]Robert C. Chang, Member, IEEE, and Beng-Huat Lim” Efficient IP Routing Table VLSI Design for Multigigabit Routers ” IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—I: REGULAR PAPERS, VOL. 51, NO. 4, APRIL 2004
[12]H Fadishei, MS Zamani, M Sabaei “A Novel Reconfigurable Hardware Architecture for IP Address Lookup” Symposium on Architectures for Networking and Communications Systems 2005
[13]Will Eatherton, George Varghese, Zubin Dittia “Tree bitmap: hardware/software IPlookups with incremental updates.” Computer Communication Review 34(2): 97-122 (2004)
[14] Z. Pfeffer B. Gamache and S.P. Khatri, “A fast ternary cam design for ip networking applications,” in ICCCN 2003, 20-22 Oct. 2003, pp. 434 – 439.
[15] Wang He-Ming Wang Zhen-Xing and Sun Ya-Min, “High-performance ipv4/ipv6 dual-stack routing lookup,” in 18th International Conference on Advanced Information Networking and Applications, 2004. AINA 2004., 2004, vol. 1, pp. 476– 481.
[16] T. Miyazaki T. Hayashi, “High-speed table lookup engine for ipv6 longest prefix
match,” in Global Telecommunications Conference, 1999. GLOBECOM ’99, 1999,
ol. 2, pp. 1576 – 1581.
[17] P. Francis A.J. McAuley, “Fast routing table lookup using cams,” in INFOCOM
’93, 28 March-1 April 1993, vol. 3, pp. 1382 – 1391.
[18]www.6net.org
[19]M.A. Ruiz-Sanchez, E.W.Biersack ,and W.Dabbous , “Survey and Taxonomy of IP Address Lookup Algorithm,” IEEE Network ,Vol.15 ,Mar.-Apr.2001 ,pp. 8-23
[20]HaoyuSong , Johnthan Turner John Lockwood “Shape Shifting Tries for Faster IP Route Lookup” International Conference on Network Protocols ,2005.
[21] Tan Mingfeng Gong Zhenghu “High Speed IP Lookup Algorithm with Scalabilityand Parallelism Based on CAM Array and TCAM” IEEE Communications Society , 2004.
[22] R. Jain, “A comparison of hashing schemes for address lookup in computer
networks,” IEEE Transactions on Communications, vol. 40, no. 3, pp. 1570–1573, October ,1992.
[23] M.V. Ramakrishna, “An exact probability model for finite hash table,” in Fourth
International Conference on Data Engineering, 1-5 Feb. 1991, pp. 362–368.
[24]Shyu , W-L “Architecture Design and Performance Analysis of Internet Route Cache” PHD Thesis 2005
[25]Po-Feng Lin “High speed Routing Lookup IC Design for IPv6” Master Thesis , 2005 .
[26] Andrew S. Tanenbaum and Albert S.Woodhull, Operating Systems: Design And
Implementation, Second Edition, Prentice Hall, December ,1996.
[27] Huan Liu, “Reducing cache miss ratio for routing prefix cache,” in Global
Telecommunications Conference, 2002. GLOBECOM ’02. IEEE, 17-21 Nov.
2002, vol. 3, pp. 2323 – 2327.
[28] Adil Akaaboune Jaafar Alghazo and Nazeih Botros, “Sf-lru cache replacement
algorithm,” in Records of the 2004 International Workshop on Memory Technology,
Design and Testing(MTDT’04), 2004., 9-10 Aug. 2004, pp. 19 – 24.
[29] Cheng-Shong Wu Woei-Luen Shyu and Ting-Chao Hou, “Efficiency analyses
on routing cache replacement algorithms,” in IEEE International Conference on
Communications, 2002. ICC 2002., 28 April-2 May 2002, vol. 4, pp. 2232 – 2236.
[30] RIPE NCC APNIC, ARIN, RIPE267: IPv6 Address Allocation and Assignment
Policy, APNIC, ARIN, RIPE NCC, January 2003.
[31] IESG IAB, RFC3177: IAB/IESG Recommendations on IPv6 Address Allocations
[32] “potaroo.net, http://bgp.potaroo.net/,” .
[33] “6net, large-scale international ipv6 pilot network, http://www.6net.org/,”