Non-Convex Optimization and Rate Control for Multi

1Non-convexOptimizationandRateControlforMulti-classServicesintheInternetJang-WonLee,RaviR.Mazumdar,andNessB.ShroffSchoolofElectricalandComputerEngineeringPurdueUniversityWestLafayette,IN47907,USA{lee46,mazum,shroff}@ecn.purdue.eduAbstractInthispaper,weinvestigatetheproblemofdistributivelyallocatingtransmissiondataratestousersintheInternet.Weallowuserstohaveconcaveaswellassigmoidalutilityfunctionsasappropriatefordifferentapplications.Intheliterature,forsimplicity,mostworkshavedealtonlywiththeconcaveutilityfunction.However,weshowthatapplyingratecontrolalgorithmsdevelopedforconcaveutilityfunctionsinamorerealisticsetting(withbothconcaveandsigmoidaltypesofutilityfunctions)couldleadtoinstabilityandhighnetworkcongestion.Weshowthatapricingbasedmechanismthatsolvesthedualformulationcanbedevelopedbasedonthetheoryofsubdifferentialswiththepropertythattheprices“self-regulate”theuserstoaccesstheresourcesbasedonthenetutility.Wediscussconvergenceissuesandshowthatanalgorithmcanbedevelopedthatisefficientinthesenseofachievingtheglobaloptimumwhentherearemanyusers.I.INTRODUCTIONOverthelastdecades,therehasbeenasignificantamountofinterestintheareaofInternetratecon-trol,whichaimsatprovidingsatisfactoryservicesandalleviatingcongestionintheInternet.Currently,mostservicesintheInternetareelastictosomedegree,i.e.,thesourcescanadjusttheirtransmissionThisresearchhasbeensupportedinpartbyNSFgrantsANI-0073359,ANI-9805441,andANI-0207728.2dataratesinresponsetocongestionlevelswithinthenetwork.Hence,byappropriatelyexploitingtheelasticitythroughratecontrol,onecanmaintainhighnetworkefficiencywhileatthesametimeallevi-atingnetworkcongestion.Tothatend,itisnecessarytohaveanappropriatemodeltocharacterizetheelasticityoftheservice.Thisistypicallydoneusingthewell-knownconceptofautilityfunctionthatrepresentsthelevelofusersatisfactionorQualityofService(QoS)attheallocatedrate.WecanclassifyservicesintheInternetintotwoclassesbasedontheshapeoftheutilityfunction.Onecorrespondstotraditionaldataservices,suchasfiletransferandemail.Theseservicescanadjusttheirtransmissiondataratesgradually,resultingingracefuldegradationoftheQoSinthepresenceofnetworkcongestion.Theelasticityoftheseservicescanbemodeledbyconcaveutilityfunctions[1].Theothercorrespondstodelayandrateadaptiveservices,suchasstreamingvideoandaudioservices.Theseservicesarelesselasticthandataservices.Inresponsetonetworkcongestion,theycandecreasetheirtransmissiondataratesuptoacertainlevelwithacorrespondinggracefuldegradationintheQoS.However,decreasingthetransmissiondataratebelowacertainthresholdresultsinasignificantdropintheQoS(e.g.,belowacertainbitrate,thequalityofaudiocommunicationfallsdramatically).Theelasticityoftheseservicescanbemodeledbyusingsigmoidal-likeutilityfunctions[1].Wecallanincreasingfunctionf(x)asigmoidal-likefunction,ifithasoneinflectionpointxo,andd2f(x)dx20,forxxoandd2f(x)dx20,forxxo,asshowninFig.1.Inthepastfewyears,utilitybasedratecontrolproblemshavebeguntobeaddressedbythenetwork-ingresearchcommunity[2],[3],[4],[5],[6],[7],[8],[9].TheyhavealmostexclusivelydealtwiththesituationwheretheutilitiesareconcaveforwhichthereexistextensivetheoriesandalgorithmssuchasDatarateUtilityFig.1.Asigmoidal-likefunction.3theKarush-Kuhn-Tucker(KKT)conditionsandthedualitytheorem.However,asmentionedbefore,concaveutilityfunctionsareappropriateonlyformodelingtraditionaldataservices,anddonotcapturethecharacteristicsofservicessuchasaudioandvideothatarebecomingincreasinglypopularintheInternet.Hence,fortheefficientallocationoftransmissionratesamongserviceswithdiversecharacter-istics,aratecontrolalgorithmmustbeabletoefficientlyhandledelayandrateadaptiveserviceswithsigmoidal-likeutilityfunctionsaswellasdataserviceswithconcaveutilityfunctions.Butthisresultsinthenon-convexityofthesystem,whichis,ingeneral,difficulttohandle.Anaturalandlogicalapproachtodealingwiththeissueofnon-convexityistosimplyapproximateasigmoidal-likeutilityfunctionwithaconcavefunctionanduseoneofthealgorithmsdevelopedforconcaveutilityfunctions.However,thisapproachcouldresultinahighlyinefficientsolution.Forexample,supposethatasystemhasasinglebottlenecklinkwithcapacity10Mbpsand11users.Further,supposethateachuserhasthesameutilityfunctionU(x)thatisastepfunctiondescribedbelow:U(x)=0,ifx1Mbps1,ifx≥1Mbps.Notethatthestepfunctionisanextremecaseofasigmoidal-likefunction.IfweapproximateU(x)withaconcavefunction,U′(x),wecanapplyanalgorithmforconcaveutilityfunctionsthathasbeenproposedintheliteraturetomaximizethetotalsystemutility.Inthiscase,sinceallusershavethesameconcaveutilityfunctions,attheglobaloptimalsolution,eachuserisallocatedthesameamountofrate,x∗=1011Mbps,whichprovidesU(x∗)=0.Hence,withthisapproach,weachievezerototalsystemutilityfortheoriginalutilityfunction.However,byallocating1Mbpsto10usersandzerotooneuser,wecanachieveatotalsystemutilityof10units.Eventhoughthisexampleconsidersanextremecase,itemphasizesthattoefficientlyaccommodatediverseservicesintheInternet,itisnecessarytodeveloparateallocationalgorithmthattakesintoaccountthepropertiesofbothconcaveandsigmoidal-lik