GOKA: A Network Partition and Cluster Fusion Algorithm for Controller Placement Problem in SDN

Software Defined Networking (SDN) is a new promising network architecture, with the property of decoupling the data plane from the control plane and centralizing the network topology logically, making the network more agile than traditional networks. However, with the continuous expansion of network scales, the single-controller SDN architecture is unable to meet the performance requirements of the network. As a result, the logically centralized and physically separated SDN multi-controller architecture comes into being, and thereupon the Controller Placement Problem (CPP) is proposed. In order to minimize the propagation latency in Wide Area Network (WAN), we propose Greedy Optimized K-means Algorithm (GOKA) which combines K-means with greedy algorithm. The main thought is to divide the network into multiple clusters, merge them greedily and iteratively until the given number of controllers is satisfied, and place a controller in each cluster through the K-means algorithm. With the purpose of proving the effectiveness of GOKA, we conduct experiments to compare with Pareto Simulated Annealing (PSA), Adaptive Bacterial Foraging Optimization (ABFO), K-means and K-means++ on 6 real topologies from the Internet Topology Zoo and Internet2 OS3E. The results demonstrate that GOKA has a better and more stable solution than other four heuristic algorithms, and can decrease the propagation latency by up to 83.3%, 70.7%, 88.6% and 64.5% in contrast to PSA, ABFO, K-means and K-means++, respectively. Moreover, the error rate between GOKA and the best solution is always less than 10%, which promises the precision of our proposed algorithm.

Automated summary

Software Defined Networking (SDN) is a new network architecture that decouples the data plane from the control plane and centralizes the network topology logically, making it more agile than traditional networks. The single-controller SDN architecture is insufficient for large networks, leading to the proposal of a multi-controller architecture and the Controller Placement Problem (CPP). To minimize propagation latency in WAN, the Greedy Optimized K-means Algorithm (GOKA) is proposed, which divides the network into clusters, merges them greedily, and places a controller in each cluster using K-means algorithm. Experimental results show that GOKA outperforms other heuristic algorithms in terms of stability and solution quality, reducing propagation latency significantly.