超立方體網(wǎng)絡(luò)中多播路由優(yōu)化策略研究.pdf

1、超立方體是一種具有優(yōu)良性質(zhì)的拓?fù)?它具有高度冗余通信路徑與強(qiáng)容錯(cuò)通信能力、結(jié)構(gòu)對(duì)稱引入的自嵌入性、便于增加節(jié)點(diǎn)的可擴(kuò)展性、網(wǎng)絡(luò)尋路算法簡(jiǎn)潔性等優(yōu)點(diǎn)。并且其它多種類型拓?fù)渚W(wǎng)絡(luò)均可以便捷的與之相結(jié)合形成復(fù)合型拓?fù)?從而該型拓?fù)涑蔀榱烁咝阅懿⑿杏?jì)算機(jī)系統(tǒng)設(shè)計(jì)中最具吸引力的網(wǎng)絡(luò)模型之一。
　　應(yīng)用超立方體作為拓?fù)溥B接方式的并行計(jì)算機(jī)系統(tǒng)性能在很大程度上取決于其所采用的多播路由策略,其主要包括多播通信策略,容錯(cuò)多播通信策略和不相交路徑多播通

2、信策略。多播操作產(chǎn)生的通信量在眾多并行計(jì)算機(jī)運(yùn)算環(huán)境中的全部通信量中占相當(dāng)大比重,設(shè)計(jì)能夠提供高效通信服務(wù)的多播通信策略是提高系統(tǒng)通信效率和計(jì)算機(jī)整體可靠性的有效途徑。而并行計(jì)算機(jī)規(guī)模擴(kuò)大帶來(lái)計(jì)算節(jié)點(diǎn)增多,系統(tǒng)中出現(xiàn)計(jì)算節(jié)點(diǎn)或通信鏈路故障頻率也隨之變高,因而在存在部分節(jié)點(diǎn)故障和連接故障情況下為了保證系統(tǒng)連續(xù)正確運(yùn)行,設(shè)計(jì)產(chǎn)生通信信息量盡量小的容錯(cuò)多播通信策略是一個(gè)重要挑戰(zhàn)性問(wèn)題。不相交路徑路由策略從目標(biāo)節(jié)點(diǎn)數(shù)量上分為單目標(biāo)節(jié)點(diǎn)和多目標(biāo)節(jié)

3、點(diǎn)兩類,單目標(biāo)節(jié)點(diǎn)不相交路徑路由是增大節(jié)點(diǎn)間網(wǎng)絡(luò)帶寬并提高容錯(cuò)能力的綜合解決方案,而多目標(biāo)節(jié)點(diǎn)不相交路徑通信可以看作是以路徑不相交為約束條件的多播通信,他們?yōu)榫W(wǎng)絡(luò)及系統(tǒng)可靠性提供了更高層次保障。如何在容錯(cuò)能力,通信效率,通信開銷等方面對(duì)這三種通信策略進(jìn)行優(yōu)化成為超立方體網(wǎng)絡(luò)路由策略研究的熱點(diǎn)問(wèn)題。
　　本文的主要研究?jī)?nèi)容如下:
　　以減少基于樹型拓?fù)涠嗖ゲ呗酝ㄐ砰_銷為目標(biāo),提出了一個(gè)超立方體網(wǎng)絡(luò)基于逐層聚簇策略的啟發(fā)式多播樹

4、構(gòu)造算法(LWC-MT)。利用樹型拓?fù)涠嗖シ桨干蛇^(guò)程的分析結(jié)論及分簇模型,LWC-MT采用了以聚簇代價(jià)沿著最小增長(zhǎng)方向進(jìn)行聚簇操作的方法,對(duì)多播樹建立過(guò)程進(jìn)行了優(yōu)化。仿真實(shí)驗(yàn)結(jié)果也表明,該算法在通信開銷上優(yōu)于現(xiàn)存算法。
　　以在保證一定容錯(cuò)通信能力條件下減小多播通信開銷為目標(biāo),提出了一種容錯(cuò)多播路由策略(FT-MT)和基于局部k維子立方連通超立方體網(wǎng)絡(luò)的分布式容錯(cuò)多播路由策略(DFT-MT)。FT-MT利用近優(yōu)容錯(cuò)路徑存儲(chǔ)模型構(gòu)

5、造容錯(cuò)多播方案,在保證容錯(cuò)能力的同時(shí),得到了降低多播方案總體網(wǎng)絡(luò)通信開銷的優(yōu)化結(jié)果。DFT-MT針對(duì)局部k維子立方連通超立方體網(wǎng)絡(luò),實(shí)現(xiàn)了對(duì)近優(yōu)容錯(cuò)路徑存儲(chǔ)模型局部化管理和分布式存儲(chǔ),規(guī)避了近優(yōu)容錯(cuò)路徑存儲(chǔ)模型在更新過(guò)程中的大量信息交換開銷。模擬實(shí)驗(yàn)結(jié)果顯示在確保滿足局部k維子立方連通約束條件下,算法產(chǎn)生的通信開銷優(yōu)于相關(guān)文獻(xiàn)中的方法。
　　針對(duì)基于路徑的多播通信中大量目標(biāo)節(jié)點(diǎn)情況下對(duì)路徑長(zhǎng)度進(jìn)行優(yōu)化的問(wèn)題,提出了一種基于極大目標(biāo)

6、節(jié)點(diǎn)分布密度的多播路徑構(gòu)造策略(MDPMP)和基于蟻群的多播路徑構(gòu)造算法(AMPA)。MDPMP利用目標(biāo)節(jié)點(diǎn)分布密度不均勻性質(zhì)進(jìn)行子立方體劃分,從而構(gòu)造多播路徑。仿真實(shí)驗(yàn)數(shù)據(jù)顯示出在目標(biāo)節(jié)點(diǎn)較多情形下,算法輸出路徑長(zhǎng)度優(yōu)于相關(guān)文獻(xiàn)中的策略。為獲得更短的多播路徑,引入蟻群算法來(lái)求取子立方體劃分問(wèn)題(其為組合優(yōu)化問(wèn)題)的優(yōu)化解,并以此建立多播路徑,仿真實(shí)驗(yàn)數(shù)據(jù)表明路徑長(zhǎng)度得到了減小。進(jìn)一步,論文通過(guò)把MDPMP和AMPA相結(jié)合的方式給出了分

7、布式蟻群優(yōu)化策略,有效緩解了蟻群算法引入較大計(jì)算時(shí)間復(fù)雜度問(wèn)題。實(shí)驗(yàn)獲得的數(shù)據(jù)顯示,相對(duì)于源節(jié)點(diǎn)計(jì)算路由策略,分布式優(yōu)化算法對(duì)優(yōu)化結(jié)果的影響在可接受范圍之內(nèi)。
　　以減小節(jié)點(diǎn)不相交路徑通信策略的路徑長(zhǎng)度為目標(biāo),提出了一種一對(duì)多目標(biāo)節(jié)點(diǎn)不相交容錯(cuò)優(yōu)化路徑算法和一對(duì)一不相交容錯(cuò)雙路徑算法。一對(duì)多目標(biāo)節(jié)點(diǎn)不相交容錯(cuò)優(yōu)化路徑算法利用近優(yōu)容錯(cuò)路徑存儲(chǔ)模型優(yōu)化生成多條不相交路徑,其在最長(zhǎng)路徑上限和平均路徑長(zhǎng)度兩方面均優(yōu)于已有算法。然后,基于一