具有可維修鏈路的Ｅ－２ＤＭｅｓｈ網絡可靠性研究
2009-01-01 00:00:00肖杰梁家榮徐霜李銀
計算機應用研究 2009年2期
（廣西大學 計算機與電子信息學院， 南寧 530004）
摘 要：
對E-2DMesh網絡中單工失效鏈路模式進行了研究，提出了基于子網的狀態轉移模型。基于該方法分別對不可維修和可維修鏈路模式進行了分析，證明了對較大規模的E-2DMesh網絡，不可維修鏈路模式的可靠性要比可維修鏈路模式低。提出的方法能夠用于研究其他層次結構網絡和其他網絡通信問題。
關鍵詞：E-2DMesh網絡； 可靠性； 子網； 馬爾可夫模型
中圖分類號：TP393 文獻標志碼：A
文章編號：1001-3695(2009)02-0668-03
Reliability research of E-2DMesh network with repairable links
XIAO Jie， LIANG Jia-rong， XU Shuang， LI Yin
(School of Computer， Electronics Information， Guangxi University， Nanning 530004， China)
Abstract:To investigate the mode of E-2DMesh network with unidirectional links failure， this paper proposed a state transition model which was based on subnet for the E-2DMesh network.Analyzed the mode of network with unrepairable and repairable links based on the algorithm respectively. The results show that the reliability of network with unrepairable links is less than the one with repairable links for the E-2DMesh network with large scale. The scheme is applicable to the study of other hierarchical network structures and other network communication problems.
Key words：E-2DMesh network; reliability; k-E-2DMesh; Markov model
0 引言
隨著計算機技術的發展，大型多處理器并行計算機系統已在各個領域得到了廣泛的應用。越來越多的重要部門，如通信、金融、國防、工業控制等對大型并行計算機系統產生了很強的依賴性，這些系統的計算機一旦發生故障，將帶來不可估量的損失。以E-2DMesh網絡為拓撲結構的新型并行計算機系統，因其結構簡單、規則、可擴展且易于VLSI實現等優點而成為許多大型多處理器并行計算機系統所采用的拓撲結構[1]。因此，對其可靠性進行研究具有重要的實際價值。
目前大多數文獻在研究通信網絡可靠性時，一般均假設失效鏈路不可維修[2]，只有少量的文獻涉及到鏈路可維修的情況[3]。而在實際的通信系統中，通信線鏈路是冗余設計的，也就是說存在鏈路失效時對其進行維修是不影響系統通信的。因此，對可維修鏈路的大規模并行計算機系統進行研究更具有現實意義。
現有的方法在研究具有失效鏈路的通信系統可靠性時，大多是通過研究終端對的可靠性來評價整個系統的可靠性[4]，這種方法不能實地反映整個系統的可靠性，缺乏靈活性。有的方法如馬爾可夫鏈模型運算量比較大[5]，只能分析中小型規模網絡。Menezes等人使用組合模型方法研究了多級網絡的可靠性[6]，但是他們沒有考慮鏈路可修復的情況且缺乏嚴格的數學論證，使人們在實際使用時對其可靠性仍然沒有足夠的把握。
基于上述原因，本文設定從網絡中任意節點到其他所有節點至少存在一條路徑的概率來度量E-2DMesh網絡的可靠性，通過組合模型與馬爾可夫鏈模型相結合的方法對單工可維修鏈路的E-2DMesh網絡可靠性進行定量分析。這是第一次對單工可維修鏈路的E-2DMesh網絡可靠性給出嚴格的數學推導。
1 E-2DMesh網絡可靠性分析
本文首先研究k-E-2DMesh子網的可靠性模型(為簡單起見，令k=3)，然后給出整個具有單工可維修鏈路的E-2DMesh網絡的可靠性模型。由于節點的可靠性通常大于鏈路的可靠性，本文只考慮鏈路失效而不考慮節點失效的情況，并假定所有鏈路具有相同的失效率λ和維修率α。
一個規模為m×n的E-2DMesh網絡EMm×n，可以被分成(m/k)×(n/k)個不相交的k-E-2DMesh子網，整個E-2DMesh網絡EMm×n被分成m/k行和n/k列，每一行上有n/k個子網，每一列上有m/k個子網。圖１給出了6×6的E-2DMesh網絡EM6×6被劃分為四個3×3的３-E-2DMesh子網的情形及其鏈路方向。
1. 1 不可維修鏈路可靠性模型
令EMk是一規模為k×k的E-2DMesh網絡，為簡單起見，本文以規模為3×3的3-E-2DMesh子網為例來介紹子網可靠性模型的建立和分析。包含９個節點，20條鏈路，由單工鏈路組成的子網EM3如圖２所示。假定鏈路失效服從指數分布，網絡正常工作時的鏈路失效率和維修率均為λ和α。失效不可維修鏈路對應的馬爾可夫狀態轉換圖如圖３所示。在圖２中，假定所有虛線表示的單工鏈路均為有效鏈路，實線表示的單工鏈路具有失效性。
定義１ 由于鏈路失效，在實線表示的單工鏈路部分，除節點sk不能接收消息和節點dk不能發送消息外，子網EMk中如果存在一個節點不能發送或者接收消息時，網絡即不連通(網絡失效)。
圖３中，狀態i(i=0，1，2，…，11)表示i條單工鏈路失效后，子網仍然保持連通狀態。０表示子網的初始狀態，沒有鏈路失效；Ｆ表示網絡處于不連通狀態，即網絡失效。箭頭上的數字表示在Δt時間內狀態間的轉移概率。
在不可維修的EM3子網中，若在失效的i條單工鏈路外又有鏈路失效，那么該失效鏈路的生成導致狀態從i向j(j=i，i+1，i+2，…，11，F)轉移。以下對已失效鏈路外一條單工鏈路的失效導致各狀態轉移的情況進行討論。
0→F：表示子網從初始狀態轉為失效狀態。根據定義１容易知道，只要圖２中左右兩邊４條單工鏈路中的任何一條失效，網絡即進入不連通狀態，即失效。所以子網從０狀態轉移到Ｆ狀態的概率為e-4λΔt。
0→1：表示子網從初始狀態轉為有１條鏈路失效狀態，子網仍然保持連通。因為子網EM3中共有20條鏈路，除了能使網絡從初始狀態轉移到不連通狀態的４條鏈路外，剩余的16條鏈路中任意一條失效都能使子網從０狀態轉移到１狀態。所以狀態轉移概率為e-16λΔt。
0→0：因為０狀態只能轉移到１狀態和Ｆ狀態，所以子網保持初始狀態的概率為1-e-20λΔt。
同理，可以得出i→j(i=1，2，…，11; j=i，i+1，…，11，F)的狀態轉移概率，結果如圖３所示。
為了分析子網的可靠度R(t)，引入時間的概念進行分析并建立子網的狀態轉移方程。
1)在T=t時刻
定義EM3處于初始狀態，在此狀態下的概率為p0，t；處于狀態i(i=1，2，…，11)下，EM3仍然保持連通的概率為pi，t、EM3處于Ｆ狀態下的概率為pF，t。
2）在T=t+Δt時刻
（1)在初始狀態下，子網EM3只有從t時刻開始Δt時間內沒有故障鏈路出現，子網才能維持其狀
態，因此概率為p0，t+Δt=p0，t(1-20λΔt)+o(Δt)。
（2)子網EM3處于狀態１下有兩種情況：①T=t時子網處于狀態１下，Δt后仍處于狀態１下，此時的概率為P1，t(1-19λΔt)+o(Δt)；②T=t時子網處于狀態０下，Δt后轉移到狀態１下，此狀態轉移概率為p0，t16λΔt+o(Δt)。故在T=t+Δt時刻，系統處于狀態１下的概率為
相同的方法，可得到系統在T=t+Δt時刻處于狀態j(j=2，3，…，11，F)下的概率分別為
定義可靠度Ri(t)(0≤i≤11)為系統到時刻t有i條鏈路失效仍保持連通的概率。因此，根據上式可求得子網EM3的可靠度。
定理１ 在單工不可維修鏈路模式下，假設子網EM3中每條鏈路具有獨立的失效概率λ，則子網EM3的可靠度為
其中：p0，t=e-20λt，p1，t=-16e-20λt+16e-19λt，p2，t=112e-20λt-224e-19λt+112e-18λt，p3，t=-1 456/3e-20λt+1 456e-19λt-1 456e18λt+1 456e/3e-17λt， …。限于篇幅，這里不一一列舉。
證明 前面已經建立了子網EM3的狀態轉移方程，根據福克—普朗克方程式，可得以下方程組：
其中，pi，t是子網EM3處于狀態i下的穩態概率。因為可靠度Ri(t)=Ri-1(t)+pi，t，R0(t)=p0，t，所以可得到子網EM3在單工不可維修鏈路模式下的可靠度為R(t)=∑11i=0 pi，t。得證。
由于規模為m×n的E-2DMesh網絡EMm×n可被分成(m/3)×(n/3)個不相交的3-E-2DMesh子網，當每個子網EM3都保持連通時，根據設定可知，整個E-2DMesh網絡EMm×n也保持連通。依據定理１，可得規模為m×n的E-2DMesh網絡EMm×n的可靠度為(∑111i=0pi，t)m×n/9。根據可靠性手冊，取λ=3.509×10-6，由此可得不同規模下單工不可維修鏈路模式E-2DMesh網絡的可靠性。結果如圖４所示。其中虛線為３×３規模的E-2DMesh網絡可靠性對應于時間t的曲線；實線為12×12規模的E-2DMesh網絡可靠性對應于時間t的曲線。
1. 2 可維修鏈路可靠性模型
由于大規模并行計算機系統內部的通信鏈路都是冗余設計的，某些鏈路失效后對其進行維修是不影響系統正常運行的。從另一個角度來說，對失效鏈路進行維修，也增強了系統的可靠性。
對于單工鏈路組成的E-2DMesh網絡來說，某條鏈路的失效導致該鏈路不可用，對其進行維修后使得該鏈路可用。這里定義鏈路的維修強度θ=λ/α。其中：λ為鏈路的失效率；α為鏈路的維修率。注意到鏈路維修強度0≤θ＜1，否則系統將不能進入穩態。顯然，θ越小越好，當θ=0時，鏈路失效后立即就會被修復。
下面對單工可維修鏈路模式下子網EM3的狀態轉移情況進行討論并建立狀態轉移方程。
0→F：表示子網從初始狀態轉為失效狀態。根據定義１容易知道，只要圖２中左右兩邊４條單工鏈路中的任何一條失效，網絡進入不連通狀態，即失效。因此子網從０狀態轉移到Ｆ狀態的概率為e-4λΔt。
0→1：表示子網從初始狀態轉為有１條鏈路失效狀態，子網仍然保持連通。因為子網EM3中共有20條鏈路，除了能使網絡從初始狀態轉移到不連通狀態的４條鏈路外，剩余的16條鏈路中任意一條失效都能使子網從０狀態轉移到１狀態。所以狀態轉移概率為e-16λΔt。
0→0：因為０狀態只能轉移到１狀態和Ｆ狀態，所以子網保持初始狀態的概率為1-e-20λΔt。
F→0：由于單工鏈路可維修，只要對使狀態從０轉移到Ｆ的失效鏈路進行修復即可使網絡回復到初始狀態。狀態轉移概率為e-αΔt。
1→0：子網要從有１條鏈路失效狀態轉到初始狀態，只要對使子網從初始狀態轉移到１狀態的那條鏈路進行維修即可。此時的轉移概率為e-αΔt。
同樣的道理，可得子網EM3在可維修鏈路模式下的狀態轉移關系圖，如圖５所示。
根據圖５不難建立子網EM3在可維修鏈路模式下t+Δt時刻的狀態方程。
從上式不難得出子網在可維修鏈路模式下的穩態可靠性概率。
定理２ 在可維修鏈路模式下子網EM3的可靠性概率為
R(t)=∑11i=0 pi，t
證明類似于定理１，這里不再重復。
依據定理２，同樣可得m×n規模的E-2DMesh網絡在可維修鏈路模式下的可靠度為(∑11i=0pi，t)m×n/9。這里，不妨設鏈路維修強度θ=1/2，結果如圖６所示。其中虛線為３×３規模的E-2DMesh網絡可靠性對應于時間t的曲線；實線為12×12規模的E-2DMesh網絡可靠性對應于時間t的曲線。
2 不可維修和可維修鏈路模式下的可靠性分析
將不可維修和可維修鏈路兩種模式情況下的子網EM3可靠性進行對比，其關系如圖7所示。其中虛線為可維修鏈路模式下３×３規模的E-2DMesh網絡可靠性對應于時間t的曲線；實線為不可維修鏈路模式下3×3規模的E-2DMesh網絡可靠性對應于時間t的曲線。
從圖７可知，可維修鏈路模式的可靠性要大于不可維修鏈路模式的可靠性。這是因為鏈路可維修使得原來不可用的鏈路又可用，這就相當于減小了鏈路的失效率。需要說明的是，這里的網絡可靠性實際上是一個下界，其實際可靠性比下界更高。
3 結束語
本文主要基于子網的策略對單工不可維修鏈路模式和可維修鏈路模式的E-2DMesh網絡可靠性進行了研究，通過馬爾可夫鏈過程建立了子網的可靠性模型，利用組合模型原理得到整個網絡可靠性的一個下界。對這兩種模式的可靠性進行了比較。比較結果表明，隨著網絡規模的不斷擴大，兩種模式的可靠性都在不斷下降；在相同網絡規模時，可維修鏈路模式的可靠性要優于不可維修鏈路模式的可靠性。
參考文獻：
[1]CHEN Xiao．Fault-tolerance adaptive and shortest routing in 2D extended Meshes using faulty-block-information[C]//Proc of 2000 International Workshops on Parallel Processing. 2000:267-274．
[2]陳育斌，李建東，陳家模，等．計算通信網絡整體概率連通性的一種新算法[J]．通信學報，2000，21(9):91-96．
[3]劉愛民，劉有恒．關于可修復系統 的MTBF和MTTR[J]．電子學報，1998，26(1):70-72.
[4]HSU S J， YUANG M C. Efficient computation of marginal reliability-importance for reducible networks[J]. IEEE Trans on Reliability，2001，50(1):98-106.
[5]王衍，張彪，張友鵬，等．基于Markov model的容錯計算機聯鎖系統可靠性分析[J].電氣自動傳動化，2007，29(2):8-11.
[6]CHEN H L. Submesh determinination in faulty Tori and Meshes[J]. IEEE Trans on Parallel and Distributed Systems， 2001，12(3): 272-282.
