Dynamic bandwidth Reservation in Virtual Private N

arXiv:math/0609496v1[math.OC]18Sep2006DynamicbandwidthReservationinVirtualPrivateNetworkunderUncertainTrafficH´el`eneLeCadreENSTBretagneTechnopˆ[e-mail]-TheaimofthispaperistoanalyzethedynamicevolutionofaVirtualPrivateNetwork.Thenetworkismodeledasasystem,controledbyamanagerwhoshouldtakeappropriatedecisions.How-ever,tobeabletotakethebestpossibledecisions,themanagershouldalsobeabletoforecasttheworstbehavior,inthesenseofaqualityofservicecriterion,ofthesystem,hewantstocontrol.Wehavechosentomodelthisproblem,asaniterativetwosidegame.Ontheoneside,theoperatortriestoreservetheminimalamountsofbandwidthtoguaranteethebestpossiblequalityofcommunicationforitsvariousclients.Ontheotherside,thetrafficoftheclientsfollowstheworstbehavior,inthefaceofthereservedbandwidths.ThetheoryofMarkovdecisionprocesses(MDP)enablesustomodeltheuncertaintyassociatedtotheknowledgeofthetraffic.Besides,twolevelsshouldbedifferentiatedinoursystem.Thelocalleveloftheclients,whoevolveindependentlyofoneanotherandselfishly,choosingtheworstpossibletrafficevolu-tion.Atthislevel,themanagercouldreservebandwidthlocally,oneachlinkforeveryVirtualPrivateNetwork.Whereas,atthegloballevelofthelinks,decisionsshouldbetakenbythemanagertocentrallycontrolthenetwork.AhierarchicalMDPapproachandthestochasticgameframeworkareintroducedtoproposesolutionstothisdifficultproblem.Furthermore,westudytheasymptoticbehaviorofthesystem,andprovetheconvergencetowardsstationarystrategies.Inthefinalsection,weintroduceparametrizedstrategies,whoseparametersshouldbeestimatedwiththehelpofsimulation.Indeed,simulationbasedoptimiza-tion,overthepolicyspace,providesusanalternativetoBellman’sprinciple,allthemoreinterestingasthisprinciplemightbecomehardtoapply,whenthecardinalityofthestatespaceincreases.Keywords:Hosemodel,MarkovDecisionProcess,Bellman’soptimalityprinciple,stochasticGames,Cross-Entropymethod1IntroductionDuringthelastdecades,manymethodshavebeendevelopedtotackletheratherhardproblemoftrafficmatrixestimation.Ourpurposeinthisarticleisnottodevelopanewmethodfortrafficmatrixestimation,butrathertoconsidertheproblemunderasystemorientedpointofview.Indeed,oursystemismadeofatelecommuni-cationnetworkofnodesanddirectedlinks.Theoperator,orthenetworkmanagerhasthepossiblitytoactonthebandwidthreservation,inviewoftheevolutionofthetrafficgoingthroughthewholenetwork.Weassumethat,ateachglobalbandwidthallocation,thetrafficevolves,followingtheworstconfigurationinthesenseofaQualityofService(QoS)criterion.Thenetworkoperatorshouldbeabletoforecasttheworstpossibleevolutionofthetraffic,andtoproposesolutionssoastodrivethenetworkinanoptimalway.InthecontextofVirtualPrivateNetworks,guaranteeinganadmissibleQoS,viareservedbandwidths,loss,anddelaycharacteristics,isacrucialtaskforthenetworkmanager.VirtualPrivateNetworks(VPNs)arenetworksbuiltbetweengeographicallydistantIP-sitesofafirm.Withthehelpofthistechnology,distantsitesofthesamefirmareabletocommunicateviasecuredtunnels.Indeed,thedatashouldbetransmittedviaInternet,whichisapublicinfrastructuresharedbymanyoperators.Inordertoguaranteethesecurityofitsclient,thedatawillbeencryptedandsentalongvirtualtunnelsusingMPLStech-nology.Besides,aServiceLevelAgreement(SLA)contractshouldbepassedbetweenthenetworkprovideranditsclient.TheaimofthistreatyistospecifyboundsonadmissiblelevelsofQoS.Asaresult,themanagershouldbeabletoforecastboththespatialandthetemporalevolutionofitstraffic.Traditionalytrafficmatricesareusedtosolvesuchproblems.Nevertheless,theiraccuracyrelymainlyonthequalityoftheestimatoritselfandofthedata,whichcanbequitehazardous.Thesolutionwehavechosentogetaroughcharacterizationofthetraffic,istousethehosemodel,introducedforthefirsttimein[1].Theclientisaskedtomerelyspecify:-theamountoftrafficgoingin/outeachofitswebsites,-therelationshipsbetweenallitswebpoints(source→destination).Youcancheckthat,althoughthehosemodelisquitesimpletospecifyfromtheclientpointofview,itisfullofuncertaintyforthemanager.Indeed,foreachsourcenode,forexample,theoperatorignoreshowthetrafficissharedbetweenthedifferentdestinationnodes,whichconstitutesinitselfaspatialuncertainty.Furthermore,duetotheroughtnessofthisapproach,hedoesnotknowhowthetrafficshouldevolveunderthisassumption.Consequently,wehavechosentomodelthedynamicevolutionofthetrafficasaMarkovdecisionprocess(MDP),whichenablesustointroduceuncertainty,inourmodel.Indexofthemainnotations,usedextensivelythroughoutthearticle.-{X(t)}t∈N-discretetime,discretestatespacestochasticprocessmodelingthetrafficintheVirtualPrivateNetwork1.-X(t)ij-trafficgoingfromthenodeitothenodej,atthedecisionepocht.-S-genericstatespace.-{L(t)}t∈N-trafficontheMPLSnetworklinks.-N-setofthesites,ornodesoftheMPLSnetwork.-L-setofthelinksoftheMPLSnetwork.-tout1-amountoftrafficleavingthesite1oftheVPN1.-tout2-amountoftrafficleavingthesite2oftheVPN1.2Figure1:Thehosemodel.Asanexample,weconsiderthehosemodelappliedtoasmallnetwork.Thefirmiscomposedof5differentIPsites,whicharesupposedtobegeographicallydistant.Forthesite1,whichissupposedtobetheheadofthefirm,theclientgivestheopera