抗毀WDM光網(wǎng)絡中的保護算法研究.pdf

1、WDM(Wavelength-Division Multiplexing)技術的出現(xiàn)使得一根光纖可以提供巨大的帶寬。在基于WDM技術的光網(wǎng)絡中，一根光纖的失效會導致大量數(shù)據(jù)的丟失。對WDM光網(wǎng)絡的生存性進行深入研究具有重要的價值。網(wǎng)絡生存性技術主要分為保護和恢復兩大類。保護是指事先為業(yè)務分配好保護資源，當故障發(fā)生時，業(yè)務可以利用這些分配好的保護資源來承載業(yè)務。恢復是指事先并不為業(yè)務分配保護資源，而是當故障發(fā)生之后再動態(tài)的尋找網(wǎng)絡資源來承

2、載受故障影響的業(yè)務。由于保護設計時已經(jīng)為業(yè)務分配好了保護資源，因而保護設計具有較快的故障恢復時間。正是由于這一優(yōu)勢， 本文研究抗毀WDM網(wǎng)狀網(wǎng)中的保護設計問題，主要集中在以下幾個方面：抗毀WDM網(wǎng)狀網(wǎng)中的分段保護設計問題、SRLG(Shared Risk Link Group)約束下的保護設計問題、支持區(qū)分可靠度的保護設計問題、多播的保護設計等問題。 分段保護是一種新的保護方式。它不但具有較高的資源利用率，而且具有較短的

3、恢復時間。 本文第二章研究抗毀WDM網(wǎng)狀網(wǎng)中的分段保護設計問題。主要貢獻在于： 1)在分段保護當中，工作路被分成了多個工作路段，而每條工作路段都被一個保護路段保護起來。通常情況下，兩個工作路段會有一部分相互重疊。這樣，工作路上的一些鏈路就會同時被兩個保護路段保護起來。在為每個保護路段預留資源的時候，傳統(tǒng)上只考慮這個保護路段對應的工作路段的情況而不關心這條工作路段與其它工作路段的關系。這樣就會出現(xiàn)兩個保護路段同時為某條鏈路

4、預留資源的情況，從而出現(xiàn)不必要的資源浪費。針對這一問題，本文提出了一種有效的減少保護資源的保護算法并分析對比了其性能。 2)另一方面，雖然分段保護方式下計算出的保護路段大都比較短，但是有的情況下利用分段保護計算出的保護路段依然比較長，從而不能真正達到縮短恢復時間的目的。因此，有必要對保護路段的跳數(shù)進行限制，使得每一條保護路段的跳數(shù)都限制在某個給定的門限之內(nèi)。本文研究了保護路段跳數(shù)有限制的分段保護問題并提出了一種基于分段的保護算法

5、，同時分析了其性能。 在抗毀WDM網(wǎng)狀網(wǎng)中引入SRLG概念之后，為一個源宿節(jié)點對計算一對SRLG分離的路徑對是NP-C的。因此，通常的做法是首先為源宿節(jié)點對計算一條工作路，將工作路上的所有鏈路以及那些跟工作路有相同SRLG的鏈路全部從網(wǎng)絡中刪除后，再計算一條源宿節(jié)點對之間的保護路。在工作路確定的情況下，有時可能找不到跟工作路SRLG分離的保護路。這就是所謂的“陷阱(Trap)”問題。陷阱既有可能是由實際的物理拓撲決定的，也有可能

6、是資源匱乏或者資源分配不合理而引起的。 本文第三章研究抗毀WDM網(wǎng)狀網(wǎng)中SRLG約束下的保護設計問題。主要貢獻在于： 1)一種有效解決“陷阱”問題的方式是分段保護。然而，對于究竟需要多少個段才能夠有效的解決“陷阱”的問題，還沒有見到相應的研究。本文研究發(fā)現(xiàn)在絕大多數(shù)情況下(99％)只需利用2個保護段就可以有效的解決“陷阱”問題。據(jù)此，本文進一步提出了一種只利用兩個保護段來保護工作路的算法并分析對比了其性能。 2)

7、由于“陷阱”有可能是因為資源分配不合理而導致的。因此，為連接請求合理的分配資源就變得十分重要。為此，本文將業(yè)務量工程的思想引入了SRLG約束下的保護設計當中并提出了一種基于業(yè)務量工程的保護設計算法來達到這一目的。為連接請求提供不同可靠等級的服務是光網(wǎng)絡發(fā)展的趨勢。為了實現(xiàn)上述目標，必須要根據(jù)連接請求的可靠度來為其計算合適的路由。 第四章研究了抗毀WDM網(wǎng)狀網(wǎng)中支持區(qū)分可靠度的保護設計問題。主要貢獻在于： 1)提出了兩種在

8、單鏈路失效模型下不允許資源共享的近似算法。第一種近似算法通過構造一個輔助圖，可以一次性找到路由連接請求需要的所有資源，避免了傳統(tǒng)算法需要分步計算的缺點；而第二種近似算法首先為連接請求計算一條工作路，然后構造一個輔助圖并在輔助圖中為連接請求計算滿足可靠度要求的路由。兩種近似算法相比較，第一種算法的近似程度要好，但是需要較高的計算復雜度。 2)提出了一種在單鏈路失效模型下允許資源共享的啟發(fā)式保護設計算法。 3)提出了一種在獨

9、立失效模型下不允許資源共享的啟發(fā)式保護設計算法。該算法允許利用多個保護路段來提高路由的可靠度，從而有效的克服了傳統(tǒng)算法只允許利用一個保護路段來提高路由可靠度的缺點。 由于WDM網(wǎng)絡能夠提供巨大的帶寬，這使得一些帶寬需求較高的多播業(yè)務應運而生。在基于光樹的多播路由當中，一條鏈路失效意味著同時會有多個目的節(jié)點不能正常接收數(shù)據(jù)。因此，多播的生存性路由問題在近年來成為了一個研究熱點。 第五章研究了抗毀WDM網(wǎng)狀網(wǎng)中多播的保護設計

10、問題。主要貢獻在于： 1)研究了多播之間在不可以共享保護資源的情況下，多播樹給定時如何為多播樹計算保護資源的問題并提出了相應的算法。計算機仿真結果表明，本文提出的算法具有比文獻中已有算法更好的性能(如較低的阻塞概率、較小的保護代價等)。 2)由于為多播請求計算路由的問題是NP-c的，因而文獻中大都是提出一些啟發(fā)式算法。這就意味著計算出的路由會有冗余資源。本文第一次提出這一問題并提出了一種有效減少冗余資源的算法。計算機仿真