故障超立方體變形網(wǎng)絡(luò)路由算法的研究.pdf

1、　　隨著并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大,互聯(lián)網(wǎng)絡(luò)中處理器或處理器鏈路發(fā)生故障的情形是不可避免的。因此,故障網(wǎng)絡(luò)中的路由問(wèn)題和連通性以及容錯(cuò)性成為了計(jì)算機(jī)研究領(lǐng)域的熱點(diǎn)。如何設(shè)計(jì)簡(jiǎn)單可行的路由算法從而保證網(wǎng)絡(luò)能繼續(xù)有效的工作迫在眉睫。本文主要討論了結(jié)點(diǎn)故障條件下超立方體變形網(wǎng)絡(luò)(折疊超立方體網(wǎng)絡(luò)和交叉超立方體網(wǎng)絡(luò))的局部連通性、拓展局部連通性、在局部連通性和拓展局部連通性下的容錯(cuò)路由算法、結(jié)點(diǎn)故障條件下的圈嵌入加強(qiáng)超立方體網(wǎng)絡(luò)以及增廣超

2、立方體網(wǎng)絡(luò)的邊泛圈和邊哈密頓性。
　　論文主要分為四章,研究故障超立方體變形網(wǎng)絡(luò)的容錯(cuò)性、連通性和路由算法。
　　第一章主要介紹圖的相關(guān)基本概念及其性質(zhì),超立方體網(wǎng)絡(luò)及其變形網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和性質(zhì)簡(jiǎn)介；并闡述與網(wǎng)絡(luò)中路由算法相關(guān)的容錯(cuò)性和連通性的研究意義。
　　第二章主要研究了折疊超立方體網(wǎng)絡(luò)的局部連通性和拓展局部連通性以及基于局部連通性和拓展局部連通性下的高效容錯(cuò)路由算法,得到了以下五個(gè)定理和兩個(gè)高效容錯(cuò)并行

3、路由算法：
　　(1)若n-維折疊超立方體網(wǎng)絡(luò)FQn是局部k-維子折疊超立方體連通的,則在FQn中必定存在至少K=min(Dk (u ), Dk (v ))條從非故障源結(jié)點(diǎn)u到目的結(jié)點(diǎn)v的并行路徑,且每一條路徑的長(zhǎng)度不超過(guò)(d (Uk ,Vk )+3)2k 。
　　(2)局部k-維子折疊超立方體連通的n-維折疊超立方體 nFQ 中的所有非故障結(jié)點(diǎn)構(gòu)成一個(gè)連通圖。
　　(3)局部子折疊超立方體連通的n-維折疊

4、超立方體 nFQ 中的所有非故障結(jié)點(diǎn)構(gòu)成一個(gè)連通圖。
　　(4)在一個(gè)拓展局部k-維子折疊超立方體連通的n-維折疊超立方體 nFQ 中所有的非故障結(jié)點(diǎn)構(gòu)成一個(gè)連通圖。
　　(5)在一個(gè)拓展局部子折疊超立方體連通的n-維折疊超立方體 nFQ 中,所有的非故障結(jié)點(diǎn)構(gòu)成一個(gè)連通圖。
　　算法1、具有大量故障結(jié)點(diǎn)的n-維折疊超立方體 nFQ 中的高效并行路由算法。
　　算法 2、基于拓展局部k-維子折疊超