| 研究生: |
高延國 Kao, Yen-Kuo |
|---|---|
| 論文名稱: |
處理封包路由搜尋且有效減少TCAM使用之二階層式結構設計 Two level TCAM reduction architecture for IP lookup |
| 指導教授: |
張燕光
Chang, Yeim-Kuan |
| 學位類別: |
碩士 Master |
| 系所名稱: |
電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering |
| 論文出版年: | 2005 |
| 畢業學年度: | 93 |
| 語文別: | 英文 |
| 論文頁數: | 49 |
| 中文關鍵詞: | 路由位址查詢 、電量消耗 、三項內容定址記憶體 |
| 外文關鍵詞: | IP address lookup, TCAM, power consumption |
| 相關次數: | 點閱:88 下載:1 |
| 分享至: |
| 查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近年來TCAM廣泛的被使用在路由位址查詢的設計中,主因為TCAM達到了快速的效能和便利的使用性在處理路由查詢的領域。值得注意的是,現今網路核心路由器所使用的路由表往往都存在超過十萬筆以上的路由資訊。所以當我們單純使用TCAM來儲存路由表時,也必須要使用到能儲存超過十萬筆資訊的大型或大量TCAM。但是我們發現到當大量TCAM欄位同時執行搜尋比對動作時,將會產生出大量的廢熱,造成整個系統溫度上升。而當溫度超過某個溫度限制時,整個系統就可會出錯而處於不穩定的狀態。
為了避免過熱的情況發生,我們採取盡量減少使用TCAM欄位的方式來減少電量的消耗,並提出一個結合TCAM和DRAM的二階層架構來處理路由位址的查詢。相較於單純使用TCAM來儲存路由表,根據實驗結果,當使用我們的架構時,所需要使用的TCAM欄位僅為前者的2%.也就是說當我們對同一張路由表執行路由位址查詢時,相較於過去使用TCAM的路由設計架構,使用我們的架構將可減少相當多的電能消耗。有別於其它的架構,我們的架構所需求的TCAM使用量並不會隨著路由表之大小線性成長。藉由彈性使用TCAM的MASK和使用小型的TCAM來儲存切割後的路由表這兩種方法,我們能夠精確的控制電量的消耗。同時本架構對每一個封包的路由查詢,只需要一次的TCAM比對和兩次的DRAM存取就能保證完成路由的動作。
In recent years using TCAM in lookup design becomes more and more popular. TCAM provide a fast and convenient solution for IP lookup problem. But the BGP table in the core router today often has more than 100k prefixes, so we will need the same large TCAM entries to store the routing table. Unfortunately, when enabling too many TCAM entries together will bring large power consumption and result in system over hot. And the over hot situation may block the regular system work.
To avoid the over hot situation, we try to cut down the power consumption by reducing the TCAM entry in our design. We propose a two level architecture hybrid of TCAM and DRAM for IP lookup problem. According to our experiment result, our scheme only needs 2% TCAM entries rather than purely using TCAM to storing the routing table. It also means our architecture is less power consumption than tradition TCAM lookup design for the same routing table. Contrast with other architectures, our design make sure the requirement of TCAM entries will not linearly increase with the routing table growing. And by using mask extension and partitioning sub-TCAM steps, we can exactly control the enable TCAM entries and ensure the power consumption under the power restriction. At last, our architecture only needs one TCAM memory access and two DRAM memory accesses to finish the IP address lookup for each incoming IP packet.
[1]BGP Routing Table Analysis Reports,http://bgp.potaroo.net/.
[2]A. Basu, G. Narlikar, “Fast Incremental Updates for Pipelined Forwarding Engines,” IEEE INFOCOM, April 2003.
[3]F. Baboescu, S. Singh, G. Varghese, “Packet Classification for Core Routers: Is there an alternative to CAMs?” IEEE INFOCOM, April 2003.
[4]CYRESS. http://www.cypress.com/.
[5]EZ Chip Network Processors. http://ezchip.com
[6]IDT. http://www.idt.com/products/.
[7]Stefanos Kaxiras and Georgios Keramidas, "IPStash: a Power-Efficient Memory Architecture for IP-lookup." IEEE/ACM International Symposium on Microarchitecture, no 36, 2003.
[8]R. Panigrahy, S. Sharma, “Reducing TCAM Power Consumption and Increasing Throughput”, Proceedings of HotI’02, Stanford, California, USA, pp. 107.
[9]A. Gallo, “Meeting Traffic Demands with Next-Generation Internet Infrastructure.” Lightwave, 18(5):118-123, May 2001.
[10]H. Liu, "Routing table compaction in ternary CAM," IEEE Micro, Vo1.22, Issue 1, pp. 57-64, Jan-Feb2002.
[11]Intel IXP2850 Network Processor. http://www.intel.com/design/network/products/npfamily/ixp2850.htm
[12]R. K. Montoye, "Apparatus for Storing “Don’t care” in a Content Addressable Memory Cell.", United States Patent 5,319,590, June 1994. HaL Computer Systems, Inc.
[13]D. Meyer, "University of Oregon Route Views Archive Project", at http://archive.routeviews.org/.
[14]IBM PowerNP Network Processors. http://www.chips.ibm.com/products/wired/network_processors.html
[15]A. J. McAuley and P. Francis. Fast Routing Table Lookup Using CAMs. In Proceedings of Infocom ’93, pages 1382–1391, San Francisco, CA, March 1993
[16]Y. Rekhter, T. Li, “An Architecture for IP Address Allocation with CIDR.” RFC 1518, Sept. 1993.
[17]D. Shah and P. Gupta, “Fast Updating Algorithms for TCAMs”, IEEE Micro, 21(1):36-47, January-February 2001.
[18]M. A. Ruiz-Sanchez, Ernst W. Biersack, and Walid Dabbous, "Survey and Taxonomy of IP Address Lookup Algorithms," IEEE Network Magazine, 15(2):8--23, March/April 2001.
[19]M. Wang, S.Deering, T. Hain, L. Dunn, "Non-random Generator for IPv6 Tables," in Proc. 12th Annual IEEE Symposium of High Performance Interconnects, pp. 35-40, Aug. 2004.
[20]Network and Communications ICs. http://www.agere.com/enterprise_metro_access/network_processors.html
[21]Vitesse IQ2200. http://www.vitesse.com
[22]K. Zheng,, H.B. Lu, and B. Liu, “A Parallel IP Lookup Algorithm for Terabit Router”, Proceeding of ICCT, April 9-11,2003, Beijing, China, pp.478-481.
[23]Kai Zheng, Cheng chen,Hong bin, Bin Liu, “An Ultra High Throughput and Power Efficient TCAM-Based IP Lookup Engine.” IEEE INFOCOM 2004.
[24]F. Zane, G. Narlikar, A. Basu, “CoolCAMs: Power-EfficientTCAMs for Forwarding Engines.” IEEE INFOCOM, April 2003.