Time-average and asymptotically optimal flow control policies in networks with multiple transmitters

 Klimawandel

 3 views
of 30
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
We considerM transmitting stations sending packets to a single receiver over a slotted time-multiplexed link. For each phase consisting ofT consecutive slots, the receiver dynamically allocates these slots among theM transmitters. Our objective is to
Share
Transcript
  Time-AverageandAsymptoticallyOptimal FlowControlPoliciesinNetworks withMultipleTransmitters  RedhaM.Bournas,FrederickJ.Beutler andDemosthenisTeneketzis DepartmentofElectricalEngineeringandComputerScience TheUniversityofMichigan AnnArbor,Michigan48109 September10,1991   Abstract Weconsider M  transmittingstationssendingpacketstoasinglereceiveroveraslottedtime-multiplexedlink.Foreachphaseconsistingof T  consecutiveslots,thereceiverdynamicallyallocatestheseslotsamongthe  M  transmitters.Ourobjectiveistocharacterizepoliciesthatminimizethelong-termaverageofthe totalnumberofmessagesawaitingserviceatthe  M  transmitters.Weestablishnecessaryandsucientconditionsonthearrivalprocessesatthe transmittersfortheexistenceofnitecosttime-averagepolicies;itisnotenough thattheaveragearrivalrateisstrictlylessthantheslotcapacity.Weconstructa purestrategythatattainsaniteaveragecostundertheseconditions.Thisinturn leadstotheexistenceofanoptimaltime-averagepurepolicyforeachphaselength  T  ,andtoupperandlowerboundsonthecostthispolicyachieves.Furthermore,we showthatsuchanoptimaltime-averagepolicyhasthesamepropertiesasthose ofoptimaldiscountedpoliciesinvestigatedbytheauthorsinapreviouspaper.Finally,weprovethatintheabsenceofcostsaccruedbymessageswithinthe phase,thereexistsapolicysuchthatthetime-averagecosttendstowardzeroasthephaselength  T  !1  . Keywords: COMMUNICATIONNETWORKS;STABILITY;RANDOM WALKS; G=G=  1QUEUES;TIME-AVERAGEOPTIMALITY;ASYMPTOTIC OPTIMALITY.  1.Introduction  Weconsideraowcontrolproblemthatarisesintheperformancemodelling ofthe`hop-by-hop'layerofcomputercommunicationnetworks.Foradetailed overviewonthearchitecturallayersandowcontrolmechanisms,thereaderisreferredto7,8,17].Thehop-by-hopschemestudiedinthispaperisthesame astheonein2,3,4,5],itspurposebeingtomaintainasmoothowoftrac between  M  transmittingstationsattemptingtosendmessagesthroughasingle communicationchanneltoanadjacentreceivingstation.Thetimeaxisisdivided intoequalsegmentscalledslots.Allmessagesconsistofpacketsofequallength;the transmissiontimeofapacketisoneslotandapackettransmissionmayonlybegin onaslotboundary.Eachtransmitter j hasanindependentgenerallydistributed arrivalprocessofpacketsperslotwithniterstmoment   ( j ) andabuerofinnitesize.Weassumethatthearrivalprocessestodistincttransmittersaremu-tuallyindependent.Onlyonestationisallowedtotransmitduringanyparticularslot. T  consecutiveslotsforma  phase  .Priortothebeginningofeachphase,there-ceiverinformseachtransmitterofthenumberofpackets(referredtoasa  window  size)thatitispreparedtoacceptandtheparticularslotsduringwhicheachtrans-mitterisallowedtotransmit.Inmakingadecisionontheassignedwindowsize,thereceiverusestheknowledgeofarrivalstatistics,thenumberofqueuedpacketsforeachtransmitteratthebeginningoftheprecedingphase,andthewindowsize assignedfortheprecedingphase.Thenumberofqueuedpacketsataphaseissentbyeachtransmittertothereceiverwithnegligibleoverheadsometimebefore thebeginningofthenextphase.Duetothearrivalofnewpackets,thenumberofqueuedpacketschangesbythetimethereceiverisabletousetheinformation forthenextwindowassignment.Thewindowallocationsbythereceiverthusconstituteadiscrete-timeMarkovdecisionprocesswithpartialinformation.OptimalowcontrolallocationswererstanalyzedbyRosbergandGopal16],whoconsideredasingletransmitter,andacostfunctionreectingthenumberofqueuedpacketstogetherwiththenumberofunutilized(i.e.,wasted)transmission slots.Subsequently,CanseverandMilito3]investigatedtheproblemfortwo transmitters( M  =2)withidenticalarrivalstatistics,withlatergeneralizationsto heterogeneousarrivals4].CanseverandMilitoalsoconjecturedresultsfor M>  2 transmitters.Later,theyextendedtheirworktomorecomplexnetworkswith multiplestatesinalayered,tree-likenetwork5].Ourmodelin2]issimilartothatof3,4].Asinthesereferences,thecostperphasein2]istheexpectationofthesumofthenumberofuntransmitted packetsattherespectivestations.Ourobjectivethenwastodynamicallyallocate axednumber T  ofslotsamongthe  M    2transmitterstominimizethetotaldiscountedcost.Ourresultsin2]includeapartialcharacterizationofasetof1   optimalallocationpolicies.Thesestructuralpropertiesenableustoprovethat,forthesetofalldiscountfactors <  1,anitenumberofdynamicoptimalallocationssucetocompletedescribeanoptimalallocationpolicy.For M  =2,weproveinadditionthattheoptimalpolicyisamonotonefunctionofastate,andthatthetotalcostisconvex.Whentheprocessofmessagegenerationatone transmitterisstochasticlargerthanthemessagegenerationprocessattheothertransmitter,wefurthercharacterizeanoptimalallocation.Finally,ifthemessage generatingprocessesatthe  M    2transmittersareiid,wendanexplicitformoftheoptimalallocationpolicy(compare3])thatdoesnotdependonthediscountfactor   .Here,weturnourattentiontotime-averagepolicies.Webelievethatatime-averagecostcriterionisamorenaturalsettingforowcontrolproblems,since itrepresentsthelong-termperformancemeasureoftheowcontrolalgorithm.Moreover,inthetimescaleunderwhichaowcontrolsystemgenerallyoperates,anydiscountattachedtopastdataoughttobeminimal;hence,discountingappearstoustobeanarticethatfacilitatessolutions,atthecostofdetractingfromthe validityofthemodel.Itisnotsurprisingthattheexistenceoftime-averagepoliciesofnitecostrequiresthattheaveragearrivalrateisstrictlylessthantheslotcapacity,i.e, <  1intermsofatracintensity.Weshowthatmoreisrequired:if <  1,a necessaryandsucientconditionfortheexistenceofnitecoststrategiesisthe nitenessofthesecondmomentofthenumberofarrivalsduringaphase.Weexhibitapurestrategythatattainsaniteaveragecostunderthecondition oftheprecedingparagraph.Thisinturnleadstofourfurtherresults:1.Foreachphaselength  T  ,thereexistsanoptimaltime-averagepolicy.2.Thetime-averageoptimalpolicycanbeobtainedasalimitofinnitehorizon optimaldiscountedpoliciesasthediscountingfactor   !  1.3.Thepropertiesofthetime-averageoptimalpolicyarethesameasthose derivedin2]foroptimaldiscountedpolicies.4.Upperandlowerperformanceboundsareobtainedforthecostattainedby theoptimalpolicy.Foreachphaselength  T  ,theexistenceoftime-averageoptimalpoliciesandthe derivationoftheirstructuralpropertiesarebasedon:(1)theworkofBournasetal.2]ontheinnitehorizonoptimaldiscountedcostandstructuralpropertiesoftheoptimaldiscountedstationarypolicies,and(2)theworkofSennott18].Finally,weprovethatintheabsenceofcostsaccruedbymessageswithinthe phase,thereexistsapolicysuchthatthetime-averagecosttendstowardzeroas2   thephaselength  T  !1  .Thisresultismotivatedbyourinterestininvestigating thelong-termaveragecostasafunctionofthephaselength  T  ,whichinturnleadstoanoptimalphaselengthsize.Thisproblemturnsouttobeaverydicultoneandwehavenotsolveditinthispaper.However,wehavebeenabletosolve acloselyrelatedproblemasweshallexplain.Foreachphase,thecosthastwo additivecomponents:(1)thenumberofpacketsawaitingtransmissionatthebe-ginningofthephase,and(2)thewaitingtimesaccumulatedbypacketsarriving duringthephase,andnotbeingavailablefortransmissionuntilthebeginningofthenextphase.Usingthestronglawoflargenumbersandthetheoryofconver-genceofprobabilitymeasuresasinBillingsley1],wehavebeenabletoshowthatthecostcomponent(1)asymptoticallygoestozeroas T  !1  .Inaddition,the correspondingasymptoticallyoptimalpoliciesarestateindependentandpropor-tionaltothearrivalprocessesrates.Theasymptoticbehaviourofcomponent(1)as T  !1  combinedwiththemonotonicityin  T  ofthecostcomponent(2)shed morelightintotheissuesthatshouldbeaddressedtodeterminetheoptimalphase length.SomeoftheseissuesarediscussedinSection5.Thepaperisorganizedasfollows.InSection2,weformalizethemodeland formulatetheproblem.InSection3,werstderivenecessaryconditionsonthe statisticsofthearrivalsprocessesthatensuresystemstablebehaviour.Undertheseconditions,wethenconstructapurestrategypossessedofnitelong-term averagecost.InSection4,wedemonstratetheexistenceofoptimaltime-average stationarypolicies,andshowthatthesepolicieshavethesamepropertiesasthose derivedin2]foroptimaldiscountedstationarystrategies.InSection5,weexhibittheexistenceofastationarynonrandomizedpolicyunderwhichthelong-term averagenumberofpacketsawaitingtransmissionatthebeginningofeachphase convergestozeroas T  !1  .Theowcontrolproblemwithprioritiesisbriey discussedinSection6.Finally,conclusionsarepresentedinSection7. 2.ModelFormulation  2.1DenitionsandProblemStatement Considerahop-by-hopschemethatoperatesasfollows.Thereare  M  transmit-tingnodesattemptingtosendmessagestoasinglereceiver.Allmessagesconsistofpacketsofxedlengthandtimeisdividedintoequalslots,oneslotbeinglong enoughtotransmitapacket.Apackettransmissionmaybeginonlyonaslotboundary.Thewindowallocationproceedsinphases,a  phase  beingaxedprede-terminednumberofslots,say  T  slots.Onlyonetransmitterisallowedtotransmitduringaparticularslot.Wealsoassumethateachtransmitterhasabuerofinnitesize.Weplacetwofurtherrestrictionsonthemodel:(1)packetsarriving inaparticularphasemaynotbetransmittedinthatphase,and(2)packetsthat3 
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks