超立方體網(wǎng)絡(luò)容錯模型及其路由算法研究.pdf

1、隨著計算機(jī)網(wǎng)絡(luò)技術(shù)與計算科學(xué)的發(fā)展，并行計算機(jī)及其互連網(wǎng)絡(luò)作為一個跨數(shù)學(xué)、計算科學(xué)與信息科學(xué)等多門學(xué)科的領(lǐng)域，逐漸成為計算機(jī)科學(xué)研究的熱點之一，各種拓?fù)浣Y(jié)構(gòu)的互連網(wǎng)絡(luò)，如環(huán)、Mesh、超立方體、星型網(wǎng)絡(luò)等得到迅速發(fā)展。在一個多處理器互連網(wǎng)絡(luò)中，處理器之間的有效通信是衡量系統(tǒng)性能的一個重要標(biāo)準(zhǔn)。當(dāng)處理器數(shù)目逐漸增多時，其發(fā)生故障的可能性也隨之增加，不同處理器之間信息傳遞過程中的容錯性便成為一個非常關(guān)鍵的問題。因此，如何設(shè)計新的網(wǎng)絡(luò)容錯模型

2、以便容納更多的錯誤結(jié)點，以及如何設(shè)計高效的容錯路由算法以便保證無故障處理器間正確可靠的信息傳遞是至關(guān)重要的。 超立方體網(wǎng)絡(luò)是多處理機(jī)系統(tǒng)中常見的一種互連網(wǎng)絡(luò)，這種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)由于具有直徑小、可擴(kuò)展性強(qiáng)、結(jié)構(gòu)對稱、網(wǎng)絡(luò)尋路算法簡單等優(yōu)點，且多種拓?fù)浣Y(jié)構(gòu)的互連網(wǎng)絡(luò)都可以很容易的嵌入其中，因而成為最重要和最具吸引力的網(wǎng)絡(luò)模型之一。本文基于LIP容錯模型和局部連通性，對超立方體網(wǎng)絡(luò)的容錯性和路由算法進(jìn)行研究，主要研究內(nèi)容如下：

3、1.給出了超立方體網(wǎng)絡(luò)及其k維子立方體的概念，同時結(jié)合LIP的相關(guān)概念和性質(zhì)，給出了對求解LIP長度的程序的改進(jìn)，并根據(jù)程序的運行結(jié)果進(jìn)行了分析。 2.結(jié)合第二章最長導(dǎo)出路LIP的概念，提出了超立方體中基于LIP的廣播容錯路由算法。該算法是基于“超立方體中至少存在一條無故障結(jié)點的LIP”的前提條件的，在此條件滿足的情況下，超立方體是全局連通的，且該算法能容許大量的錯誤結(jié)點（2n-1甚至更多），在容錯性上有了很大提高。 3

4、.基于LIP容錯模型和超立方體中的4維子立方體，提出超立方體網(wǎng)絡(luò)中的一種單播容錯路由算法。該算法在必要的搜索時間內(nèi)，在具有大量錯誤結(jié)點的超立方體網(wǎng)絡(luò)中找出連接兩個正確結(jié)點的路徑，并且該算法是基于局部信息的，因而具有很好的實際意義。 本文在超立方體網(wǎng)絡(luò)容錯模型及路由算法方面作了一些探索工作，取得了一定的結(jié)果，但還有大量工作需要研究。 首先，進(jìn)一步研究超立方體網(wǎng)絡(luò)中的LIP容錯模型，給出LIP長度的近似或精確計算公式，以便更