Mesh網(wǎng)絡(luò)容錯(cuò)性及容錯(cuò)路由算法研究.pdf

1、多計(jì)算機(jī)系統(tǒng)作為當(dāng)今最流行的并行計(jì)算機(jī)，具有廣泛的應(yīng)用領(lǐng)域。Mesh網(wǎng)絡(luò)拓?fù)涫瞧駷橹共⑿杏?jì)算機(jī)系統(tǒng)研究中最重要和最有吸引力的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一，隨著計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)規(guī)模的擴(kuò)大，結(jié)點(diǎn)出錯(cuò)的可能隨之增加。因此，研究具有出錯(cuò)結(jié)點(diǎn)的Mesh網(wǎng)絡(luò)的容錯(cuò)性和容錯(cuò)路由不可避免。
　　 容錯(cuò)性是多計(jì)算機(jī)系統(tǒng)非常重要的研究主題。目前，從概率角度分析Mesh網(wǎng)絡(luò)的容錯(cuò)性，是假定網(wǎng)絡(luò)每個(gè)結(jié)點(diǎn)具有獨(dú)立均勻的出錯(cuò)概率。本文基于結(jié)點(diǎn)隨機(jī)出錯(cuò)概率研究多計(jì)算機(jī)網(wǎng)

2、絡(luò)Mesh的容錯(cuò)性，采用子網(wǎng)劃分方法，將網(wǎng)絡(luò)劃分為相互獨(dú)立且不相交的子網(wǎng)，假設(shè)每個(gè)結(jié)點(diǎn)具有隨機(jī)出錯(cuò)概率，通過分析子網(wǎng)的連通性，得到整個(gè)網(wǎng)絡(luò)的連通概率。數(shù)值和模擬結(jié)果表明，網(wǎng)絡(luò)連通概率隨時(shí)間的增大而減小，在給定的時(shí)間內(nèi)，網(wǎng)絡(luò)規(guī)模越大，連通概率越低。與假定網(wǎng)絡(luò)每個(gè)結(jié)點(diǎn)具有獨(dú)立均勻的出錯(cuò)概率的結(jié)論相比較，本文提出的方法和結(jié)論更能體現(xiàn)出網(wǎng)絡(luò)結(jié)點(diǎn)出錯(cuò)的真實(shí)性，所以也具有更好的理論和實(shí)際意義。
　　 其次，本文基于最小連通分量模型（MCC）

3、提出了啟發(fā)式自適應(yīng)容錯(cuò)路由算法（簡(jiǎn)稱HAR算法），該算法采用自適應(yīng)路由，是在消息傳遞的過程中動(dòng)態(tài)建立的，因此，該算法能容許相當(dāng)多的錯(cuò)誤結(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，對(duì)于較高的結(jié)點(diǎn)出錯(cuò)概率，不同規(guī)模的Mesh網(wǎng)絡(luò)中，HAR算法得到的平均路徑長(zhǎng)度與最小容錯(cuò)路由算法得出的平均路徑長(zhǎng)度非常接近。HAR算法的意義還在于：多計(jì)算機(jī)系統(tǒng)中某對(duì)特定源和目的結(jié)點(diǎn)間的路由被應(yīng)用的次數(shù)極少，因而在路徑長(zhǎng)度和時(shí)間開銷間尋找折衷比窮盡搜索最短路徑更有實(shí)際意義。相對(duì)最小容錯(cuò)