# Enforcing Optimal ACL Policies Using K-Partite Graph in Hybrid SDN
## 4 Proposed Solution  
To handle the problems discussed in Section 3, we proposed a systematic and efficient way for implementing multiple ACL policies in hybrid SDN by using a single decision tree with embedding optimization parameters (as discussed in Section 4.1). We model the hybrid SDN (HN) as \((H)=(V,L)\), where \(L\) is the set of undirected links and \(V\) represents the set of vertices, i.e., switches, routers. \(V\) consists of two types of switches, \(V=(T\cup O)\) where \(T\) is set of traditional (legacy) switches, and \(O\) represents a set of OpenFlow switches. For this network, a path from a source node c to destination node d such that \(c\
eq d\) is presented as a set to traversed edges that is represented mathematically as \(p(c,d)=c,v_{1},v_{2},...v_{k},d\) and where \(v_{1},v_{2}...v_{k}\epsilon\{T\cup O\}\). To minimize the number of policies and number of transmissions is a combinatorial problem, in which we must search such combinations of ports, where a minimum number of policies are required with a minimum number of transitions for unwanted traffic. Combinatorial problems involve finding a grouping, ordering, or assignment of a discrete, finite set of objects that satisfies given conditions. Candidate solutions are combinations of solution components that may be encountered during a solution attempt but need not satisfy all given conditions. Implementation of P policies on V vertices (switches) involves a set of combinations switch ports where policies are installed to secure the network. Furthermore, optimum policy implementation is also an NP-hard problem as there is no polynomial time algorithm to solve this problem. This problem is NP-hard like the most famous NP-hard problem (the decision subset sum problem) and the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph. We have to adopt the following strategies to implement policies optimally. Let c(v) represent the limit on the total number of ACL rules that can be configured on a switch v, including all its interfaces and in both traffic directions.  
**Minimum Rules Strategy:** The operator wants to use a minimum number of rules on all switches in the network. Let \(V=V_{1},V_{2},V_{3},....V_{m}\) represents the number of switches, \(P=P_{1},P_{2},P_{3},....P_{n}\) represent number of policies, \(R(U_{i})\) refers to number of rules on \(U\) switches to implement \(P_{i}\) where \(U\)\(\leqslant\)\(V\), and \(U=U_{1},U_{2},U_{3},....U_{k}\).  
\[Min\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k=1}^{l}R((P_{i})(V_{j})) \tag{1}\]  
**Minimum Unwanted Traffic Strategy:** Let Tr indicate the minimum unwanted traffic, it means that unwanted traffic should not go around the network. It should be dropped as early as possible. The operator wants to install rules on switches \(v\) in such way so that there is a minimum amount of unwanted traffic generated. Formally:  
\[Min\sum Tr(v) \tag{2}\]  
In Figure 10, we have shown the overall design of our system by showing the components and their interaction with the external environment. Efficient policy configuration systems consist of three main components. The first component is a decision tree construction showing the interconnection of network devices through links. The second component declares the policies that governed the data traffic. The third component considers the multiple policies configuration using decision tree traversing together with the K-partite graph.