Processor-Ring Communication A Tight Asymptotic Bo

DIMACSTechnicalReport96-36August1996Processor-RingCommunication:ATightAsymptoticBoundonPacketWaitingTimesbyE.G.Coman,Jr.BellLaboratoriesLucentTechnologiesMurrayHill,NJ07974NabilKahaleAT&TResearchLaboratoriesMurrayHill,NJ07974F.T.LeightonDept.ofMath.andLaboratoryforComputerScienceMITCambridge,MA02139DIMACSisapartnershipofRutgersUniversity,PrincetonUniversity,AT&TRe-search,Bellcore,andBellLaboratories.DIMACSisanNSFScienceandTechnologyCenter,fundedundercontractSTC{91{19999;andalsoreceivessupportfromtheNewJerseyCommissiononScienceandTechnology.AbstractWeconsiderNprocessorscommunicatingunidirectionallyoveraclosedtransmissionchannel,orring.Eachmessageisassembledintoaxed-lengthpacket.Packetstobesentaregeneratedatrandomtimesbytheprocessors,andthetransittimesspentbypacketsontheringarealsorandom.Packetsbeingforwarded,i.e.,packetsalreadyonthering,havepriorityoverwaitingpackets.Theobjectiveofthispaperistoanalyzepacketwaitingtimesunderagreedypolicy,withinadiscreteMarkovmodelthatretainstheover-allstruc-tureofapracticalsystem,butissimpleenoughsothatexplicitresultscanbeproved.Independent,identicalBernoulliprocessesmodelmessagegenera-tionattheprocessors,andi.i.d.geometricrandomvariablesmodelthetransittimes.Ouremphasisisonasymptoticbehaviorforlargeringsizes,N,whentherespectiverateparametershavethescaling=Nand=N.Ourmainresultshowsthat,ifthetracintensityisxedat==1,thenasN!1theexpectedtimeamessagewaitstobeputontheringisboundedbyaconstant.Thisresultveriesthattheexpectedwaitingtimeunderthegreedypolicyiswithinaconstantfactorofthatunderanoptimalpolicy.11.IntroductionCommunicationamongNprocessorstakesplacecounterclockwisealongaslot-tedcirculartransmissionchannel,orring.Aprocessorgeneratesmessages,receivesmessages,andforwardsmessagesbetweenotherprocessors.Eachmessageisapacketofxedduration.Onetimeunitisrequiredforapackettobesentorforwardedfromoneprocessortoitscounterclockwiseneighbor.Packetsaregeneratedrandomlyattheprocessorsaccordingtoi.i.d.arrivalprocesses.Theintegertimesspentbypacketsonthering,packettransittimes,arei.i.d.randomvariables.Packetsbeingforwardedontheringhavepriority;whileaprocessorhasapackettobeforwarded,itcannotplaceoneofitsownwaitingpacketsonthering.Apacketwaitingfortransmissionisheldinaqueueattheprocessorwhereitwasgenerated.Thedetailsdeningapracticalimplementationofaprocessorringaremanyandvaried.Indeed,theapplicationsandanalysisofcommunicationringsformaratherlargeandgrowingliterature;seevanAremandvanDoorn(1990),BarrosoandDubois(1993),andGeorgiadis,Szpankowski,andTassiulas(1993)forbriefsurveysandmanyreferences.Asaconcessiontomathematicaltractability,weadoptherethesimplediscreteMarkovmodelinFig.1,wheretheringispartitionedintocells,eachcapableofholdingasinglepacket.Thecellsrotatecounterclockwisepasttheprocessorsindiscretesteps,onestepperunitoftime.PacketsaregeneratedateachoftheNprocessorsbyaBernoulliprocessatrate=N0N,pertimeunit(step);thetotalarrivalrateisthen.Thepackettransittimesaregeometricallydistributedwithrateparameter=N,N.Thus,atanygivenstep,apacketontheringdepartswithprobability=Nandstaysforatleastonemorestepwithprobability1=N,independentofhowlongthepackethasalreadybeenonthering.Wewillexplainshortlythereasonforthescalingofarrivalandtransit-timeparametersbytheringsize.Ineachstep,theringsystemundergoesatransitionaccordingtothefollowingsequence:(i)Theringrotatesonepositionwhileprocessorqueuesacceptnewarrivals,ifany(atmostoneperqueueineachstep).(ii)Packetsontheringthathavecompletedtheirtransittimesaredelivered,i.e.,removedfromtheircells.(iii)Eachprocessorwithanonemptyqueueoppositeanemptycellthenputsawaitingpacketintothiscell.Thisgivesthenonblockingmodel;reversing(ii)and(iii)wouldgivetheblockingmodel:adepartingpacketcannotbereplacedinthesametimestepbyawaitingpacket.Asweshallsee,ourasymptoticresultsapplytobothmodels.Theabovesequencegivesthegreedycelladmissionpolicy,placingwaitingpacketsontheringassoonasemptycellsareavailable.2i12NFigure1:Therotatingringmodel.3AsdiscussedinComanetal.(1993),thegreedypolicyhastheundesirableeectofoccasionally\freezingoutcertainprocessorqueuesforlongperiodsoftime;longtrainsofoccupiedcellspassbysuchprocessorsdenyingthemaccesstothering.Theresultsofthispaperwillshowthat,forlargeringswithinourprobabilitymodel,thegreedyruleisremarkablyecient,andthatinfacttheabovebehaviorisquiterare.Ourspecicobjectiveistoanalyzepacketwaitingtimesunderthegreedypolicy.(Hereafter,unlessnotedotherwise,waitingtimesalwaysrefertotimesspentwaitinginprocessorqueues.)Toprepareforthestatementofourmaintheoremonwaitingtimes,weneedalittlemorenotation.Foragivenadmissionpolicy,wedenotethejointqueuelengthatintegertimetbyQ(t)=(Q1(t);:::;QN(t)),whereQi(t)isthenumberintheithprocessorqueueattimet.Thephrase‘attimet’meansataninstantjustaftertsothatevents,ifany,occurringatthavealreadytakenplace.DenetheN-bitvectorR(t)whoseithbitis1ifandonlyifapacketisintheithcellattimet.Hereafter,thetermstatereferstoapairQ(t);R(t)atsometimet.Itfollowsfromthegeometriclawfortransittimesthattheringprocessf(Q(t);R(t));t=0;1;: