0.   引言

近年来，受到云计算、大数据、物联网等新兴产业快速发展的影响，全球数据信息量呈现爆炸式增长趋势，为满足巨量信息的存储和处理需求，数据中心已成为不可或缺的信息基础设施平台，负责管理和维护海量的计算和存储设备。伴随着数据中心规模不断增长、部署业务种类日益丰富，网络拥塞问题日益成为制约数据中心性能的一大因素，研究如何缓解数据中心网络拥塞具有十分重要的意义。

数据中心网络产生拥塞的原因主要有以下3点。

1）传统网络的路由协议不适用于数据中心网络。例如传统的生成树协议会沿着单一路径转发数据包，没有充分利用数据中心网络的富连接多路径，链路利用率低，且固定路由寻址方式易导致链路发生拥塞^[1]。此外，数据中心网络目前广泛使用的等价多路径（Equal-Cost Multi-Path，ECMP）路由算法^[2]基于哈希算法随机选择路由，最坏情况下会将多条大流映射到同一条路径上，导致链路拥塞，而其他的链路却处于空闲状态。

2）持续增长的东西流量与数据中心网络内有限带宽之间的矛盾造成拥塞。根据源地址和目的地址不同，可以将数据中心网络内的流划分为两大类，即南北流量和东西流量。其中，南北流量是指从数据中心外到达数据中心内，进行处理后离开的流量；而东西流量则指同一个数据中心内部服务器之间产生的流量^[3]。云计算、大数据的发展，使数据中心内多机协同运算变得越来越普遍，数据中心内部服务器之间流量不断增加，其流量模式也从原来的南北流量占主导地位，逐渐演变为如今的东西流量占主导地位，数据中心网络原拓扑的带宽分配难以满足持续增长的东西流量的通信需求，对应的链路存在很高的拥塞风险^[4]。

3）数据中心网络流量的突发性易引起链路拥塞。文献[5]的统计结果表明，数据中心网络中的流量具有很高的瞬时到达率，即本质上数据中心网络的流量具有突发性，而流量突发性造成的拥塞会同时和数十条链路相关联。文献[6]中指出，如果某些业务的路由经过拥塞链路，会导致业务数据传输失败概率增加1.1倍，明显降低其服务质量。

数据中心中通常运行着多元应用，能为用户提供数据分析、Web搜索、移动互联网应用等不同的服务。多种差异化的应用会产生差异化的流量，现有的数据中心网络中的流量大体上可以划分为2种类型^{[3, 7]}：一种类型是小流，其数据大小通常小于100 kB，如游戏、语音和用户查询等应用通常产生小流，呈现出持续时间短、高度随机性和对时延敏感等特性；另一种类型是大流，其数据大小通常在几MB到几GB，虚拟机迁移、文件备份、数据分析等应用通常产生大流，呈现出持续时间长、吞吐量大且对网络带宽敏感等特性。在研究网络拥塞避免策略时，需要考虑和利用数据中心业务的大小流特性。

现有的解决数据中心网络拥塞的方法包括增大交换机缓存能力^[8-9]、修改TCP参数^[10-11]和重路由^{[1, 4, 12-13]}等技术，但也存在不足。增大交换机缓存能力能一定程度上对抗业务分组突发的拥塞，但会受到交换机缓存容量的约束，而增大交换机缓存能力意味着高昂的经济支出。修改TCP参数的方法主要是对TCP拥塞控制参数进行修改，从而控制发送端的分组发送速率，通常用于单条端到端业务流的拥塞避免。现有的基于重路由避免数据中心网络拥塞的方法中，一部分方法没有考虑数据中心网络的大小流特性，而对小流执行重路由容易导致其时延明显增加；另一部分方法仅以链路利用率作为重路由路径的选择标准，但实际上由于链路时延性能不仅与链路利用率有关，也与链路带宽、链路是否有多个大流汇聚等因素有关，因此仅考虑链路利用率单一指标的重路由方法，缺乏对链路利用率、链路时延性能的综合表征，没有建立链路利用率和链路时延的关联关系，可能导致重路由路径上的时延性能较差。

针对上述提到的问题，本文提出一种基于路径关键度的拥塞避免重路由方法，首先综合考虑链路负载和链路时延，设计了链路关键度指标，用来表征大流对链路的影响程度；然后将重路由路径分配问题，建模为以最小化最大链路关键度为优化目标的整数多商品流问题；最后提出了基于路径关键度的重路由算法，将大流调度到关键度较低的路径上，能有效地缓解链路拥塞，进而保证网络性能。

1.   系统模型

本文将数据中心网络建模成一个无向图G= < V, E > ，其中集合V包括所有交换机和服务器，集合E包括网络中所有链路。e=(u, v)∈E代表节点u和节点v之间的一条通信链路。同时，本文将拥塞链路上的大流建模为一组流F={f₁, f₂…f_k}，第k条大流可以用一个三元组f_k= < s_k, d_k, r_k > 表示，其中s_k、d_k和r_k分别表示大流f_k的源节点、目的节点和传输速率。数据中心网络与流建模示意如图 1所示。图中的流f1= < v15, v19, r₁ > ，即流f₁的源节点为v15，目的节点为v19，传输速率为r₁。

图  1  数据中心网络与流建模示意

Figure  1.  Modeling for data center networks and flows

下载: 全尺寸图片 幻灯片

2.   基于路径关键度的拥塞避免重路由方法

2.1   拥塞避免重路由方法步骤

基于路径关键度的拥塞避免重路由方法利用了基于软件定义网络（Software Defined Networking，SDN）的数据中心网络架构^[4]，利用SDN控制器获得全局网络视图和业务流参数，方便监控和管理网络状态。本文的重路由方法主要包括3个步骤：链路拥塞状态检测、大流检测和重路由路径分配。

1）步骤一：链路拥塞状态检测。为了观察数据中心网络是否出现拥塞，需要知道当前网络的状态信息。考虑到交换机端口相互连接组成了链路，再结合数据中心网络拓扑如Fat-tree^[14]的特点，利用SDN控制器向所有的汇聚层交换机发送“端口统计量请求消息”，随后每个汇聚层交换机向SDN控制器回复“端口统计量回复消息”。通过每隔固定的时间间隔，SDN控制器轮询每个汇聚层交换机的方式，获取和存储网络中所有链路的负载信息。本文通过判断链路负载是否超过拥塞阈值，确定链路的拥塞状态。如果链路负载未超过拥塞阈值，则认为链路没有发生拥塞，反之，则认为链路发生了拥塞。

2）步骤二：大流检测。为了检测大流，需要知道网络中所有的流信息，本文通过每隔固定的时间间隔，利用SDN控制器向所有边缘层交换机发送流“流统计量请求消息”的方式来获取网络中所有的流信息。根据数据中心网络的大小流特性可知，小流的特点是持续时间短且时延敏感，如果重路由小流增加其时延，会造成其超时。而考虑到大流的非时延敏感特性，本文选择重路由大流来避免链路拥塞。利用边缘层交换机回复的“流统计量回复消息”可以计算流的速率，进而区分大小流。流速率的计算公式为：

式中：r_k表示第k条流的速率；bt和b_t–T分别表示在t时刻和t–T时刻，SDN控制器收到边缘层交换机回复的“流统计量回复消息”中流的总字节数；T为固定的时间间隔，同文献[12]一样，本文将速率大于链路带宽10%的流判断为大流。

3）步骤三：重路由路径分配。为拥塞链路上的大流选择新路径需要遵循原拥塞链路不再拥塞，并且避免新路径上链路拥塞的原则。本文将重路由路径分配问题建模为以最小化最大链路关键度为目标的优化问题，具体问题描述见2.3节。

2.2   链路关键度定义

由于链路负载和链路时延均是表征链路质量的重要参数，因此本文综合考虑链路负载和链路时延来定义链路关键度指标，用来表征大流对链路的影响程度，链路e∈E的关键度w_e表示为：

式中：B_e和D_e分别表示链路e的负载和分组在链路e上的时延；B_max和D_max分别表示该链路最大的链路容量和最大的链路时延；α和β分别表示链路负载和链路时延的权重，并且α和β之和等于1。

链路利用率与负载是线性关系，链路时延为链路首节点对分组的处理时延、分组排队时延、传输时延和传播时延之和，链路时延与负载的关系目前难以精确描述，因此本文通过测量结果近似的方式，建立链路分组时延与链路负载之间的关系，为流调度之后链路时延变化提供依据。当分组长度固定时，可以认为链路首节点（主要是交换机）的处理时延和传输时延是固定值，对时延性能的变化影响不大；传播时延和链路长度有关，当网络拓扑给定，传播时延也是固定值，随链路负载变化的主要是分组的排队时延。

链路时延测量场景图如图 2所示。

图  2  链路时延测量场景图

Figure  2.  Scenario for link delay measurement

下载: 全尺寸图片 幻灯片

本文在采用图 2所示的场景中，利用SDN控制器对链路时延进行测量，从而得到链路时延和链路占用率的关系。相关的拓扑涉及4台主机（用符号H1，H2，H3，H4表示）和4个交换机（用3001、3002表示2个边缘层交换机，用2001、2002表示2个汇聚层交换机），链路带宽设置为100 Mbps。主机H1和H2同时沿着相同的路径3001→2001→3002分别向主机H3和H4发送模拟的数据流，2条数据流分别用符号f₁₃和f₂₄表示。测量中利用Iperf工具发送模拟的数据流，对Iperf发包命令中的–b参数分别设置为5、10、20、30、35、40 Mbps，–b参数设置的是Iperf的最大允许发送速率，实际测量值可能低于该参数。本文在不同发送速率下测量10组，每组测试100 s，每秒记录一次链路时延，得到的10组链路3001→2001和链路2001→3002的时延均值随链路占用率变化的散点图分别如图 3和图 4所示。

图  3  不同链路占用率下对链路3001→2001时延的测量结果（链路带宽100 Mbps）

Figure  3.  Measured delay versus occupancy ratio in link 3001→2001 with 100 Mbps bandwidth

下载: 全尺寸图片 幻灯片

图  4  不同链路占用率下对链路2001→3002时延的测量结果（链路带宽100 Mbps）

Figure  4.  Measured delay versus occupancy ratio in link 2001→3002 with 100 Mbps bandwidth

下载: 全尺寸图片 幻灯片

通过对不同流发送速率下测量得到的10组数据进行平均，并对结果进行曲线拟合，可得到链路3001→2001的时延和链路2001→3002的时延与链路占用率之间的函数关系，分别如图 5和图 6所示。

图  5  链路3001→2001的时延与链路占用率的关系（链路带宽为100 Mbps）

Figure  5.  Relationship of delay versus occupancy ratio in link 3001→2001 with 100 Mbps bandwidth

下载: 全尺寸图片 幻灯片

图  6  链路2001→3002的时延与链路占用率的关系（链路带宽为100 Mbps）

Figure  6.  Relationship of delay versus occupancy ratio in link 2001→3002 with 100 Mbps bandwidth

下载: 全尺寸图片 幻灯片

对比图 5和图 6可以看出，链路时延不仅与链路占用率有关，而且与链路是否有多个大流汇聚有关。在相同的链路占用率下，链路3001→2001的时延明显大于链路2001→3002的时延，而随着链路占用率的增大，链路3001→2001的时延增长趋势也不同于链路2001→3002。这是因为随着流速率的增大，在大流汇聚的节点，不同流的分组会竞争传输资源，导致分组的排队时延增加明显，而多个大流合并成单个大流之后，在节点2001上发送时没有分组间的竞争，从而测量的链路时延非常小。文献[15]中测量了链路往返时延随链路占用率逐渐增大的变化情况，其结果与本文测量的链路2001→3002的时延变化趋势一致。根据链路时延测量结果，可以建立如下的链路时延和链路占用率之间的函数关系。根据链路占用率与链路时延的关系，可以估计出重路由流调度之后链路时延的变化情况。

2.3   基于最小化最大链路关键度的重路由优化问题

本文将重路由路径分配问题，建模为以最小化最大链路关键度为优化目标的整数非线性规划问题，具体描述如下。

式中：二进制变量x^k_e表示大流是否会经过链路e(e∈E)，因此有流守恒约束式（5）和（6），out(v)和in(v)分别表示以节点v为起点的边的集合和以节点v为终点的边的集合。约束（5）表示对于大流f_k而言，从非源节点、非目的节点流出的流数量等于流入该节点的流数量。约束（6）表示对于大流f_k而言，从源节点流出的流数量比流入源节点的流数量多1个。其次将大流f_k的原路径建模为X^k_e，其表示大流f_k原本是否经过链路e(e∈E)，如果大流f_k原本经过链路，则X^k_e等于1，否则X^k_e等于0。本文针对检测到拥塞后的重路由路径分配问题，假设每条流的原路径是已知的，即X^k_e(∀e∈E, k∈F)是常量，因此公式（7）用来计算重路由后的链路负载，其中B′_e和B_e分别表示重路由前后的链路负载。为了保证每条链路上所有流的速率之和不能超过该链路的容量，因此有带宽约束（8）。本文假设如果重路由路径上原来的链路占用率小于0.1，则认为原来链路上存在的是小流，将大流重路由到该链路后不发生大流汇聚；否则，认为会产生改变链路时延特性的大流汇聚。同时本文将链路占用率为0.75带入公式（3）中可以分别得到有无大流汇聚情况下的链路最大时延值。可以看出，该优化问题是一个NP-Hard的整数多商品流问题。因此，本文设计了一种启发式算法来实现最小化最大链路关键度的目标。

2.4   基于路径关键度的重路由算法

由于上节建模的非线性问题，难以直接求解，本文设计了一种基于路径关键度的重路由（Rerouting based on Path Criticality，RPC）算法来近似求解该优化问题。考虑到多条链路相互连接组成路径，本文将路径关键度定义为组成该路径的所有链路的关键度之和，即

式中w_pn表示路径p_n的关键度。

基于路径关键度的重路由算法的主要步骤如算法1所示。首先SDN控制器向网络中的所有汇聚层交换机发送“端口统计量请求消息”获取和存储链路的负载信息，向所有的边缘层交换机发送“流统计量请求消息”获取网络中的流信息，计算流速率并存储网络中的大流。然后当检测到链路发生拥塞时，将拥塞链路上的流信息与存储的大流信息进行比对，从而确定出拥塞链路上正在传输的所有大流，并添加到集合F中，最后为F中的每条流f_k计算重路由路径。具体计算过程为：首先根据流f_k的源节点和目的节点信息，计算其可行的最短路径集合P；然后依次计算P中每条路径的关键度；最后从P中选择关键度最小的路径作为流f_k的重路由路径，同时SDN控制器向相应的交换机下发新的流表项。

算法1：基于路径关键度的重路由（RPC）算法

输入：数据中心网络拓扑G= < V, E >

输出：拥塞大流的重路由路径

1、SDN控制器获取和存储链路负载和大流信息；

2、for集合E中的链路e do

3、   if链路负载超过拥塞阈值then

4、   确定拥塞链路上所有大流，并放入集合F

5、   end if

6、end for

7、for F中的流fk do

8、计算fk的可行最短路径集合P

9、   for P中的路径pndo

10、     for e∈pn do

11、     利用公式（2）计算链路e的关键度

12、     end for

13、     利用公式（10）计算路径pn的关键度

14、   end for

15、   pmin←集合P中关键度最小的路径

16、end for

17、return {pmin}

下载: 导出CSV 

| 显示表格

3.   应用场景与性能仿真

3.1   应用场景

伴随着数据中心规模和数量的快速发展，数据中心耗电大、占地广、供电难的问题逐渐凸显，国家电网有限公司于2019年提出变电站、充换电站（储能站）和数据中心站的“三站合一”建设模式，传统变电站升级为集电力业务数据采集和处理、电力能源管理和调度等多功能为一身的智慧变电站，每个变电站可作为边缘数据中心，充分挖掘和利用电力大数据，推进能源互联网的建设。目前我国正大力推进涉及5G基站建设、特高压、城际高速铁路和城市轨道交通、新能源汽车充电桩、大数据中心、人工智能、工业互联网七大领域的“新基建”战略，每个领域都将对“三站合一”模式带来新的挑战与机遇。本文提出的基于路径关键度的拥塞避免重路由方法，既可以用于处理单个电力边缘数据中心网络拥塞问题，提升单个变电站的数据处理能力，也可用于缓解多个电力数据中心之间的网络拥塞，提升多数据中心的协作效率，提升对电力和互联网大数据业务的处理效率。

3.2   仿真设置

3.2.1   仿真拓扑

在本文的仿真中，拓扑采用Fat-tree结构，如图 7所示。

图  7  k=4的Fat-tree拓扑

Figure  7.  Fat-tree topology with k=4

下载: 全尺寸图片 幻灯片

Fat-tree结构主要由核心层、汇聚层、边缘层组成。Fat-tree拓扑具有以下特点^[16]：①各层均采用廉价的商用交换机，降低了纵向扩展所带来的高成本；②由于各层采用廉价的商用交换机，为了保证网络的可靠性，所有的汇聚层和边缘层交换机被划分为不同的集群Pod，并采用全相连的方式将Pod内的汇聚层和边缘层交换机连接起来。对于k（k是偶数）个集群Pod的Fat-tree拓扑^[14]，每一个Pod包含k/2个汇聚层交换机和k/2个边缘层交换机，并连接k²/4个核心层交换机。对于每一个k端口的边缘层交换机，其k/2个端口与汇聚层交换机相连，其余k/2个端口与服务器相连。对于每一个k端口的汇聚层交换机，其k/2个端口连接到边缘层交换机，其余端口连接到核心层交换机。

3.2.2   软件及参数设置

本文利用Mininet软件在Linux系统上搭建Fat-tree拓扑，并选择Ryu作为本文用的SDN控制器。采用单个边缘数据中心网络场景进行仿真，网络拓扑选择k=4的Fat-tree结构，链路容量均设置为100 Mbps，SDN控制器的监督间隔设置为5 s，拥塞阈值设置为链路容量的70%。从Fat-tree拓扑中随机选择8台服务器作为发送端，并随机选择8台与发送端位于不同Pod内的服务器作为接收端。利用发送端的Iperf工具发送模拟的大流，数据流的发送速率以10 Mbps为步长，从10 Mbps增加到60 Mbps，每个Iperf发送模拟数据流的持续时间为60 s，同时利用相同发送端的Ping命令发送模拟的小流。本文根据Iperf生成的测试报告计算平均吞吐量和平均丢包率，平均吞吐量定义为单位时间内所有接收端接收到的平均数据，平均丢包率定义为单位时间内丢失数据包数量占总发送数据包的比例。根据Ping命令生成的测试报告计算小流的平均时延，其定义为所有发送端的数据包传输到接收端所用的平均时间。

3.3   仿真结果及分析

为了保证仿真结果的可信度，本文在不同流发送速率下进行20次仿真，并对这20次仿真数据计算平均值从而得到最终的仿真结果（见图 8—图 10）。在本文的仿真工作中，主要对比了3种算法：本文提出的基于路径关键度的重路由算法（RPC）、等价多路径（Equal-Cost Multi-Path，ECMP）算法和全局首次适应（Global Fit First，GFF）算法^[12]。

图  8  平均吞吐量对比结果

Figure  8.  Comparison results of the average throughput

下载: 全尺寸图片 幻灯片

图  9  平均丢包率对比结果

Figure  9.  Comparison results of the average packet loss rate

下载: 全尺寸图片 幻灯片

图  10  小流平均时延比对结果

Figure  10.  Comparison results of the average delay of little flows

下载: 全尺寸图片 幻灯片

从图 8可以看出，当流发送速率在10~20 Mbps时，3种算法的平均吞吐量近似等于流的发送速率。这是因为此时流的发送速率较小，网络完全可以容纳这些数据流。当流发送速率大于30 Mbps时，ECMP算法的平均吞吐量增加缓慢，并趋于稳定，而其余2种算法的平均吞吐量均有不同程度的增加。当流发送速率为60 Mbps时，相比与ECMP算法和GFF算法，RPC算法的平均吞吐量分别增加了37.1%和17.3%。这是因为ECMP算法在计算路径时不考虑网络当前负载信息，其基于哈希算法有可能将多条大流路由到同一条链路上导致网络出现拥塞，同时ECMP算法不会处理链路拥塞，所以ECMP算法的平均吞吐量最低。而GFF算法贪婪地选择可以容纳大流的新路径，可能导致新路径出现拥塞，本文提出的RPC算法，在为流选择新的路径时综合考虑了链路负载和链路时延，不仅可以缓解已经发生的拥塞，还可以避免新路径的拥塞，所以RPC算法的平均吞吐量最高。

从图 9中可以观察到，当流发送速率在10~20 Mbps时，网络负载较小，3种算法的平均丢包率近似等于0。当流发送速率大于20 Mbps时，ECMP算法和GFF算法的平均丢包率增长速度明显大于RPC算法。当流发送速率为60 Mbps，相比于ECMP算法和GFF算法，RPC算法的平均丢包率分别减小了55.1%和47.7%。这是因为随着流发送速率不断增大，网络中出现了不同程度的拥塞，使得3种算法均出现丢包现象。但是相比于ECMP算法和GFF算法，本文提出的RPC算法能够有效地减小网络拥塞，因此RPC算法的平均丢包率最低。

本文通过统计小流的时延来比较3种算法在减小网络拥塞方面的性能。从图 10可以看出，当流发送速率在10~20 Mbps时，3种算法的平均时延近似为0。当发送速率大于30 Mbps时，ECMP算法和GFF算法的平均时延增长速率明显快于RPC算法。当流发送速率为60 Mbps时，相比于ECMP算法和GFF算法，RPC算法的平均时延分别减小了92.7%和90.2%。这是由于随着流传输速率的增加，网络中出现不同程度的拥塞，而ECMP算法缓解拥塞能力弱，导致小流平均传输时延较高。此外，GFF算法主要考虑链路利用率作为选择新路径的标准，而本文所提的RPC算法综合考虑了链路负载和链路时延，因此在数据流传输过程中，可以有效减小网络拥塞，进而减小小流的时延。

4.   结语

针对数据中心网络极易出现的拥塞问题，本文提出了一种基于路径关键度的拥塞避免重路由方法。首先设计了链路关键度指标，用来表征大流对链路的影响程度，然后以最小化最大链路关键度为优化目标，对重路由路径分配问题进行建模，提出一种基于路径关键度的重路由算法，将大流调度到关键度较低的路径上，实现减小大流拥塞，避免小流超时的目标。最后通过仿真验证了本文所提的算法可以有效缓解链路拥塞，保障数据中心网络的性能。