軟體定義網路是一種新一代的網路架構，它的特色是將網路分成控制層和資料層，並將控制層交由集中式的控制器來管控，讓網管人員可以更靈活的操作和管理網路資源，以滿足不斷變化的網路需求，並且能夠降低操作的成本及改善現存網路的問題。
近年來，許多大型網路例如：雲端、資料中心、大型企業，甚至是校園等網路架構都紛紛加入了軟體定義網路的概念。而OpenFlow是最流行也是第一個用來實現軟體定義網路的通訊協定。OpenFlow在傳遞封包時將封包傳送路徑看成是一條flow，透過flow來判斷如何轉送封包。為了要讓軟體定義網路更加靈活、更有擴展性，軟體定義網路隨後提出了多表的概念來改善單表在面臨龐大且多樣化規則時的問題。因此，當封包擁進時如何快速的在大量規則中找出相對應的規則使得packet classifier的效率變得很關鍵。三元內容可定址記憶體（Ternary Content Addressable Memory，TCAM）是目前學界及業界最常用來解決packet classifier效能問題非常重要的元件，它在尋找路由指向及與封包相對應之規則時的速度比一般的隨機存取記憶體（RAM）要快上許多。然而，TCAM在使用上有一些限制，他的容量很小、價格也很昂貴。因此，它並不適合用在規則量比較龐大的網路環境。另外，當Openflow多表被應用在ㄧ個擁有龐大且人為輸入規則的環境且時，冗餘重複規則是無法避免的。為了要解決這些問題，在OpenFlow的環境中需要一個機制來加快搜尋速度並透過冗餘重複規則的偵測來減少Flow Table中規則的個數，進而避免影響網路的流暢度。因此，這篇論文提出一個可偵測多表中的冗餘規則方法來減少多表中的規則數量。演算法主要分成兩大部分：多表轉單表以及透過建樹的方式來偵測冗餘規則。此外，在建樹時透過了兩種優化的方法來降低建樹所需要的時間和記憶體空間。最後，透過實驗結果可以看出利用這個方法可以在可容忍的時間內有效的減少多表中的規則數量。如此一來，可以降低規則搜尋的時間並且降低所需的硬體成本。

Software-Defined Networking (SDN) has been proposed as a promising paradigm in the next generation networks. SDN addresses the network management problem occurred in the static architectures of conventional networking environment. It decouples the software-based control plane from the hardware-based data forwarding plane, and utilize centralize remote controller to manage the entire network environment. With the programmable controller, the costs of operating a network is reduced and network administrators are able to manage network resources in a more flexible fashion to satisfy the ever-changing networking requirements. OpenFlow is the first standard communication protocol implemented for SDN. Data packets transmitted in OpenFlow is treated as a flow and flow-based control is utilized over OpenFlow-enabled switches to determine how data packets should be forwarded across the network. For a more agile and flexible management over the network, multi-flow table pipeline has been proposed in the later version of OpenFlow specifications to improve the problems when handling a large set of diverse flow entries in a single flow table. Therefore, the effectiveness of the packet classifier becomes the key factor when searching for corresponding flow entries in high traffic loads. Ternary Content-Addressable Memory (TCAM) is the most commonly used component in both industry and academia to address the packet classification performance issues. This is because the processing time of routing and flow entry lookup is much lower than random access memory. However, it is not suitable for the network with large number of flow entries due to its limitation in capacity and its high cost. Furthermore, when multi-flow table pipeline being used in large number of flow entries, sometime redundant flow entries is unavoidable due to unintentional mistake or repeated flow entries made by different network administrators while adding new flow entries. In order to address these problems, a mechanism is needed not only to decrease flow entry lookup time, but also to identify the redundant flow entries in the single or multi-flow tables. Thus, this thesis proposes a multi-flow table reduction algorithm to overcome the redundant flow entry problem in OpenFlow to reduce the number of redundant entries in single or multi-flow tables. The algorithm can be divided into two parts, multi-flow tables to a single flow table conversion and redundant flow entry reduction by constructing an all-match tree. Two optimization methods were used to reduce the process time and memory usage requirement while constructing this tree. From the experiment results, the multi-flow tables reduction algorithm can effectively reduce the number of flow entries in single and multi-flow tables with tolerable time. As a result, the proposed algorithm reduces the processing time of flow table lookup and the memory requirement in multi-flow tables after performing flow entry redundancy reduction mechanism.

[APP07] David L. Applegate ; Gauia Calinescu ; David S. Johnson ; Howard. Karloff ; Katrina Ligett ; Jia Wang, “Compressing rectilinear pictures and minimizing access control lists,” Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pages. 1066-1075, 07-09 January 2007.
[BAB01] Florin Baboescu ; George Varghese, “Scalable Packet Classification,” Proceeding of ACM SIGCOMM '01, pages. 199-210, 27-31 August 2001.
[BAR12] Anat Bremler-Barr ; Danny Hendler, “Space-Efficient TCAM-Based Classification Using Gray Coding,” IEEE Transactions on Computers, vol. 61, pages. 18-30, January 2012.
[DON06] Qunfeng Dong ; Suman Banerjee ; Jia Wang ; Dheeraj Agrawal ; Ashutosh Shukla, “Packet classifiers in ternary CAMs can be smaller,” Proceeding SIGMETRICS of the joint international conference on Measurement and modeling of computer systems, pages. 311-322, 26-30 June 2006.
[INO14] Takeru Inoue ; Toru Mano ; Kimihiro Mizutani ; Shin-ichi Minato ; Osamu Akashi, “Rethinking Packet Classification for Global Network View of Software-Defined Networking,” IEEE 22nd International Conference on Network Protocols, pages. 296-307, 21-24 October 2014.
[LAK98] T. V. Lakshman ; D. Stidialis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, vol. 28, pages. 203-214, October 1998.
[LEN15] Bing Leng ; Liusheng Huang ; Xinglong Wang ; Hongli Xu ; Ying Zhang, “A Mechanism for Reducing Flow Tables in Software Defined Network,” IEEE International Conference on Communications (ICC), pages. 5302-5307, 8-12 June 2015.
[LI03] Ji Li, Haiyang Liu ; Karen Sollins, “Scalable Packet Classification Using Bit Vector Aggregating and Folding,” MIT LCS Technical Memo, April 2003.
[LIU08] Alex X. Liu ; Chad R. Meiners ; Yun Zhou, “All-Match Based Complete Redundancy Removal for Packet Classifiers in TCAMs,” IEEE INFOCOM, pages. 111-115, 13-18 April 2008.
[LIU08] Alex X. Liu ; Eric Torng ; and Chad R. Meiners, “Firewall Compressor: An Algorithm for Minimizing Firewall Policies,” IEEE INFOCOM, pages. 176-180, 13-18 April 2008.
[LIU10] Alex X. Liu ; Mohamed G. Gouda, “Complete Redundancy Removal for Packet Classifiers in TCAMs,” IEEE Transactions on Parallel and Distributed Systems, vol. 21 no. 4, pages. 424-437, April 2010.
[LO15] Chun-Chih Lo ; Pei-Yu Wu ; Yau-Hwang Kuo, “Flow Entry Conflict Detection scheme for Software-Defined Network,” International Telecommunication Networks and Applications Conference (ITNAC), pages. 220-225, 18-20 November 2015.
[MCK08] Nick McKeown ; Tom Anderson ; Hari Balakrishnan ; Guru Parulkar ; Larry Peterson ; Jennifer Rexford ; Scott Shenker ; Jonathan Turner, ”Openflow: Enabling innovation in campus networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pages. 69-74, April 2008.
[MEI09] Chad R. Meiners ; Alex X. Liu ; Eric Torng, “Bit Weaving: A Non-Prefix Approach to Compressing Packet Classifiers in TCAMs,” IEEE International Conference on Network Protocols (ICNP), pages. 93-102, 13-16 October 2009.
[MEI10] Chad R. Meiners ; Alex X. Liu ; Eric Torng, “TCAM Razor: A Systematic Approach Towards Minimizing Packet Classifiers in TCAMs,” IEEE/ACM Transactions on networking, vol. 18, no. 2, pages. 490-500, April 2010.
[ONF11] Open Networking Foundation (OpenFlowTM). Available at
https://www.opennetworking.org/
[OSS11] OpenFlow Switch Specification v1.1.0 (Feb. 28, 2011). Available at
https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.1.0.pdf
[OSS13] OpenFlow Switch Specification v1.3.4 (Mar. 27, 2014). Available at
https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-switch-v1.3.4.pdf
[PAN13] Heng Pan ; Hongtao Guan ; Junjie Liu ; Wanfu Ding ; Chengyong Lin ; Gaogang Xie, “The FlowAdapter: Enable Flexible Multi-Table Processing on Legacy Hardware,” Proceedings of the second ACM SIGCOMM workshop on Hot topics in software defined networking, pages. 85-90, 2013.
[QU13] Yun R. Qu ; Shijie Zhou ; Viktor K. Prasanna, “Scalable Many-Field Packet Classification on Multi-core Processors,” Proceedings of the 25th International Symposium on Computer Architecture and High Performance Computing, pages. 33-40, 23-26 October 2013.