近年來，一種新型態的網路架構「軟體定義網路」逐漸地受到重視，許多企業、校園、或是資料中心等網路服務提供者紛紛將軟體定義網路應用於該網路環境中以克服當今網路環境的不足之處。透過具有可編程的集中控制，網管人員可以更彈性地管理網路以提高網路資源的利用率、降低操作上所需耗費的成本及促進創新與發展的應用。而第一個用來實現軟體定義網路概念的標準通訊協定是OpenFlow。它是採用flow-based的控制模式來決定該如何轉送封包並且以集中控管的方式來監控整個網路環境的狀態。然而，規則中的欄位是允許有wildcard的存在，這導致規則間存在著相依性的關係，進而造成一個封包可以同時匹配多條規則。在這樣的情況下，OpenFlow採用first-match的機制來決定要選擇哪一條規則。然而，藉由這個機制會使得某些封包比對到不期望的規則，進而造成封包被執行錯誤的動作。此外，隨著網路規模的快速增長以及急劇增加的網路資源需求，管理Flow Table中的規則對於網管人員也變成一項極具挑戰的任務。因此，在OpenFlow網路環境中需要一個自動化衝突偵測方法來偵測規則衝突的問題。在現有的方法中，位元向量方法及聚合位元向量方法已經被廣泛地運用在封包比對上，像是封包分類或在防火牆中被用來偵測規則的衝突。然而，兩種方法皆存在著一些缺點，像是位元向量方法在對單一欄位取聯集或對所有欄位取交集時，它都需要讀取所有的規則，因此在處理上需要花費較多的時間；此外聚合位元向量方法需要回去對應到原本的位元向量，因此會產生額外的mapping back cost。所以，在這篇論文中我們提出縮減位元向量方法來偵測規則的衝突。縮減位元向量方法是基於位元向量及聚合位元向量這兩個演算法並且額外新增兩個方法。一個是Redundancy Reduction，另一個是Group Classification。透過我們的方法可以減少重複的規則，降低儲存的位元數及減少規則被重複讀取的次數。最後，透過實驗結果我們說明縮減位元向量方法比起其他兩個方法來得有效率，包含降低搜尋時間、在某些情況要求較少的記憶體空間、以及在新增或是刪除規則時，可以利用較少的時間來進行更新。

Software-Defined Network (SDN) is a promising networking paradigm that decouples the network control plane from the data forwarding plane. This separation makes it possible to provide network administrators to overcome complexity caused by modern networking environments. With a programmable centralized control, network administrators can create applications that provide a more flexible and agile network management to improve network resource utilization, reduce operating cost, and promote innovation and evolution. OpenFlow is a great concept to realize SDN architecture that simplifies the network and traffic management in enterprise and data center environments by utilizing flow-based control over the OpenFlow switches and providing global view of the network status. It not only utilizes first-matching mechanism to forward packets in the network, but also uses a field of arbitrary bitmask wildcards that have binary flags in the match. However, by applying the first-matching mechanism to match flow entries at a switch may not always produce the desire outcome. This is because flow entries with wildcard fields sometimes create conflicts between flow entries. Thus, the policy selected in this situation may be undesired and wrong action is used for the incoming packet. In addition, with the rapid growth in communication needs for modern networking environments, it is a challenging task for network administrators to manage large amount of flow entries in the flow table. Therefore, an automated conflict detection method is necessary in OpenFlow to identify conflict flow entry problem. In previous studies, the bit vector algorithm (BV) and the aggregated bit vector algorithm (ABV) have been widely applied to packet classification and rule conflict detection in firewalls. So, we studied the applicability of BV and ABV algorithm in OpenFlow to deal with conflict detection in flow entries. However, the BV algorithm reads all bits in processed bit vectors resulting in higher search time and the ABV algorithm could generate excess mapping back cost to detect truly conflicting flow entries. Therefore, inspired by BV and ABV, this thesis presents a conflict detection method called Reduced Bit Vector (RBV) to detect the existence of conflicting flow entries. This is achieved by adopting Redundancy Reduction and Group Classification. The benefits includes that: 1) reducing redundant flow entries in a flow table could decrease memory cost and search time; 2) the number of bits associated with each valid node in each trie is reduced according to Group Classification; 3) some flow entries could avoid repeatedly reading when searching the corresponding tries. Experimental results showed that RBV algorithm requires less search time, lower memory cost, and less incremental update time is required than BV and ABV algorithm for conflict detection in flow entries.

Open Networking Foundation (OpenFlowTM). Available at https://www.opennetworking.org/
McKeown, N. ; Anderson, T. ; Balakrishnan, H. ; Parulkar, G. ; Peterson, L. ; Rexford, J. ; Shenker, S. ; Turner, J., ”Openflow: Enabling innovation in campus networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pages 69-74, April 2008.
Al-Shaer, E. ; Hamed, H., “Discovery of policy anomalies in distributed firewalls,” Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), vol. 4, pages 2605-2616, Mar. 2004.
Al-Shaer, E. ; Hamed, H. ; Boutaba, R. ; Hasan, M., “Conflict classification and analysis of distributed firewall policies,” IEEE Journal on Selected Areas in Communications, vol. 23, no. 10, pages 2069-2084, Oct. 2005.
Lihua Yuan, Hao Chen ; Jianning Mai ; Chuah, Chen-Nee ; Zhendong Su ; Mohapatra, P., “FIREMAN: a toolkit for firewall modeling and analysis,” IEEE symposium on Security and Privacy, 15 pp. - 213, May 2006.
OpenFlow Switch Specification v1.3.4 (Mar. 27, 2014) https://www.opennetworking.org/technical-communities/areas/specification
Natarajan, S. ; Xin Huang ; Wolf, T., “Efficient conflict detection in flow-based virtualized networks,” IEEE International Conference on Computing, Networking and Communications (ICNC), pages 690-696, Feb. 2012.
Lopes Alcantara Batista, B. ; Lima de Campos, G.A. ; Fernandez, M.P., “Flow-based conflict detection in OpenFlow networks using first-order logic,” IEEE Symposium on Computers and Communication (ISCC), pages 1-6, Jun. 2014.
Tong Shen ; Dafang Zhang ; Yanbiao Li ; Guo Li, “A Trie-Based Approach to Fast and Scalable Flow Recognition for OpenFlow,” Computer Science and its Applications Lecture Notes in Electrical Engineering, vol. 330, pages 223-230, 2015.
Hongxin Hu ; Wonkyu Han ; Gail-Joon Ahn ; Ziming Zhao, “FLOWGUARD: building robust firewalls for software-defined networks,” Proceedings of the third workshop on Hot topics in software defined networking (HotSDN’14), pages 97-102, 2014.
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, Oct. 1998.
Gupta, P. ; McKeown, N., “Algorithms for packet classification,” IEEE Network, vol. 15, no. 2, pages 24-32, March-April 2001.
F. Baboescu ; G. Varghese, “Fast and scalable conflict detection for packet classifiers,” Computer Networks, pages 717-735, Jan. 2003.
F. Baboescu, ; G. Varghese, “Scalable packet classification,” IEEE/ACM transactions on Networking, vol. 13, pages 2-14, Feb. 2005.
Ji Li, Haiyang Liu ; Karen Sollins, “Scalable Packet Classification Using Bit Vector Aggregating and Folding,” MIT LCS Technical Memo, April, 2003.
Srinivasan, T. ; Vijayalakshmi, D., “PAFBV: A Novel Parallel Aggregated and Folded Bit Vector Packet Classification Scheme for IPv6 Routers,” Proceedings of The Sixth IEEE International Conference on Computer and Information Technology (CIT ‘06), Sept. 2006.