基于软件定义网络的数据中心网络负载均衡算法研究*

樊自甫，张 丹，李 书

(重庆邮电大学通信与信息工程学院，重庆 400065)

1 引言

传统的数据中心采用专用的负载均衡设备实现网络资源的有效利用，存在设备成本昂贵和可扩展性差等问题，而基于软件定义网络SDN(Software Defined Networking)[1,2]的集中化方式能够简化网络管理，降低运营成本。对于负载均衡技术而言，软件定义网络提供了一种成本低廉、灵活性强的流量管理。SDN是一种新型的网络架构，采用了集中式的控制平面和分布式的数据平面，两个平面相互分离。随着数据中心在全球范围内开始得到广泛的应用，数据中心流量也急剧增长，传统数据中心网络存在运行效率低、链路利用率低、易拥塞等问题，而下一代网络技术(如SDN技术)的出现为数据中心网络当前的问题提供了解决方案。然而，基于SDN 的数据中心网络存在着链路负载分布不均匀的的问题，解决基于SDN的数据中心网络负载均衡问题能有效地提高网络资源利用率，降低设备管理复杂度。

目前根据对流的传输方式的不同，可以将基于SDN的负载均衡算法分为以下三种：

第一种是流分割后再传输方法。如文献[3]提出的流分割策略，将控制器匹配到的大流进行分割后再进行传输。文献[4]根据Fat-Tree拓扑的特征，将路径分为上行和下行路径，并根据下一跳链路负载情况选择最佳路径，并当检测到大流时将其进行分割，再将其分配到路径中。该类方案需要对大流进行分割，且重路由仅考虑了下一跳，可能导致网络负载不均衡，甚至拥塞。

第二种是流聚合后再传输方法。针对当前数据中心网络中主要是针对大流进行调度容易产生小流拥塞的问题，文献[5]提出了MiceTrap方案，该方案将网络中的小流聚合后，再根据计算的路径权重对聚合后的流进行多路径转发。对流进行分割或聚合后再进行负载均衡，虽然能将负载分布得更为均匀，但没有高效的方案解决包失序的问题。

第三种是流透明传输方法，也是当前负载均衡的主流方案。例如，文献[6]提出了模糊综合评估机制FSEM(Fuzzy Synthetic Evaluation Mechanism)实现路径负载均衡。文献[7]提出了基于数据中心网络Fat-Tree拓扑的动态负载均衡DLB(Dynamic Load Balancing)算法，通过单跳贪婪策略为最大的流选择最优下一跳链路，该算法仅通过单跳贪婪策略为流量选路，难以避免算法的局限性，从而引发网络拥塞。文献[8]针对数据中心网络的折叠式Clos网络架构提出了选择性随机负载均衡SRL(Selective Randomized Load Balancing)和FlowFit两个不同的实现方案。SRL是对随机负载均衡的增强，类似于等价多路径ECMP(Equal Cost MultiPath)的随机路由[9]，但并不是随机选择一条路径，而是随机选择两条路径并将最大的流分配到负载最低的路径中。文献[10]提出了负载均衡算法LABERIO，该方案采用最大最小剩余带宽法为流量选择最佳下一跳链路，将最高负载链路上的最大的流调度到负载最小的链路上。

综上所述，当前的负载均衡方案主要是直接将最高负载链路上的最大流调度到最低负载链路，并没有考虑整条链路的负载情况，可能由于瓶颈链路而造成局部拥塞。同时，直接对链路上的最大流进行调度，不仅可选路径少，甚至可能由于频繁调度大流，导致网络性能下降。针对上述算法存在的一些不足，本文提出了一种基于SDN的负载均衡算法，该算法对容易引起网络拥塞的大流进行调度，将高负载链路的流调度到低负载链路，以降低最大链路负载，并使整个网络的链路负载尽量均衡。

2 负载均衡算法设计

2.1 算法思路

数据中心网络的流量具有局部性和动态性、分布不均匀、明显的大小流等特征，本文充分利用SDN 网络架构的集中式控制优势，提出一种基于SDN的数据中心网络负载均衡算法。具体的算法流程如图1所示。

Figure 1 Flow chart of load balancing scheduling图1 负载均衡调度流程图

首先，控制器通过链路层发现协议LLDP(Link Layer Discovery Protocol)获取并更新全局网络拓扑。然后，控制器向OpenFlow交换机发送OFPT_STATS_REQUEST消息，以获取所需的链路统计信息和流的统计信息。根据获取的链路统计信息，控制器进一步为网络中的路径设置一个权重，选择权重最小的路径对流进行传输。其次，为了衡量网络负载均衡程度，进一步设置一个负载均衡度。最后，根据调度的流的大小和路径当前负载状况，选取合适的大流进行调度。若该链路上存在多条满足条件的大流，则优先调度更大的流。当流调度和负载均衡完成后，对路径的权值进行更新。

2.2 负载均衡算法实现

2.2.1 算法模型

网络描述：给定SDN网络拓扑加权图G=(V,E)，其中V={v1,v2,…,vn}为网络链路中的非空节点集，E={e1,e2,…,en}为各节点之间的链路集。数据包从源节点S传输到目的结点D的路径记为P，且路径P由m条链路构成，记为P={l1,l2,…,lm}。网络中共有n条链路，拓扑中每条链路的负载分别为{L1,L2,…,Ln}。

(1)

LMax=max{L1,L2,…,Ln}

(2)

LFi=1-Li

(3)

式(1)定义负载为当前已占用的链路带宽百分比。其中，Li表示链路i的负载，Bi表示链路i的已占用带宽，Ci表示链路i的最大可用带宽。由式(2)可知网络中的最大链路负载为LMax，而链路的空闲负载可用式(3)表示。由式(3)可看出第i条链路的空闲负载为LFi。

2.2.2 算法流程

(1)路径选择。

为了均衡链路负载和网络流量，避免流量在某条链路过度集中和链路拥塞的产生，首先需要将路径的空闲带宽作为路径权重的考虑因素。同时，为了使整个网络链路负载和流量分布更均匀，可将路径中所有链路负载的标准差作为路径权重另一个考虑因素。本文目标是最小化最大链路负载。

(4)

由式(4)可计算出路径权重，其中WPath表示路径权重，LFi表示链路i上的空闲负载。由式(4)可知，路径权重WPath是路径空闲负载的标准差和平均值比值。路径平均空闲负载越大，路径权重WPath越小，表明该路径平均可用带宽越大，传输性能越好。标准差越小，路径权重WPath越小，表明该路径负载离散程度小，越不易引发局部链路拥塞，该条路径传输性能越好。

在数据传输过程中还需要进一步考虑路径跳数，因此需要对路径的选择进行一定的约束。当控制器为流计算路径时，首先检测源主机与目的主机是否与同一边缘层交换机相连。若连接到相同的边缘层交换机，则将路径跳数限制为一跳。若连接的是不同的边缘层交换机，则优先将流转发到跳数较少的路径中，即拓扑中的多条最短等价路径。当所有等价路径中链路负载已超过链路负载门限值时，再将流传输到其余跳数较多的等价路径中。对于跳数的限定有效保证了流的传输时延。路径选择算法如算法1所示。

算法1路径选择算法

Input：Network topology,information of link state,information of flow state。

Output：the Path。

1 forFr← the rate of flow do

2 ifFr>δ

3elephant_flow←the flow is recorded as a stream;

4 forelephant_flow

5Path←Calculate all paths between the source and destination host;

6 for all Path

7LFi←Idle load in a link;

8m←Number of links in a path;

11WPath=σ/mean;

12hop←hop in a path;

13 if connected to the same edge switch

14 hop←1;

15 else if

16Path_List←the path hop in ascending order;

17 forli←Path_List

18 ifli<ε

19Path_Select←the least number of hops and small weight;

20 else if

21Path_Delete←Remove congestion link;

22Path_List←the least number of hops and small weight;

23 end for

24 end if

25 end for

26 end for

27 end if

28 end for

(2)负载均衡调度。

当处于流量高峰期时，由于大量突发性大流的存在，网络的某些链路可能会处于高负载状态，导致链路负载不均匀。因此，设定一个负载均衡度ρ用于判定当前链路负载是否均匀、网络中是否存在高负载链路。

整个网络的链路平均负载Lavg为：

(5)

全网负载均衡度ρ的定义如下：

ρ=Lavg/LMax

(6)

则网络中某条链路的负载均衡度ρ′为：

ρ′=Lavg/Li

(7)

由式(6)可以看出，ρ是链路负载的平均值与最大链路负载的比值。ρ越接近1，表明网络中负载越均匀，ρ越接近0，表明网络中负载差异非常大，需要对最大链路负载进行调整。本文设定了一个负载均衡度阈值θ用于判断链路的负载均衡程度，并决定是否需要对流进行调度。当负载均衡度阈值过大时，容易导致对流的频繁调度，若负载均衡度阈值太小，则容易导致网络负载不均衡。针对阈值θ的取值，通过测量不同θ与网络吞吐量的关系选取了最佳θ值。

(3)调度流选取。

OpenFlow控制器可以向交换机发送查询请求消息，从交换机获取网络流量和链路等相关的统计信息，如收发字节数、收发数据包、统计时间周期等。因此，可以通过周期性监测交换机传输流的总字节数和统计周期来对大小流进行判定。流的大小可用式(8)求出。

K=(Mt+T-Mt)/T

(8)

其中，Mt是交换机在t时刻接收到的流字节数，Mt+T是交换机在t+T时刻接收到的流字节数，T为控制器监测统计周期。针对流的大小设定一个阈值δ用以区分大小流。当一条流的大小超过该阈值时，则记录该流的匹配域并判定该流为大流；否则，判定该流为小流。针对大流阈值的选取，当前并没有一个明确的规定。学者们主要是针对不同的网络与流量状况，定义不同的大流阈值，一般均是将占用1%～10%链路带宽的流设定为大流，因此本文将占用5%链路带宽的流设为大流。

设一条路径正在传输一条大小为Fr的大流fe，由于路径的负载逐渐增至最大，导致负载均衡度小于阈值θ，因此需要将路径POri上的流调度到其它路径中以均衡全网负载。经过路径权重计算与比较后，最终为大流fe选择了另一条传输路径PNew。路径POri中负载最高的链路为lOri，负载大小记为LOri，路径PNew中负载最高的链路为lNew，负载大小记为LNew。当对大流fe进行调度时，新路径PNew的空闲带宽首先需要满足其带宽需求，同时为避免调度大流可能造成的链路拥塞，进一步限定了每条链路的最高负载，设定了一个链路最高负载门限ε，链路负载门限设定为链路带宽的80%。在对大流fe调度之前，有必要对流的需求带宽和链路空闲带宽进行计算，以确定大流fe调度到路径PNew后是否会导致造成链路拥塞或负载过高。因此，调度的流的大小应小于路径PNew中的最大可用带宽。即:

(Fr+LNewCNew)/CNew<ε

(9)

其中，CNew表示链路lNew的最大带宽。

则可得Fr需满足条件：

Fr<εCNew-LNewCNew

(10)

当大流fe调度后，Fr还需使新路径PNew满足条件：ρ′≥θ，以避免频繁的流调度，即：

(11)

进一步可将Fr限定条件表示为：

Fr≤CNewLavg/θ-LNewCNew

(12)

考虑本文拓扑状况，每条链路带宽均为C，Fr的范围最终可化简为：

(13)

若该链路上存在多条满足调度条件的大流，则优先调度最大的流。大流选取算法如算法2所示。

算法2大流选取算法

Input：Network topology,information of link state,information of flow state。

Output：Information of large flow。

1 forLi← the link load do

3Lmax=max{L1,L2,…,Lm};

4ρ=Larg/Lmax;

5 ifρ<θ

6 ifLmax=max{L1,L2,…,Lm}

7Fr←rate of flow in a link;

8 ifFr>σ

9elephant_flow←The flow is recorded as a stream;

10 forelephant_flow

11 ifFr≤(Larg/θ-LNew)*C&&Fr<(ε-LNew)*C

12flow_select←the information of flow;

13 end if

14 end for

15 end if

16 end if

17 end if

18 end for

3 仿真和性能分析

3.1 仿真环境

为了测试与验证提出的负载均衡算法的性能，本文采用了Mininet[11]和Ryu[12]控制器作为网络仿真平台。实验主机中采用VMware Workstation作为虚拟机软件，并安装两个Ubuntu 14.04.4 LTS系统。其中，一个系统安装Mininet，用于模拟OpenFlow网络环境和拓扑结构；另一个系统安装Ryu控制器，并通过指令与Mininet相连，对OpenFlow网络进行集中式控制。同时，Ryu控制器向上层提供了可编程接口，因此可以使用Python语言实现负载均衡功能。本文模拟数据中心网络拓扑架构，使用Mininet构建了一个4元Fat-Tree拓扑，如图2所示，共包括20台OpenFlow交换机和16台主机，并将网络中链路的带宽设置为10 Mbps，链路均为全双工链路。使用Iperf软件生成不同速率、大小的数据流，仿真网络环境流量，并对算法进行性能测试与比较。实验仿真参数设置如表1所示。

Table 1 Experimental simulation environment表1 仿真环境

Figure 2 Four-element Fat-Tree network topology图2 4元Fat-Tree网络拓扑结构

3.2 性能分析

在Mininet构建的网络拓扑环境下，首先选取合适的负载均衡度阈值，再对本文提出的数据中心负载均衡算法DCLB(Load Balancing in Data Center)的性能进行对比与分析，使用平均传输时延、链路带宽利用率和负载分布三个性能指标与ECMP、LABERIO算法进行对比。使用Iperf使网络中的主机互相随机发送数据包，并将流量速率从2 Mbps逐渐提升到8 Mbps，测量不同负载状况下，DCLB算法与ECMP、LABERIO算法的平均时延对比，如图3所示。由图3可见，三种算法的平均时延均随着发包速率的提升而逐渐增加。整体上来看，DCLB算法和LABERIO算法时延更为稳定。当发包速率小于3 Mbps时，网络中链路负载较轻，三种路由算法都能较为稳定地传输网络中的数据包，平均时延总体也较为稳定。

Figure 3 Average delay图3 平均时延

通过调整Iperf发包速率，测量了满负载情况下，核心层交换机与汇聚层交换机之间链路的带宽利用率，如图4所示。其中，横坐标表示核心交换机与汇聚层交换机之间的链路。由图4可以看出，ECMP算法的平均链路利用率为61.7%，LABERIO算法的平均链路利用率为67.2%，DCLB算法的平均链路利用率为72.4%，DCLB算法和LABERIO算法的链路利用率均优于ECMP算法。ECMP算法是随机选择路径，多条大流在同一条链路中碰撞，导致Pod内部产生热点路径，因此核心交换机与汇聚层交换机链路的带宽利用率较低。而LABERIO算法是基于单跳贪婪策略，且仅在链路负载超过门限阈值时实现对流的调度，不能主动均衡链路负载，因此在网络负载较高的情况下，链路利用率较低。

Figure 4 Link utilization图4 链路利用率

通过统计控制器中监控模块输出的交换机状态信息，可以获得网络中所有核心交换机接收到的字节数，用以表征核心交换机之间的负载分布。图5是拓扑中核心交换机的负载分布。由图5可以看出，采用DCLB和LABERIO算法时，核心交换机之间的负载分布得更为均匀。在ECMP算法下，核心交换机的负载范围为[2008,3107] Mbit，平均负载为2 505 Mbit，方差为461.4。在LABERIO算法下，核心交换机的负载范围为[2503,3014] Mbit，平均负载为2 718 Mbit，方差为254.5。在DCLB算法下，核心交换机的负载范围为[2638,3006] Mbit，平均负载为2 837 Mbit，方差为157.9。通过方差的比较，可以发现DCLB算法的负载分布得更加均匀。

Figure 5 Load distribution图5 负载分布

4 结束语

本文充分利用OpenFlow技术的全局网络拓扑和集中式控制等特点，通过实时监控和统计链路与流量的状态信息，实现了动态的链路负载均衡，并通过仿真验证了本文所提算法能有效提高网络资源利用率，并均衡全网负载。本文的方案尚存在着不足,网络环境仅考虑了单控制器和单域的情况，而在多控制器或混合网络的情况下，如何保证本文提出的负载均衡方案的性能稳定是下一步需要完善的地方。

[1] Zuo Qing-yun, Chen Ming, Zhao Guang-song,et al.Research on OpenFlow-based SDN technologies [J].Journal of Software,2013,24(5):1078-1097.(in Chinese)

[2] Nadeau T D,Gray K.SDN:Software defined networks[M]. Sebastopol:O'Reilly Media,Inc,2013.

[3] Braun W,Menth M.Load-dependent flow splitting for traffic engineering in resilient OpenFlow networks[C]∥Proc of 2015 International Conference and Workshops on Networked Systems(NetSys),2015:1-5.

[4] Craig A, Nandy B, Lambadaris I,et al.Load balancing for multicast traffic in SDN using real-time link cost modification[C]∥Proc of 2015 IEEE International Conference on Communications(ICC’15),2015:5789-5795.

[5] Trestian R, Muntean G M,Katrinis K.MiceTrap:Scalable traffic engineering of data center mice flows using OpenFlow[C]∥Proc of 2013 IFIP/IEEE International Symposium on Integrated Network Management(IM 2013),2013:904-907.

[6] Li J,Chang X,Ren Y,et al.An effective path load balancing mechanism based on SDN[C]∥Proc of 2014 IEEE 13th International Conference on Trust,Security and Privacy in Computing and Communications(TrustCom),2014:527-533.

[7] Li Y,Pan D.OpenFlow based load balancing for fat-tree networks with multipath support[C]∥Proc of the 12th IEEE International Conference on Communication(ICC’ 13),2013:1-5.

[8] Sehery W,Clancy T C.Load balancing in data center networks with folded-Clos architectures[C]∥Proc of 2015 1st IEEE Conference on Network Softwarization,2015:1-6.

[9] Xi K,Liu Y,Chao H J.Enabling flow-based routing control in data center networks using probe and ECMP[C]∥Proc of 2011 IEEE Conference on Computer Communications Workshops(INFOCOM WKSHPS),2011:608-613.

[10] Long H,Shen Y,Guo M,et al.LABERIO:Dynamic load-balanced routing in OpenFlow-enabled networks[C]∥Prco of 2013 IEEE 27th International Conference on Advanced Information Networking and Applications(AINA),2013:290-297.

[11] Lantz B,Heller B,Mckeown N.A network in a laptop:Rapid prototyping for software-defined networks[C]∥Proc of ACM Sigcomm Hotnets Workshop,2010:19.

[12] Stancu A L,Halunga S,Vulpe A,et al.A comparison between several software defined networking controllers[C]∥Proc of 2015 12th International Conference on Telecommunication in Modern Satellite,Cable and Broadcasting Services(TELSIKS),2015:223-226.

附中文参考文献：

[1] 左青云,陈鸣,赵广松.基于OpenFlow的SDN技术研究[J].软件学报,2013,24(5):1078-1097.