Mesh網絡容錯性及容錯路由算法研究.pdf

1、多計算機系統(tǒng)作為當今最流行的并行計算機，具有廣泛的應用領域。Mesh網絡拓撲是迄今為止并行計算機系統(tǒng)研究中最重要和最有吸引力的網絡拓撲結構之一，隨著計算機互聯(lián)網絡規(guī)模的擴大，結點出錯的可能隨之增加。因此，研究具有出錯結點的Mesh網絡的容錯性和容錯路由不可避免。
　　 容錯性是多計算機系統(tǒng)非常重要的研究主題。目前，從概率角度分析Mesh網絡的容錯性，是假定網絡每個結點具有獨立均勻的出錯概率。本文基于結點隨機出錯概率研究多計算機網

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

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