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

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

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

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

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