Approximation Algorithms for Controller Placement Problems in Software Defined Networks
Tianshu Li, Zhaoquan Gu, Xiao Lin, Shudong Li, Qingfeng Tan · 2018
Software Defined Networks (SDNs) have been a new paradigm to separate the network control plane from the data forwarding plane. Controller placement is one fundamental problem which identifies the number of controllers and the placement of these controllers. Time to reach and control each node in the network is denoted as latency and no provably-efficient algorithms have been proposed under various latency constraints. In this paper, we initialize the study of controller placement problems in SDNs under two different latency constraints. The first one is to design efficient placement algorithms when the maximum or average latency is bounded. We derive that the controller placement problem becomes NP-hard under such latency constraints and propose approximation algorithms to identify the minimum number of controllers. The other one is balanced cost-latency placement, which seeks to minimize a function considering both the controller cost (setup and maintain) and the latency. We also propose a constant approximation algorithm based on the primal dual approach. We conducted these algorithm on real network topologies and the simulation results validate our theoretical analyses.