張莉敏 王 輝 李沛諭 李哲青

1(河南科技大學信息工程學院 河南 洛陽 471023)2(河南科技大學網絡信息中心 河南 洛陽 471023)

基于多路由配置的數(shù)據(jù)中心網絡故障恢復研究

張莉敏1王 輝2李沛諭2李哲青2

1(河南科技大學信息工程學院 河南 洛陽 471023)2(河南科技大學網絡信息中心 河南 洛陽 471023)

針對數(shù)據(jù)中心網路故障恢復問題，提出一種使用多路由備份配置MRC(Multiple Routing Configuration)的IP快速恢復算法。通過研究MRC主動恢復過程對數(shù)據(jù)中心網絡中鏈路負載分布的影響以及網絡鏈路利用率的分布，在最短路徑算法中引入自適應權重分布模型。該模型能有效地分離高負載鏈路的數(shù)據(jù)流量到其他可用鏈路，減少網絡擁塞。實驗結果表明，對比傳統(tǒng)的MRC算法，改進后的算法(Modified MRC)能夠通過有效降低最大鏈路利用率來實現(xiàn)更均衡的網絡流量負載分布。

數(shù)據(jù)中心網絡 故障恢復 IP快速恢復 鏈路利用率 負載均衡

0 引 言

數(shù)據(jù)中心網絡是應用于數(shù)據(jù)中心內的網絡，因為數(shù)據(jù)中心內的流量呈現(xiàn)出典型的交換數(shù)據(jù)集中、東西流量增多等特征[1]，對數(shù)據(jù)中心網絡提出了進一步的要求：高擴展性、高健壯性[2]、靈活的拓撲[3]和鏈路容量控制、綠色節(jié)能[4]等。數(shù)據(jù)集中意味著風險集中、響應集中、復雜度集中，數(shù)據(jù)中心出現(xiàn)故障的情況幾乎不可避免[5]。因此，數(shù)據(jù)中心解決方案應著重關注如何盡量減小數(shù)據(jù)中心出現(xiàn)故障后對網絡中關鍵業(yè)務造成的影響。

數(shù)據(jù)中心的故障類型較多，但故障所導致的結果基本相同,即數(shù)據(jù)中心中的設備、鏈路或服務器發(fā)生故障，無法對外提供正常服務。緩解這些問題最簡單的方式就是冗余設計，即通過對設備、鏈路、服務器提供備份，從而將故障對用戶業(yè)務的影響降低到最小。但是，冗余性在帶來好處的同時也會帶來如下一些缺點：網絡復雜度增加，網絡支撐負擔加重，配置和管理難度增加。為了適度降低冗余，提高數(shù)據(jù)中心設備的使用效率，應當及時對網絡進行故障檢測、診斷和恢復。

如果某個數(shù)據(jù)中心網絡發(fā)生故障，它將具有兩個明顯特征：第一，大量的節(jié)點可能同時不可用；第二，數(shù)據(jù)中心區(qū)域內，故障節(jié)點造成比較差的連通性。由于數(shù)據(jù)中心網絡的分布特點，使用OSPF算法達到最小的收斂時間是非常困難的。但存在路徑替代方法—IP快速恢復機制，即當路由器檢測到故障時，不立即通知其他路由器，而是計算備份路徑進行故障恢復，可以大大減小收斂時間[6-8]。作為從單一的網絡組件(鏈路或節(jié)點)故障快速恢復的多路由配置方法(MRC)[9]也已經被提出。

MRC算法的主要思想是基于網絡的原始拓撲生成一組備份拓撲，每個備份拓撲中均包含原始拓撲的所有節(jié)點和鏈路。通過配置不同備份拓撲中的鏈路權重，使得每個備份拓撲中的某些節(jié)點的鄰接鏈路因權重值過大而不被選作恢復路徑上的鏈路，從而使得恢復路徑不經過故障設備。

對于MRC算法的改進，文獻[10]通過創(chuàng)建生成樹來減少備份拓撲數(shù)；文獻[11,12]通過增加重路由時的可用鏈路數(shù)，減少恢復路徑跳數(shù)。然而，在備份拓撲創(chuàng)建中，所有鏈路權重都被提前賦為固定值，這使得在發(fā)生單一組件故障時，替換路徑的某條鏈路負載過高，導致網絡擁塞。對此，本文采用啟發(fā)式算法來自動分配備份拓撲中的鏈路權重，盡可能使用鏈路利用率小的鏈路進行重路由，并且結合鏈路費用目標函數(shù)來實現(xiàn)較好的負載分布。

1 MRC應用于數(shù)據(jù)中心故障恢復

在本小節(jié)，主要介紹了MRC算法在數(shù)據(jù)中心網絡故障恢復中的應用。網絡拓撲結構如圖1所示，假設每個節(jié)點代表一個數(shù)據(jù)中心網絡，MRC恢復方案將保證每一個節(jié)點和鏈路至少在一個備份配置中孤立一次。因此，MRC保護任何區(qū)域中的一個數(shù)據(jù)中心故障不會造成整個網絡服務中斷。

圖1顯示的是一個原始網絡拓撲結構和由MRC算法產生的2個備份拓撲結構。每一個備份拓撲包含兩類節(jié)點(正常節(jié)點和孤立節(jié)點)和三種鏈路(正常鏈路、受限鏈路和孤立鏈路)。為了能從單個的鏈路故障或節(jié)點故障中恢復，備份拓撲集應滿足以下特征：

(1) 每個備份拓撲不改變原始的網絡拓撲結構，并且都必須包含一個主干網，即從備份配置中移除所有孤立的節(jié)點、鏈路和受限鏈路后，剩余的節(jié)點相互連通。備份拓撲中每一個孤立節(jié)點可以通過至少一個受限鏈路連接到主干網。

(2) 孤立節(jié)點只與孤立鏈路和受限鏈路相連，并且至少連接一個受限鏈路。在同一個備份拓撲中，受限鏈路的兩端不能同為孤立節(jié)點。

(3) 每一條鏈路和每一個節(jié)點都必須至少在一個備份配置中被孤立。

圖1 原始拓撲圖和備份拓撲圖

在MRC算法中，數(shù)據(jù)包轉發(fā)最多使用兩個路由表，即正常路由表和備份路由表。備份路由表是通過計算備份配置中任意節(jié)點對之間的最短路徑得到，其中孤立鏈路被設置無窮大權重值，所以不被用來轉發(fā)數(shù)據(jù)包；受限鏈路被設置足夠大的權重值，在最短路徑中僅作為第一跳和最后一跳使用。在數(shù)據(jù)包轉發(fā)的過程中，需要在數(shù)據(jù)包頭部寫入當前所使用的路由表標記號，確保節(jié)點在轉發(fā)數(shù)據(jù)包時所使用的路由表與數(shù)據(jù)包頭部標記的路由表相同。正常路由表標記為0，備份路由表標記為i(i>0)。如果節(jié)點u收到目的節(jié)點為d的數(shù)據(jù)包，下一跳節(jié)點和鏈路分別為v和u-v，則具體的數(shù)據(jù)包轉發(fā)過程如下：

(1) 如果鏈路u-v未發(fā)生故障，則轉發(fā)數(shù)據(jù)包到v，否則執(zhí)行(2)。

(2) 如果路由表標記大于0(數(shù)據(jù)包之前已被重路由)，則丟棄該數(shù)據(jù)包，否則執(zhí)行(3)。

(3) 分別執(zhí)行以下兩步：

① 如果節(jié)點v和目的節(jié)點d不同，則選擇備份配置中節(jié)點v被孤立的備份路由表。

② 如果節(jié)點v和目的節(jié)點d相同，并且鏈路u-v和節(jié)點v在同一個備份配置中被孤立，則選擇與此相應的備份路由表；如果鏈路u-v和節(jié)點v不在同一個備份配置中被孤立，則選擇備份配置中鏈路u-v被孤立的備份路由表。

(4) 在數(shù)據(jù)包頭部寫入所選擇的備份路由表標記，根據(jù)路由表轉發(fā)數(shù)據(jù)包。

2 MRC對故障后鏈路負載分布的影響

網絡中的某一鏈路或節(jié)點發(fā)生故障后，數(shù)據(jù)包轉移到替換路徑可能導致丟包和網絡擁塞。為降低MRC恢復過程對故障后鏈路負載分布的影響，首先提出使用手動鏈路權重分布方法。

實驗使用NS2仿真軟件測試MRC恢復過程對鏈路負載分布的影響。拓撲模型如圖1所示，假設節(jié)點7發(fā)生故障，節(jié)點1將選用備份配置BC2繼續(xù)進行轉發(fā)到目的節(jié)點5，這將導致備份配置中的一些鏈路發(fā)生擁塞。為了減少擁塞鏈路的負載，使用手動權重分布來實現(xiàn)較好的負載的分布，即根據(jù)當前鏈路負載分布情況，增加或減小鏈路權重。圖2顯示了這種方法對鏈路1-5和鏈路8-2的負載分布的影響。由圖可知，隨著時間的增加，鏈路1-5的負載明顯增大，使用手動修改鏈路權重后，鏈路利用率明顯減小。

圖2 鏈路1-5和鏈路8-2的利用率

但是使用手動鏈路權重分布的缺點是網絡中的其他一些鏈路有較高的鏈路利用率，圖3所示，顯示了鏈路1-8和鏈路2-3在使用手動權重分布后的鏈路利用率分布情況。隨著時間的增加，鏈路1-8的負載也不斷增大。

圖3 鏈路1-8和鏈路2-3的利用率

由此可以得出，使用手動鏈路權重分布技術來實現(xiàn)較好的負載分布有以下幾個優(yōu)點：

(1) 簡單，不需要復雜的算法。

(2) 在小型網絡中比較容易實現(xiàn)。

(3) 可以對選擇的某些鏈路實現(xiàn)好的負載分布。

這個方法的缺點如下所示：

(1) 手動修改在大型網絡中很難實施。

(2) 不能同時對網絡中的所有鏈路實現(xiàn)全局的負載分布。

3 改進的MRC算法的負載均衡模型

由第2部分可知，鏈路權重手動分布技術不能實現(xiàn)故障后所有鏈路都有較好的負載分布。并且，手動方法限制了網絡拓撲的規(guī)模和流量需求矩陣的規(guī)模。改進的方法是在備份拓撲中使用自適應權重分布。假定流量矩陣已知，根據(jù)當前網絡模型和流量矩陣，提出負載均衡機制，建立網絡中所有路徑間均衡分布流量的優(yōu)化模型，降低網絡擁塞程度。

3.1 網絡模型

用有向圖G(V，E)表示網絡拓撲，其中V表示網絡中路由器的集合，E表示鏈路集合。數(shù)據(jù)包從源點s到目的節(jié)點d的路徑P由鏈路(l1,l2,…,ln)組成。c(a)表示鏈路a可承受量的最大流量帶寬，流量矩陣D給出每個OD(Origin-Destination)對(s,d)間要求傳輸?shù)牧髁空埱蟆Ｍㄐ咆撦d為l(a)，表示經過鏈路a的總的數(shù)據(jù)流量，鏈路的利用率為u(a)=l(a)/c(a)。流量目標函數(shù)即對于任意的a∈E，u(a)<1成立。

3.2 負載均衡機制

采用文獻[13]中定義的描述鏈路費用的函數(shù)，建立負載均衡機制，優(yōu)化的目標是最小化所有鏈路的費用函數(shù)Φ，如式(1)所示：

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

(1)

(2)

其中，φ(l(a))表示鏈路利用率函數(shù)，由式(2)可知，該函數(shù)呈線性遞增趨勢。隨著鏈路利用率的增加，函數(shù)值也不斷增加，而且增加的速度不斷加快。若鏈路利用率較高，則對該鏈路賦予較大的花費函數(shù)值，為實現(xiàn)優(yōu)化目標則會降低該鏈路的通信負載。由于任意節(jié)點對之間的網絡流量是根據(jù)最短路徑算法計算得到的，而最短路徑算法又與鏈路權值相關，所以需計算出一組經過優(yōu)化的權值w，將其合理地分配給每條鏈路以滿足特定的目標函數(shù)∑a∈Eφ(l(a))，并使所有鏈路的費用之和最小。

對于MRC，所有的流量是在無故障時根據(jù)備份配置BC0進行路由。當出現(xiàn)單故障時，所有的重路由流量根據(jù)相應的備份配置進行重路由。這個邏輯上的分離對重分布數(shù)據(jù)流量到可用鏈路有很大的靈活性。為優(yōu)化備份配置權重w，采取啟發(fā)式方法。首先w(a)=wmax/2,a∈E，每條鏈路a給出一個費用函數(shù)φ(l(a))，總的網絡的費用函數(shù)∑a∈Eφ(l(a))是所有鏈路費用的總和。通過改變w(a)值，計算φ(l(a))值，新的鏈路權重從{1,2,…,wmax}選擇(wmax=5 000)，通過多次試探來尋求最小化目標函數(shù)值的權值設置。為簡化分析，假設每條鏈路的容量相同，而鏈路權值設置為如式(3)所示。

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

(3)

其中k和d為常數(shù)，d∈[0,100]，w(a)≤wmax。當權值在{1,2,…,wmax/2}范圍內，若經過多次迭代循環(huán)(每個備份配置進行至少10次迭代)，目標函數(shù)值沒有明顯的改善，將轉到{wmax/2,…,wmax}范圍內繼續(xù)進行試探。為避免陷入查找最小值的無限循環(huán)，在設定的迭代次數(shù)內，若更改一部分鏈路權值，目標函數(shù)值沒有明顯的改善，則終止迭代，將此時的鏈路權值作為最優(yōu)權值。

4 實驗仿真

網絡中流量分布是不均勻的，在某些鏈路發(fā)生擁塞的同時，另一部分鏈路可能正處于空閑狀態(tài)，因此需要對某些流量選擇新路由。為了減少網絡擁塞的發(fā)生，提高網絡利用率，應使網絡中的流量越均衡越好。本節(jié)使用第3部分提出的自動權重分布模型，并且根據(jù)鏈路權重分布數(shù)據(jù)流量來實現(xiàn)鏈路負載均衡。實驗結果比較ModifiedMRC和MRC兩種情況下的鏈路的利用率。

拓撲模型如圖1所示，假設數(shù)據(jù)包同時從源節(jié)點發(fā)送，源節(jié)點及目的節(jié)點不可能發(fā)生故障。為計算方便，假設所有鏈路的容量為1。圖4(a)所示為單條鏈路故障后兩種算法下的網絡花費φ(l(a))值。由于流量需求矩陣規(guī)模限制，無故障狀態(tài)下φ(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算法，鏈路利用率的方差比較小，即所有鏈路負載在某一范圍內波動比較小。該算法盡可能利用利用率低的鏈路進行數(shù)據(jù)包的傳輸，如表1中低利用率的鏈路3、鏈路8和鏈路15，在使用改進算法后，利用率穩(wěn)定在45%左右，轉移了高利用率鏈路負載，實現(xiàn)較好的負載分布。

表1 單鏈路故障后的鏈路利用率 %

如果中間節(jié)點1發(fā)生故障，與其相連的鏈路也不可用來轉發(fā)數(shù)據(jù)包。圖5表示的是節(jié)點1故障后，Modified MRC算法對鏈路負載分布的影響。由圖可知，其中，80%的鏈路的利用率低于70%，而MRC方法僅有70%的鏈路的利用率低于70%，并且30%的高利用率鏈路從90%～96%降低到70%～81%。

圖5 單節(jié)點故障時各條鏈路的平均利用率

表2表示的是單節(jié)點故障后鏈路利用率的方差分析。由表2可知，相比MRC算法，使用Modified MRC算法后鏈路利用率的方差比較小。并且低利用率的鏈路4、鏈路11和鏈路15在使用Modified MRC算法后，鏈路利用率穩(wěn)定在50%左右，轉移了高利用率鏈路負載，實現(xiàn)較好的負載分布。

表2 單節(jié)點故障后的鏈路利用率 %

5 結 語

文中提出使用多路由配置的IP快速恢復機制用于數(shù)據(jù)中心故障恢復，并且考慮了故障后鏈路的負載分布情況。討論了MRC恢復過程對網路鏈路負載分布的影響。首先使用手動權重分布的方法來最小化MRC重路由過程對鏈路負載分布的影響，同時說明了這種方法的優(yōu)點和缺點。最后提出使用Modified MRC算法，即在最短路徑算法中使用不均等權重分布，并且根據(jù)鏈路權重分布數(shù)據(jù)流量，以鏈路花費函數(shù)和鏈路利用率作為評價指標，尋找最優(yōu)權重值，以實現(xiàn)較好的負載分布。

配置的創(chuàng)建和鏈路權重的優(yōu)化是兩個相互獨立的過程，未來的研究工作是希望將這兩個過程統(tǒng)一起來得到更好的結果。并且可以在無故障狀態(tài)下使用多平行網絡配置，通過使用替換配置從超載鏈路轉移數(shù)據(jù)流量達到動態(tài)負載均衡。

[1] 鄧罡,龔正虎,王宏,等.現(xiàn)代數(shù)據(jù)中心網絡特征研究[J].計算機研究與發(fā)展,2014,51(2):395-407.

[2] 朱桂明,謝向輝,郭得科,等.一種高吞吐量、高可擴展數(shù)據(jù)中心網絡結構[J].軟件學報,2014(6):1339-1351.

[3] 李丹,陳貴海,任豐原,等.數(shù)據(jù)中心網絡的研究進展與趨勢[J].計算機學報,2014,37(2):259-274.

[4] 董仕,李瑞軒,李曉林,等.基于軟件定義數(shù)據(jù)中心網絡的節(jié)能路由算法[J].計算機研究與發(fā)展,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