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

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

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

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

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