超立方體網絡容錯模型及其路由算法研究.pdf

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

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

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

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