A cross entropy based approach to minimum propagation latency for controller placement in Software Defined Network

In recent years, the Software Defined Network (SDN) has emerged as a pivotal element not only in data centers and wide-area networks, but also in next generation networking architectures. SDN is characterized by decoupled data and control planes with logically centralized architecture. In order to span across the networks and avoid single point of failure, one major challenge in the SDN is to select appropriate locations for controllers to shorten the latency between controllers and switches, especially in wide area networks. For this purpose, we formulate the Controller Placement Problem (CPP) as an integer programming problem, which takes both the communication cost and synchronization cost into account. Due to its high computational complexity, the cross entropy belonging to the field of Stochastic Optimization is proposed and can sample the problem space and approximate the distribution of good solutions. As a result, we propose a cross entropy based approach to solve CPP, and we conduct experiments on 6 real topologies from the Internet Topology Zoo and Internet2 OS3E. The results verify that the proposed approach can realize the minimum propagation latency for different network scales with different number of controllers, with a less than 5.30% margin from the optimal solution. Moreover, the cross entropy can promise the calculation result be stable with a less than 2% margin, and can apply to all the network scales including large network topologies.