modeling and simulation of mesh networks with path

M.C.CalzarossaandE.Gelenbe(Eds.):MASCOTS2003,LNCS2965,pp.88–117,2004.©Springer-VerlagBerlinHeidelberg2004ModelingandSimulationofMeshNetworkswithPathProtectionandRestorationHassanNaserandHusseinT.MouftahSchoolofInformationTechnologyandEngineering(SITE)UniversityofOttawa,Ottawa,Ontario,CanadaK1N6N5{hnaser,mouftah}@site.uottawa.caAbstract.Thisarticlepresentsamodelingandsimulationmethodologytoanalyzetheavailabilityperformanceofdemandswhencarriedovermesh-basedtransportnetworkswithpath(end-to-end)protectionandrestorationschemes.Threemainschemesareexaminedandformulationsfordiverseroutingandcapacityallocationaregiven.Theseschemesare:(a)sharedpathrestoration,(b)dedicatedpathprotection,and(c)unprotectedpath.Theimpactofseveralnetworkparametersincludinglinkfailuresandrepairtimesontheachievableperformanceisinvestigated.Techniquesofobject-orientedmodelingandnotationsintheUnifiedModelingLanguage(UML),includingclassdiagramsandstatediagrams,areusedtocharacterizethestructureofstatesandbehaviorsofprevalentnetworkcomponents.1IntroductionSurvivabletransportnetworksaredefinedasnetworksthatcontinuefunctioningcorrectlyinthepresenceofnon-functioning(failed)networkcomponents.Thearchitectureoftransportnetworksconsistsoftwobasiccomponents:(1)nodesand(2)linksthatinterconnectthesenodes.Thefocusofsurvivablenetworksistoensuretheconnectivityofthenetworkincaseofasinglelinkornodefailure.Animportantcategoryofsurvivablenetworksisthecategoryof“meshrestorable”networks.Inthesenetworks,therestorationmechanismisabletoidentifythefailednetworkcomponentandreroutequicklythetraffictraversingit.Thisisdonebyexploitingmeshtopologyandthroughhighlydiverseandefficientroutingmechanism.Therearetwosurvivabilityparadigmsinmeshnetworks[1][2][5]:(1)linkprotection/restorationand(2)pathprotection/restoration.Inlinkprotection/restoration,whenalinkfails,thetwonodesthatterminatethelinkreroutethetraffictraversingthelinkoverasetofreplacement(backup)pathsbetweenthesenodes.Thesourceanddestinationnodesofthetraffictraversingthefailedlinkareoblivioustothelinkfailure.Inpathprotection/restoration,thesourceanddestinationnodesofthetraffictraversingthefailedlink(orfailednode)reroutethetrafficoverasetofreplacementpathsbetweenthesenodes.Inthissense,linkprotection/restorationmechanismsareconsidered“local”,whereaspathprotection/restorationmechanismsare“end-to-end”.Protectionandrestorationmechanismsaregenerallydifferentinthefollowingmanner.Inprotectionmechanisms,thebackuppathshavebeenidentifiedandspare(backup)capacitiesallocatedstaticallyinadvance,whereasinrestorationmechanismsthebackuppathsareestablisheddynamicallyafterthefailureoccurs.ProtectionModelingandSimulationofMeshNetworkswithPathProtectionandRestoration89mechanismsareproactive,whereastherestorationmechanismsvaryfromtotally-reactivetosemi-proactive.Intotally-reactiverestorationmechanisms,thebackuppathsareidentifiedandresourcesconfiguredafterthefailureoccurs.Insemi-proactiverestorationmechanisms,thebackuppathsareidentifiedandsignaledpriortofailure,buttheresourcesalongthesepathsareconfiguredonlyafterthefailureoccurs.Therearetwoapproachestobackupresourceallocationinsurvivablenetworks:(1)dedicated-resourceprotectionand(2)shared-resourcerestoration.Indedicated-resourceprotection,thebackupresourcesareexclusivelyreservedforeachfailedconnection(inthepathprotection)orfailedlink(inthelinkprotection).Inshared-resourcerestoration,thebackupresourcesaresharedamongdifferentconnections(inthepathrestoration)orlinks(inthelinkrestoration).Theconnections(orlinks)sharingthebackupresourcesaretobechoseninsuchawaythatanysinglefailurecannotputoutofservicemorethanoneconnection(orlink)atonetime.Doublefailuresleadingtothelossofmorethanoneconnection(orlink)atonetimemaybetolerated,providedtheprobabilityofsuchfailuresislow.Inthisarticle,wedescribeasimulationframeworkformodelingprotectionandrestorationmechanismsintransportmeshnetworks.Thefocuswillbeontheend-to-endpathprotection/restorationmechanisms,including,inparticular,dedicatedpathprotectionandsharedmeshrestoration.Oneofthemaincharacteristicsofthesimulationframeworkisitsgenerality:itcanbesimplyextendedtomeshnetworkswith“local”linkprotection/restorationmechanismsortonon-meshtopologies(suchasrings).Thearticleisorganizedasfollows.Section2introducesthenetworkmodelandoutlinesprotectionandrestorationschemesimplementedinthenetwork.Anoverviewofthediversityroutingmechanismstobeemployedbyeachschemeisgiven.Section3describesthesimulationapparatusandthefunctionalmodeloftherelevantnetworkcomponents.Networkobjects,classes,anddiagramsaredemonstratedbyusinganumberofcommonlyusednotationsintheUnifiedModelingLanguage(UML)withminoradaptationsinsyntaxforthesakeofconsistencywithC/C++.Section4presentsalgorithmsforconstrain-basedpathcomputationandprotocolsforbandwidthreservationinthesimulatednetwork.Section5givesthestatetransitiondiagramofthesimulatednetwork.Section6presentsthecoreofthesimulationprogramimplementedinC++code.Section7characterizestheperformanceoftheimplementedprotectionandrestorationmechanismsbyshowingtheresultsfrom