超立方體網絡下的自適應容錯路由研究

摘 要:針對超立方體結構的多處理機系統出現故障的問題，對容錯超立方體網絡的局部連通性進行了研究。根據局部連通性的特點定義了相鄰節點集合類的概念，提出并證明了求解兩類相鄰節點集合的公式。給出了滿足任意子連通性條件的超立方體網絡的自適應容錯路由算法。該算法是分布式和基于局部信息的，可以預防死鎖。仿真實驗的結果表明算法是高效的，且構建的路徑長度接近于最優路徑長度。

關鍵詞:超立方體網絡;容錯路由算法;局部連通性

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

文章編號:1001-3695(2010)03-1151-03

doi:10.3969/j.issn.1001-3695.2010.03.096

Research of adaptive fault tolerant routing algorithm in hypercube networks

WENG Yi，LIANG Jia-rong，HUA Ren-jie

(School of Computer， Electronics Information， Guangxi University， Nanning 530004， China)

Abstract:In order to deal with the fault possibility of computers and links in hypercube multi-computer system，this paper studied local connectivity of fault tolerant hypercube networks.The concept of the neighbor sets of present node had been defined in accordance with the characteristics of local connectivity. The formula which could solve two kinds of sets of neighbor nodes was proposed and proved.This paper developed an adaptive fault tolerant routing algorithm for arbitrary subcube-connected hypercube networks.This algorithm was distributed and based on local information， and it could prevent deadlock.Simulation results show that this algorithm is efficient and the length of the routing path constructed by this algorithm is close to the optimal length.

Key words:hypercube network; fault tolerant routing algorithm; local connectivity

0 引言

隨著超立方體結構的多處理機系統商業運用的成功[1]，人們對超立方網絡的拓撲結構和通信能力進行了大量的研究工作。超立方體網絡具有高對稱性、強層次結構和最大容錯性的特點[2]，但是這些特點傳統的容錯性度量方法卻不能完全顯示出來。例如，超立方體網絡Hn去掉任意k個節點和相應邊后要保持連通，必須有k≤n-1。這種特殊情況使超立方體網絡的容錯性被極大地低估了。因為在實際應用中，超立方體網絡Hn的某個節點的所有n個鄰節點同時失效的概率是極小的。因此，人們試圖引入更能有效度量網絡實際能力的定義。文獻[3]提出了forbidden faulty set概念的網絡容錯模型，該模型是指網絡中的一些節點或邊不可能同時出錯以避免上述情況的發生。作為這種模型的一種特殊情況，文獻[4]提出了k-safe容錯模型，即每一個正確節點至少有k個正確的鄰節點。文獻[5]提出了subcube partitioning(子立方體劃分)的方法，利用該方法使人們可以從局部入手來研究超立方體網絡的整體容錯性。文獻[6]提出了局部連通性的概念，滿足此概念條件的超立方體網絡可包含任意接近50%的錯誤節點而仍保持正確節點的連通性。文獻[7]對文獻[6]中的局部連通性的概念進行了擴展，進一步提出了子連通性的概念，其目的是在滿足概念條件的超立方體網絡的故障節點數任意大于整個立方體網絡的節點總數的一半時，仍然能夠保證整個立方體網絡的全局連通性。本文根據子連通性這一特點提出了相鄰節點集合類的概念，并依據概念給出了一種路由算法。由于算法結合了子連通性概念的特點，能保證路由的高效性和正確性:對符合子連通性條件的超立方體網絡必然可以在相鄰k維子立方體中構造一條連通可達節點的正確路徑，進而找到連通源節點與目標節點的正確路由。在超立方體網絡的子立方體中尋徑可以有效降低路由算法的時間復雜度，從而降低系統開銷。

1 超立方體網絡的相關定義

1.1 基本定義

定義1 n維超立方體網絡Hn是具有下述性質的一種網絡拓撲結構:a)它由2n個節點和n×2n-1條邊構成;b)每一個節點可由一個不相同的n位二進制串表示;c)當且僅當Hn中兩個節點的二進制串恰有一位不同時，兩個節點是相鄰的，即這兩個節點之間有一條邊相連。

定義2 n維超立方體網絡的n維二進制串中長度為n-k的二進制串對應于超立方體網絡中的一個具有2k個節點和k×2k-1條邊的k維子立方體Hk。在n維超立方體網絡Hn中，所有的k維子立方體Hk都是同構的。

定義3 如果n維超立方體網絡Hn中每個k維子立方體Hk中所有可達節點構成一個連通圖且Hk中至少存在兩個可達節點，則稱Hn為k維子連通的。

定義4 如果n維超立方體網絡Hn對任意一個k維子立方體Hk，存在一個包含Hk的h維子立方體Hh，且Hh是h維子連通的，則稱Hn為任意子連通的。

1.2 超立方體網絡的連通性與相鄰節點集合類

定理1 滿足k維子連通條件的n維超立方體網絡Hn中所有可達節點構成一個連通圖[7]。

推論1 若n維超立方體網絡Hn滿足k維子連通條件，則Hn的任意h維子立方體Hh(h≥k)的所有可達節點構成一個連通圖[7]。

定理2 滿足任意子連通條件的n維超立方體網絡Hn中所有可達節點構成一個連通圖[7]。

定義5 若n-cube中任一節點vj，在給定限維k內與vi僅一個元素相異，保持其他限維與vi對應位置不變，則稱vj為相鄰蘊涵節點，相鄰蘊涵節點的子集合記為Vj*。

定義6 若n-cube中任一節點vj保持限維k內對應位置全不變，而在其他限維中僅一個元素相異，則稱vj為相鄰擴展節點，相鄰擴展節點的子集合記為Vj**。

定理3 n維超立方體網絡Hn中的任意節點vi在給定限維k(k≤n)的k維子立方體Hk中的所有鄰接點組成集合Vj*，且

Vj*=∪i∈k(xi(2i)+0j=n-1，i≠jxj(2j))

證明 由定義1和2可知，vi在Hk中的鄰接點vj是通過改變vi的限維k中的某一位xi得到的。不妨設

vi=∪2n-1i=0xi=∪i(xn-1…xi+1xixi-1…x1x0)

vj=∪2n-1i=0xi=∪i(xn-1…xi+1xixi-1…x1x0)

對vi和vj進行布爾運算分兩種情況討論。

1)當xi=0時可得

Vj*=∪2n-1j=0，i∈k(vi，vj)=∪(xn-1∪xn-1，…，xi+1∪xi+1，xi∪xi，xi-1∪xi-1，…，x1∪x1，x0∪x0)=∪ (xn-1，…，xi+1，xi，xi-1，…，x1，x0)

其中:xi∪xi=xi為vi的相鄰蘊涵節點子集可加元素，說明應該加上這一項。所以

Vj*=∪i∈k(xi(2i)+0j=n-1xj(2j))

2)當xi=1時可得

Vj*=∪2n-1j=0，i∈k(vi⊙vj)=∪(xn-1⊙xn-1，…，xi+1⊙xi+1，xi⊙xi，xi-1⊙xi-1，…，x1⊙x1，x0⊙x0)=∪(xn-1，…，xi+1，0，xi-1，…，x1，x0)

其中:xi⊙xi=0說明xi是vi的相鄰蘊涵節點子集可去元素，應該消去這一項。所以

Vj*=∪i∈k((0j=n-1xj(2j))-xi×(2i)+xi×(2i))

由1)2)可得

Vj*=∪i∈k(xi(2i)+0j=n-1，i≠jxj(2j))

定理4 在n維超立方體網絡Hn中的任意節點vi在給定限維k(k≤n)后與相鄰k維子立方體的所有鄰接點組成集合Vj**，且

Vj**=∪i∈n-k(xi(2i)+0j=n-1，i≠jxj(2j))

證明過程與定理3的證明類似，只要把xi的限維改到n-k后即可。

推論2 滿足k維子連通條件的n維超立方體網絡Hn中的任意h(k≤h

證明 可用反證法來證明。若滿足k維子連通條件的n維超立方體網絡Hn中的某k維子立方體Hk的所有節點的Vj**都為空，則根據定理4有Hk中的節點與所有Hk以外的節點都不連通，這與定理1相違背。再由推論1可知，Hh也存在使Vj**不為空的節點。

推論3 滿足任意子連通條件的n維超立方體網絡Hn中的任意可達非端節點vj的Vj*∪Vj**中至少存在兩個元素。

證明 由定理2可知Hn中所有可達節點構成一個連通圖，則所有可達非端節點都存在至少兩個鄰接點，由定理3和4可知Vj*∪Vj**至少有兩個元素。

2 任意子連通超立方體網絡的路由算法

從定理1和推論2可看出，要在滿足k維子連通條件的n維超立方體網絡Hn中找到一條從起點A到終點B的正確路徑，其基本思想就是:如果A與B屬于同一個k維子立方體Hk，只需在Hk內部路由即可;如果A與B不屬于同一個k維子立方體Hk，只要通過在Hk中尋找一個Vj**不為空的節點vi，連通vi和Vj**中的某節點來逐步改變A與B的二進制串的不同位，最終使得A與B屬于同一個k維子立方體Hk即可。

根據推論3，在尋徑過程中可以排除Vj*∪Vj**只有一個元素的可達節點。在需要回朔時為了避免死鎖，可在當前節點的Vj*或Vj**中給它的前驅節點加一個標志位，且按照一定的順序在Vj*和Vj**中尋找后續節點即可。為了把算法推廣到任意子連通的n維超立方體網絡Hn，可以先假設一個k(k≤n)值(存在大量錯誤節點可采用較大的k值)，在無法找到從A到B的正確路由時增加k值即可。如果在k>n時仍不能找到，則說明從A到B是不可達的。

算法:任意子連通的n維超立方體中的路由算法

輸入:具有錯誤節點的n維超立方體網絡Hn和該網絡中的兩個正確節點A和B。

輸出:Hn中連接A和B的正確節點組成的路徑。

1 A←a1…an，B←b1…bn(取A、B的二進制串)

2 初始化路徑P:P←A

3 初始化帶標志位的當前節點C:C←A

4 輸入選定的k(k維子連通)

5 for(i=k i≤n i++)

5.1 if(i

while(存在Vj**不為空的節點vi)

then計算C的Vj*，路由到vj，更新路徑P:P←C

else Hn不是i維子連通的，轉5

5.2 if(i=n)計算C的Vj*，路由到B，更新路徑P:P←C

5.3 if(C=B)輸出P，end

6 if(C≠B)不存在可行路徑，end

算法是基于前述定理和推論設計的，所以算法的正確性很容易證明。算法在尋徑時是根據當前的網絡狀態來選擇路徑的，所以算法是自適應的。不難看出，算法的時間復雜度為O(n×2kmin)+O(2kmin)=O(n×2kmin)。算法在k=n的情況下退化為在Hn中尋找子圖的問題，該問題屬于NP難問題。在其他情況下，算法都可以將此問題簡化為在Hk中尋找子圖的問題，從而降低算法的時間復雜度。

3 實驗結果

為了驗證算法的可靠性和實用性，用OPNET網絡仿真工具來構建模擬網絡。參數配置情況為:節點具有獨立均勻的錯誤概率P，針對維數為10、20、30的超立方體網絡，分別設置P為0.5%、10%、20%和30%四種情況，隨機選擇20對正確節點進行消息傳遞。仿真實驗結果如表1所示。其中:Path F為算法找到的正確路徑數與網絡無錯誤時可用總路徑的比率;Min P為算法找到的最短路徑數與網絡無錯誤時可用總路徑的比率;Path L為算法構建的路徑長度與兩節點間漢明距離的比率。實驗結果表明:當節點的錯誤概率為10%時，算法有93%以上的概率路由成功;當節點的錯誤概率為0.5%時，算法有99%以上的概率路由成功。通過與文獻[7]的模擬實驗結果比較可以看出，算法構造的路徑長度更接近于最優路徑長度。對算法進行分析可以看出，死鎖可能發生在存在Vj**不為空的節點vi，卻不存在到達vi的可行路徑時。由于為當前節點添加了局部標記變量，且算法步驟5的循環結構定序地選取vi，算法能夠正確回朔來避免死鎖，模擬實驗的結果也表明算法可以預防死鎖。

表1 算法尋徑實驗結果

nP/%PathF/%MinP/%PathL/%

nP/%PathF/%MinP/%PathL/%

100.599.693.6108.8202098.987.1125.4

101094.574.5114.3203096.176.3133.6

102097.281.1127.1200.599.380.2109.5

103093.478.2137.4301099.273.6114.1

100.599.179.0105.6302097.695.5123.7

101093.594.7112.5303094.877.0131.3

202091.885.3121.0300.599.784.7106.0

203098.479.9138.7301099.073.9118.4

200.599.775.4104.2302091.374.8127.2

201095.382.8116.9303094.992.4136.8

4 結束語

本文提出了相鄰節點集合類的概念和在n維超立方體網絡中求解相鄰節點集合的方法，解決了在相鄰子立方體中尋找一對連通的可達節點的問題。利用子連通性的概念減小了求解路由問題的規模，有效降低了算法的時間復雜度。在實際應用中由于很少碰到k接近于n的特殊情況，該算法在根據網絡的錯誤節點情況選取一個合適的k后是很高效的。新提出的概念也可以推廣到其他層次型拓撲結構的網絡中去。

參考文獻:

[1]DAY K，TRIPATHI A.A comparative study of topological properties of hypercubes and star graphs[J].IEEE Trans on Parallel and Distributed Systems，1994，5(1):31-38.

[2]AKERS S B，KRISNAMURTHY B.A group-theoretic model for symmetric interconnection networks[C]//Proc of International Conference on Parallel Processing.1986:216-223.

[3]ESFAHANIAN A H.Generalized measures of fault tolerance with application to N-cube networks[J].IEEE Trans on Comput，1989，38(11):1586-1591.

[4]LATIFI S，HEDGE M.Conditional connectivity measures for large multiprocessor systems[J].IEEE Trans on Comput，1994，43(2):218-222.

[5]BRUCK J，CYPHER R，SOROKER D.Tolerating faults in hypercubes using subcube partitioning[J].IEEE Trans on Comput，1992，41(5):599-605.

[6]CHEN Jian-er，WANG Guo-jun.Locally subcube-connected hypercube networks:theoretical analysis and experimental results[J].IEEE Trans on Comput，2002，51(5):530-540.

[7]王雷，陳治平.故障超立方體網絡中的高效容錯路由算法研究[J].計算機應用，2005，25(1):4-6.