0 引言

近年来云应用的普及，使网络流量呈指数式增长，这给传统数据中心网络(Data Center Network, DCN)的承载能力带来了前所未有的挑战^[1-3]。网络流量的突发性和现有网络路由算法的不足更是加剧了DCN的链路拥塞问题。通过大规模增加网络设备资源来缓解链路拥塞问题，一方面损害了运营商利益，另一方面也增加了系统的能耗，这违背了绿色数据中心建设的要求。考虑到网络中还有很多设备由于路由算法的缺陷始终处于低负载或者空载的状态，并且随着网络时代的发展，云用户对于网络服务质量和等级提出了新的需求，所以寻找更高效的路由算法来控制和协调现有网络设备资源成为更为科学的解决方法。这就是DCN的流量工程(Traffic Engineering, TE)的目标。目前广泛使用的多协议标签交换(Multi-Protocol Label Switching, MPLS)网络具有易于部署新的路由算法的特点，这也为解决网络拥塞问题的流量工程^[4-7]实现提供了良好的基础。

针对网络流的干扰问题，贝尔实验室提出了最小干扰路由算法(Minimum Interference Routing Algorithm, MIRA)^[8]，它的主要思想是在源-目的(Origin-Destination, OD)节点间选择尽可能少的关键链路来建立流量请求分布的路径，使之对未来网络流产生的干扰最小。MIRA将进出节点信息纳入算法考虑，在一定程度上缓解了关键链路的拥塞问题；但在实现过程中，在线阶段需要利用最大流算法确定关键链路，这不但增加了算法复杂度，也不利于算法在实际网络中的部署。针对MIRA的问题，唐治果等^[9]提出了链路关键性路由算法(Link Criticality Routing Algorithm, LCRA), 它在离线阶段求解链路的关键性，在线阶段只考虑链路的实时链路剩余容量，进而综合得到链路的成本，这种方式将算法控制在线性复杂度范围内；但是LCRA只能得到一条最优路径分布流量请求，这往往不能满足数据中心网络高带宽和低延迟应用的要求，容易导致链路拥塞。多路径算法成为实现DCN流量工程必然的选择。多路径健忘路由算法(Multipath Oblivious Routing Algorithm, MORA)^[10]是在等价多路径路由算法(Equal-Cost Multi-Path, ECMP)的基础上为适应网络负载的变化而设计的，它根据OD节点间多路径的网络负载情况，按权重分布流量请求，这既克服了单路径算法在网络容量上的不足，又能够在多路径上合理分配流量；但是MORA没有考虑OD节点间多路径的交叉形成的瓶颈链路问题，使得算法应用存在一定的局限。杨华卫等^[11]提出的最小割多路径(Min-Cut Multi-Path, MCMP)路由算法是利用最大流最小割定理确定OD节点间的瓶颈链路，并根据瓶颈链路建立尽量互不相交的多路径均分流量请求，定点控制瓶颈链路的负载，从而达到均衡链路间负载的目的；但其不能根据多链路的当前差异化负载状态分配链路的流量，不能很好地均衡各链路负载，且获得最大流的过程会发生多次迭代，加重计算负担。利用软件定义网络(Software Defined Network, SDN)技术的免拥塞路由策略(Congestion-Free Routing Strategy, CFRS)^[12]通过设置全局网络控制器监视网络流量，给每个到来的包分配时间槽和制定相应的路由路径，从而达到了全局无阻塞的效果。上述算法都没有考虑到DCN拓扑结构和流量请求的带宽需求，这造成了在数据中心环境下关键链路的拥塞问题仍然存在。

针对上述DCN中关键链路的拥塞问题，本文利用新型DCN拓扑——广义超立方体网络(Generalized Hypercube, GHC)^[13]拓扑的多维正交和单维全连接的特性，结合网络流的最大流最小割理论，提出了拓扑感知地选取分布流量请求的不相交路径策略，从而能够根据OD节点选取不同的不相交路径。然后根据带宽需求和OD节点间多路径的网络负载状态，动态优化流量请求分布的多路径数和各路径流量的分配比例，从而提出了一种拓扑感知型拥塞控制(Topology-Aware Congestion Control, TACC)算法。

1 网络模型

随着DCN规模的不断扩大和高阶路由器技术的发展，多种新型拓扑在DCN中得到了广泛的应用和实现^[14-15]，其中超立方体拓扑因其丰富的链路资源和正交特性在学术研究中尤为受到青睐。GHC拓扑扩展了超立方体拓扑单维上的节点数，并采用全连接的方式互联节点，一方面保留了超立方体拓扑的原有特性，另一方面也避免了拓扑本身由于节点规模的增加而导致维度急剧升高的缺点。

从图论的角度，d维GHC拓扑可以表示为G=(V, E)，其中V代表节点集合，E代表链路集合。假设N=|V|为拓扑的节点总数，n_i为拓扑第i维的节点数目，由此可知，N可以用n_i的乘积来表示，即：

N=n_d×n_d-1×…×n₁

其中n_i≥2(i=1, 2, …, d)。根据上述定义，可以将拓扑中每一个节点用唯一的d维坐标形式表示，即：

node^j←(x_d^j, x_d-1^j, …, x₁^j)

其中：0≤x_i^j≤n_i-1, 0≤j≤N-1, 1≤i≤d。例如当n₃=3, n₂=2, n₁=4时，节点总数N=24，node⁰←(0, 0, 0), node²³←(2, 1, 3)。

集合E中任意两相邻节点仅在一个坐标方向上不同，即节点(x_d, x_d-1, …, x_i+1, x_i, x_i-1, …, x₁)与节(x_d, x_d-1, …, x_i+1, x′_i, x_i-1, …, x₁)直接相连，其中0≤x_i≤n_i-1, 1≤i≤d, x_i≠x′_i。图 1是GHC拓扑图(为显示清晰，作图时去除了一些隐藏连接线)。

结合DCN网络环境的要求，GHC拓扑还应满足以下要求：

1)拓扑中每个节点作为交换机，可连接单个或多个服务器，但在流量请求分析过程中仅作为一个数据源点；

2)拓扑中两节点之间的距离D等于节点坐标表示下不同坐标方向的数量，说明算法可以在D步完成路由过程；

3)拓扑中所有节点和链路的物理性能均一致；

4)出于对节点存储空间限制的考虑，拓扑中每个源节点只存储已经建立流量请求且满足带宽需求的不相交路径；

5)拓扑中实时链路剩余带宽存放于与之相接的节点端口缓存中，路由算法执行过程中可随时读取。

2 拓扑感知型拥塞控制算法

本文提出的TACC算法针对现有拥塞控制路由算法在拓扑结构感知和带宽需求考虑上的不足，首先，根据网络流定理，在选取分布流量请求的不相交路径间运用拓扑感知的策略；然后，结合流量请求的带宽需求和拓扑链路的剩余容量等权重因子，自适应调整路径间的流量分配比例。通过上述过程，达到缓解网络拥塞的目的。

2.1 拓扑感知地选取分布请求的不相交路径策略

从图论的角度分析，OD节点间瓶颈链路集合即为它的最小割。由网络的最大流最小割定理^[16]可知，OD节点间的链路容量必是该OD节点间多条不相交路径的容量，因此，TACC通过拓扑感知地求解不相交路径的方式来定点规划瓶颈链路的负载分布，从而达到规避网络拥塞的目的。假设在源节点s和目的节点r之间分布流量请求，OD节点间的距离为q，其中1≤q≤d，为了方便表示，令s=(x_d, x_d-1, …, x_q+1, x_q, x_q-1, …, x₁)，r=(x_d, x_d-1, …, x_q+1, x′_q, x′_q-1, …, x′₁)。根据GHC拓扑的定义可知，s和r之间流量请求分布的多路径长度为q，并且从源节点出发，流量可以向q个不同的坐标方向分布，那么可以将求解由s向r分布流量请求的多路径问题理解为q到1的全排列问题。通过邻位对换法，可以快速地得到所有多路径的全排列。根据图论的知识可知，在流量请求分布的第i步不相交路径之间不能有相同坐标方向上的变化，否则选择的不是最多路径数或者路径间存在相交链路。如式(1)是由一组不相交路径形成的矩阵。为方便表示，矩阵中只显示路由的后一节点相对于前一节点改变的坐标方向。矩阵中每一行表示一条不相交路径，从左到右是数据流的传输方向。

$ \left[ {\begin{array}{*{20}{c}} {{d_1}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_2}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_{q - 1}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_q}} \\ {{d_2}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_3}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_q}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_1}} \\ { \vdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \vdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \times {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \vdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \vdots } \\ {{d_{q - 1}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_q}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_{q - 3}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_{q - 2}}} \\ {{d_q}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_1}{\kern 1pt} {\kern 1pt} {\kern 1pt} \cdots {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_{q - 2}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_{q - 1}}} \end{array}} \right] $

(1)

从式(1)中可以看出，随机排列矩阵的q列依旧可以构成不相交多路径，则根据数学知识可知，q列的全排列数是q!。结合矩阵的行代表不相交路径，且分布流量请求的过程没有对路径顺序进行要求，所以可以得到不相交路径组的数量为q!/q=(q-1)!。

2.2 确定多路径数

因为GHC拓扑的富连接特性，OD节点间可供流量请求分布的不相交路径往往较多，当带宽需求较小或者现有路径负载状态不均匀时，在全部这些路径间分配流量，容易导致分组交换网络中目的节点侧数据重组的压力，所以TACC采用设置路径自适应阈值的方式，确定分布流量请求的多路径数，从而达到了减轻目的节点侧数据重组压力的目的。设置路径自适应阈值φ来控制分布流量请求的路径数。假设OD节点间带宽需求为b，一个不相交路径矩阵中q条路径的剩余容量从大到小依次排列为c₁, c₂, …, c_q，则设置路径自适应阈值φ可按如下公式确定：

$ \varphi = 1 + \frac{{\delta \times b}}{{\sum\limits_{i = 1}^q {{c_i}} }} $

(2)

其中δ为比例因子，通常取小于1的常数。当q条路径的剩余容量和较大时，φ会变小，说明带宽资源较丰富，链路不易拥塞，适当收窄路径自适应阈值参数，可以降低目的节点侧数据重组的压力；当带宽需求b较大时，φ也较大，说明带宽需求较大，链路可能拥塞，需要适当放宽路径自适应阈值参数。

根据路径自适应阈值φ选择剩余容量较大的前p条路径作为流量请求的分配路径，由如下公式确定：

$ \sum\limits_{i = 1}^q {{c_i}} \geqslant \varphi \times b $

(3)

结合式(2)和式(3)中可以看出，选择的流量请求分布的路径数会随着带宽需求b的增加呈平方曲线上升。特殊情况下，当$ \sum\limits_{i = 1}^p {{c_i}} < \varphi \times b $时，选择全部的q条不相交路径分布流量请求来尽量均衡链路间的负载分布。

2.3 确定各路径的流量分配比例

考虑到在路径间均分链路负载无法平衡路径间已存在的负载不均衡性，所以TACC按各路径流量权重动态分布流量请求，避免均分流量无法改善现有网络不对称负载分布的问题。假设流量请求的带宽需求为b，按照上述选择的p条路径中每条路径的实时剩余容量c_i占总实时剩余容量C_m的比例为动态权重分配，则第k条路径分配的流量为rc_k，确定公式如下：

$ r{c_k} = \frac{{{c_k}}}{{{C_m}}} \times b;{C_m} = \sum\limits_{i = 1}^q {{c_i}} $

(4)

由式(4)可以看出，当路径剩余容量较大时，被分配的流量也较大，这样起到了均衡网络链路负载状态的目的。

2.4 算法步骤

算法主要步骤如下：

步骤1  根据2.1节中确定不相交路径矩阵的算法过程计算GHC拓扑中当前OD节点间流量请求的一个不相交路径矩阵，并将该不相交路径矩阵存储在源节点中。

步骤2  计算路径自适应阈值φ，根据当前请求的带宽需求和不相交多路径的剩余容量状态，通过式(3)求解分布流量请求的多路径。若满足式(3)执行步骤3，若不符合执行步骤1。

步骤3  在步骤2得到的多路径间，结合多路径的负载分布状态，通过式(4)分配各路径的流量比例。

步骤4  更新网络的链路剩余容量信息，转向步骤1接受新的流量请求。

2.5 算法性能开销分析

算法流量请求建立之后，在进行不相交路径选取过程中，需要源节点提供一定的空间来存储通过拓扑感知策略得到的路径，以便算法后续步骤对其进行判断是否满足带宽需求，这带来了存储空间的开销；但是其不需持续维护这个空间，在该流量请求结束之后，即可释放，可以循环为后续请求所使用，所以空间开销有限。另一方面，由于节点不维护路由路径，所以每次进行流量请求时都需一定的时间比较选择满足带宽需求条件的不相交路径；但是由于GHC拓扑的富连接特性和拓扑感知的选取策略，时间开销往往在线性的范围内。通过上面的分析，本文算法的空间和时间开销均可认为在实际可接受的范围内。

3 仿真实验

本文采用8×6×7=336的GHC拓扑结构在NS2网络仿真平台上进行仿真实验，设定网络中所有节点间的链路带宽均为10 Gb/s，这与数据中心网络中普遍使用的光纤容量大小适配。为了验证TACC算法均衡流量分布的性能，本文选取性能较优的单路经LCRA和多路径MORA、MCMP和CFRS进行实验比较。算法特点比较如表 1。

网络流量请求的分布问题可以建模成多商品流问题，这种问题已经被证明是NP难问题。为了衡量各种算法对网络流量请求分布的优劣程度，本文选择网络的最大链路负载、平均链路负载、接受流量请求的总带宽、分布路径数和算法部署时间作为性能指标进行对比实验。

3.1 最大链路负载和平均链路负载

本文选取2组120 min的数据中心流量数据作为实验样本a和b，a是网络低负载情况，b为网络高负载情况，采样周期为5 min，以此来验证算法在低负载和高负载情况下的最大链路负载和平均链路负载的情况。最大链路负载l_max是部署路由算法分布流量请求后链路的最大负载，是衡量网络负载分布均衡程度的重要指标；平均链路负载l_ave表示网络中所有链路负载的平均值，是衡量路由算法对网络资源消耗程度指标。假设e∈E，那么最大链路负载为l_max=max l(e)，平均链路负载可以表示为$ {l_{{\text{ave}}}} = \frac{1}{N}\sum\limits_e^E {l\left( e \right)} $。通常情况下，最大链路负载的降低是以平均链路负载的增加为代价的。由于GHC拓扑结构的特殊性，导致各种算法都是按照OD节点间不同坐标方向进行路由，所以求解的平均链路负载基本相同，本文中不再讨论。

图 2是各路由算法在低负载数据样本a情况下，网络最大链路负载分布的曲线。从图中可以看出：因为LCRA是单路径算法，流量请求只能分布在一个路径上，所以它的最大链路负载最大；其他四种算法都是采用多路径分配流量请求的方案，在负载较低的情况下，网络中链路的剩余容量相对较多，不易引起链路拥塞，所以最大链路负载相对较小，且TACC算法通过权重分配的方式能够均衡链路的已有负载，所以其最大链路负载最小。图 3是各路由算法在高负载数据样本b情况下，网络中最大链路负载分布的曲线图。与图 2比较可以看出，在高负载情况下，网络中链路的剩余容量相对较少，链路易拥塞。TACC算法通过动态权重的方式均衡网络流量，效果最佳；CFRS算法通过全局控制器监测网络的流量状态，能够规避拥塞链路，从而能够达到均衡链路负载的目的；而MORA无法自适应流量请求分布的路径数，MCMP只是均分已有流量请求，无法改善链路的已存在的不均衡状态，所以在高负载情况下这两种算法效果不佳；单路经LCRA的最大链路负载出现较大波动，且远大于其他四种算法。

3.2 接受流量请求的总带宽

接受流量请求的总带宽是指网络中所有节点接受流量请求数的总和，是表征网络吞吐量性能的重要指标。该性能指标与丢包率和路由延迟指标呈负相关关系，而这些指标都是衡量网络性能的关键因素。所以本文选取流量请求带宽从0 Tb/s到50 Tb/s变化，观察接受的流量请求总带宽在各种算法下的变化，具体曲线如图 4。

由图 4可知：本文TACC算法在流量请求分布的多路径数和各路径流量分布比例同时进行自适应优化，能明显改善网络性能，在五条曲线中表现最佳；而在负载较重时，由于MORA算法无法自适应分配流量请求的路径数，MCMP算法无法均衡链路间的负载状况，所以两者均出现了一定的性能下降；CFRS需要统一的控制器进行调度，在负载较重时，控制器无法为每一个情况选择合适的路径，且存在单点失效的风险，所以接受流量请求的总带宽也较差；单路径LCRA的网络带宽吞吐量性能最差，必然导致网络丢包率和路由延迟的增加。

3.3 流量请求分布的路径数

分布的路径数用来衡量目的节点侧数据重组的复杂程度，也是表征算法有效性的重要指标。由于LCRA是单路径算法，所以任何情况下，分布的路径数都为1(没在图 5上标注)；TOMA将流量请求分布的路径数最大限制为k，一般取可用路径数的中间值；MCMP算法分布的路径数与OD节点的位置相关，若OD节点位置(距离为q)确定，路径数也是确定的；CFRS的分布路径数受全局控制器调度，总体随着负载的增加而增加；而本文的TACC算法也会根据实时的带宽需求和当前网络的负载状态更新路径数，是自适应的过程。流量请求分布的路径数要结合最大链路负载等其他指标判断，不能单单看这一指标。假设OD节点间的距离q为3，则取k为2，当节点带宽总需求在0 Tb/s到50 Tb/s间变化时，各种算法优化下的分布流量请求的路径数曲线如图 5。

从图 5中可以看出：本文TACC算法和CFRS算法的自适应机制能够使分布路径数随着带宽需求的变化而动态变化，这比其他算法有更强的适应性，从而能均衡最大链路负载和目的节点侧数据重组的压力；其他三种算法只是固定分布的路径数，无法适应带宽需求的变化，在实际应用中存在一定的局限性。

3.4 算法部署时间

本文中的算法部署时间主要是指算法将流量请求部署到OD节点间相关路径上所需要的时间，是衡量算法在实际应用中部署难易程度的重要指标。LCRA都将算法计算量较大的部分放在离线阶段，在线阶段只需考虑剩余容量，所以部署时间最短；CFRS需要将流量请求上传给统一控制器进行规划路径，存在一定的时延，所以算法部署时间最长；本文TACC算法由于拓扑感知地选取不相交路径，相对速度较快，而MORA和MCMP算法都是在确定流量请求的分布过程进行大量计算得到路由路径，这大大增加了部署的延迟，在拓扑规模增加的情况下，导致算法部署时间急剧增加。

4 结语

本文针对DCN的链路拥塞问题，采用流量工程的思路，结合GHC拓扑的结构优势，提出了自适应拥塞控制路由算法——TACC。该算法从降低计算分配流量请求的不相交路径的复杂度与优化流量请求分布的多路径数和各路径上的流量分配比例方面着手，在均衡网络链路流量和易于部署实现方面获得了极大的提升，这也体现了拓扑感知型算法在实际应用中的优势。在此基础之上，下一步的研究方向是保证拥塞控制的前提下进一步降低数据中心网络的能耗。