# Enforcing Optimal ACL Policies Using K-Partite Graph in Hybrid SDN
## 1 Introduction
In case of in-band connection between SDN switches and the SDN controller and connectivity among SDN controllers, traditional routing protocols are very useful. Thus, by using a hybrid SDN, an SDN controller can be released from these tasks that can be handled by traditional protocols effectively. 5. The SDN infrastructure has recently appeared. OpenFlow switches are not as mature as traditional switches. So, network administrators vacillate to replace traditional network device with SDN devices at once. Hybrid SDN can comfort the transition from traditional network devices to SDN devices. For instance, Google [16] has deployed SDN in several steps over several years for management and control of their data centers. In some scenarios, two SDNs are interconnected by traditional network switches. For these scenarios, hybrid SDN is required to allocate resources for the SDN interconnection suitably. Network policies, like Access Control List (ACL), control the network behavior and are used by the operators to specify the network requirements [25; 26]. The approach for implementation of ACL policies is different in SDN and traditional network as follows. In a traditional computer network, the operators usually implement ACL at the interfaces of switches/routers [1; 2] by using low-level commands. The operators manually plan, design, and then implement these ACL policies according to network requirements. Thus, this approach for implementing ACL is very complicated and error-prone [3; 4; 5]. A misconfiguration can drastically degrade the network performance by enabling unauthorized users to access confidential resources [6]. Moreover, it is also a very expensive process requiring a team of 10-30 members to handle a network of hundred switches [7]. In SDN, ACL policies are specified at the controller, and thus, it is easy to do. Due to the different architecture of hybrid SDN from both SDN and traditional network, hybrid SDN needs new approaches to implement ACL policies. Recently, we have proposed a tree-based approach to implement the ACL policies at legacy network devices through an SDN controller in case of a topology change in hybrid SDNs, the detail of this approach is given in \"Related Work\". However, in this approach, a tree is  
Figure 1: An Example of hybrid SDN scenario: OpenFlow switches are deployed in the distribution network to obtain the benefits of SDN while millions of forwarding entries are handled in the access network by using legacy devices. Figure 2: Example of hybrid SDN in an enterprise network: The network portion in the blue box needs fine-grained control and is upgraded to SDN, while the rest of the network continues to operate with legacy switches. computed and traversed for each policy. It causes high processing overhead and large memory for a network having a large number of policies. In this paper, we propose a single tree construction and traversal for all policies by reducing the processing overhead and reducing memory storage. Moreover, ACL policies may be implemented at the interfaces of legacy network devices in many ways, e.g., near the source nodes, near the destination nodes, at the egress ports and at the ingress ports [27], etc. All these ways for policy implementation have some tradeoffs as follows. If policies are implemented near source nodes, then they require filtration of each packet generated by source nodes. This method incurs extra processing overheads at the switches are attached directly to the source nodes for the packets that do not contradict with the policy. Similarly, if policies are implemented near destination nodes, then we require a large number of implementations according to destination nodes. Furthermore, any change in policy requires much effort and struggle from network operators. It will be explained through examples in the \"Problem Statement\".