基于超立方體容錯路由算法分析
2007-12-31 00:00:00林瑋楊小帆
計算機應用研究 2007年7期
摘要：基于超立方體的優良的拓撲性質，提出了一個應用于超立方體網絡的容錯路由算法。該容錯路由算法是基于局部信息的，因為路由算法在路由過程中，只需要知道其鄰節點的信息，而無須知道其他節點的出錯情況。對于給定的源節點和目的節點，路由算法均能夠找到一條最優容錯路徑，并且可以預防死鎖。模擬實驗結果表明，路由算法所構造的路由路徑長度接近于兩個節點之間的最優路徑長度。
關鍵詞：超立方體網絡;容錯;空閑維
中圖分類號：TP302．8文獻標志碼：A
文章編號：1001－3695(2007)07－0273－03
0引言
由于多處理機系統的規模越來越大，系統中出現處理機故障或處理機間鏈路故障的可能性也隨之增加。設計較好的容錯路由策略，能盡可能多地記錄系統中存在的最優通路信息，使得當系統中存在故障時實現更有效的容錯路由，達到提高整個系統性能的目的，也越發顯得重要。假設G是一個網絡，網絡G的容錯性是指滿足以下條件的最大的整數k:在網絡G中去掉任意k個節點和相應的邊后不會破壞網絡的連通性。
超立方體網絡是研究者們研究得最早，并且現在仍然是最為重要和最有吸引力的網絡模型之一。特別地，高對稱性、強層次結構和最大容錯性等性質是超立方體網絡最有吸引力的幾個特征。近年來在科研和工業界中已設計和生產出研究用和商用的、以超立方體網絡為模型的并行計算機系統。
國內外對基于超立方體容錯路由的研究已有多年，也得到了很多很有價值的成果。大致可分為以下幾類：
（1）通過添加額外的節點或連接邊來完成容錯。雖然可以達到容錯的目的，但是這類方法會使得投入的硬件成本增加，另外對于那些已經投入市場的并行機而言，再去改變它們的拓撲結構使其容錯性能增強是不可行的。
（2）采用大量的虛通道(Virtual Channel)。但是使用虛通道會增加節點的緩沖空間和復雜的邏輯控制。這些虛通道也使得節點變得更容易出錯和不可靠。
（3）采用錯誤塊(Fault Block) 模型。使用錯誤塊模型會減少部分正確節點。
（4）利用拓撲結構本身的性質來進行容錯。它不需要添加額外的節點，這類方法不會改變拓撲結構。
本文利用超立方體自身的性質設計了路由算法。該算法是簡單的，同時又是很強的。首先，在超立方體網絡故障數小于n的情況下，該算法均適用，在滿足要求的條件時，該算法將成功地構造一條路由路徑。其次，該算法是基于局部信息的，網絡中的每一個節點只需要知道其鄰節點的狀態而不要求知道網絡的全局信息。該算法是高效的。
1基本概念和常用術語
4實驗結果
本文提出的算法基于超立方體局部信息的連通性容錯模型。筆者作了大量的模擬實驗，以研究不同錯誤概率情況下的超立方體網絡路由算法的容錯性和概率。模擬實驗基于均勻的節點錯誤概率分布，即假定每一個節點具有相等的并且是獨立的錯誤概率Pf。值得說明的是，在超立方體網絡滿足一定的條件下，算法理論上能夠構造出至少一條從源節點到目的節點的連通路徑。模擬實驗結果如表1所示。n是超立方體網絡的維數，這里測試了維數n=10、15和20的情況。對每一個維數n，測試了五種節點錯誤概率，即Pf=0.5%、12.5%、25%和30%。對于每個這樣的超立方體網絡Hn， 選擇其局部子立方體Hm，在Hm隨機選擇20對正確節點，并測試算法的容錯性和效率。以下是測試程序所使用的輸入參數和輸出參數介紹。
輸入參數：
n——超立方體網絡的維數。
Pf——節點錯誤概率。
Hm——局部子立方體，這里固定m=3和m=4兩種。
P——每個超立方體網絡所測試源節點和目的節點對的樣本數，這里固定為20。
輸出參數：
Path_Found——通過算法找到的節點間路徑數目占無節點錯誤時節點間路徑總數的比率。
MinPath_Found——通過算法找到的節點間最短路徑數目占無節點錯誤時節點間路徑總數的比率。
PathBit——算法所成功構造的路由路徑長度的總和與相應的源節點及目的節點對之間海明距離的總和之間的比值。
實驗表明，如果單個節點的錯誤概率不大于12.5%，網絡中正確節點保持連通的概率為95%左右；如果單個節點的錯誤概率不大于0.5%，則對于所有實際規模的超立方體網絡，網絡中正確節點保持連通的概率至少為99%，而且該算法構造的路由路徑長度小于源節點和目的節點海明距離的1.5倍。
5結束語
本文算法是利用超立方體的拓撲結構特性和冗余路徑，得到故障信息后，尋找一條可達路徑傳遞消息。定義空閑維的算法是根據源節點和目的節點地址得到坐標序列，本地保留錯誤信息，而后選擇非最短路徑繞過故障節點。空閑維狀態的記錄還可以避免消息無限地在同一條路徑上反復路由，這就預防了死鎖的危險。由于超立方體有多種變體(如Locally Twisted Cubes、Mobius Hypercube、Enhanced Hypercube、Crossed Hypercube、Extended Hypercube等)，將算法應用于其變體中，將會有更大的實用價值和推廣意義。
參考文獻：
［1］WU J，FERNANDEZ E B. Reliable broadcasting in faulty hypercube computer[J].Microprocess Microprogr，1993，39:43－53.
[2]LEE T C，HAYS J P. A fault－tolerant communication scheme for hypercube computers[J].IEEE Trans Computer，1992，41(10):1242－1256.
[3]CHIU Geming.A fault－tolerant broadcasting algorithm for hypercubes[J].Information Processing Letters，1998， 66(2):93－99.
[4]YANG X F， EVANS D J，MEGSON G M. The locally twisted cubes[J].International Journal of Computer Mathematics，2005，82(4):401－413.
[5]王國軍，陳建二，陳松喬. 具有大量錯誤節點的超立方體網絡中的高效路由算法的設計與討論[J]. 計算機學報，2001，24(9)：909－916.
[6]朱曉峰，孫惠泉.基于路由選擇能力的容錯路由選擇[J]. 計算機工程與科學，2000，22(3)：41－44.
[7]DUATOJ，YALAMANCHILI S，NI L.并行計算機互連網絡技術：一種工程方法[M].謝倫國，張民選，竇強，等譯.北京：電子工業出版社，2004.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
