具有失效節點和鏈路的Ｅ２ＤＭｅｓｈ網絡可靠性研究

（廣西大學 計算機與電子信息學院， 南寧 530004）



摘要：

對E2DMesh網絡中節點和鏈路失效模式進行了研究，構造了一種多級事件狀態分解法，對網絡狀態空間進行分解。基于該方法和組合模型原理研究了在給定節點和鏈路失效概率均為0.10%以下時，對多達上千個節點的E2DMesh網絡仍可達超過0.911 9的可靠度。該方法能夠應用于研究其他層次結構的網絡與其他網絡通信問題，也很適合近似計算。

關鍵詞：E2DMesh網絡；可靠性； kE2DMesh子網； 概率分析

中圖分類號：TP393文獻標志碼：A

文章編號：10013695(2009)03103603



Reliability research of E2DMesh network with node and link failures



XIAO Jie， HUANG Yihai， LIANG Jiarong



(College of Computer Electronic Information， Guangxi University， Nanning530004， China)



Abstract:

To investigate the mode of E2DMesh network with node and link failures， this paper gave a multilevel decomposition algorithm of the event states space. Based on the algorithm and the theory of combination model， the reliability of E2DMesh network with over one thousand nodes was above by 0.9119 when the failure probability of the node and link in E2DMesh network which was attributed bounded by 0.10%. The scheme is applicable to the study of other hierarchical network structures and other network communication problems， and is most suitable for approximating computation.

Key words：E2DMesh network; reliability; kE2DMesh; probability analysis



0引言

隨著計算機技術的迅速發展，計算機已在各個領域得到廣泛的應用。越來越多的部門，如通信、金融、國防、工業控制等領域，對計算機產生了很強的依賴性。這些系統一旦發生故障，將帶來不可估量的損失。E2DMesh網絡以其結構簡單、規則及良好的可擴展性、易于VLSI實現而成為許多大型多處理器并行計算機系統所采用的拓撲結構[1]。其可靠性計算已成為人們關注的重要課題。

目前大多數文獻在研究通信網絡可靠性時，一般均假設鏈路失效，而節點完全可靠[2~4]，只有少量的文獻涉及到節點失效的情況[5~6]。而在實際的通信系統中，通信網中的節點代表通信終端，它們同樣存在失效的可能性。因此，研究節點、鏈路均具有失效可能的通信網可靠性更具有現實意義。

在考慮節點和鏈路失效的可靠性計算方法中，現有方法如factoring法[7]、Buzacott法[8]運算量都很大，只能分析中小規模網絡，文獻[8]提出的多邊形化簡方法，只能減小等效網絡的狀態空間，仍需要進行大量的計算。網絡分解技術[9，10]著眼于處理事件而不是基本事件，從而大大提高了運算速度，然而，這種方法用于計算大規模并行計算網絡時仍具有較大的運算量。

基于上述原因，本文采用網絡分解技術對節點和鏈路失效下的kE2DMesh子網的可靠性進行定量分析，再通過組合模型計算出整個E2DMesh網絡的可靠性。據筆者所知，這是第一次對節點和鏈路失效下的E2DMesh網絡可靠性給出嚴格的數學推導。

1E2DMesh網絡可靠性分析

網絡終端對可靠性是指在通信網的兩個指定節點之間，至少存在一條通信路徑的概率大小。為了評價一個規模為m×n的E2DMesh網絡EMm×n的可靠性，根據其特點，本文隨機給出E2DMesh網絡上的兩個通信終端，通過分析在兩終端之間至少存在一條連通路徑的概率來評價其可靠性。

一個規模為m×n的E2DMesh網絡，可被分成(m/k)×(n/k)個不相交的kE2DMesh子網，整個E2DMesh網絡EMm×n被分成m/k行和n/k列，每一行上有n/k個子網，每一列上有m/k個子網。用二維坐標（x，y）來標志E2DMesh網絡EMm×n的節點，這里1≤x≤m，1≤y≤n，若兩個(x1，y1)與(x2，y2)節點相鄰，則它們的坐標關系有：1≤|x1-x2|+|y1-y2|≤2。則稱節點（x1，y1）與 (x2，y2)為鄰接點。圖１給出了6×6的E2DMesh網絡EM6×6被分成4個3×3的3E2DMesh子網的情形。

定義1E2DMesh網絡EMm×n中的一個kE2DMesh子網EMb，d是由兩個整數 b和d決定的，b＜m/k，d＜n/k，規模為k×k的E2DMesh網絡，組成其節點的坐標為(x，y)，這里x=bk+1，bk+2，…，(b+1)k；y=dk+2，…，(d+1)k。

根據定義１可知EMm×n可由一系列互不相交的子網EM1，1，EM1，2，…，EMm/k，n/k構成。

在E2DMesh網絡EMm×n中，本文作如下假設：

a)整個網絡及每個元件(節點和鏈路)的工作狀態在統計上相互獨立；

b)整個網絡的每個元件有兩種工作狀態，即正常工作或失效。

c)網絡中節點和鏈路以一定的概率正常工作。

1.1節點和鏈路失效下的子網可靠性度量算法

在子網 EMk中，本文對符號進行如下約定：pNi、pLj表示為EMk中節點i和鏈路j正常工作的概率；n 、m分別表示節點數和鏈路數；Si、Fj表示成功事件和失效事件 i;Si，j為Si的子事件，包含終端節點為j的各條鏈路狀態信息；Fi，j為Fi的子事件，包含終端節點為j的各條鏈路狀態信息；NSf為本文方法總的生成事件數。

令EMk為一規模為k×k的kE2DMesh子網，為了方便起見，本文以３×３的3E2DMesh子網為例來介紹子網可靠性模型的建立和分析。包含９個節點，20條鏈路，且具有節點和鏈路失效的EM3子網有向化后如圖２所示。在EM3中，不妨設s3為始點，t1為匯點。其中實線對應的方向為正方向，虛線對應的方向為負方向，且實線和對應的虛線在物理上為同一條鏈路。

考慮到對子網EMk有向化轉換后會帶來事件的統計相關性，使得同一條鏈路參與了兩次可靠性計算，以致產生錯誤的結果。為了解決這個問題，先對無向網絡進行有向化轉換，再消除統計相關性。其基本思路是在網絡EMk有向化處理后，對條件進行適當的約束，確保雙向鏈路中只有一條有向鏈路參與到可靠性中計算，并對參與計算的鏈路進行標記；如果雙向鏈路〈i，j〉和〈j，i〉中有一條鏈路失效，由于〈i，j〉和〈j，i〉在物理上是一條鏈路，則令〈i，j〉和〈j，i〉同時失效。依據網絡分解技術，以下給出具有節點和鏈路失效下的EMk子網的可靠性算法理論[10]。

在事件Si中，將有同終端的鏈路歸結到同一分塊，則有

pr{Si}=pNs×∏nj=1， j≠spr{Si，j}(1)

其中：s表示為網絡EMk的始點；pNs為該終端的正常工作概率。

在Si中若不存在指向節點j的鏈路狀態，則令pr{Si，j}=1。若在指向節點j的鏈路中，鏈路X1，X2，…，Xkj正常工作，而不存在其他鏈路狀態，則有

pr{Si，j}=pNj×∏Xkjk=X1pLk(2)

在Si指向節點j的鏈路中，若鏈路X1，X2，…，XLj失效，而XLj+1，XLj+2，…，XLj+kj正常工作，則對任意的Lj≥1，可得

pr{Si，j}=pNj×∏XLjk=X1(1-pLk)∏XLj+xjk=XLj+1pLk;kj≥1(3)

若kj=0，則可推知節點j失效或者全部Lj條鏈路失效但節點j正常。因此有

pr{Si，j}=（1-pNj）+pNj×∏XLjk=X1(1-pLk);kj=0(4)

由于事件的分解原理是依據達摩定律所得，可知EMk的可靠性概率為所有成功事件的概率之和：

RE=∑|S|i=1pr{Si}(5)

其中|S|表示成功事件的總數。

根據式(1)~(4)同樣可得失效事件的不可靠概率如下：

FT=∑|F|i=1pr{Fi}(6)

其中|F|表示失效事件總數。

所以 RE也可表示為

RE=pNS-FT(7)

由于節點失效的聯合算法可以通過分解技術嵌入到Dotson算法中，因此在算法終止前有：

∑|NS|i=1pr{Si}≤RE≤1-(∑|NF|i=1pr{Fi})(8)

其中：|NS|、|NF|分別表示當前未完成的成功和失效事件總數。這樣在算法迭代過程中，可不斷更新可靠度的上下界，從而保證在算法運行結束前仍可得到可靠度的范圍，增加了算法的可用性。

為了實現節點和鏈路失效下網絡EMk可靠度的計算，本文定義了狀態矩陣 A=[ai，j]用來表示成功或失效事件對應的有向圖，以及用來表示當前所有鏈路狀況的事件E。其中：

[ai，j]＞0如果成功事作s中鏈路〈i，j〉正常工作

＜0如果成功事件s中鏈路〈i，j〉失效

=0其他

且利用棧結構Q來存放產生的事件E。

算法(MSA)：以s為始點、t為匯點的EMk子網可靠度度量算法(MSA)。

輸入：子網EMk的鄰接矩陣H，節點和鏈路的概率向量及始點s和匯點t。

輸出：子網 EMk可靠度上下界Rup、Rtow。

令以s為始點、t為匯點的EMk子網可靠度下界Rtow=0；

令以s為始點、t為匯點的EMk子網可靠度上界 Rup=PNs；

初始化事件 E={0，0，…，0}；i=1；

將事件E加入到 Q的棧頂。

a)從Ｑ的棧頂取出事件E并產生其對應的鄰接矩陣H1，利用深度優先搜索鄰接矩陣H1中s到t的可行路徑Ｐ。

b)若P≠，則Si=E+P且產生新的狀態矩陣 A，利用式(1)~(5)和A求得 Si對應的可靠性概率ps；Rlow=Rlow+ps，利用達摩定律產生Si的補事件并加入到Q的棧頂，i++;否則，Fi=E且由Fi產生狀態矩陣A，利用式(6)和(7)及A，求得Fi對應的不可靠性概率pf，Rup=Rup-pf，i++。

c）若Q=，則轉a）；否則結束。

執行完畢后，子網可靠度上下界Rup、Rlow的結果將是一致的。在算法結束前，根據式(8)可得可靠性概率的范圍，也可以通過設置一個范圍來提前終止程序。

由于采用鄰接矩陣作為圖的存儲結構，不難得出利用深度優先搜索尋找從始點到匯點時間復雜度為O(n2)，因為本文方法生成總的事件數為NSf，所以總的時間復雜度為O(n2NSf)。

1.2理論計算與實驗結果

由于本文是通過分析兩個通信終端之間至少存在一條連通路徑的概率來評價E2DMesh網絡的可靠性，需要在兩個終端u和v之間構造一條由無失效節點和鏈路組成的路徑。不妨假設，在兩個相鄰子網的四個方向上至少存在一對相鄰的正確節點。也就是說，子網間是相互連通的。圖３顯示了子網間的連接關系。

設節點u(xu，yu)位于kE2DMesh子網EMs，t中，v(xv，yv)位于kE2DMesh子網EMs′，t′中，不失一般性，假設s≤s′，t≤t′，則可按子網序列EMs，t，EMs，t+1，…，EMs，t′，EMs+1，t′，…，EMs′，t′構造一條從u到v的路徑。因為S=（xu-1）/k」，t=(yu-1)/k」，s′=(xv-1)/k」，t′=(yv-1)/k」，所以可得u到 v的成功路徑所經過的子網數為|s′-s|+|t′-t|+1。

根據假設在兩個相鄰子網的四個方向上至少都存在一對相鄰的正確節點，從圖2可知，子網 EMk的始點和匯點對共有８對組合。經過分析發現s3→t1組合對是可靠度最差的一組，不妨就以這對組合的可靠度來求得整個網絡的可靠度下界。

由于以E2DMesh網絡為拓撲結構的大規模并行計算機是多個處理器同時相互獨立地進行工作，根據組合原理，可得以u和v為終端的E2DMesh網絡EMm×n的可靠度為|s′-s|+|t′-t|+1個子網同時可靠工作的概率，即

RE(EMm×n)=RE(EMs，j)∩RE(EMs，t+1)∩…∩RE（EMs，t′）∩RE(EMs+1，t′)∩…∩RE（EMs′，t′）=(RE(EMk))|s′-s|+|t′-t|+1

注意到(s′-s)≤「m/k-1，(t′-t)≤「n/k-1，因此有RE(EMm×n)≥(RE(EMk)）「m/k+「n/k-1。

根據分析，本文得出的是以u和v為終端的E2DMesh網絡EMm×n可靠度的一個下界。為了更具體地體現本文的結果，下面用具體的例子來說明。令k=3，且假設每個節點和鏈路的失效概率均為0.10%（這是現有的大規模集成電路技術完全能夠做到的），對不同規模下的E2DMesh網絡EMm×n可達到的可靠度如表1所示。實驗表明，上面提出的算法還具有較快的收斂速度。

表１的結果說明了以E2DMesh網絡為拓撲結構的大規模并行計算機系統的可用性和較強的可靠性。在網絡節點和鏈路的失效率被控制在0.10%以下時，對多達上千個節點的E2DMesh仍然可達到超過0.911 9的可靠度，且這是現有的大規模集成電路技術完全可以辦到的。

2結束語

本文主要基于網絡分解技術和組合模型原理對E2DMesh網絡在節點和鏈路失效情況下對其可靠性進行了研究。通過網絡分解技術建立了子網在節點和鏈路失效情況下的可靠性模型，又利用組合模型原理求得了整個E2DMesh網絡的可靠度。實驗結果表明，隨著網絡規模的擴大，E2DMesh網絡的可靠性也隨之下降。當節點和鏈路的失效率被控制在0.01%以下時，則對多達上千個節點的E2DMesh仍可達超過0.911 9的可靠度。

參考文獻：

[1] CHEN Xiao．Faulttolerant adaptive and shortest routing in 2D extended meshes using faultyblockinformation[C]//Proc of International Workshops on Parallel Processing. 2000:267274.

[2]HSU S J， YUANG M C. Efficient computation of marginal reliabilityimportance for reducible networks[J]. IEEE Trans on Reliability，2001，50(1):98106.

[3]HSU S J， YUANG M C. A network reduction axiom for efficient computation of terminalpair reliability[J]. Computers Mathematics with Applications， 2000，10(3):359372.

[4]KUO S Y， LU S K， YEH F M. Determining terminalpair reliability based on edge expansion diagrams using OBDD[J]. IEEE Trans on Reliability， 1999，48(3):234246.

[5]王高才，陳建二，陳松喬，等．Mesh網絡路由算法容錯性的概率分析[J].計算機學報，2004， 27(3):319327.

[6]鐘子果，胡愛群，陳勇．具有不完全可靠節點的無向網絡終端可靠性評價方法[J]．電路與系統學報， 2005，10(5):136143.

[7]RESENDEL L I. Implementation of a factoring algorithm for reliability evaluation of undirected networks[J]. IEEE Trans on Reliability， 1988，37(5):462467.

[8]MONTICONEL C. An implementation of the Buzacott algorithm for network globalreliability[J].IEEE Trans on Prliability， 1993，42(1):4649.

[9]TORRIERI D. Calculation of nodepair reliability in large networks with unreliable nodes[J]. IEEE Trans on Reliability， 1994，43(3):375382.

[10]向東，張躍鯉.Mesh網中高效無死鎖自適應路由算法[J].計算機學報，2007，30(11):19541962.

[11]MAURICIO G C R. A program for reliability evaluation of undirected networks via polygontochain reduction[J]. IEEE Trans on Reliability， 1986， R35(1):2429.