基于SDN的动态负载均衡最优路径算法研究

侯晓婷

(安徽广播电视台播控中心，安徽 合肥 230071)

基于SDN的动态负载均衡最优路径算法研究

侯晓婷

(安徽广播电视台播控中心，安徽 合肥230071)

在传统网络中，转发路径由各路由节点的动态协议决定，传统路径分配算法的全局性差、效率不高，对网络负载平衡的考虑不够，而且管理员难以确定业务报文所走路径。利用SDN改变传统网络对数据流控制的方式，提出一种H-Dijkstra负载均衡最优路径算法。该算法在传统Dijkstra算法的基础上设定一个动态负载均衡阈值，当检测到负载均衡参数超过此阈值，则触发动态调度策略对路径分配算法进行调整。通过反复实验与传统网络对比分析，结果表明，本文算法不仅发挥了SDN在转发与控制分离架构上的速度优势，而且避免了网络资源的浪费，提高了网络性能。

SDN；负载均衡；Dijkstra；最优路径

0 引言

当前，SDN已成为全球网络领域最热门的研究方向。SDN作为一种数据控制分离、软件可编程的新型网络体系架构，采用了集中式的控制平面和分布式的转发平面，控制平面利用控制—转发通信接口对转发平面上的网络设备进行集中式的控制，并提供灵活的可编程能力[1]。SDN可以解决传统网络中的以下问题：(1)传统网络中的转发路径受各种网络协议控制，而且管理员无法直接操控路径转发行为，使得业务部署和路径转发的效率不高[2]；(2)传统网络技术中网络协议对转发行为的影响是固有模式的，比如路由协议只能靠目的IP地址来进行转发，且不同情况下的转发只能对报文进行固定模式的修改，灵活度不高[3]。

相比传统网络，SDN最大的特点是改变了传统网络对数据流进行控制的方式。从设备可编程转变为网络可编程，SDN的网络可编程性实现的是对整个网络的编程而不仅仅是针对单个网络节点。SDN控制器具有全局拓扑，可以计算任意节点间的路由，并控制转发路径[4]。本文利用SDN网络的特点及优势，提出一种H-Dijkstra负载均衡最优路径算法，将其运用在SDN网络，在提高了整个系统的稳定性的同时，保证整体链路动态平衡，避免了局部拥塞，同时将路径的选择进行了最优化。

1 SDN系统架构

近来年，SDN技术迅猛发展，提出了至关重要的网络分层耦合概念，包括转发层、控制层和业务层，如图1所示。数据转发层即物理网络设备、OpenFlow交换机。控制层即网络操作系统，它是SDN的核心，包括链路发现、拓扑管理、转发管理和配置管理等。控制层与转发层间以一种标准化的协议来通信，目前OpenFlow协议最为流行。应用层可以开发各类应用业务，用户可以自由选择网络操作系统并开发自己的网络管理软件和应用[5]。控制层与应用层之间有一个API模块。API 模块由网络管理策略、路由选择和流表下发组成，如图2所示。

图1 SDN网络架构图

图2 应用接口模块

网络管理策略是API模块的核心，负责在控制器上记录功能模块所产生的网络策略。路由选择是在掌握了全网拓扑信息的前提下，为用户访问选择一个最优路径。流表下发是保证控制器产生的流表项成功地下发到转发层。

为了提高处理网络大数据的效率，降低服务器群的处理压力，本文采用在SDN网络架构下对大数据的负载进行均衡处理，这种灵活的可编程架构也非常适用于负载均衡服务，并对网络数据传输的路径进行最优化。

2 H-Dijkstra算法介绍

传统的Dijkstra算法是众多实现最短路径的算法中公认的好算法，且有名的OSPF协议是根据链路状态数据库计算出从本路由器到域内其他所有路由器的最短路径，其中SPF最短路径优先算法也是用的Dijkstra算法[6]。本文沿用传统Dijkstra算法中的精髓思想，并在此算法过程中加入一个动态负载均衡阈值φ，避免局部承载负载过大而造成不必要的拥塞。通过综合因素考虑，选择真正的最优路径。图3给出了整个H-Dijkstra算法的流程框图。

图3 H-Dijkstra算法流程图

(1)SDN控制器遍历所有主机，对整个网络拓扑有个镜像，确定每台主机之间可能的路径集合，预先计算出网络中所有主机之间两辆存在的所有路径，每条路径包括从源主机到目的主机之间所需要经过的所有链路，根据这条路径上所有链路当前可用带宽/链路开销/距离/费用等为每条路径生成一个权重，用此来衡量此路径的均衡程度。

(2)设D=(V,A,W)是一个非负权网络，V=(v1,v2,…,vn)，则D中最短(vi,vj)∈A路径满足方程：

U1=0

(1)

Uj<φ(j=2,3,…,n)

(2)

Uj=min(Uk+Uj) (j=2,3,…,n)

(3)

如果D从定点v1到其余各顶点最短路径长的排序为：

Ui1≤Ui2≤…≤Uin

(4)

当i1=1，即U1=0。

(5)

当k>j时，Uik≥Uij，且Wikij≥0，所以Uij≤Uik+Wikij，即：

(6)

(3)通过上述步骤找到源主机到目的主机的最优路径，需要与系统设定的动态负载均衡阈值φ比较，当检测到负载均衡参数σ(t)超过动态负载均衡阈值φ，则触发并行动态调度策略对负载的路径选择进行动态调整，将超过部分的数据流调度到负载较小的节点上。其中负载均衡参数σ(t)用方差的形式表示：

(7)

UA(t)代表服务器平均负载量，Ui(t)代表服务器节点i在时间t时所承载的负载量。当σ(t)<φ时，全部的数据流选择步骤(2)计算出的最优路径中进行传输；当σ(t)>φ时，动态调整最优路径。

本算法给系统设定一个平衡度，即动态负载均衡阈值φ，避免了多个数据流选择同一条最优路径，通过实时计算，这条路径并非一直都是最优路径，权重会随着负载的增加而增加，如果不采取必要的措施，很有可能造成局部拥塞。本文在保证不超过负载均衡阈值φ的前提下，选择最短路径提高效率，一旦超过阈值φ，控制器将调整最短路径的选择，最终实现动态的负载均衡。

3 H-Dijkstra算法具体实现

根据上述理论分析，具体实施方案采用图4所示的仿真测试结构，SDN控制器会实时记录服务器负载情况。

图4 仿真测试结构

图5为一组由带宽/链路开销/距离/费用等所形成的带权邻接矩阵，用此权重来衡量每条路径的均衡程度，作为选择最优路径的依据。

图5 各主机间权重矩阵图

根据图5矩阵画出网络拓扑结构图如图6所示。假设需要计算节点S5到节点S8的最优路径以及所经过的各节点。通过测试计算出动态负载均衡阈值为120。

图6 仿真网络拓扑结构图

(1)Floodlight控制器遍历每台主机，每台主机遍历整个网络，可以得到从节点S5到节点S8的所有可能路径：

D(S5-S2-S7-S8)=195

D(S5-S6-S7-S8)=260

D(S5-S6-S3-S8)=290

D(S5-S2-S3-S8)=180

……

(2)根据H-Dijkstra算法计算出最优路径为S5-S2-S3-S8，当数据流适中，没有超过所设定的阈值120时，选择S5-S2-S3-S8路径进行数据流传输。一旦负载均衡参数σ(t)>φ，负载发生倾斜，控制器会触发并运行动态调整策略，将后续数据流调度到S5-S2-S3-S7-S8，此时S5-S2-S3-S7-S8这条路径作为当前的最优路径进行数据流的传输，以此类推，以实现整体动态平衡，避免局部拥塞。

4 实验测试及分析

本文选用的仿真测试环境为Ubuntu14.04，在Linux系统下用Mininet搭建网络拓扑图，选用Floodlight控制器，实现最优路径的选择，从而达到负载均衡的目的。通过性能检测，验证H-Dijkstra算法的可行性和高效性。

实验测试同样采用图4所示的仿真测试结构，具体方案采用图6所示的仿真网络拓扑结构。本文选用负载均衡权重值对比分析H-Dijkstra算法与SPF算法的整体性能差异，通过速率对比分析该算法运用在SDN网络架构相比运用在传统网络架构的优势。

图7为传统SPF算法与H-Dijkstra算法的负载均衡对比图，从图6可知整个网络架构共有14条路径。随着业务请求量的增加，之前所选定的最优路径的权重会随之增加，当到达动态负载均衡阈值，H-Dijkstra算法会自动更改所选最优路径，而传统的SPF算法会造成局部拥塞，最终导致业务传输速率降低，整个网络性能下降。

图7 负载均衡对比图

图8为H-Dijkstra算法在传统网络架构与SDN网络架构的速率对比分析图，由于采用了灵活的SDN网络架构，相比传统网络架构，SDN能够集中控制网络，对整个网络进行编程，方便计算任意端点间的路由，并下发流表，控制转发路径，这种网络架构方便了网络管理，极大地提高了业务转发速率。

图8 速率对比图

5 结论

本文针对经典的Dijkstra算法进行研究并优化，提出了H-Dijkstra算法，将其用于SDN网络架构中，此算法可作为内部模块作用于SDN控制器中。本文模拟实际应用场景进行对比实验，证明优化算法能够提高网络数据速度，并简化了网络操作，具有重要的应用价值。

[1] 王勇,匡玉雯.基于SDN的云中心动态负载均衡方法[J].桂林电子科技大学学报,2015,35(4):321-324.

[2] 匡玉雯,王勇,曾小宝. 基于SDN的一种云服务流量控制方法研究[J]. 微型机与应用,2015,34(4):61-63.

[3] 徐秋伊. 基于SDN的路由映射算法的设计与实现[D].北京：北京邮电大学,2015.

[4] 魏凯. 基于蚁群算法SDN负载均衡的研究[D]. 长春：吉林大学,2015.

[5] JIANG J R,HUANG H W,LIAO J H,et al.Extending Dijkstra’s shortest path algorithm for software defined networking[C]. Network Operations & Management Symposium,2014,16th Asia-Pacific,2014:1-4.

[6] 王春枝,罗晨,陈宏伟. SDN中基于负载均衡的最优路径分配算法研究[J].计算机应用研究,2016,33(8):2462-2466.

Dynamic optical path algorithm based on load balancing for SDN

Hou Xiaoting

(Broadcasting Center of Anhui TV Station,Hefei 230071,China)

In traditional network,the forwarding routes are decided by dynamic protocols on routers. The traditional routing algorithms are no-global optimal,low efficient,and usually ignore load balance issues. And system administrator are unaware of the actual path of each traffic flow. Taking the advantage of SDN’s capability to control data flow,this paper gives a H-Dijkstra load balance optimal routing algorithm. Our algorithm adds one dynamic load balance threshold to traditional Dijkstra algorithm. When load balance metric exceeds the threshold,dynamic adjustment to the algorithm’s parameters will be trigger. Compared with traditional network,experiment result shows that our algorithm,which is benefit from SDN’s architecture to separate forwarding plane with control plane,can avoid the waster of network bandwidth and improve network performance.

software defined network(SDN); load balance; Dijkstra; optimal path

TP301

A

10.19358/j.issn.1674-7720.2017.24.019

侯晓婷.基于SDN的动态负载均衡最优路径算法研究J.微型机与应用，2017,36(24)：65-68.

2017-06-27)

侯晓婷(1968-)，女，本科，工程师，主要研究方向：通信网络和网络安全。