基于ＬＩＰ和ＲＳＣ的超立方體網絡單播容錯路由算法

摘要：基于LIP和RSC的概念，提出了一個有效的超立方體網絡單播容錯路由算法。該算法不僅能容納指數級的錯誤節點，而且算法效率也很高。

關鍵詞：超立方體網絡；多處理機系統；單播；容錯路由

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

文章編號：1001－3695(2007)07－0255－03

超立方體網絡是多處理機系統中常見的一種互連網絡，由 Squir和Palais于1963年最早提出。這種拓撲結構具有直徑小、可擴展性強、結構對稱、網絡尋路算法簡單等特點，且許多互連網絡，如環型網絡、樹型網絡以及Meshes等均可以在超立方體網絡中很容易且高效率地得以實現，因而成為最重要和最具吸引力的網絡模型之一。例如Intel iPSC/1、iPSC/2和n－CUBE等并行機均采用了超立方體結構。這種結構在實際并行計算中也得到了廣泛應用。

4結束語

多處理機系統中的容錯性一直是影響其性能的一個重要因素；單播通信也是最基本的通信方式之一。本文在LIP和RSC的基礎上，提出一種超立方體網絡單播容錯路由算法。該算法在“超立方體網絡中至少存在一條無故障節點的LIP”條件下，所能容納的壞節點數多于2n-1，達到指數數量級。此外，該算法的最少步數為H(S， D)，極壞情況為LIP(Qn)+1，且算法達到極壞情況的可能性是非常小的。因此，算法在很大程度上是比較優越的。

參考文獻：

［1］ESFAHANIAN A H. Generalized measures of fault tolerance with application to n－cube networks[J].IEEE Transactions on Compu－ters，1989，38(11): 1586－1591.

［2］GU Qianping，PENG Shietung.Optimal algorithms for node－to－node fault tolerant routing in hypercubes[J].The Computer Journal，1996，39(7): 626－629.

［3］TIEN S B，RAGHAVENDRA C S. Algorithms and bounds for shortest paths and diameter in faulty hypercubes[J].IEEE Transactions on Parallel and Distributed Systems， 1993，4(6): 713－778.

［4］朱曉峰. 立方體網絡路由選擇算法[J].數學的實踐與認識， 2002，32(1):70－74.

［5］CHIU Geming，CHEN Karshung. Use of routing capability for fault－tolerant in hypercube multicomputers[J].IEEE Transactions on Computers，1997，46(8): 953－958.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”