封包分類是一個會大大影響現在網路路由器整體效能的一個重要問題。因此近年來已經有許多的研究在探討這個領域。這些研究包含了使用TCAM裝置來加快封包分類的速度。然而，TCAM裝置有著一個嚴重的問題：巨大的能源消耗。這樣大能量的消耗會使得網路供應商的電力預算大幅增加。除此之外，TCAM裝置無法儲存封包分類中的任意數值範圍，而傳統的解決方法也沒有效率。因此，extended TCAM 利用TCAM裝置本身可以同時只啟動部份的TCAM而不需要全部啟動的特性，設計出一個遞迴地切割rule table使得可以降低能源消耗的方法，並且設計出額外的硬體架構來處理任意數值儲存及比對的問題。而在本篇論文中，我們提出了更有效率的切割rule table方法來解決TCAM裝置高耗能的問題。除此之外，我們不使用額外特殊的硬體架構，而是採用編碼技術對任意數值範圍進行編碼，使得它可以有效率的被儲存在TCAM裝置中。再來，我們亦發展出兩種平行處理的架構。如此一來，整體所需要的TCAM容量可以大大地降低。為了測試我們的分割演算法以及架構，我們利用ClassBench來幫助產生不同特性及大小的rule tables。實驗結果顯示，我們提出的演算法和架構的確可以大大地降低能源的消耗量。

Packet classification is a key technology that would affect the total system performance of modern routers. Many researches have widely studied this problem by using TCAM devices to speedup the search process. However, the usage of TCAM suffers from the issue of high power consumption such that the power budget gets large. Also since TCAM devices can not efficiently represent the arbitrary ranges such that each rule in rule table may occupy many number of TCAM entries. Due to the property that partial TCAM entries can be enabled at a time, Extended TCAMs [16] use the recursive cut to partition the multidimensional space to save the average power consumption. It also employs particular hardware designs to solve the inefficient representation of arbitrary ranges in TCAMs which requires additional power budget. In this paper, we design efficient partitioning algorithms to reduce the average power consumption while using TCAMs and improve the efficiency of the representation for arbitrary ranges by using the existing encoding technique. Besides, we develop parallel architectures which can truly reduce the total TCAM size. We use ClassBench [19] to generate rule tables and trace files with different properties to test our proposed algorithms and architectures. The results show that our methods can reduce the power consumption by a significant factor compared with the conventional TCAM.

[1] M.D. Berg, M.V. Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications. Springer Verlag, 1997.
[2] Florin Baboescu, Sumeet Singh and George Varghese, “Packet Classification for Core Routers: Is there an alternative to CAMs?”, IEEE INFOCOM 2003, Volume 1, pp. 53-63, 30 March-3 April 2003
[3] Yeim-Kuan Chang, “Power-Efficient TCAM partitioning for IP Lookups with incremental updates,” Lecture Notes on Computer Science 3391 (ICOIN 2005), pp. 531-540, 2005. (SCI)
[4] Yeim-Kuan Chang and Yung-Chieh Lin, “Dynamic Segment Trees for Ranges and Prefixes”, IEEE Transactions on Computers, June 2007, pp. 769 – 784
[5] Yeim-Kuan Chang and Cheng-Chien Su, “Efficient TCAM Encoding Schemes for Packet Classification Using Gray Code”, IEEE Globecom 2007.
[6] Pankaj Gupta and Nick Mckeown, “Packet Classification using Hierarchical Intelligent Cuttings”, Hot Interconnects VII, August 1999.
[7] Pankaj Gupta and Nick Mckeown, “Packet Classification on Multiple Fields”, ACM Sigcomm, August 1999
[8] G. Huston. Analyzing the Internet’s BGP Routing Table. The Internet Protocol Journal, 4, 2004
[9] IDT, http://www.idt.com/
[10] Jan van Lunteren and Ton Engbersen, “Fast and Scalable Packet Classification”, IEEE Journal on Selected Areas in Communications 2003, Vol. 21, No. 4, May 2003
[11] Haibin Lu and Mian Pan, “Partition Filter Set for Power-Efficient Packet Classification”, IEEE GLOBECOM 2006
[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] Netlogic, http://www.netlogicmicro.com
[14] V.C. Ravikumar, Rabi N. Mahapatra and Laxmi Narayan Bhuyan, “EaseCAM: an energy and storage efficient TCAM-based router architecture for IP lookup”, IEEE Transactions on Computers, Volume 54, issue 5, pp. 512-533, May 2005
[15] V. Srinivasan, S. Suri and G. Varghese, “Packet classification using Tuple Space Search”, SIGCOMM 1999, pp. 135-146.
[16] Ed Spitznagel, David Taylor and Jonathan Turner, “Packet Classification Using Extended TCAMs”, Proceedings of ICNP 2003
[17] Sumeet Singh, Florin Baboescu, George Varghese and Jia Wang, “Packet Classification Using Multidimensional Cutting”, Proceedings of ACM SIGCOMM 2003, August 2003
[18] David E. Taylor, “Survey and taxonomy of packet classification techniques”, ACM Computing Surveys, Volume 37, Issue 3, pp. 238-275, September 2005
[19] David E. Taylor and J. Turner, “ClassBench: A Packet Classification Benchmark”, IEEE INFOCOM 2005.
[20] Francis Zane, Girija Narlikar and Anindya Basu, “CoolCAMs: Power-Efficient TCAMs for Forwarding Engines”, IEEE INFOCOM 2003, Volume 1, pp. 42-52, March-April 2003
[21] Kai Zheng, Zhiyong Liang and Yi Ge, “Parallel Packet Classification via Policy Table Pre-Partitioning”, IEEE Globecom 2005.