# An Optimization Routing Algorithm Based on Segment Routing in Software-Defined Networks
## 3 Algorithm Design
### Proposed Optimization Algorithm for Link Weight
\begin{array}{cc}\text{dgbest}(t)&|\Delta E(t)|< \delta_{\text{c}}\\ \text{cgbest}(t)&|\Delta E(t)|>\delta_{\text{c}}\end{array} \right. \tag{4}\]  
where dgbest(\(t\)) is the solution with the best diversity at the \(t\)-th iteration; cgbest(\(t\)) is the solution with the best convergence at the \(t\)-th iteration. \[\text{dgbest}(t)=\text{argmin}DV(x_{i}(t)) \tag{5}\]  
where \(DV(x_{i}(t))\) denotes the diversity degree of the \(i\)th solution \(x_{i}(t)\). \[DV(x_{i}(t))=\left|\overline{d}-d_{i}\right| \tag{6}\]  
where \(\overline{d}\) is the average value of all \(d_{i}\), and the operation formula of \(d_{i}\) is as follows:  
\[d_{i}=\min_{j=1,\ldots,|P|,j\
eq i}\left\{\sum_{m=1}^{M}\left|f_{m}(x_{i})-f_{ m}(x_{j})\right|\right\} \tag{7}\]  
Figure 2: Pareto front in parallel cell coordinate system. where \(M\) represents the number of objective functions; \(P\) represents the best solution set on the approximate Pareto front; \(f_{m}(x_{i})\) represents \(m\)-th objective function value of \(x_{i}\). \[\text{cgbest}(t)=\text{argmin}CV(x_{i}(t)) \tag{8}\]  
where \(CV(x_{i}(t))\) is the convergence degree of the \(i\)-th solution. \(CV(x_{i}(t))\) is defined as:  
\[CV(x_{i}(t))=\min_{1\leq j\leq|P^{*}|}\sqrt{\sum_{n=1}^{M}{(\frac{f_{m}(x_{i})- f_{m}(x_{j}^{*})}{f_{m}^{\text{max}}-f_{m}^{\text{min}}})^{2}}} \tag{9}\]  
where \(P^{*}=\{x_{1}^{*},x_{2}^{*},\ldots,x_{|P^{*}|}^{*}\}\) represents the best solution set on the real Pareto front. In the following part, we set the objective functions. We use a weighted graph \(\mathbf{G}=(\mathbf{V},\mathbf{E})\) to present the network topology of SDN, where \(\mathbf{V}\) represents the set of nodes and \(\mathbf{E}\) represents the set of edges. For each link, there is a link capacity \(c(\mathbf{e})\) and weight \(w(\mathbf{e})\). Let \(f(\mathbf{e})\) denote the total amount of traffic flows carried by the link \(e\). Thus, \(u(\mathbf{e})=f(\mathbf{e})/c(\mathbf{e})\) denotes the link utilization of the link \(\mathbf{e}\). The goal of traffic engineering is to maintain \(u(\mathbf{e})\leq 1\) for any \(\mathbf{e}\in\mathbf{E}\), but this goal is too general. We define the function in (10), which describes the link cost:  
\[\psi(\mathbf{e})=\left\{ \begin{array}{ll}u(\mathbf{e}),&0\leq u\Big{(}\mathbf{e})<\! \frac{1}{3}\\ 3u(\mathbf{e})-\frac{2}{3},&\frac{1}{3}\leq u(\mathbf{e})<\!\frac{2}{3}\\ 10u(\mathbf{e})-\frac{16}{3},&\frac{1}{3}\leq u(\mathbf{e})<\!\frac{9}{10}\\ 70u(\mathbf{e})-\frac{178}{3},&\frac{9}{10}\leq u(\mathbf{e})<1\\ 500u(\mathbf{e})-\frac{1468}{3},&1\leq u\Big{(}\mathbf{e})<\!\frac{11}{10}\\ 5000u(\mathbf{e})-\frac{16318}{3},&\frac{11}{10}\leq u(\mathbf{e})<\!\infty\end{array} \right. \tag{10}\]  
According to (10), we can see that the cost increases faster and faster with the growth in link utilization. When the link utilization rate is close to 1 (the link is congested), the cost rises sharply. A link with high link utilization rate has a high cost, which imposes a punitive high cost on the overloaded link. Therefore, when seeking a path, the allocation scheme to avoid link overload will be chosen. The cost of a path is not only related to link utilization but also to the length of the path. We take the sum of the cost of all the links on a path as the cost of this path. The cost function of path \(\mathbf{p}\) is defined as follows [28]:  
\[\cos\text{t}(\mathbf{p})=\!\sum_{\mathbf{e}\in\mathbf{p}}\psi(\mathbf{e}) \tag{11}\]  
The variance of the link utilization expresses the load balance. The smaller the variance, the more balanced the load distribution is. Let \(\overline{u}\) denote the average link utilization. The formula of load balance is expressed as:  
\[\sigma=\sum_{\mathbf{e}\in\mathbf{p}}{(u(\mathbf{e})-\overline{u})}^{2}/h(\mathbf{p}) \tag{12}\]  
where \(h(\mathbf{p})\) denotes the hop counts of path \(\mathbf{p}\).