分層超立方網絡的可靠性評估

劉西蒙，張郁芳，周書明，李小燕

（1.福州大學數學與計算機科學學院，福建 福州 350108；2.福州大學網絡安全福建省高校重點實驗室，福建 福州 350108；3.福建師范大學數學與信息學院，福建 福州 350007）

1 引言

隨著多處理器系統規模不斷擴大，處理器發生故障的情形不可避免。為了確保系統的穩定運行，需要對處理器進行測試和診斷，從而修復或更換有故障的處理器，以提高系統的可靠性。

故障診斷是評估系統可靠性和可用性的關鍵研究。系統中識別故障處理器的過程稱為系統級診斷[1]。最早的系統級診斷模型由Preparata、Metze和Chien[1]提出，稱為PMC 模型。PMC 模型通過相鄰2 個處理器互相測試來進行診斷。Maeng 和Malek[2]提出了基于比較的MM 模型，該模型是通過一個處理器把任務發送到與它相鄰的2 個處理器，然后比較它們的測試結果來進行診斷。隨后，Sengupta 等[3]提出了MM*模型，該模型是MM 模型的一種特殊情況，在該模型下，每個處理器均對與它有直接物理相連的任意2 個不同處理器的測試結果進行比較。在系統級診斷中，如果系統可以檢測出不超過t個故障處理器，則稱該系統為t-可診斷的。在t-診斷系統中可以實現的t的最大值稱為診斷度[1]。由于系統的最小度的限制，傳統的診斷度很小。為進一步提高系統的診斷能力，Zhang 等[4]提出了一種新的度量方法，稱為h-額外條件診斷度，并研究了超立方網絡的h-額外條件診斷度。圖G的h-額外條件診斷度（用(G)表示）是指在滿足G中每個無故障分支至少包含h+1個頂點的條件下，G可以保證識別的最大故障頂點數目。Lin 等[5]研究了一些正則網絡在PMC 模型下的h-額外條件診斷度（h=1 或2）。Huang 等[6]分析了交錯群圖在PMC 模型下的h-額外條件診斷度。Liu 等[7]研究了分層立方網絡在PMC 模型和MM*模型下的h-額外條件診斷度。LYU 等[8]確定了一般正則網絡在PMC模型和MM*模型下的h-額外條件診斷度（h=1或2）。Sun 等[9]研究了完全立方網絡在PMC 模型和MM*模型下的h-額外條件診斷度。

t/s-診斷策略（即系統最多可以識別出t個故障頂點，其中至多s個無故障頂點被誤診為故障頂點）是一種十分高效的系統級診斷策略。Somani 等[10]基于t/s-診斷策略提出了t/s-診斷度，并研究了超立方網絡和星形網絡在PMC 模型下的t/s-診斷度；Fan 等[11]研究了雙射連接網絡的t/s-診斷度；Yang等[12]提出了立方網絡的(4m-h)/3-診斷算法；Zhou等[13]給出了星形網絡的t/s-診斷度；Lin 等[14]討論了符合某些條件的正則網絡的t/s-診斷度，并提出了一種t/s-診斷算法；Liang 等[15]研究了關于超立方網絡在PMC 和MM*模型下的t/s-診斷度和t/s-診斷算法。此外，Xie 等[16]提出了關于超立方類網絡的時間復雜度較低的t/s-診斷算法；Li 等[17]研究了數據中心網絡DCell 在PMC 和MM*模型下的t/s-診斷度。然而，大多數網絡在MM*模型下的t/s-診斷度和t/s-診斷算法尚未得到研究。

Malluhi 等[18]提出了一種新的互連拓撲，稱為分層超立方網絡，其拓撲結構適用于大規模并行系統，且通信效率較高。目前，關于分層超立方網絡可靠性問題的研究較少，嚴重制約了分層超立方網絡的應用和推廣，基于此，本文對n維分層超立方（HHCn,n-dimension hierarchical hypercube）網絡（后文簡稱HHCn）在PMC 模型和MM*模型下的h-額外條件診斷度和t/s-診斷度展開研究，設計了相應的t/s-診斷算法，并分析其時間復雜度。

2 準備工作

2.1 術語與符號

對于以下未定義的圖論和網絡術語，可以參考文獻[19]。網絡可以拓撲為圖G=G(V,E)，其中每個頂點u∈V表示一個處理器，每條邊(u,v)∈E表示處理器u和v之間的連接。在圖G中，頂點v的鄰集N G(v)表示在圖G中與v相鄰的任意頂點u的集合，即NG(v)={u∈V|(u,v)∈E}。類似地，子集S?V的鄰集N G(S)表示與S中的某些頂點相鄰但是不包含S本身的頂點的集合。由S導出的G的子圖用G[S]表示，其頂點集為S，邊集為{(u,v)|(u,v)∈E,u,v∈S}。根據鄰域和子集鄰集的定義可知，N G[S]=N G(S)∪S。當G在上下文中語義明確時，為方便起見，將省略下標G。頂點u在G中的度定義為d(u)=|N G(u)|。集合M和N的對稱差集表示為

對于任意子集F?V(G)，符號G-F表示從圖G中刪除F中所有頂點，并刪除至少有一個末端頂點在F中的邊所得到的圖。G-F的每個極大連通子圖稱為圖G的一個連通分支，如果G-F是不連通的，則稱F為點割集。G1?G2表示G1與G2同構。mc(G) 表示圖G的最大連通分支的頂點數目。表示{1,2,3,…,n}。圖G的h-額外連通度是指使G-F不連通，并且剩余的每個連通分支的頂點數目不小于h+1的集合F的最小基數，用κh(G)表示。D表示PMC模型或MM*模型，(G,D)表示圖G在PMC 模型或MM*模型下的h-額外條件診斷度。在本文中，“圖”“網絡”“系統”含義相同。

2.2 PMC 模型和MM＊模型

在PMC 模型中，對于系統G=G(V,E)中任意2 個相鄰頂點u和v，當且僅當u測試v時，(u,v)∈E。G(V,E)中的測試結果集用函數σ:E→{0,1}表示，σ稱為系統癥候。用u測試v的結果表示為σ(u,v)。當u無故障時，如果v也無故障，則σ(u,v)=0；否則，σ(u,v)=1。如果u有故障，則σ(u,v)的值是不可靠的。

在MM*模型中，系統G=G(V,E)的比較方案可以刻畫為一個多重圖M(V,L)，其中V和L分別為G的頂點集和邊集。若2 個頂點u和v都與頂點w相鄰，則u與v可以通過w進行比較，即(u,v)w∈L。σ(u,v)w表示頂點w對2 個頂點u和v執行比較的結果。符號σ稱為系統癥候，定義為圖G中所有比較結果的集合。當w無故障時，如果u和v都沒有故障，則σ(u,v)w=0；否則，σ(u,v)w=1。如果w有故障，則σ(u,v)w的值可能為1 或0。在MM*模型中，如果(u,w),(v,w)∈E，則(u,v)w∈L。

引理1[20]對于系統G=(V,E)中的任意2 個不同故障子集F1和F2，當且僅當存在一個頂點u∈V-(F1∪F2)和一個頂點v∈F1ΔF2使(u,v)∈E時，F1和F2在PMC 模型下才是可區分的。

引理2[3]對于系統G=(V,E)中的任意2 個不同的故障子集F1和F2，當且僅當滿足以下條件之一時，F1和F2在MM*模型下才是可區分的。

1) 有2 個頂點u,w∈V-(F1∪F2)，并且有一個頂點v∈F1ΔF2使(u,w)∈E和(v,w)∈E。

2) 有2 個頂點u,v∈F1-F2，并且有一個頂點w∈V-(F1∪F2)使(u,w)∈E和(v,w)∈E。

3) 有2 個頂點u,v∈F2-F1，并且有一個頂點w∈V-(F1∪F2)使(u,w)∈E和(v,w)∈E。

2.3 分層超立方網絡

Malluhi 等[18]提出了分層超立方網絡，它將n維帶環立方網絡[21]中的環用超立方網絡替代。下面介紹分層超立方網絡的定義和性質。

定義1[18]n維分層超立方網絡HHCn用圖來定義，其中頂點集為{(X,Y)|X=an-1an-2…a m,Y=am-1am-2…a0}，ai∈{0,1}，0≤i≤n-1，n=2m+m且m≥ 1。HHCn的頂點連接規則如下。

1) (A,Bl)對于所有0≤l≤m-1。

2) (Am+dec(B),B)，其中dec(B)是B的十進制值。

HHCn是由2n個頂點組成的(m+1)-正則二部圖，每個頂點的度數為m+1，其中n=2m+m。HHCn由 22m簇組成，每個簇與m維超立方網絡Qm同構。每個簇用Ci表示，i∈<22m＞。Q2m結構與HHCn結構如圖1 所示（其中，m=2，n=6）。

圖1 Q 22結構與HHC6結構

情況2X中的頂點至少分布在2 個不同的簇中，如圖2 所示。

圖2 引理7 情況2 示意

3 分層超立方網絡的h-額外條件診斷度

本節將對分層超立方網絡在2 個不同的模型下的h-額外條件診斷度進行研究。

定義2[4]在圖G=G(V,E)中，當G-F是不連通的且G-F的每個分支至少含有h-1 個頂點時，稱故障集F為h-額外故障集。

定義3[4]對于圖G=G(V,E)中任意一對不同的h-額外故障子集F1,F2?V滿足|F1|≤t和|F2|≤t，且F1,F2是可區分的，則稱圖G是h-額外條件t-可診斷的，使圖G是h-額外條件t-可診斷的t的最大值，稱為圖G的h-額外條件診斷度，記作～t h(G)。

圖3 引理10 示意

證明記P是HHCn中一個簇C1的一個頂點子集，其中HHCn[P]?K1,h，F1=N(P)且F2=F1∪P。設S=N(P) ∩(HHCn-C1)，通過引理5 和HHCn的性質可得

因此，根據引理4 和引理9 可知引理11 成立。證畢。

根據引理10 和引理11，可以得出定理1。

圖4 引理12 示意

聲明1J不包含孤立的頂點。

假設I(≠?)是J中的一組孤立頂點集。顯然，對于任意i∈I有I≤2n-1，N(i)?F1∪F2。此外，|F1F2|≥ 1，|F2F1|≥ 1。否則，如果F2F1=?（或者F1F2=?），則F1?F2。也就是說N(i)?F2，則i是HHCn-F2中的一個孤立頂點，這與h≥ 1的條件相矛盾。另一方面，如果在F1F2中存在2 個頂點u和v使(u,i),(v,i)∈E，則(F1,F2)是可區分的，這與假設相矛盾。如果不存在頂點u∈F1F2使(u,i)∈E，則HHCn-F2中的i是一個孤立頂點，這與h≥ 1的條件相矛盾。因此，N(i) ∩(F1F2)=1。同樣地，N(i) ∩(F2F1)=1。因此，有

所以，|F1∩F2|≥ |N(i) ∩(F1∩F2)|=m-1。

令A=JI，接下來證明A≠?。利用反證法，假設A=?，可得

這是矛盾的，證畢。

根據引理10 和引理12，可以得出定理2。

4 分層超立方網絡的t/s-診斷度

本節將研究HHCn在PMC模型下以及MM* 模型下的t/s-診斷度（m≥5，n=2m+m，1≤s≤m-1）。此外，還將設計相應的t/s-診斷算法。

定義4[10]給定一個系統G，當系統中的故障頂點數目不超過t時，若對于任意癥候σ，系統可以將所有故障頂點都分離在一個故障集合F′中，且F′包含至多s個無故障頂點，即F′≤|F|+s，則稱這個系統是t/s-可診斷的。滿足系統是t/s-可診斷的最大的t值稱為t/s-診斷度。

定義5[12]給定系統G=(V,E)和在G中由故障集產生的癥候σ。若T0(G)是G的0-測試子圖，則需滿足T0(G)是G的一個子圖，同時V(T0(G))?V且E(T0(G))={(u,v)∈E,σ(u,v)=σ(v,u)=0}。

引理13[12]在PMC 模型下給定一個系統G=(V,E)以及在G中由故障集產生的癥候σ，有如下結論。

1) 令u,v是G中的 2 個相鄰頂點。如果σ(u,v)=σ(v,u)=0，則要么頂點u和v均無故障，要么頂點u和v均存在故障。

2) 令C為T0(G)的分支，則C中的所有頂點要么都是故障的，要么都是無故障的。

定義6[17]給定系統G=(V,E)及在G中由故障集產生的癥候σ。令x?V，頂點x的0-比較子集表示為C0(x)={c∈V|?a∈V,σ(x,a)c=0}。G的0-比較子圖記為T′(G)，表示為G的一個子圖，其中，V(T′(G))?V且E(T′(G))={(x,c)∈E|c∈C0(x),x∈C0(c)}，如圖5 所示。

圖5 G 的0-比較子圖 T ′(G)的說明

引理14[17]給定一個至多包含t個故障頂點的系統G=(V,E)，以及在G中基于MM*模型由故障集產生的癥候σ，有如下結論。

1) 如果對于任意2 個頂點x,y∈V且(x,y)∈E使y∈C0(x)和x∈C0(y)，則x和y具有相同的狀態（即同為故障或無故障）。

2) 對于連通分支R?T′(G)，R中的所有頂點要么都是故障的，要么都是無故障的。

3) 如果T′(G)的連通分支R滿足|V(R)|≥t+1，則R中的所有頂點都是無故障的。

根據引理13中結論2)和引理14中結論2)可知，C中的所有頂點均為無故障，因此引理15 成立。證畢。

證明設F是HHCn的故障集，F′是所有故障頂點和可疑頂點的集合，C為T0(HHCn)或T′(HHCn)的最大連通分支。通過考慮F的大小進行證明。

根據引理15 可得

F′中最多包含s個無故障頂點。因此，在此情況下，定理3 成立。

輸出故障頂點集F′和無故障頂點集Y，其中F′∪Y=V(HHCn)

1) 初始化F′=?，Y=?，U=V(HHCn)，其中，?表示空集。

2) 檢查HHCn中所有的測試結果。?表示2個頂點u和v在PMC 模型下相互測試。刪除測試結果是1 ? 0、0 ? 1、1 ? 1的邊，并將0 ? 0的邊添加到E′中。令T0(HHCn)為E′的導出子圖。

3) 獲得無故障頂點的集合C。通過廣度優先搜索在T0(HHCn)中獲得最大連通分支C，并將C中的所有頂點添加到Y中。令U=U-Y。

4) 對于前面步驟中每個未診斷的頂點v，如果它的相鄰頂點u∈C且σ(u,v)=1，則將v添加到F′中。令U=U-F′。

根據定理3 中情況2 可知，如果可疑頂點的數目超過s+1 個，則所有的可疑頂點都是無故障的。如果可疑頂點的數目少于s個，那么定理4 顯然成立。

這意味著F′最多包含s個無故障頂點。因此，定理4 成立。證畢。

定理5當m≥ 5，n=2m+m，且1≤s≤m-1時，算法t/s-HHCn-DIAG-PMC 的時間復雜度為O(NlogN)，其中N=|V(HHCn)|。

證明算法t/s-HHCn-DIA G-PMC 主要時間成本在于獲取T0(HHCn)的最大連通分支C，廣度優先搜索算法最多運行O(N(m+1))次。因為log(2m+1)=m+1 ≤log(N)，所以獲取T0(HHCn)的最大連通分支C的時間復雜度為O(NlogN)。其他每步的時間復雜度至多為O(N)。因此，算法t/s-HHCn-DIA G-PMC 的時間復雜度為O(NlogN)。證畢。

本文提出了一種在MM*模型下通過深度優先搜索（DFS,depth first search）定位HHCn的無故障連通分支的算法DFS-MM*，如算法2 所示。然后基于DFS-MM* 算法，提出了一個針對HHCn的t/s-診斷算法t/s-HHCn-DI AG-M M*，其中，T表示無故障的頂點集合，F′表示通過此算法被診斷為故障頂點的集合，H表示為未診斷(可疑)的頂點集合。

算法2DFS-MM*

輸入HHCn中由故障集F產生的癥候σ，頂點集R和頂點x∈HHCn

由定理3 中情況2 可知，若可疑頂點的數目超過s+1，則所有可疑頂點都是無故障的。相反，如果可疑頂點的數目小于s，那么定理6 顯然成立。

由引理3 可知，HHCn-F中存在一個唯一的最大連通分支K且V(K)≥V(HHCn) -|F|-s，那么HHCn中除去最大連通分支K外剩余的小連通分支至多包含s個頂點。根據t/s-HHCn-DIAG-MM*算法，當|V(K)|≥V(HHCn) -|F|-s＞t+1時，K中的所有頂點被診斷為無故障。在t/s-HHCn-DIAG-MM*算法中，如果|F′ |=t，則H中的所有頂點被診斷為無故障，沒有頂點被誤診；如果|F′ |≠t，則將所有未診斷（可疑）頂點分離到F′中。因此，F′=V(HHCn)-T，其中T被診斷為無故障的頂點的集合。則有

這意味著F′最多包含s個無故障頂點。因此，定理6 成立。證畢。

定理7當m≥ 5，n=2m+m，且1≤s≤m-1時，t/s-HHCn-DIAG-MM*算法的時間復雜度為O(NlogN)，其中N=|V(HHCn)|。

5 比較結果

在系統級診斷中，如果系統可以檢測出不超過t個故障處理器，則稱該系統為t-可診斷的。在t-診斷系統中可以實現的t的最大值稱為診斷度，即傳統診斷度[1]。根據t-可診斷的定義可知，分層超立方網絡的傳統診斷度為m+1 。本節對本文研究的分層超立方網絡的h-額外條件診斷度、t/s-診斷度與傳統診斷度進行比較分析，結果如圖6 所示。

圖6 HHCn 在3 種診斷策略下的故障診斷度（n=2m+m）

由圖6 可知，當m≥5 時，分層超立方網絡的h-額外條件診斷度、t/s-診斷度均大于傳統診斷度，且分層超立方網絡的h-額外條件診斷度是傳統診斷度的h+1 倍，t/s-診斷度是傳統診斷度約s+1 倍。因此，與傳統診斷度相比，h-額外條件診斷度和t/s-診斷度提高了網絡的診斷度，能更好地評估分層超立方網絡的可靠性。

6 結束語

本文的研究成果有利于進一步評估分層超立方網絡的可靠性，為分層超立方網絡的應用和推廣奠定了的理論基礎。在接下來的工作中，可以考慮使用t/s-診斷算法監控分層超立方網絡中的故障服務器。此外，郭晨等[26]研究了交換交叉網絡在PMC模型下的(t,k)-診斷度，熊茜等[27]研究了交換超立方網絡在PMC 模型下的(t,k)-診斷度，受其啟發，分層超立方網絡在PMC 模型和MM*模型下的(t,k)-故障診斷問題將是下一個研究內容。