局部扭曲立方體容錯路由策略研究.pdf

1、互連網(wǎng)絡(luò)為多計算機(jī)系統(tǒng)中處理器單元之間的通信提供了一種有效的機(jī)制，隨著并行計算機(jī)互連網(wǎng)絡(luò)規(guī)模越來越大，網(wǎng)絡(luò)中出現(xiàn)處理機(jī)故障或處理機(jī)間的邊故障的可能性也越來越大。因此，在出現(xiàn)處理機(jī)故障或處理機(jī)間的邊故障的情況下，互連網(wǎng)絡(luò)之間高效的通信成為評估該網(wǎng)絡(luò)的一個重要依據(jù)。 局部扭曲立方體作為超立方體的變體，是一種新型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，保持了超立方體的很多優(yōu)點的同時，其自身也有很多非常好的性質(zhì)，直徑大約只有超立方體的一半，擁有更好的容錯和嵌入

2、屬性。基于局部扭曲立方體的這些良好的特性，使其成為最為重要和最有吸引力的網(wǎng)絡(luò)模型之一。 本文主要是對n維局部扭曲立方體存在節(jié)點故障或邊故障的情況下，如何實現(xiàn)消息傳遞進(jìn)行了研究。下面是本文的主要研究工作： ①在節(jié)點故障的情況下，提出了一種基于節(jié)點安全級概念的單播容錯路由算法。該算法除了考慮鄰接節(jié)點的安全狀況外，還充分利用了局部扭曲立方體自身特有的結(jié)構(gòu)，使得信息盡可能沿最優(yōu)路徑傳遞。通過模擬仿真實驗可知，算法具有較高的容錯能

3、力。當(dāng)故障節(jié)點的數(shù)目達(dá)到或超過一半時，算法仍能保持一個相當(dāng)高的容錯路由成功率，且算法所選路徑在多數(shù)情況下是最優(yōu)路徑。 ②在邊故障的情況下，基于局部信息的思想，通過存儲其鄰接節(jié)點的邊故障信息數(shù)組并引入消息回溯機(jī)制，設(shè)計了一種單播容錯路由算法。仿真實驗表明，當(dāng)有大量的邊發(fā)生故障時，該算法也能成功地實現(xiàn)消息傳遞。 ③在節(jié)點故障的情況下，基于路由能力的概念提出了一種單播容錯路由算法，該算法首先尋找最短路徑上滿足路由能力值要求的鄰

4、接節(jié)點，其次尋找非最短路徑上滿足路由能力值要求的鄰接節(jié)點。這樣求得的容錯路徑首先是最優(yōu)路徑，其次為次優(yōu)路徑。 ④基于立方體分割的思想，設(shè)計了一種廣播容錯路由算法。通過證明可知，若源節(jié)點為安全節(jié)點，算法產(chǎn)生的廣播樹是最優(yōu)的；若源節(jié)點為非安全節(jié)點(故障節(jié)點數(shù)小于n)，廣播能夠在，n+1步內(nèi)完成。 ⑤接著，我們提出了一種基于單播的多播容錯路由算法，該算法通過把局部扭曲立方體多播組節(jié)點分成若干個較小的子集合，多播消息只在各個子集