交叉立方體及加強(qiáng)交叉立方體互連網(wǎng)絡(luò)容錯(cuò)性質(zhì)的研究.pdf

1、該文以提高網(wǎng)絡(luò)的容錯(cuò)度為目的,從兩個(gè)方面分析互連網(wǎng)絡(luò)的容錯(cuò)性質(zhì):一是在原網(wǎng)絡(luò)基礎(chǔ)上增加少量連接,使新型網(wǎng)絡(luò)具有更高的連通度(容錯(cuò)度為連通度減 1);二是在給定互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下,考慮故障處理器發(fā)生的概率和故障處理器的分布狀況,在其中的某一具體條件下,即在條件連通度和簇容錯(cuò)下分析互連網(wǎng)絡(luò)的容錯(cuò)性能,從而得到更高的網(wǎng)絡(luò)容錯(cuò)度.該文選擇交叉立方體,及該立方體的一個(gè)變型—加強(qiáng)交叉立方體作為研究對(duì)象,圍繞上述問(wèn)題進(jìn)行了研究.根據(jù)Menger定理,

2、n-維交叉立方體可以容納n-1個(gè)故障頂點(diǎn),我們給出了它的時(shí)間復(fù)雜度為O(n)的容錯(cuò)路由選擇算法及其最長(zhǎng)路徑長(zhǎng)度分析;在此基礎(chǔ)上該文證明,n-維交叉立方體的條件連通度為2n-2(n≥2),并給出了相應(yīng)時(shí)間復(fù)雜度為O(n)的算法及其最長(zhǎng)路徑長(zhǎng)度;除此之外,該文還證明了n-維交叉立方體中的故障簇個(gè)數(shù)不大于n-1,其直徑不大于1,故障頂點(diǎn)總數(shù)不超過(guò)2n-3(n≥2)時(shí),交叉立方體中任兩個(gè)無(wú)故障頂點(diǎn)都至少有一條可靠路徑.交叉立方體的上述這些性質(zhì)都