發(fā)布時間：2024-06-29 14:35

　　k最短路徑應用在大數(shù)據(jù)中心和高性能計算集群網(wǎng)絡中具有低延遲,高帶寬等優(yōu)點,因而受到研究人員的廣泛關注。為了實現(xiàn)網(wǎng)絡節(jié)點在k最短路徑策略中信息的可靠傳遞,本文研究鏈路失效模型下k最短路徑的可靠性和期望路徑長度問題,主要結論如下:1.本文考慮了節(jié)點可靠,鏈路可能失效的可靠性模型中,k最短路徑的等長路徑選擇問題,并將等長路徑的選擇問題轉化為一個可靠性優(yōu)化問題。最終提出了精確算法和基于蒙特卡洛模擬的近似算法求解該問題,實例表明了近似算法的有效性。2.本文建立了期望k最短路徑長度的參數(shù)去衡量網(wǎng)絡性能,并證明了廣義德布魯因圖的期望k最短路徑長度擁有近似最優(yōu)的性能。仿真結果有效地驗證了理論分析。

【文章頁數(shù)】：41 頁

【學位級別】：碩士

【部分圖文】：

圖２．１可靠性算法示意圖間??Ｆｉ．?２．１?Ａｎ?ｉｌｌｕｓｔｒａｔｉｏｎ?ｆｏｒ?ｒｅｌｉａｂｉｌｉｔａｌｏｒｉｔｈｍｓ?Ｊ２３１??

鏈路??的集合，Ｐ是每條鏈路獨立正常運行的概率。詳細假設如下：??（１）網(wǎng)絡中的每條鏈路都以相同的概率９?＝?１－０失效。??（２）網(wǎng)絡中的每個節(jié)點都是完美的。??（３）所有鏈路失效都是獨立的。??２．２．１料可靠性的精確算法??本文主要研宄的是可靠性（兩終端可靠性），即考慮給定....

圖２．２因子定理示意圖Ｍ??Ｆｉｇ．?２．２?Ａｎ?ｉｌｌｕｓｔｒａｔｉｏｎ?ｆｏｒ?ｆａｃｔｏｒｉｎｇ?ｄｅｃｏｍｐｏｓｉｔｉｏｎ?ａｌｇｏｒｉｔｈｍ?１２３１??

華東理工大學碩士學位論文?第７頁??（１）容斥原理算法＿２５］［２６］??容斥原理算法主要利用概率論的相關理論。其中￡；，￡；，．．．，￡：表示《個事件，則??Ｅ＇，Ｅ２，…，瓦中至少有一個事件發(fā)生的概率公式：??ＷＧ）?＝?Ｐｒ％?Ｕ?￡＂２?Ｕ?…Ｕ??＝Ｚｋ?ＰＫ＆）?－?....

圖２．３網(wǎng)絡Ｇ和子網(wǎng)絡：Ｇｉ）網(wǎng)絡＝?１，＜?＝?４?（的子網(wǎng)絡Ｗ?（ｃ）子網(wǎng)絡Ｇ／??Ｆｉｇ．?２．３?Ａ?Ｎｅｔｗｏｒｋ?Ｇ?ａｎｄ?ｓｕｂｎｅｔｗｏｒｋｓ：ａ）?Ａ?ｎｅｔｗｏｒｋ?Ｇ?ｗｉｔｈ?ｓ?＝?１?ａｎｄ?ｔ?＝?４（ｂ）Ａ．?ｓｕｂｎｅｔｗｏｒｋ?Ｇ２１?（ｃ）?Ａ?ｓｕｂｎｅｔｗｏｒｋ??

．１?ｔ最短可靠路徑??經(jīng)典的ｔ最短路徑問題作為最短路徑問題的泛化，通過尋求網(wǎng)絡源節(jié)點與終端節(jié)??點ｆ之間的最短路徑，次短路徑，次次短路徑，．．．，直到找到第＆短的路徑，最終形成??灸最短路徑集合，提供給用戶用于支持決策。經(jīng)典的Ａ最短路徑在選擇第／（１ＵＳ幻短路??徑的時候，重點....

圖３．１?８個節(jié)點，點度為３的ＧＤＢＧ?（８，?３）．??Ｆｉｇ．?３．１．?ＧＤＢＧ?（８，?３）?ｗｉｔｈ?８?ｎｏｄｅｓ?ａｎｄ?３?ｄｅｇｒｅｅｓ?ｏｆ?ｅａｃｈ?ｎｏｄｅ．??

期望Ａ最短路徑長度的下界。接下來，我們將會考慮廣義德布魯因圖的期望ｉｔ最短路徑??長度。??３，２．２廣義德布魯因圖的期望最短路徑長度分析??廣義德布魯因圖（Ｇｅｎｅｒａｌｉｚｅｄ?Ｄｅ?Ｂｒｕｉｊｎ?Ｇｒａｐｈ，?ＧＤＢＧ）是一種特殊的有向正則圖，??和隨機正則圖不同，它是一種....

本文編號：3997700