# Enforcing Optimal ACL Policies Using K-Partite Graph in Hybrid SDN
## 4 Proposed Solution
### Decision Tree Traversing for Multiple ACL Policies
```
1:Set M = m, d(m) = 0
2:for All neighbor nodes u to m, set d(u) = w(m,u) do
3:for All other non neighbor nodes, set \(d(u)=\infty\)do
4:while\(M\
eq V\)do
5: Choose vertex \(veM\) with \(d(v)\) minimum
6: Set \(M=Mev\)
7:for All neighbor nodes q to v such that \(qeM\)do
8:if d(q) > d(v) + w(v,q) then
9: Set d(q) = d(v) + w(q,v)
10:endif
11:endfor
12:endwhile
13:endfor
14:endfor
```

**Algorithm 3** Shortest Path for K-Partite graph

Optimum policy implementation is an NP-hard problem as there is no polynomial time algorithm to solve this problem. This problem is NP-hard similar to the most famous NP-hard problem which is

Figure 14: K-partite Graph in which link values are combined as a discrete value. Figure 15: K-partite Graph with scaled values of number of rules and number of transmissions. Shortest path for this K-partite graph is calculated that gives the optimal policy implementation points. the decision subset sum problem and the optimization problem of finding the least-cost cyclic route through all nodes of a weighted graph. In Figure 16, interaction among different components of the proposed system is shown. In this system, we get the network topology information from switches and other network devices in the form of a topology graph. A 3-tuple network policy is traversed using a decision tree that governs a K-partite graph. After this step, the shortest path for K-partite graph is computed that indicates the switch ports were policies can be installed optimally, i.e., less number of rules with minimum unwanted traffic. ## 5 Simulation Results

To evaluate the performance of our proposed solution, we developed the complete architecture and algorithms in Mininet [40] and POX controller [41]. We used a random topology generator [42] to produce a different set of network scenarios. We performed these experiments on 64-bit Ubuntu Linux 16.01 LTS operating system that is installed on an HP ENVY Notebook with Intel Core Intel(R) Core(TM) i5-6200U CPU @ 2.30 GHz, 8 GB RAM and 500 GB SATA HDD. The network topology is created using both type of switches, i.e., legacy switches and OpenFlow switches. OpenFlow switches can be used as legacy switches by setting the ovs to fail mode as a \"standalone,\" and these are disconnected from the SDN controller. Some switches and policies are varied for different network topologies. All links are assumed to be bi-directional with a bandwidth of 100 Mbps for each direction. SDN nodes randomly initiate data requests with traffic demands uniformly selected from 512 kbps to 3 Mbps discretely with a step size of 128 kbps. To compute the time for graph traversing, a number of switches are varied as 5, 10, 15, 20, 25, 30, 35, 40, 45, and 50, Similarly, the number of policies also

Figure 16: Flow Chart for proposed solution. varied as 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. We used the following parameters to evaluate the entire performance of the proposed approach:

* **Graph Computation Time:** Graphs are traversed for a specific policy to find appropriate places (interfaces) for rule installation. Firstly, network policy is traversed on the decision tree, and the K-partite graph is created. Secondly, the shortest path is computed on a K-partite graph having a subset of the interface where policies can be installed. * **Traffic Optimization:** Policy implementation plays important role in traffic optimization. If policies are deployed at the proper places, then network congestion can be avoided and traffic losses are eliminated. By using a K-partite graph, we regularized the overall network traffic, so that the minimum number of rules are installed with the best route for network traffic. * **Number of ACL rule versus Number implementations:** To secure the entire network, ACL rules are implemented on the network devices. If we install ACL rules at the egress ports of the switch where end nodes are connected, then the number of rules is directly proportional to the number of nodes.