e-ddlesh網(wǎng)絡(luò)中單工失效鏈路模式的研究

e-ddlesh網(wǎng)絡(luò)中單工失效鏈路模式的研究

0研究網(wǎng)絡(luò)可靠性隨著計(jì)算機(jī)技術(shù)的發(fā)展，大規(guī)模多處理器并行網(wǎng)絡(luò)系統(tǒng)在多個(gè)領(lǐng)域得到了廣泛應(yīng)用。越來(lái)越多的重要部門(mén),如通信、金融、國(guó)防、工業(yè)控制等對(duì)大型并行計(jì)算機(jī)系統(tǒng)產(chǎn)生了很強(qiáng)的依賴(lài)性,這些系統(tǒng)的計(jì)算機(jī)一旦發(fā)生故障,將帶來(lái)不可估量的損失。以E-2DMesh網(wǎng)絡(luò)為拓?fù)浣Y(jié)構(gòu)的新型并行計(jì)算機(jī)系統(tǒng),因其結(jié)構(gòu)簡(jiǎn)單、規(guī)則、可擴(kuò)展且易于VLSI實(shí)現(xiàn)等優(yōu)點(diǎn)而成為許多大型多處理器并行計(jì)算機(jī)系統(tǒng)所采用的拓?fù)浣Y(jié)構(gòu)。因此,對(duì)其可靠性進(jìn)行研究具有重要的實(shí)際價(jià)值。目前大多數(shù)文獻(xiàn)在研究通信網(wǎng)絡(luò)可靠性時(shí),一般均假設(shè)失效鏈路不可維修,只有少量的文獻(xiàn)涉及到鏈路可維修的情況。而在實(shí)際的通信系統(tǒng)中,通信線鏈路是冗余設(shè)計(jì)的,也就是說(shuō)存在鏈路失效時(shí)對(duì)其進(jìn)行維修是不影響系統(tǒng)通信的。因此,對(duì)可維修鏈路的大規(guī)模并行計(jì)算機(jī)系統(tǒng)進(jìn)行研究更具有現(xiàn)實(shí)意義?，F(xiàn)有的方法在研究具有失效鏈路的通信系統(tǒng)可靠性時(shí),大多是通過(guò)研究終端對(duì)的可靠性來(lái)評(píng)價(jià)整個(gè)系統(tǒng)的可靠性,這種方法不能實(shí)地反映整個(gè)系統(tǒng)的可靠性,缺乏靈活性。有的方法如馬爾可夫鏈模型運(yùn)算量比較大,只能分析中小型規(guī)模網(wǎng)絡(luò)。Menezes等人使用組合模型方法研究了多級(jí)網(wǎng)絡(luò)的可靠性,但是他們沒(méi)有考慮鏈路可修復(fù)的情況且缺乏嚴(yán)格的數(shù)學(xué)論證,使人們?cè)趯?shí)際使用時(shí)對(duì)其可靠性仍然沒(méi)有足夠的把握?；谏鲜鲈?本文設(shè)定從網(wǎng)絡(luò)中任意節(jié)點(diǎn)到其他所有節(jié)點(diǎn)至少存在一條路徑的概率來(lái)度量E-2DMesh網(wǎng)絡(luò)的可靠性,通過(guò)組合模型與馬爾可夫鏈模型相結(jié)合的方法對(duì)單工可維修鏈路的E-2DMesh網(wǎng)絡(luò)可靠性進(jìn)行定量分析。這是第一次對(duì)單工可維修鏈路的E-2DMesh網(wǎng)絡(luò)可靠性給出嚴(yán)格的數(shù)學(xué)推導(dǎo)。1網(wǎng)絡(luò)emmn本文首先研究k-E-2DMesh子網(wǎng)的可靠性模型(為簡(jiǎn)單起見(jiàn),令k=3),然后給出整個(gè)具有單工可維修鏈路的E-2DMesh網(wǎng)絡(luò)的可靠性模型。由于節(jié)點(diǎn)的可靠性通常大于鏈路的可靠性,本文只考慮鏈路失效而不考慮節(jié)點(diǎn)失效的情況,并假定所有鏈路具有相同的失效率λ和維修率α。一個(gè)規(guī)模為m×n的E-2DMesh網(wǎng)絡(luò)EMm×n,可以被分成(m/k)×(n/k)個(gè)不相交的k-E-2DMesh子網(wǎng),整個(gè)E-2DMesh網(wǎng)絡(luò)EMm×n被分成m/k行和n/k列,每一行上有n/k個(gè)子網(wǎng),每一列上有m/k個(gè)子網(wǎng)。圖1給出了6×6的E-2DMesh網(wǎng)絡(luò)EM6×6被劃分為四個(gè)3×3的3-E-2DMesh子網(wǎng)的情形及其鏈路方向。1.1失效狀態(tài)的轉(zhuǎn)換令EMk是一規(guī)模為k×k的E-2DMesh網(wǎng)絡(luò),為簡(jiǎn)單起見(jiàn),本文以規(guī)模為3×3的3-E-2DMesh子網(wǎng)為例來(lái)介紹子網(wǎng)可靠性模型的建立和分析。包含9個(gè)節(jié)點(diǎn),20條鏈路,由單工鏈路組成的子網(wǎng)EM3如圖2所示。假定鏈路失效服從指數(shù)分布,網(wǎng)絡(luò)正常工作時(shí)的鏈路失效率和維修率均為λ和α。失效不可維修鏈路對(duì)應(yīng)的馬爾可夫狀態(tài)轉(zhuǎn)換圖如圖3所示。在圖2中,假定所有虛線表示的單工鏈路均為有效鏈路,實(shí)線表示的單工鏈路具有失效性。定義1由于鏈路失效,在實(shí)線表示的單工鏈路部分,除節(jié)點(diǎn)sk不能接收消息和節(jié)點(diǎn)dk不能發(fā)送消息外,子網(wǎng)EMk中如果存在一個(gè)節(jié)點(diǎn)不能發(fā)送或者接收消息時(shí),網(wǎng)絡(luò)即不連通(網(wǎng)絡(luò)失效)。圖3中,狀態(tài)i(i=0,1,2,…,11)表示i條單工鏈路失效后,子網(wǎng)仍然保持連通狀態(tài)。0表示子網(wǎng)的初始狀態(tài),沒(méi)有鏈路失效;F表示網(wǎng)絡(luò)處于不連通狀態(tài),即網(wǎng)絡(luò)失效。箭頭上的數(shù)字表示在Δt時(shí)間內(nèi)狀態(tài)間的轉(zhuǎn)移概率。在不可維修的EM3子網(wǎng)中,若在失效的i條單工鏈路外又有鏈路失效,那么該失效鏈路的生成導(dǎo)致?tīng)顟B(tài)從i向j(j=i,i+1,i+2,…,11,F)轉(zhuǎn)移。以下對(duì)已失效鏈路外一條單工鏈路的失效導(dǎo)致各狀態(tài)轉(zhuǎn)移的情況進(jìn)行討論。0→F:表示子網(wǎng)從初始狀態(tài)轉(zhuǎn)為失效狀態(tài)。根據(jù)定義1容易知道,只要圖2中左右兩邊4條單工鏈路中的任何一條失效,網(wǎng)絡(luò)即進(jìn)入不連通狀態(tài),即失效。所以子網(wǎng)從0狀態(tài)轉(zhuǎn)移到F狀態(tài)的概率為e-4λΔt。0→1:表示子網(wǎng)從初始狀態(tài)轉(zhuǎn)為有1條鏈路失效狀態(tài),子網(wǎng)仍然保持連通。因?yàn)樽泳W(wǎng)EM3中共有20條鏈路,除了能使網(wǎng)絡(luò)從初始狀態(tài)轉(zhuǎn)移到不連通狀態(tài)的4條鏈路外,剩余的16條鏈路中任意一條失效都能使子網(wǎng)從0狀態(tài)轉(zhuǎn)移到1狀態(tài)。所以狀態(tài)轉(zhuǎn)移概率為e-16λΔt。0→0:因?yàn)?狀態(tài)只能轉(zhuǎn)移到1狀態(tài)和F狀態(tài),所以子網(wǎng)保持初始狀態(tài)的概率為1-e-20λΔt。同理,可以得出i→j(i=1,2,…,11;j=i,i+1,…,11,F)的狀態(tài)轉(zhuǎn)移概率,結(jié)果如圖3所示。為了分析子網(wǎng)的可靠度R(t),引入時(shí)間的概念進(jìn)行分析并建立子網(wǎng)的狀態(tài)轉(zhuǎn)移方程。1tt專(zhuān)業(yè)定義EM3處于初始狀態(tài),在此狀態(tài)下的概率為p0,t;處于狀態(tài)i(i=1,2,…,11)下,EM3仍然保持連通的概率為pi,t、EM3處于F狀態(tài)下的概率為pF,t。2p2p,2e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e,3e(1)在初始狀態(tài)下,子網(wǎng)EM3只有從t時(shí)刻開(kāi)始Δt時(shí)間內(nèi)沒(méi)有故障鏈路出現(xiàn),子網(wǎng)才能維持其狀態(tài),因此概率為p0,t+Δt=p0,t(1-20λΔt)+o(Δt)。(2)子網(wǎng)EM3處于狀態(tài)1下有兩種情況:①T=t時(shí)子網(wǎng)處于狀態(tài)1下,Δt后仍處于狀態(tài)1下,此時(shí)的概率為P1,t(1-19λΔt)+o(Δt);②T=t時(shí)子網(wǎng)處于狀態(tài)0下,Δt后轉(zhuǎn)移到狀態(tài)1下,此狀態(tài)轉(zhuǎn)移概率為p0,t16λΔt+o(Δt)。故在T=t+Δt時(shí)刻,系統(tǒng)處于狀態(tài)1下的概率為p1,t+Δt=p0,t16λΔt+p1,t(1-19λΔt)+o(Δt)相同的方法,可得到系統(tǒng)在T=t+Δt時(shí)刻處于狀態(tài)j(j=2,3,…,11,F)下的概率分別為定義可靠度Ri(t)(0≤i≤11)為系統(tǒng)到時(shí)刻t有i條鏈路失效仍保持連通的概率。因此,根據(jù)上式可求得子網(wǎng)EM3的可靠度。定理1在單工不可維修鏈路模式下,假設(shè)子網(wǎng)EM3中每條鏈路具有獨(dú)立的失效概率λ,則子網(wǎng)EM3的可靠度為R(t)=11∑i=0pi,tR(t)=∑i=011pi,t其中: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=-1456/3e-20λt+1456e-19λt-1456e18λt+1456e/3e-17λt,…。限于篇幅,這里不一一列舉。證明前面已經(jīng)建立了子網(wǎng)EM3的狀態(tài)轉(zhuǎn)移方程,根據(jù)?？恕绽士朔匠淌?可得以下方程組:{dp0,t/dt=-20λp0,tdp1,t/dt=-19λp1,t+16λp0,tdp2,t/dt=-18λp2,t+14λp1,tdp3,t/dt=-17λp3,t+13λp2,tdp4,t/dt=-16λp4,t+11λp3,tdp5,t/dt=-15λp5,t+9λp4,tdp6,t/dt=-14λp6,t+8λp5,tdp7,t/dt=-13λp7,t+7λp6,tdp8,t/dt=-12λp8,t+5λp7,tdp9,t/dt=-11λp9,t+4λp8,tdp10,t/dt=-10λp10,t+3λp9,tdp11,t/dt=-9λp11,t+2λp10,tdpF,t/dt=4λp0,t+5λp1,t+5λp2,t+6λp3,t+7λp4,t+7λp5,t+7λp6,t+8λp7,t+8λp8,t+8λp9,t+8λp10,t+9λp11,t???????????????????????????????????????????????????????????????????dp0,t/dt=?20λp0,tdp1,t/dt=?19λp1,t+16λp0,tdp2,t/dt=?18λp2,t+14λp1,tdp3,t/dt=?17λp3,t+13λp2,tdp4,t/dt=?16λp4,t+11λp3,tdp5,t/dt=?15λp5,t+9λp4,tdp6,t/dt=?14λp6,t+8λp5,tdp7,t/dt=?13λp7,t+7λp6,tdp8,t/dt=?12λp8,t+5λp7,tdp9,t/dt=?11λp9,t+4λp8,tdp10,t/dt=?10λp10,t+3λp9,tdp11,t/dt=?9λp11,t+2λp10,tdpF,t/dt=4λp0,t+5λp1,t+5λp2,t+6λp3,t+7λp4,t+7λp5,t+7λp6,t+8λp7,t+8λp8,t+8λp9,t+8λp10,t+9λp11,t初始條件為p0,0=1,pi,0=0(i=1,…,11,F)。求得此微分方程組的解為pi,t(0≤i≤11)。其中,pi,t是子網(wǎng)EM3處于狀態(tài)i下的穩(wěn)態(tài)概率。因?yàn)榭煽慷萊i(t)=Ri-1(t)+pi,t,R0(t)=p0,t,所以可得到子網(wǎng)EM3在單工不可維修鏈路模式下的可靠度為R(t)=11∑i=0pi,tR(t)=∑i=011pi,t。得證。由于規(guī)模為m×n的E-2DMesh網(wǎng)絡(luò)EMm×n可被分成(m/3)×(n/3)個(gè)不相交的3-E-2DMesh子網(wǎng),當(dāng)每個(gè)子網(wǎng)EM3都保持連通時(shí),根據(jù)設(shè)定可知,整個(gè)E-2DMesh網(wǎng)絡(luò)EMm×n也保持連通。依據(jù)定理1,可得規(guī)模為m×n的E-2DMesh網(wǎng)絡(luò)EMm×n的可靠度為(111∑i=0pi,t)m×n/9。根據(jù)可靠性手冊(cè),取λ=3.509×10-6,由此可得不同規(guī)模下單工不可維修鏈路模式E-2DMesh網(wǎng)絡(luò)的可靠性。結(jié)果如圖4所示。其中虛線為3×3規(guī)模的E-2DMesh網(wǎng)絡(luò)可靠性對(duì)應(yīng)于時(shí)間t的曲線;實(shí)線為12×12規(guī)模的E-2DMesh網(wǎng)絡(luò)可靠性對(duì)應(yīng)于時(shí)間t的曲線。1.2e-2dmeh網(wǎng)絡(luò)在不同鏈路模式下的可靠度由于大規(guī)模并行計(jì)算機(jī)系統(tǒng)內(nèi)部的通信鏈路都是冗余設(shè)計(jì)的,某些鏈路失效后對(duì)其進(jìn)行維修是不影響系統(tǒng)正常運(yùn)行的。從另一個(gè)角度來(lái)說(shuō),對(duì)失效鏈路進(jìn)行維修,也增強(qiáng)了系統(tǒng)的可靠性。對(duì)于單工鏈路組成的E-2DMesh網(wǎng)絡(luò)來(lái)說(shuō),某條鏈路的失效導(dǎo)致該鏈路不可用,對(duì)其進(jìn)行維修后使得該鏈路可用。這里定義鏈路的維修強(qiáng)度θ=λ/α。其中:λ為鏈路的失效率;α為鏈路的維修率。注意到鏈路維修強(qiáng)度0≤θ<1,否則系統(tǒng)將不能進(jìn)入穩(wěn)態(tài)。顯然,θ越小越好,當(dāng)θ=0時(shí),鏈路失效后立即就會(huì)被修復(fù)。下面對(duì)單工可維修鏈路模式下子網(wǎng)EM3的狀態(tài)轉(zhuǎn)移情況進(jìn)行討論并建立狀態(tài)轉(zhuǎn)移方程。0→F:表示子網(wǎng)從初始狀態(tài)轉(zhuǎn)為失效狀態(tài)。根據(jù)定義1容易知道,只要圖2中左右兩邊4條單工鏈路中的任何一條失效,網(wǎng)絡(luò)進(jìn)入不連通狀態(tài),即失效。因此子網(wǎng)從0狀態(tài)轉(zhuǎn)移到F狀態(tài)的概率為e-4λΔt。0→1:表示子網(wǎng)從初始狀態(tài)轉(zhuǎn)為有1條鏈路失效狀態(tài),子網(wǎng)仍然保持連通。因?yàn)樽泳W(wǎng)EM3中共有20條鏈路,除了能使網(wǎng)絡(luò)從初始狀態(tài)轉(zhuǎn)移到不連通狀態(tài)的4條鏈路外,剩余的16條鏈路中任意一條失效都能使子網(wǎng)從0狀態(tài)轉(zhuǎn)移到1狀態(tài)。所以狀態(tài)轉(zhuǎn)移概率為e-16λΔt。0→0:因?yàn)?狀態(tài)只能轉(zhuǎn)移到1狀態(tài)和F狀態(tài),所以子網(wǎng)保持初始狀態(tài)的概率為1-e-20λΔt。F→0:由于單工鏈路可維修,只要對(duì)使?fàn)顟B(tài)從0轉(zhuǎn)移到F的失效鏈路進(jìn)行修復(fù)即可使網(wǎng)絡(luò)回復(fù)到初始狀態(tài)。狀態(tài)轉(zhuǎn)移概率為e-αΔt。1→0:子網(wǎng)要從有1條鏈路失效狀態(tài)轉(zhuǎn)到初始狀態(tài),只要對(duì)使子網(wǎng)從初始狀態(tài)轉(zhuǎn)移到1狀態(tài)的那條鏈路進(jìn)行維修即可。此時(shí)的轉(zhuǎn)移概率為e-αΔt。同樣的道理,可得子網(wǎng)EM3在可維修鏈路模式下的狀態(tài)轉(zhuǎn)移關(guān)系圖,如圖5所示。根據(jù)圖5不難建立子網(wǎng)EM3在可維修鏈路模式下t+Δt時(shí)刻的狀態(tài)方程。從上式不難得出子網(wǎng)在可維修鏈路模式下的穩(wěn)態(tài)可靠性概率。定理2在可維修鏈路模式下子網(wǎng)EM3的可靠性概率為R(t)=11∑i=0pi,t證明類(lèi)似于定理1,這里不再重復(fù)。依據(jù)定理2,同樣可得m×n規(guī)模的E-2DMesh網(wǎng)絡(luò)在可維修鏈路模式下的可靠度為(11∑i=0pi,t)m×n/9。這里,不妨設(shè)鏈路維修強(qiáng)度θ=1/2,結(jié)果如圖6所示。其中虛線為3×3規(guī)模的E-2DMesh網(wǎng)絡(luò)可靠性對(duì)應(yīng)于時(shí)間t的曲線;實(shí)線為12×12規(guī)模的E-2DMesh網(wǎng)絡(luò)可靠性對(duì)應(yīng)于時(shí)間t的曲線。2網(wǎng)絡(luò)可靠性分析將不可維修和可維修鏈路兩種模式情況下的子網(wǎng)EM3可靠性進(jìn)行對(duì)比,其關(guān)系如圖7所示。其中虛線為可維修鏈路模式下3×3規(guī)模的E-2DMesh網(wǎng)絡(luò)可靠性對(duì)應(yīng)于時(shí)間t的曲線;實(shí)線為不可維修鏈路模式下3×3規(guī)模的E-2DMesh網(wǎng)絡(luò)可靠性對(duì)應(yīng)于時(shí)間t的曲線。從圖7可知,可維修鏈路模式的可靠性要大于不可維修鏈路模式的可靠性。這