伊雯雯，張書奎，王 喜，，李文俊

1. 蘇州工業(yè)職業(yè)技術(shù)學(xué)院 軟件與服務(wù)外包學(xué)院，江蘇 蘇州 215004； 2. 蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006

近年來，隨著云計算和大數(shù)據(jù)應(yīng)用的飛速發(fā)展，數(shù)據(jù)中心網(wǎng)絡(luò)(Data Center Network)作為其基礎(chǔ)設(shè)施和下一代網(wǎng)絡(luò)技術(shù)的創(chuàng)新平臺，得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[1-3]．

數(shù)據(jù)中心網(wǎng)絡(luò)的容錯性是評估網(wǎng)絡(luò)性能的重要因素．連通度是度量數(shù)據(jù)中心網(wǎng)絡(luò)容錯性的一個重要參數(shù)，連通度越大，則數(shù)據(jù)中心網(wǎng)絡(luò)的容錯性能就相對越高．?dāng)?shù)據(jù)中心網(wǎng)絡(luò)連通度定義中，發(fā)生故障的服務(wù)器是任意的、沒有限制條件的，然而實際情況往往并非如此．僅使用連通度來評估數(shù)據(jù)中心網(wǎng)絡(luò)的容錯性，會嚴(yán)重低估數(shù)據(jù)中心網(wǎng)絡(luò)的容錯性能．因此，涌現(xiàn)了大量在特定網(wǎng)絡(luò)拓?fù)渖系南拗七B通度問題的研究成果[3-12]．

傳統(tǒng)的樹型數(shù)據(jù)中心網(wǎng)絡(luò)存在可擴展性不足和容錯性較差等缺點，因此研究者們提出了DCell，BCube等多種遞歸型數(shù)據(jù)中心網(wǎng)絡(luò)，與樹型數(shù)據(jù)中心網(wǎng)絡(luò)不同，這些結(jié)構(gòu)采用遞歸方式構(gòu)建網(wǎng)絡(luò)拓?fù)洌碚撋峡梢灾С职偃f臺服務(wù)器的規(guī)模[13-14]，且它們避免了核心層交換機帶來的性能瓶頸，并使服務(wù)器之間擁有多條可用的不相交路徑，其在可擴展性、容錯性等多方面都有較好表現(xiàn)．本文提出了一類遞歸型數(shù)據(jù)中心網(wǎng)絡(luò)——RDCN，與傳統(tǒng)樹形數(shù)據(jù)中心網(wǎng)絡(luò)相比，該網(wǎng)絡(luò)具有更好的網(wǎng)絡(luò)帶寬和網(wǎng)絡(luò)容錯性能；研究了遞歸型數(shù)據(jù)中心網(wǎng)絡(luò)的限制連通度，該結(jié)果能夠更加精確地度量該網(wǎng)絡(luò)的容錯性．本文將討論RDCN在限制故障頂點集情形下的限制連通度，并設(shè)計和分析了相應(yīng)的容錯單播算法．

1 預(yù)備知識

數(shù)據(jù)中心網(wǎng)絡(luò)可以表示為一個簡單圖G=(V(G)，E(G))，其中V(G)表示頂點集，E(G)表示邊集．頂點和邊分別表示數(shù)據(jù)中心網(wǎng)絡(luò)中的服務(wù)器和連接服務(wù)器的鏈路，而交換機被認(rèn)為是透明的網(wǎng)絡(luò)設(shè)備[13]．給定圖G中任意兩個頂點u和v，若(u，v)∈E(G)，則u和v是鄰居．頂點u在圖G的鄰居集合可表示為N(G，u)={v|(u，v)∈E(G)}．圖G的連通度可表示為κ(G)．

圖G中兩個頂點u和v之間的路徑P可表示為一個頂點的序列P=(u0=u，u1，…，uk=v)，P中除了u和v以外的任意兩個點都是不同的．從ui到uj的子路徑可用Path(P，ui，uj)表示，其中0≤i

進一步，對于頂點集合V′?V(G)，定義V′的鄰居集合為Γ(G，V′)=∪x∈V′Γ(G，x)/V′．明顯地，Γ(G，V′)=N(G，V′)/V′．

定義1給定圖G，令F?V(G)表示G中一個故障頂點集合，如果u∈F，那么u是G中一個故障頂點；否則，u是G中一個無故障頂點．若G中每個頂點至少有一個無故障鄰居，則基于該條件下G的限制連通度可表示為κ′(G)．另外，基于故障頂點無限制的G的連通度可表示為κ(G)．

對于任意整數(shù)n≥3和k≥1，部署于n-口交換機上的k-維遞歸完全圖網(wǎng)絡(luò)可以表示為一個圖Xk，n．Xk，n的基圖是一個有n個頂點的完全圖，tk，n表示Xk，n的頂點個數(shù)，e(u，v)表示頂點u到頂點v的邊，σ表示圖中任意頂點與同維度其他子圖相連接的邊數(shù)，其中σ∈{1，n-1}，s表示Xk，n中子圖的個數(shù)．Xk，n的頂點u表示為[uk，uk-1，…，ui，…，u0]，其中0≤u0≤n-1，0≤ui≤si且i≥1，可用(u)i表示u中的第i個元素ui．

定義2當(dāng)k≥0，n≥3且σ∈{1，n-1}時，Xk，n的遞歸定義如下：

(1) 當(dāng)k=0時，Xk，n是一個具有n個頂點的完全圖．

根據(jù)文獻(xiàn)[13]和文獻(xiàn)[14]，可得出Xk，n網(wǎng)絡(luò)的基本性質(zhì)如下．

定理1Xk，n是一個(n+kσ-1)-正則圖．

定理2κ(Xk，n)=λ(Xk，n)=n+kσ-1．

本文將RDCN與幾種典型的數(shù)據(jù)中心網(wǎng)絡(luò)進行對比(如表1所示)，其中N表示服務(wù)器數(shù)量，n表示交換機端口數(shù)量，比較的指標(biāo)包括： 頂點的度、連通度和網(wǎng)絡(luò)直徑．其中數(shù)據(jù)中心網(wǎng)絡(luò)中頂點的度越小則表示其頂點間網(wǎng)絡(luò)連接越少，從而構(gòu)建網(wǎng)絡(luò)的成本越低；數(shù)據(jù)中心網(wǎng)絡(luò)的連通度越高，則表示其具有更好的容錯性；數(shù)據(jù)中心網(wǎng)絡(luò)的直徑越小則表示它的實時響應(yīng)路由所花費的時間越少．

表1 幾種常見數(shù)據(jù)中心網(wǎng)絡(luò)性質(zhì)比較

與RDCN相比，Tree和Fat-Tree的擴展規(guī)模在理論上受限于核心交換機的端口數(shù)目，不利于數(shù)據(jù)中心網(wǎng)絡(luò)規(guī)模的快速擴張，且它們的容錯性受到核心交換設(shè)備影響較大，對核心交換設(shè)備的故障非常敏感．同時，Tree和Fat-Tree的拓?fù)浣Y(jié)構(gòu)的特點決定了其不能很好支持一對多、廣播和全交換等網(wǎng)絡(luò)通信模式．另外，與RDCN相比，F(xiàn)iConn網(wǎng)絡(luò)的容錯性較差，網(wǎng)絡(luò)直徑較大．因此與上述數(shù)據(jù)中心網(wǎng)絡(luò)相比，RDCN具有較高的網(wǎng)絡(luò)帶寬、較好的容錯性．特別的，σ=n-1時的RDCN比σ=1時的RDCN具有更高的網(wǎng)絡(luò)帶寬和容錯性能．

2 遞歸型數(shù)據(jù)中心網(wǎng)絡(luò)的限制連通度

根據(jù)定義2，可以證明下述引理成立．

引理3[15]對于任意的整數(shù)k≥1，n≥3且σ∈{1，n-1}，Xk，n上存在長度為3的圈．

引理4[15]對于任意的整數(shù)k≥1，n≥3，σ∈{1，n-1}，Xk，n中存在相鄰的兩個頂點u=ukuk-1…u0和v=vkvk-1…v0，邊(u，v)∈E(Xk，n)，令leftIdx(u，v)表示為u和v從左側(cè)開始最先不同的下標(biāo)，則有

引理5對于任意的整數(shù)k≥1，n≥3且σ∈{1，n-1}，網(wǎng)絡(luò)中的故障頂點集合F?V(Xk，n)且|F|≤2kσ+n-3，若Xk，n中每個無故障頂點都至少存在一個無故障鄰居，則Xk，n-F是連通的．

證要證明上述情況成立需要證明下述斷言成立．

斷言．對于任意兩個不同的頂點u，v∈V(Xk，n-F)，在Xk，n-F中存在一條連接u和v的路徑．

當(dāng)k=1時，該斷言顯然成立．

令α=(u)k，β=(v)k，當(dāng)k>1時，可以分兩種情形討論．

1) 若fα≤n+kσ-3，則G0是連通的，因此G0中存在u和v的路徑連接；

2) 若fα≥n+kσ-2，且u，v在同一個連通分支，則G0中存在u和v的連接路徑；

3) 若fα≥n+kσ-2，且u，v不在同一個連通分支，假定x是u的一個無故障鄰居頂點，y是v的一個無故障鄰居頂點．令γ=(x)k且δ=(y)k，接下來可以分為以下3種子情形．

情形1.1α≠δ且α≠γ．對于任意整數(shù)i∈Ik，n{α}，有fi≤|F|-fα≤(2kσ+n-3)-(n+kσ-2)=kσ-1≤n+kσ-3．根據(jù)引理2，G1是連通的，G1中存在路徑Q連接x和y．因此Xk，n-F中存在路徑(u，x，Q，y，v)連接u和v．

令

對c′求導(dǎo)則有

顯然有min(c′)=n+2kσ-2．不失一般性，假設(shè)x1=u1，x2=u2，…，xc=uc，則有{uc+1，uc+2，…，un+kσ-3}∩{xc+1，xc+2，…，xn+kσ-3}=?．

因為|F|≤2kσ+n-3

和

根據(jù)情形1.1中討論，G1中存在一條路徑P連接z和y．因此，Xk，n-F中存在一條路徑(Q，P，v)連接u和v．

情形1.3α=δ．證明與情形1.2類似，不再贅述．

若fα=n+kσ-2則fβ≤|F|-fα≤(2kσ+n-3)-(kσ+n-2)=kσ-1≤n+kσ-3，與fα≤fβ矛盾．因此fα≤n+kσ-3．接下來，分以下兩種情形討論．

根據(jù)引理2，可得G1是連通的，故G1中存在一條路徑Q連接u和x．從而路徑(Q，P-1)是Xk，n-F中連接u和v的一條路徑．

綜上所述，對于任意的u，v∈V(Xk，n-F)且u≠v，Xk，n-F中存在一條連接u和v的路徑，因此Xk，n-F是連通的，證畢．

定理4對于任意整數(shù)k≥1，n≥3且σ∈{1，n-1}，κ′(Xk，n)=2κ(Xk，n)-n=2kσ+n-2κ′(Xk，n)=2κ(Xk，n)-n=2kσ+n-2．

證通過引理5可得κ′(Xk，n)≥2kσ+n-2κ′(Xk，n)≥2kσ+n-2．下面將證明κ′(Xk，n)≤2kσ+n-2成立．

對于任意的整數(shù)k≥1，n≥3且σ∈{1，n-1}，如果Xk，n中每個頂點都至少有一個無故障鄰居，則存在一條邊(u，v)∈E(Xk，n)，使得|Γ(Xk，n，{u，v})|=2kσ+n-2且Xk，n-Γ(Xk，n，{u，v})有且僅有兩個連通分支： 其中一個連通分支為Xk，n[{u，v}]，另外一個連通分支為Xk，n-N(Xk，n[{u，v}])．

首先證明當(dāng)n=3，k=1時該結(jié)論成立．當(dāng)n=3，k=1時，分為兩種情況：σ=1或σ=n-1．

當(dāng)n=3，k=1，σ=1時，選擇一條邊(00，01)，令故障集合為Γ(X1，3，{00，01})={02，10，20}．明顯的|Γ(X1，3，{00，01})|=3=2×1×1+3-2．容易驗證X1，3-Γ(X1，3，{00，01})有且僅有兩個連通分支： 其中一個連通分支為X1，3[{00，01}]，另外一個連通分支為X1，3-N(X1，3，{00，01})．

當(dāng)n=3，k=1，σ=n-1時，選擇一條邊(00，01)，令故障集合為Γ(X1，3，{00，01})={02，10，11，20，21}．明顯的|Γ(X1，3，{00，01})|=5=2×1×(3-1)+3-2．容易驗證X1，3-Γ(X1，3，{00，01})有且僅有兩個連通分支： 其中一個連通分支為X1，3[{00，01}]，另外一個連通分支為X1，3-N(X1，3，{00，01})．

通過上述過程知κ′(Xτ，n)≤2τσ+n-2成立．

綜上所述，當(dāng)n≥3，k≥1，σ∈{1，n-1}時，κ′(Xk，n)=2kσ+n-2，證畢．

3 遞歸型數(shù)據(jù)中心網(wǎng)絡(luò)基于限制故障集的單播算法

定理4證明了遞歸型通用網(wǎng)絡(luò)上限制連通度的精確值，本節(jié)將提出網(wǎng)絡(luò)上基于限制故障頂點集合的單播算法XFRouting．

Algorithm： XFRouting

Input： A networkXk，n，a global variableσ∈{1，n-1}，a faulty node setF?V(Xk，n) with |F|≤2kσ+n-3，and two nodesu，v∈V(Xk，n)．

Output： A path fromutov inXk，n-F．

Letσto be a global variable；

print (XFR(Xk，n，F(xiàn)，u，v))；

function XFR(Xk，n，F(xiàn)，u，v，k)

1. if (u，v)∈E(Xk，n) ork=0 then

2. return (u，v)；

3. else if |F|≥2kσ+n-2 then

4. return (BFS(Xk，n-F，u，v))；

5. else ifF=? then

6. ifσ=1 then

7. return DCellRouting (Xk，n，u，v)；

8. else ifσ=n-1

9. then return BCubeRouting (Xk，n，u，v)；

10. end if

11. end if

12. LetmFas the first index of the subsets with the minimal number of fault nodes

13. Letα←(u)k，β←(v)k；

14. ifα=βthen

16. else ifα?mFthen

17. foriinmFthen

20. break；

21. end for

22. ifV(P)∩V(Q)=? then

24. end if

25. return (P，S，Q-1)；

26. Find the 1st common nodexfromPandQ；

27. return (Path(P，u，x)，Path(Q-1，x，v))；

28. end if

29. else ifα≠βthen

30. ifα∈mFthen

32. ifu∈V(Q) then return (Path(Q，u，v))；

33. end if

35. else ifβ∈mFthen

37. ifv∈V(P) then return (Path(P，u，v))；

38. end if

40. else then

41. foriinmFthen

44. break；

45. end for

46. ifV(P)∩V(Q)=? then

48. end if

49. return (P，S，Q-1)；

50. Find the 1st nodexfromPandQ；

51. return (Path(P，u，x)，Path(Q-1，x，v))；

52. end if

53. end function

function XMapping(u，G0，G1，F(xiàn)，mF)

1. forvinN(G0-F，u) andvinmFthen return (u，v)；

2. end for

3. forvinN(G0-F，u) then

4. forxinN(G1-F，v) andvinmFthen

5. return (u，v，x)；

6. end for

7. end for

8. forvinN(G0-F，u) then

9. forxinN(G0-F，v) then

10. foryinN(G1-F，x) andyinmFthen

11. return (u，v，x，y)；

12. end for

13. end for

14. end for

18. end function

接下來，定理5將給出XFRouting算法的設(shè)計思路和執(zhí)行過程，并分析其時間復(fù)雜度．

定理5當(dāng)k≥1，n≥3且σ∈{1，n-1}時，對于任意的頂點集合F?V(Xk，n)且|F|≤2kσ+n-3，算法XFRouting可以構(gòu)造出Xk，n-F中任意兩個不同頂點間的一條無故障路徑，時間復(fù)雜度為O(k)≤O(┌l(fā)ogs|F|┐k3)．

證當(dāng)k≥1，n≥3且σ∈{1，n-1}時，故障集合F?V(Xk，n)且滿足|F|≤2kσ+n-3，XFRouting算法可以構(gòu)造出Xk，n-F中任意兩個不同頂點u到v的一條無故障路徑．XFRouting算法中包括4個函數(shù)： XFR，XMapping，DCellRouting[12]和BcubeRouting[13]．其中實現(xiàn)函數(shù)XMapping構(gòu)造出從G0中的頂點u到G1-F的一條無故障路徑，函數(shù)DCellRouting構(gòu)造出當(dāng)σ=1時Xk，n中u到v的一條路徑，函數(shù)BcubeRouting構(gòu)造出當(dāng)σ=n-1時Xk，n中u到v的一條路徑．函數(shù)XFR將構(gòu)造的路徑以一個向量的形式保存，向量中的頂點采用長度為k+1的字符串表示．

函數(shù)XFR第1-2行，如果u和v存在邊，則直接返回邊(u，v)．函數(shù)XFR第3-4行，如果條件滿足|F|≥2kσ+n-2，則采用廣度優(yōu)先算法(BFS)構(gòu)造一條無故障路徑，在最壞情形下時間復(fù)雜度為O((tk，n)2)．函數(shù)XFR第5-11行，當(dāng)無故障頂點且σ=1時函數(shù)DCellRouting構(gòu)造一條無故障路徑，時間復(fù)雜度為O(k)，當(dāng)無故障頂點且σ=n-1時調(diào)用函數(shù)BcubeRouting構(gòu)造一條無故障路徑，時間復(fù)雜度為O(k)．函數(shù)XFR第12行，計算最小故障子集，時間復(fù)雜度為O(k)．

接下來分5種情況討論函數(shù)XFR的時間復(fù)雜度，令R=n+kσ-1，mF表示故障數(shù)最小的子圖前綴，s表示子集的個數(shù)，其中當(dāng)σ=1時，s=tk-1，n+1，當(dāng)σ=n-1時，s=n．函數(shù)XFR第14-15行，當(dāng)α=β且α∈mF時，T(k)≤T(k-1)+O(R)；函數(shù)XFR第16-28行，當(dāng)α=β且α?mF時，則有T(k)≤T(k-1)+O(R3)；函數(shù)XFR第29-34行，當(dāng)α≠β且α∈mF時，則有T(k)≤T(k-1)+O(R3)；函數(shù)XFR第35-39行，當(dāng)α≠β且β∈mF時，則有T(k)≤T(k-1)+O(R3)；函數(shù)XFR第40-52行，當(dāng)α≠β，α?mF且β?mF時則有T(k)≤T(k-1)+O(R3)．

因此可得：

即O(k)≤O(logs|F|k3)，證畢．

接下來，定理6分析XFRouting算法構(gòu)造的路徑長度的最大值．

定理6當(dāng)k≥1，n≥3且σ∈{1，n-1}時，對于任意的頂點集合F?V(Xk，n)且|F|≤2kσ+n-3，XFRouting算法可以構(gòu)造出Xk，n-F中任意兩個不同頂點間的一條無故障路徑，其路徑長度的上界為

證令L(k)表示XFRouting算法構(gòu)造得到的路徑的長度．當(dāng)|F|=0時，令D(Xk，n)表示圖Xk，n的直徑，根據(jù)文獻(xiàn)[12]和文獻(xiàn)[13]，則有

當(dāng)0<|F|≤2kσ+n-3時，分為以下情形討論：

函數(shù)XFR第14-15行，L(k)=L(k-1)；函數(shù)XFR第16-28行，L(k)≤L(k-1)+6；函數(shù)XFR第29-34行，L(k)≤L(k-1)+3；函數(shù)XFR第35-39行，L(k)≤L(k-1)+3；函數(shù)XFR第40-52行，L(k)≤L(k-1)+6．

令

d=logs|F|

則有

當(dāng)σ=1時s=tk-1，n+1?|F|，則d=logs|F|<1．因此有

證畢．

綜上所述，本文提出的時間復(fù)雜度為O(logs|F|k3)的算法XFR與采用時間復(fù)雜度為O((tk，n)2)的廣度優(yōu)先搜索算法相比，具有明顯的優(yōu)越性．

4 模擬實驗及結(jié)果分析

本文提出的XFRouting算法采用Python語言編程實現(xiàn)，實驗通過設(shè)備配置為Intel(R) Core(TM) i5-4200U CPU 1.61GHz，8 GB 內(nèi)存的計算機來評估算法的性能并分析實驗結(jié)果．實驗中頂點故障和測試點都是隨機生成的．給定隨機生成的限制故障集合F?V(Xk，n)且|F|≤2kσ+n-3，給定σ=1，1≤k≤3，n=3，網(wǎng)絡(luò)最大規(guī)模為24 492個頂點，將使用XFRouting算法構(gòu)造出Xk，n-F上一條單播路徑花費的CPU時間分別與廣度優(yōu)先BFS算法和深度優(yōu)先DFS算法所得的結(jié)果進行比較．將XFRouting算法和BFS算法、DFS算法重復(fù)運行1 000次，隨機生成故障頂點集合，構(gòu)建任意兩個頂點之間的無故障路徑，最壞情況如圖1(a)所示，平均情況如圖1(b)所示．

圖1 σ=1時3種算法花費的CPU時間

給定隨機生成的限制故障集合F?V(Xk，n)且|F|≤2kσ+n-3，給定σ=n-1時，1≤k≤7，n=3，網(wǎng)絡(luò)最大規(guī)模為6 561個頂點．將XFRouting算法構(gòu)造出Xk，n-F上一條單播路徑花費的CPU時間分別與BFS算法、DFS算法進行比較．將XFRouting算法、BFS算法和DFS算法重復(fù)運行1 000次，隨機生成故障頂點集合，構(gòu)建任意兩個頂點之間的無故障路徑，最壞情況如圖2(a)所示，平均情況如圖2(b)所示．

圖2 σ=n-1時3種算法花費的CPU時間

根據(jù)實驗結(jié)果，構(gòu)造Xk，n-F上兩個頂點間的一條單播路徑所花費的CPU時間隨著維度k的增加逐步增多．根據(jù)實驗結(jié)果，當(dāng)σ=1，n=3且k=3時，XFRouting算法、BFS算法和DFS算法所花費的最壞CPU時間分別為760 ms，960 ms和948 ms，平均CPU時間分別為151 ms，415 ms和483 ms；當(dāng)σ=n-1，n=3且k=7時，XFRouting算法、BFS算法和DFS算法所花費的最壞CPU時間分別為234 ms，972 ms和990 ms，平均CPU時間分別為189.2 ms，362.6 ms和564.7 ms．由實驗數(shù)據(jù)可以得到，本文所提出的XFRouting算法在執(zhí)行效率上優(yōu)于廣度優(yōu)先搜索算法BFS和深度優(yōu)先搜索算法DFS．

5 結(jié) 論

數(shù)據(jù)中心網(wǎng)絡(luò)的容錯性是評估其網(wǎng)絡(luò)性能的重要因素，如果用連通度來評估其容錯性能，會低估數(shù)據(jù)中心網(wǎng)絡(luò)的容錯性能．基于每個頂點都至少有一個無故障鄰居這一條件下的限制連通度，能夠更加精確地度量數(shù)據(jù)中心網(wǎng)絡(luò)的容錯性．本文提出了一類遞歸型數(shù)據(jù)中心網(wǎng)絡(luò)(RDCN)，與傳統(tǒng)樹形數(shù)據(jù)中心網(wǎng)絡(luò)相比，該網(wǎng)絡(luò)具有更好的網(wǎng)絡(luò)帶寬和網(wǎng)絡(luò)容錯性能．證明了當(dāng)k≥1，n≥3且σ∈{1，n-1}時，其限制連通度為2kσ+n-2，這一結(jié)果近于其連通度的2倍；接著提出了該情形下時間復(fù)雜度為O(「logs|F|?k3)的容錯單播路由算法，證明了在最壞情況下構(gòu)造出容錯單播路由最長路徑長度的上界．仿真實驗結(jié)果表明XFRouting算法在執(zhí)行效率上優(yōu)于廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法．