基于SDN的流分类多指标负载均衡策略研究

2020-04-01张正之

现代计算机 2020年6期

张正之

（四川大学计算机学院，成都610065）

0 引言

随着数据中心网络（Data Center Networks，DCN）规模的不断扩大，数据中心内部之间东西向的流量不断增多，可能会造成部分链路的拥塞，而其余链路利用率则低；时延长和高丢包率等问题。而软件定义网络（SDN）采用数控分离的网络架构，拥有灵活的可编程性和全局信息控制的特点，可以实现流的路径调度和控制。控制器使用OpenFlow[1]南向协议下发流表项到支持OpenFlow的交换机来控制路由转发，使得底层转发设备可以被统一的控制和管理。

目前针对数据层面的流量调度工作可以分为路径和服务流量的负载均衡两大类，进一步可将前者分为基于大象流（超过一定大小且持续时间长的流）识别的调度，面向QoS的调度以及其他算法[2]。有研究表明，数据中心网络中90%的流小于100KB（老鼠流），而10%的流则具有大量的数据（100KB到1GB）或更长的生存周期（大象流），它们产生超过80%的数据量[3]。大象流对带宽要求高，而老鼠流则更看重时延，因此如何选择合理的路径对大象流和老鼠流调度，避免网络拥塞，是十分有必要的。

当前在DCN中应用较为多的是等价多路径ECMP[4]算法，其通过哈希散列的方式，基于流的数量平均分配流量，在一定程度上提高了负载均衡度，适合老鼠流的调度，但其有可能将多条大象流映射到同一路径上，从而加剧网络拥塞。考虑到数据中心流量大小分布不均及传统的ECMP机制的弊端。本文针对Fat-Tree拓扑结构，提出一种基于流分类多指标负载均衡（LB-FC⁃MI）方案。利用SDN对网络全局掌握和对流进行分类处理的同时，对判断出来的大象流和老鼠流按照各自的综合评价方案分别进行评分，选出最高得分的路径进行转发。最后通过实验验证方案的有效性。

1 近年来相关研究工作

自SDN诞生以来，基于SDN的数据中心网络负载均衡研究一直是学术界和工业界追捧的热点，许多学者和专家从不同的方面采用不同的方法进行了研究。在基于识别大象流调度的研究中，文献[5]提出一种面向Fat-Tree拓扑的动态流量负载均衡机制（LBFC），采用动态调整流分类阈值来判定大小流，大象流采用动态自适应算法调度，老鼠流采用轮询算法调度，适应了不同的流对传输性能需求不同这一特点。文献[6]提出一种基于流概率路径选择的方法，通过分离出传输流中占比较大的大象流，算出数据流量转发时对每条路径的利用率，根据利用率求得此路径被选择的概率，最后综合参照概率大小和路径长度来确定转发路径。而小流则采用ECMP算法计算路径。文献[7]提出一种分裂大象流的负载均衡方法，当网络负载超过设置的阈值时，控制器将采集到的大象流分裂成许多老鼠流，再根据实际的网络情况算出负载最小的下一跳交换机来传输老鼠流，从而保证负载均衡。文献[8]提出一种基于蚁群优化的流调度系统（TSACO），该系统通过Open⁃Flow和sFlow发现大象流，然后通过基于蚁群的自适应多路径算法来调度大象流，而老鼠流则通过路径数据表转发。

在针对基于k条最短路径评价方案的研究中，文献[9]提出一种基于多路径传输的动态负载均衡路由（MTDLR）算法，该算法综合了路径层面的多个因素进行分析，包括链路带宽均衡度，路径带宽最优度和路由跳数，能够实现为每一条数据流提供最佳路径选择。文献[10]提出一种基于流调度选择的动态负载均衡（DLBFSS）算法，该算法首先计算满足带宽需求的多条等价最短路径，然后选择其中剩余吞吐量最大的路径作为最佳调度路径;最后以最佳调度路径的负载和流量的带宽来决定调度的拥塞概率，并把概率大小作为流调度的依据。文献[11]提出一种基于多指标的链路负载均衡（MI-LB）模型，该模型计算出起始节点到目的节点的k条可达路径，再用多指标的综合评价算法对k条可达路径进行评分，最后选择评分最高的路径作为转发路径。

然而上述文献中的研究要么没有考虑到老鼠流的合理调度，要么路径选择的评价指标过于单一，只是对指标进行简单加权，可能会导致评价不合理。鉴于此本文首先计算出源目的节点对的k条最短路径，对大象流和老鼠流路径选择采用不同的评价指标进行综合评分，最后选择最优的转发路径。

2 总体架构设计

SDN作为一种新提出的网络架构，与传统网络结构相比，具有实现控制平面与数据平面分离的特性，能够集中控制网络状态，实现底层网络对上层应用的透明化。针对数据中心网络中对大小流调度不均衡，对路径选择的评价指标过于单一的情况，本文提出基于流分类多指标路径综合评价机制，该机制首先在交换机检测识别大象流和老鼠流，并计算源目的节点的k条最短路径，并分别对大小流用不同的评价指标进行评分选路，选出综合评分最高的链路，最后进行流表下发。LB-FCMI模型包含以下几个模块：网络监测模块，多路径计算模块，大象流评价模块和老鼠流评价模块。框架如图1所示。

图1 基于Ryu控制器的负载均衡框架

2.1 大流的发现与标记

本文对大小流进行分别选路，因此需要有一种机制来检测大小流。当前业界没有确切统一大象流阈值的大小。研究者们针对不同的网络规模情况，有不同的阈值设定。一般是将占用1%到10%链路带宽的流设定为大象流[12]。控制器通过定期获取每个交换机的每条流条目的统计信息来实现，本文设定平均传输速率不小于链路带宽5%的流条目对应的网络流为大象流。

2.2 网络检测模块

该模块用于实时收集底层交换机的流量统计信息，利用这些信息计算网络的负载状态，并统计链路上的大小流。收集的接口状态信息即是评价系统中的指标，主要包括：链路带宽利用率，传输时延，数据包丢失率，并把这些采集到的数据信息传输到控制器。

将数据中心网络拓扑采用图论方法表示为G=(V,E)；其中V={v1,v2,…,vn}是所有节点集合；E是网络中所有链路的集合；eij∈E表示节点vi和vj之间有连接。

（1）链路带宽利用率

传输链路上已承载的负载与链路总大小的比例。eij链路利用率，如式（1）所示：

其中bwij为链路负载，bc为链路带宽总容量。对于每条完整的路径p=，选取链路eij利用率占比最大的max{buij}作为路径带宽利用率，也称瓶颈链路利用率bur。这里需假设路径中所有链路的带宽总容量相同。

（2）时延

控制器利用发送的LLDP数据包到相应的交换机开始的时间戳，然后交换机转发该数据包到另一台交换机，最后回到控制器的时间戳相减来计算链路时延。假设此过程的时延为T1，同理测得反向的时延为T2;控制器发送echo报文测得到交换机i，j的往返时延为Ti，Tj。则最后的链路eij前向后向的平均时延为dij=(T1+T2-Ti-Tj)/2。对于构成路径p的链路集合，有max{dij};称为路径p的瓶颈时延dr。

（3）丢包率

丢失数据包数量占所发送数据包的比率。对于一条完整的路径p，其丢包率rlp计算公式为：

2.3 k路由算法

对于Fat-Tree的数据中心网络来说，任意两台端主机之间的可选路径非常多。从所有可到达的路径中选出最佳的一条转发路径会造成计算资源的巨大浪费。因此只需要考虑找到源目的节点对之间的多条最短路径，在最短路径之间进行传输即可。在Fat-Tree结构下，源目的节点在同一个pod层之间的等价路径有k/2条，在不同pod层中的等价路径有k2/4。k为pod的数量。

本文采用基于跳数的k条最短路径（KSP）算法找出前k条最短的路径集合P。该算法如下思想如下：首先使用Dijkstra算法计算出原始节点s到目的节点d的第一条最短的路径p()1，并将其放到设置好的最短路径集合A中，之后以第一条最短路径上的节点为基础，逐个计算其余的k-1条次最短路径。在计算的时候，把上除开停止节点以外的全部节点分别当作偏移节点vi，在逐个算出每个偏移节点vi到停止节点d的最短路径，同前面的p(i)上原始节点到偏移节点的路径相连接，组成备选路径的集合B，从B中选择最短的路径作为p( i +1)加入到A中，重述上述步骤求得最终的k条最短路径。此外在计算时应注意以下两点：

防止从起点到终点的整体路径有环。即从vi到d的最短路径不能包含s到vi的路径上的任何节点。

避免与已经在结果列表中的路径重复。即从vi发出的边应该与结果列表中的路径p1,p2,…,pk上从vi发出边的方向保持不相同。

2.4 大象流和老鼠流评价模块

大象流评分模块选择链路带宽利用率和丢包率两个参数作为评价的标准，而老鼠流评分模块选择链路利用率和时延两个参数作为评价的标准。然而这些指标中存在量纲上的不同，必须考虑各个指标因单位和数量级的巨大差异而造成错误的结果，为此要标准化各项评分指标，从而更好地反映真实情况。本文采用极值法[13]对带宽利用率、时延、丢包率进行负指标处理。公式如下：

基于这三个参数提出本文的流分类多指标综合路径评分公式。由于大象流对带宽要求更高，对时延要求不敏感，所以设置其综合评价方案公式为：

ge为大象流路径评价的得分，xbu，xrlp分别表示带宽利用率和丢包率标准化后的权数值。瓶颈链路带宽利用率越低，说明该路径负载较轻，xbu值越大；丢包率越低，说明该路径质量越好，xrlp值越大；则ge的值越大，代表路径性能越好，其中w1+w2=1。

而老鼠流则对时延敏感，对带宽要求不高，所以设置其综合评价方案公式为：

gm为老鼠流的路径评价的得分，xdr，xrlp分别代表时延和丢包率标准化后的权数值。瓶颈时延越低，说明该路径传输的越快，xdr值也越高；同理丢包率越低，说明该路径质量越好，xrlp值越高，则gm的值越大，代表路径性能越好。其中w3+w4=1。

2.5 模型总体过程：

（1）确定数据流源地址与目的地址的信息并找到与其直连的交换机，然后区分大象流和老鼠流。

（2）调用多路径计算模块算出前k条最短可达的路径；

（3）分别调用大象流和老鼠流的评价模块对选出的k条可达路径评分，然后大象流和老鼠流分别选择对应评分最大的最优转发路径进行转发；

（4）最后派发流表给此路径上的全部交换机，引导流量转发。

3 仿真实验与分析

3.1 仿真实验架构搭建

本实验在较为稳定的Ubuntu16.04系统上搭建，并选择在轻量级网络仿真工具Mininet[14]上进行模拟，控制器使用开源的Ryu控制器，对于实验拓扑采用K=4的胖树DCN拓扑，由于Fat-Tree架构可以采用一般商业的交换机来构建，因此网络链路的带宽能够保持一致。其架构在20台交换机下面连接16台终端机，其中核心交换机有4台位于顶层，汇聚层8台，边缘层8台，依次排列。构如图2所示。

通过Iperf流量工具产生模拟网络流量，网络链路带宽均设为10Mbit/s；SDN控制器的网络负载监控周期为5秒，权重指标W大象流和老鼠流的都分别设为0.6，0.4。采用的的数据中心流量模型为:

Staggered Prob（Subnet_P，Pod_P）模式：网络中的主机以Subnet_P的概率向连接到同一边缘层的交换机的主机发送数据，以Pod_P的概率向同一Pod内其他主机发生数据，以1-Subnet_P-Pod_P的概率向不同Pod内的其他主机发生数据。

本文算法将和ECMP、FlowFit[15]算法分别在传输时延、链路利用率两个指标间来衡量对比。验证负载均衡效果的评价指标则选取平均带宽利用率和平均时延来衡量。其中平均带宽利用率是指取所有流的接收端收到的带宽与发送端带宽流量的比值之和再取的平均值。平均时延是指一条流从一端到另一端传输时延的平均值。

3.2 实验结果与分析

为了检验所提出的负载均衡策略性能的优越性，在实验中将LB-FCMI依次与经典的ECMP算法和比较新的FlowFit大象流调度算法做对比，用平均带宽利用率和平均时延两个指标来对数据流进行分析比较。其中ECMP是一种在所有的可用路径上分配相同数量的流量的一种算法，当数据流大小一致时负载均衡效果较好；FlowFit是一种针对大象流的负载均衡算法，主要方法是将出现拥塞路径上的最大流调度到剩余负载轻的路径上来，以此缓解网络拥塞程度。

Staggered Prob模式下的仿真结果如图3所示：以Staggered（0.5，0.3）模式每隔1秒向其他主机发送数据流，流量负载从0.1逐步增加至0.9。

图2 4元Fat-Tree网络拓扑结构

由图3可知，LB-FCMI的平均带宽利用率要高于ECMP和FlowFit。刚开始时网络负载较低，三种方式都有足够的带宽传输，平均带宽利用率较高。随着负载增加，三种方式的利用率开始下降，其中ECMP下降最快，这是因为ECMP并未考虑链路带宽情况，可能将数据流分配到负载较高的一条路径上，造成网络拥塞。FlowFit仅仅对路径上最大的大象流进行调度而忽略了其余大象流，因此可能导致链路拥塞。而LB-FC⁃MI采用综合评级指标来对大流进行调度，选择评分最高的最佳路径来对大流进行调度，减小了调度路径拥塞的可能，提高了平均带宽利用率。

图3 平均带宽利用率

图4 描述了在Staggered Prob模式下三种方式的平均时延随着流量负载变化的情况。可以看到，随着负载从0.1逐步增加至0.9，其时延也不断上升，其中ECMP上升的最快，LB-FCMI最慢。这是因为ECMP没有考虑链路状态信息，只是使用简单的哈希散列方式随机分发流量，可能会把流分发到链路负载已很高的路径上去，从而加重网络拥塞层度，导致数据包的传输时间过长，平均时延较高。而FlowFit和LB-FCMI不仅仅注意路径的负载，并可以随着路径情况的变化将流调度到其余负载层度较低的路径上去，从而降低数据包的传输时间。FlowFit在调度时仅考虑对各条大象流进行选择，而LB-FCMI不仅考虑对大象流进行调度，还对老鼠流进行合理的调度分配，避免了部分小流因大流长时间占据带宽而导致的时延增加，从而进一步减小网络拥塞，所以平均时延低于FlowFit。