由於三態內容尋址記憶體(TCAM)擁有快速的查詢速度以及在確定性時間完成查詢等優點，TCAM現今已成為一個非常廣泛被用於儲存封包分類規則的硬體裝置。但是當儲存於TCAM中的規則需要被更新的時候，如何管理這些規則就成為了一個非常複雜的議題。為了確保TCAM對於封包分類查詢時的正確性，被新增的規則必須要被置入正確的位置。除此之外，為了維持規則之間的重疊關係以及優先權的排序之正確性，有些規則可能必須被搬動。一般而言，一個輔助性的資料結構需要被維護以及用來計算如何新增規則至TCAM或從TCAM中刪除規則。但是，這個輔助性的資料結構通常很複雜且需要占用許多記憶體空間。在這篇論文當中，我們提出一個有效使用記憶體的方式，即使用少部分的TCAM查詢週期來計算在更新規則的時候如何搬動這些相關的規則而不是維護一個輔助性的資料結構。這麼一來，可以省下用於儲存這個輔助性資料結構的大量記憶體。在這篇論文之中，我們採用了與其他已存在的方法相同的假設，即所有的規則都擁有不同的優先權。一般而言，規則在資料庫中的索引值可被當成優先權值。在這篇論文的實驗結果顯示出我們的更新方法只有利用了少部分TCAM查詢週期，然後在記憶體使用量上比其他已存在的方法都還要好。除此之外，實驗結果也顯示出我們的方法與CoPTUA方法比較需要搬動較少次的規則就可以完成更新。

Ternary Content Address Memory (TCAM) becomes a popular hardware device for storing the packet classifiers due to its high and deterministic lookup performance. However, managing the filter set in TCAM is quite complicated when filters need to be updated. To ensure the correctness of search results, it is necessary to obtain the right position in TCAM for storing the new filters. In addition, some filters need to be moved to other positions for maintaining the correct filter overlapping relationship based on their priorities. Normally, an auxiliary data structure is maintained to compute how to insert or delete a filter into/from TCAM. However, this auxiliary data structure is usually complicated and large. Instead of maintaining an auxiliary data structure, in this thesis, we propose a memory-efficient TCAM update scheme that simply uses a very small portion of TCAM search cycles to compute how to move the filters related to the filter to be inserted or deleted. Therefore, a large amount of memory for storing the auxiliary data structure for updates can be avoided. In our experiments, we use the same assumption in other existing schemes that all of the filters have different priorities. Generally, the indices of the filters in the database are used as priorities. The experimental results show that our scheme requires less memory compared with all existing schemes while only a small portion of TCAM search cycles are required for calculation. In addition, our update scheme needs less number of TCAM entry moves than the existing CoPTUA update scheme [16].

[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] M. Akhbarizadeh and M. Nourani, “Efficient Prefix Cache for Network Processors,” IEEE Symposium on High Performance Interconnects.
[3] F. Baboescu, G.Varghese, “Fast and Scalable Conflict Detection for Packet Classifiers,” IEEE International Confererence on Network Protocols 2002.
[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] 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.
[6] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, "Algorithms for Advanced Packet Classification with Ternary CAMs," SIGCOMM’05, 2005.
[7] J. Lunteren and T. Engbersen, "Fast and Scalable Packet Classification," IEEE Journal on Selected Areas in Communications, vol. 21, Issue 4, pp.560-571, May 2003.
[8] T. Mishra and S. Sahni, “Consistent Updates for Packet Classifiers,” IEEE Transactions on Computers 2012.
[9] T. Mishra and S.Sahni, “DUOS – Simple Dual TCAM architecture for routing tables with incremental update”, IEEE Symposium on Computers and Communications, 2010.
[10] 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.
[11] R. Panigrahy and S. Sharma, "Reducing TCAM Power Consumption and Increasing Throughput," Proc. Hot Interconnects, 2001.
[12] D. Shah and P. Gupta, “Fast Incremental Updates on Ternary-CAMs for Routing Lookups and Packet Classification”. In HotI, 2000.
[13] H. Song and J. Turner, “Fast Filter Updates for Packet Classification using TCAM”, GLOBECOM, 2006.
[14] 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.
[15] B. Vamanan and T.N. Vijaykumar, “TreeCAM: Decoupling Updates and Lookups in Packet Classification,” CoNEXT 2011.
[16] Z. Wang, H. Che, M. Kumar, and S.K. Das, “CoPTUA: Consistent Policy Table Update Algorithm for TCAM without Locking”,IEEE Transactions on Computers, 53, 12, pp.1602-1614. December 2004.
[17] F. Yu and R. H. Katz, "Efficient Multi-Match Packet Classification with TCAM”, Hot Interconnects, August, 2004.
[18] 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.
[19] F. Zane, G. Narlikar, and A. Basu, “CoolCAMs: Power-efficient TCAMs for Forwarding Engines”, IEEE INFOCOM, 2003.
[20] K. Zheng, H. Che, Z. Wang, and B. Liu, "An Ultra High Throughput and Power Efficient TCAM based IP lookup Engine," Proc. IEEE INFOCOM, 2004.