A density algorithm for controller placement problem in software defined wide area networks

Through decoupling the data plane from the control planes, the Software Defined Network (SDN) improves the network flexibility and has gained much attention from both academia and industry. In order to apply to Wide Area Network (WAN), the logically centralized and physically distributed multi-controller network architecture is proposed. In this situation, how many controllers are required and where they should be placed is a urgent problem to be solved, which is called the Controller Placement Problem (CPP). This paper discusses the joint optimization of latency and required number of controllers considering revenue cost and network architecture. We propose a Density-based Controller Placement Algorithm (DCPA), which can obtain the optimal number of controllers and then divides the entire network into multiple sub-networks adaptively. In each sub-network, the controllers are deployed with the purpose of minimizing the average propagation latency and the worst-case propagation latency between controllers and switches at the same time. We conduct experiments on 8 real network topologies from the OS3E and Internet Topology Zoo to evaluate the performance of algorithm. The results verify that DCPA can always find out the optimal solution with a low time consumption to reduce latency for different network scales, which reduces latency by up to 46, 11 and 7 when compared with Density-Based Controller Placement (DBCP), Pareto-based Optimal COntroller placement (POCO) and Clustering-based Network Partition Algorithm (CNPA), respectively, and reduce the load of controllers by up to 38, 20 and 13 when compared with DBCP, POCO and CNPA, respectively. As a result, our proposed DCPA can decrease the controller cost, propagation latency and controller load simultaneously when solving CPP.