臺灣博碩士論文加值系統

近年來由於網路規模持續成長，enduser快速增加，造成傳統IPv4位址即將耗盡，而IPv6將會解決這個問題將會解決這個問題，在未來也會取代IPv4。另外網路速度加快，IP查找速度沒辦法跟上連結頻寬，在路由器上的IP查找造成網路傳遞封包速度的瓶頸。現今在網路應用上，TCAM是一個普遍的記憶體裝置，TCAM有平行查找且儲存don’t care X的特性，可以在一個clock cycle完成搜尋動作。不過TCAM有高弁茠滲岈I，每個TCAM晶片(100MHz 18Mb)會消耗12W~15W，另外為了符合1993年提出的CIDR，執行正確的查找要符合longest prefix match，TCAM內entry的prefix length要求要遞減順序，因此造成更新速度變慢。本論文以IPv6為基礎，提出一個快速查找以及快速更新的TCAM查表系統架構，利用簡單電路在查找時，只啟用部分的TCAM晶片，能夠節省62.5%的電源消耗，此外也對TCAM內路由表作壓縮，可以達到35%壓縮率，減低TCAM使用量也有助於降低弁荂C另外提出一套TCAM快速更新的方法，90%的prefixes都能在不用記憶體移動下完成更新。利用TCAM快速查找特性，本系統可以在一秒鐘執行10億次的查找。

With the rapid development of the Internet applications and the explosion of the end users，IPv4 address has been exhaustedly used, and the IPv6 will be the future solution and replace IPv4. With the increasing speed and network traffic of Internet, IP lookup forms a bottleneck in packet forwarding, because lookup speed cannot catch up with the increase in link bandwidth.A popular device is special type to fully associative memory: TCAM. Each cell in TCAM can take three logic states:0,1,or don’t care X and it can Search data in single clock cycle. But TCAM also has some disadvantage. Today’s high-density TCAM consume 12 to 15W per chip when the entire memory is enabled. So, TCAM arrays have high power consumption. Furthermore the adoption of CIDR in 1993 required a routing lookup to perform a LPM operation. Therefore, lookups are performed in TCAM by sorting forwarding table entries in order of decreasing prefix lengths. The need to maintain a sorted list makes incremental updates slow in a TCAM.We propose a power efficient TCAM-Based router architecture for IPv6 lookup. The architecture can reduces 62.5% TCAM power consumption through the selective enablement of only one TCAM chip. We also perform routing table compaction and achieve 35% compaction rate. It help reduce TCAM storage and power consumption. We also propose a fast TCAM update scheme. the insertion of 90% update prefixes won’t need any memory movement. Our lookup system can achieve fast lookup rate up to 100 million lookup per second.

目錄
頁碼
致謝辭 I
摘 要 II
ABSTRACT III
圖目錄 VII
第一章 簡介 1
第二章 相關研究 7
2.1 TCAM更新方法 7
2.1.1 Prefix-length ordering constraint 8
2.1.2 Centralized Sorting Prefix (CSP) 9
2.1.3 Sorting Prefix Block (SPB) 11
2.1.4 PLO_OPT 12
2.1.5 Chain-ancestor ordering constraint 14
2.1.6 CAO_OPT 15
2.2 路由表壓縮(ROUTING TABLE COMPACTION) 18
2.2.1 Pruning 19
2.2.2 Mask extension 21
2.2.3 Prefix expansion 24
第三章 系統架構 25
3.1 IPv6主幹網路路由器(backbone router)現況 25
3.2 系統架構 28
3.3 路由查找弁� 32
3.3.1 搜尋(lookup) 32
3.3.2 更新(插入、刪除) 34
3.4 架構效能分析 34
3.4.1 查找效能分析 34
3.4.2 低弁茪尷R 35
3.4.3 提高路由查找效能 35
3.4.4 節省TCAM空間 36
第四章 快速TCAM更新方法 37
4.1 路由表更新觀察 37
4.2 本論文提出方法 38
4.3 路由更新弁酮y程 42
4.4插入 44
4.4.1插入root prefixes 44
4.4.1.1 插入沒有子集的Root prefixes 44
4.4.1.2 插入至少有一個子集的Root prefixes 46
4.4.2 插入level 2 prefix 47
4.4.3 插入other prefixes 48
4.4.3.1 插入other prefixes在empty space2上方 48
4.4.3.2 插入other prefixes在empty space2下方 49
4.5 刪除 50
4.5.1 刪除root prefixes 50
4.5.1.1 刪除沒有子集的root prefixes 50
4.5.1.2 刪除至少有一個子集的root prefixes 51
4.5.2 刪除level 2 prefixes 52
4.5.3 刪除other prefixes 53
4.5.3.1 刪除在empty space2上方的other prefixes 53
4.5.3.2 刪除在empty space2下方的other prefixes 54
第五章 模擬與效能分析 55
5.1 模擬數據 55
5.2 路由表的壓縮 56
5.3 TCAM更新 57
第六章 結論 62
參考文獻 63
















圖目錄
圖 頁碼
圖 1. 2 TCAM查找示意圖 4
圖 1. 3 TCAM內LONGEST PREFIX MATCH示意圖 5
圖2.1、TCAM配置根據PREFIX-LENGTH ORDERING CONSTRAINT 8
圖2.2、TCAM配置根據CENTRALIZED SORTING PREFIX 9
圖2.3、CENTRALIZED SORTING PREFIX更新發生 9
圖2.4、CENTRALIZED SORTING PREFIX更新步驟 10
圖2.5、TCAM配置根據SORTING PREFIX BLOCK 11
圖2.6、TCAM配置根據PLO_OPT 12
圖2.7、PLO_OPT 更新步驟 13
圖2.8、PREFIX轉換成樹狀結構示意圖 15
圖2.9、TCAM配置根據CAO_OPT 15
圖2.10、CAO_OPT在位使用空間下方插入PREFIX步驟 16
圖2.11、CAO_OPT在位使用空間是上方插入PREFIX步驟 17
圖2.12、CAO_OPT刪除PREFIX步驟 17
圖2.13、在IPV4路由表中，CHAIN長度分佈圖[13] 18
圖2.14、PRUNING動作 20
圖2.15、MASK EXTENSION 動作 22
圖2.16、MASK EXTENSION 詳細動作以及PSEUDOCODE 22
圖2.17、使用PRUNING以及MASK EXTENSION對現今路由表作壓縮之結果 23
圖2.18、PREFIX EXPANSION動作 24
圖2. 24 、四個路由表中PREFIX長度分佈分析(USA、JAPAN、POTAROO、TILAB) 26
圖2. 25、四個路由表中PREFIX前16BIT開頭數量分析(USA、JAPAN、POTAROO、TILAB) 27
圖3. 3、COMPARATOR示意圖 30
圖3. 5、查找流程圖 33
圖3. 6、TCAM水平垂直壓縮示意圖 36
圖4.1、0X2001開頭的PREFIXES，17TH~32TH BIT分佈統計 37
圖4.2、PREFIXES集合關係 38
圖4.3、舉例說明PREFIXES分類 39
圖4.4、TCAM管理空間架構 40
圖4.6、插入判斷流程 43
圖4.7、刪除判斷流程 44
圖4.8、插入ROOT PREFIXES，ROOT PREFIXES沒有子集 45
圖4.10、插入LEVEL 2 PREFIX 47
圖4.12、在EMPTY SPACE2下方插入OTHER PREFIXES 49
圖4.13、刪除的ROOT PREFIXES沒有子集 50
圖4.15、刪除LEVEL 2 PREFIXES 52
圖4.16、在EMPTY SPACE2上方刪除OTHER PREFIXES 53
圖4.17、在EMPTY SPACE2下方刪除OTHER PREFIXES 54
圖5.2、對POTAROO和TALIB兩個路由表作壓縮 56
圖5.4、TILAB路由表內CHAIN長度統計 58
圖5.5、V6GEN 10000筆，CHAIN長度統計 59
圖5.6、V6GEN 50000筆，CHAIN長度統計 59
圖5.7、V6GEN 100000筆，CHAIN長度統計 59


















表目錄
表 頁碼
1.1 路由表範例 3

2.1 TCAM快速更新方法分類 7
2.2 現今IPV4路由表中PREFIX以及NEXT HOP統計[15] 19
2.3 PREFIX儲存在TCAM內的狀態[15] 21
2.4 對表2.3做MASK EXTENSION結果 23

3. 1 四個路由表中以0X2001 PREFIXES開頭比例 28

5.1 模擬數據分析 55
5.2 PREFIXES分類分布分析 57
5.2 最長CHAIN長度統計 57
5.4 更新時記憶體移動次數統計 60
5.5 更新方法比較 61

[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” in 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] 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.
[7] 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–
[8] Kai Zheng , Chengchen Hu , Hongbin Liu and Bin Liu ,“An ultra high throughput and power efficient TCAM based IP lookup engine ” in INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 7-11 March 2004 Volume: 3, On page(s): 1984-1994 vol.3
[9] Zhiyong Liang and Jianping Wu Ke Xu , ”A TCAM based IP lookup scheme for multi nexthop routing ” in Computer Networks and Mobile Computing, 2003. ICCNMC 2003. 2003 International Conference on, 20-23 Oct. 2003 On page(s): 128- 135
[10] Ravikumar, V.C. and Mahapatra, R.N. ,“TCAM Architecture for IP Lookup Using Prefix Properties” in Micro, IEEE, Mar-Apr 2004 Volume: 24, Issue: 2 On page(s): 60- 69
[11] Panigrahy, R. and Sharma, S., ”Reducing TCAM power consumption and increasing throughput”, in High Performance Interconnects, 2002. Proceedings. 10th Symposium on, 2002 On page(s): 107- 112
[12] Weidong Wu and Ruixuan Wang ,“A TCAM management scheme for IP lookup” in Networks, 2006. ICON ''06. 14th IEEE International Conference on
,Sept. 2006 Volume: 1, On page(s): 1-4
[13] Devavrat Shah and Pankaj Gupta, “fast updating algorithms for TCAMs” in IEEE Micro Volume 21 , Issue 1 (January 2001) Pages: 36 - 47
[14] WANG Zhi-heng , YE Qiang and BAI Ying-cai ,“Fast update algorithm for TCAM-Based routing lookups” in journal of Shanghai Jiaotong University,Vol.E7,No.1,2002,8~14
[15] Huan Liu “Routing table compaction in TCAM “IEEE Micro ,Jan/Feb 2002
Volume: 22, Issue: 1 On page(s): 58-64
[16] R. Hinden and S. Deering , RFC 2373,”IP Version 6 Addressing Architecture” , Internet Engineering Task Force (IETF), July 1998
[17] R. Hinden, M. O''Dell and S. Deering,RFC 2374 ,”An IPv6 Aggregatable Global Unicast Address Format”, Internet Engineering Task Force (IETF), July 1998
[18] R. Hinden and S. Deering , RFC 2375,”IPv6 Multicast Address Assignments” , Internet Engineering Task Force (IETF), July 1998
[19] C. Partridge, T. Mendez and W. Milliken, RFC 1546,” Host Anycasting Service
”, Internet Engineering Task Force (IETF), November 1993
[20] http://www.routeviews.org/
[21] http://bgp.potaroo.net/v6/as1221/bgptable.txt
[22] http://net-stats.ipv6.tilab.com/bgp/bgp-table-snapshot.txt
[23] Kai Zheng and Bin Liu ,“A Scalable IPv6 Prefix Generator for Route Lookup Algorithm”, in Advanced Information Networking and Applications, 2006. AINA 2006. 20th International Conference on , 18-20 April 2006 Volume: 1, On page(s): 6 pp.-
[24 Zhenqiang Li , Dongqu Zheng and Yan Ma ,” Tree, Segment Table, and Route Bucket: A Multi-Stage Algorithm for IPv6 Routing Table Lookup”, in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE , 6-12 May 2007 On page(s): 2426-2430