多域光網(wǎng)絡(luò)的保護(hù)算法-資源利用率

摘要隨著光網(wǎng)絡(luò)的快速開展，有關(guān)保護(hù)算法的研究逐漸由單域網(wǎng)絡(luò)轉(zhuǎn)移到多域網(wǎng)絡(luò)。多域光網(wǎng)絡(luò)保護(hù)算法的研究涉及拓?fù)渚酆?、路由策略等課題，具有一定的復(fù)雜性。本文介紹了WDM光網(wǎng)絡(luò)的根本概念，對(duì)相關(guān)生存性技術(shù)做了歸納總結(jié)，重點(diǎn)分析了共享分段保護(hù)技術(shù)，并且在已有的算法根底上提出了改良。最后通過仿真改良前和改良后的算法在網(wǎng)絡(luò)中的表現(xiàn)，比擬了兩者的性能差異。關(guān)鍵詞：WDM光網(wǎng)絡(luò)，多域，生存性，保護(hù)算法，共享分段保護(hù)ABSTRACTWiththerapiddevelopmentofopticalnetworks,researchontheprotectionofthealgorithmgraduallyshiftsfromsingle-domaintomulti-domain.Multi-domainopticalnetworkprotectionreferstosomecomplicatedtopicssuchastopologyaggregationandrouting.Inthispaper,thebasicconceptsabouttheWDMopticalnetworksisintroduced,asummaryofthesurvivalofthetechnologyisdone,thefocusoftheresearchisonthesegment-sharedprotection,andtheimprovementsbasedontheexistingalgorithmisputforward.Finally,throughthesimulationofthetwoalgorithmsinthenetwork'sperformance,wegetthedifference.Keywords:Opticalmeshnetworks,Multi-domains,Survivability,Segment-sharedprotection目錄第1章引言[21]中的回歸共享分段保護(hù)。局部文獻(xiàn)中由于假設(shè)了多域網(wǎng)絡(luò)的整體和局部信息的情況，實(shí)際局限在了單域網(wǎng)絡(luò)的問題中。此文獻(xiàn)中考慮的多域網(wǎng)絡(luò)是指有大量中間域的網(wǎng)絡(luò)，提出一種兩步啟發(fā)式算法。首先，多域網(wǎng)絡(luò)進(jìn)行拓?fù)渚酆献兂梢粋€(gè)緊湊的域間網(wǎng)，可以得到一個(gè)初步的路由。然后，在各個(gè)域中分別得到詳細(xì)的路由。聚合拓?fù)涞氖褂每梢员ＷC可測(cè)量性的限制。第一步路由可以通過貪婪算法或動(dòng)態(tài)規(guī)劃算法得到。在提供的解決方案中，工作分段和保護(hù)分段的長(zhǎng)度也是受到限制的，已經(jīng)知道故障恢復(fù)時(shí)間是由故障發(fā)現(xiàn)時(shí)間和保護(hù)分段激活時(shí)間組成的。前者是由工作分段長(zhǎng)度決定的而后者是由保護(hù)分段長(zhǎng)度決定的。因此，工作分段和保護(hù)分段的長(zhǎng)度限制將確?？焖俚幕謴?fù)。下面簡(jiǎn)要說明文獻(xiàn)[10]中的域間路由使用貪婪算法GROS(GreedyOverlappingShortsegmentsharedprotection)的路由過程。路由目標(biāo)在于將新連接的工作路和保護(hù)路消耗的總帶寬最小化，總帶寬可以表示為公式3-1。(3-1)在域間網(wǎng)絡(luò)(虛擬拓?fù)?中，可以等同于公式3-2。(3-2)在多域網(wǎng)絡(luò)中，通路可能會(huì)比擬長(zhǎng)。為了確?？焖俚幕謴?fù)，設(shè)置工作分段和保護(hù)分段的門限值分別為L(zhǎng)W和LB，即為分段長(zhǎng)度限制。兩步路由如下：域間步驟首先優(yōu)化(1)，其中虛鏈路和域間鏈路被賦予代價(jià)和，并且將工作長(zhǎng)度限制也考慮進(jìn)去。事實(shí)上，此時(shí)的路由問題已經(jīng)成為一個(gè)單域路由問題，任何OSSP的單域路由算法都可以使用，只要滿足虛擬鏈路的代價(jià)和分段長(zhǎng)度限制。下面簡(jiǎn)要說明GROS的流程。1〕找到用表示的源到目的最短工作路。2〕工作路被貪婪的分為分段，第一個(gè)分段從源節(jié)點(diǎn)開始。每一個(gè)分段的尾節(jié)點(diǎn)選擇原那么是在分段長(zhǎng)度限制LW下盡可能的取長(zhǎng)一些。然而，如果不能找到這樣的尾節(jié)點(diǎn)，那么指定離頭節(jié)點(diǎn)最近的節(jié)點(diǎn)為尾節(jié)點(diǎn)。從尾節(jié)點(diǎn)朝頭節(jié)點(diǎn)返回最小的跳數(shù)，直到找到一個(gè)節(jié)點(diǎn)度大于2的新節(jié)點(diǎn)，此節(jié)點(diǎn)是下一個(gè)分段的頭節(jié)點(diǎn)。這個(gè)過程持續(xù)到到達(dá)目的節(jié)點(diǎn)。3〕對(duì)于每一個(gè)先前確定的工作分段，找到用表示的工作分段端節(jié)點(diǎn)之間的最短保護(hù)分段，保護(hù)分段的長(zhǎng)度不能大于LB。域內(nèi)步驟對(duì)每一個(gè)分段對(duì)，工作分段的虛鏈路先映射成為相應(yīng)最小代價(jià)的域內(nèi)路徑。完整的工作分段得到以后，保護(hù)分段的虛鏈路也映射成為相應(yīng)最小代價(jià)的域內(nèi)路徑。需要說明的是為了確保工作分段和保護(hù)分段是別離的，需要在映射保護(hù)分段的時(shí)候排除工作分段的節(jié)點(diǎn)。每次使用最短路算法的映射只是在一個(gè)域內(nèi)，這樣可以很好地滿足可測(cè)量性要求。一個(gè)請(qǐng)求可能在域間路由的時(shí)候成功，但是在域內(nèi)路由的時(shí)候由于帶寬缺乏等或需要保證和工作分段別離等原因?qū)е掠騼?nèi)路由阻塞。為了防止這種情況，文中提出一種“Blocking-go-backoption〞的策略，即域間路由的迭代。該次路由只需要在域間路由之前將阻塞的虛鏈路去除，后續(xù)步驟和第一次一致。這樣，就可以防止重復(fù)前面的阻塞。需要指出的是，雖然“Blocking-go-back〞降低了阻塞率，但是會(huì)花費(fèi)更長(zhǎng)的時(shí)間。分段共享保護(hù)算法LSSP研究問題描述假定WDM網(wǎng)狀網(wǎng)的物理拓?fù)錇镚{,GL}(1r)，虛擬拓?fù)錇镚v{,GL}(1r)，兩個(gè)拓?fù)涠加蓚€(gè)域組成，其中，={GNr,INr,ILr,W}(1r),={GNr,VLr}(1r)，GL是連接不同域的網(wǎng)關(guān)節(jié)點(diǎn)的鏈路。考慮到網(wǎng)關(guān)節(jié)點(diǎn)之間的鏈路相對(duì)很少，可以配置成專用保護(hù)的模式，其保護(hù)不需要?jiǎng)討B(tài)路由計(jì)算。一些重要的符號(hào)表示如下所示：GNr:：域r的網(wǎng)關(guān)節(jié)點(diǎn)。每一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)都有一個(gè)路由表，其內(nèi)容包含域r的物理拓?fù)湫畔⒁约罢麄€(gè)多域網(wǎng)絡(luò)的虛擬拓?fù)湫畔ⅰNr：域r的內(nèi)部節(jié)點(diǎn)。每個(gè)內(nèi)部節(jié)點(diǎn)都與一個(gè)路由表，其內(nèi)容只包含域r的物理拓?fù)湫畔?。ILr和W：分別表示域r的內(nèi)部鏈路和每個(gè)鏈路上的波長(zhǎng)數(shù)目。既然內(nèi)部鏈路比網(wǎng)關(guān)節(jié)點(diǎn)之間的鏈路多得多，其保護(hù)需要?jiǎng)討B(tài)路由——共享保護(hù)。VLr：域r的虛擬鏈路。每個(gè)虛擬鏈路可以提前計(jì)算和確定，它包含一些物理鏈路并且表示了域r中兩個(gè)網(wǎng)關(guān)節(jié)點(diǎn)之間的路由。這里，主要研究針對(duì)每個(gè)域中最多有一條鏈路失效那么多域網(wǎng)絡(luò)中多鏈路失效的問題，也就是說，有Q個(gè)域的情況下，在同一時(shí)刻，最多有Q條鏈路失效。基于上述網(wǎng)絡(luò)模型，動(dòng)態(tài)路由分成兩步：工作路路由和保護(hù)分段路由。工作路路由分成域內(nèi)路由和域間路由。保護(hù)分段路由只需要域內(nèi)路由即可。路由過程的流程如圖3-3所示?？梢钥吹剑嘤蚬饩W(wǎng)絡(luò)中的路由問題主要集中在解決域間路由上。在LSSP中，將多域光網(wǎng)絡(luò)中的域間路由問題分成三大步來完成。第一步是通過比擬源節(jié)點(diǎn)到所有網(wǎng)關(guān)節(jié)點(diǎn)的路徑代價(jià)找到源網(wǎng)關(guān)節(jié)點(diǎn)。第二步是在通過拓?fù)渚酆系玫降奶撏負(fù)渲?，通過比擬源網(wǎng)關(guān)節(jié)點(diǎn)到目的域的所有網(wǎng)關(guān)節(jié)點(diǎn)的路徑代價(jià)找到目的網(wǎng)關(guān)節(jié)點(diǎn)。第三步那么為找出目的網(wǎng)關(guān)節(jié)點(diǎn)到目的節(jié)點(diǎn)最短路徑。在域間路由完成之后，再通過最短路算法將域間路由中得到的用虛鏈路表示的路徑映射成實(shí)際的物理路徑。從LSSP的路由步驟中可以看到，在尋找源網(wǎng)關(guān)節(jié)點(diǎn)時(shí)，是通過源節(jié)點(diǎn)到網(wǎng)關(guān)節(jié)點(diǎn)的路由比擬得到的。而域間路由的關(guān)鍵也在于找到源網(wǎng)關(guān)節(jié)點(diǎn)，這樣僅僅通過域內(nèi)的信息并沒有考慮整個(gè)網(wǎng)絡(luò)拓?fù)湫畔⒌那闆r下得到的源域網(wǎng)關(guān)節(jié)點(diǎn)是否是最優(yōu)的值得討論。所以從這方面出發(fā)，我們?cè)贚SSP算法的根底上提出了一些改良。詳細(xì)的算法分析見3.4。LSSP算法流程圖算法詳細(xì)描述詳細(xì)介紹算法之前，先說明算法中使用的符號(hào)含義。：從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的連接請(qǐng)求n：的工作路，可以是域內(nèi)或域間。：在域r中從節(jié)點(diǎn)v1到節(jié)點(diǎn)v2的分段。如果s和d都在同一個(gè)域內(nèi)，那么=。：在域r中與對(duì)應(yīng)的保護(hù)分段。如果s和d都在同一個(gè)域中，那么=。：鏈路e上的自由波長(zhǎng)數(shù)：鏈路e上的工作波長(zhǎng)數(shù)。：鏈路e上的保護(hù)波長(zhǎng)數(shù)。(ILr)：工作分段經(jīng)過鏈路f并且保護(hù)分段經(jīng)過鏈路e的工作分段集合。：集合中的元素個(gè)數(shù)。：鏈路e的代價(jià)，是由當(dāng)前網(wǎng)絡(luò)信息決定的。：虛鏈路e的代價(jià)。如果該虛鏈路可以成功映射成為物理鏈路，那么取值為1，否那么取值為0。下面詳細(xì)介紹啟發(fā)式過程。輸入：={GNr,INr,ILr,W}(1r),={GNr,VLr}(1r)和輸出：工作路和保護(hù)路；或者工作分段及其在各個(gè)域中對(duì)應(yīng)的保護(hù)分段。第一步：如果，讓，轉(zhuǎn)入第二步；否那么轉(zhuǎn)入第五步。第二步：通過公式(3-3),得到鏈路的鏈路代價(jià)，計(jì)算出域r內(nèi)從v1到v2的最小鏈路代價(jià)和的工作路，如果找到，轉(zhuǎn)入第三步；否那么返回空值。(3-3)第三步：通過公式(3-4)，得到計(jì)算保護(hù)分段時(shí)鏈路的代價(jià)。如果可以找到，轉(zhuǎn)入第四步；否那么返回空值。表示新增共享資源值，其計(jì)算在共享保護(hù)的實(shí)現(xiàn)中詳細(xì)說明。(3-4)第四步：如果，讓，并且返回得到的解；否那么，記錄下此分段并在域m選擇下一個(gè)工作分段。如果所有的工作分段都選擇完畢，那么返回解。否那么，讓并返回第三步。第五步：在域r中，通過公式(3-3)得到的鏈路代價(jià)計(jì)算從源節(jié)點(diǎn)s到網(wǎng)關(guān)節(jié)點(diǎn)g的最小鏈路代價(jià)的工作分段。如果找到，那么轉(zhuǎn)到第六步；否那么返回空值。第六步：通過公式(3-5)的得到的鏈路代價(jià)，可以在虛拓?fù)渲杏?jì)算出從源網(wǎng)關(guān)節(jié)點(diǎn)到目的網(wǎng)關(guān)節(jié)點(diǎn)的最小鏈路代價(jià)路徑M。如果可以找到M,那么轉(zhuǎn)到第七步；否那么返回空值。(3-5)第七步：通過公式(3-3)鏈路的代價(jià)可以得到域t中從網(wǎng)關(guān)節(jié)點(diǎn)k到目的節(jié)點(diǎn)d的最小鏈路代價(jià)的工作分段。如果可以找到，那么轉(zhuǎn)到第八步；否那么返回空值。第八步：將虛路徑M映射成實(shí)際的工作分段。將所有工作分段連接起來那么形成工作路。選擇源節(jié)點(diǎn)和源網(wǎng)關(guān)節(jié)點(diǎn)，讓，返回第三步。物理拓?fù)浜吞撏負(fù)湓诒Ｗo(hù)算法的研究中，網(wǎng)絡(luò)拓?fù)涞妮斎胧侵匾囊粋€(gè)環(huán)節(jié)。拓?fù)湮募袷揭欢ǔ潭壬蠒?huì)影響算法執(zhí)行的策略。由于是多域光網(wǎng)絡(luò)的保護(hù)問題，拓?fù)浞殖晌锢硗負(fù)浜吞撏負(fù)鋬煞N。在本文的算法實(shí)現(xiàn)中，將物理拓?fù)浜吞撏負(fù)浞旁谝粋€(gè)拓?fù)湮募?，?jiǎn)化了輸入文件，但是對(duì)拓?fù)湮募母袷阶龀隽艘恍┮?guī)定以滿足讀取拓?fù)湫畔⒌男枰斎胪負(fù)湮募袷饺绫?-1所示：拓?fù)湮募袷芥溌稩D源節(jié)點(diǎn)－目的節(jié)點(diǎn)域ID鏈路屬性Link00－110(false)例如中表示鏈路0的源節(jié)點(diǎn)為0，目的節(jié)點(diǎn)為1，其所在域?yàn)橛?，鏈路屬性為0(false)表示是實(shí)際物理鏈路，為1(true)表示是域間鏈路或虛鏈路。鏈路屬性為true的時(shí)候應(yīng)該考慮到兩種情況：一種是域間鏈路，域間鏈路是專用保護(hù)，但是增減自由波長(zhǎng)數(shù)目的時(shí)候都應(yīng)該考慮到，但是注意因?yàn)橛蜷g鏈路使用的是專用保護(hù)，那么不考慮共享波長(zhǎng)數(shù)目的變化。另一種是虛鏈路，涉及到刷新波長(zhǎng)數(shù)和刷新連接編號(hào)數(shù)的時(shí)候都不應(yīng)該考慮。并且值得一提的是，工作路路由和保護(hù)路路由不包含這種虛鏈路。如果包含，那么說明路徑映射的時(shí)候出現(xiàn)了問題。最短路算法實(shí)現(xiàn)中，會(huì)遍歷所有節(jié)點(diǎn)。這樣就存在兩種情況來執(zhí)行最短路算法。一種是虛拓?fù)渲械乃泄?jié)點(diǎn)，另一種是單域物理拓?fù)渲械乃泄?jié)點(diǎn)?？梢?，需要區(qū)分節(jié)點(diǎn)屬性來實(shí)現(xiàn)這兩種情況。為了得到節(jié)點(diǎn)的屬性，可以利用域ID這一參數(shù)。如果鏈路是域間鏈路，那么設(shè)置域ID為0，如果讀取到域ID的值為0就可以知道該鏈路的源節(jié)點(diǎn)和目的節(jié)點(diǎn)都是網(wǎng)關(guān)節(jié)點(diǎn)，這些就是虛拓?fù)淅镒疃搪匪惴ㄖ斜闅v的節(jié)點(diǎn)，其他的那么是物理拓?fù)淅镒疃搪匪惴ㄖ斜闅v的節(jié)點(diǎn)。編程實(shí)現(xiàn)中，通過上述拓?fù)湮募袷剑恍枰勒麄€(gè)拓?fù)滏溌返膶傩?，就可以方便的得到虛拓?fù)浜臀锢硗負(fù)洹＠?，?dāng)需要虛拓?fù)涞臅r(shí)候，遍歷鏈路，只要鏈路屬性為0(false),那么將其鏈路代價(jià)設(shè)置為無窮大，顯然使用最短路算法找路時(shí)代價(jià)為無窮大的鏈路不起作用，從而到達(dá)提取虛拓?fù)涞哪康?。同樣的原理，只需將除開域間鏈路和虛鏈路的其他鏈路代價(jià)設(shè)為無窮大，就可以獲得物理拓?fù)洹Ｉ鲜龇椒ê?jiǎn)化了多域網(wǎng)絡(luò)的拓?fù)湮募膹?fù)雜性，提高了效率。連接的動(dòng)態(tài)產(chǎn)生為了使仿真結(jié)果更接近實(shí)際情況，采用了動(dòng)態(tài)產(chǎn)生連接請(qǐng)求的方式。已經(jīng)知道，網(wǎng)絡(luò)中的連接請(qǐng)求到達(dá)時(shí)刻服從泊松分布，持續(xù)時(shí)間服從負(fù)指數(shù)分布。下面附上產(chǎn)生泊松流，處理連接請(qǐng)求的偽碼。/*產(chǎn)生泊松流、到達(dá)事件及離開事件的重要偽碼*/begin/*變量初始化*/stream(6);//初始化隨機(jī)產(chǎn)生函數(shù)的時(shí)間種子Simulation_Clock=0.0;//模擬時(shí)鐘清0/*到達(dá)事件初始化：產(chǎn)生第一次到達(dá)事件及離開事件表，到達(dá)事件服從泊松分布*/First_Arrival_Interval=Exponential(1.0/Arrival_Rate_Lambda);Arrival_time=Simulation_Clock+First_Arrival_Interval;LeaveEvents.clear(); //離開事件表為空Stop_Alarm_On=FALSE; Leave_Event_Over=TRUE;/*主程序：調(diào)用定時(shí)程序以確定下次事件；調(diào)用相應(yīng)的子程序?qū)ο麓问录M(jìn)行處理*///根據(jù)發(fā)生時(shí)間確定下次事件的類型 找出最近結(jié)束的事件停止時(shí)間stop_timeif((stop._time)<Arrival_time){//Cond1LeavebeforeArrivalNext_Event=LEAVING;Simulation_Clock=stop_time;}elseif(stop_time>Arrival_time){//Cond2ArrivalbeforeLeaveNext_Event=ARRIVING;Simulation_Clock=stop_time;}else{//cond3Arrival=Leave,Killthecomputer! Next_Event=LEAVING; Simulation_Clock=stop_time; }/*調(diào)用下次事件對(duì)應(yīng)的子程序：到達(dá)或離開*///CallthesubroutineoftheNext_Eventswitch(Next_Event){caseARRIVING:Arriving_Event(); //調(diào)用到達(dá)事件處理模塊break;caseLEAVING:Leaving_Event(); //調(diào)用離開事件處理模塊Leave_Counter++;break;caseNOEVENT:break;}endwhileend到達(dá)事件處理子程序Arriving_Event()begin/*在處理當(dāng)前到達(dá)事件前，產(chǎn)生下一次到達(dá)事件發(fā)生的時(shí)間間隔，進(jìn)而計(jì)算下一次到達(dá)事件的發(fā)生時(shí)間*/Next_Arrival_Interval=Exponential(1.0/Arrival_Rate_Lambda);Arrival_time=Simulation_Clock+Next_Arrival_Interval;Choose_Demand(&src,&dst,&bandwidth);//確定到達(dá)事件的源、宿及帶寬需求等。/*保護(hù)計(jì)算局部，在此不詳細(xì)展開說明*/調(diào)用相應(yīng)保護(hù)算法對(duì)業(yè)務(wù)連接請(qǐng)求進(jìn)行工作路和備份路計(jì)算。Iffindarouteforthisdemandrequest /*成功找到路徑，更新網(wǎng)絡(luò)狀態(tài)分配相應(yīng)資源，產(chǎn)生離開事件*/Resource_Allocation();//分配資源Leave_Event_Over=FALSE;Service_Time=(double)exponential(1.0/Service_Rate_mu);leave_time=Simulation_Clock+Service_Time;構(gòu)造一新的離開事件結(jié)構(gòu);endifend離開事件處理子程序Leaving_Event()beginRead_Leave_event();//得到當(dāng)前離開事件 Release_Primary_Resource();//釋放該工作通路所占用網(wǎng)絡(luò)資源 Update_Backup_Resource(); //更新保護(hù)通路經(jīng)過的鏈路上的預(yù)留資源end共享保護(hù)的實(shí)現(xiàn)在共享分段保護(hù)中，為了確保在單鏈路或單節(jié)點(diǎn)失效的情況下100%的保護(hù)，只有在工作分段是鏈路和節(jié)點(diǎn)別離時(shí)，其共享分段才可以共享帶寬。圖3-4給出了解釋。情況(a)中，從v1到v2的工作分段請(qǐng)求帶寬為d1,從v5到v6的請(qǐng)求帶寬為d2，兩個(gè)工作分段是鏈路和節(jié)點(diǎn)別離的。因此，它們的保護(hù)分段可以共享鏈路(v4,v3)上的帶寬，這樣，兩個(gè)保護(hù)分段在這條鏈路上使用的帶寬就是max{d1,d2}。情況(b)中，兩個(gè)工作分段都經(jīng)過節(jié)點(diǎn)v7,所以它們的保護(hù)分段必須使用別離的保護(hù)帶寬，兩個(gè)保護(hù)分段在鏈路(v4,v3)上使用的帶寬就是d1+d2,顯然大于情況(a)中的使用帶寬。保護(hù)帶寬可以共享(a)和不能共享(b)例如下面對(duì)共享保護(hù)實(shí)現(xiàn)的理論加以說明。保護(hù)帶寬共享例如圖3-5(a)表示了鏈路e上的帶寬(波長(zhǎng)數(shù)目)結(jié)構(gòu)。顯然，鏈路e上的可以共享的保護(hù)帶寬是-。共享保護(hù)會(huì)存在兩種情況：1〕可以共享的帶寬小于等于連接請(qǐng)求帶寬d，鏈路e上需要額外的新增共享資源，如圖3-5(b)所示；2〕可以共享的帶寬大于連接請(qǐng)求帶款d，不需要額外的新增共享資源，那么，如圖3-5(c)所示?？梢缘玫焦?-6：(3-6)結(jié)合上述理論根底，我們可以得到計(jì)算保護(hù)分段時(shí)，確定全網(wǎng)鏈路的代價(jià)的方法。令E為全網(wǎng)鏈路集合，表示工作路經(jīng)過鏈路g共享保護(hù)路經(jīng)過鏈路l的所有業(yè)務(wù)帶寬之和，表示鏈路e上用于共享保護(hù)的資源，WP為業(yè)務(wù)的工作路，d為業(yè)務(wù)帶寬，為工作路上的鏈路集合,那么如果業(yè)務(wù)的工作路經(jīng)過鏈路e1，而業(yè)務(wù)的保護(hù)路經(jīng)過e2，那么e2上新增共享資源為(3-7)為了保護(hù)工作路任一鏈路那么鏈路e2上應(yīng)至少新增的共享資源為(3-8)下面附上實(shí)現(xiàn)共享保護(hù)的重要偽代碼。/*共享保護(hù)過程*/beginif當(dāng)前鏈路類型為域間鏈路，那么應(yīng)該采用專用保護(hù)//專用保護(hù)將工作路由壓棧將保護(hù)路由壓棧〔專用保護(hù)中，保護(hù)路由和工作路由相同〕endifif當(dāng)前鏈路類型為域內(nèi)鏈路，那么應(yīng)該采用共享保護(hù)//共享保護(hù)調(diào)用保護(hù)權(quán)重分配函數(shù)，根據(jù)工作分段路由重新分配權(quán)重將工作路由經(jīng)過的鏈路權(quán)重設(shè)為無窮大，使得工作分段和保護(hù)分段鏈路別離調(diào)用最短路算法計(jì)算與工作分段對(duì)應(yīng)的保護(hù)分段endifend/*權(quán)重分配函數(shù)*/begin if工作路屬性為共享路調(diào)用新增共享資源計(jì)算函數(shù)，計(jì)算每條鏈路上的新增共享資源，endifif當(dāng)前鏈路屬性為域間鏈路or虛鏈路權(quán)重設(shè)為無窮大elseif新增共享資源大于剩余資源權(quán)重設(shè)為無窮大else按照公式計(jì)算得出權(quán)重endifendifend/*新增共享資源計(jì)算函數(shù)*/beginif當(dāng)前鏈路為域間鏈路or虛鏈路 跳出//防止將域間鏈路和虛鏈路參加新增共享波長(zhǎng)數(shù)的計(jì)算else記錄經(jīng)過每條鏈路的工作路信息 endif 通過已經(jīng)記錄的每條鏈路上的工作路ID和保護(hù)路ID得到公式(3-8)中的ifendifif//假設(shè)每個(gè)連接請(qǐng)求一個(gè)波長(zhǎng)出錯(cuò) elseendifend基于LSSP的算法改良問題描述已經(jīng)知道，LSSP中在源域中尋找出口網(wǎng)關(guān)節(jié)點(diǎn)時(shí)，是通過比擬源節(jié)點(diǎn)到所有源網(wǎng)關(guān)節(jié)點(diǎn)的路由找到最短路得到。但是，這樣找到的源網(wǎng)關(guān)節(jié)點(diǎn)有可能不是最正確選擇。如圖3-6所示，連接請(qǐng)求A到P，假定當(dāng)前所有域內(nèi)物理鏈路的代價(jià)相等，即域內(nèi)路由由跳數(shù)決定。在LSSP中，先由源節(jié)點(diǎn)A尋找到所有網(wǎng)關(guān)節(jié)點(diǎn)的最短路，得到出口網(wǎng)關(guān)節(jié)點(diǎn)G1，再由G1通過虛拓?fù)涞挠蜷g路由得到目的網(wǎng)關(guān)節(jié)點(diǎn)G6，最后的路徑為：A-G1-G4-C-G8-G6-P，該路徑經(jīng)過了兩條域間鏈路。LSSP在尋找域內(nèi)出口網(wǎng)關(guān)節(jié)點(diǎn)時(shí)存在的問題例如但是，實(shí)際網(wǎng)絡(luò)情況是域間鏈路的代價(jià)會(huì)遠(yuǎn)大于域內(nèi)鏈路，域間鏈路的選擇一定程度上會(huì)決定路徑的優(yōu)劣?；趯?duì)整體拓?fù)湓敿?xì)情況了解的情況下，我們可以得到從源節(jié)點(diǎn)A到目的節(jié)點(diǎn)Q的最短路徑為A-G1-K-G2-G6-P，只經(jīng)過了一條域間鏈路，顯然比先前通過LSSP找到的最短路徑代價(jià)更小。可見，LSSP會(huì)存在找不到最優(yōu)路的情形，本文將針對(duì)這一點(diǎn)加以改良，改良方法歸結(jié)為動(dòng)態(tài)地將源、宿節(jié)點(diǎn)參加虛拓?fù)?。改良后的算法流程如圖3-7所示。和前面介紹的LSSP算法的差異主要在尋找源網(wǎng)關(guān)節(jié)點(diǎn)方面。改良后的算法中，主要方案是將源節(jié)點(diǎn)和目的節(jié)點(diǎn)都參加虛拓?fù)渲?。?dāng)然二者參加虛拓?fù)渲靶枰龀鲆恍╊A(yù)處理，即參加源、宿節(jié)點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)之間的虛鏈路的前提是實(shí)際的物理路徑路由成功，否那么就不添加相應(yīng)的虛鏈路。將源、宿節(jié)點(diǎn)參加虛拓?fù)渲?，域間路由就直接在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間進(jìn)行，這樣就免去了通過源節(jié)點(diǎn)域內(nèi)路由尋找源網(wǎng)關(guān)節(jié)點(diǎn)的步驟，一定程度上考慮了全局信息。改良的算法流程源、宿節(jié)點(diǎn)參加虛拓?fù)涞膶?shí)現(xiàn)將源節(jié)點(diǎn)參加虛拓?fù)洌枰诼酚芍案脑?、宿?jié)點(diǎn)到網(wǎng)關(guān)節(jié)點(diǎn)的鏈路屬性，分別增加源、目節(jié)點(diǎn)到同域網(wǎng)關(guān)節(jié)點(diǎn)的虛鏈路，路由之后將圖恢復(fù)成初始化的情況，以便后續(xù)的路徑映射的實(shí)施。根據(jù)圖3-6中的物理拓?fù)涞玫絾渭兲崛√撏負(fù)浜驮垂?jié)點(diǎn)參加虛拓?fù)涞膬煞N情形，如圖3-8所示，節(jié)點(diǎn)A為連接請(qǐng)求的源節(jié)點(diǎn)。(a)改良前(b)改良后虛拓?fù)涮崛。焊牧记昂透牧己髮⒃?、宿?jié)點(diǎn)參加虛拓?fù)浜?，可以有效找到使路徑代價(jià)更小的源網(wǎng)關(guān)節(jié)點(diǎn)，這樣會(huì)使找路更準(zhǔn)確。以域1到域3的路由為例，其出口網(wǎng)關(guān)節(jié)點(diǎn)選擇G2會(huì)優(yōu)于G1，LSSP是單純通過源節(jié)點(diǎn)到所有網(wǎng)關(guān)節(jié)點(diǎn)路徑的比擬會(huì)得到出口網(wǎng)關(guān)節(jié)點(diǎn)G1，而采用改良后的LSSP算法那么可以選擇到較為準(zhǔn)確的出口網(wǎng)關(guān)節(jié)點(diǎn)G2。在第4章中將會(huì)對(duì)兩種算法的性能進(jìn)行編程仿真和詳細(xì)的分析。值得一提的是，在編程實(shí)現(xiàn)中，存儲(chǔ)鏈路信息的數(shù)據(jù)結(jié)構(gòu)采用了C++中的map結(jié)構(gòu)，對(duì)于將源、宿節(jié)點(diǎn)參加虛拓?fù)湫枰龀鲆恍┨幚硪詽M足編程環(huán)境中數(shù)據(jù)結(jié)構(gòu)的要求，具體程序參見附錄。仿真結(jié)果與分析仿真使用增長(zhǎng)流量模型。在該模型中，連接是動(dòng)態(tài)產(chǎn)生的，假設(shè)所有業(yè)務(wù)請(qǐng)求的到達(dá)速率服從均值為β的泊松分布，所建業(yè)務(wù)的持續(xù)時(shí)間服從均值為1/μ的指數(shù)分布，即全網(wǎng)總負(fù)載為β/μ愛爾蘭(Erlang)，仿真時(shí)取μ=1。到達(dá)業(yè)務(wù)請(qǐng)求的源、宿節(jié)點(diǎn)在所有節(jié)點(diǎn)對(duì)之間隨機(jī)選擇，如果業(yè)務(wù)連接建立失敗那么立即丟棄，即無等待隊(duì)列。為了更精確地仿真網(wǎng)絡(luò)真實(shí)情況，產(chǎn)生連接數(shù)需要到達(dá)106以上。連接請(qǐng)求是依次到達(dá)網(wǎng)絡(luò)的，一旦分配資源，連接請(qǐng)求不能重配置，并且假定每個(gè)請(qǐng)求帶寬就是一個(gè)波長(zhǎng)。仿真用的網(wǎng)絡(luò)拓?fù)淙鐖D3-6所示，網(wǎng)絡(luò)包含三個(gè)不同的域。在單個(gè)域中，節(jié)點(diǎn)對(duì)之間是由雙向光纖鏈路連通的。在兩個(gè)不同的域之間，節(jié)點(diǎn)對(duì)是由一條雙向工作路光纖和一條雙向?qū)Ｓ帽Ｗo(hù)路光纖連接的。每條光纖鏈路設(shè)置成有128個(gè)波長(zhǎng)，為了獲得較好的性能和簡(jiǎn)化仿真過程，認(rèn)為每個(gè)節(jié)點(diǎn)都有波長(zhǎng)轉(zhuǎn)換容量和光電光(O-E-O)波長(zhǎng)變換能力。連接的動(dòng)態(tài)產(chǎn)生，尤其需要注意的是資源的占用和資源的釋放問題。資源的占用和釋放都可以分成從工作分段和保護(hù)分段不同分成兩類。資源占用中，工作分段每條鏈路的工作波長(zhǎng)數(shù)應(yīng)該增加，并且記錄連接編號(hào)數(shù)；保護(hù)分段的所有鏈路通過計(jì)算新增共享資源值確定自己的共享波長(zhǎng)數(shù)，并且記錄連接編號(hào)數(shù)。資源釋放中，工作分段只需要將每條鏈路的工作波長(zhǎng)數(shù)減一，并且刪除記錄的當(dāng)前應(yīng)該釋放的連接編號(hào)；保護(hù)分段資源的釋放問題比擬復(fù)雜。在共享保護(hù)中，設(shè)計(jì)多條工作分段共享保護(hù)鏈路的問題，資源釋放的時(shí)候不僅要考慮當(dāng)前釋放連接，更要考慮到這些鏈路保護(hù)的其他連接。本文中采用的方式是通過保護(hù)分段鏈路上的共享連接編號(hào)集來確定這些鏈路需要保護(hù)的工作分段，從工作分段出發(fā)，重新計(jì)算保護(hù)分段上所有鏈路的共享資源。保護(hù)分段的共享資源釋放的代碼見附錄。我們將改良后的算法與改良前的分段保護(hù)算法LSSP(LocalSegment-SharedProtection)進(jìn)行了比照研究，主要研究資源利用率(ResourceUtilizationRatio，RUR)。資源利用率定義為總的保護(hù)波長(zhǎng)資源與總的工作波長(zhǎng)資源的比值，資源利用率越小，說明保護(hù)預(yù)留資源越少?？梢缘玫?，資源利用率越高，后續(xù)業(yè)務(wù)請(qǐng)求可用的空閑資源就越多，阻塞率就會(huì)越低，網(wǎng)絡(luò)性能越好。仿真結(jié)果如圖4-1所示。X軸都是用Erlang表示的網(wǎng)絡(luò)負(fù)載，Y軸分別為資源利用率和阻塞率?？梢郧宄目吹?，在不同的網(wǎng)絡(luò)負(fù)載下，改良后的算法RUR有所降低，即網(wǎng)絡(luò)性能有所提高。改良后的算法將源、宿節(jié)點(diǎn)參加虛拓?fù)渲?，一定程度上減少了找路是對(duì)出口網(wǎng)關(guān)節(jié)點(diǎn)的依賴，相對(duì)于LSSP中依靠源節(jié)點(diǎn)到源域所有網(wǎng)關(guān)節(jié)點(diǎn)的路徑比擬得到出口網(wǎng)關(guān)節(jié)點(diǎn)的方式，無論是準(zhǔn)確性還是資源利用方面，改良后的算法性能都優(yōu)于LSSP。資源利用率的比擬總結(jié)及展望在WDM光網(wǎng)絡(luò)中，網(wǎng)絡(luò)部件失效時(shí)可能遭受比傳統(tǒng)網(wǎng)絡(luò)更大的損失，比方一根光纖斷裂將導(dǎo)致所有經(jīng)過該光纖的光路都失效，而每條光路都能以Gb/ps的速率傳輸數(shù)據(jù)，這樣的失效對(duì)網(wǎng)絡(luò)中業(yè)務(wù)的影響是非常巨大的。因此，網(wǎng)絡(luò)生存性問題對(duì)WDM光網(wǎng)絡(luò)是一個(gè)非常重要的問題。本文研究了大量已有的多域光網(wǎng)絡(luò)中動(dòng)態(tài)連接下的保護(hù)算法，特別是共享分段保護(hù)算法，對(duì)其中一種算法進(jìn)行了詳細(xì)的分析和研究，在此根底上提出了改良，并通過編程仿真對(duì)算法性能進(jìn)行了驗(yàn)證和評(píng)價(jià)。本章5.1節(jié)是對(duì)全文研究工作的歸納總結(jié)，5.2節(jié)提出了有待解決的問題和改良的方向。研究工作總結(jié)通過前面的工作，了解了WDM光網(wǎng)絡(luò)的特點(diǎn)，結(jié)構(gòu)以及光交換技術(shù)等光網(wǎng)絡(luò)根本概念，對(duì)網(wǎng)絡(luò)生存性技術(shù)有了較為深刻的認(rèn)識(shí)，進(jìn)而拓展到多域光網(wǎng)絡(luò)的保護(hù)算法研究上。本文在以下幾個(gè)方面做了相關(guān)研究。連接的動(dòng)態(tài)產(chǎn)生模型動(dòng)態(tài)產(chǎn)生連接請(qǐng)求，按照連接到達(dá)時(shí)刻服從泊松分布，持續(xù)時(shí)間服從復(fù)指數(shù)分布構(gòu)建數(shù)學(xué)模型。通過偽時(shí)鐘控制連接的到達(dá)和結(jié)束，從而到達(dá)仿真網(wǎng)絡(luò)連接情況的目的。拓?fù)渚酆贤負(fù)渚酆鲜嵌嘤蚓W(wǎng)絡(luò)中域間傳遞拓?fù)湫畔⒈仨毜募夹g(shù)，多域光網(wǎng)絡(luò)的保護(hù)算法的前序步驟也是拓?fù)渚酆?。拓?fù)渚酆虾螅诒ＷC準(zhǔn)確的前提下，網(wǎng)關(guān)節(jié)點(diǎn)之間傳遞少量的交互信息來實(shí)現(xiàn)域間路由等功能，提高了網(wǎng)絡(luò)性能。共享保護(hù)相較于專用保護(hù)，共享保護(hù)可以大大提高資源利用率。保護(hù)算法一般都是基于共享保護(hù)進(jìn)行研究，共享保護(hù)的原理見3.3.5小節(jié)?；贚SSP算法的改良在對(duì)已經(jīng)提出的LSSP的重現(xiàn)過程中，發(fā)現(xiàn)在尋找源域的出口網(wǎng)關(guān)節(jié)點(diǎn)時(shí)可以改良。提出的改良方法是，將源、宿節(jié)點(diǎn)參加拓?fù)渚酆虾蟮奶撏負(fù)渲?，這樣就將尋找出口網(wǎng)關(guān)節(jié)點(diǎn)這一環(huán)節(jié)省略掉，從而提高尋找最短路的準(zhǔn)確性。展望本文提出的改良的算法仍然存在可以提升的空間。在源、宿節(jié)點(diǎn)參加虛拓?fù)浜?，?jì)算源、宿之間的路由時(shí)只是簡(jiǎn)單的將可以映射的虛擬鏈路權(quán)重設(shè)為1，這樣和真實(shí)情況存在出入，可以在虛拓?fù)錂?quán)重設(shè)置上做出改良，例如結(jié)合網(wǎng)關(guān)節(jié)點(diǎn)預(yù)先存儲(chǔ)的信息估算虛鏈路的權(quán)重。所以，該算法有待進(jìn)一步完善。通過對(duì)多域光網(wǎng)絡(luò)的保護(hù)算法有了比擬深入的研究，發(fā)現(xiàn)該研究方向還存在很多可以突破和改良的地方，現(xiàn)列舉如下：1〕目前的研究大多集中于給定網(wǎng)絡(luò)的失效情況，比方LSSP中限制了一個(gè)域最多有一個(gè)故障。然而，如果網(wǎng)絡(luò)中的故障數(shù)不確定，以前提出的生存性機(jī)制或保護(hù)算法就不再適用。因此，需要普遍適用的保護(hù)算法。2〕現(xiàn)有的保護(hù)算法多是基于“兩步路由〞的框架，即先域間路由再域內(nèi)路由?？梢試L試在整體框架上作一些改良。3〕拓?fù)渚酆戏矫娴母牧肌Ｔ诒疚闹?，拓?fù)渚酆现皇呛?jiǎn)單地采用了全連通聚合，但是這種聚合方式只適用于規(guī)模較小的網(wǎng)絡(luò)，如果網(wǎng)絡(luò)規(guī)模較大，那么拓?fù)渚酆系拇鷥r(jià)相當(dāng)大，所以應(yīng)該考慮其他聚合方式來提高網(wǎng)絡(luò)性能。4〕參加限制的保護(hù)算法。本文的實(shí)現(xiàn)的分段保護(hù)算法中，并沒有考慮參加跳數(shù)限制等限制因素，這和實(shí)際網(wǎng)絡(luò)情況有差異，可以進(jìn)一步改良。5〕區(qū)分業(yè)務(wù)可靠度。本文實(shí)現(xiàn)的保護(hù)算法沒有區(qū)分業(yè)務(wù)，不同業(yè)務(wù)對(duì)可靠度的要求通常都不一樣，要使得工作路和保護(hù)路的可靠度滿足連接請(qǐng)求的可靠度要求。6〕本文實(shí)現(xiàn)的保護(hù)算法中，域間的鏈路是使用的專用保護(hù)，可以將其改良為共享保護(hù)。參考文獻(xiàn)徐寧榕,周春燕,WDM技術(shù)與應(yīng)用.北京:人民郵電出版社,2002羅洪斌,抗毀WDM網(wǎng)狀網(wǎng)中的保護(hù)算法研究:[博士學(xué)位論文].成都:電子科技大學(xué),2006紀(jì)越峰,王宏祥,光突發(fā)交換網(wǎng)絡(luò),北京:北京郵電大學(xué)出版社,2005GregBermstein,BalaRajagopalan,DebanjanSaha,黃蔚等譯,智能光網(wǎng)絡(luò)－體系結(jié)構(gòu)、協(xié)議和標(biāo)準(zhǔn),北京:人民郵電出版社,2007崔延軍,李健,張志珊,顧畹儀.智能光網(wǎng)絡(luò)的多域生存性研究.量子電子學(xué)報(bào),2006,Vol.23,No.3:420~423S.Ramamurthy,LaxmanSahasrabuddhe.SurvivableWDMMeshNetworks.Journaloflightwavetechnology,2003,Vol.21,No.4:870~883劉愛波,陸月明,紀(jì)越峰.智能光網(wǎng)絡(luò)路由及其關(guān)鍵技術(shù)分析.光通信技術(shù),2004,第8期:29~31BaruchAwerbuch,YiDu,etal.RoutingThroughNetworkswithHierarchicalTopologyAggregation.JournalofHigh-SpeedNetworks,1998,Vol.7,No.1:57~73SuleymanUludag,King-ShanLui,KlaraNahrstedt,GregBrewster.ComparativeAnalysisofTopologyAggregationTechniquesandApproachesfortheScalabilityofQoSRouting,2005.雷蕾,郭林,紀(jì)越峰.一種應(yīng)用于不對(duì)稱網(wǎng)絡(luò)中的生成樹拓?fù)涑橄笏惴?電子與信息學(xué)報(bào),2006,Vol.28,No.10:1917~1920D.L.Truong,B.Thiongane.Dynamicroutingforsharedpathprotectioninmulti-domainopticalmeshnetworks.Journalofopticalnetworking,2006,Vol.5,No.1:58~74LeiGuo.LSSP:Anovellocalsegment-sharedprotectionformulti-domainopticalmeshnetworks.ComputerCommunications,2007,30(2007)1794-1801D.L.Truong,B.Jaumard.OverlappedSegmentSharedProtectioninMulti-domainNetworks.Proc.ofSPIE,2006,Vol.635463541K-1Dieu-LinhTruong,BrigitteJaumard.UsingTopologyAggregationforEfficientSharedSegmentProtectionSolutionsinMulti-DomainNetworks.IEEEJournalonselectedareasincommunications,2007,Vol.25,No.9:96~107S.RamamurtyandB.Mukherjee,SurvivableWDMmeshnetworks,partI-protection,1999.P.-H.Ho,J.Tapolcai,andT.Clinkler.Segmentsharedprotectioninmeshcommunicationsnetworkswithbandwidthguaranteedtunnels.IEEE/ACMtransactionsonnetworking,2004,Vol.12,No.6:1105~1118G.Ranjith,G.P.Krishna,andC.S.R.Murthy.Adistributedprimary-segmentedbackupschemefordependablereal-timecommunicationinmulti-hopnetworks.ProceedingsoftheInternationalParallelandDistributedProcessingSymposium,2002--.SparecapacityallocationforWDMmeshnetworkswithpartialwavelengthconversioncapacity,2003.P.-H.HoandH.T.Mouftah,Aframeworkforservice-guaranteedsharedprotectioninWDMmeshnetworks.IEEECommunicationsMagazine,2002,02:97~103D.Xu,C.Qiao,andY.Xiong,Protectionwithmulti-segments(PROMISE)innetworkswithsharedrisklinkgroups(SRLG).IEEE/ACMTransactionsonNetworking(TON),2002J.Cao,L.Guo,H.Yu,andL.Li,AnovelrecursivesharedsegmentprotectionalgorithminsurvivableWDMnetworks.JournalofNetworkandComputerApplications,2007,Vol.30,No.2:677~694致謝本文無論是選題還是具體的研究工作，以至于論文的撰寫都得到我的指導(dǎo)老師虞紅芳副教授無微不至的關(guān)心和悉心指導(dǎo)。您嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度、淵博的知識(shí)、樸實(shí)的生活作風(fēng)，令我敬佩萬分！值此論文完成之際，向您獻(xiàn)上我誠(chéng)摯的敬意和深深的感謝！由衷的感謝所有關(guān)心我的老師、同學(xué)和朋友，尤其是章小寧博士、董擁?yè)韼熜趾涂娊鹈魍瑢W(xué)，正是通過和你們的交流、討論和你們的幫助，我才能克服種種困難，順利地完成課題，我為能夠得到你們的幫助而深表感謝！附錄附錄一工作路路由過程〔改良后〕核心代碼boolCallData::Connect_Call(CGraph&graph,VertexIDsourceid,VertexIDsinkid)//找工作路{UINTs1,s2,n;UINTtz=0;boola;list<Edge*>::iteratoreit;list<Edge*>::iteratorwe_it;list<Vertex*>::iteratorwv_it;map<pair<VertexID,VertexID>,Path>::iteratorvp_it;Pathtemp_path;ofstreamout_file;out_file.open("out.txt",ofstream::app);s1=graph.Vertex_vector[sourceid].GetDomain_ID();s2=graph.Vertex_vector[sinkid].GetDomain_ID(); if(s1==s2)//源節(jié)點(diǎn)和目的節(jié)點(diǎn)在同一個(gè)域中 { graph.GetPgraph();//得到單域的物理拓?fù)鋋=graph.ShortestPath(sourceid,sinkid,temp_path,s1);//域內(nèi)節(jié)點(diǎn)之間最短路算法if(a==false) {returnfalse; }WP.push_back(temp_path);//將工作路放入對(duì)應(yīng)的業(yè)務(wù)數(shù)據(jù)結(jié)構(gòu)中temp_path.ClearPathInfo(); } else//源、宿節(jié)點(diǎn)不在同一個(gè)域中 {graph.GetVgraph(sourceid,sinkid);//得到多域的虛擬拓?fù)鋋=graph.ShortestPath(sourceid,sinkid,graph.gpath,0);//域間節(jié)點(diǎn)之間最短路算法if(a==false) {returnfalse; }EraseNewEdge(graph);//將參加虛拓?fù)涞脑垂?jié)點(diǎn)和目的節(jié)點(diǎn)刪除graph.ChangeNode_prop(sourceid,sinkid);for(eit=graph.gpath.EdgeList.begin();eit!=graph.gpath.EdgeList.end();eit++) { if((**eit).GetDomain_id()==0) {//域的鏈路即為域間網(wǎng)關(guān)節(jié)點(diǎn)之間的鏈路，保護(hù)為專用保護(hù)，直接將節(jié)點(diǎn)和鏈路放入路徑信息中temp_path.ExpendVertex(&graph.Vertex_vector[(**eit).GetSource_ID()]);temp_path.ExpendEdge(*eit);temp_path.ExpendVertex(&graph.Vertex_vector[(**eit).GetSink_ID()]);WP.push_back(temp_path);temp_path.ClearPathInfo();continue; }else {//鏈路需要路徑映射graph.GetPgraph();//得到單域的物理拓?fù)鋘=graph.path_map((**eit).GetSource_ID(),(**eit).GetSink_ID());//將虛鏈路映射為實(shí)際鏈路if(n==0) {returnfalse; }if(WP.empty()!=true) {Joint_path(graph.tpath);//將同一域的分段連接起來 }else {WP.push_back(graph.tpath); }WP.push_back(graph.tpath); } }graph.gpath.ClearPathInfo();//去除暫存路徑信息graph.tpath.ClearPathInfo(); }returntrue;}附錄二共享保護(hù)過程核心代碼boolCGraph::SharedProtectProcess(CallData&call_data){VertexIDsourceid,sinkid;RouteWorkRoute,ProtectRoute,temp;DemandIDDemandId;DomainIDdomainid;DemandId=call_data.GetDemandId();UINTi,tz,b;Pathtemp_path,path1,path2;boola;list<Vertex*>::iteratorvit;ofstreamfileout;fileout.open("out.txt",ofstream::app);tz=static_cast<UINT>(call_data.WP.size());for(i=0;i<tz;i++) { path1.ClearPathInfo();path1=call_data.WP[i];Edge*ef_it;ef_it=path1.EdgeList.front();if((*ef_it).GetL_type()==1) {//路徑中鏈路屬性為true的鏈路使用專用保護(hù)path2=path1;PathToRoute(path1,WorkRoute);WorkRoute.SetOwnerDemandId(DemandId);//設(shè)置連接編號(hào)WorkRoute.SetPathType(Work_Path);//設(shè)置路徑屬性為工作路AllocateResource(WorkRoute,DemandId);//工作路經(jīng)過的鏈路記錄當(dāng)前連接編號(hào)PathToRoute(path2,ProtectRoute);ProtectRoute.SetOwnerDemandId(DemandId);ProtectRoute.SetPathType(Dedicated_Path);//設(shè)置路徑屬性為專用保護(hù)路AllocateResource(ProtectRoute,DemandId);//專用保護(hù)路經(jīng)過的鏈路記錄當(dāng)前連接編號(hào)call_data.work_route.push_back(WorkRoute);//存儲(chǔ)工作路分段call_data.backup_route.push_back(ProtectRoute);//存儲(chǔ)保護(hù)路分段WorkRoute.ClearRouteInfo();ProtectRoute.ClearRouteInfo();continue; }PathToRoute(path1,WorkRoute);WorkRoute.SetOwnerDemandId(DemandId);WorkRoute.SetPathType(Work_Path);AllocateResource(WorkRoute,DemandId);b=AssignWeight(Shared_Path,WorkRoute);//通過計(jì)算每條鏈路的新增共享資源值設(shè)置權(quán)重if(b==0) {returnfalse; }ForbiddenPath(path1);//為了是保護(hù)路和工作路別離，將工作路經(jīng)過的鏈路屏蔽vit=path1.VertexList.begin();domainid=(**vit).GetDomain_ID();sourceid=(*path1.VertexList.front()).GetVertex_ID();sinkid=(*path1.VertexList.back()).GetVertex_ID();a=ShortestPath(sourceid,sinkid,temp_path,domainid);//通過最短路算法找到保護(hù)路分段if(a==false) {returnfalse; }else {path2.ClearPathInfo();path2=temp_path;PathToRoute(path2,ProtectRoute);ProtectRoute.SetOwnerDemandId(DemandId);ProtectRoute.SetPathType(Shared_Path); AllocateResource(ProtectRoute,DemandId);call_data.work_route.push_back(WorkRoute);call_data.backup_route.push_back(ProtectRoute); }WorkRoute.ClearRouteInfo();ProtectRoute.ClearRouteInfo(); }returntrue;附錄三共享資源釋放過程核心代碼//呼叫結(jié)束Current_timer=LeastStopCallIT->GetStopTime();DemandIDdemandid;demandid=LeastStopCallIT->GetDemandId();cout<<"連接"<<demandid<<"*"<<LeastStopCallIT->GetSourceNode()<<""<<LeastStopCallIT->GetDestNode()<<"結(jié)束，釋放資源"<<endl;wr_it=LeastStopCallIT->work_route.begin();//釋放工作路資源for(;wr_it!=LeastStopCallIT->work_route.end();wr_it++){for(we_it=(*wr_it).LinkList.begin();we_it!=(*wr_it).LinkList.end();we_it++) {(**we_it).WorkDemandId.erase(find((**we_it).WorkDemandId.begin(),(**we_it).WorkDemandId.end(),demandid)); (**we_it).SetfreeWave_Num(graph1.Getwave_Num()); } }UINTcnt,tcnt;list<Edge*>::iteratorbe_it;list<Edge*>::iteratoreit;list<vector<UINT>>::iteratorListOfVectorIT;list<DemandID>::iteratorDemandIT;list<DemandID>::iteratorWD_it;vector<Route>cun_route;UINTCanntShare=0;UINTMaxCanntShare=0;//釋放保護(hù)路資源for(cnt=0;cnt<static_cast<UINT>(LeastStopCallIT->backup_route.size());cnt++){ for(be_it=LeastStopCallIT->backup_route[cnt].LinkList.begin();be_it!=LeastStopCallIT->backup_route[cnt].LinkList.end();be_it++) {if((**be_it).GetL_type()==1) {continue; }else { (**be_it).SharedDemandId.erase(find((**be_it).SharedDemandId.begin(),(**be_it).SharedDemandId.end(),demandid)); }MaxCanntShare=0;//同時(shí)保護(hù)sharedDemandID中的連接，Max應(yīng)該最大化for(CallIT=m_cCall.begin();CallIT!=m_cCall.end();CallIT++) {WD_it=find((*be_it)->SharedDemandId.begin(),(*be_it)->SharedDemandId.end(),CallIT->GetDemandId());if(WD_it!=(*be_it)->SharedDemandId.end()) {cun_route=CallIT->work_route;//存儲(chǔ)當(dāng)前鏈路保護(hù)的工作路由for(tcnt=0;tcnt<static_cast<UINT>(cun_route.size());tcnt++) {for(eit=cun_route[tcnt].LinkList.begin();eit!=cun_route[tcnt].LinkList.end();eit++) {cun_route[tcnt].ListOfVector.clear();if((**eit).GetL_type()==true) {continue; }UINTDemandNum=Counter+1;vector<DemandID>temp_vector(DemandNum,0);for(DemandIT=(*eit)->WorkDemandId.begin();DemandIT!=(*eit)->WorkDemandId.end();DemandIT++) {temp_vector[*DemandIT]=1; }cun_route[tcnt].ListOfVector.push_back(temp_vector); }for(ListOfVectorIT=cun_route[tcnt].ListOfVector.begin();ListOfVectorIT!=cun_route[tcnt].ListOfVector.end();ListOfVectorIT++) {CanntShare=0;for(DemandIT=(*be_it)->SharedDemandId.begin();DemandIT!=(*be_it)->SharedDemandId.end();DemandIT++) {CanntShare+=(*ListOfVectorIT)[*DemandIT]; }if(MaxCanntShare<CanntShare) {MaxCanntShare=CanntShare; } } } } }if((*be_it)->GetSharedWaveNum()>MaxCanntShare) { (*be_it)->SetSharedWaveNum(MaxCanntShare); (*be_it)->SetfreeWave_Num(64); } }}m_cCall.erase(LeastStopCallIT);外文資料原文LSSP:Anovellocalsegment-sharedprotectionformulti-domainopticalmeshnetworksLeiGuoAbstract—Thispaperinvestigatesthesurvivabilityinmulti-domainopticalmeshnetworksandpresentsanewmodelofmultiplefailuresthatisdefinedthatthereisonefailedlinkineachsingle-domainandaremultiplefailedlinksinthewholemulti-domains.SincetheconventionalExtended-Path-SharedProtection(EPSP)approachcannotprovide100%protectionabilityforthismodel,weproposeanovelapproachcalledLocalSegment-SharedProtection(LSSP)toprovideefficientsurvivabilityforthismodel.Inourapproach,LSSPfirstcomputesoneinter-domainprimarypathforeachconnectionrequestandfollowstocomputeoneintra-domainlink-disjointlocalsegment-backuppathforeachprimary-segmentpathineachsingle-domain,respectively,wherethebackupresourcescanbesharedbydifferentsegment-backuppathsifthecorrespondingprimary-segmentpathsarelink-disjoint.ComparedwiththeconventionalEPSP,althoughLSSPincreasesmoderatebackupresourcesconsumption,itnotonlycanprovide100%protectionabilityformultiplefailuresbutalsocanperformmuchfasterrecoverytimeandeasiersurvivableoperationandmanagement.Thesimulationresultsareshowntobepromising.1.IntroductionSurvivabilityhasbeenanimportantissueinWDMopticalnetworksandalsohasbeenstudiedformanyyears[1–5].Sincethesingle-fiber-linkfailurescenarioisdominantinWDMopticalnetworks,previousmanyworkshavefocusedtheprotectionforsingle-linkfailureandalsoproposedthecorrespondingsurvivableapproaches,inwhichthePath-SharedProtection(PSP)iseasierconfiguredandalsohasbetterresourceutilizationthanotherapproaches[4,5].InPSP,eachconnectionrequestwillbeassignedtooneprimarypathandonelink-disjointbackuppathfromthesourcenodetodestinationnode,andtwobackuppathscansharethebackupresourcesifthecorrespondingprimarypathsarelink-disjoint.AlthoughPSPcanprovidecompleteprotectionabilityforsingle-linkfailureandperformefficientend-to-endrouting,itisonlysuitableforsingle-domainnetworkinwhicheachnetworknodeneedstoviewtheglobenetworkinformation[6],e.g.,physicaltopology,bandwidthallocation,etc.Inreal-world,howeveranopticalWDMnetworkcontainsmulti-domainsbecausedifferentcarriersorserviceprovidersmaywanttomanagetheirownpartsofthenetwork[7–9].Anotherreasonisthatdifferentpartsofthetransportnetworkmayusedifferenttechnologies.Inmulti-domainnetworks,eachsingle-domainhastwokindsofnodes,whichareinteriornodeandgatewaynode.Eachinteriornodeonlycanviewthelocalnetworkinformationofphysicaltopologyinitsownsingle-domain,andthegatewaynodecanviewboththelocalnetworkinformationofphysicaltopologyandtheglobenetworkinformationofvictualtopology.Therefore,lackofglobenetworkinformationtheconventionalPSPneedstobemodifiedtoprovideefficientinter-domainsurvivableroutinginmulti-domainnetworks.In[6],theauthorsproposedanExtended-PSP(EPSP)approachthatcontainstowstepstoachieveinter-domainsurvivablerouting.Inthefirststep,aroughroutingsolutionissketchedinthevirtualnetworkthatisthetopologyaggregationofthemulti-domainnetwork.Acompleteroutingisthendeterminedbysolvingroutingproblemswithineachoriginalsingle-domainnetwork.Finally,anend-to-endinter-domainroutingpairwithoneprimarypathandonelink-disjointbackuppathcanbeestablishedfromthesourcenodetodestinationnode.ItisobviousthatEPSPcanprovidecompleteprotectionforthesingle-linkfailureandalsohasthesameefficientresourcesutilizationwithPSP.However,EPSPisasimpleextendedapproachfromthesingle-domaintomulti-domains,sothatitmaynotbesuitableforsurvivableroutinginreal-worldmulti-domainnetworks.Inpracticalmulti-domainnetworks,eachsingle-domainhasthecarrierorserviceproviderwhomaywanttomanageitsownpartsofthenetwork.Therefore,eachsingle-domaincanberegardedasanindependentnetworkthathasitsownlocalrulesofoperationandmanagementtoprovideservices.TheindependentlocalrulesofoperationandmanagementmayleadtosomeproblemsthatcannotbesolvedbyEPSP.ForexampleinFig.1,theblacknodesarethegatewaynodesthatcanviewboththelocalnetworkinformationofphysicaltopologyinitsownsingle-domainshowninFig.1(a)andtheglobenetworkinformationofvirtualtopologyshowninFig.1(b),andothernodesaretheinteriornodesthatonlycanviewthelocalnetworkinformationofphysicaltopologyinitsownsingle-domainshowninFig.1(a).InFig.1(c),weassumethereisaconnectionrequestestablishedbyEPSPfromsourcenodeAindomain1todestinationnodeKindomain3.Duetoindependentlocalrulesindifferentdomains,thefirstproblemisthattheremaybeexistonefailedlinkineachsingle-domainatatimepoint.Forexample,ifthefailedlinkA-G1isindomain1,thefailedlinkG4-Eisindomain2,andthefailedlinkJ-Kisindomain3,thisconnectionrequestwithaprimarypathA-G1-G4-E-G5-G6-KandabackuppathA-B-G2-G7-J-KprovidedbyEPSPwillbeblockedsincetheprimarypathandbackuppatharebothunavailable.ThesecondproblemisthattherecoverytimeofEPSPislongthatmaynotsatisfytherequirementofeachsingle-domain.Forexample,ifdomain3requires3msrecoverytimeconstraintsandhowevertherecoverytimeofEPSPfromsourcenodeAtodestinationnodeKis5ms,thedestinationnodeKindomain3willconsiderthattherecoveryprocedurefailsandthisconnectionrequestwillbeblocked.Thethirdproblemisthattheinter-domainbackupsmayrequiremuchcomplicatedoperationandmanagementsincetheinter-domainbackuppathmaytraversemultipledomainsandneedtoconfiguremanyinter-domainsignals,messagesandgatewaysnodes.Inordertoovercometheaboveproblems,weproposeanovelLocalSegment-SharedProtection(LSSP)approach.InLSSP,eachinter-domainprimarypathcanbedividedtomultiplesegment-primarypathsaccordingtodifferentdomains,andeachsegment-primarypathcanbeassignedtooneintra-domainlink-disjointsegment-backuppath.InLSSP,twosegment-backuppathsinthesamedomaincansharethebackupresourcesifthecorrespon