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

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

情形1.1α≠δ且α≠γ．對(duì)于任意整數(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．

令

對(duì)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}=?．

因?yàn)閨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．接下來(lái)，分以下兩種情形討論．

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

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

定理4對(duì)于任意整數(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．

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因此可得：

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

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

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

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

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

函數(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時(shí)s=tk-1，n+1?|F|，則d=logs|F|<1．因此有

證畢．

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

4 模擬實(shí)驗(yàn)及結(jié)果分析

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

圖1 σ=1時(shí)3種算法花費(fèi)的CPU時(shí)間

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

圖2 σ=n-1時(shí)3種算法花費(fèi)的CPU時(shí)間

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

5 結(jié) 論

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