互聯(lián)網(wǎng)絡PCP(n)的容錯性研究.pdf

1、并行計算機系統(tǒng)中的容錯技術是當今計算機科學研究的熱點之一。網(wǎng)絡容錯是指，在互聯(lián)網(wǎng)絡中某些節(jié)點或鏈路發(fā)生故障的情形下，仍能保證網(wǎng)絡中無故障的節(jié)點之間進行可靠的信息傳送。一個網(wǎng)絡的容錯度，是網(wǎng)絡中能保證任意兩個無故障節(jié)點間進行可靠信息傳送所允許故障節(jié)點的最大個數(shù)?；ヂ?lián)網(wǎng)絡作為并行計算機系統(tǒng)的主干，其容錯性能的高低用容錯度來衡量，容錯度越高，容錯性能越好。因此，高容錯度是互聯(lián)網(wǎng)絡設計的重要目標之一。
　　交叉立方體互聯(lián)網(wǎng)絡，是超立方體互

2、聯(lián)網(wǎng)絡的一種變形，它在某些方面有著比超立方體更好的拓撲性質，因此是非常具有吸引力的互聯(lián)網(wǎng)絡拓撲結構之一。RCP(n)互聯(lián)網(wǎng)絡（即基于交叉立方體環(huán)連接的彼特森圖互聯(lián)網(wǎng)絡）是一種新型的并行計算機互聯(lián)網(wǎng)絡拓撲結構，環(huán)的簡單擴展性、彼特森圖的短直徑與交叉立方體網(wǎng)絡中節(jié)點的高可連接性，使得RCP(n)網(wǎng)絡具有良好的通信性能。
　　本文的主要研究成果是論文的第三章和第四章。
　　第三章提出了局部k維子交叉立方體連通性和局部子交叉立方體連

3、通性的概念，并給出交叉立方體互聯(lián)網(wǎng)絡中兩種基于子交叉立方體結構的局部連通性容錯模型;基于這兩種局部連通性容錯模型，設計了兩個高效的單播容錯路由算法，并分析了路由算法的時間復雜度。在這兩種局部連通性容錯模型中，即使交叉立方體網(wǎng)絡中的錯誤節(jié)點數(shù)接近50％，正確節(jié)點仍能保持連通。兩個容錯路由算法的時間復雜度分別為O(n)和O(n2)，都是多項式時間算法，并且都是基于局部信息，因而具有很好的通信性能。
　　第四章構建了RCP(n)網(wǎng)絡上的

4、三種容錯模型:以環(huán)為基本容錯元素的容錯模型，以彼特森圖為基本容錯元素的容錯模型和以交叉立方體為基本容錯元素的容錯模型;基于局部（k維）子交叉立方體連通的RCP(n)網(wǎng)絡容錯模型，給出了RCP(n)網(wǎng)絡上的兩個容錯路由算法，其時間復雜度都是O(2n-3)。雖然時間復雜度是指數(shù)的，但因為n的取值不會太大，所以它們?nèi)匀皇峭ㄐ鸥咝У?。這三種容錯模型中，以環(huán)為基本容錯元素的容錯模型適合網(wǎng)絡中的錯誤節(jié)點分布比較均勻的情況，可允許20％到40％的錯誤