Communication Delay and Instability in Rate-Controlled Networks

CommunicationDelayandInstabilityin

Rate-ControlledNetworks

PriyaRanjan,EyadH.Abed,andRichardJ.La

Abstract—WeanalyzetheoptimizationframeworkforrateallocationproblemproposedbyKellyandcharacterizetheoscillationsintermsofunderlyingmap’speriodtwoorbitintheinstabilityregimewitharbitrarycommunicationdelay.Weshowtheoscillationscanbefairlylargebycom-putingtheboundsexplicitlyforlargereturntriptimes.

I.INTRODUCTION

WiththeunprecedentedgrowthandpopularityoftheInternettheproblemofrate/congestioncontrolisemergingasamorecrucialproblem.Poormanagementofcongestioncanrenderonepartofanetworkinaccessibletotherestandsignificantlydegradetheperformanceofnetworkingapplications.KellyhasproposedanoptimizationframeworkforrateallocationintheInternet[7].Usingtheproposedframeworkhehasshownthatthesystemoptimumisachievedattheequilibriumbetweentheendusersandresources.Basedonthisobservationresearchershaveproposedvariousrate-basedalgorithmsthatsolvethesys-temoptimizationproblemoritsrelaxation[7],[11],[12].How-ever,theconvergenceofthesealgorithmshasbeenestablishedonlyintheabsenceoffeedbackdelay,andtheimpactoffeed-backdelayhasbeenleftopenaswellasanytrade-offthatmayexistbetweenstabilityandselectedutilityandcostfunctions.Inparticulartheissueofstabilityhasnotbeensystematicallyinvestigatedwithlargecommunicationdelays.

Inourearlier[15]wehaveestablishedaglobalstabilitycri-terionforsystemoptimizationprobleminthepresenceofarbi-trarydelayforsimpleoneresourceproblemwithmultipleho-mogeneousflows.Thisstabilityconditionwasderivedusingtheinvariance-basedglobalstabilityresultsfornonlineardelay-differentialequations[13],[5],[4],[3].ThiskindofglobalstabilityresultsaredifferentfromthatbasedonLyapunovorRazumikhintheoremsinthesensethatinourapproachalsopro-videsuswithinsightonthestructureofemergingperiodicor-bits,e.g.,theirperiodicityandamplitude,inthecaseoflossofstability.Thislossofstabilityandcharacterizationofensuingperiodicorbitaremaintopicsofthispaper.

Generallyspeaking,ourresultstellusthatiftheuserandresourcecurveshaveastablemarketequilibrium,thencorre-spondingdynamicalequationforflow-optimizationwillcon-vergetotheoptimalsolutioninthepresenceofarbitraryde-lay.Thisresultessentiallyshowsthatstabilityisrelatedtoutil-ityandpricecurvesinafundamentalway.Inparticular,foragivenpricecurve,itpossibletodesignstableuserutilityfunc-tionssuchthatthecorrespondingdynamicalsystemconvergestotheoptimalflowirrespectiveofcommunicationdelay.Con-versely,iftheunderlyingmarketequilibriumisunstablethenitispossibletofindalargeenoughdelayforwhichtheoptimal

TheauthorsarewiththeDepartmentofElectricalandComputerEngineeringandtheInstituteforSystemsResearch,UniversityofMaryland,CollegePark,MD20742USA.Email:priya@isr.umd.edu.

pointlosesitsstabilityandgiveswaytooscillations.Thispa-perstudiestheoscillatoryorbitsbyexplicitlygivingtheboundsontheiramplitude.Itisalsoshownthattheseboundsarede-rivedfromanunderlyingdiscretetimemapwhichgoesthroughaperioddoublingbifurcationwiththelossofstability.

Theseresultsprovideaninterestingperspectivefordesign-ingenduseralgorithmsandactivequeuemanagement(AQM)mechanisms.Itisalsoworthnotingthatingeneralcharacter-izingtheexactconditionsforstabilitywithadelayisdifficult.Hence,ourresultprovidesasimpleandyetrobustwayofdeal-ingwiththeproblemofwidelyvaryingfeedbackdelayincom-municationnetworksthroughacleverchoiceoftheuserutilityfunctionandpricefunctions.

Thispaperisorganizedasfollows.SectionIIdescribestheoptimizationproblemforratecontrol.Relevantpreviousworkonthestabilitycriterionofasystemgivenbyadelayeddifferen-tialequationisgiveninSectionIII.Ourmainresultsoninstabil-ityarepresentedinSectionIV,whichisfollowedbynumericalexamplesinSectionVI.WeconcludethepaperinSectionVII.

II.BACKGROUND

Inthissectionwebrieflydescribetheratecontrolproblemintheproposedoptimizationframework.Consideraflowtravers-ingasingleresource.Theratecontrolproblemcanbeformu-latedasthefollowingnetutilityoptimizationproblemfromtheenduser’spointofview[7]:

(1)

s.t.

whereistherate,istheutilityoftheuserwhenitreceives

arateof,

isthepriceperunitflowtheuserhastopaywhentherateis,andisthecapacityoftheresource.Theproposedenduseralgorithmintheabsenceofdelayisgivenbythefollowingdifferentialequation[9].

.

Now,supposethatcongestionsignalgeneratedatthesharedre-source,i.e.,

,isreturnedtotheuserafterafixedandcom-monroundtriptime.Inthepresenceofdelaytheinteractionisgivenbythefollowingdelayeddifferentialequation

CDC2003

(4)Afternormalizingtimebyandreplacing

,eq.4

becomes:

(6)

where

(7)

ofgeneralnonlineardifferenceequationwithcontinuousargu-mentgivenby

(8)

whereandinthecontextofeq.6.

Undercertainnaturalinvertibilityconditionson

,itleadstomuchstudiedequation[16].

(9)

where.Forthesolutionofeq.9tobe

continuousfor

,alongwiththecontinuityofand,whichistheinitialfunction,aso-calledconsistencycondition

isrequired[5],[16].

Itturnsoutthatagreatdealabouttheasymptoticstabilityofeq.7canbelearnedfromtheasymptoticbehavioroffollowingdifferenceequation,withdenotingthesetofpositiveinte-gers:

(10)

Someofrelevantpreviousworkontheseequationsispre-sentedinthefollowingsection.

III.PREVIOUSWORK

Inthissectionwesummarizesomeofrelevantworkpresented

in[4].Consideranonlineardelaydifferentialequationofthefollowingform:

(11)

wherefunctionsandarecontinuousfor

withthevaluesin.wemakefollowingadditionalassump-tionsthesefunctions:

1.

isstrictlyincreasing,,and,

2.thereisexactlyonepoint

andin

.

2

isthegloballyattractingfixedpointof

themap,thenforanyinitialfunction

andeverythecorrespondingsolutionofeq.12approaches

where

(13)

Thiskindofmarkingfunctionarisesiftheresourceismodeledasqueuewithaserviceratepacketperunittimeandapacketreceivesamarkwithacongestionindicationsignalifitarrivesatthequeuetofindatleastpacketsinthequeue.Gen-erally,anystrictlyincreasingcontinuousfunctionshouldsufficeforourpurpose.

Theclassofutilityfunctionsweconsiderherehastheform

(14)

Inparticular,hasbeenfoundusefulformodelingthe

utilityfunctionofTransmissionControlProtocol(TCP)algo-rithms[10].Wesaythatauser

withutilityfunctionisgreedierthananotheruserwithutilityfunction.Onecaninterpretthenotionofgreedhereusingthe

if

notionofelasticityofdemand[17].Withtheutilityfunctionsoftheformineq.14onecaneasilyshowthattheelasticityofthedemanddecreaseswithincreasingasfollows.Givenaprice,theoptimalrateoftheuserthatmaximizesthenet

utility

isgivenby(15)

Therefore,onecanseethatpriceelasticityofthedemandde-creaseswith,i.e.,thelargeris,thelessresponsivethede-mandis.

Themodelusedfordesignofend-userratecontrolalgorithmin[8]doesnotexplicitlyaddressthecasewherethetotalde-mandoftheusersexceedsthelinkcapacity.Inpracticetotalrateoftheusersislimitedbythelinkcapacity.Inordertohan-dlethisshortcomingofthemodelwemakefollowingnaturalassumption:

CDC2003Assumption1:Supposethattherearehomoge-neoususers,i.e.,userswiththesamefeedbackdelayandrate.Weassumethattherateofeachuserisboundedfromaboveby

mayexceedthetotalthrough-putmomentarilyleadingtoseverepenaltiesforalltheusers.Thisboundalsomakessenseduetothefactthatnetworkedusershaveatendencytosynchronize[6].

Inthepresenceoftimedelay,

homogeneousenduserswiththeirutilityfunctionineq.14,eachusersratedynamicalequationisgivenby

(16)

Bysubstituting

(17)

where

and

(19)

Wefirstmakethefollowingassumptionsonthefunctionsand.

Assumption2:(i)Thefunction

asgivenineq.18isstrictlydecreasingwithforall.(ii)The

function

isincreasingforall(iii)BothandareLipschitzcontinuousonstrictlypositiverealaxis.Forourresultsinthispapertheexactformofusers’utilityfunctionsortheresourcepricefunctionneedsnotbegivenbyeq.14and13,respectively,butrathermustsatisfyAssump-tion2.Thisallowsusthefollowingchangeofcoordinate:

(20)

3

whereisanunstablefixedpoint

ofmap.Inthefollowingsubsectionwedescribehowtheinstabilityofunderlyingdiscrete-timemapistranslatedtotheinstabilityofdelay-differentequationineq.23.

B.LinearInstability

Assumingthatthemapgivenbyeq.24islocallysmooth,

itispossibletofindconditionsforlinearinstabilityofthefixed

pointofthemap

andthatofconstantfunctionforthedelay-differentialequationineq.23.Inorderfor

CDC2003tobelocallyasymptoticallystableforall,followingvariationalequationshouldhaveitszerosolutionstable.

(because

)

(25)

whereand.Nowtodetermine

thestabilityof

,wecanapplywellknownresults[14].(1)Itisknownthateq.25isstableforall

onlyif:and

(26)

(2)Incasewhenaboveisviolatedwehavepartialstabilityfor

somevaluesoftimedelays:

and

(27)

Forourcaseitfollowsfromeq.25thatisalways

negative,whichholdsduetofactthat

isalwayspositive.Thesecondconditioniscrucialtostabilityofeq.23.

Clearly,forthecasewhen

(perioddoublingconditionforthemap)thelinearstabilityconditiongivenbyeq.26isvi-olatedandforalargeenoughtheconstantsolution

willnotbestable.Thus,weknowthatinunstablesituationso-lutionswillbemorecomplexthanaconstantfunctionandwillstaywithintheintervaltheyinitiallystartfromduetotheinvari-anceresultsgivenbytheorem3.Nextweshowthatincaseofinstabilitytheboundsonthesolutionofdelay-differentialequa-tionwillbegivenbytheperiodtwosolutionofunderlyingdis-cretetimemap.

Theorem5:Let

beaclosedintervalsuchthat.Lettheinitialcondition,

where

,bethesolutionofeq.23.Now,ifandthe

points

andarefixedpointsof,thenforallsufficientlysmallthereexistsafinitesuchthat

forall.

Proof:TheprooffollowsthesameargumentsusedintheproofofTheorem3,whichisgivenin[15],exceptthatboundaryconsideredthistimewillsolutionwillbestrictlydecreasingfromright.untilIntheinterval

.fromAfterwardsabove.fromSimilarinvariancereasoningtheoremfollowsititstaysreachesthepointforlowerboundedbound.

by4

andisindependent

of.Therefore,thestabilityofthesystemdoesnotdependonthenumberofusersinthesystem.Thiscanalsobeexplainedusingthepriceelasticityofdemand.Since,givenautilityfunc-tionoftheformineq.14forsome,thepriceelasticity

ofthedemandisconstantforall

fromeq.15,onewouldexpectthestabilityofthesystemtobeindependentoftheop-eratingpoint,i.e.,thefixedpoint,andcapacity,butonlyonthechoicesoftheutilityandpricefunctionsthatdeterminethere-sponsivenessoftheusersandresource,respectively.

However,inthecaseofinstabilitywhen

,dependingonthefeedbackdelay,itwilloscillate.Clearly,theupperboundonthesolutionisgivenbytheself-imposedlimit

CDC20035

userstoavoidanycapacitymismatch.AccordingtoTheorem5thelowerboundwillbegivenby.Hence,linkwillseeawidefluctuationfromfulltoverylowutilizationirrespectiveofthenumberofusers.

VI.NUMERICALSIMULATIONS

Wetaketwohomogeneoususerswiththeirutilityfunctionsandpricefunctionasinoftheformgivenbyeq.14with

andlinkcapacitytobe5.Itisclearthatforeq.13with

thesevaluesofandratecontrolalgorithmisunstablesince

CDC20036

[9][10][11][12][13][14][15][16][17]F.Kelly,A.Maulloo,andD.Tan.Ratecontrolforcommunicationnet-works:shadowprices,proportionalfairnessandstability.JournaloftheOperationalResearchSociety,49(3):237–252,March1998.

S.KunniyurandR.Srikant.End-to-endcongestioncontrolschemes:Util-ityfunctions,RandomlossesandECNmarks.InProc.ofIEEEINFO-COM,Tel-Aviv,Israel,2000.

S.KunniyurandR.Srikant.Atimescaledecompositionapproachtoadap-tiveecnmarking.InProc.ofIEEEINFOCOM,Anchorage,AK,2001.S.LowandD.Lapsley.Optimizationflowcontrol.IEEE/ACMTransac-tionsonNetworking,7(6):861–874,June1997.

J.Mallet-ParetandR.D.Nussbaum.Globalcontinuationandasymptoticbehaviourforperiodicsolutionsofadifferential-delayequation.AnnalidiMatematicaPuraedApplicata,145(4):33–128,1986.

S.Niculescu,E.I.Verriest,L.Dugard,andJ.Dion.Stabilityandrobuststabilityoftimedelaysystems:Aguidedtour.StabilityandControlofTime-DelaySystem,LNCS:228:16–17,1997.

P.Ranjan,E.H.Abed,andR.J.La.Greed,delayandstabilitytradeoffsinnetworkeconomics.SubmittedtoGlobecom,2003.

ANSharkovsky,Y.L.Maistrenko,andE.Y.Romaneko.DifferenceEqua-tionsandtheirapplications:(Trans.fromRussian).KluwerAcademic,1995.

HalR.Varian.IntermediateMicroeconomics.Norton,NewYork,1996.