為了讓網際網路執行多樣的運用，封包分類是一項很重要的功能包含服務品質、封包安全、封包監控及多媒體傳輸。為了將封包分類到特殊串流或其他串流，網路節點必須依封包的欄位去搜尋封包分類規則表。通常可以用軟體或硬體的方法來搜尋封包分類規則表。三元內容位址記憶體(TCAM)是應用在封包分類上的硬體解決方法。
　　當我們使用TCAM來儲存封包分類規則表時，TCAM儲存Port Range使用到大量的TCAM空間。在最差的情況下，儲存W-bits的Range將需要O(W) 的Prefixes的空間。考慮標準五維的規則表，包含來源及目的的Port Range。若將這n個五維的規則儲存至TCAM時，最差情況下需要儲存O(nW2) Prefix。我們必須壓縮封包分類規則表並有效率的儲存在TCAM中
　　本論文中我們提出一個方法，我們對Prefix重新作編碼，使得Prefix Entry的數目減少且同時減少單一Entry的位元數。在九個模擬產生的規則表中，可以利用壓縮的方式節省67%~83% 的TCAM空間。且在最差的情況下, 從O(nW2)縮減成O(nlog2n)使得TCAM有效率的儲存封包分類規則表。

　　Packet classification is an enabling function for a variety of Internet applications including Quality of Service, security, monitoring, and multimedia communications. In order to classify a packet as belonging to particular flow or set of flows, network nodes must perform a search over a set of filters using multiple fields of the packet as the search key. In general, there have been two major threads of research addressing packet classification: software and hardware. A Ternary Content Addressable Memory (TCAM) is a hardware solution for packet classification.
　　When we store the classification tables in TCAM, it will waste too much TCAM space since the port fields of the classification tables are arbitrary ranges. In the worst-case, it needs O(W) prefixes for a range in W-bit address space. Consider the standard 5-tuple rule tables in which source and destination ports are ranges. The worst-case number of prefix entries is O(nW2) if we store n 5-tuple rules in TCAM. For efficiently using the TCAM space, we need to compress the classification table in an efficient way.
　　In this thesis, we propose a scheme that can compress the TCAM space efficiently. The scheme first re-encode the port field of the classification tables, hence, we can use less number of bits to represent the port field. Moreover, each arbitrary range in port fields can be stored in only few TCAM entries. Experiment results conducted according to nine synthetic classification tables indicate our scheme save 67-83 percent of the TCAM space. In worst case, the TCAM storage complexity is reduced from O(nw2) to O(nlog2n).

[1] David E. Taylor, “Survey & Taxonomy of Packet Classification Techniques”, WUCSE-2004-24, May 10, 2004
[2] P. Gupta and N. McKeown, “Algorithms for Packet Classification”, in IEEE Network, Vol.15, Issue 2, pp. 24-32, March-April 2001
[3] H. Liu, “Routing table compaction in ternary CAM”, in IEEE Micro, Vol. 22, Issue 1, pp. 58-64, Jan-Feb 2002
[4] M. S. Chen and K. G. Shin, “Processor allocation in an N-cube multiprocessor using gray codes”, in IEEE Tran. on Computers archive, Vol.36, Issue 12, pp. 1396-1407, Dec 1987
[5] 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.
[6] T. Lakshman and D. Stiliadis, “High-speed policy-based packet forwarding using efficient multi-dimensional range matching,” in Comput. Commun. Rev., Vol.28, no. 4, pp. 203–214, Oct 1998
[7] Van Lunteren J. and Engbersen T, “Fast and scalable packet classification” in IEEE Journal on Selected Areas in Communications, Vol. 21, Issue 4, pp. 560-571, May 2003
[8] David E. Taylor and Jonathan S. Turner, “ClassBench: A Packet Classification Benchmark,” WUCSE-2004-28, May 21 2004.
[9] S.H. Huang, L.E. Lee and M.L. Huang, “A Special Purpose Content Addressable Memory for Network Packet Classifier”, in 2004 Symposium on Digital Life and Internet Technologies, Taiwan, 2004.
[10] E. Spitznagel, D. Taylor, and J. Turner, "Packet Classification Using Extended TCAMs," in Proceedings of IEEE International Conference on Network Protocols (ICNP), 2003.