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

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

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

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

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