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

1、隨著社會(huì)經(jīng)濟(jì)的發(fā)展，人們對(duì)通信業(yè)務(wù)的需求體現(xiàn)出高層次和多樣化，這對(duì)通信網(wǎng)絡(luò)的容量提出了巨大的挑戰(zhàn)，而光纖通信技術(shù)的出現(xiàn)給通信領(lǐng)域帶來了蓬勃發(fā)展的機(jī)遇。目前光纖通信中單波長(zhǎng)傳輸速率已達(dá)到40Gbit/s，進(jìn)一步提高單波長(zhǎng)傳輸速率將受到半導(dǎo)體技術(shù)的制約，因此，波分復(fù)用WDM(Wavelength Division Multiplexing)技術(shù)成為了光纖傳輸網(wǎng)絡(luò)增容的主要技術(shù)手段，該技術(shù)的發(fā)展大大提高了通信網(wǎng)絡(luò)的傳輸容量，成為了下一代骨干網(wǎng)

2、絡(luò)的核心傳輸方式。然而在WDM網(wǎng)狀光網(wǎng)絡(luò)中，網(wǎng)絡(luò)的故障(如光纖斷裂，節(jié)點(diǎn)失效等)會(huì)導(dǎo)致大量的業(yè)務(wù)中斷，因此抗毀性設(shè)計(jì)就顯得異常重要。WDM網(wǎng)狀光網(wǎng)絡(luò)的抗毀性技術(shù)主要分為保護(hù)和恢復(fù)兩大類：保護(hù)是指事先為業(yè)務(wù)預(yù)留備份資源，當(dāng)故障發(fā)生后，業(yè)務(wù)可以被快速地切換到預(yù)留的備份資源上進(jìn)行承載；恢復(fù)是指事先不為業(yè)務(wù)預(yù)留備份資源，當(dāng)網(wǎng)絡(luò)發(fā)生故障后，再動(dòng)態(tài)地尋找網(wǎng)絡(luò)資源來承載受影響的業(yè)務(wù)。由于保護(hù)技術(shù)可以實(shí)現(xiàn)更快的業(yè)務(wù)恢復(fù)，這也更符合WDM網(wǎng)狀光網(wǎng)絡(luò)的抗毀

3、性要求，因此本文主要研究了WDM網(wǎng)狀光網(wǎng)絡(luò)的保護(hù)設(shè)計(jì)問題，內(nèi)容主要包括以下幾個(gè)方面：抗毀WDM網(wǎng)狀光網(wǎng)絡(luò)中的分段保護(hù)設(shè)計(jì)問題、支持區(qū)分可靠性的保護(hù)設(shè)計(jì)問題、基于SRLG約束的保護(hù)設(shè)計(jì)問題和業(yè)務(wù)恢復(fù)時(shí)間受限制的保護(hù)設(shè)計(jì)問題。 WDM網(wǎng)狀光網(wǎng)絡(luò)中的保護(hù)按照路由方式的不同可以分為通路保護(hù)、鏈路保護(hù)和分段保護(hù)。分段保護(hù)結(jié)合了通路保護(hù)和鏈路保護(hù)的特點(diǎn)，它可以在資源利用率和業(yè)務(wù)恢復(fù)時(shí)間之間取得良好的性能折中。目前很多研究分段保護(hù)的文獻(xiàn)采用的

4、方法都是首先對(duì)工作通路進(jìn)行分段，然后再為每個(gè)工作分段計(jì)算保護(hù)分段。這種分段方式缺乏靈活性，而且在對(duì)工作通路進(jìn)行分段的時(shí)候無法保證后續(xù)一定能計(jì)算出合適的保護(hù)分段。另外雖然利用分段保護(hù)所計(jì)算出的保護(hù)分段大都比較短，但是在共享保護(hù)策略下，仍然會(huì)有部分保護(hù)分段經(jīng)過很長(zhǎng)的路徑，這不利于實(shí)現(xiàn)快速的業(yè)務(wù)恢復(fù)。針對(duì)上述問題，本文的第二章研究了抗毀WDM網(wǎng)狀光網(wǎng)絡(luò)中的分段保護(hù)設(shè)計(jì)問題，主要貢獻(xiàn)包括：1)提出了一種遞歸式的分段保護(hù)算法，該算法采用遞歸的方式

5、逐跳計(jì)算保護(hù)分段，在確保找到保護(hù)分段后才會(huì)確定工作分段，同時(shí)在計(jì)算保護(hù)分段的時(shí)候考慮了跳數(shù)的限制，這樣可以避免計(jì)算出過長(zhǎng)的保護(hù)分段。2)雖然對(duì)保護(hù)分段的跳數(shù)進(jìn)行了限制，但并一定可以百分之百地縮短業(yè)務(wù)恢復(fù)時(shí)間，因?yàn)闃I(yè)務(wù)恢復(fù)時(shí)間不僅與保護(hù)分段的跳數(shù)有關(guān)，也與工作分段的跳數(shù)有關(guān)，因此本章又提出了一種共享分段保護(hù)算法，該算法采用了保護(hù)圈的概念，通過對(duì)每個(gè)保護(hù)圈跳數(shù)的限制來達(dá)到對(duì)工作分段和保護(hù)分段總跳數(shù)的限制，這樣就能更加有效地縮短業(yè)務(wù)恢復(fù)時(shí)間。

6、最后作者通過大量的仿真分析了算法的性能。 可靠性定義為在某個(gè)時(shí)間段內(nèi)，系統(tǒng)或連接正常工作的概率。根據(jù)不同的可靠性等級(jí)來為用戶提供保護(hù)，可以更加合理地分配網(wǎng)絡(luò)資源，因此本文的第三章研究了WDM網(wǎng)狀光網(wǎng)絡(luò)中支持區(qū)分可靠性的專用保護(hù)問題，主要貢獻(xiàn)包括了：1)分析了專用通路保護(hù)和專用分段保護(hù)模型下的可靠性計(jì)算問題，分析了專用保護(hù)模型下的業(yè)務(wù)恢復(fù)過程。2)提出了一種動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下的啟發(fā)式專用保護(hù)算法，該算法的核心思想是從目的節(jié)點(diǎn)出發(fā)，反向

7、逐跳計(jì)算保護(hù)分段，通過僅對(duì)工作通路上的某段進(jìn)行保護(hù)來提高整個(gè)連接的可靠性，以達(dá)到用戶要求。仿真結(jié)果表明了該算法對(duì)比通路保護(hù)可以節(jié)約更多的網(wǎng)絡(luò)資源并進(jìn)一步縮短業(yè)務(wù)恢復(fù)時(shí)間。3)針對(duì)前面提出的算法，本文作者又提出了一種改進(jìn)算法，主要針對(duì)分段的方式進(jìn)行了改進(jìn)，該算法的核心思想是從網(wǎng)絡(luò)中可靠性最低的鏈路開始，并向兩側(cè)擴(kuò)展，找到工作通路上最需要被保護(hù)的分段，再為該分段計(jì)算保護(hù)路，試圖利用最少的保護(hù)資源來使整個(gè)連接的可靠性達(dá)到要求。通過仿真對(duì)比，發(fā)

8、現(xiàn)改進(jìn)算法可以進(jìn)一步縮短保護(hù)路的跳數(shù)，降低阻塞率并縮短業(yè)務(wù)恢復(fù)時(shí)間。 在實(shí)際網(wǎng)絡(luò)中，光纖鏈路間由于共享了某些相同的物理設(shè)備(如光纜，隧道，旁路等)而具有了故障的關(guān)聯(lián)性，這點(diǎn)可以利用共享風(fēng)險(xiǎn)鏈路組SRLG(Shared Risk Link Groups)來表示?，F(xiàn)有文獻(xiàn)已經(jīng)證明了為源宿節(jié)點(diǎn)計(jì)算SRLG分離路徑對(duì)的問題是NP-C的，因此通常的做法都是先計(jì)算工作通路，然后再把工作通路上的所有鏈路以及網(wǎng)絡(luò)中所有與工作通路具有相同SRLG

9、的鏈路刪除掉，再在剩余的網(wǎng)絡(luò)中計(jì)算保護(hù)通路。在某些特定的情況下，即使網(wǎng)絡(luò)中存在SRLG分離的路徑對(duì)時(shí)，采用上面的方法也無法找到SRLG分離的路徑對(duì)，這就是所謂的“陷阱”問題。本文的第四章研究了抗毀WDM網(wǎng)狀光網(wǎng)絡(luò)中SRLG分離約束下的保護(hù)設(shè)計(jì)問題，作者采用了兩點(diǎn)措施來解決“陷阱”問題：1)利用K路由算法來計(jì)算多條候選工作通路，并試圖尋找與工作通路完全SRLG分離的保護(hù)通路，通過仿真分析得到在一般規(guī)模的網(wǎng)絡(luò)中，通常選取K=3就可以成功地計(jì)

10、算出完全SRLG分離的路徑對(duì)。2)在滿足足夠低的同時(shí)失效概率下，允許工作通路和對(duì)應(yīng)的保護(hù)通路之間有部分SRLG重疊，這點(diǎn)對(duì)于網(wǎng)絡(luò)中根本不存在完全SRLG分離路徑對(duì)時(shí)更加有效。保護(hù)通路之間的資源共享也考慮了同時(shí)失效的概率，即只要工作通路之間同時(shí)失效的概率足夠低，即使它們并不完全SRLG分離，也允許它們各自對(duì)應(yīng)的保護(hù)通路共享保護(hù)資源，這樣可以進(jìn)～步提高資源共享度，節(jié)約網(wǎng)路資源。 在WDM網(wǎng)狀光網(wǎng)絡(luò)中，保護(hù)設(shè)計(jì)的主要目的就是為了實(shí)現(xiàn)高

11、效快速的業(yè)務(wù)恢復(fù)，一些實(shí)時(shí)性要求較高的業(yè)務(wù)對(duì)故障后的業(yè)務(wù)恢復(fù)速度要求很高，因此業(yè)務(wù)恢復(fù)時(shí)間成為了衡量一個(gè)保護(hù)算法的重要性能指標(biāo)。對(duì)比端到端的通路保護(hù)，分段保護(hù)可以通過限制保護(hù)路的長(zhǎng)度來縮短業(yè)務(wù)恢復(fù)時(shí)間，而目前的很多文獻(xiàn)也都是通過對(duì)保護(hù)路的跳數(shù)進(jìn)行限制來控制業(yè)務(wù)恢復(fù)時(shí)間的，但這種處理只是一種盡力而為的方法，不能嚴(yán)格準(zhǔn)確地限制業(yè)務(wù)恢復(fù)時(shí)間。因此，本文的第五章研究了WDM網(wǎng)狀光網(wǎng)絡(luò)中業(yè)務(wù)恢復(fù)時(shí)間嚴(yán)格受限的保護(hù)設(shè)計(jì)問題。主要貢獻(xiàn)在于：1)詳細(xì)分

12、析了共享保護(hù)模型下的業(yè)務(wù)恢復(fù)過程，導(dǎo)出了業(yè)務(wù)恢復(fù)時(shí)間的計(jì)算公式，通過對(duì)網(wǎng)絡(luò)鏈路時(shí)延的特殊設(shè)置，并利用一種時(shí)延受限的最短路徑算法來計(jì)算候選保護(hù)分段，利用這些候選保護(hù)分段所實(shí)現(xiàn)的業(yè)務(wù)恢復(fù)時(shí)間嚴(yán)格滿足要求。2)在計(jì)算候選保護(hù)分段的同時(shí)考慮了保護(hù)資源的共享和SRLG分離的約束。3)結(jié)合已經(jīng)找到的候選保護(hù)分段，設(shè)計(jì)出一種輔助圖，利用該輔助圖計(jì)算出具有最小代價(jià)和的保護(hù)分段集合。綜合上述三點(diǎn)，本章提出了一種在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下的啟發(fā)式算法，用于計(jì)算業(yè)務(wù)恢