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

1、超立方體是一種具有優(yōu)良性質(zhì)的拓撲,它具有高度冗余通信路徑與強容錯通信能力、結構對稱引入的自嵌入性、便于增加節(jié)點的可擴展性、網(wǎng)絡尋路算法簡潔性等優(yōu)點。并且其它多種類型拓撲網(wǎng)絡均可以便捷的與之相結合形成復合型拓撲,從而該型拓撲成為了高性能并行計算機系統(tǒng)設計中最具吸引力的網(wǎng)絡模型之一。
　　應用超立方體作為拓撲連接方式的并行計算機系統(tǒng)性能在很大程度上取決于其所采用的多播路由策略,其主要包括多播通信策略,容錯多播通信策略和不相交路徑多播通

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

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

4、構造算法(LWC-MT)。利用樹型拓撲多播方案生成過程的分析結論及分簇模型,LWC-MT采用了以聚簇代價沿著最小增長方向進行聚簇操作的方法,對多播樹建立過程進行了優(yōu)化。仿真實驗結果也表明,該算法在通信開銷上優(yōu)于現(xiàn)存算法。
　　以在保證一定容錯通信能力條件下減小多播通信開銷為目標,提出了一種容錯多播路由策略(FT-MT)和基于局部k維子立方連通超立方體網(wǎng)絡的分布式容錯多播路由策略(DFT-MT)。FT-MT利用近優(yōu)容錯路徑存儲模型構

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

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

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