封包分類是一項經過充分研究的技術，他提供許多網路管理功能像是防火牆、流量控制、負載平衡。在軟體定義網路中，藉由分離出控制平面以及資料平面，控制平面負責制定網路的轉發政策。因此藉由控制平面的全域視野，允許SDN應用程式提供更多精巧的服務像是網路驗證、錯誤定位以及虛擬網路隔離等等。這些應用程式都仰賴封包的網路行為(network-wide behavior)，也就是封包在網路交換機中的動作組合。然而因為標頭空間被複雜的劃分，傳統的封包分類方法不能很好的用於全域網路的封包分類問題。
在這篇論文中我們提出一個兩階段的封包分類架構，能夠有效的解決全區域網路架構中，多個規則表與路由表混和的封包分類問題。第一階段對各個維度的輸入值做區段編碼的處理，第二階段對編碼後的結果做雜湊來達快速的封包分類查詢。在多維度的規則表中，規則的有些維度可能是wildcard，這樣的規則會導致建立雜湊表時發生記憶體使用量過大的問題。為了解決這個問題，我們根據各個維度是否為wildcard對規則進行分組，並為每個組建立雜湊表來減少記憶體使用量。
透過用雜湊表來存取規則，我們可以解決cross-product產生過大的記憶體使用量的問題，同時提供快速分類吞吐量。同時我們的方法支持增量更新。

Packet classification is a well-studied technology, which provides many network management functions such as firewalls, traffic control, and load balancing. In software-defined networking, the control plane is responsible for defining the network's forwarding policy by separating the control plane and the data plane. Therefore, with the global view of the control plane, SDN applications are allowed to provide more sophisticated services such as network verification, fault localization, and virtual network isolation. These applications rely on the network-wide behavior of the packets, which is the combination of actions of switches in the network. However, due to the complicated partitioning of the header space, the traditional packet classification method can’t well support the packet classification problem of the global network.
In this thesis, we propose a two-stage packet classification architecture that can effectively solve the packet classification problem of a global network where multiple routing tables and rule tables are mixed. In stage 1, we encode the field values of the input header separately. In stage 2, hash tables are used for the encoded values to achieve high classification speed. Some of the header fields in the multidimensional rule table may be wildcards, and these rules cause a memory explosion problem with the hash table. To solve this problem, we group the rules based on whether each dimension is wildcard or not and create a hash table for each group to reduce memory usage.
Using the hash table to access rules can solve the problem of excessive memory usage generated by cross-product while providing fast classification throughput. Also, our scheme supports incremental updates compared to the BDDs and MDD.

[1] R.E. Bryant, “Graph-based algorithms for boolean function manipulation,” IEEE Transactions on Computers, C-35(8):677–691, 1986.
[2] A. Srinivasan, T. Ham, S. Malik, and R.K. Brayton, “Algorithms for discrete function manipulation,” in IEEE ICCAD, pp. 92–95, 1990.
[3] H. K. Yang and Simon S. Lam, “Real-time Verification of Network Properties using Atomic Predicates,” in 21st IEEE International Conference on Network Protocols (ICNP), 2013.
[4] H. Z. Wang, C. Qian, Ye Yu, H. K. Yang and Simon S. Lam, “Practical network-wide packet behavior identification by AP classifier,” in IEEE/ACM Transactions on Networking, vol. 25, pp. 2886-2899, 2017.
[5] T. Inoue, T. Mano, K. Mizutani, S. Minato, and O. Akashi, “Rethinking Packet Classification for Global Network View of Software-Defined Networking,” in IEEE 22nd International Conference on Network Protocols (ICNP), pp. 296-307, 2014.
[6] T. Inoue, T. Mano, K. Mizutani, S. Minato, and O. Akashi, “Fast packet classification algorithm for network-wide forwarding behaviors,” in Computer Communications, vol. 116, pp. 101-117, 2018.
[7] D. E. Taylor, “Survey and Taxonomy of Packet Classification Techniques,” in ACM Computing Surveys, vol. 37, no. 3, pp. 238-275, Sep. 2005.
[8] M. Kuzniar, P. Peresini, and D. Kostic, “What you need to know about SDN flow tables,” in Proc. PAM, pp. 347–359, 2015.
[9] S. Kandula, S. Sengupta, A. Greenberg, P. Patel, and R. Chaiken, “The nature of data center traffic: Measurements & analysis,” in Proc. ACM IMC, pp. 202–208, 2009.
[10] T. Benson, A. Akella, and D. A. Maltz, “Network traffic characteristics of data centers in the wild,” in Proc. ACM IMC, pp. 267–280, 2010.
[11] D.E. Taylor and J.S. Turner, “ClassBench: a packet classification benchmark,” IEEE/ACM Trans. Networking, vol. 15, no. 3, pp. 499-511, Jun. 2007
[12] S. Jain et al., “B4: Experience with a globally-deployed software defined WAN,” in Proc. ACM SIGCOMM, pp. 3–14, 2013.
[13] A. Feldman and S. Muthukrishnan, “Tradeoffs for Packet Classification,” in Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 1193-1202 vol.3, 2000.
[14] F. Baboescu, G. Varghese, “Scalable Packet Classification,” IEEE-ACM Transactions on Networking, vol. 13, no. 1, pp. 2-14, Feb. 2005.
[15] F. Geraci, M. Pellegrini, and P. Pisata, “Packet Classification via Improved Space Decomposition Techniques,” in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 304-312 vol. 1, 2005.
[16] H. J. Chao, “Next Generation Routers,” in Proceedings of the IEEE, vol. 90, no. 9, pp. 1518-1558, Sep. 2002.
[17] H. Lu, S. Sahni, “O(log W) Multidimensional Packet Classification,” in IEEE/ACM Transactions on Networking, vol. 15, no. 2, pp. 462-472, Apr. 2007.
[18] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary. “Algorithms for Advanced Packet Classification with Ternary CAMs,” in Proceedings of the ACM SIGCOMM ’05 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM ’05), pp. 193 – 204, 2005.
[19] R. Cohen and D. Raz, “Simple Efficient TCAM based Range Classification,” in Proc. IEEE Conf. Commun. (INFOCOM’11), pp. 196-200, Apr. 10-15, 2011.
[20] H. Song and J. W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection Using FPGA,” Proc. Thirteenth ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA), 2005.
[21] W. Jiang and V. K. Prasanna, “Scalable Packet Classification on FPGA,” IEEE Transactions on vary large scale integration (VLSI) systems, vol. 20, no. 9, pp. 1668–1680, 2012.
[22] J. M. Wagner, W. Jiang and V. K. Prasanna, “A Scalable Pipeline Architecture for Line Rate Packet Classification on FPGAs,” Proc. The 21st IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS), 2009.
[23] P. Gupta and N. McKeown, “Algorithms for Packet Classification,” in IEEE Network, vol. 15, no. 2, pp. 24-32, Mar.-Apr. 2001.
[24] P. Gupta and N. McKeown, “Packet Classification Using Hierarchical Intelligent Cuttings,” in Proceedings. IEEE High-Performance Interconnects, pp. 34-41, 1999.
[25] T. V. Lakshman and D. Stiliadis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” in Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, pp. 203-214, 1998.
[26] P. Gupta, and N. McKeown, “Packet Classification on Multiple Fields,” in Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pp. 147-160, 1999.
[27] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet Classification Using Multidimensional Cutting,” in Proceedings. ACM Special Interest Group on Data Communication, pp. 213-224, 2003.
[28] Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, “Cuckoo Filter: Practically Better Than Bloom,” in 10th ACM International on Conference on emerging Networking Experiments and Technologies, 2014, pp.75-88.
[29] B. Vamanan, G.Voskuilen, T. Vijaykumar, “EffiCuts: Optimizing Packet Classification for Memory and Throughput,” in ACM SIGCOMM, 2010.
[30] Y. C. Cheng and P. C. Wang, “Packet Classification Using Dynamically Generated Decision Trees,” in IEEE Transactions on Computers, vol. 64, pp. 582-586, 2015.
[31] Y. K. Chang and C. Y. Chien, “Layer Partitioned Search Tree for Packet Classification,” in IEEE 26th International Conference on Advanced Information Networking and Applications, pp. 276-282, 2012.
[32] Y. K. Chang and H. C. Chen, “Layered Cutting Scheme for Packet Classification,” in IEEE 25th International Conference on Advanced Information Networking and Applications (AINA-2011), 2011.
[33] Y. K. Chang and K. Y. Liu, “An Efficient TCAM Update Scheme for Packet Classification,” in IEEE 27th International Conference on Advanced Information Networking and Applications, pp. 1017-1024, 2013.
[34] Y. K. Chang and Y. H. Wang, “Cubecuts: A Novel Cutting Scheme for Packet Classification,” in Proc. IEEE Workshops Int. Conf. Adv. Inf. Netw. Appl, 274–279, 2012.
[35] Y. K. Chang, “Efficient Multidimensional Packet Classification with Fast Updates,“ IEEE Transactions on Computers, vol. 58, no. 4, pp. 463-479, Apr. 2009.
[36] Y. K. Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding,” Computer Networks, vol. 51, no. 3, pp. 588-605, Feb. 21 2007.
[37] Y. K. Chang, C. C. Su, Y. C. Lin, and S. Y. Hsieh, “Efficient Gray Code Based Range Encoding Schemes for Packet Classification in TCAM”, IEEE/ACM Transactions on Networking, pp. 1201-1214, 2013
[38] Y. K. Chang, Y. S. Lin, and C. C. Su, “A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification,” Proc. the International IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), pp.215 - 218, 2010.
[39] Y. K. Chang and Y. C. Lin, “Dynamic Segment Trees for Ranges and Prefixes”, IEEE Transactions on Computers, pp. 769-784, 2007.
[40] Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li, "Packet Classification Algorithms: From Theory to Practice," in Proceedings of INFOCOM 2009, pp. 648-656, 2009.
[41] W. Li, X. Li, “HybridCuts: a scheme combining decomposition and cutting for packet classification,” IEEE Hot Interconnects symposium, pp. 41–48, 2013.
[42] S. Yingchareonthawornchai, J. Daly, A.X. Liu, E. Torng, “A sorted partitioning approach to high-speed and fast-update OpenFlow classification,” in IEEE International Conference on Network Protocols, pp. 1–10, 2016.
[43] V. Srinivasan, S. Suri, G. Varghese, “Packet classification using tuple space search,” ACM SIGCOMM, pp. 135–146, 1999.
[44] A. Liu, C. Meiners, E. Torng, “TCAM razor: a systematic approach towards minimizing packet classifiers in tcams,” IEEE/ACM Transactions on networking, pp. 490–500, 2010.