幾種互聯(lián)網(wǎng)絡最短路算法及可分組性研究.pdf

1、互聯(lián)網(wǎng)絡是隨著信息技術與計算機科學的發(fā)展而產(chǎn)生的一個跨數(shù)學、通信、信息等多種學科的研究領域?；ヂ?lián)網(wǎng)絡拓撲結構是當今并行計算機一個研究熱點，大量學者對并行計算機互聯(lián)網(wǎng)絡拓撲結構做了很多研究，如環(huán)、樹、星型、網(wǎng)格、環(huán)繞、超立方體和彼特森圖等互聯(lián)網(wǎng)絡拓撲結構，并且已把其中一些網(wǎng)絡應用于實際中。
　　互聯(lián)網(wǎng)絡的最短路和可分組性一直是網(wǎng)絡研究領域的熱點。互聯(lián)網(wǎng)絡的最短路尋徑方式直接影響著計算機并行處理的性能，建立一種有效的路由方式無疑將為大

2、規(guī)模網(wǎng)絡的高效并行處理提供堅實的基礎?？煞纸M性直接反映一個互聯(lián)網(wǎng)絡的通信開銷，可分組性良好的網(wǎng)絡通信開銷也小。因此研究互聯(lián)網(wǎng)絡的最短路算法和可分組性具有重要的理論意義和應用價值。
　　超立方體(Hypercube)是最早提出的網(wǎng)絡拓撲結構之一。它具有正則性、對稱性、強容錯性、短直徑、可嵌入性等優(yōu)良性質。1991年，EfeK等提出了超立方體互聯(lián)網(wǎng)絡的一個變種——交叉立方體互聯(lián)網(wǎng)絡(Crossedcube)，它不僅具有和超立方體相同的

3、節(jié)點數(shù)、連通度、正則性、對稱性，而且還有一些比超立方體更優(yōu)越的性質，如其直徑和通信開銷大約是超立方體的一半。因此人們把交叉立方體嵌入到一些更復雜的互聯(lián)網(wǎng)絡中構成新的網(wǎng)絡拓撲結構，例如新型的互聯(lián)網(wǎng)絡RCP(n)的拓撲結構就是由交叉立方體、環(huán)和Petersen圖組成的。
　　本文針對超立方體、交叉立方體和RCP(n)互聯(lián)網(wǎng)絡節(jié)點編碼的特點，在理論分析的基礎上，研究了這三種互聯(lián)網(wǎng)絡最短路和可分組性問題，得到了如下主要結果:
　　1

4、.給出了基于超立方體節(jié)點編碼的任意兩節(jié)點間的所有最短路算法，并分析了算法復雜度;
　　2.對于交叉立方體，先采用雙向逼近的思想給出了一個基于交叉立方體互聯(lián)網(wǎng)絡節(jié)點編碼的路由算法，然后給出了交叉立方體中任意兩節(jié)點間所有的最短路算法，并分析了這兩個算法的算法復雜度;
　　3.給出了基于RCP(n)節(jié)點編碼的最短路算法，并分析了算法復雜度;
　　4.研究了超立方體Qn、交叉立方體Dn和RCP(n)互聯(lián)網(wǎng)絡的可分組性，給出了最