網際網路快速的發展，有越來越多的高品質的網路服務或是網路應用程式需要被實做在現今的路由器(router)上，例如 QoS ( Quality of Service )、網路的資訊安全、多媒體通訊等等…。所以封包分類的技術因而被提出來滿足這些需求，為了要分配封包到特定的封包串流(flow)，路由器(router)必須根據封包的表頭(header)資訊並且搜尋一系列封包分類的規則將封包分類至特定的封包串流(flow)。
傳統上，三元內容位址記憶體(Ternary Content Addressable Memory) 常被用來解決IP lookup的問題，因為它擁有快速跟平行搜尋的特性，此外因為它可以儲存三種邏輯狀態 (“0”, “1”, “don’t care”) 所以它也非常適合用來儲存Prefix格式的資料。但是在五維的封包分類中，它包含了兩維任意範圍的通訊阜號碼(Port number)，所以對於TCAM而言，它並不適合儲存此種格式的資料。此種情形下我們或許需要使用大量的TCAM位址空間去儲存一條封包分類的規則。
在此篇論文中我們提出了一個兩接層的TCAM架構及相關的配套方法去解決五維封包分類的問題，我們所提出的方法的基本概念是，我們複製五維的位址空間並且設計一個策略將所有的規則分類，此外我們也設計了一系列裁切 ”分類規則” 的方法好讓我們可以達成五維封包分類的目標。在我們所提出的方法中，我們不但可以保有TCAM快速及平行搜尋的好處並且不會使用很大量的TCAM位址空間去儲存封包分類的規則表。

The Internet is growing very rapidly. There are more and more high-quality Internet services and network applications are demanded in modern-day router, such as quality of service (QOS), security, and multimedia communication…etc. The packet classification is a proposed function for these demands. In order to classify a packet to a particular flow, the router must perform a search over a set of rules using multiple fields of the packet’s header as the search key.
Traditionally, ternary content addressable memory (TCAM) has been adopted to solve the IP lookup problem due to their ability to perform fast and parallel searching. TCAM is very suitably for storing prefix. Because it can store three logic states (1, 0, don’t care) in a TCAM cell. But in five dimensional packet classification, it contains two fields arbitrary rang. In this situation, we may need many TCAM entries to store a classification rule.
In this paper, we propose 2-Level TCAM architecture and relative complete method and strategy for five-dimensional packet classification. The basic idea of our scheme is that we duplicate the address space and we develop a strategy to group all packet classification rules. Besides, we also devise a method to trim the packet classification rules to help us to achieve our goal. Finally, in our proposed scheme, we can keep the advantage of TCAM and we won’t result in large number of packet classification rules.

[1].N. Mohan, M. Sachdev, "Low Power Dual Matchline Ternary Content Addressable Memory," Proc. IEEE ISCAS 2004, Vancouver, pp. 633-636, May 23-26, 2004.

[2].F. Zane, G. Narlikar, and A. Basu, "CoolCAMs: Power-Efficient TCAMs for Forwarding Engines," in Proc. INFOCOM 03, March 2003.

[3].Yeim-Kuan Chang, "Power-Efficient TCAM Partitioning for IP Lookups with Incremental Updates", Lecture Notes in Computer Science, Volume 3391, Jan 2005, Pages 531 – 540

[4].V. Srinivasan, Geroge Varghese, S. Suri, M. Waldvogel, “Fast and scalable layer four switching”, SIGCOMM ’98, Volume 28 Issue4, Oct. 1998.

[5].Florin Baboescu. and Geroge Varghese.. “Scalable packet classification”, ACM SIGCOMM’01, August. 2001.

[6].Yeim-Kuan Chang, “A 2-Level TCAM Architecture for Ranges”, IEEE Transactions on Computers, Volume 55, Issue12, Dec 2006.

[7].Gupta P., McKeown N., “Algorithms for packet classification”, Network, IEEE, Volume 15, Issue 2, pp. 24-32, Mar.-Apr. 2001

[8].Gupta P., McKeown N., “Packet classification using hierarchical intelligient cuttings”, Hot Interconnects VII 1999.

[9].Sumeet Singh, Florin Baboescu, George Varghese, Jia Wang, “Packet classification using multidimensional cutting” ACM SIGCOMM’03, August, 2003.

[10].David E. Taylor, “Surveys and Taxonomy of Packet Classification Techniques”, ACM Computing Surveys, Vol. 37, No. 3, pp. 238-275, Sep. 2005.

[11].T.V. Lakshman and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching”, ACM SIGCOMM '98,

[12].Van Lunteren, J. and Engbersen, T. “Fast and scalable packet classification”, IEEE Journal on Selected Areas in Communications, Volume 21, Issue 4, May 2003 Page(s): 560 – 571.

[13].Ed Spitznagel, Dave Taylor, Jonathan Turner, “Packet classification using extended TCAMs” IEEE International Conference on Network Protocols (ICNP), 2003.

[14].Florin Baboescu and George Varghese, “Scalable packet classification”, ACM SIGCOMM: Special Interest Group on Data Communication, 2001.

[15].Banit Agrawal, Timothy Sherwood, “Modeling TCAM power for next generation network devices”, IEEE International Symposium on Performance Analysis of System and Software (ISPASS-2006).

[16].Ruiz-Sanchez, M.A.; Biersack, E.W.; Dabbous, W, “Survey and taxonomy of IP address lookup algorithms”, IEEE Network, Volume 15, Issue2, March-April 2001 Page(s):8 – 23.

[17].D. E. Taylor and J. S. Turner, "ClassBench: A Packet Classification Benchmark," Tech. Rep. WUCSE2004 -28, Department of Computer Science & Engineering, Washington University in Saint Louis, May 2004.