Hop-by-hop Congestion Control over a Wireless Multi-hop Network

Hop-by-hopCongestionControloveraWireless

Multi-hopNetwork

YungYiandSanjayShakkottai

Abstract—Thispaperfocusesoncongestioncontrolovermulti-hop,wirelessnetworks.Inawirelessnetwork,animportantconstraintthatarisesisthatduetotheMAC(MediaAccessControl)layer.ManywirelessMACsuseatime-divisionstrategyforchannelaccess,where,atanypointinspace,thephysicalchannelcanbeaccessedbyasingleuserateachinstantoftime.Inthispaper,wedevelopafairhop-by-hopcongestioncontrolalgorithmwiththeMACconstraintbeingimposedintheformofachannelaccesstimeconstraint,usinganoptimizationbasedframework.Intheabsenceofdelay,weshowthatthisalgorithmaregloballystableusingaLyapunovfunctionbasedapproach.Next,inthepresenceofdelay,weshowthatthehop-by-hopcontrolalgorithmhasthepropertyofspatialspreading.Inotherwords,focusedloadsataparticularspatiallocationinthenetworkget“smoothed”overspace.Wederiveboundsonthe“peakload”atanode,bothwithhop-by-hopcontrol,aswellaswithend-to-endcontrol,showthatsignificantgainsaretobehadwiththehop-by-hopscheme,andvalidatetheanalyticalresultswithsimulation.

Keywords:Controltheory,Mathematicalprogram-ming/optimization

I.INTRODUCTION

Weconsidertheproblemofcongestioncontroloverwire-less,multi-hopnetworks.Nodesinsuchnetworksareradio-equipped,andcommunicatebybroadcastingoverwirelesslinks.Communicationpathsbetweennodeswhicharenotinradiorangeofeachotherareestablishedbyintermediatenodesactingasrelaystoforwarddatatowardthedestination.Thediverseapplicationsofsuchnetworksrangefromcommunitybasedroof-topnetworkstolarge-scalead-hocnetworks.

Overthepastfewyears,theproblemofcongestioncontrolhasreceivedwide-spreadattention,bothintheInternetcontext[1],[2],[3],aswellasinanad-hocnetworkcontext[4].Mostofthisresearchhasfocusedonmodeling,analysis,algorithmdevelopmentofend-to-endcontrolschemes(suchasTCP),andadaptationofsuchschemestoad-hocnetworks.Givenroutingpathandbandwidthconstraints,algorithmshavebeendevelopedwhichconvergeandhaveastableoperation.

Inawirelesscontext,however,animportantadditionalconstraintthatarisesisthatduetotheMAC(MediaAccessControl)layer.ManywirelessMACsuseatime-divisionstrategyforchannelaccess[5],[6],where,atanypointinspace,thephysicalchannelcanbeaccessedbyasingleuserat

ThisresearchwassupportedbyNSFGrantsACI-030andCNS-0325788,andagrantfromtheTexasTelecommunicationsEngineeringProgram(TxTEC).TheauthorsarewiththeWirelessNetworkingandCommunicationsGroup,DepartmentofElectricalandComputerEngineering,TheUniversityofTexasatAustin,email:{yi,shakkott}@ece.utexas.edu.AshorterversionofthispaperappearedintheProceedingsofIEEEInfocom,,March,2004.

eachinstantoftime(atimeconstraint).Thispaperformulatesanoptimizationframeworkforcongestioncontrolalgorithminwirelessmulti-hopnetworkswiththeconstraintimposedbytheMAC.Wedevelopadistributed,hop-by-hopcongestioncontrolscheme,whichisshowntobestableintheabsenceofpropagationdelays.

Hop-by-hopcongestioncontrolalgorithmshavebeenstud-iedintheInternetcontext[7],[8],[9].Suchschemesprovidefeedbackaboutthecongestionstateatanodetothehopprecedingit.Theprecedingnodethenadaptsitstransmissionratebasedonthisfeedback.Feedbackistypicallyprovided[7],[8],[10],[11],[9]basedonthequeuelengthatthecongestednode.Ifthequeuelengthexceedsathreshold,congestionisindicatedandtheprecedingnodeisnotifiedinordertodecreaseitstransmissionrate.Itiswellknownthatsuchschemes,byreactingtocongestionfasterthanend-to-endschemes(thebottlenecknodewouldsendfeedbackbackward,thusdecreasingthedelayinthecontrolloop),resultinbetterperformancethanacorrespondingend-to-endscheme.How-ever,Internetcongestioncontrolhasbeendominatedbyend-to-endschemes(inparticular,TCP),andresearchinalternatemechanismsintherecentpasthasfocusedonthesame[1],[3],[2],primarilyduetoscalabilityanddeployability.Hop-by-hopschemesrequiretohaveper-flowstatemanagementinintermediatenodes,whichgeneratesscalabilityproblems.However,inawirelessnetwork,thenumberofflowspernodeisofamuchsmallerorderthanintheInternet.Further,wirelessnetworksusuallyhaveper-flowqueueingforreasonsofpacketscheduling[5],andthefactthatdifferentusersareatdifferentlocations,thusrequiringdifferentphysicallayerstrategies(suchasthechannelcodingandmodulationschemeofthepowerlevel).Thus,wearguethathop-by-hopschemesarefeasibleoverawirelessnetwork.

Inthispaper,wedevelopahop-by-hopcontrolscheme,whichisshowntoconvergeintheabsenceofdelay,andallocatesbandwidthtovarioususersinaproportionally-fairmanner.Inthepresenceofdelay,weshowthatithasthepropertyofspatialspreading.Inotherwords,focusedloadsataparticularspatiallocationinthenetworkget“smoothed”overspace.InFigure1,weillustratethiseffect.Consideranodeaccessedbyanumberofflows.Whileanend-to-endcontrolschemecouldresultinlargetransientoverloads(duetodelayedfeedback)atasinglenode,ahop-by-hopschemewill“push-back”andcausecongestiontooccuroverspace,resultinginsmallerpeakoverloads.Thus,evenifthebottlenecknodeisveryclosetothereceiver(the“worst-case”forahop-by-hopscheme),therearepotentialgainstobehadduetospatialspreading.Hence,evenifthetotalbuffer

Congested Region..Sources...Destinations.....2-D NetworkFig.1.SpatialSpreadingwithhop-by-hopcontrollers

requirementoverthenetworkisthesame,thehop-by-hopschemeensuresthatthebuffersrequiredarespatiallyspread.

II.MAINCONTRIBUTIONS

Themaincontributionsinthispaperare:

(i)Wedevelop(weighted)proportionally-faircongestion

controlalgorithms(bothhop-by-hopaswellasend-to-end)withtheMACconstraintbeingimposedintheformofachannelaccesstimeconstraint,usinganoptimizationbasedframework.Intheabsenceofdelay,weshowthatthesealgorithmsaregloballystableusingaLyapunovfunctionbasedapproach.

(ii)Weconsidertheevolutionofthesealgorithmsinthe

presenceofpropagationdelay.Weanalyticallyshowtheeffectofspatialspreading,byexplicitlyderivingthereductioninpeakbufferoverloadunderthehop-by-hopschemeforatreenetwork.Weshowthatatabottlenecknode,thedifferenceinthepeakqueuelengthbetweenanend-to-endschemeandahop-by-hopschemeisatleastoforderLαN,whereListhenumberofhops,Nisthenumberofsessions,andforsomeα≥1.A.RelatedWork

Theworkof[12],[2]providesanoptimizationbasedframe-workforInternetcongestioncontrolandderivesadifferentialequationbaseddistributedsolution.Worksof[13],[1],[14],[3],[15],[16]studythestabilityofsuchend-to-endcontrollersinthepresenceoffeedbackdelay.

In[8],[17],[7],[9],usingasimulationbasedapproach,theauthorsprovidehop-by-hopcontrolalgorithmsandshowthatthehop-by-hopschemesreactfasterthanend-to-endschemes,thusreducingbufferrequirements.In[10],theauthorproposesaframeworkforcongestioncontrolandroutingbasedonpush-back,where-in,queuebuildupatadown-streamnodecausesupstreamnodestodecreaserateandusealternatepaths.Thishasbeenextendedtothemulticastcasein[11].

Relatedworkincludes[18],wheretheauthorsconsidermax-minfairschedulinginthecontextofawirelessnetworkusingasimilarmodelasthatconsideredhereformediaaccesscontrol(MAC).Theauthorsdevelopatokenbasedlocalschedulingpolicyateachnodetoensuremax-minfairness.

2

Thispaperdiffersinthatwedevelopratebased(end-to-endandhop-by-hop)controllerswiththeobjectiveof(weighted)proportionally-fairresourceallocationamongusers,andwithMACconstraints.Wederiveexplicitboundsonqueuelengthsinthepresenceofpropagationdelay,bothwithanend-to-endandhop-by-hopscheme,anddemonstratespatialspreadingwithhop-by-hopcontrol.B.Organization

WebeginwithadescriptionofthesystemmodelinsectionIII,anddiscussanutilityfunctionbasednetworkoptimizationframework.

Next,inSectionVII,weillustratespatialspreadinginahop-by-hopalgorithmbymeansofderivingboundsonthepeakqueuelengthsinthepresenceoffeedbackdelay.WeprovidesimulationresultsinSectionVIIItovalidatetheanalysis.

III.SYSTEMMODEL

ConsideranetworkwithasetLoflinks,asetVofvertices(nodes),andletclbethefinitecapacityoflinkl,forl∈L.Eachvertexcorrespondstoanodeinthenetwork.Eachdataflowrinthenetworkcorrespondstoanorderedsequenceoflinksl∈L,andwedenoteRasthesetofpossiblesessions1.Thus,wemodelawirelesslinkbetweenanytwonodesinthenetworktohaveafinitepositivecapacity.

Inreality,wirelesschannelsaretime-varying[19],eachwithsomeaveragecapacitywhichwilldependonthephysicallayerscheme.However,inthispaper,wemodelthelinktohaveafixedcapacity.Suchamodelisaccurateintworegimes:(i)wherethechannelchangesaremaskedbythephysicallayercodingandmodulationschemesoastopresenta“constantchannel”tothehigherlayer,or,(ii)thechannelchangesmuchslowerthanthecongestioncontrolscheme.Inthiscase,usingatime-scaledecompositionargument,wecanthenformallyjustifyaconstantchannelmodelatthetime-scaleofthecongestioncontroller(thusleadingtoafluidmodelfortheMAC).Further,asin[18],weassumethatatanyinstantoftime,dataflowsthatdonotsharenodescantransmit/receivesimultaneously,butdataflowsthatshareanodecannotdoso.Inotherwords,simultaneoustransmissionscantakeplaceoverlinks(i.e.,betweenapairnodes)aslongasthelinksdonotshareacommonnode.

This,forinstance,modelsawirelesssystemwheremul-tiplefrequencies/codesareavailablefortransmission(usingFDMA/CDMA),andenablesparallelcommunicationsinaneighborhoodusingsuchorthogonalFDMA/CDMAchannels(see[18]foradditionaldiscussion).Inaddition,allowingsimultaneousparalleltransmissionscouldalsomodelwirelesssystemsthatemployinterferencecancellation[19].

Thus,accessconstraintsattheMAC/PHYlayersariseduetothefactthateachnodehasonlyasingletransceiver,andhencecannotperformmultipletransmissionsorreceptionssimultaneously.Wenextdescribetheconstraintsonthedataflowsthatfollowsfromthiswirelesssystemmodel.

1We

usethewords’session’and’flow’interchangeablythroughoutthis

paper.

3

A1C3D2Brestrictourselvestoonlytimeconstraints.Ingeneral,thetimeconstraintspresentedabovearenotsufficienttoensurethatafeasibleMACprotocolexists[18],[20].However,afeasibleMACalwaysexistsifthetimeconstraintsarerelaxedbyreplacingtheRHSoftheexpressions(i.e.,theterm’1’)byaparameterρ≤2/3.Thiscorrespondstothefactthat100%utilizationofresourcesateachnodemaynotbealwaysfeasiblebecauseofthenetworktopology(see[18]foranexample).However,ithasbeenshownin[20]thatifthetimeconstraintisrelaxedto2/3,afeasibleMACalwaysexists.A.AnOptimizationProblem

TimeConstraint

x1+x2c2x1+x3

x1+x2

LetusdenoteN(L),N(V),andN(R)asthenumberoflinks,nodes,andsessions,respectively.Foranylinklandsessionr,letAlr=1

≤1

x1+x2

c2x1+x3c2

≤1+

x1+x3

cj

Observethaty11canbeinterpretedasthefractionoftimenode’C’expendstoreceivedataofsession1fromnodeAoveranunitintervaloftime.Similarly,y13isinterpretedasthefractionoftimeexpendedbynode’C’totransmitdataofsession1tonodeDoveranunitintervaloftime.Similarinterpretationsholdforallyij.Thus,astotalfractionoftimeexpendedatnode’C’cannotexceed’1’,thetimeconstraintatnode’C’is

󰀄

yij≤1.

i,j

Similartimeconstraintsapplyforallothernodesinthenetwork.TableIpresentsvariouslinkandtimeconstraintsforthenetworkinFigure2.Aswecanobservefromthetable,thelinkconstraintsaresubsumedbythetimeconstraints.Anylinkconstraintistriviallyatimeconstraint,ifitistheonlyflowandterminatesatthenode.Inallothercases,thetimeconstraintisstrictlystrongerthanalinkconstraint.Thus,wedonotneedtoconsiderlinkconstraints,andwillhenceforth

developcongestioncontrolmechanismstosharethetimeresourcesinthenetworkina(weighted)proportionallyfairmanner.WeconsiderafluidmodelfortheMAC,anddonotfocusontheactualimplementationoftheresourceshar-ingmechanismateachnode.Forexample,anidealMACalgorithmwouldallowthemaximumpossible(subjecttoMACfeasibility)time-resourcesateachnodetobeusedforsuccessfuldatatransfer.However,anALOHAbasedMACwouldhaveinefficienciesassociatedwithit,whichwouldallowonlyafractionofthetimeresourcesatanodetobeusedforsuccessfuldatatransfer.Atthefluidtime-scale,thedetailsofthesedifferentMACprotocolsmanifestonlyasanefficiencyfactorthatiscapturedbytheparameter󰀱in(3),whichgovernsthefractionoftimethatthetimeresourceateachnodecanbeusedforsuccessfuldatatransfer.Asdiscussedearlier,theefficiencyfactorischosensuchthatsomeMACprotocolisfeasibleforthegivennetworktopology.Fromourearlierdiscussion,󰀱≥1/3ensuresthatatime-divisionMACisalwaysfeasibleindependentofthenetworktopology[20].Further,aninefficientMACscheme(suchasrandomaccess)wouldbeassociatedwithalargervalueof󰀱.

Thus,foranyfixedβ>0,andwithsessionratesx=(xr,r∈R),weneedtosolve

P:max󰀂

r∈Rwr

Tβ

log(xr)+λ(GAx−(1−󰀱)1).

(4)

Wedenotetheinputandoutputlinkofasessionronvwhenasessionrgoesthroughvasli(v,r)andlo(v,r),respectively(forinstance,inFigure2,areli(C,1)=1andlo(C,1)=3).Forcompleteness,forthesourceanddestinationnodes,wedefinecli(s(r),r)=∞andclo(d(r),r)=∞respectively,wherethesourceandthedestinationofsessionraredenotedbys(r)andd(r).LetusdenoteAj(r)asthesetofalldownstreamnodesfromjinthepathofsessionr.Thus,As(r)(r)isthecollectionofallnodesinthepathofsessionr.Bydifferentiating(4),wehave

dL

βx−󰀄󰀅(1)λjj∈As(r)(r)

lo(j,r)

󰀇=0(5)rc4

Therefore,theuniquesolutiontotheproblemPisgivenbythefollowingcondition:

xr=

wr

1

cli(j,r)

+

c+

1

li(j,r)

c+

1

li(j,s)

cli(j,r)

+

1

c1

li(j,r)

+

cli(j,r)

+

1

y

󰀎+

(9)

Asseenin(8),theparameteryofpj(y)isthesumofMAC

timeutilizationsbyallflows,bothincomingandoutgoing,atnodej.

Thus,pjdesired󰀈(y)marksthefractionofflowwhichexceedsatimethresholdtj.ObservethatthetotaltimeutilizationattheMACcannotexceed1.Thus,timeutilization(say,random󰀈tj<1isaparameterthatcontrolstheatthelink.Forinstance,foraninefficientMACaccess),onewouldsetWewilldiscussthechoiceofthisparameterinSection󰀈tjIV-C.

󰀒1.C.StabilityAnalysis

Inthissection,weshowthatthesystemofcontrollersdefinedin(7)isgloballystable.Theproofisanalogoustothatin[12].LetthefunctionU(x)bedefinedbyPU(x)=−

s∈D(j)

xs(t)(

1

clo

(j,s)

)

pj(y)dy

∈V

0

+

󰀄󰀆

r󰀄jwr

∈R

V.DISTRIBUTEDHOP-BY-HOPALGORITHM

Inthissection,wedevelopadistributedhop-by-hopal-gorithmforcongestioncontrol.First,weobservethatthecongestioncontrolleratthesourceofeachsessionreactsbasedonthesumofthecongestionpricesateachnode.Insteadofpassingthisfeedbackdownstreamasintheend-to-endalgorithm,onecouldenvisageaschemewhereeachnodepassesthe(partialsum)priceupstream.Inotherwords,eachnodeaddsitscurrentcongestioncosttothatitreceivedfromadownstreamnode,andpassesthisinformationtowardtheupstreamnode.Thesourcewillultimatelyreceivethesumofallpriceinformationfromthecorrespondingdownstreamnodesandusetheinformationforcontrollingrates.WerefertoFigure3fortheillustrationofthehop-by-hopalgorithm.Thebasicideaofahop-by-hopalgorithmisthateverynodeinthepathofthesessionoperatesacongestioncontrolalgorithm.InFigure3,thecongestionpriceatnodeCispassedtotheupstreamnodeB.NodeBcomputesitslocalcongestionpriceandaddsittothecongestionpricefromnodeC.NodeBadaptsitstransmissionratetonodeCbasedonthissumofcongestionprices.Inaddition,nodeBpassesthissumoftwopricestotheupstreamnodeA.Usingthis“pricepassing”method,thesourceofsession1receivesaggregatecongestionpricefromitsdownstreamnodesandcontrolsitstransmissionratebasedonit.Letusdenoteair(t)astheactualtransmissionrateatthei-thhopofsessionrinthehop-by-hopcontrolalgorithm.Correspondingtoeachnodeialongthepathofsessionr,is

5

cλ1A

(t)+`

1

cλ2

´

B(t)+

1

feedbackB:

`

1

c2

´

λB(t)+

1

cλ2

C(t)

feedback Afeedback Bfeedback CSource12ABC : Destinationsession 1c+

1

li(j,r)

Proposition5.1:Thetransmissionratesforthehop-by-hopcontrollerdescribedin(11)and(12)convergetotheequilib-riumvaluex∗=(x∗1,...,x∗R)T

giveninProposition4.1.In

particular,foreachrouter,andforeachhopi,ai∗

.

r(t)→xast→∞rProof:Atanyfixedtimet,notethatair(t)decreasesalongaflowpath.Thisfollowsfrom(12),wherethemin

impliesthatair(t)≤ai−1

thethesumofther(t).Further,from(11),itfollowsthatLagrangemultipliersdecreasesalongaflowpath(assmallernumberofnon-negativetermsaddedaswegetclosertothedestination).Thesetwofactsimplythat

d

VI.CONGESTIONCONTROL

WITH

DELAY

Intheprevioussectionwhereweprovedstability,weassumedthatthetimeresourcewaslargeenoughsothatqueueing󰀈didnotoccur(orequivalently,thetimethresholdtaresuitablychosen).Inthissection,wedonotmakesuchanassumption.Wewillstudythedynamicswithqueueinginthepresenceoffeedbackdelay.

Fortheend-to-endalgorithm,wedenotetheoutputtrans-missionrateofsessionratk-thhoptraversingthelinklbyxkr,l(t).Thesuperscriptkcorrespondstothefactthatlinklis

k-thhopofthepathofthesessionr.Thus,xk−1

r,l

i(j,r)

(t)andxkr,lo(j,rthe)(t)aretheincominginputandoutgoingtransmissionrateinend-to-endalgorithmrespectively.

Similarly,forthehop-by-hopalgorithm,wedenotetheactualandmaximum(virtual)sendingrateofsessionratk-th

hoptraversingthelinkl.byakr,l(t)andck

r,l(t),respectively.

Thus,akr,lk

i(j,r)(t)andar,lo(j,r)(t)aretheactualincominginputandactualoutgoingtransmissionratesofsessionratnodejrespectively.

Finally,eachnodehasaper-flowbuffertotemporarilystoredatabeforeforwarding.Wedenotethequeuelengthofsessionratnodejbyqrj(t).

6

A.TheEnd-to-EndControllerwithDelay

Unlikeinthedelay-freecaseconsideredinSectionIV,queueingcanoccuratintermediatenodesduetofeedbackdelay.Inthissection,wedescribethedetaileddynamicsofratesforasessionateachnode.

Foreachnodej,letusdefineEj

I(t)by

Ej

j,r)(t)

I(t)

=

r󰀄xk

−1

r,li(∈D(j)

clo(j,r)

TheinterpretationofEj

O(t)isthefollowing:Ifthereisnocongestionatthenodej,theoutputtransmissionsimplybeequaltotheincomingrate.Ej

rateswould

O(t)isthetimeutilizationattheMACinsuchacase.

Wenowconsiderthefollowingtwocases.

(i)EjEj

I(t)+O(t)>1

Asthetimeutilizationatthenodewillexceed’1’iftheoutputflowratesequaltheinputflowrates,wedecreasethetransmittedoutputratessuchthatthetimeconstraintismet.Inotherwords,wechooseα(t)∈(0,1]suchthatEj(t)EjrateI(t)+αbyxkO(t)=1,andsetk−1

theoutputtransmission

r,lo(j,r)(t)=α(t)x−α(t))isqueuedr,li(j,r)(t).Theremainingflow(offraction1atnodej.(ii)EI(t)+EO(t)≤1

Inthiscase,theoutputflowrateforeachsessioncanbesettoatleasttheinputrateofthecorrespondingsession.Ifsomeofthesessionshavestrictlypositivequeuelengths,i.e.,userswithbackloggedqueues(cor-respondingtocongestioninthepast),theseusersareallocatedoutputratesthataregreaterthantheirinputrates.Therateswillbeallocatedinsomefairmanner(forexample,aproportionalrateincreasetoallbackloggedusers),subjecttothetimingconstrainbeingmet.LetusdenoteQ+j(t)bethesetofbackloggedsessionsatnodejattimet.Wechooseα(t)>1suchthatthetime

utilizationatthenodeislessthanorequaltoallsessionsr∈Q+j(t),xk

t)xkone,−1andfor

r,lo(j,r)(t)=α(r,li(j,r)(t).B.TheHop-by-HopControllerwithDelay

Wenowdevelopthedynamicsofthehop-by-hopcontrollerwithdelay.AsintheSectionVI-A,wedefinethetotaltimeutilizationduetoincomingflowsatnodej,by

Hjr,li(j,r)

(t)I(t)=

r∈󰀄ak−1

D(j)

clo(j,r)

+

󰀄

min[ckk−1r,lo(j,r)(t),ar,li(j,r)(t)]

r∈D(j)

r∈/Q+j(t)

7

c+

1

I

Nc+

1

I

β(x∗(1/cI+1/cO)−wherex∗istheaveragesteady-staterateover󰀈t)

,

allflows,and

isinvariantwithN.

Wefinallycommentthatwehaveassumedthatthefeedback(marks)donotexperiencecongestion,andthatthedelayinthefeedbackissolelyduetopropagationdelays.Aswehaveper-flowqueueing,apacketimplementationtoapproximatethiscouldbethefollowing.Whencongestionoccursatanode,insteadofmarkingtheincomingpacket(implementedviasettingtheECN(ExplicitCongestionNotification)bit[26]),onecouldmarkthehead-of-line(outgoing)packetinthequeueofthecorrespondinguser.Thiswouldensurethatthequeueingdelaysareminimizedforthefeedback,andthatthesourcegetstheappropriatefeedback.Suchaschemeisfeasiblein

awirelesscontext,asper-flowqueueingisexpectedtobeimplementedforschedulingaswellasphysical)=summing(15)acrossallsessions,weobtain

N󰀂layerreasons.

Letx(t1

Nj=1wj.Byx˙(t)=κ󰀊w−β󰀍x(t−D)󰀅1c󰀇

−󰀈tO

=󰀅1󰀎+󰀌cO

󰀇κβ󰀊w1cI+

󰀅1cO

Now,denotingc󰀈=

󰀇󰀎+󰀌

(16)

c+

et

1

cI

+

1

cI

+

1

I

xO(t)

cI

+

cI+cO

q˙e(t)=xI(t)−xO(t)

=cxI(t)I

=cIcO

󰀅cI+ccI

O

󰀇

cI+cO

(ii)xI(t)≤

󰀋

(18)

cI+cO

andqe(t)=0

Inthiscase,asthebufferatthebottlenecknodeisempty,andthereisnocongestion,wehaveq˙e(t)=0.Thus,with

q󰀈˙e(t)=

q˙e(t)WenextderivecI+cO.

the“worst-case”peakqueuelengthsatthe

bottlenecknodeundertheend-to-endcontrolleraswellasahop-by-hopcontroller,duetoinitialtransients.LetQmaxe(T)bethe(unscaled)maximumqueuelengthatthebottlenecknodewithend-to-endcontrolwiththeround-tripdelayforeachsessionbeingT.Thus,thiswouldcorrespondtothetreenetworkinFigure4havingLlinkspersession,witheachlinkhavingaround-tripdelayofT/L.Alsoletqmaxe(T)=Qmaxe(T)/Nbethepeakqueuelengthforthescaledsystemdefinedby(17)and(20).Withthisdefinition,wehave

Lemma7.1:Fixanyδ>0.Then,∃(Lo,α)withα≥1andLo≥1,suchthat∀L≥Lo,LαQmaxe(δ)≤Qmaxe(Lδ).

8

TheproofispresentedinAppendixA.Usingthisresult,we

provethemainresultofthissection.LetQmaxh(T)bethe(unscaled)maximumqueuelength(duetoinitialtransients)fromwiththehop-by-hopcontrol,andqmaxh(T)bethecorrespondingscaledqueue-length,whereTistheround-tripdelayforeachsession.Wethenhave

Proposition7.1:Fixanyδ>0.Then,∃(Lo,α)withα≥1andLo≥1,suchthat∀L≥Lo,Lαqmaxh(Lδ)≤qmaxe(Lδ).

Proof:Observethatanupperboundonthequeuelengthatthebottlenecknodewiththehop-by-hopcontrolcanbederivedbyassuminganinfinitebacklogofdataatallthenodesprecedingthebottlenecknode(theLevel2nodesinFigure4).Asthecontrolloopforthishophasroundtripdelayδ,withnointermediatenodes,itfollowsthatqmaxh(Lδ)≤qmaxe(δ).Thus,fromLemma7.1,thedesiredresultfollows.

40End to EndHop by Hop353025setaR m20uS15105001002003004005006007008009001000TimeFig.5.SumRatesofbothcontrollerswithκ=1,w=0.13,and˜t

=0.415.1000End to EndHop by Hop800edoN kcenel600ttoB eht ta ht400gneL eueuQ d200eipuccO0−20001002003004005006007008009001000TimeFig.6.Occupiedqueuelengthatthebottlenecknode(D=20)

illustratestheeffectofspatialspreading.Eventhoughtheconvergencepropertiesareaboutthesame,thepeakqueuelengthatthebottlenecknodeunderthehop-by-hopschemeissmaller.

InFigure7,weincreasetheroundtripdelaytoD=40(correspondingtoaone-wayperhopdelayof4msec),thiseffectisexacerbated.Thus,theresultsinthispaperargueforconsideringhop-by-hopcontrollersforawirelessmulti-hopnetwork.

B.PacketSimulations

Inthissection,weconsiderpacketlevelsimulationsusingthens-2[27]simulator.Wehavemadesuitablemodificationsinns-2tosupporthop-by-hopaswellasend-to-endcontrollerswithaMAC.Inourimplementation,weapproximatethefluidmodelforaMACwithatime-divisionMAC.

ThenetworktopologyusedinthepacketsimulationisthesameasthatinthefluidsimulationpresentedinSectionVIII.Eachoftheinputandoutputlinksatthebottlenecknodehasabandwidthof5Mbps.Sincewesetthesizeofpackettobe1000bytes,thiscorrespondsto625pkts/sec.Thus,theequilibriumrateoveronesessionpkts/sec.Wesuitablysetwand˜atthebottleneckis62.5

t

suchthatthelinkutilizationratioisabout95%.

9

1800End to EndHop by Hop1600ed1400oN kce1200nelttoB e1000ht ta ht800gneL eu600euQ dei400puccO2000−20001002003004005006007008009001000TimeFig.7.Occupiedqueuelengthatthebottlenecknode(D=40)400)ces/st300kp( etaR gnidne200SEnd to End etHop by HopagerggA la100toT00100200300400500600Time (sec)Fig.8.Ratesofasessionofbothcontrollers,Onehopdelay=10msec400)ces/st300kp( etaR gnidne200S etagerggEnd to EndA la100Hop by HoptoT00100200300400500600Time (sec)Fig.9.Ratesofasessionofbothcontrollers,Onehopdelay=200msecFigures8and9plottheinstantaneoussumrateoffivesessionsfor10msecand200msecofone-hopdelay,respec-tively.The10mseccasecorrespondstoanefficientMAC,wherethehop-delayprimarilyoccursduetothepropagationdelayandphysicallayerairinterface.Ontheother-hand,thecasewherethehopdelayis200mseccorrespondstoa

10

400End to EndHop by HopARate300Occupied Queue Size (pkts)B200Time10000100200300Time (sec)4005006002

RateFig.10.msecOccupiedqueuelengthatthebottlenecknode.Onehopdelay=10A700End to EndHop by HopB6005004003002001000Occupied Queue Size (pkts)Time2

0100200300Time (sec)400500600APPENDIXA:PROOF

OF

LEMMA7.1

Fig.11.Occupiedqueuelengthatthebottlenecknode.Onehopdelay=200msecnetworkwithlargeper-hopdelays(possiblyduetotheMACimplementation).Inbothofthesecases(Figures8and9),weseethatthetransmissionrates(withtheend-to-endandhop-by-hopcontrollersoscillateaboutthecorrespondingfixedpoint.Asexpected,weobservethatforthelargedelaycase,theend-to-endalgorithmleadstolargeroscillationsthanthehop-by-hopalgorithm.

InFigures10and11,weplottheevolutionofthebottleneckqueuelength(measuredevery20msec).Thespatialspreadingeffectisclearlyillustratedbytheseplots,whereweseethatthepeakbuffersizewiththehop-by-hopcontrollerismuchsmallerthanthatoftheend-to-endcontroller.Thesefluidandpacketsimulationsindicatethatsignificantgainsaretobehadwiththehop-by-hopscheme,andvalidateouranalyticalresults.

IX.ACKNOWLEDGMENTS

TheauthorswouldliketothankProf.GustavodeVecianaforhiscommentsandvaluablediscussions.

Lemma7.1:Fixanyδ>0.Then,∃(Lo,α)withα≥1andLo≥1,suchthat∀L≥Lo,LαQmaxe(δ)≤Qmaxe(Lδ).

Proof:Letusdefinethefollowingtimeepochs.Lett1bethetimesuchthatx(t)crosses󰀈c,t2bethefirsttimeaftert1suchthatx(t)crossesc,t3=t1+δ,t4=t2+δ,t5=t3+δ,andt6bethefirsttimeaftert4suchthatx(t)crossesc.ThesetimesareillustratedinFigure12andFigure13.Formally,wecandefinethesetimeepochsby

t1=inf{t>0:x(t)>󰀈c}t2=inf{t>t1:x(t)>c}t3=t1+δt4=t2+δ

t5=t3+δ

t6=inf{t>t4:x(t)Wenotethatdependingonκ󰀈δ,t6canbegreater(Figure12)orless(Figure13)thant5.AlsodenotethecorrespondingvaluesofthetrajectoriesbyRA=x(t4)andRB=x(t3).

Nowobservethatthepeakqueuelengthatthebottlenecknodeisgivenby

󰀆t6

qmaxe(δ)=x(t)dt(21)

t2

Weassumethattheinitialconditionsatisfiesx(s)≤󰀈c,∀s≤0.First,wenotethatforfixedκ󰀈suchthatδκ󰀈<1,wehaveqmaxe(δ)Bytheassumptionabouttheinitialcondition,over[t1,t3],wehave

x˙(t)=κ󰀈w󰀈(22)Usingthefactthatc−󰀈c=κ󰀈w󰀈(t2−t1),wehave

tc−󰀈c

2−t1=

(23)

Inaddition,

t−tκ󰀈

1

43=t2−t1=

2

)+dκ󰀈w󰀈+c󰀈(27)

Bydefinition,wehavey(δ)=x(t5).Wenowderivetheconditiononδκ󰀈suchthaty(δ)=to¯c.Thiswillcorrespondt

6=t5.=c⇔κ󰀈(wt󰀈−

κ󰀈wt2

y(δ)2

)+δκ󰀈w󰀈−w󰀈=0

⇔(κ󰀈δ)2−4κ󰀈δ+2=0

(28)

5Thus,

itispossiblethatx¯(t)tobetemporarilybufferedatnodesprecedingthebottlenecknode,seeCase(i)inSectionVI-A.

11

Solving,wegetκ󰀈δ=2+

√

2,thisconditionensuresthatthetrajectoryofx(t),

andthusx¯(t),isoftheformshowninFigure13.

Further,fromthemonotonicitypropertyofthequeuelengthwithrespecttodelay,forfixedκ󰀈,andanyδsuchthatκ󰀈δ2+

ò22(correspondingto

Figure13).

Thepeakqueue-lengthcomputationdiffersdependingontherelativepositionofcIwithRAandRB.WefirstconsiderthecasewherecI>RA(seeFigure13).

LetusdenotetheareaoftheregionS1(overthetimeinterval[t2,t3])inFigure13byA(S1).Then,

A(S1)=

1

2κ󰀈

(δκ󰀈−1)2(29)

Bydefinition,wehave

A(S2)=󰀆

s

y(t)dt,

(30)

0

wheres√ischosensuchthaty(s)=c.From(27),wehave

s=1+

κe

.Thus,A(S2)=󰀆wehaves

(y(t)−c)dt

0=

−󰀍

󰀅

1+√6+

󰀅κ󰀈2

1+√+

󰀅1+

√2κ󰀈

κ󰀈

(31)Thus,fromtheequations(29)and(31),whenwehavecI>RB,thepeakqueuelengthisgivenby

A(S1)+A(S2)=

w󰀈

−1+2δκ󰀈−1+2δκ󰀈󰀇3󰀎

−1+2δκ󰀈󰀇(δκ󰀈wκ󰀈󰀈w󰀈

−w󰀈)

󰀇2

w󰀈

Next,definefort∈[0,∆t],

y¯1(t)=x¯(κ󰀈tw+󰀈

t4)

andfort∈[0,δ−∆t],define

y¯2(t)

=x¯(t+t4+∆t)

Thus,wehave

y¯1(t−δ)=κ󰀈wt󰀈+cy¯2(t−δ)=cI

(33)

Thus,fort∈[0,∆t],wehave

y¯˙1(t)=κ󰀈(w󰀈−(κ󰀈wt󰀈+c)p(κ󰀈wt󰀈+c))

=−κ󰀈2Similarly,fort∈[0,δ−wt∆󰀈

t],wehave

y¯˙(34)2(t)=κ󰀈(w󰀈−cIp(cI))

=−κ󰀈(cI−c)

(35)

Also,bydefinition,wehave

y¯1(0)=cIy¯2(0)=y¯1(∆t)

(36)

Thus,integrating,wehave

y¯t2

1(t)=−κ󰀈2

w󰀈

2w󰀈

(cI−c)2+cI

(37)

Inaddition,defining¯ttobethefirsttimesuchthaty¯2(¯t)=c,¯t

=12w󰀈

)(38)

Thus,thepeakqueuelengthatthebottlenecknodewhencI1

2

(2δ−∆t)(cI−c)+M,

(39)

whereM=󰀃∆t0y¯1(t)dt+Finally,weneedtoperform󰀃t¯

0y¯2(t)dtisindependentofδ.asimilarcomputationwhenRB√ourproof,chooseLlargeenoughsuchthatLκ󰀈δ>2REFERENCES

[1]F.P.Kelly,“Modelsforaself-managedInternet,”Philosophical

TransactionsoftheRoyalSociety,vol.A358,pp.2335–2348,2000.[2]S.KunniyurandR.Srikant,“End-to-endcongestioncontrol:utility

functions,randomlossesandECNmarks,”inProceedingsofIEEEInfocom,TelAviv,Israel,March2000,vol.3,pp.1323–1332.

[3]F.Paganini,J.Doyle,andS.Low,“Scalablelawsforstablenetwork

congestioncontrol,”inProceedingsoftheIEEEConferenceonDecisionandControl,December2001,vol.1,pp.185–190.

[4]G.HollandandN.H.Vaidya,“AnalysisofTCPperformanceover

mobileadhocnetworks,”inProceedingsofIEEE/ACMMobicom,August1999,pp.219–230.

[5]P.Bender,P.Black,M.Grob,R.Padovani,NSindhushayana,and

A.Viterbi,“CDMA/HDR:Abandwidthefficienthighspeedwirelessdataservicefornomadicusers,”IEEECommunicationsMagazine,pp.70–77,July2000.[6]“IEEE802.11bstandards,”Availablefordownloadat

http://grouper.ieee.org/groups/802/11/main.html.

[7]H.T.KungandA.Chapman,“TheFCVC(flowcontrolledvirtual

channel)proposalforatmnetworks,”inProceedingsofICNP,October1993.

12

[8]P.P.MishraandH.Kanakia,“Ahopbyhopratebasedcongestion

controlscheme,”inProceedingsofACMSigcomm,August1992.[9]H.T.Kung,T.Blackwell,andA.Chapman,“Credit-basedflowcontrol

foratmnetworks:Creditupdateprotocol,adaptivecreditallocationandstatisticalmultiplexing,”inProceedingofACMSigcomm,1994,pp.101–114.

[10]L.Tassiulas,“Adaptiveback-pressurecongestioncontrolbasedonlocal

information,”IEEETransactionsonAutomaticControl,vol.40,no.2,pp.236–250,February1995.

[11]S.SarkarandL.Tassiulas,“Backpressurebasedmulticastscheduling

forfairbandwidthallocation,”inProceedingsofIEEEInfocom,2001,pp.1123–1132.

[12]F.P.Kelly,A.Maulloo,andD.Tan,“Ratecontrolincommunication

networks:shadowprices,proportionalfairnessandstability,”JournaloftheOperationalResearchSociety,vol.49,pp.237–252,1998.

[13]G.Vinnicombe,“Onthestabilityofend-to-endcongestioncontrolfor

theInternet,”2001,UniversityofCambridgeTechnicalReport.

[14]L.Massoulie,“Stabilityofdistributedcongestioncontrolwithhet-erogenousfeedbackdelays,”TechnicalReport,MicrosoftResearch,Cambridge,UK,2000.

[15]S.Shakkottai,R.Srikant,andS.Meyn,“Boundsonthethroughputof

congestioncontrollersinthepresenceoffeedbackdelay,”IEEE/ACMTransactionsonNetworking,vol.11,no.6,pp.972–981,December2003.

[16]R.JohariandD.Tan,“End-to-endcongestioncontrolfortheInternet:

Delaysandstability,”IEEE/ACMTransactionsonNetworking,vol.9,no.6,pp.818–832,December2001.

[17]C.M.Ozveren,R.J.Simcoe,andG.Varghese,“Reliableandefficient

hop-by-hopflowcontrol,”IEEEJournalonSelectedAreasinCommu-nications,vol.13,no.4,pp.2–650,1995.

[18]L.TassiulasandS.Sarkar,“Maxminfairschedulinginwireless

networks,”inProceedingsofIEEEInfocom,NewYork,NY,June2002,pp.763–772.

[19]T.S.Rappaport,WirelessCommunications:PrinciplesandPractice,

PrenticeHall,UpperSaddleRiver,NJ,2002.

[20]B.HajekandG.Sasaki,“Linkschedulinginpolynomialtime,”IEEE

TransactionsonInformationTheory,vol.34,no.5,1988.

[21]J.MoandJ.Walrand,“Fairend-to-endwindow-basedcongestion

control,”IEEE/ACMTransactionsonNetworking,vol.8,no.5,pp.556–567,2000.

[22]S.KunniyurandR.Srikant,“Atime-scaledecompositionapproachto

adaptiveECNmarking,”IEEETransactionsonAutomaticControl,vol.47,no.6,pp.882–4,June2002.

[23]S.KunniyurandR.Srikant,“Analysisanddesignofanadaptivevirtual

queuealgorithmforactivequeuemanagement,”inProceedingsofACMSigcomm,SanDiego,CA,August2001,pp.123–134.

[24]Y.YiandS.Shakkottai,“Hop-by-hopcongestioncontrolovera

wirelessmulti-hopnetwork,”TechnicalReport,WirelessNetworkingandCommunicationsGroup,DepartmentofElectricalandComputerEngineering,TheUniversityofTexasatAustin,2003.

[25]S.ShakkottaiandR.Srikant,“Howgoodaredeterministicfluidmodels

ofInternetcongestioncontrol?,”inProceedingsofIEEEInfocom,NewYork,NY,June2002,vol.2,pp.497–505.

[26]S.FloydandV.Jacobson,“Randomearlydetectiongatewaysfor

congestionavoidance,”IEEE/ACMTransactionsonNetworking,vol.1,no.4,pp.397–413,August1993.

[27]UCB/LBNL/ISI,NetworkSimulator-ns(version2).Availableat

http://www.isi.edu/nsnam/ns