基于SDN的胖树数据中心网络多路径负载均衡算法研究

付应辉 刘必果 束永安

(安徽大学计算机科学与技术学院 安徽 合肥 230601)

基于SDN的胖树数据中心网络多路径负载均衡算法研究

付应辉 刘必果 束永安

(安徽大学计算机科学与技术学院 安徽 合肥 230601)

软件定义网络SDN(Software Defined Network)通过将网络设备的控制层与数据层分离解耦，能够实现网络的集中控制和流量的灵活转发，因此被广泛应用于数据中心等相关领域。在数据中心网络中，为了提高网络的带宽和吞吐量，多采用具有多路径特性的层次型网络拓扑结构，如胖树拓扑结构。然而传统路由算法对多路径的支持非常有限，无法充分利用网络剩余带宽。重点研究基于SDN的胖树数据中心网络多路径负载均衡算法。利用SDN网络集中控制的特点，获取多路径实时状态信息，计算各路径当前可用带宽，根据数据流的带宽需求选择最佳转发路径。实验结果表明，该算法无论在降低网络传播时延还是在提高网络吞吐量等方面都优于传统路由算法，能够实现胖树数据中心网络的多路径负载均衡。

软件定义网络 SDN 胖树 数据中心网络 多路径负载均衡

0 引 言

软件定义网络(SDN)[1]是当前热门的新型网络创新架构，其控制层与数据层的分离能够提供全网信息的集中控制和统一部署，被广泛应用于数据中心网络以提高网络带宽利用率。数据中心网络配套各种存储系统、网络互连设备，网络规模庞大。为了实现各服务器之间的高效互联，数据中心网络多采用具有多路径特性的胖树拓扑结构[2-3]。

传统的基于IP的等价多路径路由(ECMP)协议根据数据包的源目的地址计算路由并转发，虽然支持多路径协议，但是没有考虑流对带宽的需求，也无法感知网络负载状态及数据流带宽需求的变化。仅仅是从具有相同最小代价的路径中选择备选路径，导致该算法有很大的局限性[4]。

目前针对数据中心网络设计的多路径解决方案主要有如下几种：Al-Fares等[5]提出的全局最先匹配算法和模拟退火法；Heller等[6]提出的ElasticTree数据中心网络能量管理方法，包括贪婪装箱算法和拓扑感知的启发式算法。

其中，全局最先匹配算法选择网络中第一条满足流带宽需求的路径，算法简单但是必须获取所有链路信息，而且往往找到的路径都不是全局最优路径；模拟退火法使用概率性搜索方法确定全网最优路径，能够实现全局最优，但是收敛速度可能会很慢，不适应对响应速度要求很高的网络；贪婪装箱算法通过评估所有可用路径然后选择最左边满足需求的路径，缺点是每次数据流到来时都要进行一次评估，系统开销比较大；拓扑感知的启发式算法基于胖树拓扑结构的特性使用快速启发式，要依赖于流划分也没有考虑到整个网络的流量状态。

在SDN集中控制机制下，实现数据中心系统状态最优也有相关研究。如文献[7]中通过在SDN控制器中建立流分布规则，减小控制器过载和延迟，以及控制规则表规模。文献[8]通过动态分配权值减轻SDN交换机和普通交换机混合网络中局部拥堵路径，提高整个全网工作效率。

但是，这些方法缺少自适应性，没有考虑网络运行状态，不能保证在全局最优的情况下，实现胖树数据中心网络全网多路径负载均衡。

本文的目标是在SDN结构下，研究胖树数据中心网络中基于网络运行状态且支持多路径的高效可行的多路径负载均衡算法(F-MPLB)，以提高网络带宽和吞吐量，实现全网负载均衡。

F-MPLB算法的研究思路是利用SDN控制器收集全网状态信息，然后计算节点可调用带宽、链路剩余带宽等信息。通过评估所有可选路径找出最佳路由，最后由控制器制定路由转发策略并下发到各交换机节点。算法主要研究以下几个方面：

(1) 节点可调用带宽，根据节点转发阈值上限及当前负载情况计算节点可调用带宽，在节点发生拥塞前能够提前更换转发节点；

(2) 链路剩余带宽，根据链路最大负载及当前已用带宽计算链路剩余带宽，防止链路拥塞；

(3) 路径的选择，根据节点可调用带宽与链路剩余带宽，评估节点对之间所有路径，创建可选路径集合，根据可选路径的瓶颈带宽选择最佳转发路径。

1 系统结构

为了让F-MPLB算法具有更强的可执行性，本文将网络信息的收集、多路径的分析与评估、路由策略的下发进行分离，分别使用信息收集模块、路由模块、控制器模块等3部分实现，算法系统结构如图1所示。

图1 F-MPLB算法系统结构

1.1 信息收集模块

信息收集模块实时监控转发层流量、节点状态和链路状态，获取网络流量需求及当前节点和链路负载状态等信息，通过数据库存储到对应的数据表中供路由模块使用。

1.2 路由模块

路由模块根据流、节点和链路相应的数据表中记录的网络流量、节点状态和链路状态等数据信息，将各信息计算模块通过不同的独立进程实现，分别负责流管理、节点管理和链路管理。然后基于网络拓扑结构找出源目的节点对之间所有多路径，对多路径路由进行评估找出全网最佳路径。路由的评估包括节点评估和链路评估两部分。

(1) 节点评估

节点评估主要对节点的可调用带宽进行评估。节点转发能力有限，为了防止节点超载造成网络瘫痪，一般都会设定节点转发阈值上限来限定节点最大带宽利用率。节点可调用带宽通过节点最大带宽与当前已用带宽的差值计算得出。

路由模块根据节点当前带宽利用率，首先淘汰超过节点转发阈值上限的节点以及包含这些节点的路径，然后计算剩余节点的可调用带宽，预测最佳转发节点。

(2) 链路评估

胖树数据中心网络是层次型网络拓扑结构，越靠近核心层的链路带宽需求越高。为了避免链路拥塞，路由模块通过设定合理的链路最大负载来限定链路最大可用带宽。然后根据当前负载情况计算各链路剩余带宽，淘汰那些剩余带宽不足以满足流量带宽需求的链路。最后从剩下的链路中选择最佳转发链路。

1.3 控制器模块

控制器模块是SDN结构的核心。控制器主要完成以下任务：(1)从信息收集模块获取网络流量、节点状态和链路状态等信息形成全局视图，提供给路由模块进行计算；(2)根据路由模块计算得出的全局最佳路径，形成路由转发策略并生成流表下发到各个交换机节点。

F-MPLB算法的三个模块构成如图2所示。

图2 F-MPLB算法模块构成

各模块进程相互独立且按照一定的顺序触发。首先信息收集模块收集信息写在数据库对应的数据表中；然后路由模块评估算法从数据库中读取数据并根据全局视图进行多路径路由评估确定最佳转发路径；最后交给控制器模块制定路由转发策略。

2 路由模块算法设计

2.1 网络环境描述

胖树拓扑结构具有边缘层、汇聚层和核心层3层结构[9-10]。其中，汇聚层和边缘层分为K个POD，每个POD包含K个交换机，其中K/2个在汇聚层，另外K/2个在边缘层；每个交换机有K个端口，其中K/2个向下级联，另外K/2个向上级联；核心层共有(K/2)2个核心交换机，每个交换机K个端口分别连接到分属于K个POD的汇聚层交换机向上的级联口。整个网络共有5K2/4个交换机、3K3/4条链路，可以容纳K3/4个主机。本文构造一个K=8的简单胖树数据中心网络，如图3所示。

图3 胖树数据中心网络(K=8)

该网络可以看作图G=(H∪S;E)，其中，H与S是节点集合，H代表主机，S代表交换机，E是链路集合。交换机节点s∈S的带宽用b(s)表示，链路e∈E的带宽用b(e)表示。

设网络中所有数据流组成集合F={f1,f2,…,fn}，流fi的运行带宽用b(fi)表示。构造矩阵X=F×S，矩阵元素的值x(fi,s)∈(0,1)代表流fi是否流经交换机节点s。构造矩阵Y=F×E，矩阵元素的值y(fi,e)∈(0,1)代表流fi是否流经链路e。

2.2 节点评估算法

节点评估算法的目标是设定节点转发阈值上限，路由模块根据节点带宽利用率，淘汰节点负载接近节点转发阈值上限的节点，然后根据节点最大转发带宽及当前已用带宽，计算各节点的可调用带宽Ava(s)，选择出最佳的转发节点。

节点转发阈值上限直接限定了节点最大转发带宽。考虑到网络流量带宽的不确定性，本文引用绝对中位差MAD[11]来衡量数据流稳定性。

根据MAD的定义，当前节点s的MAD值可表示为：

MAD=mediani(x(fi,s)×b(fi)-medianj(x(fj,s)×b(fj)))

(1)

节点转发阈值上限定义为：

Thu(s)=1-α×MAD

(2)

其中，α∈R+，为自定义参数，通过调整α值可以调整节点转发阈值上限。MAD值越小说明该节点上数据流越稳定，节点转发阈值上限可以调大些；MAD值越大说明数据流越不稳定，需要调小节点转发阈值上限避免数据流突发造成节点拥塞。

设wl(s)表示节点已用带宽，则节点s的带宽占用率为：

Pwl(s)=wl(s)/b(s)

(3)

节点带宽占用率不能超过节点转发阈值上限，即Pwl(s) ≤Thu(s)。

因此，节点s可调用带宽为：

Ava(s)=Thu(s)×b(s)-wl(s)

(4)

2.3 链路评估算法

为了避免链路拥塞造成网络瘫痪，链路评估算法会综合考虑链路关键度及链路所处网络层次等因素设定合理的链路最大负载，根据链路剩余带宽选择最佳转发链路。

首先，我们将链路e的链路关键度ρ(e)定义为：

ρ(e)=AVE(e)/b(e)

(5)

其中，b(e)表示链路建设时带宽；AVE(e)表示链路的平均期望负载，定义为网络中所有流过链路e的流量带宽之和与流数目的比值，则：

(6)

AVE(e)值越高说明数据流在选择转发路径时更容易选中该链路，链路关键度越高，应该设置更高的链路最大负载。

胖树数据中心网络不同网络层次需要的最大带宽也不同，为此我们引入参数β∈R+，不同网络层次设置不同的β值。链路最大负载定义为：

max=β×ρ(e)

(7)

则链路e的剩余带宽c(e)为：

(8)

算法应该满足如下限制：

(9)

(10)

式(9)表明了链路最大负载与链路可用带宽的关系，即对链路需求的带宽总和不超过链路的可用带宽。式(10)表明流守恒限制，即流经任意中间节点v的流数目不会改变。

2.4 算法的实现代码

本文在SDN环境中实现F-MPLB算法，通过SDN控制器获取网络中所有节点和链路状态信息。当数据流需要重新选择路径或者一个新流产生时，根据流的源目的IP地址建立路径集合数据库；然后根据节点转发阈值上限与链路最大负载的约束，排除节点超载或链路剩余带宽不足的路径；最后在剩下的可选路径中根据节点可调用带宽和链路剩余带宽对多路径进行评估，选择瓶颈带宽最大的路径对数据流进行转发。

算法实现伪代码如下：

begin

{ 输入流f，源主机Hs，目的主机Hd；

if(Hs和Hd同属一个边缘交换机)

return path(Hs,Hd);

else

{ PATHS=getAllpath(Hs,Hd);

Deletepath();

for( int m=0;m

MINWIDTH=min( PATHS.minNodewidth, PATHS.minBandwidth );

end for;

for(int k=0;k< MINWIDTH.length;k++)

if( MINWIDTH[k].width ≥ b(f) )

path.width=max( path.width, MINWIDTH[k].width );

end for;

return path(Hs,Hd);

}end if;

输出转发路径path(Hs,Hd)及其瓶颈带宽path.width。

}

end

路径评估由路径上所有节点带宽和链路带宽的最小值决定路径瓶颈带宽，即路径L瓶颈带宽=min(节点1带宽，节点2带宽,…,节点m带宽，链路1带宽，链路2带宽,…,链路n带宽)。路径选择算法选择瓶颈带宽最大的路径，即转发路径=max(路径L1瓶颈带宽，路径L2瓶颈带宽，…,路径Lk瓶颈带宽)，最终实现多路径负载均衡。

3 实验和算法评估

3.1 平台介绍

本文使用Mininet+Floodlight实验平台模拟运行环境，F-MPLB算法各独立模块在Floodlight控制器上实现。Floodlight控制器周期性地调度监控事件获取全网状态信息，包括交换机状态、链路负载情况以及数据流带宽需求等信息。

Mininet版本为2.2.0，Floodlight控制器版本为Ubuntu 16.04-desktop-64位，硬件环境为ACER E1-571G，CPU为Intel Core(TM) i5，2.60 GHz，内存4 GB，硬盘500 GB。Mininet选择严格胖树拓扑结构[12]模拟数据中心网络，取K=8模拟128个主机场景，网络中叶节点交换机64个，核心交换机16个。

实验中设定叶节点交换机带宽为200 MB/s，核心交换机带宽为1 GB/s，交换机转发阈值上限缺省值为60%；链路带宽为100 MB/s，核心层到汇聚层链路最大负载缺省值为70%，汇聚层到边缘层链路最大负载缺省值为60%；算法将网络中传输的流归约到叶节点交换机，流直接在交换机端产生；数据流的源目的节点在叶节点交换机集合中随机产生；大流带宽大小服从[1 MB/s,10 MB/s]为区间的随机分布，小流带宽大小服从[1 KB/s,10 KB/s]为区间的随机分布，流发生频率服从指数分布。每次实验流的数量相等，长短流按照设定配给比例产生，缺省情况下比例各为50%。

3.2 对比实验

本文实验选择严格胖树拓扑结构模拟数据中心网络环境，数据流数量达到107数量级，对网络的响应速度要求很高。如今已有的多路径解决方案及SDN集中控制下的相关研究，在此类网络中多使用传统的ECMP算法及Hedera中提出的GFF算法，因此本文实验主要与这两种算法进行性能对比。

其中，ECMP在可供选择的等价链路上平均分配流量，能够有效提高网络带宽及吞吐量，但是不能够根据链路状态变化改变流量分配的比例；GFF算法在监测到大流时搜寻所有有效路径，选择最先找到的符合带宽要求的链路进行转发，没有考虑网络全局负载状态。针对算法的这些差异，本文分别从节点过载次数、传播时延、平均吞吐量等三方面进行比较。

(1) 节点过载次数比较

通过网络运行过程中节点过载次数反映路径的过载次数。如果节点过载次数过大，说明该算法不能根据多路径当前负载状态合理分配数据流转发路径，随着流数量的增加最终会造成网络拥塞。节点过载情况如图4所示。

图4 节点过载次数比较

从实验结果可以看出，传统的ECMP算法引起的节点过载次数最多；GFF算法能够有效降低节点过载次数，但随着网络负载状态的改变节点过载情况也开始出现；F-MPLB算法效果最好，能够根据当前网络负载状态动态地调整转发路径，实现链路负载均衡避免节点过载情况的发生。但是，随着数据流数量的不断增加，网络流量趋于饱和并最终超过系统处理阈值，各算法的节点过载次数趋于相同。所以F-MPLB算法在系统性能阈值之内能很好地避免节点过载，但超过系统阈值能够引起的改变有限。

(2) 传播时延比较

随着数据流数量的增加，观察算法对数据流传播时延的影响，实验结果如图5所示。

图5 传播时延比较

实验中不同算法选择路径的策略不同，导致了时延上的差异。实验最开始传播时延都有所上升是因为数据流第一个数据包到来时，交换机转发流表为空，需要上报Floodlight控制器计算转发路径并下发流表。随后传播时延迅速回落。当数据流数量在0～104范围内，多路径链路状态良好，3种算法传播时延相当。当数据流数量超过104，ECMP算法传播时延开始增加，网络性能急剧下降；而GFF算法能保持时延只产生微小抖动，F-MPLB算法基本无抖动。当数据流数量到达106，网络负载状态超过系统处理阈值，传播时延都有所增加，但总体上F-MPLB算法传播时延最低，体现出一定的优越性。

(3) 平均吞吐量比较

网络平均吞吐量实验结果如图6所示。

图6 平均吞吐量比较

实验结果反映出当网络流量在0～102范围内，网络剩余带宽充足，3种算法的平均吞吐量都稳定增长。但是当数据流数量超过102，网络负载逐渐加重，传统的ECMP算法不能很好地感知网络负载状态，吞吐量开始达到瓶颈值；而GFF算法和F-MPLB算法吞吐量依然能够稳定提升。当数据流数量达到104，网络负载趋于饱和，传统的ECMP网络吞吐量急剧下降；GFF算法吞吐量趋于稳定，能够很好地处理网络拥塞；而F-MPLB算法动态调整转发路径，不仅能处理网络拥塞还能进一步提高网络平均吞吐量。

3.3 实验结论

从以上实验结果可以看出，当网络数据流数量较少、多路径带宽充足时，3种算法性能相当。但是随着数据流数量的增加，网络负载超出了系统处理能力阈值，传统算法的有效性降低。而本文提出的F-MPLB算法能够通过动态调整数据流转发路径，将流量引导至负载较低、质量较好的路径上。实现多路径负载均衡，能够有效减少节点过载次数、降低传播时延、提高网络平均吞吐量。

4 结 语

本文基于SDN结构，针对胖树数据中心网络提出了多路径负载均衡算法F-MPLB。该算法利用SDN集中控制器获取全网网络状态信息，通过求解节点转发阈值上限确定节点可调用带宽、求解链路最大负载确定链路剩余带宽，提供给路由模块以选择最佳转发路径，更好地利用多路径有效带宽达到链路负载均衡。经过Mininet+Floodlight仿真实验，结果表明本文算法在系统阈值能力范围内，在减少节点过载次数、缩减传播时延、提升网络吞吐量等方面的性能均优于传统多路径算法，能够实现胖树数据中心网络多路径负载均衡。

随着研究的逐渐深入，发现还有许多工作值得后续的关注和跟进。

1) 评估模型扩展。本文算法以多路径中交换机节点可调用带宽及链路剩余带宽两个标准评估路径最大传输能力，根据数据流带宽需求寻找最佳转发路径。但是没有考虑交换机节点转发速率及链路的传输时延，随着评估标准的增加，算法越来越复杂，需要增加控制器模块复杂度。同时模块部署时延、算法的准确度分析都需要跟进研究。

2) 流动态预测与复杂分析。SDN数据流是可以预测的，预测模型通过在控制器端增加流信息统计模块监控数据流的传输，根据流的历史统计特性可以预测其未来行为。本文对数据流的分析仅局限于数据流的带宽，没有考虑流频率及传输性质的不同。对于经常出现的流及突发产生的流应该采取不同的处理方式，但这样也会增加模块复杂度。

[1] Mckeown N,Anderson T,Balakrishnan H,et al.Open Flow:enabling innovation in campus networks[J].Acm Sigcomm Computer Communication Review,2008,38(2):69-74.

[2] Fei Y.Introduction to the development of data center network architecture[J].Network Security Technology & Application,2014,22(6):23-28.

[3] Sun Y,Cheng J,Shi K.Data Center Network Architecture[J].Zte Communications,2013,11(5):5-9.

[4] Chemeritskiy E,Smelansky R.On QoS management in SDN by multipath routing[C]//2014 First International Science and Technology Congerence(Modern Networking Technologies) (MoNeTeC).IEEE,2014:1-6.

[5] Al-Fares M,Radhakrishnan S,Raghavan B,et al.Hedera:Dynamic flow scheduling for data-center networks[C]//NSDI’10 Proceeding of the 7th USENIX conference on Networked systems design and implementation.Berkeley,CA,USA:USENIX Association,2010:19-19.

[6] Heller B,Seetharaman S,Mahadevan P,et al.ElasticTree: saving energy in data center networks[C]//Usenix Conference on Networked Systems Design and Implementation.USENIX Association,2010:17-17.

[7] Wang R,Butnariu D,Rexford J,et al.OpenFlow-based server load balancing gone wild[C]//Proceedings of the 11th USENIX Conference on Hot Topics in Management of Internet,Cloud,and Enterprise Networks and Services.Boston,USA,2011:12-12.

[8] Guo Y,Wang Z,Yin X,et al.Traffic engineering in SDN/OSPF hybrid network[C]//Proceedings of the 22nd IEEE International Conference on Network Protocols(ICNP).North Carolina,USA,2014:563-568.

[9] Eric J,Deng P,Liu J,et al.Asimulation and emulation study of sdn-based multipath routing for fat-tree data center network[C]//WSC’14 Proceeding of the 2014 Winter Simulation Conference.Piscataway,NJ,USA:IEEE Press,2014:3072-3083.

[10] Zhou J,Malveeka T,Zhu M,et al.WCMP:Weighted cost multipathing for improve fairness in data centers[C]//EuroSys’14 Proceedings of the Ninth European Conference on Computer Systems.New York,NY,USA:ACM,2014,5.

[11] Wu C,Zhao Y,Wang Z,et al.The median absolute deviations and their applications to Shewhart control charts[J].Communications in Statistics-Simulation and Computation,2002,31(3):425-442.

[12] Al-Fares M,Loukessas A,Vahdat A,et al.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review,2008,38(4):63-74.

RESEARCHONSDN-BASEDMULTI-PATHLOADBALANCINGALGORITHMOFFAT-TREEDATACENTERNETWORK

Fu Yinghui Liu Biguo Shu Yongan

(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

Software Defined Networking (SDN) is widely used in datacenters and other related fields to achieve centralized control of the network and flexible traffic forwarding by decoupling the control plane from the data plane. To improve the network bandwidth and throughput, datacenter network employ layering network topology structure with multi-path characteristics, such as Fat-tree. However, traditional routing algorithms have limited support for multi-path routing, they cannot make full use of the remaining bandwidth of the network. Therefore, this paper mainly studies the SDN based multi-path load balancing algorithm of Fat-tree datacenter network. By using the centralized control of SDN network, obtain multi-path real-time status information; calculate the available bandwidth of each path, and selects the best forwarding route according to the bandwidth requirement of the data stream. The experimental results show that the proposed algorithm is superior to traditional routing algorithms in not only reducing network propagation delay but improving network throughput, thus it is capable to achieve multi-path load balancing in Fat-tree datacenter networks.

Software defined network SDN Fat tree Datacenter network Multi-path load balancing

TP3

A

10.3969/j.issn.1000-386x.2017.09.030

2016-10-19。安徽省自然科学基金项目(1408085MF125)。付应辉，硕士生，主研领域：SDN。刘必果，硕士生。束永安，教授。