具有大量錯誤結點的超立方體網(wǎng)絡基于矩陣容錯路由算法的設計與討論.pdf

1、超立方體網(wǎng)絡拓撲結構是多處理機系統(tǒng)中常見的一種，并且在Internet上具有廣泛的應用，因此基于超立方體網(wǎng)絡的容錯性成為研究的焦點.隨著多處理機系統(tǒng)規(guī)模的增大，系統(tǒng)出現(xiàn)鏈路與結點故障的概率也隨之增大.論文在介紹相關基本概念及國內外相關研究現(xiàn)狀的基礎上，首先針對傳統(tǒng)的容錯路由算法進行了分析，并找出傳統(tǒng)路由算法在解決迂回與死鎖問題上的缺點，提出了安全矩陣容錯路由算法，針對傳統(tǒng)路由算法只能搜索最優(yōu)通路而不能記錄最優(yōu)通路的條數(shù)，提出了極大安全鏈

2、路矩陣容錯路由算法，并對搜索結果進行了數(shù)據(jù)分析.本文具體做了以下兩方面的工作： (1)論文針對超立方體結構的容錯路由設計在信息傳輸過程中出現(xiàn)迂回和死鎖的情況，提出了安全矩陣(safety matrices，簡稱SMs)這一概念，給出了一種建立SMs的方法及其容錯路由算法，并對安全矩陣的相關性質進行了證明.n維超立方體每個結點所需的存儲開銷為n2個字，安全矩陣記錄了局部更多的信息.與傳統(tǒng)的路由算法相比，該算法可以避免信息在傳輸過程

3、中出現(xiàn)迂回和死鎖，使路徑達到最優(yōu). (2)論文針對超立方體結構的多處理機系統(tǒng)中存在鏈路故障的情況，在信息的傳輸過程中傳統(tǒng)的路由算法只能判斷源結點與目的結點之間是否存在最優(yōu)通路而不能記錄最優(yōu)通路的條數(shù)，提出了用于最優(yōu)通路記錄的極大安全鏈路矩陣(maximum safety-link matrices,簡稱MSLMs)這一概念，給出了一種建立MSLMs及其容錯路由算法，并對極大安全鏈路矩陣的相關性質和定理進行了證明。通過n-1輪鄰結