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

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

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

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

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

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

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

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

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

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

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