© Wuhan University 2024

0 Introduction

In order to enhance the scalability and resiliency of Software Defined Network, the distributed multi-controller architecture comes into being, in which each controller manages a sub-network and all controllers cooperate with each other to achieve logically centralized control of the entire network^[1]. Within the distributed architecture, the number and locations of controllers must be designed carefully, as it directly affects the interaction between control and data planes, which in turn influences a wide range of network issues such as the update of routing policy, or the balance of network load^[2]. In this circumstance, the Controller Placement Problem (CPP)^[3] is proposed, which mainly solves the following three sub-problems:

• How to determine the number of controllers?

• How to determine the positions of controllers?

• How to determine the mapping relationships between controllers and switches?

The CPP is a complex problem that depends on the optimization indicators (including communication delay^[4], load balance^[5], network elasticity^[6], etc.), the application scenarios (including Wide Area Networks (WAN), data centers, etc.), and so on. Among all the performance metrics, the communication delay is the first objective that needs to be optimized^[3], which is composed of four types: propagation delay, transmission delay, queuing delay and processing delay. In WAN, the propagation delay dominates^[7], which mainly includes the delay between switches and controllers and the delay between controllers (synchronization delay). Moreover, the former can be further divided into the worst-case delay and the average delay^[8].

Besides the propagation delay, load balance is another important indicator, as the capacity of each controller is limited. If a controller is overloaded for a long time, it is easy to malfunction and then degrade network performance. If a controller is in a light load state prolongedly, a waste of network resources is inevitable^[9]. An ideal load balance is to maintain a uniform distribution of switches among all the controllers.

In our preliminary works, we proposed an algorithm based on network partitioning and cluster fusion, i.e., the Greedy Optimized K-means Algorithm (GOKA)^[10], to solve CPP in terms of reducing the propagation delay. The simulation results showed that GOKA can always promise high performance and precision, with a less than 9.51%error when compared with the global optimal solution.

On that basis, this paper aims to realize multi-objective optimization including the worst-case delay between switches and controllers (represented by SC-worst latency), average delay between switches and controllers (represented by SC-avg latency), synchronization delay among controllers (represented by CC latency) and load balance among controllers. In order to implement this goal, this paper proposes the Multi-objective Greedy Optimized K-means Algorithm (MGOKA), which models a CPP to optimize four objectives, normalizes the problem into a single-objective problem, assigns weights to these objectives adaptively, solves the problem through a combination of greedy and K-means algorithms, and finally outputs the controller placement scheme. The main contributions and novelties of our proposed algorithm are summarized as follows:

• MGOKA proposes an adaptive strategy used for assigning weights to four optimization objectives automatically. Simulation results show that our proposed algorithm performs better than other control groups which assign weights manually by up to 110.0%.

• MGOKA designs a normalization strategy to convert multi-objective into single-objective optimization problems, which can be further applied to solving other optimization problems.

• MGOKA achieves more comprehensive optimization of network performance than other algorithms in different network scales with different numbers of controllers. Simulation results depict that our proposed algorithm improves the network performance by up to 101.5%, 109.9% and 79.8% when compared with K-means, K-means++ and GOKA, respectively. Moreover, the error between MGOKA and the global optimal solution is always less than 4%.

The rest of this paper is organized as follows. Section 1 concludes related works on the CPP of SDN. Our main contributions are described in the following three sections. Section 2 establishes the mathematical models for CPP on multi-objective optimization, and section 3 illustrates our proposed MGOKA. In order to prove the effectiveness of our works, the simulation results are depicted in Section 4. Finally, concluding remarks are given in Section 5.

1 Related Works

Experts from industry and academia have done a lot of research on CPP from different perspectives. In the aspect of application scenarios, the CPP differs in WAN, data centers, wireless networks^[11], and so on. In terms of performance metrics, multiple related works focus on optimizing the communication delay, load balance, network elasticity, deployment cost, and so on, while most works propose controller placement schemes to optimize a single objective, only a portion of works realize the joint optimization of multiple performance metrics.

In terms of algorithms, the state-of-the-art works solve CPP through a random search algorithm, minimum cut algorithm, heuristic algorithm, game-playing algorithm, greedy algorithm, clustering algorithm, etc^[12,13]. Hu et al^[14] proposed a random search algorithm to solve CPP by randomly finding k locations of nodes to place k controllers, while the effect is poor. Ksentini et al^[15] designed a controller placement algorithm based on the minimum cut algorithm by dividing the whole network topology into k subgraphs and making each subgraph be managed by a controller, which can effectively enhance the reliability of the network. Rath et al^[16] imported the non-zero-sum game algorithm to achieve dynamic load balance among controllers, i.e., the algorithm can add or delete controllers adaptively. Sheng et al^[17] put forward a greedy algorithm to determine the positions of k controllers iteratively in order to enhance the network reliability. Wang et al^[18] adopted an improved K-means algorithm to divide the whole network topology into multiple clusters to optimize SC-worst latency.

The heuristic algorithm is an algorithm based on intuitive or empirical construction. Even though satisfactory solutions can be given quickly, only approximate optimal solutions are obtained in most cases. Bari et al^[19] proposed an improved bat algorithm to optimize the average delay and link failure rate simultaneously. Zhang et al^[20] designed an improved particle swarm optimization algorithm to reduce the average delay between switches and controllers and the required number of controllers at the same time. Zilberman et al^[21] combined an improved simulated annealing algorithm with the matrix perturbation theory to solve CPP to calculate the required number of controllers and decide their locations. In contrast, this paper proposes MGOKA to solve CPP in WAN, which combines the greedy strategy with the K-means algorithm to realize the joint optimization of SC-avg latency, SC-worst latency, CC latency and load balance.

2 Problem Formulation

In our previous works, we proposed GOKA^[10] to solve CPP by optimizing a single objective, which is one of SC-avg latency, SC-worst latency and global average latency. Therefore, global average latency is equal to the sum of SC-avg latency and CC-avg latency. Different from the single-objective optimization problem, the multi-objective optimization problem needs to compromise among different performance metrics as they may conflict with each other. For instance, CC latency is incompatible with SC-worst latency. On one hand, in order to reduce the synchronization delay between controllers, controllers should be gathered together. On the other hand, in order to reduce the maximum propagation delay between switches and controllers, controllers should be dispersed as much as possible, otherwise, the edge nodes may experience a longer period to reach controllers. In conclusion, there is generally no solution to promise the simultaneous optimization of multiple objectives, and coordination and compromise must be made among these goals to achieve overall optimization. In general, the multi-objective optimization problem can be modeled as:

$\mathrm{m}\mathrm{i}\mathrm{n}F\left(x\right)={\left[f_{\mathrm{1}}(x),f_{\mathrm{2}}(x),\cdots ,f_n(x)\right]}^{\mathrm{T}},$(1)

subject to:

$x\in \mathrm{\Omega },$(2)

$\mathrm{\Omega }=\left\{X\in {\mathbb{R}}^n|g_i(X)\le \mathrm{0},i=\mathrm{1,2},\cdots ,p\right\}.$(3)

Note that the space where x resides is the set of feasible solutions, and the space where F(x) resides is the target space.

Before modeling the multi-objective problem, the models for optimizing each objective need to be introduced first. The models for optimizing the three types of latencies mentioned above have been given in our previous works^[10], and in this paper, we only describe the model related to load balance. The network topology can be represented as G = (V,E,C), where V = {v₁,v₂,…,v_i} and C ={c₁,c₂,…,c_j} denote the sets of switches and controllers respectively, and E denotes the set of links between nodes. Assume that the number of required controllers is k, the number of switches is m, and the load of each switch is λ, then the load of a controller can be expressed as:

$\mathrm{L}\mathrm{B}(c_j)=\lambda {\displaystyle \sum _{i=\mathrm{1}}^m}{x}_{ij},$(4)

subject to:

$\mathrm{L}\mathrm{B}(c_j)\le \mathrm{L}\mathrm{B}(c_j{)}_{\mathrm{m}\mathrm{a}\mathrm{x}},$(5)

where the binary variable x_ij indicates whether controller c_j is in charge of switch v_i, and LB(c_j)_max refers to the load limit of each controller. On that basis, the total load of all the controllers can be expressed as:

$\mathrm{L}{\mathrm{B}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}={\displaystyle \sum _{j=\mathrm{1}}^k}\mathrm{L}\mathrm{B}(c_j),$(6)

and hence the average load of each controller can be expressed as:

$\mathrm{L}{\mathrm{B}}_{\mathrm{a}\mathrm{v}\mathrm{g}}=\frac{\mathrm{L}{\mathrm{B}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}}{k}.$(7)

In order to measure the load balance degree of the whole network, the load balance degree ξ_LB is proposed which is equal to the standard deviation of the load:

${\xi }_{\mathrm{L}\mathrm{B}}=\sqrt[]{\frac{{\displaystyle \sum _{j=\mathrm{1}}^k}(\mathrm{L}\mathrm{B}(c_j)-\mathrm{L}{\mathrm{B}}_{\mathrm{a}\mathrm{v}\mathrm{g}}{)}^{\mathrm{2}}}{k}}.$(8)

It can be inferred that the smaller the value of ξ_LB is, the more balanced the whole control plane becomes.

After proposing the load balance degree, the CPP for optimizing SC-avg latency, SC-worst latency, CC-latency and load balance degree can be modeled as:

$\mathrm{m}\mathrm{i}\mathrm{n}\sum _{i\in V}\sum _{j\in C}{d}_{ij}{x}_{ij},$(9)

$\underset{i\in V}{\mathrm{m}\mathrm{i}\mathrm{n}}\underset{j\in C}{\mathrm{m}\mathrm{a}\mathrm{x}}{d}_{ij}{x}_{ij},$(10)

$\mathrm{m}\mathrm{i}\mathrm{n}\sum _{e\in E}{d}_e{u}_e,$(11)

$\mathrm{m}\mathrm{i}\mathrm{n}\sqrt[]{\frac{{\displaystyle \sum _{j=\mathrm{1}}^k}(\mathrm{L}\mathrm{B}(c_j)-\mathrm{L}{\mathrm{B}}_{\mathrm{a}\mathrm{v}\mathrm{g}}{)}^{\mathrm{2}}}{k}},$(12)

where d_ijrepresents the minimum propagation latency from switches to controllers. Moreover, formula (11) is used to calculate CC-latency, where d_e is a binary variable indicating whether a link belongs to the control path, and u_edenotes the weight of the link e, proportional to the length of the link. On this basis, this paper proposes a formula to implement a comprehensive optimization of four objectives simultaneously, which will be introduced in Section 3.

3 Algorithm Implementation

In our preliminary works, GOKA is designed to optimize the propagation latency for WAN by combining the process of network partition based on the K-means algorithm with the cluster fusion based on the greedy algorithm. On this basis, MGOKA improves GOKA by importing the multi-objective optimization and normalizing it into a single-objective problem. The algorithm principle is shown in the form of a Venn diagram in Fig. 1. The main steps of MGOKA are similar to GOKA. When the algorithm runs to the cluster fusion stage, the principle of selecting adjacent clusters to fuse is changed from the original optimization of a single type of delay to the simultaneous optimization of multiple objectives as shown in formulas (9) to (12). The flow chart is shown in Fig. 2. In this figure, k^∗ is a multiple of k, which represents the number of clusters in the initialization stage. During the execution of MGOKA, k^∗ gradually decreases until it is equal to k.

Fig. 1 Algorithm principle of MGOKA

Fig. 2 Flow chart of MGOKA

Considering that four objectives may conflict with each other, this paper converts the multi-objective optimization problem into a single-objective optimization problem by the normalization of the four formulas mentioned above. More specifically, at each iteration of cluster fusion, we zoom all the objectives to the same baseline according to the value range and formulate a single optimization goal which is a weighted sum of these objectives. Therefore, the value range of each objective should be solved first. In other words, the maximum and the minimum values of each objective need to be calculated.

The normalization formula of four objectives is modeled as:

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\{a\frac{L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}}-L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{m}\mathrm{i}\mathrm{n}}}{L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{m}\mathrm{a}\mathrm{x}}-L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{m}\mathrm{i}\mathrm{n}}}+b\frac{L_{\mathrm{a}\mathrm{v}\mathrm{g}}-L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{m}\mathrm{i}\mathrm{n}}}{L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{m}\mathrm{a}\mathrm{x}}-L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{m}\mathrm{i}\mathrm{n}}}\\ +c\frac{L_{\mathrm{c}\mathrm{c}}-L_{\mathrm{c}\mathrm{c}\_\mathrm{m}\mathrm{i}\mathrm{n}}}{L_{\mathrm{c}\mathrm{c}\_\mathrm{m}\mathrm{a}\mathrm{x}}-L_{\mathrm{c}\mathrm{c}\_\mathrm{m}\mathrm{i}\mathrm{n}}}+d\frac{\mathrm{L}\mathrm{B}-\mathrm{L}{\mathrm{B}}_{\mathrm{m}\mathrm{i}\mathrm{n}}}{\mathrm{L}{\mathrm{B}}_{\mathrm{m}\mathrm{a}\mathrm{x}}-\mathrm{L}{\mathrm{B}}_{\mathrm{m}\mathrm{i}\mathrm{n}}}\},\end{array}$(13)

subject to:

$a,b,c,d\in [\mathrm{0,0.1,0.2,0.3,0.4},\cdots ,\mathrm{0.9,1.0}],$(14)

$a+b+c+d=\mathrm{1},$(15)

$L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{m}\mathrm{a}\mathrm{x}}>L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{m}\mathrm{i}\mathrm{n}},$(16)

$L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{m}\mathrm{a}\mathrm{x}}>L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{m}\mathrm{i}\mathrm{n}},$(17)

$L_{\mathrm{c}\mathrm{c}\_\mathrm{m}\mathrm{a}\mathrm{x}}>L_{\mathrm{c}\mathrm{c}\_\mathrm{m}\mathrm{i}\mathrm{n}},$(18)

$\mathrm{L}{\mathrm{B}}_{\mathrm{m}\mathrm{a}\mathrm{x}}>\mathrm{L}{\mathrm{B}}_{\mathrm{m}\mathrm{i}\mathrm{n}}.$(19)

In formula (13), L_worst, L_{worst_min}, and L_{worst_max} represent the minimum SC-worst latency after the fusion of adjacent clusters at each iteration, the minimum SC-worst latency of all the controller placement schemes, and the maximum SC-worst latency of all the controller placement schemes, respectively. In order to decide which pair of clusters are chosen to be fused in each iteration, we need to traverse all the pairs of adjacent clusters first. Assume that there are m (k + 1 < m $\le$k^∗) clusters for now, then this round of iteration needs to decrease the number of clusters from m to m-1, and hence total m(m-1)/2 fusion schemes need to be traversed and handled.

The rest symbols in the formula can be deduced similarly. Constraints stipulate that the denominator in equation (13) cannot be zero. Moreover, a, b, c, and d are the weights assigned to four optimization objectives, and their sum is 1. In order to determine the weights of different objectives, this paper proposes an adaptive strategy to decide the weights automatically at every time of merging two clusters, with the pseudo-code shown in Algorithm 1.

Algorithm 1 Adaptive Algorithm to Calculate Parameter Weights

Require: G = (V,E,C), a pair of adjacent clusters x and y, k^∗, k, alternative list

Ensure: a, b, c, d

1: define a new cluster merge cluster, and set it as an empty cluster;

2: merge cluster = x + y;

3: calculate a new center point for the merge cluster based on optimizing SC-worst latency, and calculate SC-worst latency for this controller placement scheme;

4: calculate a new center point for the merge cluster based on optimizing SC-avg latency, and calculate SC-avg latency for this controller placement scheme;

5: calculate a new center point for the merge cluster based on optimizing CC latency, and calculate CC latency for this controller placement scheme;

6: calculate a new center point for the merge cluster based on optimizing load balance degree, and calculate the load balance degree for this controller placement scheme;

7: calculate L_{worst_max}, L_{worst_min}, L_{avg_max}, L_{avg_min}, L_{cc_max}, L_{cc_min}, LB_max, LB_min;

8: for a,b,c,d ∈ [0,0.1,0.2,0.3,0.4,$\cdots$,0.9,1.0] do

9: substitute alternative scheme for alternative list into formula (13), and store the result in function value;

10: calculate the minimum value of function value, and find the corresponding a, b, c, d;

11: end for

12: return;

On that basis, the pseudo-code of our proposed MGOKA is described in Algorithm 2. In the experiments, MGOKA is implemented in Python code which only uses standard data structures such as dictionaries and queues. Moreover, the number of elements in these structures is proportional to the number of switches or controllers. As a result, the spatial complexity of MGOKA is considered to be O(k + m).

Algorithm 2 Multi-Objective Greedy Optimized K-means

Require: G = (V,E,C) , k^∗ , k

Ensure: the final controller placement scheme

1: use Dijkstra's algorithm to calculate the shortest distance between every two nodes;

2: generate k^∗ initial center points and store them in the pointlist;

3: whether to end while = False;

4: while whether to end while==False do

5: assign remaining nodes to initial center points according to the principle of proximity and generate k^∗ clusters;

6: traverse each cluster and calculate a new center point;

7: if k^∗> k then

8: for each cluster x do

9: for each cluster y adjacent to x do

10: assume x and y are merged, and an alternative controller placement scheme is generated;

11: add an alternative controller placement scheme to alternative list;

12: end for

13: end for

14: adopt Algorithm 1 to calculate a, b, c, d, and the result of the formula (13);

15: sort for alternative list according to results of formula (13);

16: merge clusters of alternative list[0] and generate cluster z;

17: delete nodes of cluster x and cluster y;

18: append cluster z, calculate new center point, and store it in the pointlist;

19: k^∗ = k^∗ - 1;

20: end if

21: if k^∗ = k then

22: update center point of each cluster until no changes;

23: whether to end while=True;

24: end if

25: end while

26: return;

As can be seen from the flow chart or the pseudo-code of our proposed MGOKA, the outer loop is executed for k^∗ - k times. Considering that k^∗ is a multiple of k, then these two parameters are of the same order of magnitude. In each loop, every two adjacent clusters are traversed, and the total number of adjacent clusters is equal to k^∗(k^∗ - 1)/2. In terms of each pair of clusters, a new center point needs to be determined and the shortest distance from each switch to this center point needs to be calculated. As the total number of points involved in two adjacent clusters is up to k + m, then the time complexity of MGOKA is O(k³ · (k + m)). As mentioned in Ref. [3], a single controller can meet the response time goals for multiple medium-size networks, then it can be deduced that k is relatively small, and hence MGOKA can output the controller placement scheme with a high speed.

4 Performance Evaluations

4.1 Evaluation Indicator

In order to prove the effectiveness of our proposed MGOKA, a new evaluation indicator named relative optimization rate (represented by η) is given, which considers the four objectives simultaneously. In this paper, we regard the four objectives as equally important. Moreover, we zoom all the objectives to the same baseline according to the corresponding value range to unify the weights of the four objectives, and to make the evaluation metric more convincing. The calculation formula is expressed as:

$\begin{array}{l}\eta =-(\frac{L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{M}\mathrm{G}\mathrm{O}\mathrm{K}\mathrm{A}}-L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}{L_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}+\frac{L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{M}\mathrm{G}\mathrm{O}\mathrm{K}\mathrm{A}}-L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}{L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}\\ +\frac{L_{\mathrm{c}\mathrm{c}\_\mathrm{M}\mathrm{G}\mathrm{O}\mathrm{K}\mathrm{A}}-L_{\mathrm{c}\mathrm{c}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}{L_{\mathrm{c}\mathrm{c}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}+\frac{\mathrm{L}{\mathrm{B}}_{\mathrm{M}\mathrm{G}\mathrm{O}\mathrm{K}\mathrm{A}}-\mathrm{L}{\mathrm{B}}_{\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}{\mathrm{L}{\mathrm{B}}_{\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}}),\end{array}$(20)

subject to:

$\begin{array}{l}{L}_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{t}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}>\mathrm{0},L_{\mathrm{a}\mathrm{v}\mathrm{g}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}>\mathrm{0},\\ L_{\mathrm{c}\mathrm{c}\_\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}>\mathrm{0},\mathrm{L}{\mathrm{B}}_{\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}}>\mathrm{0}.\end{array}$(21)

As shown in formula (20), L_{worst_MGOKA}, L_{avg_MGOKA}, L_{cc_MGOKA}and LB_MGOKArepresent the minimum SC-worst latency, SC-avg latency, CC latency and load balance degree of the controller placement scheme calculated by MGOKA, respectively. While L_{worst_other}, L_{avg_other}, L_{cc_other} and LB_otherrepresent the minimum SC-worst latency, SC-avg latency, CC latency and load balance degree of the calculated controller placement scheme by other baseline algorithms, including K-means, K-means++, GOKA and global optimal solution (derived through the brute force algorithm). The constraint (21) stipulates that each denominator must be greater than zero. In the following experiments, we focus on calculating and comparing the relative optimization rate between MGOKA and other algorithms, as it is significant to pay attention to the overall optimization effect of multiple objectives instead of a single objective in consideration of the possibility that four optimization objectives may conflict with each other.

4.2 Experimental Setup

In this paper, the experimental environment is Intel (R) Core (TM) I7-6700HQ CPU @ 2.60GHz and Windows 10 Pro. In order to prove the effectiveness of MGOKA, we implement our proposed algorithm and other baseline algorithms, including K-means, K-means++ and GOKA in Python. Moreover, we use the thought of exhaustive searching for all possible combinations of controller locations to find the global optimal solution, i.e., the brute force algorithm. The network topologies for experiments contain OS3E, Bellcanada, Interoute, GtsCe, and Cogentco from Internet Topology Zoo^[22] and Internet 2 OS3E, and the information on these topologies is shown in Table 1.

As the original topology files only provide the longitude and latitude information of each node, then a conversion to the propagation latency between network devices is needed, and the calculation rules are described as follows:

1) Obtain information about the total number of nodes, the longitude and latitude of each node, and the connection relations between nodes from the topology files.

2) Transform latitude and longitude data into the 2-dimensional coordinates.

3) Use the Dijkstra algorithm to calculate the physical distance (Euclidean distance) between any two nodes.

4) Divide the physical distance by the propagation speed of the electrical signal to derive the propagation latency.

As the focus of this paper is to propose an algorithm to realize a joint optimization of multiple objectives simultaneously for WAN, the experiments are designed for measuring and comparing the performance of comprehensive optimization instead of a single objective optimization. A total of 5 groups of experiments are conducted to verify the effectiveness of MGOKA, including validity experiments of the adaptive strategy and the normalization strategy used for assigning weights to parameters (Algorithm 1) and transforming multi-objective into single objective optimization, respectively, ablation experiments, and contrast experiment with the global optimal solution.

4.3 Validity Experiment of Adaptive Strategy

In order to verify the effectiveness of our proposed adaptive strategy for assigning weights to parameters (Algorithm 1), a total of 6 groups of experiments with different weights are conducted, and the relative optimization rate is compared. Among all the groups, 5 groups (numbered A, B, C, D and E) are used as the control groups which set weights manually. More specifically, in terms of group A, we assign identical weights to four parameters (0.25 for each), representing an "unbiased" way of allocating weights. This group helps to understand how well the algorithm performs when all optimization objectives are treated as equally important. In terms of groups B, C, D and E, we choose one parameter to be weighted 0.7, and the other three parameters are weighted 0.1 for each. These groups are designed to explore how the algorithm performs when a particular optimization objective is prioritized. In terms of group F, we adopt the adaptive strategy to decide parameter weights automatically.

The topology for experiments is the most frequently used topology, i.e., OS3E, and the number of controllers is set to be 5. In each group of experiments, we adopt MGOKA to decide the final controller placement scheme and to calculate the corresponding SC-avg latency, SC-worst latency, CC latency and load balance degree. On this basis, we calculate the relative optimization rate of group F to other groups to help us understand the specific effects of different weight allocation schemes on algorithm performance and demonstrate the validity of our proposed adaptive strategy. The simulation results are shown in Table 2.

It can be seen from the simulation results that in a group, the parameter with a higher weight corresponds to the minimum value, while other parameters with smaller weights receive poor performance when compared with other groups. However, when comparing the performance of comprehensive optimization, group F always achieves an improvement of the relative optimization rate to other control groups, which verifies that the adaptive strategy for assigning weights to parameters realizes a joint optimization of four parameters simultaneously.

4.4 Validity Experiment of Normalization Strategy

In this subsection, the effectiveness of the normalization strategy is verified through two groups of experiments with four algorithms for comparison. When MGOKA is adopted, we randomly select two or three from the four objectives to optimize, and assign the weights to these chosen objectives according to our proposed adaptive strategy. The topology for experiments is still OS3E, and the number of controllers increases from 3 to 7. Finally, we adopt each algorithm to calculate the final controller placement scheme as well as the corresponding chosen objectives, and calculate the relative optimization rates of MGOKA than the other three baseline algorithms.

In the first group of experiments, two optimization objectives are randomly selected, i.e., SC-avg latency and the load balance degree. When GOKA is adopted, we choose the version that optimizes SC-avg latency. The simulation results are shown in Fig. 3(a). It can be seen from the experimental results that, on one hand, when the randomly chosen two indicators are optimized, MGOKA outperforms remarkably when compared with K-means and K-means++, and the relative optimization rate can reach more than 100%. On the other hand, two GOKA-based algorithms achieve the same relative optimization rate when the number of controllers is equal to 3 or 7, while on other occasions MGOKA outclasses GOKA. More precisely, the range of the relative optimization rate between MGOKA and K-means, K-means++, GOKA is [35.0%, 101.5%], [25.8%, 87.9%] and [0%, 71.1%], respectively. In the second group of experiments, three optimization objectives are randomly selected, i.e., SC-avg latency, CC latency and the load balance degree. When GOKA is adopted, we choose the version that optimizes the global average latency. The simulation results are shown in Fig. 3(b), which are similar to the first group of experiments.

Fig. 3 Validity experiment of normalization strategy

In summary, no matter how many objectives are optimized, no matter what the optimization objectives are, our proposed normalization strategy can always achieve the effect of multi-objective joint optimization. As a result, the wide applicability of the proposed normalization strategy is verified, which means that the normalization strategy can be extended to optimize other objectives in theory, such as network reliability, deployment cost, etc., by substituting all the desired optimization objectives into the formula (13). Moreover, the normalization strategy can also be applied to solving other multi-objective optimization problems.

4.5 Ablation Experiment on Different Numbers of Controllers

In this subsection, MGOKA, GOKA, K-means and K-means++ are compared on the performance of optimizing four objectives with the same network topology OS3E and different numbers of controllers changing from 3 to 7. In order to keep experimental results stable, K-means and K-means++ are executed for 10 times and the average value is calculated for the same number of controllers. When GOKA is adopted, we choose the version that optimizes the global average latency. Similarly, we adopt each algorithm to decide the final controller placement scheme as well as four performance metrics, and then calculate the relative optimization rates of MGOKA to the other three baseline algorithms.

The simulation results are shown in Fig. 4. MGOKA performs better when compared with K-means, K-means++ and GOKA, as the relative optimization rate is usually positive. More precisely, the range of the relative optimization rate between MGOKA and K-means, K-means++, and GOKA is [55.8%, 97.7%], [27.1%, 80.1%], and [0%, 71.1%], respectively.

Fig. 4 Ablation experiment on different numbers of controllers

4.6 Ablation Experiment on Different Network Scales

In this subsection, MGOKA, GOKA, K-means and K-means++ are compared on the performance of optimizing multiple objectives with different network topologies, including Bellcanada, Interoute, GtsCe and Cogentco. In each topology, the number of controllers increases from 3 to 7. Other experimental procedures are similar to Subsection 4.5. The simulation results are shown in Fig. 5. It can be observed that MGOKA has a remarkable effect on multi-objective joint optimization when compared with the other three algorithms in most cases, and GOKA can obtain a solution close to MGOKA in very few cases. As a result, our proposed algorithm can be applied to different network topologies, including medium and large-scale networks, suitable for WAN. More precisely, the range of the relative optimization rate between MGOKA and K-means, K-means++, and GOKA is [2.4%, 92.3%], [1.2%, 109.9%], and [0%, 79.8%], respectively.

Fig. 5 Ablation experiment on different network scales

4.7 Contrast Experiment with Global Optimal Solution

In this subsection, we compare our proposed MGOKA with the global optimal solution on the performance of optimizing multiple objectives. In order to obtain the global optimal solution, we use a brute force algorithm to calculate the global average latency for each controller placement scheme, find out the scheme with the minimum global average latency, and derive the corresponding four metrics. Considering that the brute force algorithm is time-consuming, then we set the number of controllers to be 3, and chose a total of four topologies with different network scales as shown in Table 1. The simulation results are shown in Fig. 6. It can be observed that MGOKA performs better than the global optimal solution in most cases, as the global optimal solution can only promise the minimum global average latency, i.e., the minimum SC-avg latency and CC latency, while may result in an unbalanced load among controllers, leading to a poorer aggregate performance than MGOKA. When applying to Cogentco, even though MGOKA is defeated by the global optimal solution, the error rate is only 4%, which is acceptable. More precisely, the range of the relative optimization rate between MGOKA and global optimal solution is [-4%, 38%].

Fig. 6 Contrast experiment with global optimal solution

5 Conclusion

This paper designs and models a CPP for WAN with multi-objective optimization, including the maximum and average delay between switches and controllers, as well as synchronization delay and load balance between controllers.

To solve this NP-hard problem, we propose an algorithm named Multi-objective Greedy Optimized K-means Algorithm (MGOKA) which combines the process of network partition based on the K-means algorithm with the cluster fusion based on a greedy algorithm, and converts the multi-objective into single objective optimization. As shown in the simulation results, no matter how the controllers' number or network scale changes, MGOKA always performs better than the other three baseline algorithms by up to 109.9%. Moreover, the error between MGOKA and the global optimal solution is always less than 4%. As for our future works, the structure of algorithmic code needs to be optimized to reduce time complexity. Moreover, the multi-objective optimization can be implemented through other manners, such as game theory based methods.

References

All Tables

All Figures

	Fig. 1 Algorithm principle of MGOKA
In the text

	Fig. 2 Flow chart of MGOKA
In the text

	Fig. 3 Validity experiment of normalization strategy
In the text

	Fig. 4 Ablation experiment on different numbers of controllers
In the text

	Fig. 5 Ablation experiment on different network scales
In the text

	Fig. 6 Contrast experiment with global optimal solution
In the text