Static and Dynamic Evaluation of QoS Properties

StatiandDynamiEvaluationofQoSPropertiesGopalPanduranganEliUpfalMay3,2000AbstratEÆientutilizationofmodernhighbandwidthommuniationnetworksre-liesonstatistialmultiplexingofmanylogialhannelsthroughonephysialhannel.Communiationrequeststypiallyinludesomestatistialhara-terizationoftherequestedonnetion(suhaspikvalue,meanvalues,et).Thetaskofthenetworkmanagementproedureistoaommodateasmanyommuniationrequestsaspossiblewhilekeepingthefailure(e.g.overow)probabilityboundedbyapre-speiedparameter.Whenthenetworkonsistsofonelink,thetaskreduestoevaluatingtheprobabilitythatasumofran-domvariablesdoesnotexeedagivenbound.Tehniquessuhasthemethodofeetivebandwidthgiveapratialsolutionfortheonelinkproblem.InthispaperweaddressthemorerealistisettingofestimatingQoSpropertiesofmulti-linknetworkswitharbitrarypatterns.Therelatedoptimizationprob-lemforthatsettingis#P-ompleteevenforthemostsimpleommuniationharateristis.OurmainresultisaneÆientMonte-Carlomethodforestimatingthefailureprobabilityofageneralnetwork.Ourmethodispartiularlyusefulinadynamisettinginwhihommuniationrequestsaredynamiallyaddedandeliminatedfromthesystem.Theamortizedostinoursolutionofupdatingtheestimateaftereahhangeisproportionaltothefrationoflinksinvolvedinthehangeratherthantothetotalnumberoflinksinthenetwork.ComputerSieneDepartment,BrownUniversity,Box1910,Providene,RI02912-1910,USA.E-mail:fgopal,eligs.brown.edu.SupportedinpartbyNSFgrantCCR-9731477.Aprelimi-naryversionofthispaperappearedintheproeedingsofthe31stACMSymposiumonTheoryofComputing(STOC),Atlanta,1999.1IntrodutionModernommuniationprotoolssuhasATM(AsynhronousTransferMode)ahievehighutilizationofhannelbandwidthbymultiplexingommuniationstreamswithdierentowharateristisintooneommuniationhannel.Requestsforommu-niationaresubmittedtothenetworkmanagementprotoolwithsomestatistialharaterizationoftherequiredommuniation.Thenetwork(ow)managementprotoolusesthisinformationtostatistiallymultiplexasmanyommuniationre-questsaspossiblewhilemaintainingglobalnetworkperformane.NextgenerationommuniationnetworksareexpetedtoprovideQoS(qualityofservieguarantees)whensatisfyingommuniationrequests.Inpartiular,QoSprotoolisexpetedtolimittoapre-speiedvaluetheprobabilityofommuniationfailureduetoeventssuhasellloss,elldelayandelljitter[3℄.Thegoal(onthepartoftheommuniationprovider)istosatisfyasmanyommuniationrequestsaspossiblewhilemaintainingpre-speiedQoSguarantees.Inthispaperwefousonelllossfailuresduetolinkorbueroverow.Ourmethodanbemodiedtohandleotherstatistiallygovernedommuniationharateristisuhaselldelayandjitter.Intheaseofaonelinknetwork,ahievingQoSguaranteesisreduedtoboundingtheprobabilitythatasumofrandomvariablesexeedsagivenbound,whereeahrandomvariablerepresentsthestreamofdataofonelogiallink,andtheboundisthebandwidthapaityofthehannel(ortheadjaentbuers).Mostpreviousworkshavefousedonommuniationowmodeledbyanon-osoure[7℄.A(q;s)on-osouresendsatapeakrateofswithprobabilityqandzerootherwise.ThismodelapturestheextremeburstynatureofhighspeednetworksbasedonATMandrelatedtehnologies.On-osoureshavebeenstudiedextensivelybothintheory[7,10,8℄aswellasinsimulationstudiestoevaluateperformaneofroutingalgorithmsinATMnetworks[3℄.Theworkin[10℄isespeiallyinterestingasitarguesthatthefratalnatureofInternetandEthernettraÆisapturedverywellbyon-osoures.TehniquessuhaseetivebandwidthgiveeÆientandpratialsolutionforprovidingQoSguaranteesononelinknetworks[2℄.Theproblemofboundingtheoverowprobabilityinamulti-hannelnetworkofarbitrarypatternissigniantlyharder.Infattherelatedoptimizationproblemis#P-omplete[11℄evenifalllogiallinksarefedbyon-osoureswiththesameparametersqands.Wearenotawareofanyknownheuristitothisproblem,otherthansummingthefailureprobabilityonallnetworklinks.(Whihiswhatisdoneinpratie[3℄.)Suhanestimateisfartooexpensive,sineinlargenetworksitansigniantlyoverestimateoverowprobability,andthusunderutilizingnetworkapaity.Inthispaperwegivetherstnon-trivialalgorithmsforestimatingQoSpropertiesinstatistiallymultiplexednetworks.OuralgorithmsemployeÆientMonte-Carlo1connectionrequestroutingalgorithmchoosesapathinthenetworkQoSenforcer(admissioncontrol)PIsQoSviolatedCifCisroutedthroughP?CommunicationNetworkNo(RouteCviaP)YeschooseanotherpathYes(RejectC)Figure1:Ashematitoillustratehowaonnetionishandledmethodtoauratelyestimatetheoverowprobabilityofanysetofhannelsinanarbitrarytopologynetwork.Theseestimatestranslateintobetteradmissionontrolpoliythatahievehigherbandwidthutilizationwhileguaranteeingsamequalityofservie.Westudythisproblemunderstatianddynamisettings.Inthestatisetting,weassumethatasetofonnetionsarealreadyative(routed)inthenetworkandweareinterestedinwhetherQoSrequirementsareviolated.Inthedynamisetting,weareinterestedinadmittinganewonnetiontothenetworkandwedesireafastadmissionontrolalgorithmtodeidewhethertoadmitthisonnetionsubjettoQoSrequirement.Figure1illustratestheproedurefollowedbyatypialnetworkmanagementpro-toolwhenadmittinganewonnetion.Whenanewonnetionrequest,sayCarrives,theroutingalgorithm(forexample,analgorithmusedintelephonenetworksistheDynamiRoutingAlg