# Enforcing Optimal ACL Policies Using K-Partite Graph in Hybrid SDN
## 4 Proposed Solution
### Decision Tree Traversing for Multiple ACL Policies
7:while Node in DT do
8:if node in destination list then
9: Find all similar nodes and create a group \(G_{i}\)
10: Count number of \(ctr_{ACL}\) and \(ctr_{trans}\) for \(G_{i}\)
11:\(P_{i}\) is connected to \(G_{i}\) forming a K-partite graph
12:if Other Interfaces exist then
13:if Interface in _Source IP_ list then
14: No rule installed
15:else
16:if Single Interface then
17: Group \(G_{i}\) is formed for this interface
18: Count number of \(ctr_{ACL}\) and \(ctr_{trans}\) for \(G_{i}\)
19:\(G_{i}\) is added to K-Partite graph
20:endif
21:if Multiple Interfaces then
22: Take all interfaces jointly, count two rules for each
23: For each interface separate group \(G_{i}\) is formed
24: Count number of \(ctr_{ACL}\) and \(ctr_{trans}\) for \(G_{i}\)
25: All \(G_{i}\) is added to K-Partite graph in connecting each other in a series
26:endif
27:endif
28:endif
29:else
30:if Node is leaf then
31: Explore other similar nodes (leaves) connected to the switch
32:if Nodes Interfaces in _Source IP_ list then
33: No rule installed
34:else
35: Create group \(G_{i}\) of all similar leaves connected to the switch
36: Count number of \(ctr_{ACL}\) and \(ctr_{trans}\) for \(G_{i}\)
37:\(G_{i}\) is added to K-Partite graph
38:endif
39:endif
40:if Other Interfaces exist then
41:if Single Interface then
42: Group \(G_{i}\) is formed for this interface
43: Count number of \(ctr_{ACL}\) and \(ctr_{trans}\) for \(G_{i}\)
44:\(G_{i}\) is added to K-Partite graph
45:endif
46:endif
47: Take all interfaces jointly, count two rules for each
48: For each interface separate group \(G_{i}\) is formed
49: Count number of \(ctr_{ACL}\) and \(ctr_{trans}\) for \(G_{i}\)
50: All \(G_{i}\) is added to K-Partite graph in connecting each other in a series





For multiple choices, we add edges in K-partite graph in parallel format, i.e., G9, G11, and G12. For the collective implementation of ACL policies edges are added in series form, i.e., G8, G9, G13. In this way, all the interfaces are processed, and finally, a complete K-partite graph emerges as shown in Figure 12.

In K-partite graph, each link has two values, i.e., \(\mathit{ctr}_{\mathit{ACL}}\) and \(\mathit{ctr}_{\mathit{trans}}\); by adding these values a single link value is computed as shown in Figure 14. K-partite graph shows a lot of options to install network policies on different network devices. By calculating the shortest path for the K-partite graph using Algorithm 3, a set of options are indicated where policies can be installed. To find actual policy placement subset of groups, we assume that four transmissions are equal to one policy rule as policy implementation requires more computation power and resources than transmission. We have computed the link value by keeping a policy rule similar to four transmissions that are shown in Figure 15. From Figure 15, the shortest path is 64 for path G8, G11, G16, and G18. If ACL policies are deployed at these interfaces, one can observe limited unwanted traffic as well as a minimum number

Figure 13: Step by step formation of K-partite graph. (**a**) A group G1 is formed that is attached with node P1 forming a K-partite graph; (**b**) A group G2 is formed that is attached with node P1 forming a K-partite graph; (**c**) A group G3 is formed that is attached with node P1 forming a K-partite graph; (**d**) Multiple groups G4–G7 are added to graph forming a K-partite graph; (**e**) Groups G8, G9 and G10 are added in the K-partite graph as a series of edges for collective ACL implementations. of ACL rules. Similarly, for other network policies, K-partite graphs are formed, and by applying the shortest path algorithm, a set of interfaces can be found where policies can be implemented optimally.