封包分類在現今的網路設備中是一個非常重要的機制，它通常被使用於如防火牆、入侵檢測系統和服務品質等網路應用中。三態內容可定址記憶體(TCAM)被廣泛地用於基於硬體的封包分類方案中。傳統基於特殊應用積體電路(ASIC)的TCAM有著昂貴、不可擴充的特性。除此之外，這種類型的TCAM通常不能儲存帶有Range格式欄位的規則，儘管一些Range編碼的方法可以解決這個問題，但是確會造成較低的TCAM利用率。相對ASIC來說，FPGA有著可重構與佈署快速的特性，基於記憶體的TCAM設計的方法被提出並應用於現場可程式閘陣列(FPGA)上，然而有著Range格式欄位的規則仍然不能被直接儲存至這種TCAM上。在此論文中，我們提出了一個用於解決Range格式匹配的邊界匹配方法，與基於記憶體的TCAM相比，使用了額外的記憶體以及電路邏輯來進行邊界的匹配。除此之外，我們也在提出的系統中加入了適用於傳統TCAM更新方法的設計。根據於Xilinx Virtex-7 XC7V2000T上的實作結果，我們的系統可以支援12000條以上五維的規則，同時在採用管線化的設計下，系統的時脈頻率相較其他方法並不會有著太大的差距。除此之外，我們也評估了需要花費多少時鐘週期來完成一次規則的更新。

Packet classification is an important mechanism in network infrastructure today, and it is commonly used in network applications such as firewall, intrusion detectors or Quality of Service (QOS). Ternary Content Addressable Memory (TCAM) is widely used in some hardware-based solutions for packet classification. Traditional ASIC-based TCAMs are expensive and unscalable. In addition, this type of TCAM usually cannot store rules with range fields. Although some range encoding methods can solve this problem, it will result in low TCAM utilization. Compare with ASIC, FPGA are reconfigurable and can be deployed fast. RAM-based TCAM have been proposed and implemented on FPGA. However, rules with range fields still cannot be stored directly in the RAM-based TCAM. In this thesis, we proposed the bound-match method to solve the range-match problem. Compare with the RAM-based TCAM, we use additional RAMs and circuit logic to perform bound-match. Besides, we also add the design that is suitable for traditional TCAM update scheme into our system. According to the implementation results on Xilinx Virtex-7 XC7V2000T, the proposed system can support more than 12000 5-tuple rules. Compare with the RAM-based TCAM, the clock rate of the system is not decrease too much by adopted the pipelined design. We also estimate the clock cycles needed to complete the update process of a newly inserted rule.

[1] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, J. Turner, “OpenFlow: enabling innovation in campus networks” In ACM SIGCOMM Computer Communication Review Volume 38 Issue 2, pages 69-74, Apr. 2008.
[2] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. Mckeown, J, Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, D. Walker, “P4: programming protocol-independent packet processors” In ACM SIGCOMM Computer Communication Review Volume 44 Issue 3, pages 87-95, July 2014.
[3] W. Jiang, “Scalable Ternary Content Addressable Memory Implementation Using FPGAs” In Proceedings of the ninth ACM/IEEE symposium on Architectures for networking and communications systems, pages 71-82, 2013.
[4] Y. R. Qu, V. K. Prasanna, “High-Performance and Dynamically Updatable Packet Classification Engine on FPGA” In Journal of IEEE Transactions on Parallel and Distributed Systems Volume 27 Issue 1, pages 197-209, Jan. 2016.
[5] Z. Ullah, K. Ilgon, S. Baeg, “Hybrid Partitioned SRAM-based Ternary Content Addressable Memory” In Journal of IEEE Transactions on Circuits and Systems I: Regular Papers Volume 59 Issue 12, pages 2969-2979, Dec. 2012.
[6] A. Ahmed, K. Park, S. Baeg, “Resource-Efficient SRAM-based Ternary Content Addressable Memory” In Journal of IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 25 Issue 4, page 1583-1587, Apr. 2017.
[7] A. L. Buchsbaum, G. S. Fowler, B. Kirishnamurthy, K. Vo, J. Wang, “Fast prefix matching of bounded strings” In Journal of Experimental Algorithmics (JEA) Volume 8, Article No. 1.3, 2003.
[8] Y. K. Chang, K. Y. Liu, “An Efficient TCAM Update Scheme for Packet Classification” In IEEE 27th International Conference on Advanced Information Networking and Applications (AINA), 2003.
[9] F. Syed, Z. Ullah, M. K. Jaiswal, “Fast Content Updating Algorithm for an SRAM-based TCAM on FPGA” In Journal of IEEE Embedded Systems Letters Volume 10 , Issue 3, pages 73-76, Sept. 2018.
[10] E. Spitznagel, D. Taylor, J. Turner, “Packet Classification Using Extended TCAMs”, In Proceeding ICNP '03 Proceedings of the 11th IEEE International Conference on Network Protocols, pages 120, Nov. 2003.
[11] Y. K. Chang, C. S. Hsueh, “Range-Enhanced Packet Classification Design on FPGA” In Journal of IEEE Transactions on Emerging Topics in Computing Volume 4, Issue 2, pages 214-224, April-June 2016.
[12] Openflow Foundation, “Openflow Switch Specification 1.0.0” Available:
https://www.opennetworking.org/wp-content/uploads/2013/04/openflow-spec-v1.0.0.pdf.
[13] P4.org “P416 Language Specification Version 1.0.0” Available:
https://p4lang.github.io/p4-spec/docs/P4-16-v1.1.0-spec.pdf.
[14] Xilinx, “7 Series FPGAs Data Sheet: Overview Available:
https://www.xilinx.com/support/documentation/data_sheets/ds180_7Series_Overview.pdf.
[15] D. E. Taylor, J. S. Turner, “ClassBench: A Packet Classification Benchmark” in Journal of IEEE/ACM Transactions on Networking Volume 15, Issue 3, pages 499-511, June 2007.
[16] K. Qiu, J. Yuan, J. Zhao, X. Wang, S. Secci, X. Fu, “FastRule: Efficient Flow Entry Updates for TCAM-Based OpenFlow Switches” in IEEE Journal on Selected Areas in Communications Volume 37, Issue 3, page 484-498, Jan 2019