嘉興學院畢業(yè)設(shè)計（論文）外文翻譯原文題目：SharedProtectionRoutingAlgorithmforOpticalNetwork譯文題目：共享保護路由算法光網(wǎng)絡(luò)學院名稱：機電工程學院專業(yè)班級：電信112學生姓名：周俠杰譯文共享保護路由算法光網(wǎng)絡(luò)勝利元（電子郵件：syuan@）杰森P.玨（電子郵件：jjue@）計算機科學，德克薩斯大學達拉斯分校系理查森，TX75083摘要在面向連接的網(wǎng)絡(luò)，如一個全光傳輸網(wǎng)絡(luò)，共享保護提供了相同的水平的保護；防止單路徑故障的專用保護，具有潛在的更高的網(wǎng)絡(luò)利用率。此論文列出路徑保護的要求，提出了一種啟發(fā)式路由算法共享保護配置,模擬進行了驗證算法和比較的共享網(wǎng)絡(luò)利用率保護的專門保護引言1面向連接的網(wǎng)絡(luò)提供端-端的路徑，如光學的光路（的OLP）在DWDM網(wǎng)絡(luò)，和MPLS標簽在MPLS域交換路徑（LSP）。為了防止流量丟失，一個路徑可通過被保護另一個路徑，或所謂的保護路徑或備份路徑。保護路徑具有作為相同的源和目的地。主要的，還是工作路徑。當主路徑出現(xiàn)故障時，保護路徑被激活，以繼續(xù)執(zhí)行流量。在統(tǒng)計上，該通路的失效概率應(yīng)該是獨立的;因此，如果出現(xiàn)故障的概率一個路徑是pf<1，流量丟失的概率減小到pf2<PF?；诰W(wǎng)絡(luò)的共享資源是否被允許，保護方案可以被分類為專用保護或共享保護。在專門的保護，不同的保護路徑不共享公共資源，這可能是一個光纖線路，一個SONET信道，一個WDM波長或開關(guān)。專用保護的例子有SONET1+1保護和SONET1：1保護[1]。本文在2001年8月21日年在美國丹佛的OptiComm會議提出了SONET1+1保護、交通傳播較早的一個版本2同時在兩個不同的纖維從源到目的地。在SONET1：1保護，交通以上僅一個纖維在一個時間發(fā)射。對于專用保護，故障和激活一個保護路徑不會影響任何其他的保護路徑。這種類型的保護的配置相對簡單，并且其行為是確定性的。另一方面，在共享保護，多重保護路徑可以經(jīng)過公共資源如圖1所示在這個例子中，實線是主路徑和劃線是保護路徑。保護主路徑AB和CD的路徑共享公共節(jié)點E和F以及論文節(jié)點之間的聯(lián)系。SONET1：N保護是共享保護的一種特殊情況，因為所有的主路徑具有相同的源和目的地。在共享保護，當一個保護路徑被激活，這與它共享公共資源等保護路徑可能必須重新路由。例如，當在圖1中主路徑AB出現(xiàn)故障時，保護路徑aefb被激活，所以CEFD的主路徑CD的保護路徑，必須改。在另一方面，當一個公共資源發(fā)生故障，所有共享的資源保護路徑需要被重新路由。在同一個例子，如果鏈路EF失敗，新的保護兩個主路徑的路徑需要重新建立。因此共享保護是更復雜的提供和維護。然而，共享保護確實提供了一個優(yōu)勢的專用保護，也就是說，它可以提供更高的網(wǎng)絡(luò)利用。假設(shè)每個路徑需要保護。在專用的情況下，最好的網(wǎng)絡(luò)利用率為50％。另一方面，對于共享保護，因為多條路徑共享公共資源，總數(shù)如圖1所示.共享保護的例子：ABCD主路徑保護路徑EF3所有的保護路徑所需的資源可以低得多。如果主要的失敗概率路徑是統(tǒng)計獨立的,同時我們不會指望多條路徑失敗,在這種情況下,共享保護提供了相同的保護作為專門的保護。這個概念可以如下所示的例子：假設(shè)網(wǎng)絡(luò)中有10個主要路徑,每個都有一個獨立的失效概率為0.01。在任何時刻路徑失敗的概率是1-10(1-0.01)=0.9562,單路徑失效概率10*0.01*(1-0.01)=0.9135。因此一個路徑故障計數(shù)為總額的95.534%路徑失敗,共享保護執(zhí)行以及專用的保護。剩下的4.466%的失敗,即可。多路徑失敗,共享保護的性能將取決于如何有效地保護時改航路徑一個保護路徑被激活。共享與潛在的低得多的網(wǎng)絡(luò)資源保護提供了體面的保護;因此,網(wǎng)絡(luò)可以獲得更高的利用率。共享保護和專用保護計劃提供更多的互補靈活的解決方案。唯一的路徑需要專門保護最嚴格的保護要求。剩余的路徑可以保護共享保護和免費的網(wǎng)絡(luò)資源,支持更多沒有保護的路徑,或保護路徑。共享保護的好處吸引了一些研究的興趣,特別是對新興的光DWDM網(wǎng)絡(luò)。[2]提出了一種控制協(xié)議與各種功能,包括共享保護路由WDM網(wǎng)狀網(wǎng)絡(luò)，[3]實際上實現(xiàn)光層保護在一個5節(jié)點光網(wǎng)絡(luò)共享。此外,研究[4]描述了屬性和專用和共享保護環(huán)的好處,以及如何使用這兩種類型有助于一堆WDM環(huán)的設(shè)計。在本文中,我們調(diào)查的路由問題共同保護。我們的目標是小學和成功的路線保護路徑的最小使用網(wǎng)絡(luò)資源。這個問題可以被認為是在兩個不同的交通的假設(shè)。靜態(tài)路由的情況下適用于連接的設(shè)置是提前知道。在動態(tài)情況下,連接請求到達網(wǎng)絡(luò)動態(tài)。靜態(tài)非完全多項式。研究在[5]4和[6]落入第一類。[5]開發(fā)了一個整數(shù)線性規(guī)劃（ILP）配方，它是相當有效的對于小型網(wǎng)絡(luò)。對于較大的網(wǎng)絡(luò)中，提出了一種啟發(fā)式算法[6]可以是更合適的。在動態(tài)路由，[7]提出了一個“水桶型”鏈接狀態(tài)表示結(jié)合最短路徑算法。但是，這方法是最有效的僅在基于鏈路的保護，即，在工作路徑上的每個鏈路是由一個受保護的替代路徑連接的鏈路的兩個端節(jié)點。本文討論了共享保護的動態(tài)路由問題。我們先建立一個通用的框架，捕獲的風險以及網(wǎng)絡(luò)的潛在故障的信息。然后，我們提出了一個啟發(fā)式的路由算法，其利用以滿足與端至端的路徑保護動態(tài)連接請求中的信息。這種方法適用于所有面向連接網(wǎng)絡(luò)，包括所有的光學DWDM網(wǎng)絡(luò)。下一節(jié)描述了細節(jié)上的啟發(fā)式路由算法。部3給出的模擬結(jié)果。第4節(jié)討論等問題涉及到共享保護和第5節(jié)總結(jié)全文。三、半導體存儲器和改進額外的數(shù)據(jù)和計算的要求:與專用保護的算法相比,共享保護算法需要資源的保護路徑的額外的知識風險id相關(guān)的主要路徑:如果共享保護路徑允許的最大數(shù)量,以及在網(wǎng)絡(luò)的節(jié)點數(shù)量是N,那么在每個鏈接,風險IDs的數(shù)量的O(M*N)。根據(jù)圖12。16個節(jié)點NSFNET波長連續(xù)性限制020406080年100年120年140年05101520253035最大數(shù)量的共享保護路徑/鏈接的數(shù)量成功的路線C=5,最適合C=5,首先滿足C=10,最適合C=10,首先滿足C=20,最適合C=20,首先滿足找出路徑是否有共同危險IDs與目標的主要路徑,算法需要一個額外的O(NlogN+(M*N)日志(M*N))計算每個鏈接。路徑刪除：當主路徑和保護路徑被拆除曾經(jīng)占領(lǐng)的資源將被釋放：如果我們將剩下的路徑,我們可以獲得更優(yōu)的路線[8]。這適用于專用的保護和共享保護。與任何類型的保護,重路由主要航線可能會導致交通支安打。它可能是更實際的改變只有保護路徑的時候。保護激活：當多個保護路徑共享公共資源,只有一個可以被激活時間。為了允許多個激活,之后我們可以做以下保護路徑被激活:重新路由失敗的主要路徑。一旦建立了新的主要道路,交通上的保護路徑,然后停用保護路徑。這種方法需要一個變更,加上信號路徑失活。交通沖擊的概率高流量時搬到新的主路徑。離開交通激活保護路徑,使其新的主路徑。建立一個新的保護路徑,以及重路由所有其他保護路徑共享公共資源(s)。這種方法不引入流量,但它需要多個保護重路由路徑以及相關(guān)的信號重路由。網(wǎng)絡(luò)運營商應(yīng)該決定哪些選項：如果終端用戶對高流量,第一方法顯然更適合,因為,當網(wǎng)絡(luò)利用率相對較高,重路由多重保護路徑的失效概率高于只重路由的主要路徑。另一方面,如果將多個保護路徑不是問題,那么第二種方法可能被考慮。信號：共享保護需要更多的信號比專用的保護。除了道路設(shè)施和刪除、保護激活需要額外的信號如上所述。信號可以,根據(jù)網(wǎng)絡(luò)類型帶內(nèi)或完成帶外。5最大限度地提高資源共享：要求4禁止的保護路徑之間的資源共享路徑有共同風險id。然而,如果我們每個主要路徑分解成多個部分,我們可能會發(fā)現(xiàn)風險分離段的主要路徑。然后我們可以建立基于航段保護而不是基于路徑保護,實現(xiàn)更高的共享這種方式[9]。四、結(jié)論在本文中,我們提出了一個共享保護光纖網(wǎng)絡(luò)和其他面向連接的路由算法網(wǎng)絡(luò)。模擬實驗證實,該算法、共享的保護提供了一個體面的保護與網(wǎng)絡(luò)資源不如專門的保護。一旦部署,補充當前共享保護兩層的保護沒有保護或?qū)Ｓ玫谋Ｗo。本文還解決了共享保護面臨的一些問題。最明顯的一個是多余的信號、數(shù)據(jù)計算、和路徑所需的重路由算法。模擬表明,實際的實現(xiàn)可以使用一個小的分享程度減少額外費用,同時實現(xiàn)更高網(wǎng)絡(luò)利用率。當然是需要更多的研究來研究權(quán)衡和最優(yōu)實現(xiàn)。五、引用[1]RajivRamaswami,KumarN.Sivarajan“光網(wǎng)絡(luò)”,pp.430-434[2]HuiZang,BiswanathMukherjee,,連接管理的可生存的wavelength-routedWDM網(wǎng)7月/網(wǎng)絡(luò)”,光網(wǎng)絡(luò)雜志,2001年8月,pp.17-28[3]Levy,D.S.;Sarathy,J.;YounghyeKwon;Al-Salameh,D.Y.,“光學層共享使用一種基于ip的保護光學控制網(wǎng)絡(luò)”,光纖通信會議和展覽,2001學報》,2001年,pp.TuO8-1-TuO8-3[4]Arijs,P。;Demeester,p.“共享和專用保護WDM環(huán)的優(yōu)點在混合網(wǎng)絡(luò)設(shè)計”,光纖通信會議,2000年,第4期,-95年pp.93[5]美S.Ramamurthy,B.Mukherjee,“抗毀WDM網(wǎng)狀網(wǎng)絡(luò):第一部分-保護”,訴訟,IEEEINFOCOM992卷,99年,pp.744-751[6]基督教徒Mauz“閑置產(chǎn)能分配共享保護光路徑在運輸網(wǎng)絡(luò)”,第三國際研討會設(shè)計可靠的通信網(wǎng)絡(luò)(DRCN2001)[7]Ching-FongSu,XunSu,“保護路徑路由在WDM網(wǎng)絡(luò)”,OFC2001TuO2-1。[8]VishalAnand,ChunmingQiao,動態(tài)建立保護路徑在WDM網(wǎng)絡(luò):第一部分”,,9日計算機通信和網(wǎng)絡(luò)國際會議(300年IC3N),pp.198-204[9]Pin-HanHo,H.T.Mouftah,“SLSP:光網(wǎng)絡(luò)”的新路徑保護計劃,OFC2001TuO1-1原文SharedProtectionRoutingAlgorithmforOpticalNetworkShengliYuan(e-mail:syuan@)JasonP.Jue(e-mail:jjue@)DepartmentofComputerScience,UniversityofTexasatDallasRichardson,TX750831.ABSTRACTInaconnection-orientednetworksuchasanall-opticaltransportnetwork,sharedprotectionprovidesthesamelevelofprotectionagainstsinglepathfailuresasdedicatedprotection,withpotentiallyhighernetworkutilization.Thispaperliststherequirementsofpathprotectionandproposesaheuristicroutingalgorithmforsharedprotectionprovisioning.Simulationswereconductedtoverifythealgorithmandtocomparenetworkutilizationofsharedprotectiontothatofdedicatedprotection.2.INTRODUCTIONAconnection-orientednetworkprovidesend-to-endpathssuchasOpticalLightPaths(OLPs)inaDWDMnetwork,andMPLSLabelSwitchedPaths(LSPs)inaMPLSdomain.Topreventtrafficloss,apathmaybeprotectedbyanotherpath,orso-calledprotectionpathorbackuppath.Theprotectionpathhasthesamesourceanddestinationastheprimary,orworkingpath.Whentheprimarypathfails,theprotectionpathisactivatedtocontinuecarryingtraffic.Statistically,thefailureprobabilitiesofthepathsoughttobeindependent;thusifthefailureprobabilityofonepathispf<1,theprobabilityoftrafficlossisreducedtopf2<pf.Basedonwhetherthesharingofnetworkresourcesisallowed,aprotectionschemecanbecategorizedasdedicatedprotectionorsharedprotection.Indedicatedprotection,differentprotectionpathsdonotsharecommonresource,whichmaybeafiberline,aSONETchannel,aWDMwavelengthoraswitch.ExamplesofdedicatedprotectionareSONET1+1protectionandSONET1:1protection[1].InSONET1+1protection,trafficistransmittedAnearlierversionofthispaperwaspresentedattheOptiComm2001Conference,21–23Auguest2001,Denver,USA2simultaneouslyontwoseparatefibersfromthesourcetothedestination.InSONET1:1protection,trafficistransmittedoveronlyonefiberatatime.Fordedicatedprotection,thefailureandactivationofoneprotectionpathdoesn’taffectanyotherprotectionpath.Theprovisioningofthistypeofprotectionisrelativelysimple,anditsbehaviorisdeterministic.Ontheotherhand,insharedprotection,multipleprotectionpathsmaygothroughcommonresourcesasillustratedinFigure1.Inthisexample,thesolidlinesareprimarypathsandthedashlinesareprotectionpaths.Theprotectionpathsofprimarypathabandcdsharecommonnodeseandfaswellasthelinkbetweenthesesnodes.SONET1:Nprotectionisaspecialcaseofsharedprotection,sinceallprimarypathshavethesamesourceanddestination.Insharedprotection,whenoneprotectionpathisactivated,otherprotectionpathsthatsharecommonresourceswithitmayhavetobererouted.Forexample,whenprimarypathabinFigure1fails,protectionpathaefbisactivated,sotheprotectionpathcefdforprimarypathcdhastobererouted.Ontheotherhand,whenacommonresourcefails,allprotectionpathsthatsharethatresourceneedtobererouted.Inthesameexample,iflinkeffails,newprotectionpathsofbothprimarypathsneedtobereestablished.Thereforesharedprotectionismorecomplextoprovisionandmaintain.However,sharedprotectiondoesofferoneadvantageoverdedicatedprotection,i.e.,itmayofferhighernetworkutilization.Assumethateverypathneedsprotection.Inthededicatedcase,thebestnetworkutilizationwouldbe50%.Ontheotherhand,forsharedprotection,sincemultiplepathssharecommonresources,thetotalnumberofFigure1.ExampleofSharedProtectionabcdPrimaryPathProtectionPathef3resourcesrequiredforalltheprotectionpathscanpotentiallybemuchlower.Ifthefailureprobabilitiesofprimarypathsarestatisticallyindependent,wewouldn’texpectmultiplepathstofailsimultaneously,inwhichcasesharedprotectionprovidesthesameprotectionasdedicatedprotection.Thisconceptcanbeillustratedinthefollowingexample.Assumethatthereare10primarypathsinanetwork,eachwithanindependentfailureprobabilityof0.01.Atanymomenttheprobabilityofpathfailureis1-(1-0.01)10=0.9562,ofwhichsinglepathfailureprobabilityis10*0.01*(1-0.01)9=0.9135.Thusasinglepathfailurecountsfor95.534%oftotalpathfailures,forwhichsharedprotectionperformsaswellasdedicatedprotection.Fortheremaining4.466%failures,i.e.,multiplepathfailures,theperformanceofsharedprotectionwoulddependonhoweffectivelytheotherprotectionpathsarereroutedwhenoneprotectionpathisactivated.Sharedprotectionprovidesdecentprotectionwithpotentiallymuchlowernetworkresources;thus,thenetworkcanachievehigherutilization.Sharedprotectionanddedicatedprotectionschemescomplementeachothertooffermoreflexiblesolutions.Onlythepathswiththemoststrictprotectionrequirementneedtobededicatedlyprotected.Theremainingpathscanbeprotectedundersharedprotectionandfreeupnetworkresources,toeithersupportmorepaths,ortoprotectpathsthathadnoprotectionbefore.Thebenefitsofsharedprotectionhaveattractedsomeresearchinterests,especiallyfortheemergingallopticalDWDMnetwork.[2]proposesacontrolprotocolwithvariouscapabilitiesincludingsharedprotectionroutingforWDMmeshnetworks.[3]actuallyimplementsopticallayersharedprotectionina5-nodeopticalnetwork.Additionally,researchin[4]describesthepropertiesandbenefitsofdedicatedandsharedprotectionsrings,andhowbothtypescancontributetoacost-efficientdesignforastackofWDMrings.Inthispaper,weinvestigatetheroutingprobleminsharedprotection.Thegoalistosuccessfullyrouteprimaryandprotectionpathswiththeminimumusageofnetworkresources.Thisproblemcanbeconsideredundertwodifferenttrafficassumptions.Staticroutingappliestothecaseinwhichthesetofconnectionsisknowninadvance.Inthedynamiccase,connectionrequestsarrivetothenetworkdynamically.ThestaticcaseisNP-complete.Studiesin[5]4and[6]fallintothefirstcategory.[5]developsanintegerlinearprogram(ILP)formulationwhichisquiteeffectiveforsmallnetwork.Forlargernetwork,aheuristicalgorithmproposedby[6]maybemoresuitable.Underdynamicrouting,[7]suggestsa“bucket-based”linkstaterepresentationcombinedwithshortestpathalgorithms.Butthisapproachismosteffectiveonlyinlink-basedprotection,i.e.,eachlinkontheworkingpathisprotectedbyanalternativepathconnectingthetwoendnodesofthelink.Thispaperaddressesthedynamicroutingproblemforsharedprotection.Wefirstestablishagenericframeworktocapturetheinformationonrisksandpotentialfailuresofanetwork.Wethenproposeaheuristicroutingalgorithmwhichutilizestheinformationtosatisfydynamicconnectionrequestwithend-to-endpathprotection.Thisapproachisapplicabletoallconnection-orientednetworksincludingtheallopticalDWDMnetwork.Thenextsectiondescribestheheuristicroutingalgorithmindetails.Section3presentssimulationresults.Section4discussesotherissuesrelatedtosharedprotection,andSection5concludesthepaper.3.SSUESANDIMPROVEMENTSAdditionalDataandComputationRequirements.Comparedwiththealgorithmfordedicatedprotection,theproposedalgorithmforsharedprotectionrequiresresourcesofprotectionpathstohavetheextraknowledgeoftheriskIDsoftherelatedprimarypaths.IfthemaximumnumberofsharedprotectionpathallowedisM,andthenumberofnodesinthenetworkisN,thenoneachlink,thenumberofriskIDsisontheorderofO(M*N).InorderFigure12.16NodeNSFNETwithWavelengthContinuityConstraint02040608010012014005101520253035MaximumNumberofSharedProtectionPathsPerLinkNumberofSuccessfulRoutesC=5,BestFitC=5,FirstFitC=10,BestFitC=10,FirstFitC=20,BestFitC=20,FirstFit16tofindoutwhetherthepathshaveanycommonriskIDswiththetargetprimarypath,thealgorithmneedsanextraO(NlogN+(M*N)log(M*N))computationsoneachlink.PathRemoval.Whenaprimarypathanditsprotectionpatharetorndown,theresourcesthatwereonceoccupiedarefreedup.Ifwereroutetheremainingpaths,wemayobtainmoreoptimalroutes[8].Thisappliestobothdedicatedprotectionandsharedprotection.Witheithertypeofprotection,reroutingprimaryroutesmaycausetraffichits.Itmaybemorepracticaltorerouteonlytheprotectionpathsfromtimetotime.ProtectionActivation.Whenmultipleprotectionpathssharecommonresources,onlyonecanbeactivatedatatime.Inordertoallowmultipleactivation,wecandooneofthefollowingafteraprotectionpathisactivated:Reroutethefailedprimarypath.Oncethenewprimarypathisestablished,movetrafficontoitfromtheprotectionpath,thendeactivatetheprotectionpath.Thisapproachrequiresonereroute,plussignalingforpathdeactivation.Theprobabilityoftraffichitishighwhentrafficismovedtothenewprimarypath.Leavethetrafficontheactivatedprotectionpathandmakeitthenewprimarypath.Establishanewprotectionpathforit,aswellasreroutingallotherprotectionpathsthatsharedcommonresource(s)withit.Thisapproachdoesn’tintroducetraffichit,butitrequiresreroutingmultipleprotectionpathsaswellassignalingassociatedwiththererouting.Thenetworkoperatorshoulddecidewhichoptiontotake.Iftheenduserhasahightolerancefortraffichits,thefirstapproachisclearlymoresuitable,since,whenthenetworkutilizationisrelativelyhigh,reroutingmultipleprotectionpathshashigherfailureprobabilitythanreroutingonlytheprimarypath.Ontheotherhand,ifreroutingmultipleprotectionpathsisnotanissue,thenthesecondapproachmaybeconsidered.Signaling.Sharedprotectionrequiresmoresignalingthandedicatedprotection.Inadditiontopathestablishmentandremoval,protectionactivationneedsextrasignalingasdescribedabove.Signalingcanbedoneeitherin-bandorout-of-band,dependingonthenetworktype.17MaximizingResourceSharing.Requirement4prohibitsresourcesharingamongprotectionpathswhoseprimarypathshavecommonriskIDs.However,ifwebreakeachprimarypathintomultiplesegments,wemayfindriskdisjointingsegmentsoftheprimarypaths.Wecanthenestablishsegment-basedprotectioninsteadofpathbasedprotection,andachievehighersharingthisway[9].4.CONCLUSIONInthispaperweproposedasharedprotectionroutingalgorithmforopticalnetworkandotherconnection-orientednetworks.Simulationsconfirmedthat,withthisalgorithm,sharedprotectionprovidesadecentlevelofprotectionwithlessnetworkresourcethandedicatedprotection.Oncedeployed,sharedprotectioncomplementsthecurrenttwolevelprotectionofnoprotectionordedicatedonlyprotection.Thispaperalsoaddressedsomeoftheissuesthatsharedprotectionfaces.Themostobviousoneistheextrasig