WDM光網(wǎng)絡(luò)中基于軟管模型的魯棒選路及抗毀研究.pdf

1、在對WDM（Wavelength Division.Multiplexing）光網(wǎng)絡(luò)進行規(guī)劃設(shè)計時，傳統(tǒng)的選路和抗毀方案都需要給出一個明確的業(yè)務(wù)量矩陣。然而近年來，隨著Internet數(shù)據(jù)業(yè)務(wù)量的爆炸式增長以及新興寬帶業(yè)務(wù)的不斷涌現(xiàn)，運行于光層之上的分組數(shù)據(jù)會出現(xiàn)大幅度變化的情況，所以在實際運用中很難預(yù)測或估計出點到點之間具體的業(yè)務(wù)流量大小。因此，十分有必要研究帶寬需求信息不確知情況下的魯棒選路和抗毀問題，以適應(yīng)其高速增長和動態(tài)變化。軟

2、管（Hose）不確定業(yè)務(wù)量模型最早出現(xiàn)在虛擬專用網(wǎng)（VPN，Virtual PrivateNetwork）的研究中。該模型并未指定一個完整的業(yè)務(wù)量矩陣，僅對流入和流出各節(jié)點的合成業(yè)務(wù)量（即業(yè)務(wù)量矩陣的“行和”以及“列和”）的上限進行約束。由于不需要具體描述網(wǎng)絡(luò)中的業(yè)務(wù)分布情況，因此軟管模型大大降低了業(yè)務(wù)量估計的難度，同時也提高了設(shè)計的靈活性。本文研究Hose模型在WDM光網(wǎng)絡(luò)中的優(yōu)化問題，主要圍繞以下兩個方面展開：①基于Hose模型的魯

3、棒選路問題；②基于Hose模型的魯棒抗毀研究。
　　 本文的創(chuàng)新點主要包括五點。第一，研究了Hose不確定業(yè)務(wù)量模型下的靜態(tài)魯棒選路問題。與以往解決方案的區(qū)別在于，本論文并不僅僅考慮如何減少鏈路開銷，而是更為全面地對影響網(wǎng)絡(luò)代價的主要因素（包括鏈路開銷和節(jié)點交換開銷）進行考查，提出了比現(xiàn)有解決方案更節(jié)約網(wǎng)絡(luò)資源的啟發(fā)式算法。第二，在Hose模型的框架下，作者研究了如何利用部分確知的點到點的業(yè)務(wù)需求信息來實現(xiàn)魯棒優(yōu)化選路的問題，提

4、出了一種新的選路策略，并給出了相應(yīng)的啟發(fā)式算法。該算法有效解決了現(xiàn)有魯棒選路方案時延和抖動較大的問題。第三，探討了Hose模型下的動態(tài)Qos（Quality of Serive，服務(wù)質(zhì)量）選路問題，并提出了相應(yīng)的啟發(fā)式算法。該算法根據(jù)當(dāng)前連接請求的服務(wù)等級、當(dāng)前網(wǎng)絡(luò)中業(yè)務(wù)的傳輸情況以及各條鏈路上空閑波長的數(shù)目動態(tài)地調(diào)整路由。與現(xiàn)有的動態(tài)魯棒選路算法相比，本文所提算法具有更加優(yōu)越的性能。第四，研究了WDM網(wǎng)狀網(wǎng)中的魯棒單鏈路抗毀設(shè)計問題，

5、并提出了兩種共享保護啟發(fā)式算法。仿真結(jié)果表明，兩種算法在各自的應(yīng)用范圍內(nèi)均具有比較明顯的性能優(yōu)勢：相對于以前的魯棒抗毀算法，它們在開銷和恢復(fù)時間方面都有較為明顯的改善。第五，探討了基于動態(tài)Hose模型的多失效生存性問題。最主要的思路有兩點：⑴采用分級保護；⑵引入“危險程度”的概念，在為連接請求建立工作和保護路時避開危險程度高的網(wǎng)絡(luò)部件。按照這兩條思路，作者提出了相應(yīng)的啟發(fā)式算法，并通過仿真驗證了其有效性。
　　 本文第二章從三個

6、方面討論WDM網(wǎng)狀網(wǎng)在Hose業(yè)務(wù)量模型下的魯棒選路問題：⑴Hose模型下的靜態(tài)魯棒選路問題；⑵業(yè)務(wù)量矩陣部分確知（指部分網(wǎng)絡(luò)節(jié)點對之間的業(yè)務(wù)需求大小已知）情況下的魯棒選路問題；（3）Hose模型下的動態(tài)魯棒選路問題。對于問題⑴，作者以全網(wǎng)代價最小為目標(biāo)，建立了兩種分別基于單路徑選路（Single Path Routing，SPR）路由結(jié)構(gòu)以及Valiant負載平衡（ValiantLoad-balancing，VLB）路由結(jié)構(gòu)的數(shù)學(xué)規(guī)劃

7、（MP，Mathematical Programming）模型。通過對數(shù)學(xué)模型的求解，可以獲知波長、光收發(fā)器以及波長轉(zhuǎn)換器等資源的最佳配備。由于WDM網(wǎng)絡(luò)中的魯棒優(yōu)化選路問題是NP-完全（NP-complete，NPC）問題，因此作者又提出了兩種基于SPR和VLB的啟發(fā)式算法--IBFS（IterativeBreadth-first Search）算法和MNC（Maximizing Network Capability）算法。計算機仿真

8、表明，兩種算法都具有良好的性能，而MNC算法則具有更好的可擴展性，在大規(guī)模網(wǎng)絡(luò)中性能明顯優(yōu)于以往的方案。對于問題⑵，根據(jù)對業(yè)務(wù)量變化的觀察，作者在VLB的基礎(chǔ)上提出了適應(yīng)性負載平衡（Adaptive Load-balancing，ALB）機制，并給出了相應(yīng)的啟發(fā)式算--ADT（Adding Direct Traffic）算法。適應(yīng)性負載平衡機制的核心思想就是利用已知的點到點業(yè)務(wù)量信息，盡可能少地調(diào)整VLB所建立起來的兩跳虛拓撲，使更多業(yè)

9、務(wù)通過一跳路由的方式進行傳輸，從而達到降低時延和抖動的目的。仿真結(jié)果表明，ALB在具有高吞吐量的同時能提供比VLB更好的服務(wù)質(zhì)量。對于問題⑶，作者考慮全連接邏輯拓撲的情況，提出了DDALB（Differentiated Dynamic Adaptive Load-balancing）啟發(fā)式算法。
　　 本文第三章到第五章研究WDM網(wǎng)狀網(wǎng)在Hose不確定模型下的魯棒抗毀問題。其中第三章和第四章分別研究單鏈路失效（Single-li

10、nk Failure）和相關(guān)鏈路失效（Correlated-link Failure）情況下的抗毀設(shè)計問題，而第五章則對多網(wǎng)絡(luò)部件失效（Multiple Failures）時的抗毀問題進行探討。為解決單鏈路失效，作者提出了兩種分別基于VPN樹路由和Valiant負載平衡機制的共享分段保護（Shared SegmentProtection，SSP）啟發(fā)式算法叫-TSSP（Tree-based Shared-segment Protecti

11、on）算法和VLB-SSP（VLB-based Shared-segment Protection）算法。在資源配置方面，TSSP算法通過降低工作樹的葉子節(jié)點（即樹型拓撲中度為1的節(jié)點）數(shù)來減小工作路徑（Work Path，WP）和保護路徑（Backup Path，BP）的數(shù)目，從而有效地利用資源；而VLB-SSP則通過最小化全網(wǎng)代價配置工作和保護波長，以達到減小開銷的目的。在故障恢復(fù)方面，兩種算法均采用了分段保護機制，因此恢復(fù)速度也較

12、快。
　　 對于相關(guān)鏈路抗毀，本文的研究分為以下兩個方面。⑴針對雙鏈路失效的抗毀設(shè)計問題，作者提出了啟發(fā)式保護算法-DVLBSP（Differentiated VLB SharedProtection）算法。該算法遵循分級保護（Differentiated Protection）的思想計算保護路徑，只為不滿足給定可靠性要求的工作路徑尋找保護路徑；同時還考慮到了業(yè)務(wù)模型與網(wǎng)絡(luò)拓撲對全網(wǎng)代價的影響，并結(jié)合共享保護的思想配置保護波長。

13、仿真結(jié)果表明，DVLBSP算法實現(xiàn)了開銷與可靠性之間的較好折衷。⑵針對共享風(fēng)險鏈路組（Shared Risk Link Group，SRLG）的抗毀問題，作者提出了PSPPKT（PartialSRLG-disjoint Protection with Partially Known Traffic）啟發(fā)式算法，并通過計算機仿真論證了其有效性。對于多網(wǎng)絡(luò)部件失效的情況，將保護和恢復(fù)（Restoration）兩種抗毀方案結(jié)合起來，提出了基于