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

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

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