幾類互連網(wǎng)絡性能的組合分析.pdf

1、網(wǎng)絡的拓撲結(jié)構(gòu)是設計和制造機群計算機或超大規(guī)模并行計算機系統(tǒng)的第一步，也是實現(xiàn)各種協(xié)議的基礎，它對網(wǎng)絡的性能、系統(tǒng)可靠性和費用都有重大影響。人們通常把互連網(wǎng)絡中的處理器抽象成一個點，把處理器之間的信道抽象成兩點之間的連線，那么該網(wǎng)絡的拓撲結(jié)構(gòu)就被抽象成一個圖。研究網(wǎng)絡拓撲結(jié)構(gòu)問題就歸結(jié)為研究圖的結(jié)構(gòu)問題。網(wǎng)絡的容錯性研究可以轉(zhuǎn)化成對圖的參數(shù)研究?；ミB網(wǎng)絡主要有以下的評價指標： (1)硬件復雜度，可以用拓撲圖的頂點度來衡量。

2、 (2)通信開銷：可以用網(wǎng)絡拓撲圖的直徑來、平均距離來衡量。 (3)可擴展性。就是一個小網(wǎng)絡要擴充為一個大網(wǎng)絡，并保留小網(wǎng)絡的結(jié)構(gòu)性質(zhì)的可能性，它可以歸結(jié)為圖的可嵌入性問題。 (4)容錯能力?？梢杂脠D的連通度以及邊連通度、網(wǎng)絡的容錯直徑和寬直徑衡量。 目前討論比較多的網(wǎng)絡主要有網(wǎng)狀網(wǎng)、樹狀網(wǎng)、超方體狀網(wǎng)和星狀網(wǎng)類型網(wǎng)絡。本文主要考慮這些網(wǎng)絡的容錯性質(zhì)，我們的工作如下： 首先，我們對這些主要的網(wǎng)絡拓撲結(jié)構(gòu)

3、的容錯性指標，例如通信延遲、容錯直徑與寬直徑、連通性質(zhì)進行了系統(tǒng)的總結(jié)。在此基礎上，提出了互連網(wǎng)絡拓撲容錯性方面一些值得進一步研究的問題。 然后，本文對超立方體的一種變形——變種超立方體進行進一步研究。對變種超立方體的研究已有很多，包括連通度、遞歸性，可嵌入環(huán)和格、直徑、路由算法和廣播算法。本文研究變種超立方體的容錯直徑和寬直徑，證明了容錯直徑和寬直徑等于它的直徑加1或2。 最后，利用提升圖的技巧，我們提供一種構(gòu)造更大規(guī)