Call admission control schemes under the generaliz

ISSN0249-6399apportderechercheINSTITUTNATIONALDERECHERCHEENINFORMATIQUEETENAUTOMATIQUECallAdmissionControlSchemesundertheGeneralizedProcessorSharingSchedulingZhi-LiZhang,ZhenLiu,JimKurose,DonTowsleyN˚2711Novembre1995PROGRAMME1CallAdmissionControlSchemesundertheGeneralizedProcessorSharingSchedulingZhi-LiZhang,ZhenLiu,JimKurose,DonTowsleyProgramme1|Architecturesparalleles,basesdedonnees,reseauxetsystemesdistribuesProjetMISTRALRapportderecherchen2711|Novembre1995|28pagesAbstract:ProvisionofQuality-of-Service(QoS)guaranteesisanimportantandchallengingissueinthedesignofintegrated-servicespacketnetworks.Calladmissioncontrolisanintegralpartofthechallengeandiscloselyrelatedtootheraspectsofnetworkssuchasservicemodels,schedulingdisciplines,traccharacterizationandQoSspecication.InthispaperweprovideatheoreticalframeworkwithinwhichcalladmissioncontrolschemeswithmultiplestatisticalQoSguaranteescanbeconstructedfortheGeneralizedProcessorSharing(GPS)schedulingdiscipline.Usingthisframework,wepresentseveraladmissioncontrolschemesforbothsession-basedandclass-basedservicemodels.ThetheoreticalframeworkisbasedonrecentresultsinthestatisticalanalysisoftheGPSschedulingdisciplineandthetheoryofeectivebandwidths.Bothoptimalschemesandsuboptimalschemesrequiringlesscomputationaleortarestudiedundertheseservicemodels.TheQoSmetricconsideredislossprobability.Key-words:Asymptoticdecayrate,Calladmissioncontrol,Eectivebandwidths,Feasibilitytest,GeneralizedProcessorSharingscheduling,Lossprobability,Networkservicemodels,Qualityofservice.(Resume:tsvp)Correspondence:ZhenLIU,INRIACentreSophiaAntipolis,2004RoutedesLucioles,B.P.93,06902SophiaAntipolis,France.E-mail:[e-mail]´derechercheINRIASophia-AntipolisMecanismesdeContr^oled’AdmissionsouslaDisciplineProcesseurPartageGeneraliseResume:LagarantiedeQualitedeService(QS)estunaspectimportantdanslaconceptiondesreseauxahaut-debit.Lecontr^oled’admissionfaitintegralementpartiedecedeetestetroitementlieauxautresaspectsdesreseauxtelquelesmodelesetdisciplinesdeservice,lacaracterisationdutracetlaspecicationdeQS.Danscetarticlenousfournissonsuncadretheoriquedanslequeldesmecanismesdecontr^oled’admissionavecdemultiplegarantiesstatistiquesdeQSpeuventseconstruirepourladisciplinedeserviceprocesseurpartagegeneralise(GPS).CecadretheoriquesebasesurlesresultatsrecentsenanalyseprobabilistedeladisciplineGPSetsurlatheoriedelabandepassanteeective.Nouspresentonsainsiplusieursmecanismesdecontr^oled’admissionpourlesmodelesdeservicetantauniveauclientqu’auniveausession.NousconsideronsletauxdepertecommecriteredeQS,etnousetudionsdesschemasoptimauxetsousoptimauxquirequierentunco^utdecalculmoinsimportant.Mots-cle:tauxdedecroissanceasymptotique,contr^oled’admission,bandepassanteeective,processeurpartagegeneralise,tauxdeperte,qualitedeservice.CallAdmissionControlSchemesunderGPS31IntroductionProvisionofQuality-of-Service(QoS)guaranteesisanimportantandchallengingissueinthedesignofintegrated-servicespacketnetworks.Calladmissioncontrolisanintegralpartoftheproblem.Clearly,withoutcalladmissioncontrol,providingQoSguaranteeswillbeimpossible.Thetaskofcalladmissioncontrolcanbemosteasilyillustratedbyconsideringthefollowingquestion:Givenanewcall/sessionthatarrivestoanetwork,canitbeacceptedbythenetworkatitsrequestedQoS,withoutviolatingexistingQoSguaranteesmadetoon-goingcalls?Thisseeminglysimplequestionturnsouttobeverycomplicated,astheissueofcalladmissioncontroliscloselyrelatedtootheraspectsofanetwork,suchasservicemodels,schedulingdisciplines,traccharac-terizationandQoSspecication.CalladmissioncontrolwithstatisticalQoSguaranteesisaparticularlyimportantandchallengingproblem,particularlyforaheterogeneousmixtureofapplicationswithdieringQoSrequirements.InthispaperweconsiderthecalladmissioncontrolissueforanetworkusingGeneralizedProcessorSharing(GPS)schedulingatitsswitchesandsupportingmultiplestatisticalQoSguarantees.Weidentifyseveralservicemodelsthatarelikelytobeprovidedbyfutureintegratedservicespacketnetworks,andproposecorrespondingcalladmissionschemesforthem.Includedarebothoptimalschemesandsuboptimalschemesrequiringlesscomputationaleort.ThetheoreticalfoundationforourproposedschemesisbasedonrecentresultsinthestatisticalanalysisofGPSscheduling[27,30]andthetheoryofeectivebandwidths[17,14,15,18,12,19,25,4,16,20].ThestatisticalQoSmetricconsideredislossprobability.WefocusonGPS(alsoknownasWeightedFairQueueing)[10,22,23]becauseitprovidescontrolledsharingofbandwidthandisolationamongsessions(orclasses).In[8,24],GPSisrecommendedasaschedulingdisciplinewherethereareseveraldierentserviceclasseswhichmustbesupported.TheauthorsarguethatperhapsthemostimportantfeatureofGPSisitsabilitytoisolatevariousserviceclasseswhile,atthesametime,allowingbandwidthsharingamongclasses.Inaddition,thereisarichliteratureanalyzingGPSinavarietyofsettings.In[22,23],per-sessionboundsontheworst-casebackloganddelayarederivedforbothasingleGPSserverinisolationandanetworkofGPSserversunderadeterministicsetting.GPShasa