高性能并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)容錯(cuò)模型及其路由算法研究.pdf

1、由于均具有正則性、對(duì)稱性、可嵌入性、并行性、以及良好的容錯(cuò)性與網(wǎng)絡(luò)通信能力的可擴(kuò)展性等優(yōu)良特性，超立方體(Hypercube)和彼特森圖(PetersenGraph)互聯(lián)網(wǎng)絡(luò)受到了研究者們的廣泛關(guān)注，是迄今為止最為重要和最具吸引力的并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之一。隨著現(xiàn)在的并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)規(guī)模越來越大，網(wǎng)絡(luò)中出現(xiàn)處理機(jī)故障或處理機(jī)間的鏈路故障的可能性也越來越大；這就使得并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)的容錯(cuò)性及其研究也變得越來越重要，因此，設(shè)計(jì)具有

2、較好容錯(cuò)性的路由算法對(duì)并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)有著重要意義。 到目前為止，人們已經(jīng)對(duì)超立方體或彼特森圖互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦约捌淙蒎e(cuò)模型與容錯(cuò)路由算法方面分別進(jìn)行了深入的研究，并基于超立方體或彼特森圖互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦苑謩e建立了一些容錯(cuò)模型及其容錯(cuò)路由算法，但上述研究均是針對(duì)超立方體或彼特森圖互聯(lián)網(wǎng)絡(luò)單獨(dú)進(jìn)行的，缺乏對(duì)這兩種互聯(lián)網(wǎng)絡(luò)系統(tǒng)的綜合研究。超立方體和彼特森圖互聯(lián)網(wǎng)絡(luò)雖然在本質(zhì)上各不相同，但由于它們均具有正則性、對(duì)稱性、可嵌入性、并

3、行性、以及良好的容錯(cuò)性與網(wǎng)絡(luò)通信能力的可擴(kuò)展性等優(yōu)良特性，在拓?fù)涮匦陨暇哂泻艽蟪潭鹊南嗨菩?，而且還可以通過相互結(jié)合形成具有某些特殊性質(zhì)的新型互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，因此，將超立方體和彼特森圖互聯(lián)網(wǎng)絡(luò)綜合起來進(jìn)行系統(tǒng)深入的研究，將比對(duì)其中的單個(gè)網(wǎng)絡(luò)進(jìn)行孤立研究具有更好的效果，能更進(jìn)一步地促進(jìn)對(duì)這兩種互聯(lián)網(wǎng)絡(luò)乃至整個(gè)高性能并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)的研究發(fā)展，特別地，取兩個(gè)網(wǎng)絡(luò)拓?fù)涮匦灾L(zhǎng)來彌補(bǔ)各自之短，研究如何利用超立方體互聯(lián)網(wǎng)絡(luò)的可擴(kuò)展性和彼特森圖互

4、聯(lián)網(wǎng)絡(luò)的短直徑特性來構(gòu)造出具有更優(yōu)特性的新型并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)，將具有重要的研究?jī)r(jià)值。綜上所述，本文綜合系統(tǒng)地研究超立方體和彼特森圖這兩種具有相似拓?fù)涮匦缘母咝阅懿⑿杏?jì)算機(jī)互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦约捌淙蒎e(cuò)模型與容錯(cuò)路由算法。 在對(duì)超立方體互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦约捌淙蒎e(cuò)模型與容錯(cuò)路由算法方面，本文首先綜述了目前國(guó)內(nèi)、國(guó)際上在超立方體互聯(lián)網(wǎng)絡(luò)研究方面所做的主要研究工作，并基于已有的一些研究成果，提出了三種新的超立方體互聯(lián)網(wǎng)絡(luò)的容錯(cuò)模型及其容錯(cuò)

5、路由算法：即基于極大安全通路向量的容錯(cuò)模型MSPV(MaximalSafetyPathVector)及其容錯(cuò)路由算法、基于極大安全通路矩陣的容錯(cuò)模型MSPM(MaximalSafetyPathMatrix)及其容錯(cuò)路由算法，以及基于兩類子連通性的超立方體互聯(lián)網(wǎng)絡(luò)容錯(cuò)模型及其容錯(cuò)路由算法；證明了上述超立方體互聯(lián)網(wǎng)絡(luò)的容錯(cuò)模型及其容錯(cuò)路由算法分別是基于安全向量的容錯(cuò)模型SV(SafetyVector)、基于擴(kuò)展安全向量的容錯(cuò)模型ESV(Ex

6、tendedSafetyVector)、基于最優(yōu)通路矩陣的容錯(cuò)模型OPM(OptimalPathMatrix)、基于擴(kuò)展最優(yōu)通路矩陣的容錯(cuò)模型EOPM(ExtendedOptimalPathMatrix)、以及基于兩類子立方體局部連通性的超立方體互聯(lián)網(wǎng)絡(luò)容錯(cuò)模型及其容錯(cuò)路由算法的極大擴(kuò)展，因此具有比它們更強(qiáng)的容錯(cuò)能力。 在對(duì)彼特森圖互聯(lián)網(wǎng)絡(luò)的拓?fù)涮匦约捌淙蒎e(cuò)模型與容錯(cuò)路由算法方面，本文首先綜述了目前國(guó)內(nèi)、國(guó)際上在彼特森圖互聯(lián)網(wǎng)絡(luò)

7、研究方面所做的主要研究工作，并基于已有的一些研究成果，提出了兩種新的彼特森圖互聯(lián)網(wǎng)絡(luò)及其容錯(cuò)模型與容錯(cuò)路由算法：即雙環(huán)彼特森圖互聯(lián)網(wǎng)絡(luò)DLCP(k)(Double-LoopsConnectedPetersenGraph)及其容錯(cuò)模型與容錯(cuò)路由算法、層次雙環(huán)彼特森圖互聯(lián)網(wǎng)絡(luò)HDLCP(k)(HierarchicalDouble-LoopsConnectedPetersenGraph)及其容錯(cuò)模型與容錯(cuò)路由算法；并對(duì)DLCP(k)和HDLC

8、P(k)互聯(lián)網(wǎng)絡(luò)的連接度、網(wǎng)絡(luò)直徑、以及網(wǎng)絡(luò)的可擴(kuò)展性與可分組性等特性進(jìn)行了分析，證明了DLCP(k)和HDLCP(k)互聯(lián)網(wǎng)絡(luò)在網(wǎng)絡(luò)直徑、可分組性、以及網(wǎng)絡(luò)節(jié)點(diǎn)的連接度等性能指標(biāo)上，具有比二維Torus互聯(lián)網(wǎng)絡(luò)以及超立方體互聯(lián)網(wǎng)絡(luò)更優(yōu)的拓?fù)湫阅?。另外，本文還分別給出了DLCP(k)和HDLCP(k)互聯(lián)網(wǎng)絡(luò)上的容錯(cuò)路由算法，仿真實(shí)驗(yàn)表明，算法具有良好的容錯(cuò)性能。 另外，本文還對(duì)超立方體和彼特森圖互聯(lián)網(wǎng)絡(luò)進(jìn)行了綜合研究，結(jié)合彼特

9、森圖的短直徑和超立方體互聯(lián)網(wǎng)絡(luò)的可擴(kuò)展性，提出了一種基于彼特森圖連接的新型超立方體互聯(lián)網(wǎng)絡(luò)HCPG(k)(Hyper-cubesConnectedPetersenGraph)，并對(duì)其特性進(jìn)行了研究。證明了HCPG(k)互聯(lián)網(wǎng)絡(luò)在保持超立方體和彼特森圖互聯(lián)網(wǎng)絡(luò)所共有的正則性和對(duì)稱性等優(yōu)良特性的情況下，而且還兼具有超立方體互聯(lián)網(wǎng)絡(luò)的可擴(kuò)展性與彼特森圖互聯(lián)網(wǎng)絡(luò)所特有的短直徑等良好特性：即HCPG(k)互聯(lián)網(wǎng)絡(luò)不但比現(xiàn)有的超立方體互聯(lián)網(wǎng)絡(luò)Qk(

10、Hypercube)、環(huán)彼特森圖互聯(lián)網(wǎng)絡(luò)RP(k)(Ringed-Petersen)，以及超彼特森圖互聯(lián)網(wǎng)絡(luò)HP(k)(Hyper-Petersen)等具有更多的節(jié)點(diǎn)數(shù)，且其構(gòu)造開銷更小。因此，HCPG(k)是一種具有比上述互聯(lián)網(wǎng)絡(luò)更好可擴(kuò)展性的新型高性能并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)果。另外，本文還基于HCPG(k)互聯(lián)網(wǎng)絡(luò)設(shè)計(jì)了其上的容錯(cuò)路由算法，證明了其具有良好的容錯(cuò)性能。 最后，本文對(duì)超立方體模型的應(yīng)用進(jìn)行了研究，提出了一種新