# Enforcing Optimal ACL Policies Using K-Partite Graph in Hybrid SDN
## 4 Proposed Solution
### Decision Tree Traversing for Multiple ACL Policies  
We have constructed a decision tree that represents the entire network topology i.e., switches, end hosts, routers, etc. We have four policies as discussed in Section 4.2. These policies are implemented at the network device's interfaces according to the requirement. Some policies e.g., near the source, near the destination, implementation schemes are discussed in Problem Statement Section. One scheme has drawbacks or benefits over other schemes, therefore, none of them is perfect. In near the source policy implementation scheme, it requires a large number of ACL rules, and more processing power is required by the network devices to filter the network traffic. In near the destination policy implementation, the number of ACL rules are also proportional to the number of destination nodes, and it requires more bandwidth because packets are dropped after traveling the entire network at the destination nodes, e.g., more unwanted traffic is generated. We need to find such a mechanism which requires a minimum number of rules as well as minimum unwanted traffic. To implement policies optimally, we traverse the tree and find such ports by using K-partite graph traversing. We formed a K-partite Figure 12 for each policy. By computing the shortest path on K-partite graph optimal way of policy, a placement is found. We traverse the decision tree by using a K-partite graph. In this K-partite graph shown in Figure 12, policies P1, P2, P3, etc., are at the leftmost side of the graph while on the other side parti  
Figure 12: K-partite Graph that shows the different combinations of switch port to install ACL policies. Shortest path for entire K-partite graph is calculated that gives the optimal policy implementation points. is formed by using appropriate group number, e.g., G1, G2, G10, etc. The values on the edges of the links represent the number of rules required to implement ACL policy on the respective interface. The tree is traversed by using the Algorithm 2. In this Algorithm 2, firstly we move to the destination node in the tree according to given ACL policy then we start traversing the tree by exploring all the interfaces at each node. If we find source nodes then no rule is installed otherwise we install two for each interface. If there are multiple outgoing interfaces of the switches then rules are installed collectively on these interfaces. We can explore, the different policy implementation ways by traversing the decision tree. Suppose we have a policy P1 = < 10.0.1.1-10.0.1.2, Allowed, 10.0.4.1-10.0.4.2> in which first tuple i.e., 10.0.1.1-10.0.1.2 represents the Source IP and last tuple i.e., 10.0.4.1-10.0.4.2 represents the Destination IP address. According to this policy, only Source IP address, i.e., 10.0.1.1-10.0.1.2 is allowed to access respective Destination IP and all other subnets are not allowed to access this destination. To explore all interfaces for policy implementation, we traverse the decision tree DT by using this policy. Policy can be implemented at a single interface or at multiple interfaces to secure the Destination IP. We form the groups based on the set of interfaces where policies can be implemented. So, these groups are formed on the basis of rules implementation, e.g., a group can have a single interface or multiple interfaces according to the policy. For example, group G1 represent the Destination IP that contains two IP addresses, i.e., 10.0.4.1-10.0.4.2, group G2, G3 contains single IP address, i.e., 10.0.2.2, 10.0.2.1 respectively. We need to calculate the number of rules \(ctr_{ACL}\) and number unwanted transmissions \(ctr_{trans}\) to implement the policy for these respective groups. G is an adjacency list that contains the group's numbers against \(ctr_{trans}\) and \(ctr_{ACL}\) values. In the end, this adjacency list forms a K-partite graph. We traverse the decision tree to find the node linked with the interfaces having Destination IP, i.e., 10.0.4.1-10.0.4.2, node LE2 is the matching one.