一類遞歸型數據中心網絡上容錯單播算法的研究

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

1. 蘇州工業職業技術學院 軟件與服務外包學院，江蘇 蘇州 215004； 2. 蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006

近年來，隨著云計算和大數據應用的飛速發展，數據中心網絡(Data Center Network)作為其基礎設施和下一代網絡技術的創新平臺，得到了學術界和工業界的廣泛關注[1-3]．

數據中心網絡的容錯性是評估網絡性能的重要因素．連通度是度量數據中心網絡容錯性的一個重要參數，連通度越大，則數據中心網絡的容錯性能就相對越高．數據中心網絡連通度定義中，發生故障的服務器是任意的、沒有限制條件的，然而實際情況往往并非如此．僅使用連通度來評估數據中心網絡的容錯性，會嚴重低估數據中心網絡的容錯性能．因此，涌現了大量在特定網絡拓撲上的限制連通度問題的研究成果[3-12]．

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

1 預備知識

數據中心網絡可以表示為一個簡單圖G=(V(G)，E(G))，其中V(G)表示頂點集，E(G)表示邊集．頂點和邊分別表示數據中心網絡中的服務器和連接服務器的鏈路，而交換機被認為是透明的網絡設備[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)．

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

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

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

根據文獻[13]和文獻[14]，可得出Xk，n網絡的基本性質如下．

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

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

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

表1 幾種常見數據中心網絡性質比較

與RDCN相比，Tree和Fat-Tree的擴展規模在理論上受限于核心交換機的端口數目，不利于數據中心網絡規模的快速擴張，且它們的容錯性受到核心交換設備影響較大，對核心交換設備的故障非常敏感．同時，Tree和Fat-Tree的拓撲結構的特點決定了其不能很好支持一對多、廣播和全交換等網絡通信模式．另外，與RDCN相比，FiConn網絡的容錯性較差，網絡直徑較大．因此與上述數據中心網絡相比，RDCN具有較高的網絡帶寬、較好的容錯性．特別的，σ=n-1時的RDCN比σ=1時的RDCN具有更高的網絡帶寬和容錯性能．

2 遞歸型數據中心網絡的限制連通度

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

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

引理4[15]對于任意的整數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從左側開始最先不同的下標，則有

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

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

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

當k=1時，該斷言顯然成立．

令α=(u)k，β=(v)k，當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α≠δ且α≠γ．對于任意整數i∈Ik，n{α}，有fi≤|F|-fα≤(2kσ+n-3)-(n+kσ-2)=kσ-1≤n+kσ-3．根據引理2，G1是連通的，G1中存在路徑Q連接x和y．因此Xk，n-F中存在路徑(u，x，Q，y，v)連接u和v．

令

對c′求導則有

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

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

和

根據情形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．接下來，分以下兩種情形討論．

根據引理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對于任意整數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成立．

對于任意的整數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}])．

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

當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})．

當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成立．

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

3 遞歸型數據中心網絡基于限制故障集的單播算法

定理4證明了遞歸型通用網絡上限制連通度的精確值，本節將提出網絡上基于限制故障頂點集合的單播算法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，u，v))；

function XFR(Xk，n，F，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，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算法的設計思路和執行過程，并分析其時間復雜度．

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

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

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

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

因此可得：

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

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

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

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

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

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

令

d=logs|F|

則有

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

證畢．

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

4 模擬實驗及結果分析

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

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

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

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

根據實驗結果，構造Xk，n-F上兩個頂點間的一條單播路徑所花費的CPU時間隨著維度k的增加逐步增多．根據實驗結果，當σ=1，n=3且k=3時，XFRouting算法、BFS算法和DFS算法所花費的最壞CPU時間分別為760 ms，960 ms和948 ms，平均CPU時間分別為151 ms，415 ms和483 ms；當σ=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．由實驗數據可以得到，本文所提出的XFRouting算法在執行效率上優于廣度優先搜索算法BFS和深度優先搜索算法DFS．

5 結 論

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