Computer Science

CLC number: TP393.2

MGOKA: A Multi-Objective Optimization Algorithm for Controller Placement Problem Combining Network Partition with Cluster Fusion in Software Defined Network

MGOKA：一种面向SDN控制器部署问题的结合网络划分与簇融合的多目标优化算法

School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China

^† Corresponding author. E-mail: wenjinglv@sues.edu.cn

Received: 28 April 2024

Abstract

Software Defined Network (SDN) has been developed rapidly in technology and popularized in application due to its efficiency and flexibility in network management. In multi-controller SDN architecture, the Controller Placement Problem (CPP) must be solved carefully as it directly affects the whole network performance. This paper proposes a Multi-objective Greedy Optimized K-means Algorithm (MGOKA) to solve this problem to optimize worst-case and average delay between switches and controllers as well as synchronization delay and load balance among controllers for Wide Area Networks (WAN). MGOKA combines the process of network partition based on the K-means algorithm with cluster fusion based on the greedy algorithm and designs a normalization strategy to convert a multi-objective into a single-objective optimization problem. The simulation results depict that in different network scales with different numbers of controllers, the relative optimization rate of our proposed algorithm compared with K-means, K-means++, and GOKA can reach up to 101.5%, 109.9%, and 79.8%, respectively. Moreover, the error rate between MGOKA and the global optimal solution is always less than 4%.

摘要

软件定义网络(SDN)由于其在网络管理上的高效性和灵活性得到了迅速发展和广泛应用。在多控制器的SDN架构中，控制器部署问题(CPP)是直接影响全网性能的关键问题。针对CPP中的通信延迟和负载均衡等重要性能指标，本文在前期基于网络划分和聚类融合的贪心优化K-means算法(GOKA)的基础上，提出了面向多目标的贪心优化K-means算法(MGOKA)来优化广域网中交换机与控制器之间的最坏情况时延、平均时延，以及控制器之间的同步时延、负载均衡。MGOKA将基于K-means的网络划分过程和基于贪心算法的簇融合过程进行了有机结合，设计了一种归一化策略以将多目标优化问题转换为单目标优化问题。仿真结果表明，在具有不同规模的网络拓扑中，使用不同数量的控制器，本文所提出的算法始终优于K-means、K-means++和GOKA算法，相对优化率最大分别提升了101.5%、109.9%和79.8%。此外，MGOKA与全局最优解的误差始终小于4%。