基于SDN 的数据中心网络流量负载均衡研究

王灵矫，李 文，郭 华

(1.湘潭大学 自动化与电子信息学院，湖南 湘潭 411105；2.湘潭大学 智能计算与信息处理教育部重点实验室，湖南 湘潭 411105)

软件定义网络（software-defined networks，SDN）[1-2]实现了转发平面与控制平面的分离，具有可编程、集中控制和自动化等特点.集中控制的特点适用于数据中心，数据中心网络（data center network，DCN）的规模随着各种云服务的发展越来越大，信息服务的集约化和专业化使互联网上的应用、计算和存储向数据中心迁移容易出现故障、拥塞等问题.网络的大部分流量为持续时间很短的小流，Benson[3]等对数据中心的实测数据显示，80%以上的流量为小流，不到20%的大流却包含了超过90%的数据流量，承载大量数据的大流是造成网络拥塞的主要原因.

近年来，大量的研究都聚焦于大小流的检测和调度.文献[4]针对DCN 的具体拓扑和流量特性，提出了一种基于SDN 的流量调度方法，对源目地址相同的大流进行聚合，利用改进的果蝇优化算法对聚合后的大流统一调度，该方法时间复杂度较高.文献[5]给出一种细粒度流分类方法，通过预分类和精确分类两层结构的二分类方案来检测大/小流，但该方法缺乏对分类后的算法设计.文献[6]提出了一种针对大流的低成本的流调度框架，轮询周期根据实时网络负载动态调整，但该方法未考虑时延.文献[7]采用差异化的调度算法DIFFERENCE，使用加权多路径路由算法调度小流，根据链路利用率调整路径权值，提出一种基于阻塞岛的大流路径设置算法，实现更小的空间找到最不拥塞的路径.文献[8]使用经典的多协议标签交换（multi-protocol label switching，MPLS）技术聚合多路径流后传输，比传统的OpenFlow 更能有效减少交换机的流条目数量，提高了处理效率，但该方法可能会导致新的拥塞.文献[9]对SDN 网络进行拥塞感知和流量调度研究，提出了基于链路利用率样本方差的流量分配优化模型，采用了混沌遗传算法求解这一NP 难问题，但该方法的量化指标单一，仅对带宽利用率寻优.文献[10]提出了一种可扩展的动态流调度系统Hedera，能自适应地调整多级交换结构和有效地利用聚合的网络资源.文献[11]针对SDN中基于动态多路径的流量管理方法提出估计端到端延迟并计算最小成本路径，将流量重新路由到最佳路径.文献[12]提出一种基于多路径传输的动态路由算法，重新定义链路关键度并求解链路权值优化问题，该算法复杂度较高.传统的等价多路径路由（equal cost multi-path，ECMP[13-14]）算法没有拥塞感知机制不能实时获取链路状态，可能会将多个大流调度到同一条链路导致拥塞.未充分考虑链路实时状态，若数据中心的流量短期内出现随机波动，可能会造成大流碰撞出现路径拥塞等问题，影响网络性能.目前大量研究对于时延的测量精度较为粗糙，可能影响实际最优路径的选取.全局最佳拟合算法（global best fit algorithm，GBFA）作为一种贪婪启发式算法，处理大部分流量时表现良好.但在大多数流量不够大的情况下，GBFA 会导致一些路径被小流占据，而其他路径处于空闲，造成链路存在大量的带宽碎片.

针对数据中心网络流量负载不均衡问题，本文给出了一种基于SDN 流量的时延调度算法（dynamic scheduling algorithm-delay，DSA-D）.其基本思想是基于跳数，利用精确的路径时延从最短路径集中筛除部分次优路径.针对GBFA 易造成带宽碎片浪费带宽资源的问题，本文将链路可用带宽与流带宽需求作为权重引入GBFA，提升流量负载均衡准确性和效率.由于大流对带宽要求高，算法主要对大流进行调度计算，小流则采用ECMP 计算下发路径.

本文主要的贡献如下：

（1）根据性能参数跳数、时延和可用带宽，提出基于SDN 的DSA-D 流量负载均衡方法为数据流寻找最优转发路径；

（2）提出基于时延的最优路径模型，通过周期下发的LLDP 和ECHO 报文来探测链路时延，计算链路精确时延，利用时延最优路径算法求解流量下发路径；

（3）提出将GBFA 算法与概率方法相结合的概率拟合（GBFA-P）算法，考虑了路径可用带宽和流带宽需求，提高了吞吐量并减少带宽碎片；

（4）基于Ryu 控制器实现了DCN 流量负载均衡的相关实验，结果表明：在相同场景下，DSA-D比ECMP、Hedera 和DIFFER 提高了平均吞吐量、链路带宽利用率，降低了平均往返时延.

1 分析与建模

1.1 问题描述Fattree[15]是一种经典的拓扑结构，原型为Clos 架构，具有较优的网络故障恢复能力和拓展能力以及通信带宽，被研究界广泛使用.图1 展示了一个K=4(K为每个交换机的端口数或Pod 的个数)的Fattree 结构.若采用ECMP 转发，可能会产生冲突，导致交换机过载或链路拥塞(如图1 所示的由ECMP 采用哈希方法导致的局部冲突).网络负载均衡需要完成两项主要工作：①检测数据流的大小；②设计有效的调度算法计算路径，提高负载均衡度.

图1 ECMP 算法可能导致的网络冲突Fig.1 Possible network conflicts caused by ECMP algorithm

1.2 基于DSA-D 的流量负载均衡技术

1.2.1 框架介绍 负载均衡框架由链路和时延探测模块、流量分类模块、流量调度模块3 部分构成.基于DSA-D 的流量负载均衡框架如图2 所示.

图2 基于DSA-D 算法的流量负载均衡框架Fig.2 Traffic load balancing framework based on DSA-D algorithm

链路和时延探测模块周期调用控制平面与数据平面之间的南向协议接口，获取OpenVSwitch 交换机各个端口的统计数据.流量分类模块根据接口统计数据对流量的速率检测后进行分类.流量调度模块结合当前网络状态及流的需求，为流量计算最优下发路径.

1.2.2 符号定义 网络拓扑图表示为G(V,E)，V表示交换机节点集合，E表示交换机边的集合，V={v1,v2,···,vM}，E={e1,e2,···,eN}，M为网络的交换机总数，N为总边数，u、v(u≠v)表示任意两个交换机节点，eij表示节点i和j之间的链路，链路带宽为B.G(V,E,t)表示在时间t时的网络图，t∈{t1，t2，···，Tc为探测周期.

1.2.3 流量分类 根据数据中心网络流量特征，采用基于流采样的检测方法[16]，传输速率超过链路容量的10%定义为大流，并新增一个流生存时间避免流条目生存时间过短影响计算，流量传输速率计算如下.

（1）流生存时间：

式中：ft1和ft2分别为流采样的两个时刻.

（2）流生存时间限制：

（3）流传输的字节数：

（4）流传输速率：

式中：fb为流传输的字节数，B为链路容量.

（5）流分类：

2 流量负载均衡算法—DSA-D 算法

DSA-D 算法通过结合GBFA 与路径可用带宽及流带宽需求，调度前对流量进行分类，从最短路径中利用路径时延筛除部分次优路径，将可用带宽与流带宽需求作为分配权重，实现吞吐量和链路利用率的提高.

DSA-D 算法的基本流程图如图3 所示，主要包括最短路径初筛、时延最优路径筛选、GBFA-P概率拟合算法分配路径3 个阶段.

图3 DSA-D 算法基本流程图Fig.3 Basic flow chart of DSA-D algorithm

2.1 最短路径初筛网络链路的状态信息会实时变化，而在网络状态没有异常情况下基于跳数的网络路由相对稳定.在复杂网络中，如果频繁更新路由会导致计算成本增高，考虑成本和开销，本文将跳数作为初步筛查指标.首先计算源主机和目的主机的最短路径集合，定义每个流的一个3 元组信息，分别为源IP，目的IP，流量的带宽需求fc，采用KSP算法寻找k最短路径集.

为防止无效查找，限制其路径跳数不超过设定的阈值H.其约束如：

此外，流量的带宽需求应小于被选择路径的剩余带宽，约束如：

式中：b(u,v)为链路e(u,v)的剩余带宽.

除了接入层交换机节点以外，网络结构的所有节点的出流量等于入流量，如：

式中：f(u,v)为布尔变量，若u,v之间存在链路则f(u,v)=1，否则f(u,v)=0.

2.2 时延最优路径筛选将筛选后的最短跳数路径集进行时延探测，计算链路的真实时延Tt(u,v)，时延探测分别为LLDP 和ECHO 探测，如图4 所示.

图4 LLDP 和ECHO 时延探测原理图Fig.4 Schematic diagram of LLDP and ECHO delay detection

LLDP 探测过程：控制器下发含有发送时间戳的LLDP 探测数据包，控制器收到返回的Packet/in请求并解析LLDP 数据包，获得发送时间节点计算LLDP 时延.LLDP 报文的发送与收到时间之差T1为图4 红色虚线和实线组成的1-2-3 循环；反向的数据包发送与接收时间差T2为图4 黑色虚线和实线组成的4-5-6 循环.

ECHO 探测过程与LLDP 时延探测相似，控制器发送含有发送时间戳的ehco/request 探测数据包，控制器解析交换机返回的echo/reply 报文.ECHO报文的发送与接收时间之差为Ta为图4 黑色椭圆包围的红色虚线1 和黑色虚线6，Ta是控制器与交换机A 的ECHO 时延；同理控制器与交换机B 的ECHO 时延为Tb为图4 红色椭圆包围的黑色虚线4 和红色虚线3.

假设链路的往返时延相等，Tt(u,v)可表示为：

为了保证时延探测的有效性，对LLDP 和ECHO探测时间进行限制，如下所示.

式中：Tl和Te为LLDP 和ECHO 探测周期为LLDP 和ECHO 实际探测时间.

网络的状态是实时变化的，为了求出k/2 最优传输时延路径集，研究某一探测周期内的k/2 最优传输时延路径，最小化传输时延可写成

式中：Tt(u,v)为在t时刻链路e(u,v)的时延.

通过上述步骤可得到一个由时延优先级构成的路径集p={p1,p2,···,pk/2}，用概率拟合算法对路径集P进行处理，实现流量负载均衡的目的.

2.3 概率拟合算法（GBFA-P）用改进的GBFAP 算法对k/2 时延最优模块的路径集进行计算，采用GBFA 算法和概率方法消除带宽碎片.假设源目地址之间经过跳数和时延最优路径筛选得到路径集p={p1,p2,···,pk/2}，第i条路径pi={pi1,pi2,···,pix}，由x条链路组成.令Pb表示第pi条路径源目地址间的剩余可用带宽，可表示为：

式中：B为链路容量，bij为路径pi上第j条链路的已用带宽.

假设网络存在y条数据流y={f1，f2，···，fc，···，fy}，有n条不同的路径可以容纳数据流Fc，用ri表示第i条可选路径剩余带宽（Pb）与流的带宽需求（fc）之比.可表示为：

最终得到第i条路径被选择的概率计算公式为：

在一个时间周期内，流的所有候选路径剩余带宽都是确定的，概率拟合算法的关键是根据流的剩余带宽和带宽需求的比值分配路径的选择概率.候选路径被选中的概率与其剩余带宽成反比，剩余带宽与带宽需求差值越小，被选择的概率越大.

2.4 DSA-D 算法总结DSA-D 算法步骤如下：

步骤1接收来自流量分类模块的大小流，若为小流，则通过ECMP 分配转发路径，否则继续步骤2；

步骤2若为大流则请求控制器调用链路拓扑信息，计算k最短跳数路径集.并进入步骤3；

步骤3根据步骤2 得到的k最短跳数路径集合，对集合中的链路进行LLDP 和ECHO 时延探测，进入步骤4；

步骤4计算链路的精确时延，采用时延最优算法寻找k/2 时延的最优路径集；

步骤5将流带宽需求与链路可用带宽的比值作为权重，GBFA-P 结合权重选择最佳路径，控制器按所选路径下发流条目.

DSA-D 算法引入LLDP 和ECHO 时延探测，利用链路时延对路径优先级排序，提高了筛选指标的精度；GBFA-P 对最优时延路径计算其剩余带宽，分配方案结合了概率方法，可以消除一定的带宽碎片，提高链路利用率和吞吐量.

3 仿真实验

3.1 仿真环境本文在Linux 系统上使用Ryu 控制器实现了DSA-D 算法，使用mininet 模拟SDN网络环境，采用Iperf 软件模拟发包测试算法.主机配置为2.40 GHz，8 GiB 内存CPU，操作系统为Ubantu 14.04.

在如图1 所示的4-Pod Fattree 网络拓扑中，核心层交换机的n个端口分别连接到每个Pod 的某一个汇聚层交换机.设置KSP 算法的候选路径k=12，链路拓扑探测周期Tc为2 s.链路带宽为10 Mibit/s，使用Iperf 发包测试，每组实验测试时长60 s.

仿真使用2 种流量模式：

（1）Random：每台主机以相同的概率向其他主机发送数据；

（2）Stag（EdgeP，PodP）[17]：主机以概率EdgeP发送到同一接入交换机中的另一个主机，称为Pod内流量.以概率PodP 发送到相同的Pod 且不在同一接入交换机的主机.以概率1-EdgeP-PodP 发送到网络的其余部分.采用一组随机模型和最接近数据中心的4 种流量模型进行发包测试，每组重复20 次，每种流量模型结果取平均值：{random、stag_0.5_0.3、stag_0.6_0.2、stag_0.7_0.2、stag_0.8_0.1}.

3.2 性能评估指标实验比较DSA-D 与ECMP、Hedera 和DIFFER 算法，性能评估指标主要包括平均吞吐量（Ca）、链路带宽利用率（Bu）、平均往返时延（Td）3 个指标.

（1）平均吞吐量 网络系统在当前流量模型下获得的吞吐量的平均值，表示如下：

式中：Ci为路径Pi的吞吐量，n为路径总数.

（2）链路带宽利用率 每条链路实际使用的平均带宽和链路带宽的比例，表示如下：

式中：bij为路径Pi上第j条链路的已用带宽，m为路径上的链路总数.

（3）平均往返时延 数据包从客户端发出到收到服务器端回复的数据包平均时延，表示如下：

式中：Tbi为第i个数据包的往返时延，x为数据包总数.

3.3 结果分析图5 所示的柱状图直观地显示了DSA-D 算法与ECMP、Hedera 和DIFFER 算法的平均吞吐量对比.stag_0.5_0.3 表示Pod 内流量占50%，同一Pod 但不在同一接入层交换机占30%，其余部分占20%，random 则表示3 部分相等.从总体上看，随着Pod 内流量从50%增加到80%，ECMP、Hedera、DIFFER、DSA-D 的平均吞吐量也随之提高.在Pod 内流量较低的情况下，DSA-D 对平均吞吐量的提升较为明显.

Hedera 在调度网络流量时，初始利用ECMP算法进行调度，通过重新调度链路上发现的大流，DSA-D 始终采用SDN 的集中调度来处理.从实验结果可以看出，DSA-D 在大部分情况下都比ECMP、Hedera 和DIFFER 能取得更好的吞吐量，证明了基于SDN 的DSA-D 调度方法在数据中心的有效性.

表1 显示了各算法在不同流量模型下的平均吞吐量的对比，DSA-D 比ECMP、Hedera 和DIFFER提高了12%、7.6%、6.1%的总平均吞吐量.其中，在random 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升37.9%、8.1%、11.1%；在stag_0.5_0.3 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升13.3%、11.1%、4.7%；在stag_0.6_0.2 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升6.5%、9.2%、5.4%；在stag_0.7_0.2 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升8.5%、5.5%、2.7%；在stag_0.8_0.1 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升5.3%、4.3%、2.6%.可以看出，在5 种流量模型中，DSA-D 算法在random流量模型中最为有效，但随着Pod 内流量的增加，DSA-D 算法的提升程度逐渐下降.

表1 各算法在不同流量模型下的平均吞吐量对比Tab.1 Comparison of average throughput of algorithms under different traffic models Mbit

不同流量模型下的链路利用率如图6 所示，在Pod 内流量较低时，网络中被使用到的链路较多.随着Pod 内流量提高，链路利用率逐渐降低.ECMP 和Hedera 在Pod 内流量占比较高时，大流的碰撞较多，容易造成链路拥塞，链路带宽利用不均衡.DSA-D 和DIFFER 算法对大小流的传输分别优化，更好地利用了链路，两者相比DSA-D 链路利用率更高.在5 种流量模型中，DSA-D 始终取得最高的链路利用率.

图6 不同流量模型下各算法的链路带宽利用率Fig.6 Link bandwidth utilization of algorithms under different traffic models

图7 展示了各流量模型的平均往返时延结果，在数据流的传输过程中，由于大流的干扰，ECMP和Hedera 的平均往返时延起伏较大.DSA-D 采用SDN 集中控制的方法，当数据包非首包时，交换机会利用已有的策略处理数据包的流条目，将数据包快速转发出去.所以DSA-D 方案的平均往返时延较为稳定，性能最好.

图7 不同流量模型下各算法的平均往返时延Fig.7 Average round trip delay of algorithms under different traffic models

表2 显示了各算法在不同流量模型下的的平均往返时延对比，DSA-D 算法相较于 ECMP、Hedera、DIFFER 分别降低了30.01%、10.84%、5.07%的总平均往返时延，其中，在random 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升17.3%、8%、2.5%；在stag_0.5_0.3 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升45.5%、13.7%、7.5%；在stag_0.6_0.2 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER 分别提升35.6%、17.2%、11.7%；在stag_0.7_0.2 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER分别提升17.3%、8.1%、0.2%；在stag_0.8_0.1 流量模型下，DSA-D 算法相对ECMP、Hedera、DIFFER分别提升25.9%、6%、2.8%.可以看出，DSA-D 算法在stag_0.5_0.3 提升效果最好.随着Pod 内流量的增加，DSA-D 提升程度逐渐下降.

表2 各算法在不同流量模型下的平均往返时延对比Tab.2 Comparison of average round-trip delay of algorithms under different traffic models ms

4 结束语

本文针对网络流量日益增长导致的数据中心网络拥塞和负载不均衡等问题，综合考虑控制开销、链路时延以及可用带宽，实时检测链路时延状态，将SDN 应用于数据中心网络环境，对流量的大小进行分类并采用不同的调度算法，对大流进行k最短跳数筛选.根据LLDP 和ECHO 探测的时延计算得到精确的链路时延，筛除时延较大的路径，求解k/2 最优时延链路集，利用GBFA-P 将可用带宽与流需求作为权重选择最佳路径.实验结果表明，DSA-D 算法提升了网络的吞吐量、链路带宽利用率，降低了平均往返时延.虽然该算法一定程度上提高了负载均衡，但在Pod 内流量较高时仍有提升空间.今后的工作将集中在控制器的负载研究，以及减少流的平均完成时间，从而提高传输效率.