三態內容尋址記憶體(TCAM)現今已成為一個非常廣泛被用於儲存封包分類規則的硬體裝置。TCAM擁有快速且可確定性時間完成查詢等優點，但是當儲存於TCAM中的規則需要被更新的時候，為了確保TCAM對於封包分類查詢時的正確性，如何有效管理這些規則就成為了一個非常重要的議題。一般的做法是維護一個輔助資料結構來計算TCAM中需要被搬動的規則，在本論文中，我們使用 TCAM 搜索操作來查找可以移動的規則而不需使用輔助資料結構，從而減少輔助資料結構帶來的內存負擔。此外，我們將討論一個在過去的工作中沒有考慮過的問題，當前的論文有一個共同的假設，規則的優先級是已知的。換句話說，當新增一條規則時，在模擬過程中新規則的優先級已由管理者預先定義。事實上，管理者也必須花時間定義新規則的優先權，這些時間成本也應該計算在內。我們提出了一種新穎的自動數據包分類器 TCAM 更新方案。自動意味著SDN控制器可以通過算法在執行時期定義規則的優先級。實驗結果表明，我們只需要額外的幾個TCAM搜索操作就可以完成新規則的優先級定義和TCAM插入兩件事情。最後，我們的方案考慮了OPENFLOW的多維規則對TCAM資源使用引起的空間爆炸問題，提出了TCAM/CAM混合架構。我們的架構根據大部分OPENFLOW字段都是精確值的特點來降低TCAM資源的使用量。通過計算，該架構可降低硬件成本約20%。

Ternary content addressing memory (TCAM) has now become a very widely used hardware device for storing packet classification rules. TCAM has the advantages of fast and deterministic time to complete the query, but when the rules stored in the TCAM need to be updated. In order to guarantee the correctness of the TCAM for packet classification and query, how to effectively manage these rules becomes an important issue. The general approach is to maintain an auxiliary data structure to calculate the rules that need to be moved in TCAM. In this paper, we use TCAM search operations to find movable rules without using auxiliary data structures, thereby reducing the memory burden caused by the auxiliary data structure. In addition, we will discuss a problem that has not been considered in the past work. The current paper has a common assumption that the priority of the rules is known. In other word, when a newly rule be inserted, the priority of the newly rule has been pre-defined by the manager during the simulation. In fact, manager must also spend time to define priority of newly rules, and these time costs should also be included. We propose a novel automatic packet classifier TCAM update scheme. Automatic means that the SDN controller can define the priority of each rules during the execution period through an algorithm. The experimental show that we only need a few TCAM’s search operations to complete the priority definition of the newly rules and TCAM insertion. Finally, our solution considers the space explosion problem caused by the use of TCAM resources by OPENFLOW's multi-dimensional rules, and proposes a TCAM/CAM hybrid architecture. Our architecture reduce usage of TCAM resources based on the characteristic that most of the OPENFLOW fields are accurate values. Via calculation, our proposed architecture can reduce hardware costs by about 20%.

[1] M. Adiletta, M.R. Bluth, D. Bernstein, G. Wolrich, and H. Wilkinson, “The Next Generation of Intel IXP Network Processors,” Intel Technology J., vol. 6, no. 3, pp 6-18, 2002.
[2] Xianfeng Li, Yuanxin Lin and Wenjun Li, “GreenTCAM: A memory- and energy-efficient TCAM-based packet classification,” 2016 International Conference on Computing, Networking and Communications (ICNC).
[3] F. Zane, G. Narlikar, and A. Basu, “CoolCAMs: Power-efficient TCAMs for Forwarding Engines”, IEEE INFOCOM, 2003.
[4] A. L. Buchsbaum, G. S. Fowler, B. Krishnamurthy, K.-P. Vo, and J. Wang, "Fast Prefix Matching of Bounded Strings", ACM Journal of Experimental Algorithmics, vol. 8, Jan. 2003.
[5] Wenjun Li, Xianfeng Li and Hui Li “MEET-IP: Memory and Energy Efficient TCAM-Based IP Lookup”, 2017 26th International Conference on Computer Communication and Networks (ICCCN).
[6] Y.-K. Chang, C.-I. Lee, and C.-C. Su, “Multi-field range encoding for packet classification in TCAM,” in IEEE Infocom Mini-Conference, 2011.
[7] Ori Rottenstreich, Isaac Keslassy, Senior Member, IEEE, Avinatan Hassidim, Haim Kaplan, and Ely Porat, “Optimal In/Out TCAM Encodings of Ranges,” in IEEE Infocom Mini-Conference, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 24, NO. 1, FEBRUARY 2016.
[8] Tal Mizrahi, Ori Rottenstreich, and Yoram Moses, " TIMEFLIP: Using Timestamp-Based TCAM Ranges to Accurately Schedule Network Updates," IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 25, NO. 2, APRIL 2017.
[9] Eric Norige, Alex X. Liu , and Eric Torng, " A Ternary Unification Framework for OptimizingTCAM-Based Packet Classification Systems," IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 26, NO. 2, APRIL 2018.
[10] Xitao Wen, Bo Yang , Yan Chen, Li Erran Li, Kai Bu , Peng Zheng , Yang Yang and Chengchen Hu, " RuleTris: Minimizing Rule Update Latency for TCAM-based SDN Switches," 2016 IEEE 36th International Conference on Distributed Computing Systems.
[11] Bohan Zhao, Rui Li, Jin Zhao and Tilman Wolf, " Efficient and Consistent TCAM Updates," IEEE INFOCOM 2020 - IEEE Conference on Computer Communications.
[12] Kun Qiu, Jing Yuan, Jin Zhao, Xin Wang, Stefano Secci and Xiaoming Fu, " Efficient and Consistent TCAM Updates," IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 37, NO. 3, MARCH 2019.
[13] H. Song and J. Turner, “Fast Filter Updates for Packet Classification using TCAM”, GLOBECOM, 2006.
[14] T. Mishra and S.Sahni, “DUOS – Simple Dual TCAM architecture for routing tables with incremental update”, IEEE Symposium on Computers and Communications, 2010.
[15] T. Mishra and S.Sahni, “PC-DUOS: Fast TCAM Lookup and Update for Packet Classifiers”, ISCC - International Symposium on Computers and Communications, pp.265-270,2011.
[16] Tania Banerjee, Sartaj Sahni, Fellow, and Gunasekaran Seetharaman, “PC-DUOS+: A TCAM Architecturefor Packet Classifiers”, IEEE TRANSACTIONS ON COMPUTERS, VOL. 63, NO. 6, JUNE 2014.
[17] Tania Banerjee, Sartaj Sahni, Fellow and Gunasekaran Seetharaman, “PC-TRIO: A Power Efficient TCAM Architecture for Packet Classifiers”, IEEE TRANSACTIONS ON COMPUTERS, VOL. 64, NO. 4, APRIL 2015.
[18] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, "Algorithms for Advanced Packet Classification with Ternary CAMs," SIGCOMM’05, 2005.
[19] F. Yu and R. H. Katz, "Efficient Multi-Match Packet Classification with TCAM”, Hot Interconnects, August, 2004.
[20] F. Yu, T.V. Lakshman, M. A. Motoyama, and R. H. Katz, “SSA: A power and memory efficient scheme to multi-match packet classification,” in Proc. Symp. Architect. Netw. Commun. Syst., Oct. 2005.
[21] D. E. Taylor and J. S. Turner, “ClassBench: A Packet Classification Benchmark”, IEEE/ACM Transactions on Networking, Volume 15, No. 3, pp.499-511,June 2007.
[22] Peng He, Wenyuan Zhang, Hongtao Guan, Kave Dalamatian, and Gaogang Xie, “Partial Order Theory for Fast TCAM Updates”, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL.26, NO. 1, FEBRUARY 2018
[23] Kai-Yang Liu and Yeim-Kuan Chang, "An Efficient TCAM Update Schme for packet Classification", The IEEE 27th International Conference on Advanced Information Networking and Applications (AINA-2013), June, 2013 .
[24] Jiří Matoušek, Gianni Antichi, Adam Lučanský, Andrew W. Moore, Jan Kořenek, “ClassBench-ng: Recasting ClassBench After a Decade of Network Evolution”, 2017 ACM/IEEE Symposium on Architectures for Networking and Communications
[25] Balajee Vamanan and Gwendolyn Voskuilen, " EffiCuts: Optimizing Packet Classification for Memory and Throughput", SIGCOMM 2010.
[26] OpenFlow Switch Specification Version 1.5.1 ( Protocol version 0x06 ), https://opennetworking.org/wp-content/uploads/2014/10/openflow-switch-v1.5.1.pdf.
[27] K. Pagiamtzis; A. Sheikholeslami, " Content-addressable memory (CAM) circuits and architectures: a tutorial and survey ", IEEE Journal of Solid-State Circuits, Vol.26, Issue.3, March 2006.