Cooperative game theory based network partitioning for controller placement in SDN
Balaprakasa Rao Killi, Ellore Akhil Reddy, Seela Veerabhadreswara Rao · 2018
Software Defined Networking decouples the control plane from the data plane and shifts the control plane to an external entity known as the controller. In large networks, the control plane is distributed among multiple controllers to satisfy fault tolerant and response time requirements. The network is divided into multiple domains, and one or more controllers are deployed in each of these domains. The naive approach for partitioning the network using the k-means algorithm with random initialization results in solutions that are far from optimal. In this paper, we propose a network partition based controller placement strategy by leveraging k-means algorithm with cooperative game theory initialization. The partitioning of the network into subnetworks is modeled as a cooperative game with the set of all switches as the players of the game. The switches try to form coalitions with other switches to maximize their value. It is referred as cooperative k-means for brevity. We also propose two variants of cooperative k-means strategy that tries to produce partitions that are balanced in size. The performance of our proposed strategies are evaluated on networks from Internet 2 OS3E and Internet Topology Zoo. Results demonstrate that our cooperative k-means strategy generates solutions that are close to optimal in terms of the worst case switch to controller latency and outperforms the standard k-means algorithm. Evaluations also demonstrate that the first variant of cooperative k-means produce balanced partitions when the number of partitions is less while the second variant of cooperative k-means always produces balanced partitions.