k元n方體網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性

馮 凱，李 婧

山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原030006

隨著并行計(jì)算機(jī)系統(tǒng)規(guī)模的不斷增大，系統(tǒng)功能的實(shí)現(xiàn)越來(lái)越依賴于系統(tǒng)元件之間支撐通信和數(shù)據(jù)交互的連接模式（即系統(tǒng)的互連網(wǎng)絡(luò)，其中的每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)處理器，每條邊對(duì)應(yīng)一對(duì)處理器之間的一條直接通信線路）。以具有優(yōu)良性能的互連網(wǎng)絡(luò)為底層拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)高性能并行計(jì)算機(jī)系統(tǒng)已經(jīng)成為高性能計(jì)算領(lǐng)域的一個(gè)發(fā)展趨勢(shì)[1]。人們往往選用具有遞歸結(jié)構(gòu)（即高維的網(wǎng)絡(luò)可以被劃分為一些獨(dú)立的低維的子網(wǎng)絡(luò)，并且這些子網(wǎng)絡(luò)與原網(wǎng)絡(luò)具有相同的拓?fù)湫再|(zhì)）的互連網(wǎng)絡(luò)來(lái)構(gòu)建并行計(jì)算機(jī)系統(tǒng)。一方面，這類網(wǎng)絡(luò)可以通過(guò)特定的機(jī)制指派各個(gè)子網(wǎng)絡(luò)完成用戶任務(wù)的不同部分，從而有效地利用系統(tǒng)資源；另一方面，這類網(wǎng)絡(luò)便于在原有基礎(chǔ)上進(jìn)行擴(kuò)容和升級(jí)，并且能夠保持原網(wǎng)絡(luò)的良好性能。當(dāng)基于遞歸互連網(wǎng)絡(luò)構(gòu)建的并行計(jì)算機(jī)系統(tǒng)中有故障發(fā)生時(shí)，系統(tǒng)互連網(wǎng)絡(luò)關(guān)于其子網(wǎng)絡(luò)的保持能力對(duì)系統(tǒng)實(shí)際應(yīng)用至關(guān)重要。在此背景下，遞歸互連網(wǎng)絡(luò)的子網(wǎng)絡(luò)可靠性得到了學(xué)者們的關(guān)注[2-5]。Abraham和Padmanabhan[2]對(duì)n維超立方體的子網(wǎng)絡(luò)可靠性進(jìn)行了研究，分別在不同故障模型下給出了子超立方體保持無(wú)故障狀態(tài)的平均失效時(shí)間的估計(jì)值。受此啟發(fā)，F(xiàn)itzgerald等[3]分別在不同故障模型下基于固定劃分模式得出了n維星圖網(wǎng)絡(luò)中不同數(shù)目的(n-1)維星圖子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)的平均失效時(shí)間，并基于靈活劃分模式對(duì)這一子網(wǎng)絡(luò)可靠性評(píng)估參數(shù)進(jìn)行了估算。最近，文獻(xiàn)[4]和文獻(xiàn)[5]分別對(duì)(n,k)-星圖網(wǎng)絡(luò)和DCell數(shù)據(jù)中心網(wǎng)絡(luò)中不同數(shù)目的某一規(guī)模子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)的平均失效時(shí)間也進(jìn)行了分析。

k元n方體網(wǎng)絡(luò)是一類著名遞歸互連網(wǎng)絡(luò)，諸多基于k元n方體網(wǎng)絡(luò)構(gòu)建的并行計(jì)算機(jī)系統(tǒng)已經(jīng)問(wèn)世，如Cray T3E[6]、IBM Blue Gene[7]等。近年來(lái)，k元n方體網(wǎng)絡(luò)的拓?fù)湫再|(zhì)得到了廣泛的研究[8-14]。針對(duì)k為奇數(shù)的k元n方體網(wǎng)絡(luò)，文獻(xiàn)[9]在點(diǎn)故障模型下研究了使得k元n方體網(wǎng)絡(luò)中不存在k元(n-m)方體子網(wǎng)絡(luò)(0≤m≤n-1)的最小的點(diǎn)故障數(shù)，并構(gòu)建出與任意規(guī)模子網(wǎng)絡(luò)一一對(duì)應(yīng)的符號(hào)化表示。隨后，文獻(xiàn)[13]基于概率故障模型給出了k為奇數(shù)的k元n方體網(wǎng)絡(luò)中存在k元(n-1)方體子網(wǎng)絡(luò)的概率估計(jì)，文獻(xiàn)[14]在點(diǎn)故障模型下分析了k為奇數(shù)的k元n方體網(wǎng)絡(luò)中不同數(shù)目的k元(n-1)方體子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)的平均失效時(shí)間。

在實(shí)際中，許多并行計(jì)算機(jī)系統(tǒng)可以利用故障診斷算法快速判斷出發(fā)生故障的處理器并及時(shí)進(jìn)行維修和更換，而處理器之間的通信線路可能由于物理?yè)p壞、電磁干擾、人為損壞等因素產(chǎn)生故障且無(wú)法得到及時(shí)修復(fù)（由于系統(tǒng)的處理器對(duì)之間大都不存在重復(fù)的直接通信線路，不同處理器對(duì)之間的通信線路通?？梢钥醋魇菦](méi)有關(guān)聯(lián)的）?；谶@一考慮，本文將在邊故障模型下（假定互連網(wǎng)絡(luò)中的頂點(diǎn)不會(huì)發(fā)生故障，各條邊發(fā)生故障是相互獨(dú)立的，且邊的故障率是不變的），對(duì)k為奇數(shù)的k元n方體網(wǎng)絡(luò)中不同數(shù)目的k元(n-1)方體子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)的平均失效時(shí)間進(jìn)行估計(jì)，這一研究可以幫助工程師更加全面地了解k元n方體網(wǎng)絡(luò)中不同數(shù)目的k元(n-1)方體子網(wǎng)絡(luò)存在性的保持能力。

1 基本概念與性質(zhì)

k元n方體（k≥2,n≥1為整數(shù)）記為，是一個(gè)具有kn個(gè)頂點(diǎn)的無(wú)向簡(jiǎn)單圖。的任一頂點(diǎn)可表示為u=u0u1…un-1，其中對(duì)于任意的整數(shù)i(0≤i≤n-1)均有ui∈{0,1,…,k-1}。兩個(gè)頂點(diǎn)u=u0u1…un-1和v=v0v1…vn-1相鄰當(dāng)且僅當(dāng)存在j∈{0,1,…,n-1}使得uj=vj±1(modk)且對(duì)于任意的l∈{0,1,…,n-1}{j}均有ul=vl,這樣的一條邊(u,v)稱為中的一條j維邊。容易得出，當(dāng)k≥3時(shí)共有nkn條邊，且j維邊的數(shù)目為kn，其中j∈{0,1,…,n-1}。

性質(zhì)1[9]中共有nk個(gè)不同的子網(wǎng)絡(luò)。

給定任一整數(shù)d∈{0,1,…,n-1}，可以將沿第d維劃分為k個(gè)不相交的子網(wǎng)絡(luò)其中Hd,i為中由點(diǎn)集導(dǎo)出的子圖，這里i∈{0,1,…,k-1}。結(jié)合性質(zhì)1可知，當(dāng)k≥3為奇數(shù)時(shí)，中所有不同的子網(wǎng)絡(luò)恰好是由沿不同維劃分得出的。在無(wú)特殊說(shuō)明的情況下，假定下文中出現(xiàn)的均滿足k≥3為奇數(shù)。

在介紹主要結(jié)果之前，先引入一些基本概念和標(biāo)記（見(jiàn)表1）。對(duì)于文中其他未加定義而被使用的圖論術(shù)語(yǔ)和記號(hào)參見(jiàn)文獻(xiàn)[15]。

表1 主要符號(hào)及含義Table 1 Main symbols and meanings

2 主要結(jié)果

2.1 固定劃分模式下Ti的計(jì)算

選定d∈{0,1,…,n-1}，可以將沿第d維劃分為k個(gè)不相交的子網(wǎng)絡(luò)基于這一固定劃分模式，下面通過(guò)計(jì)算Ti來(lái)評(píng)估中不相交的子網(wǎng)絡(luò)的可靠性。

由R*(t)和T*的定義可知，中所有故障邊均位于i個(gè)子網(wǎng)絡(luò)中時(shí)中顯然有k-i個(gè)子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)，故對(duì)于任意的0≤i≤k-1有

因此，為了計(jì)算固定劃分模式下T*和Ti(0≤i≤k-1)的值，首先需要厘清S*,S0,S1,…,Sk之間的狀態(tài)轉(zhuǎn)換關(guān)系。

基于上述分析可知，當(dāng)t=0時(shí)，P*(0)=1且對(duì)于任意的0≤l≤k有Pl(0)=0；當(dāng)t=∞時(shí)，P*(∞)=0,Pk(∞)=1且對(duì)于任意的0≤l≤k-1有Pl(∞)=0；P*(t)，P0(t)，P1(t),…,Pk(t)之間的相互關(guān)系可表示為：

其中2≤i≤k。

進(jìn)一步地，有如下結(jié)論成立。

證明由r0)dt。結(jié)合P*(0)=1求解可得從 而 可 知，

注意到

由P0(0)=0可知：

令r=nknλ，則P*(t)=e-rt。對(duì)P*(t)=e-rt做拉普拉斯變換可知：

定理1證畢。

例1選取k∈{5,7}，n∈{4,5}。在固定劃分模式下，不同規(guī)模的的Ti的值如表2所示，其中中邊的故障率為λ=10-7/h。

表2 固定劃分模式下的Ti的值Table 2 Values of Ti in under fixed partition pattern

表2 固定劃分模式下的Ti的值Table 2 Values of Ti in under fixed partition pattern

?

2.2 靈活劃分模式下Ti的計(jì)算

注意到，對(duì)于任意的d∈{0,1,…,n-1}，可以將沿第d維劃分為k個(gè)子網(wǎng)絡(luò)。若首條故障邊為l維邊，那么將沿第l維進(jìn)行劃分（稱這種劃分模式為靈活劃分模式），這樣得到的k個(gè)子網(wǎng)絡(luò)均不會(huì)被首條故障邊所破壞。這意味著，在靈活劃分模式下，若處于狀態(tài)S*，首條故障邊不會(huì)導(dǎo)致?tīng)顟B(tài)S*轉(zhuǎn)換為狀態(tài)S1。本節(jié)將證明靈活劃分模式下Ti的值相比固定劃分模式下這一參數(shù)的值有所增加。為了區(qū)分不同劃分模式下Ti的計(jì)算公式，記靈活劃分模式下Ti的值為

令w*=nknλ,wi=(k-i)(n-1)kn-1λ(0≤i≤k)。此時(shí)S*,S0,S1,…,Sk的狀態(tài)轉(zhuǎn)換圖如圖2所示。

圖2 靈活劃分模式下S*,S0,S1,…,Sk的狀態(tài)轉(zhuǎn)換圖Fig.2 State transition diagram of S*,S0,S1,…,Sk under flexible partition pattern

基于上述分析可知，當(dāng)t=0時(shí)，P*(0)=1且對(duì)于任意 的0≤l≤k有Pl(0)=0；當(dāng)t=∞時(shí)，P*(∞)=0，Pk(∞)=1且對(duì)于任意的0≤l≤k-1有Pl(∞)=0；P*(t),P0(t),P1(t),…,Pk(t)之間的相互關(guān)系可表示為：

其中1≤i≤k。

采用類似于定理1的證明，可得出以下結(jié)論。

可以看出，相比固定劃分模式，靈活劃分模式下S*,S0,S1,…,Sk之間的狀態(tài)轉(zhuǎn)換關(guān)系發(fā)生了改變，這導(dǎo)致不同劃分模式下得出的不同數(shù)目的Qkn-1子網(wǎng)絡(luò)保持無(wú)故障狀態(tài)的平均失效時(shí)間的計(jì)算公式是不同的。

例2選取k∈{5,7}，n∈{4,5}。在靈活劃分模式下，不同規(guī)模的的值如表3所示，其中中邊的故障率為λ=10-7/h。

表3 靈活劃分模式下的值Table 3 Values of under flexible partition pattern

表3 靈活劃分模式下的值Table 3 Values of under flexible partition pattern

?

3 仿真分析

為了驗(yàn)證不同劃分模式下理論結(jié)果的精確性，本文采用蒙特卡洛仿真來(lái)評(píng)估邊故障模型下中不相交的子網(wǎng)絡(luò)的可靠性。選取不同規(guī)模的n∈{4,5})為實(shí)驗(yàn)對(duì)象。假定中邊的可靠性是獨(dú)立同分布的，且均服從故障率為λ(λ=10-7/h)的指數(shù)分布。在任意時(shí)刻t，中邊的可靠性為p(t)=e-λt。令f(t)為t時(shí)刻中故障邊的數(shù)目。由于可以看作是p(t)的估計(jì)值，f(t)可取為

注意到，對(duì)于任意的d∈{0,1,…,n-1}，可以將沿第d維劃分為k個(gè)子網(wǎng)絡(luò)Hd,0,Hd,1,…,Hd,k-1。若邊(u0u1…un-1,v0v1…vn-1)是d維邊，則該邊發(fā)生故障不會(huì)破壞Hd,0,Hd,1,…,Hd,k-1中任何一個(gè)子網(wǎng)絡(luò)；若邊(u0u1…un-1,v0v1…vn-1)不是d維邊，則該邊發(fā)生故障會(huì)破壞子網(wǎng)絡(luò)Hd,ud。

在固定劃分模式下，選定d*∈{0,1,…,n-1}，將沿第d*維進(jìn)行劃分。在靈活劃分模式下，若首條故障邊為l維邊，則將沿第l維進(jìn)行劃分。在任意時(shí)刻t，通過(guò)隨機(jī)生成10 000次故障邊集（每次生成的故障邊集的邊數(shù)為f(t)）對(duì)這一時(shí)刻在不同劃分模式下發(fā)生故障的子網(wǎng)絡(luò)的平均個(gè)數(shù)分別進(jìn)行仿真計(jì)算，并與例1和例2計(jì)算出的理論結(jié)果進(jìn)行對(duì)比，具體結(jié)果如圖3和圖4所示。

圖3 固定劃分模式下子網(wǎng)絡(luò)可靠性分析結(jié)果Fig.3 Analysis results of subnetwork reliability in under fixed partition pattern

4 結(jié)束語(yǔ)