张莉敏 王 辉 李沛谕 李哲青

1(河南科技大学信息工程学院 河南 洛阳 471023)2(河南科技大学网络信息中心 河南 洛阳 471023)

基于多路由配置的数据中心网络故障恢复研究

张莉敏1王 辉2李沛谕2李哲青2

1(河南科技大学信息工程学院 河南 洛阳 471023)2(河南科技大学网络信息中心 河南 洛阳 471023)

针对数据中心网路故障恢复问题，提出一种使用多路由备份配置MRC(Multiple Routing Configuration)的IP快速恢复算法。通过研究MRC主动恢复过程对数据中心网络中链路负载分布的影响以及网络链路利用率的分布，在最短路径算法中引入自适应权重分布模型。该模型能有效地分离高负载链路的数据流量到其他可用链路，减少网络拥塞。实验结果表明，对比传统的MRC算法，改进后的算法(Modified MRC)能够通过有效降低最大链路利用率来实现更均衡的网络流量负载分布。

数据中心网络 故障恢复 IP快速恢复 链路利用率 负载均衡

0 引 言

数据中心网络是应用于数据中心内的网络，因为数据中心内的流量呈现出典型的交换数据集中、东西流量增多等特征[1]，对数据中心网络提出了进一步的要求：高扩展性、高健壮性[2]、灵活的拓扑[3]和链路容量控制、绿色节能[4]等。数据集中意味着风险集中、响应集中、复杂度集中，数据中心出现故障的情况几乎不可避免[5]。因此，数据中心解决方案应着重关注如何尽量减小数据中心出现故障后对网络中关键业务造成的影响。

数据中心的故障类型较多，但故障所导致的结果基本相同,即数据中心中的设备、链路或服务器发生故障，无法对外提供正常服务。缓解这些问题最简单的方式就是冗余设计，即通过对设备、链路、服务器提供备份，从而将故障对用户业务的影响降低到最小。但是，冗余性在带来好处的同时也会带来如下一些缺点：网络复杂度增加，网络支撑负担加重，配置和管理难度增加。为了适度降低冗余，提高数据中心设备的使用效率，应当及时对网络进行故障检测、诊断和恢复。

如果某个数据中心网络发生故障，它将具有两个明显特征：第一，大量的节点可能同时不可用；第二，数据中心区域内，故障节点造成比较差的连通性。由于数据中心网络的分布特点，使用OSPF算法达到最小的收敛时间是非常困难的。但存在路径替代方法—IP快速恢复机制，即当路由器检测到故障时，不立即通知其他路由器，而是计算备份路径进行故障恢复，可以大大减小收敛时间[6-8]。作为从单一的网络组件(链路或节点)故障快速恢复的多路由配置方法(MRC)[9]也已经被提出。

MRC算法的主要思想是基于网络的原始拓扑生成一组备份拓扑，每个备份拓扑中均包含原始拓扑的所有节点和链路。通过配置不同备份拓扑中的链路权重，使得每个备份拓扑中的某些节点的邻接链路因权重值过大而不被选作恢复路径上的链路，从而使得恢复路径不经过故障设备。

对于MRC算法的改进，文献[10]通过创建生成树来减少备份拓扑数；文献[11,12]通过增加重路由时的可用链路数，减少恢复路径跳数。然而，在备份拓扑创建中，所有链路权重都被提前赋为固定值，这使得在发生单一组件故障时，替换路径的某条链路负载过高，导致网络拥塞。对此，本文采用启发式算法来自动分配备份拓扑中的链路权重，尽可能使用链路利用率小的链路进行重路由，并且结合链路费用目标函数来实现较好的负载分布。

1 MRC应用于数据中心故障恢复

在本小节，主要介绍了MRC算法在数据中心网络故障恢复中的应用。网络拓扑结构如图1所示，假设每个节点代表一个数据中心网络，MRC恢复方案将保证每一个节点和链路至少在一个备份配置中孤立一次。因此，MRC保护任何区域中的一个数据中心故障不会造成整个网络服务中断。

图1显示的是一个原始网络拓扑结构和由MRC算法产生的2个备份拓扑结构。每一个备份拓扑包含两类节点(正常节点和孤立节点)和三种链路(正常链路、受限链路和孤立链路)。为了能从单个的链路故障或节点故障中恢复，备份拓扑集应满足以下特征：

(1) 每个备份拓扑不改变原始的网络拓扑结构，并且都必须包含一个主干网，即从备份配置中移除所有孤立的节点、链路和受限链路后，剩余的节点相互连通。备份拓扑中每一个孤立节点可以通过至少一个受限链路连接到主干网。

(2) 孤立节点只与孤立链路和受限链路相连，并且至少连接一个受限链路。在同一个备份拓扑中，受限链路的两端不能同为孤立节点。

(3) 每一条链路和每一个节点都必须至少在一个备份配置中被孤立。

图1 原始拓扑图和备份拓扑图

在MRC算法中，数据包转发最多使用两个路由表，即正常路由表和备份路由表。备份路由表是通过计算备份配置中任意节点对之间的最短路径得到，其中孤立链路被设置无穷大权重值，所以不被用来转发数据包；受限链路被设置足够大的权重值，在最短路径中仅作为第一跳和最后一跳使用。在数据包转发的过程中，需要在数据包头部写入当前所使用的路由表标记号，确保节点在转发数据包时所使用的路由表与数据包头部标记的路由表相同。正常路由表标记为0，备份路由表标记为i(i>0)。如果节点u收到目的节点为d的数据包，下一跳节点和链路分别为v和u-v，则具体的数据包转发过程如下：

(1) 如果链路u-v未发生故障，则转发数据包到v，否则执行(2)。

(2) 如果路由表标记大于0(数据包之前已被重路由)，则丢弃该数据包，否则执行(3)。

(3) 分别执行以下两步：

① 如果节点v和目的节点d不同，则选择备份配置中节点v被孤立的备份路由表。

② 如果节点v和目的节点d相同，并且链路u-v和节点v在同一个备份配置中被孤立，则选择与此相应的备份路由表；如果链路u-v和节点v不在同一个备份配置中被孤立，则选择备份配置中链路u-v被孤立的备份路由表。

(4) 在数据包头部写入所选择的备份路由表标记，根据路由表转发数据包。

2 MRC对故障后链路负载分布的影响

网络中的某一链路或节点发生故障后，数据包转移到替换路径可能导致丢包和网络拥塞。为降低MRC恢复过程对故障后链路负载分布的影响，首先提出使用手动链路权重分布方法。

实验使用NS2仿真软件测试MRC恢复过程对链路负载分布的影响。拓扑模型如图1所示，假设节点7发生故障，节点1将选用备份配置BC2继续进行转发到目的节点5，这将导致备份配置中的一些链路发生拥塞。为了减少拥塞链路的负载，使用手动权重分布来实现较好的负载的分布，即根据当前链路负载分布情况，增加或减小链路权重。图2显示了这种方法对链路1-5和链路8-2的负载分布的影响。由图可知，随着时间的增加，链路1-5的负载明显增大，使用手动修改链路权重后，链路利用率明显减小。

图2 链路1-5和链路8-2的利用率

但是使用手动链路权重分布的缺点是网络中的其他一些链路有较高的链路利用率，图3所示，显示了链路1-8和链路2-3在使用手动权重分布后的链路利用率分布情况。随着时间的增加，链路1-8的负载也不断增大。

图3 链路1-8和链路2-3的利用率

由此可以得出，使用手动链路权重分布技术来实现较好的负载分布有以下几个优点：

(1) 简单，不需要复杂的算法。

(2) 在小型网络中比较容易实现。

(3) 可以对选择的某些链路实现好的负载分布。

这个方法的缺点如下所示：

(1) 手动修改在大型网络中很难实施。

(2) 不能同时对网络中的所有链路实现全局的负载分布。

3 改进的MRC算法的负载均衡模型

由第2部分可知，链路权重手动分布技术不能实现故障后所有链路都有较好的负载分布。并且，手动方法限制了网络拓扑的规模和流量需求矩阵的规模。改进的方法是在备份拓扑中使用自适应权重分布。假定流量矩阵已知，根据当前网络模型和流量矩阵，提出负载均衡机制，建立网络中所有路径间均衡分布流量的优化模型，降低网络拥塞程度。

3.1 网络模型

用有向图G(V，E)表示网络拓扑，其中V表示网络中路由器的集合，E表示链路集合。数据包从源点s到目的节点d的路径P由链路(l1,l2,…,ln)组成。c(a)表示链路a可承受量的最大流量带宽，流量矩阵D给出每个OD(Origin-Destination)对(s,d)间要求传输的流量请求。通信负载为l(a)，表示经过链路a的总的数据流量，链路的利用率为u(a)=l(a)/c(a)。流量目标函数即对于任意的a∈E，u(a)<1成立。

3.2 负载均衡机制

采用文献[13]中定义的描述链路费用的函数，建立负载均衡机制，优化的目标是最小化所有链路的费用函数Φ，如式(1)所示：

Φ=∑a∈Eφ(l(a))

(1)

(2)

其中，φ(l(a))表示链路利用率函数，由式(2)可知，该函数呈线性递增趋势。随着链路利用率的增加，函数值也不断增加，而且增加的速度不断加快。若链路利用率较高，则对该链路赋予较大的花费函数值，为实现优化目标则会降低该链路的通信负载。由于任意节点对之间的网络流量是根据最短路径算法计算得到的，而最短路径算法又与链路权值相关，所以需计算出一组经过优化的权值w，将其合理地分配给每条链路以满足特定的目标函数∑a∈Eφ(l(a))，并使所有链路的费用之和最小。

对于MRC，所有的流量是在无故障时根据备份配置BC0进行路由。当出现单故障时，所有的重路由流量根据相应的备份配置进行重路由。这个逻辑上的分离对重分布数据流量到可用链路有很大的灵活性。为优化备份配置权重w，采取启发式方法。首先w(a)=wmax/2,a∈E，每条链路a给出一个费用函数φ(l(a))，总的网络的费用函数∑a∈Eφ(l(a))是所有链路费用的总和。通过改变w(a)值，计算φ(l(a))值，新的链路权重从{1,2,…,wmax}选择(wmax=5 000)，通过多次试探来寻求最小化目标函数值的权值设置。为简化分析，假设每条链路的容量相同，而链路权值设置为如式(3)所示。

w(a)=k×l(a)+d

(3)

其中k和d为常数，d∈[0,100]，w(a)≤wmax。当权值在{1,2,…,wmax/2}范围内，若经过多次迭代循环(每个备份配置进行至少10次迭代)，目标函数值没有明显的改善，将转到{wmax/2,…,wmax}范围内继续进行试探。为避免陷入查找最小值的无限循环，在设定的迭代次数内，若更改一部分链路权值，目标函数值没有明显的改善，则终止迭代，将此时的链路权值作为最优权值。

4 实验仿真

网络中流量分布是不均匀的，在某些链路发生拥塞的同时，另一部分链路可能正处于空闲状态，因此需要对某些流量选择新路由。为了减少网络拥塞的发生，提高网络利用率，应使网络中的流量越均衡越好。本节使用第3部分提出的自动权重分布模型，并且根据链路权重分布数据流量来实现链路负载均衡。实验结果比较ModifiedMRC和MRC两种情况下的链路的利用率。

拓扑模型如图1所示，假设数据包同时从源节点发送，源节点及目的节点不可能发生故障。为计算方便，假设所有链路的容量为1。图4(a)所示为单条链路故障后两种算法下的网络花费φ(l(a))值。由于流量需求矩阵规模限制，无故障状态下φ(l(a))的值为1.36，最大链路利用率为65%。图4(b)所示为相同单链路故障后，自动权重分布对网络中链路负载分布的影响。由图4(b)可知，MRC方法中54%的链路的利用率在40%～70%，但是ModifiedMRC方法中70%的链路的利用率在30%～60%，并且25%的高利用率链路从70%～92%降低到70%～78%。

图4 单链路故障时Cost φ(l(a))和各条链路平均利用率

为了更加形象地表示改进后的算法对链路负载分布的影响，采用表1所示的单链路故障后链路利用率的方差进行分析。由表1可知，使用ModifiedMRC算法后，相比MRC算法，链路利用率的方差比较小，即所有链路负载在某一范围内波动比较小。该算法尽可能利用利用率低的链路进行数据包的传输，如表1中低利用率的链路3、链路8和链路15，在使用改进算法后，利用率稳定在45%左右，转移了高利用率链路负载，实现较好的负载分布。

表1 单链路故障后的链路利用率 %

如果中间节点1发生故障，与其相连的链路也不可用来转发数据包。图5表示的是节点1故障后，Modified MRC算法对链路负载分布的影响。由图可知，其中，80%的链路的利用率低于70%，而MRC方法仅有70%的链路的利用率低于70%，并且30%的高利用率链路从90%～96%降低到70%～81%。

图5 单节点故障时各条链路的平均利用率

表2表示的是单节点故障后链路利用率的方差分析。由表2可知，相比MRC算法，使用Modified MRC算法后链路利用率的方差比较小。并且低利用率的链路4、链路11和链路15在使用Modified MRC算法后，链路利用率稳定在50%左右，转移了高利用率链路负载，实现较好的负载分布。

表2 单节点故障后的链路利用率 %

5 结 语

文中提出使用多路由配置的IP快速恢复机制用于数据中心故障恢复，并且考虑了故障后链路的负载分布情况。讨论了MRC恢复过程对网路链路负载分布的影响。首先使用手动权重分布的方法来最小化MRC重路由过程对链路负载分布的影响，同时说明了这种方法的优点和缺点。最后提出使用Modified MRC算法，即在最短路径算法中使用不均等权重分布，并且根据链路权重分布数据流量，以链路花费函数和链路利用率作为评价指标，寻找最优权重值，以实现较好的负载分布。

配置的创建和链路权重的优化是两个相互独立的过程，未来的研究工作是希望将这两个过程统一起来得到更好的结果。并且可以在无故障状态下使用多平行网络配置，通过使用替换配置从超载链路转移数据流量达到动态负载均衡。

[1] 邓罡,龚正虎,王宏,等.现代数据中心网络特征研究[J].计算机研究与发展,2014,51(2):395-407.

[2] 朱桂明,谢向辉,郭得科,等.一种高吞吐量、高可扩展数据中心网络结构[J].软件学报,2014(6):1339-1351.

[3] 李丹,陈贵海,任丰原,等.数据中心网络的研究进展与趋势[J].计算机学报,2014,37(2):259-274.

[4] 董仕,李瑞轩,李晓林,等.基于软件定义数据中心网络的节能路由算法[J].计算机研究与发展,2015(4):806-812.

[5]HabibM,TornatoreM,DeLeenheerM,etal.Adisaster-resilientmulti-contentopticaldatacenternetworkarchitecture[C]//Proceedingofthe13thInternationalConferenceonTransparentOpticalNetwork,ICTON,Stockholm,Sweden,2011:26-30.

[6] 陈荣庆.IP网络中故障快速恢复技术的研究[D].杭州电子科技大学,2012.

[7] 陈荣庆,黄艳红.一种改进的IP网络多故障快速恢复算法[J].微型机与应用,2013,32(14):53-55.

[8]ShandM,BryantS.IPFastRerouteFramework[J].IETFRFC5714,2010,4(4):206-207.

[9]KvalbeinA,HansenAF,IcT,etal.MultipleroutingconfigurationsforfastIPnetworkrecovery[J].IEEE/ACMTransactionsonNetworking,2009,17(2):473-486.

[10]KamamuraS,MiyamuraT,PelsserC,etal.ScalableBackupConfigurationsCreationforIPFastReroute[C]//Proceedingsofthe2009 7thInternationalWorkshopontheDesignofReliableCommunicationNetworks,2009:312-318.

[11]DaikiImahama,YukinobuFukushima,TokumiYokohira.ARerouteMethodUsingMultipleRoutingConfigurationsforFastIPNetworkRecovery[C]//APCC2013:439-444.

[12]HaradaY,HuiW,FukushimaY,etal.Areroutemethodtorecoverfastfromnetworkfailure[C]//InternationalConferenceonICTConvergence,2014:903-908.

[13]FortzB,ThorupM.InternettrafficengineeringbyoptimizingOSPFweights[C]//ProceedingsINFOCOM,2000:519-528.

RESEARCH ON FAULT RECOVERY OF DATACENTER NETWORK BASED ONMULTIPLE ROUTING CONFIGURATIONS

Zhang Limin1Wang Hui2Li Peiyu2Li Zheqing2

1(CollegeofInformationEngineering,HenanUniversityofScienceandTechnology,Luoyang471023,Henan,China)2(NetworkInformationCenter,HenanUniversityofScienceandTechnology,Luoyang471023,Henan,China)

Aiming at the fault recovery of datacenter network, this paper proposes a IP fast reroute recovery algorithm using multiple routing configurations(MRC). By studying the impact of MRC recovery process on the load distribution over datacenter network links and the distribution of link utilization, we introduce an adaptive weight load balance model in the shortest path algorithm. This model can effectively split the traffic on high load links to other links, in order to reduce network congestion. Experimental results show that compared with traditional MRC algorithm, the modified algorithm achieves more balanced load distribution of network traffic by reducing the maximum link utilization.

Datacenter network Fault recovery IP fast reroute recovery Link utilization Load balance

2015-12-30。河南省重点攻关项目(132102210246)；河南省教育厅自然科学研究项目(14A510015)；河南省教育厅科技攻关项目(13B510001)。张莉敏，硕士生，主研领域：网络性能改善。王辉，教授。李沛谕，助教。李哲青，讲师。

TP393.02

A

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