RARE EVENT SIMULATION

RAREEVENTSIMULATIONCarmelitaGörg,EugenLamers,OliverFußCommunicationNetworks,UniversityofBremen,GermanyPoulHeegaardyTelenor,NorwayAbstractDiscreteeventsimulationasamethodforperformanceevaluationhasbecomeanindispensabletoolinmanyfields,e.g.,teletrafficengi-neering.Newcommunicationnetworksandservicesposeextremere-quirementsregardingthequalityofservice,e.g.,celllossprobabilitiesinATM1networksintheorderof109.Straightforwardsimulationforthistypeofrareeventleadstosimulationruntimesintheorderofmonthsandyears,thusrequiringnewmethodstobeinvestigatedandemployed.InthefollowingthestateoftheartinthefieldofRareEventSimulationisdescribedandexamplesaregivenfortheRESTART2/LRE3methodtodemonstratethetypeofresultsthatcanbeachievedbyusingthesemeth-ods.InrecentyearsthesemethodshavebeenappliedtorelevantqualityofserviceparametersinATMnetworks.Futureapplicationswillcon-cerntheinvestigationoftheemergingqualityofserviceconceptsforNextGenerationInternets.RESTART/LREisamulti-stepsimulationapproachwhichreducesthesimulationruntimebyseveralordersofmagnitudefrom,e.g.,yearstominutes,thusmakingsimulationstudiesforrareeventsfeasible.Theapproachcanbeappliedtosinglenodesandnetworks.Itisaso-calledimportancesplittingmethod,wheresystemstatesthatleadtotherareeventaresavedandusedasthestartingpointfornewsimulationsub-runs.Theresultsofthesub-runsaremultipliedwiththecorrespondingweightswhichareobtainedinthepreviousstepandresultinthede-siredprobabilities.ThestatisticalevaluationmethodLREusedinthiscombinedapproachhastheadditionaladvantageofevaluatingtheso-calledlocalcorrelationfunctionwhichgivesinsightintothecorrelation{cg,elm,fuss}@comnets.uni-bremen.de,@telenor.com1ATM:AsynchronousTransferMode2REpetitiveSimulationTrialsAfterReachingThreshold3LimitedRelativeErrorstructureoftheinvestigatedrandomvariableandispartofanerrormea-sureforcontrollingallphasesofasimulation.ExamplesaregivenforthelossprobabilityofATMcellsinG/G/1/N4typesystemsaswellascertaintandemnetworksthatrepresentamodelforATMreferencecon-nections.Additionalresultsarepresentedwheretherareeventdetailsofthedelaytimedistributionaretheobjectoftheinvestigation.TheRESTART/LREsimulationoffersasaresultthecomplementarydistri-butionfunctionofthedelaytimedistributionsothattheprobabilityofdelayslongerthanagivenmaximumcanbededuceddirectlyfromthisresult.ThisisoneofthequalityofserviceparametersdefinedforATM.Furthermore,newresultsareavailablewherethemethodhasbeenusedtoinvestigaterareeventdetailsofthelossprobabilitiesforhandoverinwirelessATMnetworks.TheunderlyingmodelforanATMreferenceconnectionconsistsofanetworkwithasequenceof*/D/1/N5queuesandanextradelay(propagationandswitching)betweenthesequeues.AdditionaltrafficisofferedtotheoutgoingconnectionstomodeltheinterferenceofotherATMconnections.Simulationresultsforthecom-plementarydistributionfunctionofthedelaytimearepresented.Keywords:rareeventsimulation,RES,outputanalysis,variancereductiontechniques,importancesampling,IS,importancesplitting,optimizationtech-niques,ATMnetworks,lossprobability,occupancydistribution,delaytimedistribution,RESTART1INTRODUCTIONPerformanceofcomputerandcommunicationsystemsiscommonlycharac-terizedbytheoccurrenceofrareevents.Forexample,systemunavailabilityrequirementsaretypicallylessthan105andcelllossprobabilityinasyn-chronoustransfermode(ATM)switcheslessthan109.Theperformanceofsuchsystemsisfrequentlystudiedthroughsimulation.However,estimationofrareeventprobabilitieswiththenaiveMonteCarlotechniquesrequiresapro-hibitivelylargenumberoftrialsinmostinterestingcases.Figure1showsthebasicmethodsofsimulationspeed-upbyusingparallelordistributedcomput-ingpowerorstochasticmethods.Forrareeventsimulation(RES)twostochas-ticmethods,calledimportancesplitting/RESTARTandimportancesampling(IS),havebeenextensivelyinvestigatedbytheresearchsimulationcommunityinthelastdecade.Thebasicideaofsplitting[28]istopartitionthestate-spaceofthesystemintoaseriesofnestedsubsetsandtoconsidertherareeventastheintersectionofanestedsequenceofevents.Whenagivensubsetisenteredbyasample4G/G/1/N:Kendallclassificationforqueuingsystems,GeneralInput,GeneralOutput,1Server,NBufferSpaces,usuallyFIFO(FirstInFirstOut)5*/D/1/N:queuingsystemwithinputfrompreviousstagesanddeterministicservicetimeandDistributedSolutionareaundertheconditionttmaxnnminParallel/tmaxnn*minminReductionofnecessarytrialsruntimetnumberoftrialsnFigure1:SimulationSpeed-Uptrajectoryduringthesimulation,numerousrandomretrialsaregeneratedwiththeinitialstateforeachretrialbeingthestateofthesystemattheentrypoint.Thus,bydoingso,thesystemtrajectoryhasbeensplitintoanumberofnewsub-trajectories,hencethenamesplitting.Asimilarideahasbeendevelopedin[52][53]intoarefinedsimulationtechniqueunderthenameRESTARTwhichhasbeenextendedbydifferentauthorstothemultiplethresholdcase.Acomparisonofthedifferentsplitting/RESTARTmethodsandrecentsubstantialextensionsaredescribedin[12].Importancesampling(IS)isalsobasedontheideatomaketheoccurrenceofrareeventsmorefrequent,orinotherwords,tospeedupthesimulation.Technically,ISaims