基于ＬＩＰ和ＲＳＣ的超立方體網(wǎng)絡(luò)單播容錯(cuò)路由算法

摘要：基于LIP和RSC的概念，提出了一個(gè)有效的超立方體網(wǎng)絡(luò)單播容錯(cuò)路由算法。該算法不僅能容納指數(shù)級(jí)的錯(cuò)誤節(jié)點(diǎn)，而且算法效率也很高。

關(guān)鍵詞：超立方體網(wǎng)絡(luò)；多處理機(jī)系統(tǒng)；單播；容錯(cuò)路由

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

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

超立方體網(wǎng)絡(luò)是多處理機(jī)系統(tǒng)中常見的一種互連網(wǎng)絡(luò)，由 Squir和Palais于1963年最早提出。這種拓?fù)浣Y(jié)構(gòu)具有直徑小、可擴(kuò)展性強(qiáng)、結(jié)構(gòu)對(duì)稱、網(wǎng)絡(luò)尋路算法簡單等特點(diǎn)，且許多互連網(wǎng)絡(luò)，如環(huán)型網(wǎng)絡(luò)、樹型網(wǎng)絡(luò)以及Meshes等均可以在超立方體網(wǎng)絡(luò)中很容易且高效率地得以實(shí)現(xiàn)，因而成為最重要和最具吸引力的網(wǎng)絡(luò)模型之一。例如Intel iPSC/1、iPSC/2和n－CUBE等并行機(jī)均采用了超立方體結(jié)構(gòu)。這種結(jié)構(gòu)在實(shí)際并行計(jì)算中也得到了廣泛應(yīng)用。

4結(jié)束語

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

參考文獻(xiàn)：

［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］朱曉峰. 立方體網(wǎng)絡(luò)路由選擇算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)， 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.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”