Citation
Communication algorithms for adversarial multiple access channels

Material Information

Title:
Communication algorithms for adversarial multiple access channels
Creator:
Anantharamu, Lakshmi
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
1 electronic file. : ;

Subjects

Subjects / Keywords:
Digital audio broadcasting ( lcsh )
Contention resolution protocols (Computer network protocols) ( lcsh )
Contention resolution protocols (Computer network protocols) ( fast )
Digital audio broadcasting ( fast )
Genre:
non-fiction ( marcgt )

Notes

Review:
We investigate dynamic broadcasting in multiple access channels. Packet injection and jamming are constrained by adversarial models, which determine injection rates and burstiness of traffic. We develop a number of deterministic distributed broadcast protocols and study their efficiency. The performance of protocols is measured by packet latency and queue size, as functions of the parameters of the underlying adversarial models. We derive worst-case upper and lower bounds on packet latency and queue size, and show impossibility results, all with respect to classes of broadcast protocols and adversaries. We develop a simulation environment for dynamic broadcasting on multiple access channels. We report results of experiments in which the mutual performance of protocols have been compared. The experiments involve both the classical back-off protocols and the protocols we have proposed.
Thesis:
Thesis (Ph.D.)--University of Colorado Denver. Computer science and information systems
Bibliography:
Includes bibliographic references.
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Lakshmi Anantharamu.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
862979280 ( OCLC )
ocn862979280

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

COMMUNICATIONALGORITHMSFORADVERSARIALMULTIPLEACCESS CHANNELS by LakshmiAnantharamu B.E.,UniversityofMysore,India,1994 M.S.,UniversityofColorado,2007 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof DoctorofPhilosophy ComputerScienceandInformationSystems 2013

PAGE 2

ThisthesisfortheDoctorofPhilosophydegreeby LakshmiAnantharamu hasbeenapprovedforthe ComputerScienceandInformationSystemsProgram by GitaAlaghband,Chair BogdanS.Chlebus,Advisor EllenGethner IlkyuenRa StevenWalczak April11,2013 ii

PAGE 3

Anantharamu,LakshmiPh.D.,ComputerScienceandInformationSystems CommunicationAlgorithmsforAdversarialMultipleAccessChannels ThesisdirectedbyAssociateProfessorBogdanS.Chlebus ABSTRACT Weinvestigatedynamicbroadcastinginmultipleaccesschannels.Packetinjection andjammingareconstrainedbyadversarialmodels,whichdetermineinjectionratesand burstinessoftrafc.Wedevelopanumberofdeterministicdistributedbroadcastprotocols andstudytheirefciency.Theperformanceofprotocolsismeasuredbypacketlatency andqueuesize,asfunctionsoftheparametersoftheunderlyingadversarialmodels.We deriveworst-caseupperandlowerboundsonpacketlatencyandqueuesize,andshow impossibilityresults,allwithrespecttoclassesofbroadcastprotocolsandadversaries.We developasimulationenvironmentfordynamicbroadcastingonmultipleaccesschannels. Wereportresultsofexperimentsinwhichthemutualperformanceofprotocolshavebeen compared.Theexperimentsinvolveboththeclassicalback-offprotocolsandtheprotocols wehaveproposed. Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:BogdanS.Chlebus iii

PAGE 4

DEDICATION Thisworkisdedicatedtomyfamily,Sahil,RahulandPrakashforalltheirloveand support. iv

PAGE 5

ACKNOWLEDGMENT IcannotthankmyadvisorBogdanenoughforgivingmeanopportunitytoworkwith him.Bogdanhasbeentheworstcriticofmyworkandthegreatestinspirationtodobetter always.Iamevergratefulforthat.Thiswouldnothavebeenpossiblewithouthissupport ofmethroughNSFgrant.IalsowanttothankDarekKowalskiandMariuszRokickifor collaborationonseveralresearchprojects.Iwanttothankthechairofourdepartment,Gita AlaghbandforallthesupportovertheyearsandEllenGethnerforbeinganinspirationto womenintheory. Iwanttothankmyfamilywhosupportedmeandlovedmethesamethroughthe years.IwanttothankmyhusbandPrakashfortakingonsomuchmoreofourfamily responsibilities,toleratingmylonghoursofworkandsupportingmethroughout.Icould nothavedonethiswithouthim.IalsowanttothankmykidsRahulandSahilforbeing sopatientandloving.Lastbutnotleast,Iwanttothankmymotherwhoisthegreatest inspirationofmylife,forallofhersupportandhelpovertheyearswhileIworkedonthis. v

PAGE 6

CONTENTS Figures.........................................viii Chapter 1.Introduction....................................1 2.Mainresults....................................4 3.Relatedwork...................................7 4.Technicalpreliminaries..............................15 5.Channelswithjamming..............................19 5.1Preliminaries..................................19 5.1.1Packetlatencyoffullsensingprotocols...................25 5.1.2Packetlatencyofadaptiveprotocols.....................29 5.2Conclusion...................................37 6.Channelswithoutjamming............................39 6.1Fullsensingprotocols..............................39 6.1.1Fullsensingprotocolswithcollisiondetection................40 6.1.2Adaptiveprotocol...............................44 6.2Conclusion...................................44 7.Individualinjectionrates.............................45 7.1Results......................................46 7.2Preliminaries..................................47 7.3Impossibilitiesandlowerbounds........................50 7.3.1Impossibilityresultsforacknowledgmentbasedprotocols.........50 7.3.2Lowerbounds.................................54 7.4Twoprotocolsofsmalllatency.........................55 7.4.1Afullsensingprotocolwithcollisiondetection...............56 7.4.2Anadaptiveprotocolwithoutcollisiondetection..............59 7.5Afullsensingprotocolwithoutcollisiondetection...............60 vi

PAGE 7

7.6Conclusion...................................66 8.Experiments....................................68 8.1Simulationswithoutjamming..........................68 8.1.1Machineryofpacketinjection:........................69 8.2Simulationswithjamming...........................73 8.3Conclusion...................................76 9.Adhocmultipleaccesschannels..........................78 9.1Technicalpreliminaries.............................82 9.2Limitationsonbroadcasting..........................86 9.3Activationbasedprotocols...........................93 9.3.1Anon-adaptiveprotocol...........................93 9.3.2Anadaptivealgorithm............................98 9.4Fullsensingprotocols..............................103 9.4.1Anon-adaptivealgorithm...........................104 9.4.2Anadaptivealgorithm............................109 9.5Conclusion...................................114 10.Openproblemsandfuturework..........................115 References .......................................116 vii

PAGE 8

FIGURES Figure 8.1Comparisonofmaximumpacketlatencyofdeterministicandbackoffprotocolsforvaryinginjectionrates.........................68 8.2Comparisonofmaximumpacketlatencyofdeterministicprotocolsforvaryinginjectionrates................................69 8.3Comparisonofmaximumpacketlatencyofregularandold-rstdeterministic protocolsforvaryinginjectionrates......................71 8.4Comparisonofmaximumpacketlatencyofdeterministicandbackoffprotocolsforvaryingnumberofstations.......................72 8.5Comparisonofmaximumpacketlatencyofdeterministicandbackoffprotocolsforvaryinginjectionandjammingrates..................75 8.6Comparisonofmaximumpacketlatencyofdeterministicprotocolsforvaryinginjectionandjammingrates........................76 9.1Algorithmcounting-backoff..........................94 9.2Algorithmqueue-backoff............................99 9.3Algorithmtripled-rounds............................105 9.4Algorithmpaired-rounds............................111 viii

PAGE 9

1.Introduction Westudydynamicbroadcastingonmultipleaccesschannels.Multipleaccesschannelsareamodelofmediumaccesscontrolinsomeimplementationsoflocalareanetworks.SuchimplementationsincludewiredEthernet,asrepresentedbytheIEEE802.3 collectionofstandards,andwirelessnetworksintherestrictedcasewhentheavailable bandallowstousejustoneradiofrequency.Abstractingmediumaccesscontrolasmultipleaccesschannelallowstostudyoptimalityofcommunicationprotocolsinaclearly denedcommunicationenvironment,withoutconstraintsoftheeverevolvingtechnologiesandIEEEstandards.Thegoalsofthisworkincludedemonstratingthatdeterministic distributedprotocolshaveuntappedpotential,especiallyforheavybroadcastloads.We evaluatetheperformanceofprotocolsintermsoftheworst-casequeuesizesandpacket latency. Thetraditionalapproachtodynamicbroadcastingonmultipleaccesschannelsuses randomizationtoarbitrateforaccesstothechannelinadistributedmanner.Typicalexamplesofrandomizedprotocolsincludebackoffprotocols,likethebinaryexponential backoffemployedintheEthernet.Ithasbeengenerallyconsideredinevitabletohaveto resorttorandomizationtobeabletocopewithburstytrafconsuchchannels:theunderlyingjusticationisthatinreal-worldapplicationsmoststationsstayidleformostofthe timesothatperiodsofinactivityareinterspersedwithunexpectedburstsofactivitybyunpredictablecongurationsofstations.Thisperceptioncontributedtoingraintheprevalent opinionthatdeterministicsolutionshavelittlepotential. Onecouldtrytosurmisethereasonswhythetraditionalapproachtobroadcasting viarandomizationhasbeenconsideredasessentiallytheonlyviableone.Anenormous successoftheEthernetasareal-worldimplementationoflocalareanetworkshascontributedsignicantlytothisattitude.Themethodologicalunderpinningsofthekeyperformancemetricslikestabilityandlatencyhavebeennormallystudiedwithstochastic assumptionsinmind.Thisespeciallyregardsstabilityunderstoodasergodicityofthe associatedMarkovchains.Themethodologyofsimulationsappearstohavebeenbiased 1

PAGE 10

towardsmodelsofdatainjectiondenedbysimplestochasticconstraints.Yetanotherreasonhasbeentheperceptionofanapparentlackofalternativesinboththeoreticalmodeling andsimulations.ThesuccessoftheEthernethashadnegativeconsequencesonthedevelopmentandexplorationofalternativesolutions,assuccessoftenbreedsinertiasothatone doesnotwanttochangeasolutionthatappearstowork.TheexponentialbackoffembeddedintheEthernethastwoproperties:itisarandomizedacknowledgmentbasedprotocol ofbackofftypeanditisanexponentialbackoff.Itappearsthattheformerpropertyis essentiallyresponsibleforthesuccessofEthernet,asHstad etal. [42]demonstratedthat thepolynomialquadraticbackoffoutperformstheexponentialone. Wearemotivatedtoconsiderdeterministicalgorithmsforanumberofreasons.The basicphilosophicalquestionof'whynotdeterminism?'isintriguing.Wewanttotakethis workbeyondtheIEEEstandards.Wewanttostudythetheoreticalunderpinningsinadeterministicframework.Consideringthisasaprobleminscience,ratherthanengineering, wewanttoasktheveryfundamentalquestionsofscience,like'whatisandwhatisnot possible?'. Therearevariousapproachestomodelmultipleaccesschannelsintermsofwhat isknowntostations.Historically,therstapproachwastousethequeue-freemodel, inwhicheachinjectedpacketistreatedasifhandledbyanindependentstationwithout anynameandnoprivatememoryforaqueue.Inthismodel,thenumberofstationsis notsetinanyway,asstationscomeandgosimilarlyaspacketsdo;see[35]fortheinitialworkonthismodeland[20]forrecentone.Unpredictabilityofaccesstothechannel amongthestationscanbehandledbyusingrandomizationinresolvingconictforaccess, asimplementedincarrier-sensemultipleaccessprotocols,seethebookbyKeshav[46] foranoverview.Consideringdeterministicprotocolsandtheirworst-caseperformance requiresmethodologicalsettingspecifyingworst-caseboundsonhowmuchtrafcanetworkwouldneedtohandle.Thiscanbeaccomplishedformallythroughsuitableadversarialmodelsofnetworktrafcdemands.Analternativeapproachistohaveasystemwitha xednumber n ofstations,eachequippedwithprivatememorytostorepacketsinaqueue. 2

PAGE 11

Anattractivefeatureofsuchxed-sizesystemsisthatevensimplerandomizedprotocols likeAlohaarestableundersuitabletrafcload[65]whileinthequeue-freemodelthebinaryexponentialbackoffisunstableforanyarrivalrate[4].Weconsidermodelswherethe sizeofthesystemandnamesofstationsareknownandalsoconsideranonymoussystems wherethesizeofthesystemandnamesofstationsareunknown. Tostudytheworstcaseperformanceofdeterministicalgorithms,weneedamethodologyforarrivalofpacketsthatwouldallowustodoso.Themethodologyofadversarial queuingallowsthesame.Inabasicmodel,anadversaryconstrainedbyrateandburstiness controlsinjectionofpackets.Weconsideradversarialqueuingasamodeltostudyperformanceofprotocols.Packetsareinjectedintostationsbyanadversarywhoisrestricted byrateconstraints.Weconsidertwotypesofbasicadversarialmodels-window-type adversaryandleaky-bucketadversary. Aprotocolincommunicationsisthesameasalgorithmincomputerscienceandwe willusethetwointerchangeablyinthiswork.Weconsiderrestrictedclassesofprotocols,specically:acknowledgmentbased,fullsensingandgeneraladaptiveones.We considerchannelswithandwithoutcollisiondetection.Anacknowledgmentbasedprotocoltransmitsbasedontheroundofinjectionandthebinaryarrayofbitsthatcontainsthe schedule.Anadaptiveprotocolcanhavecontrolbitsattachedtothetransmissionwhereas afullsensingonesdoesnothaveanycontrolbitsattached.Wecomparecommunication environmentsbyinvestigatingtherelativepowerofclassesofprotocolsasexpressedby attainablepacketlatencyandqueuesizeforgivendemandontrafc.Wedeveloptoolsto performexperimentstocomparepacketlatencyofdeterministicandrandomizedbackoff protocols.Weintroduceanovelapproachinmodelingadversarialpacketinjectionand jamminginsimulatedexperimentstorepresenttheburstinessoftrafc.Asfarasweknow modelingsuchanadversaryhasnotbeenattemptedbefore.Resultsofexperimentsare presentedtoverifyandvisualizetheabstractupperboundsonpacketlatency. 3

PAGE 12

2.Mainresults Herewesummarizesomeofthemainresultsinchapters5,6,7,8and9. Someoftheresultsinchapter5appearedinapreliminaryformasconferencepaper inAnantharamu etal. [12].Inchapter5weextendthebasicadversarialmodeltoinclude jamming,wherethe'jammed'roundhasthesameeffectasacollision.Thegoalofthis workwastostudystabilityandpacketlatencyofdeterministicprotocolsagainstleakybucketadversarieswithcombinedinjectionandjammingrateslessthan1.Themain resultsincludeacomparisonofperformancebetweenfullsensingandadaptiveprotocols intermsoftheworstcasepacketlatencyandknowledgerequiredtoachievebounded packetlatency.Weshowthataboundedworst-casepacketlatencyisachievablebyfull sensingprotocolsagainstadversariesforwhomjammingburstinessisatmostagiven bound J ,while J ispartofthealgorithm.Ontheotherhandwedemonstratethatadaptive protocolscanachieveboundedpacketlatencywithoutrestrictingjammingburstinessof adversariesinthealgorithm.Forallthedeterministicprotocolswestudy,wegiveupper boundsasfunctionsofthesizeofthesystemandtheadversaryandshowtightnessof bounds. Someoftheresultsgiveninchapter6appearedinapreliminaryformasconference paperinAnantharamu etal. [11].Weconsiderworstcasepacketlatencyofdeterministic distributedprotocols,dependingonsizeofthesystemandanadversaryofinjectionrates lessthanone,butachannelwithoutjamming.Weconcentrateonspecicdeterministic protocols;forthemweestimateupperboundonthequeuesizeandpacketlatencythey provideasfunctionsofthesizeofthesystemandanadversaryathand.Oneoftheinterestingandsurprisingresultsasopposedtointuitionswasthebenetofadesignparadigm, whichwecall'old-rst'inthedesignofprotocols. Someoftheresultsgiveninchapter7appearedinapreliminaryformasconference paperinAnantharamu etal. [13].Westudytheworst-caseperformanceofbroadcasting whentrafcdemandsarespeciedasadversarialenvironmentsmodeledbywindowadversarieswithindividualinjectionratesassociatedwithstationsandwhenprotocolsare 4

PAGE 13

bothdistributedanddeterministic.Weallowtheadversariestobesuchthattheassociated aggregateinjectionratethesumofalltheindividualratesis1,whichisthemaximum thatallowsforstability.Thegoalwastoexplorewhatqualityofservicecanbeachieved forindividualinjectionratesandcomparetheadversarialenvironmentsdenedbyindividualratesversusglobalones,undermaximumbroadcastloadsofonepacketperround.The underlyingmotivationforthisworkwasthatindividualinjectionratesaremorerealisticin moderatetimespansandhopefullythelimitationsonqualityofservicewiththroughput1 discoveredin[30]wouldnotholdwhentheratesareindividual.Indeed,boundedpacket latencyturnsouttobeachievablewithindividualinjectionrateswhentheaggregaterate is1.Thisisincontrastwithglobalinjectionratesforwhichachievingnitewaitingtimes isimpossibleforthroughput1,aswasshownin[30].Weshowupperandlowerboundson queuesizeandpacketlatency,whichdependontheclassesofprotocolsandwhethercollisiondetectionisavailableornot.Themostrestrictedacknowledgmentbasedprotocols cannotachievethroughput1,whichstrengthenstheresultforglobalinjectionrates[30]. Weshowupperandlowerboundsonqueuesizeandpacketlatency,whichdependonthe classesofprotocolsandwhethercollisiondetectionisavailableornot. Inchapter8wehaveexperimentalsetupandresultsofexperiments.Someofthis resultsappearedinpreliminaryforminconferencepapersAnantharamu etal. [11,12] Wepresentresultsofexperimentsinwhichprotocolsareassessedbyperformancemetrics evaluateddependingoninjectionrateandburstinessoftrafc.Patternsofpacketinjectionintheexperimentsarestructuredtocapturethecorrespondingadversarialmodels whileusingstochasticcomponentsinalimitedmanner.Weranexperimentsforthedeterministicprotocolsandalsowithtworandomizedprotocols,whichwerechosentobethe binaryexponentialback-offandthequadraticpolynomialback-off.Thendingsindicate thatdeterministicprotocolscomparefavorablywiththerandomizedcounterpartsandcan effectivelyhandlevaryinginjectionandjammingrates. Inchapter9weproposeanadversarialmodeloftrafcdemandsforadhocmultiple accesschannelswhichcapturesadynamicscenarioinwhichstationsjoinandleavethe 5

PAGE 14

system.Someoftheresultshavebeensubmittedinpreliminaryforminconferencepaper Anantharamu etal. [10].Asanonymoussystemscannotbreaksymmetryinadeterministicmanner,werestrictadversariesbyallowingthemtoactivateatmostonestationper round,whichprovidespotentialmeansfordeterministicprotocolstobeabletohandle dynamictrafc.Weconsiderdeterministicdistributedprotocols,whichwecategorizeinto acknowledgmentbased,activationbasedandfullsensing,andindependentlyintoadaptiveandnon-adaptiveones,bythepropertyofeitherusingcontrolbitsinmessagesor not,respectively.Wegiveanumberofprotocols,forchannelswithandwithoutcollision detection,forwhichweassesinjectionratestheycanhandlewithboundedpacketlatency. Morespecically,ournon-adaptiveactivation-basedprotocolcanhandleinjectionsrates lessthan 1 3 onchannelswithcollisiondetection,theadaptiveactivation-basedprotocol canhandleinjectionrate 1 2 onchannelswithoutcollisiondetection,thenon-adaptivefullsensingprotocolcanhandleinjectionrateslessthan 2 3 onchannelswithcollisiondetection, andtheadaptivefull-sensingprotocolcanhandleinjectionrate 3 4 onchannelswithcollisiondetection.Wealsoshowthatthelatterprotocolisoptimal,intermsofinjectionrate 3 4 thatcanbehandledwithboundedpacketlatency,asweprovethatnoprotocolcanprovide boundedpacketlatencywheninjectionratesaregreaterthan 3 4 6

PAGE 15

3.Relatedwork Herewesurveythepreviousworkondynamicbroadcasting. Broadcastingsubjecttostochasticconstraints: Thepreviousworkondynamic broadcastinginmultiple-accesschannelshasbeenmostlycarriedoutundertheassumptionthatpacketswereinjectedsubjecttostochasticconstraints.Suchsystemscanbe modeledasMarkovchainswithstabilityunderstoodasergodicity.Alternatively,stability maymeanthatthroughputequalstheinjectionrate.Popularearlybroadcastprotocols likeAloha[1]andbinaryexponentialbackoff[56]havebeenextensivelystudiedwith stochasticinjectionrates;Gallager[35]givesanoverviewofearlyworkinthisdirection. Forrecentpapers,seetheworkbyGoldbergetal.[38,39].AlsoHstadetal.[42],and RaghavanandUpfal[59]arerecentpapers. Acknowledgmentbasedprotocolsincludetherstrandomizedprotocolsstudiedon dynamicchannels.Alohaandbinaryexponentialbackofffallintothiscategory.The throughputofmultipleaccesschannels,understoodasthemaximuminjectionratewith Poissontrafcthatcanbehandledbyarandomizedprotocolandmakethesystemstable ergodic,hasbeenintensivelystudiedintheliterature.Itwasshowntobeaslowas 0 : 568byTsybakovandLikhanov[64].Goldbergetal.[38]gavesuchboundsforbackoff, acknowledgment-basedandfull-sensingprotocols. Stabilityofrandomizedprotocolscanbeconsideredinthequeue-freemodel,which representsalargesetofstationsbyhavinganinjectedpacketassociatedwithanewstationthatdiesafterthemessagehasbeenheardonthechannel.Acknowledgmentbased protocolsandfull-sensingoneshavebeenidentiedasnaturalimportantsubclassesofprotocols.BackoffandAlohaprotocolshavebeenmostpopularrepresentativesofacknowledgmentbasedrandomizedprotocols.Theywereshowntobeunstableinthequeue-free model;inparticularAldous[4]showedthatbinaryexponentialbackoffwastransientand hadzerothroughput.Fullsensingprotocolswereshowntofarewellinthismodel;some protocolsstableforinjectionrateslightlybelow1 = 2weredeveloped;seeGallagher[35]. Stabilityofbackoffprotocolsformultiple-accesschannelswithpacketinjectioncontrolled 7

PAGE 16

byawindowadversarywasstudiedbyBenderetal.[20]inthequeue-freemodel:they showedthatexponentialbackoffisstablefor O 1 = log n arrivalratesandunstableforarrivalratesof W loglog n = log n .Themodelofanitenumber n ofstationswithqueues gottobeconsideredasaviablealternative,asqueuesappeartohaveastabilizingeffect. Hstad etal. [42]showedthatthebinaryexponentialbackoffwasunstableifthearrival ratesatstationswereequalandtheirsumexceeded0 : 567 + 1 = 4 n )]TJ/F18 11.9552 Tf 10.34 0 Td [(2 ,andAl-Ammal et al. [3]showedthatthebinaryexponentialbackoffwasstableforinjectionratesof O n )]TJ/F50 8.9664 Tf 6.966 0 Td [(d for d > 0 : 75.Hstad etal. [42]showedthatanysuperlinearpolynomialbackoffwasstable foranyarrivalratelessthan1. Thetruncatedbinaryexponentialbackoffisusedtoimplementarbitrationforaccess tothechannelintheEthernet[56].Theperformanceofbinaryexponentialbackoffhas beeninvestigatedextensivelyinthesaturationmodelinwhicheachstationshasatleast onepacketinitsqueueatalltimes.Thismodelisconducivetodecouplingbackofffrom theenvironmenttostudyitforitsownsakewithperformancerepresentedasthesaturationthroughput.RecentworkinthisdirectionwasperformedbyBianchi[24],Huiand Devetsikiotis[43],Kong etal. [48],Kwak etal. [50],Sharma etal. [63],andZiouvaand Antonakopoulos[67].Thestabilityofaprotocolintheadversarialqueuingmodelcould beunderstoodtomeanthatthethroughputisaslargeasaninjectionrate;suchstabilityof randomizedbackoffformultiple-accesschannelswasstudiedbyBender,Farach-Colton, He,KuszmaulandLeiserson[20].Theyshowedthattheexponentialbackoffisunstable forrates r c lglg n = lg n ,forasufcientlylargeconstant c Tokenbasedprotocols: TokenringisaprotocolthatwasinitiallyusedbyIBMcomputers.Thisprotocolusesatokenwhichisaxedthreebyteframe.Thetokentravels aroundtheringandtheprocessorthathasthetokengetstotransmit.Thistokenpassing mechanismissharedbyARCNETandtokenbus. 8

PAGE 17

Adversarialqueuing: Adversarialgenerationofpacketswasproposedasanalternative methodologytocapturethenotionofstabilityofprotocolswithoutstatisticalassumptions aboutinjectionratesinstore-and-forwardrouting.Borodinetal.[26]proposedthisinthe contextofgreedycontention-resolutionroutingprotocols.Theyconsideredrate1adversaries,variousnetworksandschedulingpolicies.Theirresultsincludedshowingstability foreverydirectedacyclicnetwork,instabilityforthecaseofgraphswithdirectedcycles forFIFOandLongest-In-Systemschedulingpolicies,stabilityforaunidirectionalring withFarthest-To-GoschedulingpolicyandinstabilityforNearest-To-Goschedulingpolicy.ThesubsequentworkbyAndrewsetal.[14]concentratedonthenotionofuniversal stability,whichforaprotocoldenotesstabilityinanynetwork,andforanetworkdenotes stabilityofanarbitraryprotocolexecutedbythenetwork,bothpropertiestoholdunder injectionrateslessthan1.Theyshowthattheringisuniversallystablewithdeterministicadversarieswithrateslessthan1.Theyalsoshowthatcertainschedulingpolicies, suchasNewest-in-SystemNIS,Longest-in-SystemLISandFarthest-to-GoFTGare universallystable.Theyalsoshowthatcertaincommonschedulingpolicies,suchasFIFO andNearestToGoNTGarenotuniversallystable. Thequalityofwork-preservingprotocolsandtheimpactoftopologyofnetworkshas beenextensivelystudied;nextwegiveaselectionofrepresentativeresults.TheFIFO protocolwasshowntobeunstableatarbitrarilylowinjectionratesbyBhattacharjee,Goel andLotker[23].Everywork-preservingcontention-resolutionprotocolturnsouttobe stableifinjectionrateissmallerthan1 = D + 1 ,where d isanupperboundonthelength ofanypaththatapacketneedstotraverse,aswasshownbyLotker,Patt-Shamir,and Rosn[53].Aiello,Kushilevitz,OstrovskyandRosn[2]initiatedthestudyofstabilityof adaptiveprotocolswhichhavepacketscarryonlytheirdestinationaddresses,ratherthan completeroutingpaths.Manyquestionofhowstructuralpropertiesofnetworksaffect stabilityofcontention-resolutionprotocolswasstudiedbyKoukopoulos,Mavronicolas, NikoletseasandSpirakis[49]. RosnandTsirkin[61]consideredroutingagainstrate-1adversaries;theydened 9

PAGE 18

reliabilityofaprotocoltomeanthateachpacketiseventuallydeliveredandshowedthat reliabilityisachievableonlyinnetworkswithnocyclesoflengthatleast3.lvarezet al.[6]appliedadversarialmodelstocapturephenomenarelatedtoroutingwithvarying prioritiesofpacketsandtostudytheirimpactonuniversalstability.Inlvarezetal.[7] consideruniversalstabilityfordifferenttypespathsforundirectedgraphs.Foreachcase theyconsidertheygivepolynomialalgorithmsandalsoshowinstabilityforNTG-LIS protocols.Inlvarezetal.[5]addressthestabilityproblemwhentheselectedqueuing policyisFFS.TheyshowthepolynomialtimedecidabilityofthestabilityunderFFSinthe generalcaseinwhichtheadversarycansolvetiesarbitrarily.lvarezetal.[8]addressed thestabilityofprotocolsinnetworkswithlinkspronetofailureswithadversarialmodeling offailures. AndrewsandZhang[15]gaveauniversalprotocoltocontroltrafcwhennodesoperateasswitchesthatneedtoreservethesuitableinputandoutputportstomoveapacket fromtheinputporttotherespectiveoutputone.AndrewsandZhang[16]proposedsuitableadversarialmodelsfornetworksinwhichnodesrepresentswitchesconnectinginputs withoutputssothatroutedpacketsencounteradditionalcongestionconstrainsatnodes whentheycompetewithotherpacketsforinputandoutputports. Adversarialqueuinginmultipleaccesschannels: Adversarialqueuingasamethodologytostudytheperformanceofdeterministicdistributedbroadcastprotocolsinthe modelwithqueuesformultiple-accesschannelswasintroducedbyChlebusetal.[31]. Theyre-denedthesubclassesofacknowledgment-basedandfull-sensingdistributedprotocolsinthecasewhenprotocolsaredeterministic.Theyalsodenedlatencytobefair whenitwas O burstiness = rate andstabilitytobestrongwhenqueueswere O burstiness whenburstinesswasunderstoodasthemaximumnumberofpacketsthatcanbeinjected inaround.Itwasshownin[31]thatnoprotocolcouldbestronglystablefor w 1 log n rates andfullsensingprotocolsachievingfairlatencyfor O 1 = polylog n ratesweregiven.Paper[31]showedthatnoacknowledgmentbasedprotocolcouldbestableforrateslarger 10

PAGE 19

than 3 1 + lg n ,andhencethattherearenouniversallystableacknowledgmentbasedprotocols.Twoacknowledgmentbasedprotocolsweredevelopedin[31]:oneoffairlatency forratesatmost 1 cn lg 2 n ,forasufcientlylarge c > 0,andanexplicitoneoffairlatency forratesatmost 1 27 n 2 ln n .Inasubsequentwork[30],Chlebusetal.investigatedthequalityofserviceforthemaximumthroughput,thatis,themaximumrateforwhichstability isachievable.Theyconsideredtwokindsofadversaries,windowadversariesandleakybucketones.Theydevelopedastableprotocolwith O n 2 + burstiness queuesagainst leaky-bucketadversariesofinjectionrate1,whichmeansthatthroughput1isachievable.Theyalsoshowedlimitationsofthroughput1:achievingfairnessisimpossible, queuesneedtobe W n 2 + burstiness ,andprotocolsneedtobeadaptive.Anantharamuet al.[11,12]studiedpacketlatencyofbroadcastingonadversarialmultipleaccesschannels bydeterministicdistributedprotocolswheninjectionratesarelessthan1. Jamming: Gilbertetal.[37]proposedtomodeldisruptiveinterferenceinmulti-channel single-hopnetworksbyajammingadversary.ThiswasfurtherinvestigatedbyDolevet al.[34]whoconsideredrestrictedgossipinginwhichaconstantfractionofrumorsneeds tobedisseminatedwhentheadversarycandisruptonefrequencyperround,Gilbertet al.[36]whostudiedgossipinginwhichtheadversarycandisruptupto t frequenciesper roundandeventuallyallbut t nodeslearnallbut t rumors,andbyDolevetal.[33]who consideredsynchronizationofamultichannelunderadversarialjamming.Awerbuchet al.[18]developedarandomizedprotocolformultiple-accesschannelscompetingagainst anadaptivejammingadversarythatachievesaconstantthroughputforthenon-jammed rounds. Multi-hopwirelessnetworks: AndrewsandZhang[17]investigatedroutingand schedulinginwirelessnetworkswhereeverynodecantransmitdatatoatmostoneneighboringnodepertimestepandwheredataarrivalsandtransmissionratesaregoverned byanadversary;theydesignedschedulingalgorithmsthatensurenetworkstabilityfor 11

PAGE 20

thecaseinwhichtheadversaryspeciesthepathsthatthedatamustfollow.Bender etal. [20]appliedadversarialapproachtostudythroughputofrandomizedbackofffor multiple-accesschannelsinthequeue-freemodel;theyunderstoodstabilitytomeanthat thethroughputisaslargeastheinjectionrate.Theyshowedthattheexponentialbackoff isunstablefor r c lglg n = lg n rates,forasufcientlylargeconstant c .Packetlatency ofroutingprotocolsforstore-and-forwardwirednetworkshasbeenatopicofextensive research.Astochasticapproach[51,66]hasbeendominantpriortointroductionofadversarialqueuingmodel.AndrewsandZhang[17]studiedroutinginwirelessnetworks whendataarrivalsandtransmissionratesaregovernedbyanadversary. Multipleaccesschannelswithjamming: Weknowoftwopapersonjammingin multiple-accesschannelscloselyrelatedtothiswork.Awerbuch etal. [18]studiedjamminginmultipleaccesschannelsinanadversarialsettingwiththegoaltoestimatesaturationthroughputofrandomizedprotocols.Theyconsideredanadversarialmodelwith agivenjammingrate;themodelcapturesburstinessofjammingbygivingtheminimum windowsizethatdeterminesthejammingrate.Moreprecisely,a T ; l -typeadversary canjamatmost w l roundsinanywindow w T .Aprotocolis c-competitive ifthenodes managetoperformsuccessfulmessagetransmissionsinatleasta c -fractionofthetime stepsnotjammedbytheadversary;thisisunderstoodtobewithhighprobabilityoronexpectation.Thepaperpresentsamedium-access-controlprotocolthatisconstantcompetitivewithhighprobabilityunderany T ; 1 )]TJ/F50 11.9552 Tf 11.036 0 Td [(e -boundedadversary,assumingtheprotocol isexecutedforsufcientlymanyrounds.Thenumber e isnotknownbyprotocolsbutit needstobesufcientlylargeforthegiven n and T ,andprotocolsareassumedtoknow approximationsof n and T withsomeprecision.Thatpaperwasconcernedwithsaturationthroughput,whichmeansthatpacketstobetransmittedareavailableineverystation atalltimeswhilethegoalistomaximizethefrequencywithwhichpacketsareheardon thechannel.Amaindifferenceofpaper[18]withourapproachisthattheiradversaryis onlybusywithjammingandisnotinvolvedininjectingpackets,whileouradversaries 12

PAGE 21

controlbothaspectsoftrafc.Ontheotherhand,stationscannotdistinguishjamming fromthechannelbeingbusyduetocollisions,whichissimilartoourassumptionsabout themodel.Anotherpaper,byBayraktaroglu etal. [19],investigatedtheperformanceof theIEEE802.11CSMA/CAMACprotocol,asspeciedin[44],undervariousjammers. Thismodelsofjammingarecategorizedintwoindependentdimensions:oneisobliviousversusawareandtheotherisstatefulversusmemoryless.Theformercategorization representstheextenttowhichthejammercanreacttothemediumstateandthelatter theabilitytomaintainaninnerstatethataffectsfutureactions.Thisresultsinfourkinds oftherespectivejammers.Thegoalofthatpaperwastoinvestigatesaturationthroughput.ThetheoreticalapproachwasbasedonthediscreteMarkovmodelasproposedby Bianchi[24]butextendedtojammermodels.Theoutcomesofthetheoreticalanalysis in[19]werevalidatedbyexperiments. Wirelessnetworkswithjammingand/orfailures: Gilbert etal. [37]studiedsinglehopmulti-channelnetworkswithjammingcontrolledbyadversaries.Communicationwas representedasagamebetweentheadversarywhohasabudgetof b unknowntothestationswhilethestationsneedtotransmitsomeset V ofvalues.Arepresentativeresult showedthatcommunicationcanbedelayedfor2 b + Q lg j V j rounds.Onthemethodologicalside,thepaper[37]proposedtomeasureefciencyofmaliciousdisruptionin termsoftwonewmetrics: jamminggain ,denedastheratioofroundsdelayedtoadversarialbroadcasts,and disruption-freecomplexity ,denedasthenumberofroundsrequired toterminateinexecutionswithnodisruptions. Meier etal. [55]consideredmulti-channelsingle-hopnetworksinscenarioswhenan adversarycandisruptsome t channelsoutof m inaround,when m isknownwhile t isnot.Single-hopmultichannelwirelessnetworksarelikeanumberofmultiple-access channelssuperimposedonthesamesetofstations.Thecommunicationgoalistodiscover`communicationpartners'inthefollowingsense:twonodessuccessfullydiscover eachotherwhentwonodesusethesamechannel,oneofthemistransmittingwhilethe 13

PAGE 22

otherisreceiving,andsimultaneouslynoothernodeistransmittinginthisroundonthis channel,andthechannelisnotjammed.Aprotocolwasproposedin[55]toachievethe communicationgoal,whichisvalidatedbyexperiments.Gilbert etal. [36]considereda multi-channelwheretheadversarycancontrolinformationowonasubsetofchannels. BhandariandVaidya[21,22]consideredbroadcastprotocolsinmulti-hopnetworkswhere nodesarepronetofailures. Simulationsofback-offinmultiple-accesschannels: Binaryexponentialback-offhas beeninvestigatedinthesaturationmodel,whichhaseachstationshaveatleastonepacket initsqueueatalltimes.Themodelallowstostudytheutmostperformanceofback-offin termsofthesaturationthroughput.ForrecentworkseepapersbyBianchi[24],Huiand Devetsikiotis[43],Kong etal. [48],Kwak etal. [50],Sharma etal. [63],andZiouvaand Antonakopoulos[67]. Misbehaviorinwirelessnetworks: GeneralmisbehaviorphenomenarelatedtomediaaccesscontrolinwirelessnetworksweresurveyedbyGuang etal. [41].Jammingin wirelessandsensornetworkswasreviewedbyMpitziopoulos etal. [57]andPelechrinis etal. [58]. 14

PAGE 23

4.Technicalpreliminaries Amultiple-accesschannelisdesignedtosupportefcientbroadcast.Suchsystems haveadditionalspecicpropertieswhichwediscussinthissection.Wealsodeneadversarialmodels,classesofbroadcastprotocolsandmeasuresofqualityofservice.The letter n denotesthenumberofstationsattachedtoachannel.Eachstationhasaunique integernameintherangebetween1and n MultipleAccessChannels: Achanneloperatessynchronously.Anexecutionofaprotocolisstructuredasasequenceofrounds.Ittakesoneroundforastationtotransmita messages,sotwooverlappingtransmissionsoccurinthesameroundandarerestrictedto thisround. Amessagesuccessfullyreceivedbyastationissaidtobe heard bythestation.A broadcastsystemisa multiple-accesschannel ifcommunicationisgovernedonthelogical levelbythefollowingtworules:amessagetransmittedbyastationisdeliveredtoall thestationsinthesameround,andatransmittedmessageisheardbyallstationsifand onlyifitstransmissiondoesnotoverlapintimewithanyothertransmissions.Atmostone messageperroundcanbeheard,whichmeansthatthethroughputrateisatmost1. Multiplicityoftransmissionsdeterminesthreecases:Whennostationstransmitina round,thensucharoundis silent ,and silence iswhatthestationsreceivethenfromthe channelasfeedback.Whenexactlyonestationtransmitsinaround,thenthemessageis heardbyallthestationsinthesameround.Multipletransmissioninthesameroundresult ina conictforaccess tothechannel,whichiscalled collision .Whenacollisionoccurs, thennostationcanhearanymessage.Thechannelis withcollisiondetection whenthe feedbackfromthechannelallowsthestationstodistinguishbetweensilenceandcollision, otherwisethechannelis withoutcollisiondetection .Ifnocollisiondetectionmechanism isavailable,thenstationsperceivecollisionassilence. Adversaries: An adversary isdenedbyasetofallowablepatternsofinjectionsof packetsintostations.Anadversarygeneratesanumberofpacketsineachroundand 15

PAGE 24

next,foreachpacket,assignsastationtoinjectthepacketinthisround.Wedenethe burstiness ofanadversarytobethenumberofpacketsthatcanbeinjectedintothesystem inthesameround.Anadversaryisdenedbyconstraintsonthepatternsofinjection expressedintermsofinjectionratesatstationsandburstiness. Adversariescanbecategorizeddependingonhowinjectionratesaredened.There aretwopopularclassesofwindowadversariesandleaky-bucketones.Packetsare injectedintostationsbyawindow-typeadversarythatisrestrictedbyaninjectionrate r andawindow w .Thewindow w isusedtodenetheinjectionrate r asfollows:forany contiguoustimeinterval t of w roundsthenumberofpacketsinjectedin t isatmost r w Packetsareinjectedintostationsbyaleaky-bucket-typeadversarythatisrestrictedbyan injectionrate r andaburstiness b .Foratimeinterval t ,theadversarymayinsertatmost j t j r + b packets. BroadcastProtocols: Packetsneedtobeparkedatstationswhenthereiscontentionfor accesstothechannelorwhenmultiplepacketsareinjectedatthestationsimultaneously. Eachstationhasitspacketsstoredinalocalqueue.Ifaprotocolisstableforamultiple accesschannelwiththeFIFOqueuingdiscipline,thenitalsowillbestablewithany otherqueuingpolicy.WeuseprotocolswithFIFOqueuing,asthisdisciplineadditionally providesfairnessandminimizeslatency.Thenumberofpacketsstoredataqueueina givenroundiscalledthe sizeofthequeue intheround.Thecapacityofeveryqueueis assumedtobeunbounded,sothataqueuecanstoreanynumberofpacketsinprinciple. Whenstationsexecuteaprotocol,thenthe stateofastation isdeterminedbythe valuesofitsprivatevariables.Thenumber n ofallstationsisknown,inthesensethatis maybeapartofcode.Protocolsweconsiderarenottailoredtoanyspecicparameters oftheadversary;inthissensetheadversariesarenotknown.Thecontentsofpacketsdo notaffectexecutionofabroadcastingprotocol,aspacketsaretreatedasabstracttokens. A message ,eitherreceivedfromthechannelandsenttoit,mayincludeapacketand mayincludecontrolbits.Forinstance,aprotocolmayattachan`over'bittoatransmitted 16

PAGE 25

packettoindicatethatthestationwillnottransmitinthenextround.Amessageconsisting entirelyofcontrolbitsislegitimate. Aprotocolisformallydenedbywhatconstitutesthestatesandwhataretherules governingtransitionsbetweenstates.An event inaroundconsistsofthefollowingactions ateachstationintheordergiven:thestationeitherperformsatransmissionorpauses, asdeterminedbyitsstate,thestationreceivesafeedbackfromthechannel,inthe formofeitherhearingamessagewithcontentsorcollisionorsilence,newpacketsare injectedintothestation,astatetransitionoccurs. Astatetransitionisdeterminedbythestateattheendofthepreviousround,the packetsinjectedintheround,andthefeedbackfromthechannelintheround.State transitionsinvolvethefollowingoperations.Injectedpacketsareimmediatelyenqueued byastation.Atransmittedpacketisdiscardedandanewpackettotransmitisobtained bydequeuingthequeue.Ifamessageistobetransmittedinthenextround,thenitis preparedasapartofstatetransition.An execution ofaprotocolisasequenceofevents occurringinconsecutiverounds;weconsiderinniteexecutions. Naturalsubclassesofdeterministicprotocolsforadversarialsettingsinmultipleaccesschannelweredenedin[31,30],weusethesameclassication.Wecallaprotocol fullsensing whenadditionalcontrolbitsareneverusedinmessages.Ageneralprotocol thatisnotfullsensingiscalled adaptive ;suchprotocolsmaysendcontrolbitsinmessages. Aprotocolis acknowledgmentbased ifthedecisionwhetheracurrentlyhandledpacketis tobetransmittedornotdependsonlyonwhichconsecutiverounditisdevotedtobroadcastingthepacket,countingroundsfromtherstoneassignedforthepacket.Whenthe systemrunsanacknowledgmentbasedprotocol,thenastationmayignorefeedbackfrom thechannel,exceptfordetectingwhetherthepackettransmittedwasheardonthechannel, whichservesasan`acknowledgment'fromthechannel.Formally,anacknowledgmentbasedprotocolisdeterminedbyunboundedbinarysequencesassignedtostations.Each suchasequenceiscalleda transmissionsequence ;differentstationsrunningthesame protocolmayhavedifferenttransmissionsequences.Thesesequencesareinterpretedas 17

PAGE 26

follows:ifthe i thbitofthetransmissionsequenceofastationequals1,thenthestation transmitsthecurrentlyprocessedpacketinthe i thround,countingroundsfromtherst onewhenthepacketwasstartedtobeprocessed,whilea0asthe i thbitmakesthestation pauseinthecorresponding i thround. Aprotocolis conictfree ifinanyexecutioninanyroundatmostonestationtransmits.Aprotocolthatisnotconictfreeiscalled conictprone .Whenaprotocolisconict freethenweassumethatachanneliswithoutcollisiondetection. Thequalityofservicespeciesdesirablepropertiesofthefunctionalityofthesystem. Stability occurswhenthetotalnumberofpacketsinqueuesatthestationsisboundedin allrounds. Packetlatency meansthemaximumnumberofroundsspentbyapacketina queuewaitingtobeheardonthechannel.Observethataprotocolofboundedlatencyis stable,aslatencyisanupperboundonqueuesize. 18

PAGE 27

5.Channelswithjamming Weconsidermultipleaccesschannelswithjamming.Ajammedroundhasthesame effectasacollision,inhowitisperceivedbythestationsattachedtothechannel.Stations cannotdistinguishajammedroundfromaroundwithcollision.Thispropertyofjamming allowstocaptureasituationinwhichjammingoccursbecausegroupsofstationsexecute theirindependentcommunicationprotocolssothatforeachgroupaninterferencecaused byforeigntransmissionsislogicallyequivalenttojamming.Asimilarmotivationcomes fromascenarioinwhichadegradation-of-serviceattackproducesdummypacketsthat interferewithlegitimatepacketstransmittedbytheexecutedprotocol. Weconsidermediumaccesscontrolonmultipleaccesschannelsagainstadversaries thatcontrolbothinjectionsofpacketsintostationsandjammingofthecommunication medium.Thestudiedprotocolsaredeterministicandexecutedwithnocentralizedcontrol. Thegoalistoinvestigatequeuesizeandpacketlatencyofsuchprotocols.Weusethe slottedmodelofthechannel,inwhichanexecutionofaprotocolispartitionedintorounds, sothatatransmissionofapackettakesoneround. 5.1Preliminaries Asdenedbeforethereare n stationsattachedtothechannel.Eachstationhasa uniqueintegernameintheinterval [ 1 ; n ] .Atransmittingstationreceivesaninstantaneous feedbackthroughwhichitcanhearitsowntransmissionwhenitissuccessful.Stations' perceptionofthechannelsensedasbusydependsonwhetheramechanismofcollision detectionisavailableornot.Bycollisiondetectionwemeanthatthefeedbackfroma busychannelduetomultiplesimultaneoustransmissionsisdifferentfromonereceived whennostationattemptstotransmit.Westudychannelswithoutcollisiondetection. Jamming: Jammingconsideredinthispaperoccursinarelativelymildform:itisperceivedbystationsasarticialcollisions.Stationscannotdistinguishbetweenacollision causedbymultiplesimultaneoustransmissionsandonecausedbytheadversarytojam thechannelfortheround,inthesensethatthechannelissensedasbusyinbothcases. 19

PAGE 28

Categorizingrounds: Weusethefollowingterminologyregardingfeedbackfromthe channelobtainedbystationsinrounds.Roundsarecategorizedinto jammed or clear dependingonwhethertheadversaryjamsthemornot.Aroundwhennomessageis heardonthechanneliscalled void .Aroundwhennostationtransmitsiscalled silent .In particular,eachjammedroundisvoidandeachcollisionresultsinavoidround.Stations havenomeanstosensewhetheravoidroundisjammed,orclearbutsilent,orcleardue toacollision. Protocols: Weadaptdeterministicdistributedprotocols,asintroducedin[30,31].They areunderstoodinexactlythesamewayasfortheadversarialmodelwithoutjamming,as jammingisnotrecognizableasaspecialformoffeedbackfromthechannel.Weconsidertwoclassesofprotocols:fullsensingprotocolsandadaptiveones,thesedenitions wereintroducedfordeterministicprotocolsin[30,31].Amessagetransmittedonthe channelconsistsofapacketandcontrolbits.Packetsareprovidedbythetransportlayer representedbytheadversary.Wetreatpacketsasabstracttokens,inthesensethattheir contentsdonotaffecthowprotocolshandletransmissions.Ontheotherhand,controlbits maybeaddedbystations,inawayspeciedbythecodeofanexecutedprotocol,tofacilitatedistributedcontrolofthechannel.Aprotocoliscalled fullsensing whencontrolbits arenotsentinmessages,whichisincontrasttogeneralprotocolsreferredtoas adaptive Jammingadversaries: Weextendtheadversarialmodeltoincorporatejamming.We recallthedenitionofanadversarywithoutjamming,asusedin[11,31,30].A leakybucketadversaryoftype r ; b mayinjectatmost r j t j + b packetsinanycontiguous segment t of j t j rounds.Forsuchanadversary,theparameter r iscalledthe injection rate Inthispaperweconsideranadversarythatcontrolsbothpacketinjectionsandjamming.Anadversaryissubjecttotwoindependentratesforinjectionandjamming:A leaky-bucketjammingadversaryoftype r ; l ; b caninjectatmost r j t j + b packetsand, 20

PAGE 29

independently,itcanjamatmost l j t j + b roundsinanycontiguoussegment t of j t j rounds. Forthisadversary,wereferto r astheinjectionrate,andto l asthe jammingrate If l = 1thenanyroundcouldbejammed.Thereforeweassumethatthejamming rate l satises l < 1.Stabilityisnotachievablebyajammingadversarywithinjection rate r andthejammingrate l satisfying r + l > 1:thisisequivalentto r > 1 )]TJ/F50 11.9552 Tf 10.646 0 Td [(l ,sowhen theadversaryisjammingwiththemaximumcapacity,thenthebandwidthremainingfor transmissionsis1 )]TJ/F50 11.9552 Tf 10.884 0 Td [(l ,whiletheinjectionrateismorethan1 )]TJ/F50 11.9552 Tf 10.884 0 Td [(l .Itispossibletoachieve stabilityinthecase r + l = 1,similarlyasitwasshownfor r = 1in[30],butpacket latencyisthenunbounded.Weassumethroughoutthat r + l < 1. Thenumberofpacketsthattheadversarycaninjectinoneroundiscalledits injection burstiness .Thisparameterequals b r + b c foraleakybucketadversary.Themaximum continuousnumberofroundsthatanadversarycanjamiscalledits jammingburstiness Aleaky-bucketadversaryoftype r ; l ; b canjamatmost b b = 1 )]TJ/F50 11.9552 Tf 10.441 0 Td [(l c consecutiverounds, astheinequality l x + b x needstoholdforanysuchanumber x ofrounds. Performance: Thebasicqualityforaprotocolinagivenadversarialenvironmentis stability ,understoodtomeanthatthenumberofpacketsinthequeuesatstationsstays boundedatalltimes.Thisupperboundonthenumberofpacketswaitinginqueuesisa naturalperformancemetric,see[31,30].Asharperperformancemetricisthatof packet latency :itmeansanupperboundontimespentbyapacketwaitinginaqueue,counting fromtheroundofinjectionthroughtheroundwhenitisheardonthechannel. Knowledge: Apropertyofasystemorofenvironmentissaidtobe known whenitcan bereferredtoexplicitlyincode.Weassumethatthenumberofstations n isknownto thestations.Eachindividualnameisknowntotheownerofthename.Propertiesofan adversaryarenormallynotknown,unlessstatedotherwise.Theonlyexceptiontothisrule inthispaperoccursforfull-sensingprotocolsthathaveburstiness J ofanadversaryaspart ofcode:theprotocolsattaintheclaimedpacketlatencywhenburstinessisatmost J 21

PAGE 30

Threedeterministicdistributedprotocols: Wewillconsiderthreespecicdeterministicdistributedprotocolsalreadyknownintheliteratureaboutchannelswithoutjamming. Theseprotocolscanbedescribedasfollows. ProtocolR OUND -R OBIN -W ITHHOLDING RRWisafull-sensingprotocolforchannelswithoutcollisiondetection.Itoperatesinaround-robinfashion:stationsgainaccess tothechannelinthecyclicorderoftheirnames.Onceastationgetsaccesstothechannel bytransmittingsuccessfully,itunloadsallthepackets.Asilentroundisasignaltothe nextstation,inthecyclicorderofnames,totakeover. ProtocolS EARCH -R OUND -R OBIN SRRisafull-sensingprotocolforchannelswith collisiondetection.Itproceedswithasystematicsweepacrossallthestationslookingfor thesewithpackets,searchinginthecyclicorder.Whenastationwithapacketisidentied,thestationunloadsallitspacketsonebyone.Asilentroundtriggersthesweep toberesumed.Weapplybinarysearchtoidentifythenextstation.Thebinarysearch isimplementedusingcollisiondetection.Whenweinquireaboutasegmentofstations, thenallthestationswithpacketsthatareinthesegmenttransmitintheround.Asearch iscompletedbyapacketheard.Asilenceindicatesthatthesegmentisempty.Acollisionindicatesthatmultiplestationsareinthesegment:thisresultsinhavingthesegment partitionedintotwohalves,withonesegmentprocessednextimmediatelywhiletheother oneispushedonastacktowait.Atransitiontothenextsegmentoccurswhenthestackis empty. ProtocolM OVE -B IG -T O -F RONT MBTFisanadaptiveprotocolforchannelswithoutcollisiondetection.Eachstationmaintainsalistofallthestationsinitsprivatememory.Alistisinitializedtobesortedintheincreasingorderofnamesofstations.The listsaremanipulatedinthesamewaybyallthestationssoareallidentical.Theprotocol schedulesexactlyonestationtotransmitinaround,socollisionsneveroccur.Thisis implementedbyhavingaconceptualtokenassignedtostations,whichisinitiallyassigned totherststationonthelist.Astation p withthetokenbroadcastsapacket,ifithasany, otherwisetheroundissilent.Astationconsidersitself big inaroundwhenithasatleast 22

PAGE 31

n packets;suchastationattachesacontrolbittoallthepacketsittransmitstoindicate thisstatus.Abigstationismovedtothefrontofthelistanditkeepsthetokenforthe nextround.Whenastationthatisnotbigtransmits,orwhenitpausesduetoalackof packetswhileholdingthetoken,thetokenispassedtothenextstationinthelistordered inacyclicfashion. ProtocolsRRWandSRRwereintroducedin[31]andshowedtobeuniversal.ProtocolMBTFwasintroducedin[30]andshowedtobestableforinjectionrate1. Theold-rstparadigm: WeintroducenewprotocolsbymodifyingRRWandSRR sothatpacketsarecategorizedintooldandnew.Newpacketsbecomeeligible fortransmissionsonlyafteroldoneshavebeentransmitted.Formally,anexecutionis structuredasasequenceofconceptual phases ,whicharecontiguoussegmentsofrounds ofdynamiclength.Theideaistohavepacketsthathavebeeninjectedinagivenphase transmittedinthenextphase.Wemaintaintwocategoriesofpackets:the old oneshave beeninjectedinthepreviousphaseandthe new onesarebeinginjectedinthecurrent phase.Whenanewphasebegins,theoldpacketshavebeenheardonthechannelandthe newonesimmediatelygraduatetoold. ProtocolO LD -F IRST -R OUND -R OBIN -W ITHHOLDING OF-RRWoperatessimilarlyasRRW,exceptthatwhenastationgetsaccesstothechannelbytransmittingsuccessfully,thenthestationunloadsalltheoldpacketswhilethenewpacketsstayinthe queue.Aphaseisdeterminedasafullcyclearoundallthestations,sonoadditional communicationisneededtomarkatransitiontoanewphase. ProtocolO LD -F IRST -S EARCH -R OUND -R OBIN OF-SRRoperatessimilarlyasSRR, exceptthatthesearchisforoldpacketsonly.Anewphasebeginsafteralloldpacketshave beenprocessed. Protocolsforchannelswithjamming: Weintroduceaprotocoldesignedforchannels withjamming,J AMMING -R OUND -R OBIN -W ITHHOLDING J ,abbreviatedasJRRW J 23

PAGE 32

ThedesignoftheprotocolissimilartothatofRRW,thedifferenceisinhowthetoken istransferredfromastationtothenextone,inthecyclicorderamongstations.Justone voidroundshouldnottriggeratransferofthetoken,asitisthecaseinRRW,becausenot hearingamessagemaybecausedbyjamming. Theprotocolhasaparameter J interpretedasanupperboundonjammingburstiness oftheadversary,whichisusedtofacilitatetransferofcontrolfromastationtothenext onebywayofforwardingthetoken.Thetokenismovedafterhearingsilenceforprecisely J + 1contiguousrounds,countingfromeitherhearingapacketormovingthetoken;the formerindicatesthatthetransmittingstationexhausteditsqueuewhilethelatterindicates thatthequeueisempty.Moreprecisely,everystationmaintainsaprivatecounterofvoid rounds.Thecountersshowthesamevalueacrossthesystem,astheyareupdatedinexactly thesamewaydeterminedonlybythefeedbackfromthechannel.Avoidroundresultsin incrementingthecounterby1.Thetokenismovedtothenextstationwhenthecounter reaches J + 1.Whenapacketisheardorthetokenismovedthenthecounteriszeroed. ProtocolO LD -F IRST -J AMMING -R OUND -R OBIN -W ITHHOLDING J ,abbreviatedOFJRRW J ,isobtainedfromJRRW J similarlyasOF-RRWisobtainedfromRRW.An executionisstructuredintophases,andpacketsarecategorizedintooldandnew,withthe sameruletograduatepacketsfromnewtoold.Whenatokenvisitsastation,thenonly theoldpacketscouldbetransmittedwhilethenewoneswillobtainthisstatusduringthe nextvisitbythetoken. Wesaythataprotocoldesignedforachannelwithoutjammingisa tokenprotocol if itusesavirtualtokentoavoidcollisions.Suchatokenisalwaysheldbysomestationand onlythestationthatholdsthetokencantransmit.ProtocolsRRW,OF-RRW,JRRW, OF-JRRW,andMBTFaretokenones.Wecantakeanytokenprotocolforchannels withoutjammingandadaptittothemodelwithjamminginthefollowingmanner.As usual,thetokenindicatestherighttotransmit.Ifthereisapackettobetransmittedby astationintheoriginalprotocol,thenthemodiedprotocolhasapackettransmittedas well,otherwisejustacontrolbitistransmitted.Aroundinwhichonlyacontrolbitis 24

PAGE 33

transmittedbyamodiedtokenprotocoliscalled controlround otherwiseitisa packet round .Theeffectofsendingcontrolbitsincontrolroundsisthatifnoroundsarejammed thenamessageisheardineachround.Thisapproachcreatesvirtualcollisionsinjammed rounds,sowhenavoidroundoccursthenthisroundisjammedasotherwiseamessage wouldhavebeenheard.Onceaprotocolcanidentifyjammedrounds,wemayignoretheir impactontheowofcontrol.Theresultingprotocolisadaptive.Wewillconsidersuch modiedversionofthefull-sensingprotocolsRRWandOF-RRW,denotingthembyCRRWandOFC-RRW,respectively.NotethatprotocolMBTFworksbyhavingastation withthetokensendamessageevenifthestationdoesnothaveapacket,soenforcing additionalcontrolroundsisnotneededforthisprotocoltoconvertitintoonecreating virtualcollisions. Protocolswithexecutionsstructuredintophasesarereferredtoas phaseprotocols TheseincludeRRW,OF-RRW,JRRW,OF-JRRW,C-RRW,andOFC-RRW.When theold-rstparadigmisusedinsuchaprotocolthenitiscalled theold-rstversion ofthe protocol,otherwiseitis theregularversion oftheprotocol.Inparticular,RRW,JRRW andC-RRWareregularphaseprotocols,whileOF-RRW,OF-JRRWandOFC-RRW areold-rstphaseprotocols. 5.1.1Packetlatencyoffullsensingprotocols Weshowthataboundedworst-casepacketlatencyisachievablebyfullsensingprotocolsagainstadversariesforwhomjammingburstinessisatmostagivenbound J ,while J ispartofcode.Ontheotherhand,wewilldemonstratelaterthatadaptiveprotocolscan achieveboundedpacketlatencywithoutrestrictingjammingburstinessofadversariesin code.ThefullsensingprotocolsweconsiderareOF-JRRW J andJRRW J .Protocols OF-JRRW J andJRRW J includetheparameter J asapartofcode,butthevalueof J doesnotoccurintheupperboundsonpacketlatencyinTheorems1and2. Lemma1 Consideranexecutionofprotocol OF-JRRW J againstaleaky-bucketadversaryofjammingrate l ,burstinessb,andjammingburstinessatmostJ.Iftherearex 25

PAGE 34

oldpacketsinthequeuesinaroundround,thenatleastxpacketsaretransmittedwithin thenext x + n J + 1 + b = 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l rounds. Proof: Ittakes n intervalsof J + 1voidroundseachforthetokentomakeafullcycle andsotovisiteverystationwitholdpackets.Itisadvantageousfortheadversarytonot jamthechannelduringtheserounds.Thereforeatmost n J + 1 + x clearroundsare neededtohearthe x packets.Consideracontiguoustimesegmentof z roundsinwhich some x packetsareheard.Atmost z l + b ofthese z roundscanbejammed.Thereforethe inequality z n J + 1 + x + z l + b holds.Solvingfor z weobtain z x + n J + 1 + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l astheboundonlengthofacontiguoustimeintervalinwhichatleast x packetsareheard. Theorem1 Thepacketlatencyofprotocol OF-JRRW J is O bn 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(l 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l ,whenexecutedagainstajammingadversaryoftype r ; l ; b suchthatitsjammingburstinessisat mostJ. Proof: Let t i bethedurationofphase i and q i bethenumberofoldpacketsinthebeginning ofphase i ,for i 1.Thefollowingtwoestimatesleadtoarecurrenceforthenumbers t i Oneis q i + 1 r t i + b ; .1 whichfollowsfromthedenitionsofoldpacketsandoftype r ; l ; b oftheadversary. Theotherestimateis t i + 1 n J + 1 + q i + 1 + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l ; .2 whichfollowsfromLemma1.Denote n J + 1 = a andsubstitute.1into.2toobtain t i + 1 a + q i + 1 + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l a 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + r t i + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l = a 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + 2 b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l + r 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l t i c + dt i ; 26

PAGE 35

for c = a + 2 b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l and d = r 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l .Notethat d < 1as r < 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l Wendanupperboundonthedurationofaphasebyiteratingtherecurrence t i + 1 c + dt i .Tothisend,itissufcienttoinspectthesequenceofconsecutivebounds t 1 c ; t 2 c + dc ; t 3 c + dc + d 2 c ;::: onthelengthsoftheinitialphasestodiscovera generalpattern t i + 1 c + dc + d 2 c + ::: d i c c 1 )]TJ/F49 11.9552 Tf 10.949 0 Td [(d : .3 Aftersubstituting c = a + 2 b 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(l and d = r 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l into.3,oneobtains t i a + 2 b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 1 )]TJ/F50 8.9664 Tf 17.87 5.782 Td [(r 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l a + 2 b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.95 0 Td [(l a + 2 b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l : .4 Nowreplace a by n J + 1 in.4toexpanditinto t i n J + 1 + 2 b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l : .5 Applytheestimate J b = 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l to.5toobtain t i n b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l + 1 + 2 b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 2 bn + n + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l ; .6 whichisaboundonthedurationofaphasethatdependsonlyonthetypeoftheadversary, withoutinvolving J .Theboundonpacketlatencyweseekistwicethatin.6,asa packetstaysqueuedforatmosttwoconsecutivephases. Theorem2 Thepacketlatencyofprotocol JRRW Jis O )]TJ/F49 8.9664 Tf 33.455 -4.979 Td [(bn 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l 2 whenexecuted againstajammingadversaryoftype r ; l ; b suchthatitsjammingburstinessisatmostJ. Proof: WecomparepacketlatencyofprotocolJRRW J tothatofprotocolOFJRRW J .Tothisend,consideranexecutionofprotocolsJRRW J andOF-JRRW J determinedbysomeinjectionandjammingpatternoftheadversary.Let s i and t i bebounds onthelengthofphase i ofprotocolsOF-JRRW J andJRRW J ,respectively,whenrun againsttheconsideredadversarialpatternofinjectionsandjamming. Phase i ofOF-JRRW J takes s i rounds.WhenprotocolJRRW J isexecuted,the totallength t i ofphase i isatmost s i + s i r + l + s i r + l 2 + ::: = s i 1 )]TJ/F52 11.9552 Tf 10.949 0 Td [( r + l .7 27

PAGE 36

rounds.Weobtainthatthephase'slengthofprotocolJRRW J differsfromthatofprotocolOF-JRRW J byatmostafactorof 1 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l ProtocolsJRRW J andOF-JRRW J sharethepropertythatapacketistransmitted inatmosttwoconsecutivephases,therstonedeterminedbytheinjectionofthepacket. TheboundonpacketlatencygiveninTheorem1isfortwicethelengthofaphaseof protocolOF-JRRW J .Similarly,aboundontwicethelengthofaphaseofprotocol JRRW J isaboundonpacketlatency.Itfollowsthataboundonpacketlatencyof protocolJ-RRW J canbeobtainedbymultiplyingtheboundgiveninTheorem1by 1 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l Tightnessoftheupperbounds: TheupperboundsonpacketlatencygiveninTheorems2and1differbythemultiplicityofthefactor1 )]TJ/F50 11.9552 Tf 10.576 0 Td [(r )]TJ/F50 11.9552 Tf 10.575 0 Td [(l occurringinthedenominator. Thisdifferencebetweenthetwoboundsreectsthebenetoftheparadigmold-rstappliedinthedesignofprotocolOF-JRRW J ,ascomparedtoprotocolJRRW J Themultiplicitiesofthefactors1 )]TJ/F50 11.9552 Tf 11.069 0 Td [(l and1 )]TJ/F50 11.9552 Tf 11.069 0 Td [(r )]TJ/F50 11.9552 Tf 11.069 0 Td [(l occurringintheboundsofTheorems1and2aretight.ToshowthisfortheboundofTheorem2,considerprotocol JRRW J inachannelwithjamming.Theadversarywillinjectpacketsandjamthe channelatfullpower,subjecttoconstrainsimposedbyitstype.Thenumberofclear voidroundsineachphaseis a = n J + 1 .Thenumberofpacketsinjectedduetothese voidroundsis a r ,andittakes a r + l roundstotransmitthem.Intherstphase, a r packetsaretransmittedin a r + l roundsandaqueueof a r + l r packetsbuildsupin station n )]TJ/F18 11.9552 Tf 11.011 0 Td [(1.Inthesecondphase,thereare a r and n r + l r packetstransmittedbystations n and n )]TJ/F18 11.9552 Tf 10.897 0 Td [(1,respectively;thistakestime a r + l 2 andresultsin a r + l 2 r packets queuedatstation n )]TJ/F18 11.9552 Tf 10.979 0 Td [(2.Thisprocesscontinuesuntilphase n )]TJ/F18 11.9552 Tf 10.978 0 Td [(2inwhichtheadversary's behaviorchanges.Thedifferenceisthattheadversaryinjectsjustonepacketintostation2 afterthetokenhaspassedthroughthatstation.Whatfollowsisphase n )]TJ/F18 11.9552 Tf 11.092 0 Td [(1inwhichthe queueatstation1is W a + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l .Lettheadversaryinjectpacketsatfullpoweronlyinto station1inthisphase.Considerthelatencyofpacketinstation2.Thepacketsinsta28

PAGE 37

tion1areunloadedbywithholdingthechannelwhiletheadversarykeepsinjectingonly intothetransmittingstation.Letusassignasuitablylarge J totheadversary,forinstance J b = 2 1 )]TJ/F50 11.9552 Tf 10.897 0 Td [(l willdo.Thelatencyoftheonlypacketinstation2isestimatedasbeing W n J + 1 + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 2 = W n b 2 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l + 1 + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 2 = W bn 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 2 : ThisshowsthattheupperboundgiveninTheorem2istightinthesenseoftheformof thedenominator.RegardingtheboundofTheorem1,onepossiblewaytoargueaboutits tightnessistoexamineitsprooftoseethatthederivationcanbemimickedbyadversary's actions.AnotherapproachtoarguethattheboundinTheorem1istight,intermsofthe factors 1 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l and 1 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l ,istoobservethattheboundinTheorem2wasobtainedfromthe boundinTheorem1bymultiplyingitbythefactor 1 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l ,sothatanyimprovementinthe boundinTheorem1wouldbereectedinanimprovementintheboundinTheorem2, whichhasbeenshowntobetight. Knowledgeofjammingburstiness: Wehaveshownthatafullsensingprotocol achievesboundedpacketlatencyfor r + l < 1whenanupperboundonjammingburstinessisapartofcode.Next,wehypothesizethatthisisunavoidableandreectstheutmost poweroffullsensingprotocols. Conjecture1 Nofullsensingprotocolcanbestableagainstalljammingadversarieswith ratessatisfying r + l < 1 5.1.2Packetlatencyofadaptiveprotocols WegiveupperboundsonpacketlatencyforeachamongthefollowingadaptiveprotocolsC-RRW,OFC-RRW,andMBTF.Theboundsaresimilartothoseobtainedin Theorems1and2,fortheirfullsensingcounterparts.Theapparentrelativestrengthof adaptiveprotocolsisreectedintheirboundssheddingthefactor1 )]TJ/F50 11.9552 Tf 11.348 0 Td [(l inthedenominators.Eachoftheseadaptiveprotocolsisstableforanyjammingburstiness,unlikethe 29

PAGE 38

fullsensingprotocolsweconsiderthathavejammingburstinesstheycanhandleintheir codes. Lemma2 Consideranexecutionofprotocol OFC-RRW againsttheleaky-bucketadversaryoftype r ; l ; b .Ifinanyroundtherearesomexoldpacketsinthesystem,thenat leastxpacketsaretransmittedwithinthenext x + n + b 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(l rounds. Proof: Ittakes n controlroundsforthetokentopassthroughall n stations.Considera contiguoustimesegmentof y roundsinwhichsome x packetsareheard.Atmost y l + b ofthese y roundscanbejammed.Itfollowsthattheinequality y n + x + y l + b holds. Solvingfor y yieldstheupperbound y x + n + b = 1 )]TJ/F50 11.9552 Tf 10.997 0 Td [(l ,astheboundonlengthofa contiguoustimeintervalinwhichatleast x packetsareheard. Theorem3 Thepacketlatencyofprotocol OFC-RRW is O )]TJ/F49 8.9664 Tf 12.835 -4.979 Td [(n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.966 0 Td [(l whenexecuted againstthejammingadversaryoftype r ; l ; b Proof: Let t i denotethedurationofphase i and q i bethenumberofoldpacketsinthe beginningofphase i ,for i 1.Weusethefollowingtwoestimatestoderivearecurrence forthenumbers t i .Oneis q i + 1 r t i + b ; .8 whichfollowsfromthedenitionofoldpacketsandtheadversaryoftype r ; l ; b .The otheris t i + 1 q i + 1 + n + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l ; .9 whichfollowsfromLemma2.Usingtheabbreviations c = n + 2 b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l and d = r 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l ,substitute .8into.9toobtain t i + 1 n + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + r t i + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l = n + 2 b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + r 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l t i c + dt i : Tondanupperboundonthedurationofaphase,iteratetherecurrence t i + 1 c + dt i whichproduces t i + 1 c + dc + d 2 c + ::: d i c c 1 )]TJ/F49 11.9552 Tf 10.949 0 Td [(d : .10 30

PAGE 39

Aftersubstituting c = n + 2 b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l and d = r 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l into.3,weobtain,byalgebraicmanipulations, theestimate t i n + 2 b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 1 )]TJ/F50 8.9664 Tf 17.87 5.781 Td [(r 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l n + 2 b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.95 0 Td [(l 2 n + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l : Theboundonpacketlatencyweseekistwicethatin.11,asapacketisqueuedforat mosttwoconsecutivephases. Theorem4 Thepacketlatencyofprotocol C-RRW is O )]TJ/F49 8.9664 Tf 18.307 -4.98 Td [(n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l 2 whenexecutedagainst thejammingadversaryoftype r ; l ; b Proof: WecomparepacketlatencyofprotocolC-RRWtothatofprotocolOFC-RRW. ConsidertheexecutionsofprotocolsC-RRWandOFC-RRWforthesameinjectionand jammingpatternoftheadversary.Let s i and t i betheboundsonthelengthofphase i of protocolsC-RRWandOFC-RRW,respectively. Phase i ofC-RRWtakes s i rounds,sowhenprotocolOFC-RRWisexecuted,its phase i maytakeupto s i + s i r + l + s i r + l 2 + ::: = s i 1 )]TJ/F52 11.9552 Tf 10.949 0 Td [( r + l .11 rounds.Sothephase'slengthofprotocolC-RRWdiffersfromthatofprotocolOFCRRWbyafactorofatmost 1 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l .Aninjectedpacketistransmittedinatmosttwo phasesofanexecution,foreachprotocol.TheboundofTheorem3istwicetheboundon thedurationofaphase.ItfollowsthataboundonpacketlatencyofprotocolC-RRWcan beobtainedbymultiplyingtheboundgiveninTheorem3by 1 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l ThetightnessoftheboundonpacketlatencygiveninTheorem4canbeestablished similarlyasthatforTheorem2.Tothisend,replace n J + 1 by n inthetightnessargument fortheboundofTheorem2giveninSection5.1.1toobtain W )]TJ/F49 8.9664 Tf 18.307 -4.979 Td [(n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l 2 asabound.The tightnessoftheupperboundofTheorem3followsfromthepropertythatthederivationof theupperboundcanbecloselymimickedbytheadversary.Alternatively,weobservethat animprovementoftheboundinTheorem3wouldleadtoanimprovementtothebound inTheorem4,whichhasalreadybeenshowntobetight. 31

PAGE 40

ProtocolM OVE -B IG -T O -F RONT : NextweestimatepacketlatencyofprotocolMBTF againstjamming.Theanalysiswegiveresortstoestimatesofthenumberofpacketsstored inthequeuesatalltimes. Letatraversalofthetoken,startingatthefrontofthelistandendingagainatthefront stationofthelist,becalleda pass ofthetoken.Apassisconcludedbyeitherdiscovering anewbigstationortraversingthewholelist.Wemeasurethenumberofpacketsinthe queuesattheendofapass,toseeifthepasscontributedtoanincreaseofthenumberof packetsstoredinthequeuesornot;aformerpassiscalled increasing andalatterone nonincreasing ,respectively.Wepartitionpassesintotwocategories,dependingonwhethera bigstationisdiscoveredinthepassornot;aformerpassiscalled big andalatter small Tomakethisterminologyprecise,adiscoveryofabigstationcontributestothefollowing twoconsecutivepasses.Therstpassisconcludedbythediscoveryofabigstation,but thebigstationjustfounddoesnottransmitinthispass.Thesecondpassbeginsbya transmissionofthenewlydiscoveredbigstation,justafterithasbeenmoveduptothe frontpositioninthelist. Lemma3 Whenprotocol MBTF isexecutedbynstationsagainstthejammingadversaryoftype r ; l ; b thenthenumberofpacketsstoredinqueuesinanyroundisatmost 2 r n n + b 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(l 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r )]TJ/F50 8.9664 Tf 6.967 0 Td [(l + O bn Proof: Werstinvestigatehowmanypacketscanbeaccumulatedinqueueswhensmall passesoccur.Itissufcienttoconsiderincreasingsmallpassesonly,asotherwisethepreviouspassescontributebiggercountsofpackets.Supposesome i stationswithnonempty queuesarepassedbythetoken.Aseachofthemcontributestoapacketheardonthe channel,thereare i packetsheardinthepass.Apassthatisnotjammedtakes n rounds, butwithjammingitmaytakelongerasthejammedroundsslowtheprotocoldown.There areatmost b + n + n l + n l 2 + n l 3 ::: n 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + b roundsinasmallpass.Duringsuchapass,thenumberofinjectedpacketsisatmost 32

PAGE 41

n 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l + b r + b .Itfollowsthat i n 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(l + b r + b .Eachstationpassedhasatmost n )]TJ/F18 11.9552 Tf 11.04 0 Td [(1 packets,becausethepassissmall.Itfollowsthatasmallpassiseitherincreasingorthere areupto \000 n 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + b r + b n )]TJ/F18 11.9552 Tf 10.949 0 Td [(1 = r n n + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l + O bn .12 packetsinthequeueswhenthepassisover. Nextweconsiderthequestionhowmuchabovetheupperbound.12canthequeues growduringbigpasses.Consideratimeinterval T whenamaximumnumberofpackets isaccruedwhilesome k stationsarediscoveredatleastonceasbig.Toobtainestimates fromaboveonthetotalnumberofpacketsinthequeues,weconservativelyassumethe following:iwhenasmallstationispassedbythetokenthentherearenopacketsinthe queueofthestationandtheresultingroundisacontrolone,andiiwhenabigstationis discoveredandmoveduptothefrontofthelist,thenonlyonepacketistransmittedbythe stationandthenthetokenimmediatelymovesontothenextstation. Consideraseriesofconsecutivebigpasses.Thenumberofcontrolroundsinanybig passisatmost n )]TJ/F18 11.9552 Tf 11.024 0 Td [(1followedbythebigstationmovedtothefrontofthelist.Intherst pass,thereareatmost n )]TJ/F18 11.9552 Tf 10.92 0 Td [(1controlrounds.Inthesecondpass,thestationdiscoveredbig intherstpasstransmitsapacket,whichisnextfollowedbyatmost n )]TJ/F18 11.9552 Tf 10.883 0 Td [(1controlrounds untilanewbigstationisdiscovered.Inthethirdpass,thetwobigstationsdiscoveredso fartransmitatleastonepacketeach,astheyareatthefrontofthelist,whichisfollowed byatmost n )]TJ/F18 11.9552 Tf 11.356 0 Td [(2controlroundsbeforethethirdbigstationisdiscovered.Thispattern continuesuntilthelastpasswhichbeginsbyallthe k bigstationsresidingintheinitial segmentofthelistandsoeachofthemtransmittingonepacketinthispassfollowedby atmost n )]TJ/F49 11.9552 Tf 11.273 0 Td [(k controlrounds.Let t bethelastroundwhentheabovelastcontrolround amongatmost n )]TJ/F49 11.9552 Tf 10.949 0 Td [(k occurs. Whenthenextpassbeginsinround t + 1,theneitherthepassissmallorabigstation amongtherst k stationsinthelistisdiscovered,asthesearethestationsdiscoveredasbig intimeinterval T .Intheformercase,theupperbound.12onthenumberofpacketsin 33

PAGE 42

thequeuesapplies.Inthelatterone,therearenocontrolroundsduringthepass.Itfollows thatanupperboundisobtainedbyestimatingfromaboveanincreaseofpacketsinthe timeinterval T byround t andnextaddingtoitthebound.12asapossiblestarting pointoftheprocessofincreasingqueuesin T Nextweestimatetheincreaseofpacketsin T byround t .Thereareatmost k + 1 n )]TJ/F18 11.9552 Tf 10.668 0 Td [(1 controlroundsand1 + 2 + 3 + ::: + k = k k + 1 = 2packetstransmittedinpacket rounds.Atthesametime,theadversarymaybeinjectingpacketsandjammingrounds, withanetincreasecontributedbycontrolandjammedrounds.Theincreaseisatmost r 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l h k + 1 n )]TJ/F18 11.9552 Tf 10.949 0 Td [(1 + k k + 1 2 i + b )]TJ/F49 11.9552 Tf 12.145 8.094 Td [(k k + 1 2 = r 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l kn )]TJ/F18 11.9552 Tf 12.145 8.094 Td [(1 2 1 )]TJ/F50 11.9552 Tf 21.438 8.094 Td [(r 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l k 2 + O n + b : Weseektomaximizethefunction f k = r 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l kn )]TJ/F18 11.9552 Tf 12.145 8.093 Td [(1 2 1 )]TJ/F50 11.9552 Tf 21.438 8.093 Td [(r 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l k 2 ; whichwendtooccurattheargument k max = r n 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.95 0 Td [(l bythestandardmaximumndingprocedurebasedondifferentiation.Byalgebraicmanipulation,weobtainthatthevalues f k areatmost f k max r n 2 2 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l andtheincreaseofpacketsin T byround t isatmostthisnumberplus O n + b .We combinethisestimatewithbound.12toobtain r n n + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + r n 2 2 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.95 0 Td [(l + O bn 2 r n n + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + O bn asaboundonthetotalnumberofqueuedpackets.Theseestimatesarewithrespectto whatisthenumberofpacketsattheendsofpasses.Possibleuctuationsofthenumberof 34

PAGE 43

packetsinqueuesduringapasscannotbemorethan n + b ,whichiswithinthemagnitude oftheasymptoticcomponent O bn ofthebound. Whenbigstationsgetdiscoveredthentheregularround-robinpatternoftokentraversalisdisturbed.Supposeastation i isdiscoveredasbig,whichresultsinmovingthe stationbacktothefront.Theclearroundsthatfollow,beforethetokeneithermovesto position i + 1oranewbigstationisdiscovered,whicheveroccursrst,arecalled delayrounds .Theseroundsarespent,rst,ontransmissionsbythenewrststation,to bringthenumberofpacketsinitsqueuedownto n )]TJ/F18 11.9552 Tf 11.251 0 Td [(1,andnext,thetokenneeds i additionalclearroundstomovetothestationatposition i + 1.Givenaround t inwhicha packet p isinjected,takeasnapshotofthequeuesinthisround.Let q i bethenumberof packetsinastation i inthissnapshot,for1 i n .Weassociate credit oftheamount max f 0 ; q i )]TJ/F52 11.9552 Tf 11.001 0 Td [( n )]TJ/F49 11.9552 Tf 11.001 0 Td [(i g withstation i atthisround.Astation i hasapositivecreditwhenthe inequality q i n )]TJ/F49 11.9552 Tf 11.154 0 Td [(i + 1holds.Inparticular,abigstation i hascredit q i + i )]TJ/F49 11.9552 Tf 11.154 0 Td [(n i .Let C n ; t denotethesumofallthecreditsofthestationsinround t .Weconsidercreditonly withrespecttothepacketsalreadyinthequeuesinround t ,unlessstatedotherwise. Lemma4 Ifdiscoveringabigstationinroundtdelaysthetokenbysomexrounds,excludingjammedrounds,thentheamountsofcreditsatisfyC n ; t + x = C n ; t )]TJ/F49 11.9552 Tf 10.949 0 Td [(x. Proof: Werefertostationsbytheirpositionsjustbeforetheshift,unlessstatedotherwise. Whenabigstation i ismoveduptothefrontofthelist,itscreditgetsdecreasedrstby i )]TJ/F18 11.9552 Tf 11.318 0 Td [(1bythechangeofpositioninthelist,andnextbytheamountequaltothenumber oftransmittedpacketsbythenewrststation.Moreprecisely, q i )]TJ/F52 11.9552 Tf 11.297 0 Td [( n )]TJ/F18 11.9552 Tf 11.297 0 Td [(1 packetsare transmittedinthesemanyroundstodecreasecreditofthenewrststationfrom q i + 1 )]TJ/F49 11.9552 Tf 10.81 0 Td [(n tozero,aunitofcreditspentineachround. Thedecreaseoftheamountofcreditby i )]TJ/F18 11.9552 Tf 11.162 0 Td [(1istopayforthetravelofthetokento position i + 1.Thereisaproblemofwhathappenstothecreditatthetraversedstations thatchangedtheirpositions.Thestationsattheoriginalpositions1through i )]TJ/F18 11.9552 Tf 11.506 0 Td [(1get shiftedbyonepositiondownthelisttooccupythepositions2through i .Considersuch 35

PAGE 44

astation j ,for1 j i )]TJ/F18 11.9552 Tf 11.235 0 Td [(1,whenitisshiftedonepositiondownthelist.Itspotential staysequalto0,if q j < n )]TJ/F49 11.9552 Tf 12.812 0 Td [(j ,butitgetsincrementedby1if q j n )]TJ/F49 11.9552 Tf 12.812 0 Td [(j ,asitthenequals q j + j + 1 )]TJ/F49 11.9552 Tf 10.949 0 Td [(n 1. Whenapacketistransmittedbyastationthatdoesnotholdanycreditcredit,then thisdoesnotaffectthetotalamountofcredit,asthecreditcontributedbythisstationstays equaltozero.Apackettransmittedbyastationwithapositivecreditdecrementsthecredit by1,whichrestorestheamountofcreditheldbythestationbeforetheshiftdown.This meansthatthetotaldecreaseoftheamountofcreditequalsthenumberofroundsinthe timeperiodofdelay. Theorem5 Thepacketlatencyofprotocol MBTF isatmost 3 n n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r )]TJ/F50 8.9664 Tf 6.966 0 Td [(l + O )]TJ/F49 8.9664 Tf 10.374 -4.979 Td [(bn 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l when executedagainstthejammingadversaryoftype r ; l ; b Proof: Letapacket p beinjectedinsomeround t intostation i .Let S n ; t beanupper boundonthenumberofroundsthatpacket p spendswaitinginthequeueat i tobeheard whennobigstationisdiscoveredbythetimepacket p iseventuallytransmitted.Some additionalwaitingtimeforpacket p iscontributedbydiscoveriesofbigstationsandthe resultingdelays;denoteby T n ; t thenumberofroundsbywhich p isdelayedthisway. Thetotaldelayof p isatmost S n ; t + T n ; t First,wendupperboundsontheexpression S n ; t + T n ; t thatdoesnotdepend on t butonlyon n .Theinequality S n ; t n n )]TJ/F18 11.9552 Tf 10.949 0 Td [(1 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l .13 holdsbecausethereareatmost n )]TJ/F18 11.9552 Tf 11.005 0 Td [(1packetsinthequeueof i andeachpassofthetoken takesatmost n 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(l rounds.Theinequality T n ; t C n ; t 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l .14 holdsbecauseofLemma4andthefactthatiterateddelaysduetojammingcontributethe factor1 = 1 )]TJ/F50 11.9552 Tf 11.166 0 Td [(l .Observethat C n ; t isupperboundedbythenumberofpacketsinthe 36

PAGE 45

queuesinround t ,bythedenitionofcredit.Therefore,weobtainthat C n ; t 2 r n n + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.95 0 Td [(l + O bn ; byLemma3.This,alongwiththeestimate.14,implies T n ; t 2 r n n + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 2 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + O bn 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l : .15 Combine.13and.15toobtainthatapacketwaitsatmost n n )]TJ/F18 11.9552 Tf 10.95 0 Td [(1 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + 2 r n n + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(l 2 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l + O bn 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 3 n n + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r )]TJ/F50 11.9552 Tf 10.95 0 Td [(l + O bn 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l rounds,whereweused r < 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(l and1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r )]TJ/F50 11.9552 Tf 10.949 0 Td [(l < 1. 5.2Conclusion Weintroducedamodelofadversarialpacketinjectionandjammingtostudydeterministicdistributedprotocolsformedium-accesscontrol.Jammingisrepresentedbycollisionsthatprecludesuccessfultransmissionsofpacketsinjammedrounds.Terminals cannotdistinguishbetweencollisionscausedbysimultaneoustransmissionsandjamming, whichcapturesscenariosinwhichgroupsofstationsinterferewithoneanotherbyindependenttransmissions.Adversariesarerestrictedonlybytherequirementthattheconglomeraterateobtainedbysummingtheinjectionratewiththejammingrateislessthan one. Weconsideredtwoclassesofprotocols:fullsensingandgeneraladaptive.Protocols intheformerclassdonotusecontrolbitsinmessages,whichappearstorestricttheir powertoachieveboundedpacketlatencyforanyadversary.Weconjecturethatnofull sensingprotocolcanbestableforanadversarialjammingenvironmentwherethesumof theinjectionrateandthejammingratearelessthanone. Weshowedthatfullsensingprotocolscanhaveboundedpacketlatencyifonlythe adversariesarerestrictedbytheirjammingburstinesswhichispartofcodeoftheprotocol. 37

PAGE 46

Incontrasttothat,generaladaptiveprotocolscanattainboundedpacketlatencyforany adversary.Foreachconsideredprotocolwederivedworst-caseupperboundsontheir packetlatencyintermsofthesizeofthesystemandthetypeofanadversary. 38

PAGE 47

6.Channelswithoutjamming Weconsiderdeterministicdistributedprotocolsinchannelswithnojamming.We studytheperformanceoffullsensingandadaptiveprotocolsagainstleaky-bucketadversarieswithinjectionrates r < 1.Weconsiderchannelswithandwithoutcollisiondetection.Foreachoftheprotocolsweconsider,wegiveupperboundsforpacketlatencyas functionsofthenumberofstations n andthetype r ; b ofaleaky-bucketadversary. 6.1Fullsensingprotocols WeconsiderthepacketlatencyforfullsensingprotocolsRRWandOF-RRW.They operatesimilarlyastheadaptiveprotocolsC-RRWandOFC-RRWforachannelwith jamming,respectively.Thedifferenceisinhowthevirtualtokenmovesfromstationto stationandwhathappensinjammedrounds.Inadaptiveprotocolswithjamming,thevirtualtokenismovedwhenthestationwithtokentransmitsacontrolbit.Infullsensing protocols,thetokenismovedwhenthestationwithtokenpauses.Inadaptiveprotocols withjamming,thejammedroundsisperceivedassilenceandjustignored.Thisfacilitatestranslatingtheboundsforjammedchanneltothechannelwithoutjamming,forthe respectiveprotocols.Thefollowingresultsareobtainedbysuchtranslations. Corollary1 Thepacketlatencyofprotocol OF-RRW is O )]TJ/F49 8.9664 Tf 6.89 -4.98 Td [(n + b 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r whenexecutedagainst theadversaryoftype r ; b Proof: TheupperboundonpacketlatencygiveninTheorem3becomes O )]TJ/F49 8.9664 Tf 6.891 -4.98 Td [(n + b 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r for l = 0. Corollary2 Thepacketlatencyofprotocol RRW is O )]TJ/F49 8.9664 Tf 12.362 -4.979 Td [(n + b 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r 2 whenexecutedagainstthe adversaryoftype r ; b Proof: TheupperboundonpacketlatencygiveninTheorem4becomes O n + b = 1 )]TJ/F50 11.9552 Tf -418.211 -23.98 Td [(r 2 for l = 0. Theseboundsaretight.Theargumentfortightnessofboundsfortheprotocolswith jammingholdforthefullsensingprotocolswithoutjammingwhenthejammingrateis l = 0. 39

PAGE 48

6.1.1Fullsensingprotocolswithcollisiondetection WeconsiderpacketlatencyforprotocolsS EARCH -R OUND -R OBIN SRRandO LD F IRST -S EARCH -R OUND -R OBIN OF-SRRwhichusecollisiondetection.Webeginwith atechnicalestimatethatwillprovetobeusefulinprovingboundsonpacketlatency.Let log x denote d log 2 x e Lemma5 Iftherearex 1 packetsinthesysteminaroundthen,forany 1 y x, protocols SRR and OF-SRR makeypacketsheardinthenext min y log n ; 2 n + y rounds. Proof: Weestimateintwodifferentwayshowmuchtimeittakestoidentifystations with y oldpackets.Wepartitionanexecutionintoconsecutive epochs ,whereanepochis denedasaminimumperiodinwhichthelistofstationscycles.Notethatforprotocol OF-SRRanepochisthesameasaphase. Wearguerstthatanyoftheconsideredprotocolstakesnomorethan2 n + y consecutiveroundstotransmitsuccessfullyatleast y packets.Ittakesatmost n roundswith notransmissiontoidentifystationsthatstoreatleast y x packetsforSRR;tothisend, letthetokenmakeatmostonefullcyclealongthelistofstations.Similarly,ittakesat most2 n roundswithnotransmissiontoidentifystationsthatstoreatleast y x packets forOF-SRR.Thisisbecausetwocyclesareneededintheworstcase,asaftertherst cycleatleast y x packetsbecomeoldatthelatest,andthenextcyclewillreachstations storingthem.Havingshownthis,wecanseethatuploadingtheseatleast y packets,that areoldfortheOF-versionsoftheprotocols,takes y rounds.Thiscompletestherstpart oftheargument. Next,weprovethattheseprotocols,basedonbinarysearching,neednomorethan y log n consecutiveroundstouploadatleast y x packets.Indeed,afterapackethasbeen transmitted,ittakestimeatmosttheheightofaconceptualsearchtreetoidentifyanother stationwithapacket,thatisoldforOF-SRR.Thisheightisatmostlog n ,soapacketis heardatleastonceinanycontiguoussegmentoflog n rounds.Therefore, y packetsare transmittedwithinasegmentof y log n rounds. 40

PAGE 49

Theorem6 Thepacketlatencyforprotocol OF-SRR executedagainsttheadversaryof type r ; b isatmost 4min b log n ; n + b for r 1 = 2log n ,anditisatmost 4 n + 2 b 1 )]TJ/F50 8.9664 Tf 6.966 0 Td [(r for r > 1 = 2log n Proof: Apacketistransmittedsuccessfullybytheendofthephasefollowingtheonein whichitwasinjected.Sothemaximumpacketlatencyisupperboundedbytwicethe maximumlengthofaphase.Atmost r j t j + b packetsgetinjectedinatimeinterval t oflength j t j .Themaximumnumberofpacketsinthesystemisupperboundedbythe maximumnumberofpacketsattheendofanintervalplusthenumberofpacketsinjected withinthisinterval. Thecaseof r 1 = 2log n :Consideraround.Werstarguethatattheendof thisroundthereareatmost r min 2 b log n ; 2 n + 2 b + b packetsinthesystem.Suppose itisotherwiseandconsidertherstround t withthenumberofpacketsmorethan r min 2 b log n ; 2 n + 2 b + b attheendofit.Notethat t > min 2 b log n ; 2 n + 2 b ,asat most r min 2 b log n ; 2 n + 2 b + b packetsareinjectedintothesysteminthetimeinterval [ 1 ; min 2 b log n ; 2 n + 2 b ] .Thisfollowsfromtheassumptionthat,attheendofround t )]TJ/F18 11.9552 Tf 10.949 0 Td [(min 2 b log n ; 2 n + 2 b ,therewereatmost r min 2 b log n ; 2 n + 2 b + b packetsinthesystem.Fromthatrounduntilround t ,atleastthisnumberofpacketshave beensuccessfullytransmitted,byLemma5andtheestimate r min 2 b log n ; 2 n + 2 b + b 2 b log n 2log n + b = 2 b ; whileatmost r min 2 b log n ; 2 n + 2 b + b newpacketshavebeeninjected.Consequently,thenumberofpacketsinthesystemattheendofround t wouldbeatmost r min 2 b log n ; 2 n + 2 b + b ,whichisacontradiction.Thiscompletestheproofthatthe numberofpacketsinthesystemisatmost r min 2 b log n ; 2 n + 2 b + b .Thisboundis alsoatmost2 b .ByLemma5,aphasedoesnottakelongerthanmin 2 b log n ; 2 n + 2 b rounds,asthenumberofoldpacketsinthesystemneversurpasses2 b .Hence,thepacket latencyisatmost2 min 2 b log n ; 2 n + 2 b 4min b log n ; n + b 41

PAGE 50

Thecaseof r > 1 = 2log n :Partitionanexecutionintoconsecutivephases,asinthe specicationoftheprotocol.Let x i bethenumberofpacketsinthesysteminthebeginning ofphase i ,andlet t i bethelengthofthisphase.ByLemma5,theinequalities x 1 b and t i min x i log n ; 2 n + x i hold,forevery i 1.Therefore x i + 1 r t i + b r min x i log n ; 2 n + x i + b : Startiteratingthisformulatoobtain x i + 1 b + r min x i log n ; 2 n + x i b + r 2 n + b + r min x i )]TJ/F18 8.9664 Tf 6.967 0 Td [(1 log n ; 2 n + x i )]TJ/F18 8.9664 Tf 6.967 0 Td [(1 = b + r 2 n + b + r 2 min x i )]TJ/F18 8.9664 Tf 6.967 0 Td [(1 log n ; 2 n + x i )]TJ/F18 8.9664 Tf 6.966 0 Td [(1 ; whichcanbecontinuedtoobtain x i + 1 b + 2 n + b r + r 2 + ::: + r i )]TJ/F18 8.9664 Tf 6.967 0 Td [(1 r 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r 2 n + b r = 2 n r + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r : Thepacketlatencyisthemaximumof t i + t i + 1 ,overall i .ByLemma5,thesenumbersare atmost min x i log n ; 2 n + x i + min x i + 1 log n ; 2 n + x i + 1 : Eachofthemisupper-boundedby 4 n + 2 2 n r + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r 4 n + 2 b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r ; whichcompletestheproof. Theorem7 Thepacketlatencyofprotocol SRR executedagainsttheadversaryoftype r ; b isatmost 6 b log nfor r 1 2log n ,andatmost 4 n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r 2 for r > 1 2log n Proof: Wepartitionanexecutionintoconsecutive epochs ,eachbeingafullsweepofa searchforpacketsacrossallthestations.Let x i bethenumberofpacketsinthesystemin thebeginningofepoch i ,andlet t i bethelengthofthisepoch. 42

PAGE 51

Werstconsiderthecaseof r 1 2log n .Byasimilarargumentasintheproofof Theorem6,thenumberofpendingpacketsisnevermorethan r min 2 b log n ; 2 n + 2 b + b 2 b : ThisargumentreliesonlyonLemma5.Next,observethat t i x i + r t i + b t i = log n : Thisisbecausethenumberofallpacketsinthesysteminepoch i multipliedbythemaximumtimelog n ofavoidperiodinepoch i isanupperboundon t i .Thereareatmost r t i + b newlyarrivedpacketsinthisepoch.Combinethiswiththeestimate t i 2log n r t i to obtain x i + b log n t i .Byanupperbound2 b onthenumberofpacketsinthesystem, inthecaseof r 1 2log n ,weobtain t i x i + b log n 3 b log n Everypacketarrivinginepoch i istransmittedbytheendofepoch i + 1.Hencethe maximumpacketlatencyisatmost max i t i + t i + 1 2 3 b log n 6 b log n : Inordertoestimatepacketlatencyinthecaseof r > 1 = 2log n ,observethat t i x i + r t i + b t i )]TJ/F49 11.9552 Tf 11.498 0 Td [(n .Thisisbecausethenumberofallpacketsthatareinthesystemin epoch i plusthemaximumtotalnumber n ofvoidroundsinepoch i isanupperboundon t i Thereareatmost r t i + b newlyarrivedpacketsinthisepoch,so x i + n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r t i .Lemma5 forprotocolSRRimpliesthat 2 r n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r isanupperboundonthenumberofpacketsinthe systeminaround.Itfollowsthat t i x i + n + b 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r n 1 + r + b 2 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r 2 : Apacketarrivinginepoch i istransmittedbytheendofepoch i + 1,hencethemaximum packetlatencyisupperboundedby max i t i + t i + 1 2 n 1 + r + b 2 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r 1 )]TJ/F50 11.9552 Tf 10.95 0 Td [(r 2 4 n + b 1 )]TJ/F50 11.9552 Tf 10.949 0 Td [(r 2 ; whichcompletestheproof. 43

PAGE 52

6.1.2Adaptiveprotocol WeconsiderpacketlatencyofprotocolM OVE -B IG -T O -F RONT MBTF,whichis anadaptiveprotocolforchannelswithoutcollisiondetection.Thisprotocolwasoriginally designedforchannelswithoutjamming,butusingcontrolbitsinmessageswithoutpackets allowstotransferthetokenwithoutunnecessarydelayevenwhenachannelissubjectto jamming.Wemayconsideranyofthesetwoversionsoftheprotocolwhenthereisno jamminginachannel.Atranslationoftheboundonpacketlatencyappliesthatissimilar tothecaseoffullsensingprotocolsforchannelswithoutcollisiondetection. Corollary3 Thereareatmost 2 r n n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r + O bn packetsinqueuesinanyroundwhen protocol MBTF isexecutedagainsttheadversaryoftype r ; b Proof: FollowsfromLemma3when l = 0. Corollary4 Thepacketlatencyofprotocol MBTF is O )]TJ/F49 8.9664 Tf 6.671 -3.742 Td [(n n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r whenexecutedagainst theadversaryoftype r ; b Proof: TheboundonpacketlatencygiveninTheorem5becomes O )]TJ/F49 8.9664 Tf 6.671 -3.743 Td [(n n + b 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r for l = 0. 6.2Conclusion Weconsidereddeterministicprotocolsforchannelswithoutjammingandleaky bucketadversariesoftype r ; b ,for r < 1.Theresultsshowthatboundedpacketlatency canbeachievedbyfullsensingprotocolswithoutknowingthetypesoftheadversary. Thisisincontrasttothechannelswithjamming,wherejammingburstinesswaspartof thecode.Theresultsfortheprotocolsinchannelswithjamming,thatusetokentraversal translatenicelywhenjammingrateis0,totheonesinchannelswithoutjamming.We introducedan'old-rst'versionofprotocolthatusesbinarysearchwhencollisiondetectionisavailable.Theresultsonpacketlatencyagainindicatethebenetoftheparadigm 'old-rst'inthedesignofprotocols. 44

PAGE 53

7.Individualinjectionrates Weconsideradversarieswithindividualstations'rates;inthismodeltheadversary's injectionrateisconstrainedforeachstationseparately.Forrecentworkonadversarial queuingformultipleaccesschannels,see[11,30,31],concernedadversariesconstrained by`global'injectionrates,inthesensethattheadversaryisrestrictedbythenumber ofpacketsinjectedintoallstationsbutnotbyhowmanypacketsareinjectedintoany specicstation.Anadversarywithinjectionratesassociatedwithindividualstationsis morerestrictedthanonewitha`global'injectionrate.Onemayobservethattheglobal injectionrateofonepacketperroundisthemaximumratethatallowsforastableprotocol. Weunderstandthethroughputofaprotocolasthemaximumglobalrateforwhichitis stable,whichcanbelessthan1. Inthecontextofadversarialqueuinginstore-and-forwardnetworks,`globallyconstrained'windowadversarieswererstusedbyBorodinetal.[26]andsimilarleakybucketonesbyAndrewsetal.[14].Forthemultipleaccesschannel,Chlebusetal.[31] usedwindowadversarieswithinjectionrateslessthan1,whichdoesnotrestrictthegeneralityofresultsforsuchrates.Chlebusetal.[30]usedbothmodelsfor`global'injection rate1;forsuch`global'ratethewindowadversarialmodelisstrictlyweakerthanthe leaky-bucketone[30,60]. Weconsiderconstraintsonadversariesformulatedasrestrictionsonwhatcanbeinjectedseparatelyateachstationandalsobywhatcanbeinjectedintoallthestations combined.Constraintsare global iftheyaredeterminedonlybythenumbersofpackets injectedpertimeintervals,withoutanyconcernaboutthestationsinwhichthepackets areinjected.Trafcconstraintsare local whenthepatternsofinjectionareconsidered separatelyandindependentlyforeachstation.Constraintsforthewholenetworkimplied bylocalonesarecalled aggregate inthispaper.Inparticular,wemayhavelocaland aggregateandglobalburstiness,andlocalandaggregateandglobalinjectionrates.Observethatglobalconstraintsarelogicallyweakerthanaggregateconstraints.Globaland aggregateinjectionrate1isthemaximumthatachannelcanhandleinastableway,since 45

PAGE 54

stabilityprovidesthatthethroughputrateisatleastaslargeastheinjectionrate.Werefer toadversariesdenedonlybyglobalrestrictionsoninjectionratesasthemodelof global injectionrate ,theseadversarieswereusedin[30,31]inthecontextofmultipleaccess channels.Inthispaperweintroduceadversariesoflocalinjectionrates. Tocategorizeprotocols,weusetheterminologysimilartothatin[31,30].General protocolsarecalledfullsensing.Protocolsmayusecontrolbitspiggybackedontransmittedpackets;suchprotocolsarecalledadaptive. 7.1Results Westudytheworst-caseperformanceofbroadcastingwhentrafcdemandsarespeciedasadversarialenvironmentsmodeledbyadversarieswithindividualinjectionrates associatedwithstationsandwhenprotocolsarebothdistributedanddeterministic.We allowtheadversariestobesuchthattheassociatedaggregateinjectionratethesumofall theindividualratesis1,whichisthemaximumthatallowsforstability.Thegoalisto explorewhatqualityofservicecanbeachievedforindividualinjectionratesandcompare theadversarialenvironmentsdenedbyindividualratesversusglobalones,undermaximumbroadcastloadsofonepacketperround.Theunderlyingmotivationforthiswork wasthatindividualinjectionratesaremorerealisticinmoderatetimespansandhopefullythelimitationsonqualityofservicewiththroughput1discoveredin[30]couldbe improvedwhentheratesareindividual.Indeed,boundedpacketlatencyturnsouttobe achievablewithindividualinjectionrateswhentheaggregaterateis1.Thisisincontrast withglobalinjectionratesforwhichachievingboundedwaitingtimesisimpossiblefor throughput1,aswasshownin[30]. Weshowupperandlowerboundsonqueuesizeandpacketlatency,whichdepend ontheclassesofprotocolsandwhethercollisiondetectionisavailableornot.Wehave thefollowingresultsforawindow-typeadversary.Theacknowledgmentbasedprotocols cannotachievethroughput1,whichstrengthenstheresultforglobalinjectionrates[30]. Wegiveanon-adaptivefullsensingprotocolof O min n + w ; w log n packetlatency whencollisiondetectionisavailable.Anadaptivefullsensingprotocolcanachievesimilar 46

PAGE 55

performancewithoutcollisiondetection,asweshowthatcontrolbitsallowtosimulate collisiondetectionwithaconstantoverheadperround.Boundedpacketlatencycanalso beachievedbynon-adaptivefullsensingprotocolsinchannelswithoutcollisiondetection. Moreprecisely,wedevelopanon-adaptivefullsensingprotocolwith O n + w sizequeues and O nw packetlatency.Theoptimalityofournon-adaptivefullsensingprotocolfor channelswithoutcollisiondetectionintermsofpacketlatencyisleftopen. 7.2Preliminaries Thespecicationsofthechannelsandclassesofprotocolsremainsameasbefore. Nextweexplainconstrainingtheadversarywithindividualinjectionratesatstations. Adversarieswithindividualinjectionrates: An adversary isdenedbyasetofallowablepatternsofinjectionsofpacketsintostations.Anadversarygeneratesanumber ofpacketsineachroundandassignstoeachpacketthestationintowhichthepacketis injected. Werstreviewthetraditionalgloballyrestrictedadversaries.Globalconstraintson packetinjectionareusuallymodeledbyeitherwindoworleaky-bucketadversarialmodels. Awindow-typeadversarythatisrestrictedbyaninjectionrate r andawindowsize w .The windowsize w isusedtodenetheinjectionrate r asfollows:foranycontiguoustime interval t of w roundsthenumberofpacketsinjectedin t isatmost r w .Aleaky-bucket typeofanadversaryisrestrictedbyaninjectionrate r andaburstiness b .Themeaningof theseparametersissuchthattheadversarymayinsertatmost j t j r + b packetsduringany timeinterval t .Werestrictsuchconstraintsfurtherbyspecifyinghowpacketsareinjected intoeachstationseparately;inthisweconsideronlywindowadversaries. Windowadversarieswithindividualinjectionrates aredenedasfollows:Letthere begivenapositiveintegernumber w called windowsize .Eachstation i hasits shares i whichisanon-negativeinteger.Thesharessatisfytherequirement n i = 1 s i w .The adversarymayinsertupto s i packetsintostation i inatimeintervalof w contiguous rounds.The localinjectionrate ofstation i isdenedtobethenumber r i = s i = w .The aggregateinjectionrate isdenedtodenotethenumber r = n i = 1 s i = w .Werefertosuch 47

PAGE 56

awindowadversaryasbeingof localtype h s i i 1 i n ; w andof aggregatetype r ; w Thenotionofaggregatetypeissimilartothatofglobaltypeasconsideredin[30,31]. Forawindowadversaryofalocaltype h s i i 1 i n ; w withtheaggregaterate r ,the local burstinessatstationi isdenedtobeitsshare s i andthe aggregateburstiness isdened tobethenumber d = n i = 1 s i ,sothat r = d = w Protocoldesign: Nowwegiveanoverviewofdesignprinciplesofourprotocols.It isanaturalapproachtohavestationsworktodiscovertheparametersdeningtheadversaryathand.Thestationscouldgraduallyimprovetheirestimatesoftheshares s i and theaggregatemaximumburstiness d = n i = 1 s i .Thestationswouldadjustthenumberof theirindividualtransmissionstotheknowledgegainedintheprocessofdiscoveryofthe adversary.Theminimum-sizewindowofanadversaryisdeterminedbytheaggregate burstiness.Observethattheaggregateburstiness d inthecaseofinjectionrate1equals theminimumwindowsizefortheadversaryathand. Foragivenwindowadversaryoflocalinjectionrates,station i is active whenits share s i isapositivenumber,otherwise,when s i = 0,thestation i is passive .Station i hasbeen discovered inthecourseofanexecutionwhenapackettransmittedby i hasbeen heardonthechannel.Adiscoveredstationisclearlyactive.Inthecontextofaspecic execution,astationthathasnotbeendiscoveredbyagivenroundiscalleda candidate inthisround.Apassivestationisdoomedtobecandidateforever.Wedescribetwodata structuresusedwhenstationsworktodiscovertheirshares. Inoneapproach,eachstation i hasaprivatearray C i of n entries.Theentry C i [ j ] storesanestimateoftheshare s j ofstation j ,for1 j n .Everystation i willmodify theentry C i [ k ] inaroundinthesamewayasotherstationsdo.Thereforewemaydrop theindicesandrefertotheentriesofthearraysas C [ j ] ratherthanas C i [ j ] .Thearray C isinitializedto C [ j ]= 0forevery1 j n .Thesum g = n i = 1 C [ i ] isanestimateofthe aggregateburstiness d = n i = 1 s i Thestationsrunningaprotocolkeepadjustingtheestimatesstoredinthearray C Whenstation i entersastateimplying s i > C [ i ] then i considersitself underestimated 48

PAGE 57

Detectingunderestimationisimplementedbyhavingeverystationkeeptrackofthetransmissionsinthepast g rounds.Whenastation i detectsthatsome k > C [ i ] packetshave beeninjectedwithintherespective g consecutiverounds,where k ismaximumwiththis propertysofar,then i decidesitis underestimatedbytheamountk )]TJ/F49 11.9552 Tf 10.66 0 Td [(C [ i ] inthisround. Thisconservativemechanismofestimatingthesharesissafe,inthatthesharesarenever overestimated,asweshownext. Lemma6 IfaprotocolagainstawindowadversaryhasthepropertythatC [ i ] isincreased atmostbytheamountthatstationiconsiderstobeunderestimatedby,thentheinequality C [ i ] s i holdsatalltimes,forevery 1 i n. Proof: Weshowthattheinvariant`theinequality C [ i ] s i holdsforevery1 i n 'is preservedthroughouttheexecution.Initially C [ i ]= 0 s i forevery1 i n ,sothe invariantholdstrueintherstround.Observethatiftheinequalities C [ i ] s i holdfor every1 i n ,thenalsotheinequalities g = n i = 1 C [ i ] n i = 1 s i = d w holdtrue.Theadversarycaninject atmosts k packetsintoastation k duringanysegment of g contiguousrounds,astheinequality g w meansthatanysegmentof g contiguous roundscouldbeextendedtooneof w roundsoftheexecution.Astation k candetectto beunderestimatedbyatmost s k )]TJ/F49 11.9552 Tf 10.19 0 Td [(C [ k ] inanyroundwhiletheinvariantholds.Thismakes theinvariantstillholdinthenextround,becauseanupdateof C [ k ] raises C [ k ] toavalue thatisatmost s k Anotherapproachtoprotocoldesignistohaveeachstation i usealist D i ofbits.Such alist D i hasitstermslistedasfollows h d i 1 ; d i 2 ;:::; d i ` i ,wherethelength ` maybe modiedbyitisthesameatallstations,andadditionallytheinequality ` w holdsatall times.Thelistsareinitializedtobeempty.Thelistsaremaintainedsoastosatisfythe followinginvariants: foreach1 j ` ,when d i j hasbeendeterminedforall i ,then d i j = 1for 49

PAGE 58

preciselyone i ,and d k j = 0foranyothervalue k 6 = i suchthat1 k n ; thenumberofoccurrencesof1at D i hasthesamemeaningas C [ i ] anddenotesthe currentestimateoftheshareof i Thenumber ` willbeanestimateontheburstinessoftheadversary,similarlyasthe number g isforthearray C .Whenlists D areonlyusedandarrays C arenotexplicitly maintained,then C [ i ] willdenotethenumberofoccurrencesof1in D i .Wewilluse ` and g interchangeablywhenlists D i areused.Ifaprotocolhasthepropertythat C [ i ] isincreased atmostbytheamountthatstation i considerstobeunderestimatedby,thentheinequality C [ i ] s i holdsatalltimes,forevery1 i n .Ourprotocolswillhavethepropertythat theassumptionsofLemma6holdtrue,andforthemtheinequality g d holds. Weusearrays C wheneachstationknowsofthestationforwhichupdateofanestimateofitsshareistobeperformed.Itmayhappenthatsuchknowledgeislacking:an underestimatedstationtransmitssuccessfullybuttheotherstationsdonotknowwhich stationtransmitted.Thisisascenarioinwhichtouselists D ,asatransmittingstationcan append1attheendof D whileeveryotherstationappends0. Ourprotocolshavestationsmanipulateauxiliarylists.Wheneverweusesuchlists, thereisa mainpointer associatedwitheachlistpointingata current entry.Themain pointereitherstaysputinaroundoritisadvancedbyonepositionintheroundinthe cyclicorderingoftheentriesonthelist. 7.3Impossibilitiesandlowerbounds Inthissection,wepresentimpossibilityresultsforacknowledgment-basedprotocols andlowerboundsonpacketlatency. 7.3.1Impossibilityresultsforacknowledgmentbasedprotocols Webeginbyexaminingacknowledgment-basedprotocols.Theactionthatastation performswhenitbeginsprocessinganewpacketisalwaysthesame,asitisdeterminedby theinitialstate.Suchanactionmaybeeither`totransmit'or`topause'intherstround. 50

PAGE 59

Lemma7 Consideranacknowledgment-basedprotocolexecutedbyasetofstations.If thereisastationwhichpausesintherstroundafterstartingtoprocessanewpacketthen, foranynumber r > 1 2 ,theprotocolisunstableforsomeadversarywiththeaggregaterate equalto r Proof: Supposethatsomestation p pausesintherstroundofprocessinganewpacket. Consideranadversaryinjectsonlyintosuchastation p asoftenaspossiblesubjecttoan individualinjectionratethatisbetween 1 2 and r .Thisresultsinanexecutioninwhicha packetisheardnotmoreoftenthaneverysecondround,whileinaggregaterateisgreater than 1 2 ,sothequeueat p growsunbounded. Theorem8 Anyacknowledgment-basedprotocolisunstableinasystemofjusttwostationsandamultiple-accesschannelwithcollisiondetectionagainstsomewindowadversaryofburstiness2andaggregateinjectionrate 1 Proof: Denearoundtobe void whennopacketisheardintheround.Consideran acknowledgment-basedprotocolfortwostations p and q .Suppose,toarriveatacontradiction,thattheprotocolisstablefortheaggregateinjectionrate1.Thisimplies,by Lemma7,thatastationtransmitsanewpacketimmediately. Wedeneanexecutionoftheprotocolwithaninnitesequenceofrounds t 1 ; t 2 ;::: determinedsothatthereareatleast i voidroundsbyround t i .Theadversarywillinject twopacketsineachodd-numberedround,apacketperstation,andnopacketsinevennumberedrounds.Thismeansthateachstationhasitsindividualinjectionrateequalto 1 2 Theaggregateinjectionrateoftheadversaryis1,andsothereareatleast i packetsin queuesinround t i Dene t 1 tobetherstround.Thisroundissilentasstationsdidnothaveanypackets priortothisround.Acollisionoccursinthesecondround:eachstationgotanewpacket intherstround,soittransmitsitimmediately.Dene t 2 tobethesecondround.Each oftheroundnumbers t i willevenfor i > 1.Theadversarywillnotinjectpacketsinthese specicrounds t i ,aspacketswillnotbeinjectedinanyeven-numberedround. 51

PAGE 60

Supposetheexecutionhasbeendeterminedthroughaneven-numberedround t i .If t i + 1isvoidthendene t i + 1 = t i + 2.Otherwise,somestation,say p ,transmitsinround t i + 1. Thestation p willcontinuetransmittingforaslongasithaspackets,becauseittransmits anewpacketimmediately.Ifinonesucharound t thestation q transmitsconcurrently with p ,thenthisresultsinacollisionandwedene t i + 1 tobe t if t isevenor t + 1 otherwise.Supposethisisnotthecase,so p keepstransmittingalone.Thestation p will nothaveapackettotransmitinsomeroundafter t i + 1,sinceitsinjectionrateis 1 2 ;let t 0 > t i + 1betherstsucharound.Observethat t 0 hastobeanoddnumber,asotherwise anewpacketwouldhavegotinjectedinto p inround t 0 )]TJ/F18 11.9552 Tf 11.137 0 Td [(1so p wouldhaveapacketto transmitinround t 0 .If q doesnottransmitinround t 0 ,thenthisround t 0 issilentandwe aredone;inthiscasedene t i + 1 tobe t 0 + 1,asaroundnumberistobeeven.Otherwise, thestation q transmitsinround t 0 successfully.Simultaneouslybothstationsobtainnew packetsinround t 0 ,soeachhasatleastoneavailablepacketattheendofthisround.Each stationtransmitsinround t 0 + 1,asforeachofthemitisarstroundofprocessinganew packet.Thisisbecause p didnothaveapacketinround t 0 and q transmittedinround t 0 Dene t i + 1 tobethevoidround t 0 + 1.Thiscompletestheinductiveconstructionofthe sequence t i andbythisproducesacontradictionwiththeassumptionthattheprotocolis stable. Nextweinvestigatehowlargecouldinjectionratebe,asafunctionofthenumberofstation,whatcanbehandledinastablemannerbythestationsexecutingan acknowledgment-basedprotocol.ItwasshownbyChlebusetal.[31]theorem5.1that anobliviousacknowledgment-basedprotocolcannotbestablewhentheglobalinjection rateisatleastaslargeas 3 1 + lg n ,for n 4stations.Weshowaresultforindividualinjectionratesandnotnecessarilyobliviousacknowledgment-basedprotocols.Thefollowing theoremwasinspiredbytherelatedresultin[31];theproofissimilartothatgivenin[31]. Theorem9 Ifanacknowledgment-basedprotocolisexecutedbyn 4 stationsona multiple-accesschannelwithcollisiondetectionagainstadversarieswhosewindowsizew 52

PAGE 61

canbeassmallas 1 + d lg n e ,thenthesystemisunstableagainstanadversaryforwhich onlytwostationshavepositiveshares,onesuchshareequalto 1 andtheotherto 2 Proof: Let A beaspecicacknowledgment-basedprotocolforthe n stationsavailable. Foreachstation p ,consideranexecutionofprotocol A when p startstoworkonanew packetandtheexecutionissuchthateachtime p transmitsthen p hearscollisionandwhen p doesnottransmitthentheroundissilent.Suchanexecutiondeterminesasequenceof bits s p = b 1 ; b 2 ;::: suchthat b i = 1when p transmitsinthe i throundand b i = 0when p pausesinthe i thround,countingroundsfromtherstoneofworkingonthepacket.Let s p ; i bethissequencetruncatedtotherst i terms,for i 1.Thereexisttwostations, p 1 and p 2 ,forwhich s p 1 ; d lg n e)]TJ/F18 11.9552 Tf 17.296 0 Td [(1 = s p 2 ; d lg n e)]TJ/F18 11.9552 Tf 17.296 0 Td [(1 bythepigeonholeprinciple,because d lg n e)]TJ/F18 11.9552 Tf 17.918 0 Td [(1 1for n 4and2 d lg n e)]TJ/F18 8.9664 Tf 10.947 0 Td [(1 = 2 d lg n e = 2 < n Let k d lg n e betherstpositioninwhichthesequences s p 1 and s p 2 differ. Withoutlossofgenerality,supposethatthe k thtermof s p 1 is1andthecorresponding termof s p 2 is0.Let j bethesmallestpositionofthesequence s p 2 suchthat j > k and thereis1atthispositionin s p 2 .Wedetermineanadversaryasfollows.Thewindow size w = j andstation p 1 hasshare1andstation p 2 hasshare2,whichispossiblefor n 4 becausethen j 3. Thisadversarymayinjectthepacketsasfollows.Attheroundnumber0,theadversaryinjectsthenumberofpacketsequaltoeachstationsshareintothisstation.Thisis followedby w roundssothattwopacketsaresuccessfullytransmitted,oneatround k by station p 1 andtheotherinround w = j bystation p 2 ,whilestation p 2 stillhasonepacket. Attheround w = j ,theadversaryinjectsthenumberofpacketsequaltoeachstations shareintothisstation.Thismakesthebehaviorofthechannelduringtherounds w + 1 through2 w bethesameasduringtheroundsfrom1through w ,withtheonlydifference thatattheround2 w thestation p 2 hastwopacketspendingtransmissions.Thispatterncan beiteratedforeverwiththeresultthatattheroundnumber ` w thestation p 2 has ` pending packets. 53

PAGE 62

7.3.2Lowerbounds Nextwepresenttwolowerboundsonpacketlatency.Webeginbyshowingthataprotocolwithperformanceclosetooptimalneedstohavebounds W n + w or W )]TJ/F49 11.9552 Tf 5.475 -9.69 Td [(w polylog n onpacketlatency. Theorem10 Foranyprotocolforasystemofnstationsforanadversaryofwindoww, thepacketlatencyis W )]TJ/F49 11.9552 Tf 5.476 -9.689 Td [(w log n log w whenw nanditis W w whenw > n,insomeexecution oftheprotocol. Proof: For w n weconsideradversariesforwhicheachstationhasshareeither0or 1.GreenbergandWinograd[40]consideredastaticversionofthebroadcastproblem, inwhichsome k packetsarelocatedinitiallyamong k n stations,atmostapacketper station,andthegoalistohaveallofthemheardonthechannel.Theyshowedthatfor anyprotocolittakes W )]TJ/F49 11.9552 Tf 5.475 -9.689 Td [(k log n log k timetoachievethisgoalinsomeexecutionoftheprotocol. Protocolsthatweusehandledynamicbroadcast,butcanbeappliedtothestaticversion. Atranslationtothestaticversionofbroadcastisasfollows:lettheadversaryinject w packetsintherstround,atmostonepacketperstation. When w > n ,thentheadversarymayinject w packetsintherstroundandittakes W w + n = W w roundstohearthemall. Thenextobservationisthatapossibilityofconictforaccesstooccurinanexecution isanecessaryintrinsicpropertyofaprotocoltoachievelatencyasymptoticallybetter than wn Theorem11 Foranyconictfreeprotocolfornstations,thereisanexecutioninwhich apacketisdelayedby W nw roundsagainstawindowadversarywithw = Q n andan aggregateinjectionratelessthan 1 Proof: Let n = k + 3forapositiveinteger k .Lettherebeanarbitraryconict-freeprotocol for n stations.Wewillconsideranadversarywith w = n )]TJ/F18 11.9552 Tf 11.023 0 Td [(1,andsometimesdenote w as w = k + 2.Letusdeclareonestationtobe heavy andtheremainingonestobe mavericks Theshareoftheheavystationis k ,andoneofthemaverickshasitsshareequalto1.This 54

PAGE 63

meanstheaggregateinjectionrateis k + 1 = k + 2 < 1.Letuspartitionanyexecution intodisjointsegmentsofconsecutive k + 1 k + 2 rounds. Consideranexecution E 1 inwhichtheadversaryinjectsonlyintotheheavystation withfullcapacityof k packetsper k + 2 = w consecutiverounds.Theadversaryinjects k k + 2 packetsintotheheavystationduringeachsegment.Thisleavesaroomfor k + 2`exploratory'roundsduringasegmentof E 1 ,availabletolocatethemaverickwitha positiveshare.Theideaisthataprotocolcannotlocatesuchamaverickwithoutincurring a W n 2 delay.Wespecifyanexecution E 2 whichhasthesameprexas E 1 untiltherst injectionintoamaverick. Supposethereisasegment S of E 1 inwhichlessthan k + 2mavericksarescheduled totransmit.Takeanexecution E 2 inwhichtheadversaryinjectsintoamaverickthatis notscheduledtotransmitin S intheroundjustbefore S istobegin.Thispacketwaits k + 1 k + 2 rounds.Otherwise,supposeeverymaverickisscheduledtotransmitatleast onceduringeverysegmentof E 1 .Ifsomemaverickisscheduledtotransmitmorethan once,thenthenumberofpacketsintheheavystationincreasesduringthissegment.Ifonly suchsegmentsarein E 1 thentheprotocolisnotstableandpacketdelaysarearbitrarily large.Otherwisethereisasegment S duringwhicheachmaverickisscheduledtotransmit exactlyonce.Partition S intorstandsecondhalves,eachof k + 1 k + 2 = 2rounds.If thelastmaverickistotransmitinthersthalf,thenconsider E 2 inwhichtheadversary injectsintothislastmaverickjustafteritsscheduledtransmissionin S .Ifthelastmaverick istotransmitinthesecondhalf,thenconsider E 2 inwhichtheadversaryinjectsintothis lastmaverickjustbefore S istobegin.Ineachofthesetwocases,thepacketinjectedinto thelastmaverickwillwaitforatleast k + 1 k + 2 = 2rounds. 7.4Twoprotocolsofsmalllatency Inthissectionwepresentprotocolswiththepacketlatencythatisclosetooptimal. Theyaredevelopedforthetwoscenarioswheneithercollisiondetectionisavailable orcontrolbitscanbesentinmessages. 7.4.1Afullsensingprotocolwithcollisiondetection 55

PAGE 64

Wedevelopanon-adaptivefull-sensingprotocolU PGRADE -C OLLISION whichuses collisiondetectiontoprovidesmalllatency.ProtocolU PGRADE -C OLLISION inturn usestwoprotocolsB INARY -S EARCH -C OLLISION andC YCLIC -U PDATE -C OLLISION executedinsequence.ProtocolB INARY -S EARCH -C OLLISION isexecutedrstandwe switchtoC YCLIC -U PDATE -C OLLISION providedthatsufcientlymanycollisionsoccur inanexecutionoftheformer. Astation i usesalist D i ofbitstoimplementitsestimateofshares.Eachsuchalist D i isinitiallyempty.Astation i thatupgradesitsshareappendsa1totheendofitslist D i whileatthesametimealltheotherstationsappend0'stotheirlists.Thelists D i areused tostructuretransmissionsasfollows:thestationwhosecurrententryin D i is1transmits, whiletheotherstationspause. ProtocolB INARY -S EARCH -C OLLISION : Nowweexplainindetailhowprotocol B INARY -S EARCH -C OLLISION works.Theprotocolrunsamainthreadthatusesthelists D i withthepointersadvancedcyclically.Anyunderestimatedstationbecomes persistent inthesensethatitkeepstransmittingaslongasithaspacketswiththeonlyexception whenbeingscheduledtotransmitinthemainthread.Thiscontinuesaslongassilence orapacketareheard.Ifacollisionoccursthenthemainthreadpausesforadurationof binary-searchthreadandresumesonlyafterthebinary-searchthreadterminates;inparticular,themainpointersassociatedwiththelists D i arenotadvancedwhilethemainthread pauses.Thebinary-searchthreadperformsasearchovertherangeofallthestationsusing intervalsofnamesofstations,startingwiththeintervalof [ 1 ; n ] comprisingallthenames. Ateachsteponlystationsinthecurrentintervalthatwanttoupgradetheirsharestransmit. Ifacollisionisheardthentheintervalispartitionedandprocessedrecursivelyusinga stack.Theleftintervalispursuedrstwhiletherightintervalispushedonthestack.If asilenceisheardforthecurrentintervalthensuchanintervalisabandonedandthenext intervalispoppedfromthestackandprocessed.Ifapacketisheardthenastationthat transmittedthepacketwithholdsthechannelandtransmitsanumberofpacketsuptoits share'supgradefollowedbysilence.Suchastationappendsa1toitslist D i foreach 56

PAGE 65

transmissionofapacketisthissituation,whiletheotherstationsappend0'seach.The binary-searchthreadterminatesafterthestackbecomesempty.Themainthreadresumes afterthis. Lemma8 Packetlatencyof B INARY -S EARCH -C OLLISION isatmost O w log n whenit isexecutedagainstanadversaryofwindowwinasystemofnstations. Proof: Packetdelaymaybecausedbyeithertheburstinessorthetimespenttoupgrade theshares.Theformercontributesatmost w tothedelay.Thelattercontributesatmost 1 + lg n pereachupgrade,wherelg n isthebinarylogarithmof n ,andthesevoidrounds foreachshareupgradeoccuronlyonce.Asthereareatmost w upgrades,thetotalpacket delayisatmost w 2 + lg n ProtocolC YCLIC -U PDATE -C OLLISION : Nowweexplainindetailhowprotocol C YCLIC -U PDATE -C OLLISION operates.Itcontainstwothreads:the main threadandthe update one.Boththethreadsworksimultaneouslyunlesspausedforupgradingshares. Themainthreadusesthelists D .Astation i thathasa1asacurrententryinitslist D i in aroundtransmitsifithasapacket.Theupdatethreadworksbyusingacycliclistofthe namesofallthestationswithamainpointerassociatedwithit.Astationthatiscurrenton thislistisreferredtoascurrentinthethread.Suchastationtransmitsonlyifitndsitself underestimatedandhasapackettodoso.Ifsuchapacketinupdatethreadisheardthen thestationturns persistent inthesensethatitkeepstransmittingapacketineveryround. Astationthatispersistentturnsbacktonon-persistentifitsqueuebecomesemptyorif thereisacollisionorifitbecomescurrentagainintheupdatethread.Noticethatthereis onlyonepersistentstationatanytime.Ifacollisionisheardthenboththemainandupdatethreadspausetoupgradeshares.Nowthecurrentstationintheupdatethreadisgiven achancetotransmit.Ifitwantstoupgradeitssharethenittransmitsanumberoftimes uptoitsshare'supgradefollowedbysilence.Thisisperformedtogetherwithappending 1'stothelist D i ofthetransmittingstationand0'stosuchlistsoftheotherstations,an 57

PAGE 66

entryforeachtransmissionofapacket.Afterasilentroundanypersistentstationisgiven achancetoupgradeitsshare.Ifsuchastationexiststhenitupgradesuptoitsnewshare followedbyasilentround.Again,thisisdonealongwithappendingtherespectivebinary digitstothelists D .Boththemainthreadandupdateoneresumeaftertwosilentrounds. Lemma9 Packetlatencyof C YCLIC -U PDATE -C OLLISION isatmostq + 4 wwhenthe protocolisexecutedagainstanadversaryofwindowwinasystemofnstationswithan initialqueueofsizeq. Proof: Packetdelaymaybeattributedeithertothenumberofpacketsinheritedinthe queueortotheburstinessortotimespenttoupgradetheshares.Thequeuecontributes q andburstinesscontributesatmost w .Anupdatecostsatmostthreevoidrounds,asthey compriseonecollisionandtwosilences.Thesevoidroundsforeachshare'supgrade happenonlyonce.Asthereareatmost w upgrades,thetotalpacketdelayisasclaimed. TheultimateprotocolU PGRADE -C OLLISION : ProtocolU PGRADE -C OLLISION starts byinvokingprotocolB INARY -S EARCH -C OLLISION .Acountofthetotalnumberofcollisionsheardismaintainedthroughoutanexecution.Ifthetotalcountofcollisionsreaches n thenprotocolB INARY -S EARCH -C OLLISION isswitchedoffandprotocolC YCLIC U PDATE -C OLLISION takesover. Theorem12 Protocol U PGRADE -C OLLISION provides O min n + w ; w log n packetlatencyforachannelwithcollisiondetectionagainsttheadversaryofwindowwinasystem ofnstations. Proof: IfprotocolC YCLIC -U PDATE -C OLLISION isnotinvoked,thenpacketlatencyis givenbyLemma8.WhenC YCLIC -U PDATE -C OLLISION isinvoked,thenthereare O n packetsinqueuesintheroundofinvocation.Then O n + w becomesaboundgivenby Lemma9,whichisanupperboundonpacketlatency. 58

PAGE 67

7.4.2Anadaptiveprotocolwithoutcollisiondetection NextweshowhowtosimulateprotocolU PGRADE -C OLLISION toobtainanadaptive full-sensingprotocolforchannelsinwhichcollisiondetectionisnotavailable.Wecall thesimulatingprotocolU PGRADE -S ILENCE assilencestriggerupgradesofshares.This protocolsimulatesthetwoprotocolsinU PGRADE -C OLLISION byrunningtwosimulating protocolsB INARY -S EARCH -S ILENCE andC YCLIC -U PDATE -S ILENCE ,respectively.The simulationproceedsasfollows. Regardingthemainthread,astationwithoutpacketsscheduledtotransmittransmits acontrolbittoindicatethis,ratherthanpauseandmaketheroundsilent.Soasilence occursonlywhenthemodiedprotocolcausescollision.Thebinary-searchthreadin B INARY -S EARCH -C OLLISION reliesoncollisiondetectionbutnowcollisionisheardas silence.Itispossiblethatthesilenceheardinround t duringthebinary-searchthread actuallyindicatesnotransmissionsorcollision.Weresolvewhetherthisisthecaseinthe next t + 1-stroundasfollows.Allthestationsthattransmittedinround t transmittogether withstation1,whenstation1simplytransmitsacontrolbit.Therearetwopossibleevents occurringinround t + 1:eithertheroundissilentoramessageisheard.Silenceindicates thatmorethanonestationtransmitted,asstation1certainlydidtransmit.Thismeansthat therewascollisioninround t .Ifamessageisheardinround t + 1thenthismeansthat round t wassilent,asstation1managedtohaveitstransmissioninround t + 1heard. ThesimulationofC YCLIC -U PDATE -S ILENCE proceedssimilarlyasofthemainthreadin B INARY -S EARCH -C OLLISION Theorem13 Protocol U PGRADE -S ILENCE provides O min n + w ; w log n packetlatencyforachannelwithoutcollisiondetectionagainstanadversaryofwindowwina systemofnstations. Proof: Thesimulationweemployresultsinaconstantoverheadpereachroundthat contributestopacketlatencyofthesimulatedprotocol.Thereforepacketlatencyisofthe orderofaboundforthesimulatedprotocol,whichisasinTheorem12. 59

PAGE 68

7.5Afullsensingprotocolwithoutcollisiondetection Inthissectionweconsiderthechannelwithoutcollisiondetection.Wedevelopanonadaptivefull-sensingprotocolofboundedpacketlatencyforinjectionrate1.Theprotocol iscalledC OLORFUL -S TATIONS .Theprotocolusesalistofdiscoveredstations,inaway similarasbefore,inthatanewlydiscoveredactivestationisimmediatelyappendedtothe list,andthereisapointerassociatedwiththelistthatisadvancedinacyclicmanner. Anexecutionoftheprotocolisstructuredtobeginwithastagewecallpreparation, whichisfollowedbyiteratedphases.A phase consistsofthreestagesorganizedasfollows.Apurestageoccursrst,itisfollowedbyanupdate,andnallyamakeupconcludes thephase.Itmayhappenthat,insomephase,theupdateandmakeupstagesaremissing, sothattheinitialpurestageofthephasecomprisestheremainingpartoftheexecution: thismayoccuronlywhenapacketisheardineveryroundstartingfromacertainpointin timeinthispurestage. Thefollowingaretheintuitionsthathaveguidedthedesignofstages.Thepurpose ofthepreparationstageismerelytodiscoveratleastoneactivestation;itisbecauseof thisgoalwhythisstageoccursonlyonce.Purestagesarefortransmissionsbystations alreadydiscovered.Theamountoftimeallottedforsuchtransmissionscorrespondtothe rateofeachstation,asestimatedsofar.Itisduringthesestagesthatmostofthework ofbroadcastingisexpectedtobeaccomplished.Anupdatestageservesthepurposeto givethestationsanopportunitytoannouncethatsomeamongthemareunderestimated. Suchannouncementsresultintherespectiveentriesofthearray C gettingincrementedin ordertoimprovetheestimatesoftheshares.Stationsthatarenotunderestimatedpause duringtheseroundsoftheupdate,sotheseroundscouldbeconsideredwastedforthese stations.Eventuallynostationcouldbeunderestimatedandsoupdates,ifany,would consistofsilentroundsonly.Thiscreatesapotentialforthequeuestogrowunboundedat stationsthatkeepobtainingtheirmaximumloadofpackets.Topreventinstability,wedo notrushintoanupdate.Wewaitpatientlyuntilthereare n silentroundsaccruedduring apurestage.Eachsuchasilentroundindicatesthatthecorrespondingstationhasno 60

PAGE 69

packets.When n silentroundshaveoccurred,thestationsareconceptuallypartitionedinto thosethathavebeendetectedtohavenopacketsduringthepurestageandtheremaining `busy'onesthathavenot.Thepurposeofamakeupstageistoallowthebusystationsto compensatefortheroundswastedduringtheforcedsilentroundsoftheprecedingupdate andsokeepqueuessuitablybounded. Duringapurestage,a token isgeneratedeachtimeasilentroundoccurs.Creating andmanipulatingtokensisaconceptualmethodtoassignextraroundsfortransmissions topotentiallyheavilyloadedstationsduringthefollowingmakeup.Theproblemweneed tohandleisthattheadversarymaystartneglectingsomestationswhileinjectingatfull capacityattheremainingones.Abusystation i thatisbeinginjectedatwiththeaverageof C [ i ]= s i packetsduring g consecutiveroundsneeds C [ i ] roundstotransmitover acontiguoussegmentof g roundsontheaverage,whichisprovidedbythedesignofa purestage.Here g denotesthecurrentestimateoftheaggregateburstiness,while d isthe trueaggregateburstinessasdeterminedbytheadversary'stype.Alas,silencesincurred bythestationsneglectedbytheadversarykeeptriggeringupdates.Thesestagesarethere becausewedonotknowifthesilencesmean d < w ,andsotheinjectionrateislessthan1, orratherthattheestimatesofthesharesinarray C arestillunderestimateswhiletheinjectionrateis1.Eachsuchapossibleupdateof n roundsisspentunproductivelyinthecase whennostationisactuallyunderestimated.Inparticular,nostationiseverunderestimated oncetheentriesofthearray C havetheirnalsteadyvaluesintheexecution. Tokenscomewithtwocolors:greenandred.Redtokensareusedtomarkthepotentiallyheavilyloadedstationstoallowthemnexttomakeupfortheroundslostonsilences. Greentokensaretoindicatethattheirholdershavemissedatransmission,whichindicates thatsuchstationshavealightload.Nextwedescribethefourkindsofstagesindetail. The preparation stageisorganizedsuchthateverystationhasoneroundtotransmit atatime,assignedinaroundrobinmanner.Astationwithapacketavailabletransmits onewhenthestation'sturncomesup,otherwisethestationpausesduringitstimeslot. Thepreparationterminateswhenthestationthattransmittedrstisscheduledtotransmit 61

PAGE 70

again.Eachstation i whosepacketshavebeenheardduringthepreparationbecomes discovered,whichisrecordedbysetting C [ i ] 1. Duringa pure stage,thediscoveredstationsproceedthroughasequenceoftransmissions,startingfromthecurrentstation.Astation i hasasegmentofconsecutive C [ i ] > 0 roundsallottedforexclusivetransmissions.Duringthissegmentofrounds,thestation i keepstransmittingaslongasithaspackets,otherwisethestation i pauses.Thepointer isadvanced,andthenextstationtakesover,wheneitherthecurrentstation i hasusedup thewholesegmentof C [ i ] assignedroundsorjustafterstation i didnottransmitwhile scheduledto. Nextweexplainhowtokensarecreatedandassignedtodiscoveredstationsduring apurestage.Everystationkeepsalistofthetokensandtheirassignmentsinitsprivate memoryandperformsoperationsontokensinexactlythesamewayasotherstations.All operationsontokensaretriggeredbysilences.Whenastation i holdsatoken,thenthe color green ofthetokenindicatesthatthetokenwasgeneratedwhen i wassilentduringa roundinasegmentof C [ i ] roundsallottedfor i totransmit.The red colorofatokenheld bystation i indicatesthatitwassomeotherstation j ,for i 6 = j ,thatwassilentduringa roundinasegmentof C [ j ] roundsallottedto j totransmitandwhichgeneratedthetoken. Adiscoveredstationmayholdeithernotokensoragreenoneoraredoneinaround.No stationholdsatokeninthebeginningofapurestage.Letastation i besilentinaround assignedto i totransmit,whichgeneratesatoken.If i doesnotholdatokenyet,thenthe newtokeniscoloredgreenanditisassignedto i .If i alreadyholdsagreentoken,thenthe newtokeniscoloredredanditisassignedtotherstavailablediscoveredstationthatdoes notholdatokenyet,intheorderoftheirnames.If i holdsaredtoken,thenthenewtoken iscoloredgreen,itisassignedto i ,whiletheoriginalredtokenheldby i isreassignedto adiscoveredstationthatdoesnotholdatoken,ifany.Adiscoveredstationisconsidered colored bythesamecolorasthetokenitholdswhenanupdatebegins.Weneedtokens onlytoassigncolors,sowheneverydiscoveredstationgainsatokenandhenceacolor, thenwereferonlytothecolors,whichremainassignedtothestationsforthedurationof 62

PAGE 71

thephase.Aftereverydiscoveredstationhasgainedacolor,apurestageterminates. An update stageisstructuredtogiveeverystationoneopportunitytotransmitexclusivelyforacontiguoussegmentofrounds,includingcandidatestations.Astation i that isunderestimatedbytheamount x transmits x timeswhichisfollowedbysilence.This resultsinanimmediateincrement C [ i ] C [ i ]+ x atallstations.Inparticular,whenanew station k becomesdiscovered,thenthisresultsinsetting C [ k ] toapositivevalue.When astationsimplypausesintherstroundassignedtoit,thenthecorrespondingentryin thearray C isnotmodied;forinstance,acandidatestationmaintainsitsstatus.Itmight happenthatanunderestimatedstationdoesnothavesufcientlymanypacketsreadyto announcebyhowmuchitisunderestimatedinanupdatestage,whichisnotanissueas thisindicatesthatsofarthestationhashadenoughroomtohandleitspackets. A makeup stagefollowsnext.Theredstationsspendthisstageworkingtounload theirpacketswhilethegreenstationspause.Redstationstransmitinthecyclicorder inheritedfromthelist,startingfromthecurrentstationifitisredorotherwisethenextred onefollowingthecurrentstationonthelist.Aredstation i hasasegmentofconsecutive C [ i ] roundsallottedforexclusivetransmissions.Asilentroundbyaredstationresultsin changingthecolorofthestationtogreenimmediatelyandadvancingthepointertothe nextredstation,ifany.Amakeupstageconcludesassoonastherearenoredstations anymore.Tocontrolthedurationofamakeupstage,weimposeadditionalrestrictions. Considerthebeginningofamakeupstage:atthispointallthediscoveredstationsare colored.Let G and R denotethesetsofgreenandredstations,respectively.Let g bethe sum i 2 G C [ i ]= g oftheentriesofthearray C overthegreenstations,and r thesimilar sum i 2 R C [ i ]= r oftheentriesofthearray C overtheredstations.Wehave g + r = g Weadditionallyrequirethatmakeupstageterminatesafter3 nr = g rounds. Thisconcludesthespecicationofallthepossiblekindsofstages,andhenceofthe protocol. Whenapacketisheardinaround,thenthepacketisdequeuedwhilesimultaneously atmostonepacketontheaveragecouldbeinserted.Itfollowsthatsuchroundscontribute 63

PAGE 72

onlytouctuationsofthequeuesby O w packets,as w isanupperboundontheburstiness,sowemayrestrictourattentiontopacketsinjectedduringsilentroundsonlywhen evaluatingthesizeofqueues. Atmost n silentroundsoccurduringthelast n roundsofthepreparationstageand duringeveryfollowingstage.Foraccountingpurposes,wepartitionsilentroundsinto blocks denedasfollows.Therstblockcomprisesthesilencesincurredduringthelast n roundsofthepreparation,duringtherstpurestageandtherstupdatestage.Thenext blockconsistsofatmost3 n silencesincurredduringtheimmediatelyfollowingmakeup, pureandupdatestages.Thiscontinuesthroughouttheexecution,ablockcomprising silencesinconsecutivemakeup,pureandupdatestages.Theideaistoshowthatamakeup stagetakescareoftheprecedingblockofsilentrounds,intermsofcompensatingsome stationsforthetimelostbynotbeingallowedtotransmit. Lemma10 Amakeupstageinprotocol C OLORFUL -S TATIONS takes O nw rounds. Proof: Themakeupstageistoneutralizetheincreaseofthenumberofpacketsparked duringtheprecedingblockofsilentroundsinredstations.Simultaneouslyittakescare ofallpacketsnewlyinjectedintoredstationswithaconceptualratebeingatmosttherate oftheprecedingblock.Weneedtoestimatethetimebywhichallredstationsgogreen. ByLemma6,thesets G ofgreenstationsand R ofredstationshavehadpacketsinjected intothemwiththecumulativeratesofatmost g = g and r = g ,respectively,duringthecurrent phase. Letuscall old thepacketsinjectedintoredstationsduringallsilentupdaterounds oftheprecedingblock.Therearelessthan3 n r g oldpacketsintheredstationswhena makeupstagebegins.Letuscall new thepacketsinjectedintoredstationsduringmakeup rounds.Whentheredstationsarebusytransmittingduringmakeuprounds,theserounds canbepartitionedintodisjointsegmentsof g roundseach.Weemploythefollowingaccountingmethod.Duringsuchasegmentof g rounds,therst r roundsmaybeconsidered asdevotedtounloadingnewpacketsinjectedintoredstationsduringthissegment,while 64

PAGE 73

theremaining g roundscouldbetreatedasaccountingforunloadingtheoldpacketsinjectedintoredstationsduringtheprecedingblockofsilentrounds. Therearelessthan3 n r g oldpackets.Handlingthembyouraccountingmethod requires3 n r g 1 g segmentsoflength g each.Everysuchasegmentistakenoutfroma contiguoussegmentof g makeuprounds.Thisispossiblewhenatleast 3 n r g 1 g g = 3 n r g .1 makeuproundsarepartitionedintosuchsegmentsoflength g each.Thisboundisapart ofcodeofthemakeupstage.Weobtainthatbound.1isatmost3 nw ,as r g w and g 1,sotheboundis O nw Theorem14 Queuesare O n + w andpacketlatencyis O nw whenprotocol C OLORFUL S TATIONS isexecutedagainstadversariesofwindowwinsystemsofnstations. Proof: Apacketinjectedduringaphaseisheardbytheendofthenextphase.This observationdoesnotleadtoaboundonpacketdelay,asthereisnogeneralupperbound onthedurationofapurestage,butitcanbeuseddirectlytoestimatethetotalsizeofthe queues. Foreachstation,itsqueuebecomesemptyatsomepointduringeachphase.Thisis becausecontributingasilenceconvertsthestationgreen.Whenallstationsbecomesuch thenaphaseisover.Therearelessthan3 n silentroundsduringaphase.Theuctuation ofthesizeofthequeuesduetotheseroundsis O n + w .Thismeansthatqueuesare O n + w Toestimatelatency,letusexamineeachkindofstages.Takepurestagesrst.The inequality g w holdsbyLemma6.Weconsidertwocases.When g < w ,thenapure stagetakes O n + w rounds.Otherwise,when g = w ,thenthereisnogeneralupperbound onthedurationofapurestage.Observehoweverthatapacketisdelayedby O n + w roundsduringsuchastage,as O n + w isanupperboundonthenumberofpacketsparked whilethethroughputisequaltotheinputrate.Anupdatestagetakes O n + w roundsby 65

PAGE 74

itsdesign.Adelayduetothemakeupstageis O nw byLemma10.Thelatterbound determinesthelatencybybeingthebiggestamongthecontributionstopacketdelaysby allkindsofstages. NextweconsiderthequestioniftheboundinTheorem14istight.Observethatthe protocolisconictfree,soitfollowsfromTheorem11thatpacketlatencyhastobe W nw forsuitableadversaries. 7.6Conclusion Weintroducedamodelofadversarialqueuingonmultipleaccesschannelsinwhich individualinjectionratesareassociatedwithstations.Wedevelopedanumberofprotocols,whichhavethefollowingtwoproperties.First,thepartitioningoftheaggregaterate amongthestationsconstrainstheadversarybutisunknowntothestations.Second,the boundsonqueuesizeandpacketlatencyofourprotocolsarenotexpressedintermsofthe distributionoftheaggregateinjectionrateamongthestationsastheirindividualrates,but aregivenonlyintermsofthenumber n ofstationsandtheburstiness,whichequalsthe window w fortheaggregaterate1. Thepurposeofthisworkwastocomparetheadversariesdeterminedbyindividual injectionrateswiththeadversariesconstrainedonlybyglobalinjectionrates.Thecomparisonoftheadversarialmodelswastobeintermsoftheattainablequalityofservice forthemaximumthroughputof1.Themaindiscovereddifferencebetweenthegloballyrestrainedandindividually-restrainedadversariesisthatboundedpacketlatencyisachievablewhenaseparateinjectionrateisassociatedwitheachstationbyanadversary,evenby non-adaptivefullsensingprotocolsthatdonotknowanythingabouttheadversary,which isimpossiblefortheglobally-restrainedadversaries. Wedevelopedprotocolsforawindow-typeadversarywithpacketlatencycloseto asymptoticallyoptimalinthefollowingtwocases.Oneiswhentheprotocolsareadaptive andchannelsarewithoutcollisiondetection.Anotheriswhenprotocolsarenon-adaptive fullsensingbutchannelsarewithcollisiondetection. 66

PAGE 75

Packetlatencyofnon-adaptivefullsensingprotocolsforchannelswithoutcollision detectionturnedouttobemorechallengingtorestrict.Theprotocolwedeveloped achieves O nw boundonpacketlatency.Thisprotocolavoidsconictsforaccessto thechannel.Asweshowed,packetlatencyhastobe W nw forsuchconict-avoiding protocols.Thismeansthatthedevelopedprotocolisbestpossibleinthisclassintermsof asymptoticpacketlatency. Thequestionifanon-adaptivefullsensingprotocolcanachievepacketlatencythat isasymptoticallylessthan nw forchannelswithoutcollisiondetectionforwindow-type adversariesofindividualinjectionratesremainsopen. Theadversarialmodelconsideredinthisworkisofthewindowtype.Itisanatural questionhowtoextendittothegeneralleaky-bucketcase,andhowwouldsuchanadversarialmodelaffectprotocols'performance.Inthecaseofglobally-constrainedadversaries withinjectionrate1,itwasshownin[30]thatthetwomodelsofwindowandleaky-bucket adversariesmakeadifferenceforsuitablysmallsystems. 67

PAGE 76

8.Experiments 8.1Simulationswithoutjamming Someoftheresultsgiveninthiswerepresentedinapreliminaryformasconference papersAnantharamu etal. [11,12]. Figure8.1: Observedvaluesofmaximumpacketlatencyforvaryinginjectionrates.Parametervalues:R = 100 ; 000 ;n = 16 ;b = 10 ; a = 0 : 5 ;and b = 0 : 01 .Theverticalscale islogarithmic. Wesimulatedbroadcastprotocolsonamultipleaccesschannelwithpacketinjection patternsrelatedtoleakybucketadversaries.Thefollowingarethemainparametersthat deneasettingofasimulation:anumber n ofstations,anadversaryofsometype r ; b andaspecicbroadcastprotocol P .Theproblemwithsimulatinganadversaryisthatadversarialmodelsareusedtocaptureworst-caseperformanceofprotocols,whichischallengingtomodelviasimulationsasusingrandomnessinsimulationsisnaturalbutithas anaveragingeffect.Weworkedwithinjectionpatternsdenedbythesametype r ; b asa givenadversary,butthepatternsbeingmerelyconsistentwiththeconstraintsofthistype. Ideallytheywouldrepresenttheworst-casebehaviorbutwhattheyproduceisaffected byrandomchoices.Weattempttomodelphenomenathatoriginallypromptedtheuseof randomnesstoarbitrateforaccesstothechannel,asemployedinbroadcastprotocolslike 68

PAGE 77

theEthernet.Deterministicprotocolsareofinteresttousandwewantdeterministicprotocolstocompeteagainstrandomizedones;tothisendweneedaplaygroundthatisfair. Sowewanttomodelascenariowhentherearealwaysanumberofstationsintowhich theadversaryisinjectingpacketssotheyarebusytransmittingtheirpacketswhileother stationsdonotreceivepacketstemporarilysotheystayidle.Suchastatusofastation asbeingbusyoridlekeepschanging.Onecouldarguethatthiscapturesthereal-world applicationsandprotocolsrelyingonrandomnesswouldfarewellinsuchscenarios.To representsuchsituationsinsimulations,weprovidedtwoindependentmechanisms.One controlledthesetofstationsintowhichpacketswereinjectedandtheothergovernedthe numberofpacketsgeneratedinaround. Figure8.2: Observedvaluesofmaximumpacketlatencyforvaryinginjectionrates.Parametervalues:R = 100 ; 000 ;n = 16 ;b = 10 ; a = 0 : 5 ;and b = 0 : 1 .Theverticalscaleis logarithmic. 8.1.1Machineryofpacketinjection: Wewanttohaveabehaviorthatismoreburstythanrandom,andtofacilitateitwe introducethreeadditionalparametersapartfromburstinessandinjectionrate,denotedby thesymbols a ; b ; g .Webeginwithamodelthatcapturesthechangeofstatusofstationsas eitherbusyoridle.Eachstationgoesthroughperiodsofactivityinterleavedwithperiods 69

PAGE 78

ofpassivity.Therearetwoparameters:the activity denotedby a andandthe volatility denotedby b .Thesenumberssatisfytheinequalities0 < a 1 = 2and0 b 1.The motivationwasthatthereare a n stations active inreceivingpacketswhilethenumber b determinedthepropensitytochangestatus.Theactivestationswereeligibletoreceive packetswhiletheremaining passive stationsweretransmittingonlytheiroldpackets. Thevolatilityistobeunderstoodasarateofchangeofstatusofstationsfromactiveto passive,inthesensethatitisafractionofthesetofallactivestationsperroundthat becomepassive. Theimplementationofactivityandvolatilityareasfollows.Let k = a n bethenumber ofactivestations;initiallywepicksome k stationsasactive.Whatwedodependson whether b k isatleast1ornot.If b k 1,thenateachroundwechooserandomly d b k e activestationsand d b k e passivestations:thesestationschangetheirstatusfromactiveto passiveandviceversa.If b k < 1thenwepartitionanexecutionintotimesegmentsof length d 1 = b k e .Atthebeginningofsuchasegmentwechoosearandomactivestation andarandompassivestationandletthemswitchtheirstatus.Additionally,thenumbers ofpacketsgeneratedatconsecutiveroundsisconsistentwiththegivenadversarialtype r ; b Wemaintainavariable m calledthe potential whichistodenoteanupperboundon thenumberofpacketsthatcanbeinjectedinaround; m isarationalnumberratherthen aninteger.Thispotential m isinitializedto m b beforetherstround.Afteraround inwhich x packetsweregeneratedandinjectedwemodifythepotential m asfollows: m min m )]TJ/F49 11.9552 Tf 11.01 0 Td [(x + r ; b ,whichisconsistentwithtype r ; b ofanadversary.Thespecic numberofpacketsgeneratedduringaroundisdeterminedbyparameter g .Theparameter g issettobeequaltotheinjectionrate r .Consideraroundandlet m bethecurrentvalue ofthepotential.Werstchooseaninteger j withaPoissonprobabilitydistributionwith expectedvalue g .Ifthevalueoftheinteger j isinthesegment [ 0 ; m ] thentheadversary generates j packetsotherwisetheadversarygeneratesnopacketsinthisround. 70

PAGE 79

Figure8.3: Observedvaluesofmaximumpacketlatencyforvaryinginjectionrate.Parametervalues:R = 100 ; 000 ;n = 16 ;b = 10 ; a = 0 : 5 ;and b = 0 : 001 .Theverticalscale islogarithmic. Experimentsproper: Thegoalofthesimulationwastolookintotheworstcasebehaviorofbroadcastprotocolsforvariousparameters.Theparametersofanexperiment includedthefollowing.Thenumberof simulationroundsR ,thenumberofstations n injectionrate r ,burstiness b ,and a and b .Onlythepacketsinjectedintherst R rounds wereusedtomeasuremaximumlatency.Tothatend,executionsofprotocolswerecontinueduntilallthepacketsinjectedwithintheroundsupto R hadbeentransmitted.We simulatedthevedeterministicprotocolsalongwiththebinaryexponentialbackoffand thequadraticbackoff.Thebackoffprotocolswereimplementedasthewindowedversions wheretheroundofatransmissionisdrawnfromawindowuniformlyatrandom.ForexponentialbackoffEB,the i thwindowsizewasdeterminedas2 min 10 ; i ,for0 i 10.For quadraticpolynomialbackoffPB,the i thwindowsizewasdenedtobe min i ; 32 2 for1 i 32.Theconstant c waschosentobe10forbinaryexponentialbackoffsimilar towhatisusedintheEthernet.ThemaximumsizeofawindowwasthesameinPB andEB.Notethatnoneofthepacketsweredroppedforbothdeterministicandbackoff protocols. 71

PAGE 80

Figure8.4: Observedvaluesofmaximumpacketlatencyforvaryingnumberofstations. Parametervalues:R = 100 ; 000 ; r = 0 : 8 ;b = 10 ; a = 0 : 5 ;and b = 0 : 001 .Thevertical scaleislogarithmic. Experimentswererunundervaryinginjectionratesandnumbersofstations;theirresultsaredepictedinFigures8.1through8.4.InFigure8.1wecomparetheperformance ofdeterministicandbackoffprotocols:itcanbeseenhowthedeterministicprotocolsoutperformthebackoffonesastheinjectionratesgrow.Amongstthedeterministicprotocols MBTFfaredworse.ThisiswhatCorollary4indicates.AnotherthingtonoticeinFigure 1istheperformanceofquadraticandexponentialbackoffprotocols.Forveryhighinjectionrateswewereexpectingthequadraticbackofftooutperformtheexponentialback offbutthiswasnotachievedinourexperiments.Thisneedstobefurtherinvestigated.In Figure8.2wecomparetheperformanceofdeterministicprotocols.Theregularprotocols outperformedtheold-rstonesandMBTFhadtheworseperformance. Figure8.4showstheeffectofthenumberofstationsonthemaximumpacketlatency forsomedeterministicandbackoffprotocols:deterministicprotocolsagainoutperformed thebackoffones. Wealsolookedintotheeffectoftheold-rstparadigmtoseeifitmakesadifferenceinexperiments.InFigure8.3wecompareregularprotocolswithold-rstones.the 72

PAGE 81

performanceofOFSRRandOFRRWappearstobedifferentfromwhatwehaveinTheorem6andCorollary1.Regularprotocolsoutperformedtheold-rstones.Sowhatwe canseeisthatwhenthereissomerandomizationinvolvedinexperimentstheoldrst protocolsdonotnecessarilyoutperformregularprotocols.Thisexperimentalresultwith somerandomizationinpacketinjectionisincontrasttothetheoreticalresultswithno randomization. 8.2Simulationswithjamming Weperformedexperimentstocomparepacketlatencyofdeterministicbroadcastprotocolsamongthemselvesandalsowithrandomizedbackoffprotocolsinanadversarial settingwithjamming. Webuildonthemechanismproposedin[11]andextendittoincorporatejamming. Inanattempttocapturetheworstcasebehaviorandburstinessofbroadcastdemands, wheretypicallysomestationsareactivelyreceivingpacketswhileothersstayidle,two parameters a and b denedasbeforewereused. Anadversarycontrolsbothinjectionandjammingandinjectsonlyinactivestations inaround.Thetypeofanadversarydeterminesinjectionsbytheparameters r ; b and jammingbytheparameters l ; b ;therates r and l arerationalnumbersinexperiments. Thefreedominhowmanypacketstopossiblyinjectinaroundoriftojamarounddependsonthehistoryoftheadversary'sactivity.Werepresentsuchhistoryby potentialP understoodtomeaneitheranupperboundonthenumberofpacketspossibletoinjectina givenroundorthenumberofconsecutiveroundsthatcouldbejammedstartingfromthe currentround,dependingonwhichaspectofadversary'sactivityistobedecidedupon, respectively.Wemaintaintwopotentials, packet-injectionpotentialP i and jammingpotentialP j torepresentthemaximumnumberofpacketsthatcouldbeinjectedinthecurrent roundandtheconsecutivenumberofpacketsthatcouldbejammed,respectively.More precisely,thenumberofpacketsgeneratedtobeinjectedistakenfromtheinterval [ 0 ; P i ] andthenumberofconsecutiveroundstojamstartingfromthecurrentroundistakenfrom theinterval [ 0 ; P j ] .Thepotentialsareinitializedto P i r + b and P j l + b .After 73

PAGE 82

aroundinwhich x packetsweregeneratedandinjectedwemodifythepacket-injection potentialby P i min P i )]TJ/F49 11.9552 Tf 10.996 0 Td [(x + r ; b ,whichisconsistentwiththe r ; b componentofthe adversary'stype.Afteraroundinwhich y consecutiveroundsweredecidedtobejammed wemodifythejammingpotentialby P j min P j )]TJ/F49 11.9552 Tf 10.789 0 Td [(y + l ; b ,whichisconsistentwiththe l ; b componentoftheadversary'stype.Ineachroundofablockofroundstobejammed asdecidedinadvance,thenumbers y areinterpretedtomean0untiladecisionaboutjammingneedstobetakenagain.Givenapotential P ,thedecisiontoselectanumberinthe interval [ 0 ; P ] foraroundisdeterminedbyanadditionalparameter g ;thisisimplemented asfollows.Parameter g issettobeequaltoinjectionrate r forpacketinjectionandto jammingrate l forjamming.Firstchooseaninteger k withaPoissonprobabilitydistributionwithmean g .Ifaninteger k happenstobeinthesegment [ 0 ; P ] then k istheselected number,otherwiseitis0thatisselected.Stationsattachedtothechannelreceivetwo possiblekindsoffeedbackinaround:ifaroundisjammedtheneachstationperceives theroundassilent,otherwisewhatishearddependsontheactionsofthestationsinterms ofpackettransmissions,asitisspeciedforamultiple-accesschannelwithoutcollision detection. WeimplementedthevedeterministicprotocolsspeciedinSections5.1.1and5.1.2; thesearetwofull-sensingprotocolsJRRW J andOF-JRRW J andthreeadaptiveprotocolsC-RRW,OF-C-RRW,andMBTF.Forthetwofullsensingprotocolsthejamming burstiness J wassetto J = min b b = 1 )]TJ/F50 11.9552 Tf 11.354 0 Td [(l c + 1,3.Notethatwhilethejammingrate changesintheexperiments,thejammingburstinessalsochangesaccordingly.Inadditiontodeterministicprotocols,weimplementedtwoback-offprotocols:theexponential back-off,denotedE XP B ACKOFF ,andthequadraticpolynomialback-off,denotedP OLY B ACKOFF .Theimplementationforbackoffprotocolswasexactlysimilartotheonesused innonjammingexperiments. Simulationswereruntoseehowinjectionrates,jammingrateseffectedmaximum latency,respectively.Thenumbersofroundsforinjectionsinsimulationswerexedin advance.Themaximumlatencyofpacketsinjecteduptothemaximuminjectionround 74

PAGE 83

Figure8.5: Observedvaluesofmaximumpacketlatencyforvaryinginjectionandjammingrates.Parametervalues:R = 100 ; 000 ;n = 16 ; r = 10 l ;b = 10 ; a = 0 : 5 ;and b = 0 : 001 .Theverticalscaleislogarithmic. wasmeasuredbycontinuingthesimulationuntilallthepacketsinjecteduptothexed nalinjectionroundhadbeentransmitted.Weranexperimentstocomparemaximum latencyofdeterministicprotocolswithback-offprotocols. Maximumlatencyofdeterministicprotocolswerecomparedtoback-offprotocolsas showninFigure8.5,forvaryinginjectionandjammingrates.ThreedeterministicprotocolsMBTF,C-RRW,andJRRRW J werecomparedamongthemselvesformaximum latencyforvaryinginjectionandjammingrates;thesearetheprotocolsconsideredthat donothavetheold-rstmechanism.Theoutcomesoftheseexperimentsareshownin Figures8.6.Theoutcomescanbeinterpretedasfollows. Figure8.5containsachartthatpresentsacomparisonofallthesevenprotocols,includingtheback-offones.Alogarithmicscaleisusedforpacketlatency.Thehorizontal axisofratesinagurerepresentsthesum r + l ,whichisconsideredwithincrements0 : 05. Theverticalaxisrepresentsthemaximumpacketlatencyrecordedforthecorresponding valuesofthesum r + l .Theinjectionrate r issetto10 l .Amongstthedeterministic protocols,theorderofbestperformanceformaximumpacketlatencywasC-RRW,OF75

PAGE 84

Figure8.6: Observedvaluesofmaximumpacketlatencyforvaryinginjectionandjammingrates.Parametervalues:R = 100 ; 000 ;n = 16 ; r = l ;b = 10 ; a = 0 : 5 ;and b = 0 : 001 .Theverticalscaleislinear. C-RRW,MBTF,JRRW J andOF-JRRW J .Deterministicprotocolsoutperformed thetwoback-offprotocolsforhigherinjectionandjammingrates,althoughtheback-off protocolsdidbetterthansomedeterministicprotocolsforsmallerinjectionandjamming rates.Wecanobserveajumpinpacketlatencyofback-offprotocols,bytwoorthreeordersofmagnitude,aroundthecombinedratesof0 : 4.Againregularprotocolsperformed betterthantheOld-rstprotocols,whichisincontrastwiththecorrespondingtheorems ofSections5.1.1and5.1.2.Theadaptiveregularandoldrstprotocols,JRRW J and OF-JRRW J ,wereverycloseintermsofthemaximumpacketlatency,withtheregularprotocolperformingslightlybetter.Forthefullsensingprotocols,regularprotocol C-RRWoutperformedold-rstprotocol.Thisresultsofregularandoldrstprotocols indicatethatrandomizationinexperimentsmakeadifference. Figure8.6isacomparisonofalltheregularprotocols.Theverticalscaleusedis linear.TheorderofperformanceisC-RRW,MBTFandJRRW J 8.3Conclusion Deterministicprotocolsoutperformedthebackoffonesintheexperimentsforhigher injectionandjammingrates,althoughthebackoffprotocolsperformedbetterthanatleast 76

PAGE 85

somedeterministiconesforsmallerinjectionandjammingrates.Adaptiveprotocolstypicallyfaredbetterthanfullsensingones.AdaptiveprotocolMBTFtypicallyhadgreatest packetlatencyamongadaptivedeterministicprotocols.Betweentheregularandold-rst protocolstheregularprotocolsperformedbetterthantheold-rstones.Thisisincontrast withtheoreticalresults. 77

PAGE 86

9.Adhocmultipleaccesschannels Multipleaccesschannelsmodelshared-mediumnetworksinwhichsimultaneous broadcasttoallusersisprovided.Theyareanabstractionofthenetworkingtechnology ofpopularimplementationoflocalareanetworksbytheEthernetsuiteofalgorithms[56]. Inamultipleaccesschannel,transmissionsbymultipleusersthatoverlapintime resultininterferencesothatnonecanbesuccessfullyreceived.Thismakesitnecessary eithertoavoidconictforaccesstothechannelaltogetherortohaveamechanismto resolveconictwhenitoccurs. Weconsiderbroadcastinginmultiple-accesschannelsinadynamicscenariowhen therearemanystationsattachedtothechannel,butonlyafewofthemareactiveatany timeandthestations'statusofactiveversuspassivekeepschanging.Thiscorrespondsto arealisticsituationwhenmoststationsareidleformostofthetimewhileafewstations occasionallywanttousethebroadcastfunctionalityofthechannel.Moreover,itisnormallyimpossibletopredictinadvancewhichstationswillneedtoaccessthechannelat whattimes,asburstsofactivityamongstationsdonotexhibitanyregularpatterns.The unpredictabilityofaccesstothechannelamongthestationscanbehandledbyusingrandomizationinresolvingconictforaccess,asimplementedinthecarrier-sensemultiple access,see[46]. Consideringdeterministicalgorithmsandtheirworst-caseperformancerequiresmethodologicalsettingspecifyingworst-caseboundsonhowmuchtrafcanetworkwouldneed tohandle.Thiscanbeaccomplishedformallythroughsuitableadversarialmodelsofdemandsonnetworktrafc. Anothercomponentinaspecicationofabroadcastsystemishowmuchofwhat thecommunicatingagentsknowcanbeusedincodesofalgorithms.Therearevarious approachestomodelmultipleaccesschannelsintermsofwhatisknowntothestations attachedtothecommunicationmedium.Historically,therstapproachwastousethe queue-freemodel,inwhicheachinjectedpacketistreatedasifhandledbyanindependent stationwithoutanynameandnoprivatememoryforaqueue.Inthismodel,thenumber 78

PAGE 87

ofstationsisnotsetinanyway,asstationscomeandgosimilarlyaspacketsdo;see[35] fortheinitialworkonthismodel,and[20]formorerecentone. Analternativeapproachtoadhocchannelsistohaveasystemwithaxednumber n ofstations,eachequippedwithaprivatememorytostorepacketsinaqueue.Anattractive featureofsuchxed-sizesystemsisthatevensimplerandomizedprotocolslikeAlohaare stableundersuitabletrafcload[65],whileinthequeue-freemodelthebinaryexponential backoffisunstableforanyarrivalrate[4]. Thepopularassumptionsusedintheliteratureaddressingdistributeddeterministic broadcastingstipulatethattherearesome n stationsattachedtoachannelandthateach stationisidentiedbyitsnameintheinterval [ 0 ; n )]TJ/F18 11.9552 Tf 11.329 0 Td [(1 ] ,witheachstationknowingthe number n anditsownname;see[11,12,13,30,31].Ourgoalistoexploredeterministic broadcastingonmultiple-accesschannelswhentherearemanystationsattachedtoachannelbutonlyafewstationsuseitatatime.Insuchasituation,usingnamespermanently assignedtostationsbydeterministicdistributedalgorithmsmaycreateanunnecessarily largeoverheadmeasuredaspacketlatencyandqueuesize.Thisisbecausethepacket latencyisexpectedtobeafunctionofthetotalnumberofstations,whichisassumedto beverylarge;see[11,12]forsuchapproaches. Hereweconsiderdistributeddeterministicbroadcastingbutwedepartfromtheassumptionaboutaxedknownsizeofthesystem.Instead,weviewthesystemasconsistingofaverylargesetofstationsthatarenotindividuallyidentiedinanyway.Assome stationsneedtousethechanneltocommunicate,theyjointhebroadcastingactivity,which needstobecoordinatedwiththeothercurrentlyactivestationsbythemedium-accesscontrollayer. Theprocessofactivatingstationsismodeledbyasuitableadversarialmodelthatwe propose.Thisadversarialmodelisdesignedtorepresentaexiblesysteminwhichwe relaxtheassumptionthatthereisanitexedsetofstationsattachedtothechannel,and thattheirnumberisknowntoeachparticipatingstation,andthateachstationhasassigned uniquenamewhichitknows.Wecallsuchchannels adhoc toemphasizethevolatilityof 79

PAGE 88

thesystemandtherelativelackofknowledgeofindividualstationsaboutthemselvesand theenvironment.Adhocchannelsareacrossoverbetweenthequeue-freemodel,with whichtheysharethepropertyofanunboundedsupplyofanonymousstationsactivated byinjectedpackets,andthemodelofnitelymanystationsinasystem,withwhichthey sharethepropertythatstationsusetheirprivatememoriestoimplementqueuestostore pendingpackets. Wemeasuretheperformanceofbroadcastalgorithmsbypacketlatencyandqueue sizes.Thesemetricsreectthesuitablepropertiesoftheadversarialmodelthatdene constraintsonpacketinjection.Suchconstraintsincludepacketinjectionrate,understood astheaveragenumberofpacketsinjectedinalargetimeinterval,andburstiness,which meansthemaximumnumberofpacketsthatcanbeinjectedsimultaneously.Adversarial modelsoftrafcallowtostudytheworst-caseperformanceofdeterministiccommunicationalgorithmsinthesuitablemetrics. Ourresults. Weproposeanadversarialmodeloftrafcdemandsforadhocmultiple accesschannels,whichrepresents dynamic environmentsinwhichstationsfreelyjoinand leavebroadcastingactivity.Asanonymoussystemscannotbreaksymmetryinadeterministicmanner,werestrictadversariesbyallowingthemtoactivateatmostonestation perround.Thisisshowntobesufcientforefcient deterministic distributedbroadcastalgorithmstoexist.Wecategorizealgorithmsintoacknowledgmentbased,activation basedandfullsensing.Independentlyfromthat,wedifferentiatealgorithmsbythepropertyiftheyusecontrolbitsinmessagesornot,callingthemadaptiveandnon-adaptive, respectively.Wegiveanumberofalgorithms,forchannelswithandwithoutcollision detection,forwhichweassesinjectionratestheycanhandlewithboundedpacketlatency. Morespecically,ournon-adaptiveactivation-basedalgorithmcanhandleinjectionsrates smallerthan 1 3 onchannelswithcollisiondetection,theadaptiveactivation-basedalgorithmcanhandleinjectionrate 1 2 onchannelswithoutcollisiondetection,thenon-adaptive full-sensingalgorithmcanhandleinjectionrateslessthan 2 3 onchannelswithcollision detection,andtheadaptivefull-sensingalgorithmcanhandleinjectionrate 3 4 onchannels 80

PAGE 89

withcollisiondetection.Wealsoshowthatthelatteralgorithmisoptimal,intermsof injectionrate 3 4 thatcanbehandledwithboundedpacketlatency,asweprovethatno algorithmcanprovideboundedpacketlatencywheninjectionratesaregreaterthan 3 4 Relatedwork. AdversarialqueuingmethodologywasintroducedbyAndrewsetal.[14] andBorodinetal.[26],whereitwasusedforstore-and-forwardroutinginwirednetworks. AdversarialqueuingonmultipleaccesschannelswasrststudiedbyBenderetal.[20], inthecaseofthequeue-freemodelandrandomizedprotocols.Deterministicdistributed broadcastingonmultipleaccesschannelswithqueuesinadversarialsettingswasinvestigatedrstbyChlebusetal.[30,31]andlaterstudiedbyAnantharamuetal.[11,12,13]. Thatworkondeterministicdistributedprotocolswasaboutsystemswithaknownxed numberofstationsattachedtothechannelandwithstationsusingindividualnames.Deterministicprotocolsforcollisionresolutioninstaticalgorithmicproblemsonmultiple accesschannelswererstconsideredbyGreenbergandWinograd[40]andKomlsand Greenberg[47].Acknowledgment-basedprotocolsincludetherstrandomizedprotocols studiedondynamicchannels,asAlohaandbinaryexponentialbackofffallintothiscategory.Thethroughputofmultipleaccesschannels,understoodasthemaximuminjection ratewithPoissontrafcthatcanbehandledbyarandomizedprotocolandmakethesystemstableergodic,hasbeenintensivelystudiedintheliterature.Itwasshowntobeas lowas0 : 568byTsybakovandLikhanov[64].Goldbergetal.[38]gavesuchboundsfor backoff,acknowledgment-basedandfull-sensingprotocols.Hstadetal.[42]compared polynomialandexponentialbackoffprotocolswithrespecttoboundsontheircapacityin thequeuingmodel.Forearlyworkonfull-sensingalgorithmsinchannelswithcollision detectioninthequeue-freemodelseethesurveybyGallager[35].Randomizedprotocols ofboundedpacketlatencyweregivenbyRaghavanandUpfal[59]inthequeuingmodel andbyGoldbergetal.[39]inthequeue-freemodel.Upperboundsonpacketlatencyin adversarialnetworkswasstudiedbyAnantharamuetal.[11,12]inthecaseofmultiple accesschannelswithinjectionratelessthan1andRosnandTsirkin[61]forgeneralnet81

PAGE 90

worksandadversariesofrate1.Algorithmicproblemsofdistributed-computingavorin systemsinwhichmultipleaccesschannelsprovidetheunderlyingcommunicationinfrastructurewereconsideredbyBie nkowskietal.[25],Chlebusetal.[28,29],andCzy zowicz etal.[32]. 9.1Technicalpreliminaries Amultiple-accesschannelisamodelofcommunicationforlocalareanetworks.It consistsofasharedcommunicationmediumandstationsattachedtoit.Thesegeneral propertiescanbemadespecicinvariousways,ourspecicationsaresummarizednext. Multipleaccesschannels. Thereisanunboundedsupplyofstationsattachedtothe channel.Stationsare anonymous inthattheydonothaveindividualnamesassignedto them.Thecontentsastationbroadcastsonthechanneliscalleda message .Packetsare injectedintostationsandthegoalistobroadcastthemonthechannel.Amessagemay includeatmostonepacketandpossiblyanumberofcontrolbitsattachedtoit.Each stationhasprivatememory,whichisusedtostoreprivatevariables.Astationstores pendingpacketsinaprivatequeueimplementedinitsprivatememory;suchaqueue isoperatedinarst-in-rst-outmanner.Whenastationtransmitsamessagethenthe messagereacheseverystation.Astationreceivesthemessagesuccessfullywhenthe receptionofthismessagedoesnotoverlapwithanyreceptionofothermessages;inthis instancewesaythatthemessageis heard onthechannel.Whenamessageisheard onthechannel,thenallstationsreceiveitsuccessfully,includingthetransmittingone. Weconsidersynchronouschannelswhichoperateinrounds.Roundsandmessagesare calibratedsuchthattransmittingonemessagetakesthedurationofaround.Amessage sentinaroundisdeliveredtoeachstationinthesameround.Whenatleasttwomessages aretransmittedinthesameroundthenthiscreatesa collision ,whichpreventsanystation fromhearinganyofthetransmittedmessages.Whennostationtransmitsinaround, thentheroundiscalled silent .Achannelissaidtobe withcollisiondetection whenthe feedbackfromthechannelinacollisionroundisdifferentfromthefeedbackreceived duringasilentround,otherwisethechannelis withoutcollisiondetection .Forachannel 82

PAGE 91

withoutcollisiondetection,acollisionroundandasilentoneareperceivedthesame.A roundis void whennostationhearsamessage;sucharoundiseithersilentoracollision one.Astationissaidtobe active ifithaspacketspendingtobetransmittedonthechannel, otherwiseitis passive .Astationwithanemptyqueueissaidtobe activated whenatleast onepacketisinjectedintoit.Astationisinitializedaspassive.Weconsiderchannelsthat are adhoc whichmeansthatstationsareanonymousandthereisno apriori boundonthe numberofactivestationsinaround.Weimposerestrictionsonhowpassivestationsmay beactivated. Adversarialmodelofpacketinjection. Packetsareinjectedbyadversaries.Adversariesareconstrainedbyhowmanystationstheycanactivateinaround.Anadversary is k-constrained ,foraninteger k > 0,ifatmost k stationsmaybeactivatedinaround. Weconsider1-constrainedadversaries,unlessexplicitlystatedotherwise.Theadversarial modelofthispaperisthatofgeneralleaky-bucketadversaries.Foranumber0 < r 1 andinteger b > 0,aleaky-bucket adversaryofpacketinjectiontype r ; b mayinjectat most r j t j + b packetsinanytimeinterval t of j t j rounds.Inthiscontext,thenumber r isthe rateofinjection .Themaximumnumberofpacketsthatanadversarymayinjectin oneroundisthe burstiness ofthisadversary.Theburstinessis b r + b c fortheadversary oftype r ; b Broadcastprotocols. Weconsiderdeterministicdistributedbroadcastprotocols.Distributedprotocolsareeventdriven.Aneventinwhichastationparticipatesconsistsof everythingthathappenstothestationinaround,includingwhatthestationreceivesas feedbackfromthechannelandhowmanypacketsareinjectedintoit.Theprotocolswe considerareorganizedsuchthatpendingpacketsatastationarestoredinaqueueinthe privatememoryofthestationandsuccessfullybroadcastpacketsareremovedfromtheir queues.Thisgivesthepropertythatastationisactiveifandonlyifitsqueueisnonempty. Protocolsdonotknowanythingaboutthebroadcastsysteminwhichtheyare 83

PAGE 92

executed,whereknowledgeofpropertiesofasystemmeansusingthemasapart ofcode.Thisisincontrastwithpreviousworkondeterministicdistributeprotocols, see[11,12,13,30,31],wherethenamesofstationsandthenumberofstationswere knowntothestations.Noinformationaboutadversariesisreectedinthecodeexecuted bystations.The state ofastationisdeterminedbythevaluesofitsprivatevariables;this mayormaynotincludetheprivatequeueusedtostorependingpackets,dependingon whetherwewanttohaveastationintheinitialstatewhileitsqueueisnon-empty.Each stationisinitializedtothesameinitialstate,bythesamevaluesstoredintheprivatememorylocations,andwithanemptyqueue.Packetsaretreatedasabstracttokensandtheir individualpropertiesdonotaffectstatetransitions. Aroundofanexecutionofaprotocolisstructuredsuchthatstationsrstperform theiractionsandnexttheadversaryinjectspacketsintosomestations,ifany.Moreprecisely,aroundconsistsofthefollowingactions:rsttransmittingpackets,thenreceiving feedbackfromthechannel,nextmakingstatetransitions,andnallyhavingnewpackets injected;someoftheseactionsmaybevoidinastationinaround.Apacketthatwas successfullytransmittedbyastationisremovedfromthisstation'squeueatthetimeofits statetransition.Astationbecomespassiveintheroundinwhichitsuccessfullybroadcasts theonlyremainingpacketinitsqueue,whichmakesthequeueemptyafterdequeuingthe packet.Atthismomentthestationbecomespassive,sowhenapacketisinjectedintothis stationinthisveryround,itisaninjectionintoapassivestation.Astation'sstatus,ofactiveversuspassive,isdynamicinthecourseofanexecution:anactivestationmayeither eventuallyberelegatedtopassiveandstaysuchforever,oritmaystayactiveforever,orit maychangeitsstatusbetweenactiveandpassiveanynumberoftimes. Classesofprotocols. Wedenesubclassesofprotocolsasfollows.Generalprotocols mayhavestationsattachcontrolbitstopacketstobroadcastasmessages.Whensuchbits areusedthenwesaythattheprotocolis adaptive ,otherwisetheprotocolis non-adaptive Protocolssuchthatastationstaysintheinitialstatewhilepassiveandresetsitselftothe 84

PAGE 93

initialstateinaroundinwhichapacketittransmittedwasheardonthechannelarecalled acknowledgmentbased ;forthistobemeaningful,theprivatequeuesatstationsarenot consideredaspartofstate,whichistheonlysuchsituationweconsider.Protocolssuch thatastationstaysintheinitialstatewhilepassiveanditresetsitselftotheinitialstate whenitbecomespassiveagain,thatis,inaroundinwhichthelastpacketfromitsqueue isheardonthechannel,arecalled activationbased .Protocolssuchthatstationsmay havestatetransitionsineachround,whetherastationisactiveorpassive,effectedbythe feedbackfromthechannelaccordingtothestate-transitionrulesrepresentedbythecode, arecalled fullsensing .Thecategorizationofadaptiveversusnon-adaptiveisindependent oftheotherthreecategorizations,sooverallwehavesixcategoriesofprotocols.This categorizationofprotocolsholdsindependentlyforchannelswithandwithoutcollision detection. Astationexecutingafull-sensingprotocolmayinprinciplerememberthewhole historyofthefeedbackfromthechannel,unlessthesizeofitsprivatememoryrestricts itinthisrespect.Anactivestationexecutinganactivation-basedprotocolmayrememberthehistoryofthefeedbackfromthechannelsincetheactivation.Anactivestation executinganacknowledgment-basedprotocolmayrememberthehistoryofthefeedback fromthechannelsincethelatestsuccessfultransmissionoractivation,whicheveroccurred later.Acknowledgment-basedprotocolsareasubclassofactivation-basedprotocols.Similarly,activation-basedprotocolsareasubclassoffullsensingones,asastationexecuting anactivation-basedprotocolcouldbeconsideredasreceivingfeedbackfromthechannelbutidlingintheinitialstatewhenwithoutpendingpackets.Theterminologyabout acknowledgment-basedandfull-sensingprotocolsisconsistentwiththatusedintheliteratureonrandomizedprotocolsinthequeue-freemodel,see[35],whileitisdifferent fromtheterminologyusedintherecentliteratureondeterministicdistributedprotocolsin adversarialsettings,see[11,12,13,30,31]. 85

PAGE 94

Qualityofbroadcasting. Aprotocolis fair wheneachpacketinjectedintosomestation eventuallygetsheardonthechannel.Aprotocolis stable whenthequeuesstaybounded throughoutanyexecution.Aprotocolhas packetlatencyt wheneachpacketspendsat most t roundsinthequeuebeforeitisheardonthechannel.Thesequalityfeaturesnormallyholddependingonanadversary,thatis,how k -constraineditisandwhatisitstype. 9.2Limitationsonbroadcasting Inthissectionweconsiderwhatlimitationsondeterministicdistributedbroadcasting areinherentinthepropertiesofad-hocmultipleaccesschannelsandtheconsideredclasses ofalgorithms. Proposition1 Nodeterministicdistributedalgorithmisfairagainsta 2 -activatedadversaryofburstinessatleast 2 Proof: Wewanttomaintainaninvariantthattherearetwostationsthatproceedthrough thesamestatesinthecourseofanexecution.Letanexecutionbeginwiththeadversary injectingpacketssimultaneouslyintotwopassivestations,onepacketperstation.These twostationsexecutethesamedeterministicalgorithm,sotheiractionsarethesameuntil onestationexperienceswhattheotherdoesnot.Theadversarydoesnotneedtoinject anyotherpackets.Itfollows,byinductiononroundnumbers,thatwhenoneofthese twostationstransmitsapacketthentheotheronetransmitsaswell,andwhenonestation pausesthentheotherstationpausesaswell.Inthisexecution,eachtransmissionattempt resultsinacollision.Thismeansthatthetwopacketsnevergetheardonthechannel. InthelightofProposition1,werestrictourattentionto1-activatedadversariesinwhat follows.For1-activatedadversaries,wemayrefertostationsparticipatinginanexecution bytheroundnumbersinwhichtheyareactivated.Sowhenwereferto stationv ,for aninteger v 0,wemeanthestationthatgotactivatedintheround v .Ifnostationgot activatedinaround v ,thenastationbearingthenumber v doesnotexist.Toavoidmultiple identitiesofastation,weassumethatonceastationisactivatedandlaterbecomespassive, thenitnevergetsactivatedagain;thisdoesnotmakeadifferencefromtheperspectiveof 86

PAGE 95

theadversary,asweassumethatthereisanunboundedsupplyofpassivestations. Proposition2 Noacknowledgment-basedalgorithmisfairagainsta 1 -activatedadversaryofaburstinessthatisatleastthree. Proof: Itissufcienttodemonstratetheexistenceofanexecutioninwhichtwostations simultaneouslystartworkingtobroadcastanewpacketeach.Thisisbecausethestations startfrominitialstates,theyareanonymous,andtheyexecutethecodeofthesamedeterministicalgorithm.Wemayassumethatapassivestationimmediatelyattemptstotransmit apacketwhenactivated,asotherwiseadelayresultsinasuitablyearlieractivation. Lettheadversaryinjecttwopacketsintoapassivestationinroundoneandnextone packetintoanotherpassivestationinroundtwo.Thestation1transmitsitsrstpacket successfullyinthesecondround.Thetwostations1and2startworkingonanewpacket eachfromthethirdround,whichresultsinacollisionandanexecutionwhoseexistence wewantedtodemonstrate. Forsuchascenariotobepossible,theadversaryneedstobeabletoinjectthree packetsintwoconsecutiverounds,whichrequiresburstinesstobethreewheninjection rateislessthan 1 2 BecauseofProposition2,weconsideronlyactivation-basedandfull-sensingalgorithmsinwhatfollows.Weconsiderthequestionwhatisthemaximuminjectionratefor whichboundedqueuesorpacketlatencycanbeattained.Theanswermaydependonthe restrictionsonthealgorithmsinaclass,liketheclassesofactivationbasedandgeneral full-sensingalgorithms,andwhetherthechannelhascollisiondetectionornot. Beforeembarkingonoptimizingadversariesinnon-existenceofbounded-latencyalgorithms,wemayobservethatnodeterministicdistributedalgorithmcanprovidebounded packetlatencyagainstanadversaryofinjectionrateequalto1andwithburstinessat least2.Toseethis,consideranarbitraryalgorithmexecutedagainstsuchanadversary. Webuildanexecutionbydeningitthroughtheprexesofasequenceofauxiliary executions.Letanexecution E 1 beobtainedbyactivatingastationpereachround,by 87

PAGE 96

wayofinjectingonepacketintoapassivestation.Therearetwocases.First,suppose thatthereexistsanactivestation v 1 whichalonetransmitsapacket.Thetransmission by v 1 issuccessfulin E 1 andapacketisheard.Letusmodifytheexecution E 1 toanother execution E 2 suchthatthestation v 1 isnotactivatedatall,whichresultsinasilentround. Instead,afterthesilentroundin E 2 ,weactivateastationbyinjectingtwopacketsintoit. Thetargetexecutionhasitsprexdetermineduntilandincludingtheinjectionofthesetwo packetssimultaneouslyin E 2 .Inthesecondcase,thereexisttwoactivestations v 2 and v 3 suchthattheytransmittogetherin E 1 inaroundofthersttransmissioninthisexecution. Thiscreatesacollision,whichcontributestoapacketdelay.Thetargetexecutionhasits prexdetermineduntilandincludingthiscollisionin E 1 .Whichofthetwocasesholds dependsonthealgorithmconsidered.Thisconstructioniscontinuedbybuildingprexes ofgrowinglengths.Eachtimeweconsidertheexecutionwithitsprexdeterminingthe targetexecution,wenextexaminethesufxafterthisprexforoneofthetwopossible casesasabove.Theobtainednalexecutionhasthepropertythatthereareinnitelymany voidroundsinwhichnopacketisheard,whilesimultaneouslytheadversaryinjectswith therateofonepacketperroundontheaverage.Thisconcludestheargumentthatthe injectionrate1istoomuchtoprovideboundedpacketlatency.Thisobservationcanbe strengthenedtosmallerinjectionrateswithamoreinvolvedargument,asweshownextin Theorem15. Ifanexecutionistobeofaboundedpacketlatency,anactivestationneedstohave sufcientlymanyopportunitiestotransmititspackets.Inparticular,ifacertainround isnotcheckedforthepossibilityofastationbeingactivatedinthisroundandgivenan opportunitytotransmitatleastonepacket,thenthereexistsanexecutioninwhichastation is activatedinthisroundindeedanditspacketsareneverheardonthechannel. Thisisrepresentedformallyasfollows,foranexecutionofabroadcastalgorithm onanadhocchannel.Wesaythat roundvisveriedinrounds oftheexecutionif eitherthestationthatgotactivatedintheround v transmitsforthersttimeinround s intheexecutionornostationgotactivatedintheround v butsuchastationwouldhave 88

PAGE 97

transmittedforthersttimeinround s ifitwereactivatedintheround v intheexecution. Weusethephrasestation v isveriedinterchangeablywithround v isveriedaswe willconsideronly1-activatedadversariessothatatmostonestationgetsactivatedinany round.Intuitively,astationgetsveriedinaroundifitistherstroundinwhichthe stationgetsanopportunitytotransmit,unlessnostationgotactivatedintheroundthat identiesthestation.Wewillalwaysassumethatifastation v isveriedinround s then s v ,asotherwisethereisnostationtobeveried. Wesaythata vericationofstationvgetscompletedinroundw whenitistherst roundinwhichtheinteractionof v withthechannel,orlackthereof,certiesthat v does nothavependingpackets.Therearetwowaysinwhichsuchacerticationcouldoccur. Oneiswhenastationidentiedbythenumber v istobecomeveriedintheround w andnostationhasbeenactivatedinround v so v doesnottransmitatall.Anotherwayis when v isstillactiveinround w andtransmitsitslastpacketinthisroundtoimmediately becomepassive. Ifastation v isveriedinaround s thenthenumber s )]TJ/F49 11.9552 Tf 11.535 0 Td [(v iscalledthe delayof vericationofv .Observethatifanalgorithmhaspacketlatencyatmost t inanyexecution againstsomeadversary,thentheroundsinanyexecutionagainstthisadversaryareveried withthedelayatmost t .Thisisbecauseifsomeround r getsveriedlaterthanattheround r + t insomeexecution E 1 thenconsideranexecution E 2 inwhichastationisactivatedin round r anditspacketneedstowaitbeyondtheround r + t tobeheard,whichviolatesthe boundonpacketlatency.Onemayargueaboutunboundedpacketlatencybyspecifying anexecutioninwhichdelaysofvericationgrowunbounded.Thisishowthenextfactis proved. Theorem15 Nodeterministicdistributedalgorithmcanprovideboundedpacketlatency againsta 1 -activatedadversaryofinjectionrategreaterthan 3 4 andwithburstinessat least 2 89

PAGE 98

Proof: Letusconsideranydeterministicdistributedalgorithm A anda1-activatedadversaryofatype r ; b ,wheretheinjectionrate r satises 3 4 < r 1and b 2.We determineexecutionsofthisalgorithmbyforeseeingtheactionsofthestationsasdirected bythealgorithm A andhavetheadversaryactaccordingly. Wemakethefollowingassumptionsaboutalgorithm A tosimplifytheexpositionof thearguments.Wemayassumethatasuccessfultransmissionbyastationisfollowedby othertransmissionsofthisstation,aslongasthestationhaspendingpackets,untilthey areexhausted.Wemayassume,withoutlossofgenerality,thatthestationsareveriedin theorderoftheiractivation,asthisismostrestrictivefortheadversary.Thismeansthat nostation v isveriedinaround w whenthereexistsanumber k < v suchthattheround k hasnotbeenveriedbytheround w Webuildaspecicexecution E bydeterminingcontiguoussegmentsofuptofour rounds,whichwecall portions .Atanystageoftheconstruction,theportionsmakea prexoftheexecution E ,initiallyitistheemptyprex.Weconsiderapossibleextension ofagivenprex,andthenspecifywhattheadversary'sdoes.Theadversaryinjectspackets intoastationonlyonceatthetimeofitsinitialization. Let P bethealreadydeterminedprexof E .Weconsideraportionin E thatimmediatelyfollows P ,whichwedenoteby S .Wewillcategorizetheseportionsbythecases givenbelow.Theportionsfallingunderonecasearecalled similar .Whensuchaportion S hasthepropertiesthat S consistsoffourroundsandtheadversarymaycauseexactly fourstationstobeveriedin S whenallowedonlytousetheinjectionrate 3 4 butifthe injectionrate r issuchthat r > 3 4 thentheadversarycanmakeinnitelymanysimilar portionsresultinfewerthanfourstationsveried,assumingthattherewillbeinnitely manysuchsimilarportions,thensuchaportioniscalled critical .Weconsideronlythe stationsscheduledtobeveriedinsuchaportion S ,usuallyfourofthem.Ifstationswith greaternumbersthanthefourscheduledtobeveriedin S wanttobeveriedin S ,then theadversarycouldactivatetherstofthem.Thiswouldresultinacollision,whichcan beshownbyextendingtheargumentalongthelinesofwhatwedescribenextwhenjust 90

PAGE 99

fourconsecutivestationsareconsidered.Therearethefollowingcasestocategorizethe portions S Therstcaseoccurswhenintheroundjustaftertheprexnovericationisscheduled bythealgorithm.Thenweextend E byaddingthisroundtotheprex. Thesecondcaseoccurswhenthereareuptothreeconsecutivevericationsscheduled,subjecttothepropertythatiftherstvericationiscompletedinoneroundbya lackoftransmissionthenthesecondsimilarhappens,andsoonuptothree,butatmost thefourthonewouldinvolvemultipleverications.Theadversarydoesnotactivateany oftheveriedstationsandtheportionofuptothreeroundsisaddedtotheprex. Thethirdcaseoccurswhentherewouldbefourconsecutivevericationsofsingle roundsjustaftertheprex P iftheadversarydidnotactivateanyofthesestations.Let theadversarydonotactivatetherstofthesestations v andactivatethesecond v + 1with twopackets.Thisstation v + 1transmitssuccessfullyinthesecondroundoftheportion andnexttimeinthethirdround.Ifthestation v + 2istobeveriedconcurrentlyinthe thirdround,thentheadversaryactivates v + 2withonepacket,whichresultsinacollision inthethirdroundof S .Nowthebestscenarioforthealgorithmistohavethepacketof v + 1heardinthefourthroundof S .Such S resultsinadelaybecauseonlytwostations havebeenveriedinit.Ifthisishowthingshappenthenweextendtheprexbythis S Ifthestation v + 2isnottobeveriedconcurrentlyinthethirdround,sothatonly v + 1 transmits,thenthistransmissionissuccessful.Nowtherearesub-cases.Ifnostationor only v + 2istobeveriedinthefourthround,thentheadversarydoesnotactivate v + 2 atall,andjustthreeroundsareveriedin S andweadd S afterthecurrentprex.Ifboth v + 2and v + 3aretobeveriedinthefourthround,thentheadversarydoesnotactivate anyofthem,becauseitcouldbeatmostonesuchastationwiththeinjectionrate 3 4 .This isacriticalportionatthispointbecauseanactivationofboth v + 2and v + 3wouldresult inacollisionandsoadelayofverication.Weaddthisportion S afterthecurrentprex. Thefourthcaseoccurswhenatleasttwostationsarescheduledtobeveriedinthe sameroundoftheportion S offourroundsimmediatelyfollowingtheprex P ,whichis 91

PAGE 100

brokenintothreesubcases.Moreprecisely,wemeanthateitheraatleasttwostations arescheduledtobeveriedintherstroundof S ,orbatmostonestation v intherst roundof S andifthereisnotransmissionthenatleasttwostationsarescheduledtobe veriedinthesecondround,ornallycatmostonestation v intherstroundof S and ifthereisnotransmissionthenalsoatmostonestationinthesecondroundandwithat leasttwostationsscheduledtobeveriedinthethirdround.Inthesubcasea,when v and v + 1arescheduledtobeveriedintherstroundof S thentheadversaryactivates eachofthesestationssothereisacollisionintherstroundof S .Nowthebestcasefor thealgorithmisfor v and v + 1tocompletetheirvericationbytransmissionsinthenext tworoundsof S ,andfor v + 2and v + 3totransmittogetherinoneroundof S .Ifthisis whatoccursthentheadversarydoesnotactivateneither v + 2nor v + 3,andthisbecomes acriticalportion,becausewiththepossibilityoftwoactivationstheadversarycouldcreate acollisionandsoadelayinthefourthround.Ifsuchabestcasedoesnotoccurthenthis meansthateither v + 2or v + 3isscheduledtobeveriedinaroundinwhichoneof v and v + 1transmitssolo,andthentheadversaryactivatesthisstationtobeveriedwhich resultsinacollisionandsoadelay.Weextendtheprexoftheexecutionby S ineachof thesecases.Inthesubcaseb,whenatmostonestation v isveriedintherstroundof S andifthereisnotransmissionthenatleasttwostationsarescheduledtobeveriedin thesecondround,thentheadversarydoesnotactivate v butactivates v + 1and v + 2.This resultsinsilenceintherstroundandacollisioninthesecond.Evenwhen v + 1and v + 2 completetheirvericationsintheroundsthreeandfouroftheportion S ,thenthisresults inadelayofverication,soweaddtheportion S asis.Inthesubcasec,whentherst tworoundscouldbesilent,thentheadversarydoesnotactivate v and v + 1butactivates v + 2and v + 3.Thisresultsinthersttwosilentroundsfollowedbyacollisioninthe thirdround.Nowwhateverhappensinthethirdround,andthebestcaseforthealgorithm iswheneither v + 2or v + 3completesverication,stilloneof v + 2and v + 3cannot completeitsvericationin S sothereisadelay.Weaddthisportion S asjustspecied. 92

PAGE 101

Theexecution E isobtainedwiththeadversary'sbehaviorconsistentwithinjection rate 3 4 .Thisexecutionhasthepropertythateitherthereareinnitelymanyportionswith delayorinnitelymanycriticalportions.Iftheformeristhecasethenwearedone,since theobtainedexecutionhasunboundedpacketdelays.Otherwise,weconstructanew executioninwhichtheadversary'sbehaviorisconsistentwiththeinjectionrate r > 3 4 Theadversary'sbehaviorisasiftheinjectionratewere 3 4 untilitcaninjectonemoreextra packettocreateadelayinaportionthatotherwisewouldbecategorizedascritical.The adversarycancreateanexecutionwithanunboundednumberofdelaysbecauseeither thereareinnitelymanydelaysortheopportunitytoconvertacriticalportiontoonewith delaywilloccurinnitelytimes,duetotheinequality r > 3 4 Theorem15demonstratesadifferencebetweentheadversarialmodelofad-hocchannelswiththemodelofchannelsinwhichstationsknowthexednumberofstationsattachedtothechannelandtheirnames,asinthatmodelboundedpacketlatencycanbe attainedforanyinjectionratelessthan1,see[11,12],andmerestabilitycanbeobtained evenfortheinjectionrate1,asitwasdemonstratedin[30]. 9.3Activationbasedprotocols Weproposetwoactivation-basedalgorithms,whichhandledifferentrangesofinjectionrates,dependingonwhethertheyareadaptiveornot.Thealgorithmsapplya paradigmtoimplementaglobalqueueofstationstofacilitatecoordinationamongstationsintheirattemptstotransmit.Oneofthesequeuesusesthelast-in-rst-outqueuing disciplineandtheothertherst-in-rst-outqueuingdiscipline. 9.3.1Anon-adaptiveprotocol Wedevelopanon-adaptiveactivation-basedalgorithmwhichwecallC OUNTING B ACKOFF .Itisdesignedforchannelswithcollisiondetection.Theunderlyingparadigm ofalgorithmC OUNTING -B ACKOFF isthatactivestationsmaintainaglobalvirtualstack, thatis,alast-in-rst-outqueue.Eachstationneedstorememberitspositiononthestack, whichismaintainedasacounterwiththeoperationsofincrementinganddecrementing 93

PAGE 102

byone.Thestationatthetopofthestackhasthecounterequaleithertozeroorone.The algorithmappliestherulethatifacollisionoftwoconcurrenttransmissionsoccursthen thestationactivatedearliergivesuptemporarily,understoodasgivingupthepositionat thetopofthestack,whilethestationactivatedlaterpersistsintransmissions,understood asclaimingthetoppositiononthestack. / ifthisistherstroundafteractivationthen backoff_counter = 0 / ifbackoff_counter 1 then transmitamessage feedback feedbackfromthechannel iffeedback =collision thenbackoff_counter backoff_counter + 1 elseiffeedback =silence thenbackoff_counter backoff_counter )]TJ/F18 11.9552 Tf 10.95 0 Td [(1 elseiffeedback =ownmessage then if stillactive thenbackoff_counter 1 else backoff_counter 0 Figure9.1: A LGORITHM C OUNTING -B ACKOFF codeforoneroundofastationactive inthebeginningofaround. ThepseudocodeofProtocolC OUNTING -B ACKOFF ispresentedintheFigure9.1. Everystationhasaprivateinteger-valuedvariable backoff_counter ,whichissettozero whenthestationispassive.Thecopiesofthevariable backoff_counter aremanipulated bytheactivestationsaccordingtothefollowinggeneralrules.Anactivestationtransmitsa packetinaroundwhenit backoff_counter isatmostone.Whenacollisionoccurs,then eachactivestationincrementsits backoff_counter byone.Whenasilentroundoccurs, theneachactivestationdecrementsits backoff_counter byone.Whenamessageis heardthenthecounters backoff_counter arenotmodied,withthepossibleexception ofastationactivatedinthepreviousround. 94

PAGE 103

Astationthatgetsactivatedinitiallypreservesits backoff_counter equaltozero, sothestationtransmitsintheroundjustaftertheactivation.Suchastationincrementsits backoff_counter inthenextround,unlessitsonlypacketgotheardonthechannel,in whichcasethestationbecomespassive.Astationthattransmitsanditspacketisheard withholdsthechannelandkeepstransmittinginthefollowingrounds,unlessitdoesnot haveanyotherpendingpacketsoracollisionoccurs.Thevariables backoff_counter are manipulatedsuchthattheyimplementpositionsonastack,andtherebyserveasdynamic temporarynamesforthestationsthatareotherwisenameless.Thispreventsconictsfor accessamongthestationsthatarealreadyinthestack.Next,wemaketheseintuitions precise. Weusetheconventiontorefertoastationactivatedinround t asthestation t andto itsprivatevariable backoff_counter as backoff_counter t Lemma11 Whenanactivestationexecuting C OUNTING -B ACKOFF hasits backoff_counter positiveattheendofaround,thenthisvaluemaybeinterpretedasthisstation'sposition onaglobalstackofstations,withtheactivestationwhose backoff_counter = 1 placedatthetop. Proof: Wearguethatthefollowingstrongerinvariantismaintainedinanexecutionof algorithmC OUNTING -B ACKOFF :iftherearesome k > 0stationsactiveinthebeginning ofaroundthen,attheendofthisround,eachsuchastationthatremainsactivehasa differentvalueofits backoff_counter fromtheinterval [ 1 ; k ] ,assignedintheinverse orderoftheiractivation.Thisisshownbyinductionontheroundnumber.Therstround issilentsothebaseofinductionholds.Consideranarbitraryround t + 1 > 1andassume thattheinvariantholdspriortothisround.Inround t + 1,eitherapacketisheard,orthe roundissilent,orthereisacollisioninit.Nextweconsidereachofthesethreecases. Whenapacketisheardinround t + 1,thentherearetwosubcasesdependingon whethersomestationwasactivatedinround t ornot.Therstsub-caseoccurswhena station t gotactivatedinround t .Atthispoint backoff_counter t equalszero,which 95

PAGE 104

resultsin t transmittingitspacket.Bytheinductiveassumption,thestackisemptyat round t ,becauseotherwisethestationatitstopwouldhavetransmittedinround t + 1 andcreatedacollision.Ifstation t isstillactiveafterthetransmission,then t sets backoff_counter t 1andbecomestherstonthestack,otherwisethestackremains empty.Thesecondsub-caseoccurswhennostationgotactivatedinround t .Then,by theinductiveassumption,thestationatthetopofthestacktransmittedinround t + 1.If afterthetransmissionthisstationisstillactive,thennothingchangesinthearrangement ofthestationsinthestack,andifthetransmittingstationbecomespassive,thenitresets backoff_counter backtozero,whichisinterpretedasthisstationleavingthestack. Thenextcaseoccurswhenround t + 1issilent.Thismeansthatnostationonthe stackhas backoff_counter equaltoone,sothateitherthestackisemptyorthereisat leastonestationonthestackwithits backoff_counter equaltotwo.Inthelattercase, eachstationonthestackdecrementsits backoff_counter byone,makingitsvaluethe truepositiononthestack. Thenalcaseisofacollisioninround t + 1.Thismeansthatsomestationhasits backoff_counter equaltooneandsoisatthetopofthestack,whileanotheronehas itequaltozero,whichmeansitisastationnewlyactivatedinround t .Noweachactive stationincrementsits backoff_counter byone,whichresultsininsertingthestation t at thetopofthestack. Theorem16 Whenalgorithm C OUNTING -B ACKOFF isexecutedagainsta 1 -activation adversaryoftype r ; b ,where r < 1 3 ,thenthereareatmost 3 2 bpacketsqueuedinany roundandthepacketlatencyisatmost 6 b 1 )]TJ/F18 8.9664 Tf 6.966 0 Td [(3 r Proof: Weconsiderstrategiesbytheadversarytodelaypackets.ByLemma11,itisthe packetatthebottomofthestackthatisdelayedlongest,soaboundontimeittakesto startwithmakinganemptystacknonemptytohavingitbecomeemptyagainisaboundon packetlatency.Theadversarymaychooseastrategytouctuatethesizeofthestack,but byrearrangingtheactions,withintheconstraintsimposedbytheadversary'sspecication, 96

PAGE 105

wemayreduceeachstrategytoyieldingatleastthesameboundonpacketlatencyandsuch thatitisintwoparts:intherstpart,theadversaryworkstokeepthestackgrowingas muchaspossible,andinthesecondpart,theadversaryworkstokeepthestackdecreasing insizeasslowlyaspossible.Wealsoconsiderapacketinjectedintotherstactivated stationandestimateitsdelay,asthentheadversaryisnotadditionallyconstrainedby previousinjections.Observethatitisadvantageous,withthegoaltoincreasepacket delay,tokeepaddingstationstothestackwithjustonepackettotransmitratherthanwith multiplepackets.Weassumethroughoutthat b > 1,asotherwisetheadversarycanapply onlyveryrestrictedstrategies. Thestrategytomaximizepacketlatencyisasfollows.Intherstround,injecttwopacketsintostation1.Inthesecondround,station1transmitsandsets backoff_counter 1,whileonepacketisinjectedintostation2.Inthethirdround, stations1and2transmitsimultaneously,station1setsits backoff_counter 2and station2sets backoff_counter 1,whileonepacketisinjectedintostation3.This continuesforamaximumpossiblenumber L ofrounds,where L satisestheequality L = b )]TJ/F18 11.9552 Tf 10.888 0 Td [(1 + r L sothat L = b )]TJ/F18 8.9664 Tf 6.966 0 Td [(1 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r .Thenumberofpacketsafterthese L roundsis p 1 = L )]TJ/F18 11.9552 Tf 10.887 0 Td [(1 andthebottompackethaswaited p 1 + 1 = L rounds.Thenumber L )]TJ/F18 11.9552 Tf 10.61 0 Td [(1istheupperbound onthenumberofpacketsqueued.Wehave L = b )]TJ/F18 8.9664 Tf 6.966 0 Td [(1 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r < 3 2 b ,because1 = 1 )]TJ/F50 11.9552 Tf 11.115 0 Td [(r < 3 2 when theinequality r < 1 3 holds.Atthispoint,theadversarycannotcontinuewithanewactivationperround,immediatelyforatleastoneround,whichresultsinoccasionalsuccessful transmissions,whileatthesametimeactivatingnewstationsbyinjectingsinglepackets intothemasoftenaspossible.Whattheadversarywantstoobtainistospendthreerounds foronestation:collision,hearing,silence. Nextweestimatethetimeittakesfortheglobalvirtualstacktobecomeempty.To transmit p 1 packetsrequiresatmost3 p 1 rounds.Duringtheserounds,upto3 r p 1 = p 2 newpacketsareinjected.Observethat p 2 < p 1 as r < 1 3 .Ittakesatmost3 p 2 roundsto transmit p 2 packets.Duringtheserounds,upto3 r p 2 = 3 r 2 p 1 = p 3 newpacketsare injected.Thispatternisiteratedtodeterminethenumbers p i sothatittakesatmost3 p i 97

PAGE 106

roundstotransmit p i packets.During3 p i roundsupto 3 r p i = 3 r i p 1 = p i + 1 newpacketsinjected.Thetimeforthistooccurisatmost: L + 3 p 1 + 3 p 2 + 3 p 3 ::: = L + 3 p 1 1 + 3 r + 3 r 2 + ::: L + 3 L 1 )]TJ/F18 11.9552 Tf 10.95 0 Td [(3 r ; .1 whereweusedtheinequality p 1 < L .Theright-handsideof.1canbeupperbounded by 3 b 2 1 + 3 1 )]TJ/F18 11.9552 Tf 10.95 0 Td [(3 r 3 b 2 4 1 )]TJ/F18 11.9552 Tf 10.949 0 Td [(3 r 6 b 1 )]TJ/F18 11.9552 Tf 10.949 0 Td [(3 r ; becauseoftheinequality L = b )]TJ/F18 8.9664 Tf 6.967 0 Td [(1 1 )]TJ/F50 8.9664 Tf 6.967 0 Td [(r < 3 2 b WecanobservethatalgorithmC OUNTING -B ACKOFF onchannelswithcollisiondetectionisnotfairwheninjectionrateis 1 3 and b > 1.Toseethis,considerthefollowing execution.Lettheadversaryactivate b )]TJ/F18 11.9552 Tf 10.68 0 Td [(1stationsin b contiguousrounds,therststation activatedwithtwopacketsandthefollowingstationsactivatedwithonepacketperstation. Afterthat,lettheadversarykeepactivatinganewstationonceineverycontiguoussegmentofthreeroundsbyinjectingasinglepacketintoit.Thisresultsinacollisioninevery thirdround,inatransmissionineverythirdround,andinsilenceineverythirdround,to theeffectthatthestacknevergetsemptyandthepacketatitsbottomisneverheard. 9.3.2Anadaptivealgorithm Wepresentanadaptiveactivation-basedalgorithmwhichwecallQ UEUE -B ACKOFF Theunderlyingparadigmisthatactivestationsmaintainaglobalvirtualrst-in-rst-out queue.Thisapproachisimplementedbythestipulationthatifacollisionoccurs,caused bytwoconcurrenttransmissions,thenthestationactivatedearlierpersistsintransmitting whilethestationactivatedlatergivesuptemporarily.Thisisadualalternativetotherule usedinalgorithmC OUNTING -B ACKOFF Assumerstthatthechanneliswithcollisiondetection.Thepseudocodeofalgorithm Q UEUE -B ACKOFF isinFigure9.2. 98

PAGE 107

/ intheroundofactivation: queue_size = queue_position = collision_count = 0 / if 0 queue_position 1 then transmitamessage feedback feedbackfromthechannel iffeedback =collision then ifqueue_size > 0 thenqueue_size queue_size + 1 elseifqueue_size = 0 then queue_position )]TJ/F18 11.9552 Tf 29.747 0 Td [(1; collision_count collision_count + 1 elseiffeedback =aforeignmessagewith K > 0 andqueue_position = )]TJ/F18 11.9552 Tf 9.289 0 Td [(1 then queue_size K ; queue_position K )]TJ/F79 11.9552 Tf 10.949 0 Td [(collision_count elseiffeedback =aforeignmessagewiththeoverbitattached then queue_size queue_size )]TJ/F18 11.9552 Tf 14.557 0 Td [(1; queue_position queue_position )]TJ/F18 11.9552 Tf 10.949 0 Td [(1 elseiffeedback =ownmessage andqueue_size = 0 and stillactive then queue_size 1; queue_position 1 Figure9.2: A LGORITHM Q UEUE -B ACKOFF foroneroundofanactivestationwhenthe channeliswithcollisiondetection. 99

PAGE 108

Everystationhasthreeprivateinteger-valuedvariables: queue_size queue_position and collision_count ,whichareallsettozeroinapassivestation.Thevaluesofthese variablesrepresentastation'sknowledgeabouttheglobaldistributedvirtualqueueofstations,ascapturedbyLemma12. Amessagetransmittedonthechannelincludesapacketandthevalueofthesender's variable queue_size ;ifthisisthelastpacketfromthesender'squeuethenamarkerbit overisalsosetoninthemessage.Inaround,anactivestationwhose queue_position equalseitherzerooronetransmitsamessage.Theprivatevariablesaremanipulated accordingtothefollowingrules.Whenacollisionoccurs,theneachactivestation withapositivevalueof queue_size incrementsits queue_size byonewhileanactivestationwith queue_size = 0incrementsits collision_count byoneandsets queue_position )]TJ/F18 11.9552 Tf 23.367 0 Td [(1.Whenamessagewithsomevalue K > 0of queue_size isheard andanactivestationhas queue_position = )]TJ/F18 11.9552 Tf 9.289 0 Td [(1,thenthestationsets queue_size K and queue_position K )]TJ/F52 11.9552 Tf 10.972 0 Td [( collision_count )]TJ/F18 11.9552 Tf 10.972 0 Td [(1 .Whenamessagewiththeover bitisheard,theneachactivestationdecrementsitsvariables queue_position and queue_size byone.Whenastationisstillactive,ithasjusthearditsownmessage andits queue_size equalszero,thenthestationsetsitsvariable queue_size 1and queue_position 1;thisoccurswhentheglobalvirtualqueueisempty. Someoftheunderlyingideasofthisalgorithmaresimilartothoseusedinthedesign ofalgorithmC OUNTING -B ACKOFF ,theyareasfollows.Astationthatbecomesactivated transmitsinthenextroundafteractivation,asthenits queue_position isstillzero.A stationthattransmitsandthetransmittedmessageisheardwithholdsthechannelbytransmittinginthefollowingrounds,subjecttopacketavailability.Thisworksbecausethe rsttransmissioniswith queue_position equaltoeitherzerooroneandthefollowing oneswith queue_position equaltoone.Acollisioninaroundmeansthatsomenew stationgotactivatedinthepreviousround,becausethestationthathastransmittedmultipletimes,withnootherstationsuccessfullyintervening,hasits queue_position equal toone,whiletheonlyotherpossibilityistohavethisvariableequaltozero,whichisonly 100

PAGE 109

possiblewheninheritedfromthestatewhenstillapassivestation.AdifferencewithalgorithmC OUNTING -B ACKOFF isthatanactivestationcannotreceivesilenceasfeedback fromthechannel.ThisisbecauseQ UEUE -B ACKOFF isadaptiveandtheoverbitin messageseliminatessilentroundswhentherearesomeactivestations. Lemma12 Whenthe queue_position ofanactivestationexecuting Q UEUE -B ACKOFF ispositivethenthisvaluemaybeinterpretedasthenumberofthisstation'spositiononaglobalrst-in-rst-outqueueofstations,withtheactivestationforwhich queue_position = 1 beingatthefront. Proof: TherearetwoinvariantsthatholdtrueinanyexecutionofalgorithmQ UEUE B ACKOFF Therstinvariant:thestationswhosevariable queue_size ispositivestore inthisvariablethenumberofactivestations. Theproofofthisinvariantisbyinductionontheroundnumber.Whentherstactive stationstaysactiveforatleasttworounds,thenthissetsitsvariable queue_size toone. Theinductivestepisbytherulesofmanipulationoftheinstanceofthisvariable,namely, theoverbitdecreasesthevalueandacollisionincreasesitbyoneateachstation. Thesecondinvariant:attheendofaround,eachstationhasadifferentvalueofthenumberdenedaseither queue_position ,inthecase queue_position > 0,orthenumberofactivestationsactivatedpriortothe currentrounddecrementedbythevalueofthevariable collision_count ,in thecase position_in_queue = 0,andthesenumberslltheinterval [ 1 ; k ] where k isthenumberofactivestations. Theproofofthisinvariantisbyinductionontheconsecutiveroundnumbers.Weconsider casesdependingonwhatisthefeedbackfromthechannel.Silentroundsoccurwhen therearenoactivestationsactivatedpriortothecurrentround.Oncethefeedbackfrom 101

PAGE 110

thechannelisdifferentfromsilence,itiseitherhearingamessageoracollision.A messagebringsthenumberofactivestations,anditallowstoupdate queue_position ifitcomesafteraseriesofcollisions,bythespecicationofthealgorithmandtherst invariantthat queue_size representsthenumberofactivestationsifheardinamessage. Acollisionresultsinthestationsthatdonotknowthenumberofactivestationsrecord theiroffsetfromthenextsuccessfultransmissionbycountingcollisions.Thesevaluesare alldifferentasthereisatmostonestationactivatedinaround. Thesecondinvariantimpliesthatonceamessageisheardandthereare k activestationsthen,attheendofaround,eachsuchstationhasdifferentvalueof queue_position allthesevaluesllingtheinterval [ 1 ; k ] andassignedintheorderofactivation. Theorem17 Whenalgorithm Q UEUE -B ACKOFF isexecutedagainsta 1 -activationadversaryoftype 1 2 ; b thenthereareatmost 2 b )]TJ/F18 11.9552 Tf 11.556 0 Td [(3 packetsqueuedinanyroundand packetlatencyisatmost 4 b )]TJ/F18 11.9552 Tf 10.949 0 Td [(6 Proof: Theadversarymaychooseastrategytouctuatethesizeofthequeueaccording toanypattern,butbyrearrangingtheactions,subjecttotheconstraintsimposedbythe adversary'sspecication,wemayreducethepatternofuctuationswithoutcompromising theworstpossibleboundonpacketlatency.Suchareducedstrategyisintwoparts.In therstpart,theadversaryworkstokeepthequeuegrowingasmuchaspossible.Inthe secondpart,theadversaryworkstokeepthesizeofthequeuedecreasingasslowlyas possible. Theactivestationsmaybeinterpretedasbeingstoredinaglobalrst-in-rst-out queue,byLemma12.Thebeststrategyoftheadversaryistomaximizepacketlatency istorstbuildaqueueofmaximumsizeandthenslowdownitsevolutionwhenstations cannotbestoppedtomovetowardsthefront.Themaximumpacketlatencyisthetime spentinthequeuebythepacketinjectedatthemomentwhentheglobalqueueattainsits maximumsize.Thisstrategyisimplementedasfollowsbytheadversary. 102

PAGE 111

Intherstround,theadversaryinjectstwopacketsintotherststation.Inthesubsequentrounds,theadversaryactivatesastationperroundbyinjectingonepacketintoit. Thiscontinuesforamaximumpossiblenumber y ofrounds,where y satisestheequality y = b )]TJ/F18 11.9552 Tf 11.362 0 Td [(1 + 1 2 y sothat y = 2 b )]TJ/F18 11.9552 Tf 11.362 0 Td [(1 .Thenumberofpacketsafterthese y roundsis y )]TJ/F18 11.9552 Tf 11.23 0 Td [(1 = 2 b )]TJ/F18 11.9552 Tf 11.23 0 Td [(3.Thenumber y )]TJ/F18 11.9552 Tf 11.231 0 Td [(1istheupperboundonthenumberofpacketsqueued atanytime.Next,theadversaryinjectsasoftenaspossible,whichmeansateveryother round.Thisresultsinalternatingcollisionsandmessagesheardonthechannel.Each packetintheglobalqueueneedstworoundstomoveonepositionclosertothefront.This meansthatapacketwaitsthenumberofroundsthatisatmosttwicethemaximumsizeof theglobalqueue,whichis4 b )]TJ/F18 11.9552 Tf 10.949 0 Td [(6. ProtocolQ UEUE -B ACKOFF wasdiscussedasimplementedforchannelswithcollision detection.Wemayobservethatanexecutionhasthepropertythatwhentheglobalqueue isnonemptytheneachroundcontributeseitheracollisionoramessageheardonthe channel.Thismeansthatcollisionscanbedetectedasvoidroundsbyanyinvolvedactive station,whilepassivestationsdonotparticipateanyway.Itfollowsthatthisalgorithmcan beexecutedonchannelswithoutcollisiondetectionwithsmallmodicationsonlyand withnochangeinitsperformance. 9.4Fullsensingprotocols Stationsrunningfull-sensingalgorithmscanlistentothechannelatalltimesandso theymayhaveasenseoftimebymaintainingcommonreferencestopastrounds.Anidea couldbetoproceedthroughconsecutivepastroundstogivestationsactivatedintheman opportunitytotransmit,andthenwithholdthechannelifneededtounloadalltheirpackets. This,justbyitself,mayresultinunboundedpacketlatency,ifwespendatleastoneround toverifyanypastround,forapossibleactivationinit,becauserecurringwithholdingof thechannelwouldaccrueunboundeddelays.Topreventthisphenomenonfromoccurring, wemayconsidergroupsofconsecutiveroundsandhavestationsactivatedintheserounds transmitinthesameround.Therelevanteffectisthatifatmostonestationgotactivated 103

PAGE 112

inagroupthenwesaveatleastoneroundofverication,whichcompensatesforadelay duetowithholdingthechannel.Onthelevelofimplementation,itisnotnecessaryto maintainacounterofexaminedrounds,asitwouldgrowunbounded,instead,onecould countthenumberofroundssincethelatestroundexaminedforastationactivatedinit. Theseparadigmsareemployedinthealgorithmspresentedinthissection. Channelsareassumedtobewithcollisiondetectionthroughoutthewholesection. Wewillrefertotheactivestationsbytherespectiveroundsoftheiractivation. 9.4.1Anon-adaptivealgorithm Weproposeanon-adaptivefull-sensingalgorithmwhichwecallT RIPLED -R OUNDS Thealgorithmoperatesbyhavingtheroundsofanexecutionpartitionedintogroupsof consecutivethreeroundspergroup;thesegroupsarecalled segments .Simultaneously,an executionispartitionedintophases,thepurposeofaphaseistoverifyalltheroundsof therespectivesegment.Aphasebeginsbythestationsactivatedinroundsthatbelongto asegmenttransmittingtogether.Astationthathasitspackettransmittedwithholdsthe channeltounloadallitspackets.Asilentroundindicatesthatwithholdingthechannelby astationisover. Thefollowingistheunderlyingideawhatcanbeexploitedforsufcientlysmallinjectionrates.Whenaninjectionrateissmallerthan 2 3 ,thenlessthantwostationsget activatedinasegmentontheaverage.Inthecasewhenonestationgetsactivatedina segment,thenjustoneroundisspenttohearonepacketandanotheroneroundtoclose itstransmissions.Thismakestworoundstogetherandissmallerthanthelengthofthe segmentwhoseroundswewanttoverify. 104

PAGE 113

if thisistherstroundofaphase andlast_examined 3 and last_examined )]TJ/F18 11.9552 Tf 10.949 0 Td [(2 waiting_time last_examined then transmitamessage feedback feedbackfromthechannel iffeedback =silence then thisroundendsthephase elseiffeedback =collision and v isrstinsegment then v becomes current elseiffeedback =message then thephasebecomesaone-stationsegment else if v iscurrent then transmitamessage feedback feedbackfromthechannel iffeedback =silence then if thephaseisone-station-segmentorcurrentisthirdstationinthesegment then thisroundendsthephase elseif v isnextafterthecurrentstation then v becomescurrent last_examined last_examined + 1 if thisroundendsthephase thenlast_examined last_examined )]TJ/F18 11.9552 Tf 10.796 0 Td [(3 if v isstillactive thenwaiting_time waiting_time + 1 Figure9.3: A LGORITHM T RIPLED -R OUNDS foroneroundofanactivestationv. 105

PAGE 114

ProtocolT RIPLED -R OUNDS hasitspseudocodesummarizedinFigure9.3.Eachstationhastwoprivatevariables waiting_time and last_examined ,eachinitializedto zero.Theirinterpretationissuchthatvariable waiting_time denotesthenumberof roundssincetheactivationofthestation,and last_examined isthenumberofrounds thathavepassedfromthelastroundveried,whichmeansexaminedforexistenceofa stationactivatedinit,tothecurrentround.Thevariable last_examined ismanipulated byeachstation,includingpassiveones,ineachround.Thisvariableistreatedasacounter ofrounds,inthatitgetsincrementedbyonewitheachpassinground.Thisisjustiedbecausethedistancetothatroundgrowsbyonewitheachpassinground.Onceastationgets activated,thenitsvariable waiting_time isalsotreatedasacounterofrounds,thatis,it getsincrementedbyonewitheachpassinground,untilthestationgetspassiveagainand setsthisvariableequaltozero.Theincrementsbyoneofthesevariables,whenapplicable, occurindependentlyofanyotheroperationsonthevariables,includingdecrementing,as discussednext.Thismeansthatavariablecanbeincrementedanddecrementedinthe sameround. Anexecutionispartitionedinto phases speciedasfollows.Ifavariable last_examined isatmosttwothenaphaseconsistsofasingleroundinwhichnostationtransmitswhile thevariable last_examined getsincrementedbyone.Otherwise,when last_examined isatleastthree,thena phasewithpossibletransmissions occurs,whichtakescareof packetsinatmostthreeactivestationsthathavewaitedlongestsincetheiractivations; allsuchthreestations,whicheverofthemexist,maketogether thesegmentofthephase Thesestationsareidentiedbythefollowingproperties: therststationinthesegment isdeterminedby waiting_time = last_examined ,ifitexists,and thesecondstationin thesegment isdeterminedby waiting_time = last_examined )]TJ/F18 11.9552 Tf 11.126 0 Td [(1,ifitexists,and the thirdstationinthesegment has waiting_time = last_examined )]TJ/F18 11.9552 Tf 10.992 0 Td [(2,ifitexists.When astationsucceedsintransmittinginaround,thenitiscalledthe current one.Acurrent stationwithholdsthechanneltounloaditspackets.Whenaphasebegins,thestations initssegmenttransmittogether.Ifthisroundresultsinsilencethenthisconcludesthe 106

PAGE 115

phase,asthismeansthatthesegmentisempty.Ifamessageisheard,thenthephaseis calleda one-station-segment .Thestationthattransmittedtheheardmessagewithholdsthe channeltounloadallitspackets,andwhenthisisoverthenasilentroundconcludesthe phase.Ifthereisacollision,then,rst,therststationinthesegmentunloadsitspackets onebyone,followedbyasilentround,possiblyjustonesilentroundoccurs.Next,the secondstationinthesegmentunloadsitspacketsonebyone,concludedbyasilentround. Finally,thethirdstationinthesegmentunloadsitspackets,concludedbyasilentround, whichendsthephase.Whenaphaseisover,theninitslastroundeachstation,includingpassiveones,decrementsitsvariable last_examined bythreeandanewphasestarts fromthenextround. Thevariables last_examined and waiting_time havecomplementaryroles,inthat theformerprovidestheidentityofthelast-examinedround,representedasthedistance fromthecurrentroundcountedbackwardsintime,whilethelatterisequaltothenumber ofroundsastationhasbeenactive.Thisinterpretationismadevalidbythenexttwofacts. Lemma13 Thevariable last_examined hasthesamevalueateachstationatthe endofaround. Proof: Thevariable last_examined isinitializedtozerointhebeginningofanexecution.Nextitisupdatedbyeachstationinexactlythesameway.Namely,itisincremented byoneineachround,anditsdecrementedby3attheendofaphasewithpossibletransmissions,whichisdeterminedbythefeedbackfromthechannel,thesameforeachstation. Lemma14 Thevariable waiting_time hasauniquevalueateachactivestationat theendofaround. Proof: Weexaminehowtheinstancesofthisvariablearemanipulated.Whenastation getsactivated,thenitisuniqueamongtheactivestationsinhaving waiting_time still equaltozero,asitistheonlystationactivatedintheround.Alltheotheractivestations 107

PAGE 116

havetheirvaluesofthevariabledifferentandgreaterthanzero,aseachofthemhad anopportunitytoincrementitbyoneatleastonce.Thestationsactiveatthismoment incrementtheir waiting_time valuesbyoneinunison,sotheyallstaydistinct. Itfollows,fromLemmas13and14,thattheimplementationofalgorithmT RIPLED R OUNDS bywayofusingvariables last_examined and waiting_time iscorrect,as thesevariablesdeterminethesegmentsandeachstations'spositioninoneofthem. Theorem18 Whenalgorithm T RIPLED -R OUNDS isexecutedagainsta 1 -activationadversaryoftype r ; b ,where r < 2 3 ,thenthereareatmost b 2 )]TJ/F18 8.9664 Tf 6.967 0 Td [(3 r packetsqueuedinany roundandpacketlatencyisatmost 3 b 2 )]TJ/F18 8.9664 Tf 6.967 0 Td [(3 r Proof: Webeginbycomputingthelengthofeachkindofphases.Werestrictourattention tothecasewhenastationisactivatedwithasinglepacket,asthisismostadvantagesto theadversary.Aphaseofasilentroundtakesoneround.Aphasethatstartswithhearinga messagelaststworounds.Aphasewithtwostationsactivatedinit,saytheywereactivated inthersttworoundsofthesegment,takessixrounds,becauseitconsistsofcollision, message,silence,message,silence,andthenalsilence.Aphasewiththreestationsactivatedinittakessevenrounds,becauseitconsistsofcollision,message,silence,message, silence,message,andthenalsilence.Intermsofdelayperinjectedpacket,activating twostationspersegmentismostadvantageoustotheadversary,aseachinjectedpacket contributesthreeroundstothecorrespondingphase. Itfollowsthatthestrategyoftheadversarytomaximizethenumberofqueuedpackets andtheirdelaysistocreatethelongestpossiblecontiguousintervalofsegmentssuchthat eachhaspreciselytwostationsactivatedinit.Let L bethelengthofsuchanintervalof rounds.Itsatisestheequation 2 3 L = b + r L ,whichdetermines L = 3 b 2 )]TJ/F18 8.9664 Tf 6.967 0 Td [(3 r ;weassume,to simplifynotationthat L isanintegerdivisiblebythree. Whenthelastsegmentintheinitialintervalof L roundsiscompleted,halfofithas alreadybeenveried,becausetherateofvericationishalfoftherateoftime'sow. Whatisavailableforvericationatthispointisanintervalof L = 2rounds.Thereare 108

PAGE 117

2 3 1 2 L = b 2 )]TJ/F18 8.9664 Tf 6.967 0 Td [(3 r packetsinqueuesatthismoment,whichistheirpeaknumber.Thissegment isveriedintime2 1 2 L = 3 b 2 )]TJ/F18 8.9664 Tf 6.967 0 Td [(3 r ,whichisanupperboundonpacketlatency. 9.4.2Anadaptivealgorithm Wedevelopanadaptivefull-sensingalgorithmwhichwecallP AIRED -R OUNDS .Itis basedontheideatohavegroupsoftwoconsecutiveroundsofanexecutionpairedtogether. Thestationsinthesamegroupareveriedforactivationinanyoftheroundsofagroup bytransmittingtogether.ThisresemblestheapproachofalgorithmT RIPLED -R OUNDS thedifferenceisinhavingsmallergroupsoftwostationsonlyandinusingcontrolbits inmessages.MostoftheterminologyweintroducedforalgorithmT RIPLED -R OUNDS is applicable,afterreplacingreferencestothreestationsbythecorrespondingonestotwo stations. Anexecutionofthealgorithmispartitionedintogroupsoftwoconsecutiverounds, eachcalleda segment ,similarlyasinSection9.4.1.Theconsecutiveseriesofrounds spentonthevericationoftheroundsinasegmentisthe phase correspondingtothis segment.Whentherstmessagetransmittedbyastationisheardinanyround,thenthe stationwithholdsthechanneltounloadallitspackets.Thelastpackettransmittedby astationhastheoverbitattachedtothemessagetoindicatethatthestationbecomes passive.Aphasebeginswiththetwostationsactivatedinaroundofthephase'ssegment, ifany,transmittingtogether.Asilencemeansanimmediateendofthephase.If,instead,a messageisheard,thenthetransmittingstationunloadsitspackets,withamessagewiththe overbitconcludingthephase.Ifacollisionoccursthentherststationofthesegments beginsitstransmissions,whichisfollowedbythesecondstation'stransmissions.Inthe caseofeachstationactivatedwithasinglepacket,ittakesthreeroundstoverifyasegment oftworounds:collisionandhearingmessagestwice,eachwiththeoverbit.Thisdelay occurssufcientlyseldomtoprovidestabilityifinjectionrateisatmost 3 4 .Toseethis, considertwoconsecutivesegments,comprisingfourconsecutiveroundsintotal.Onthe average,atmostthreestationsgetactivatedinthem,sooneofthesegmentsisveried 109

PAGE 118

forthecostofonlyoneround,forasavingofoneround,andthetotaloffourrounds toverifythetwosegmentsoffourrounds.Thismayseemasnoprogresswithrespect ofthemethodtohavegroupsofsingletonroundsandaphasetoconsistofverifyingone station.Ifsothenthiswouldbetroubling,asthenaiveapproachtoverifyonestationper roundissusceptibleofacumulativedelaygrowingunbounded,duetoburstinessavailable totheadversarywhocanmakesomestationswithholdthechannelformorethanone round.ThisphenomenondoesnotoccurinanexecutionofalgorithmT RIPLED -R OUNDS becausetheadversaryneedstowithholdactivationsthroughsomeroundstobeableto injectmorethanonepacketperstationlater,withthiswithholdingresultinginaspeedup, ofoneroundspenttoverifyasegmentoftworounds. 110

PAGE 119

if thisistherstroundofaphase andlast_examined 2 and last_examined )]TJ/F18 11.9552 Tf 10.949 0 Td [(1 waiting_time last_examinedthen transmitamessage feedback feedbackfromthechannel iffeedback =silence then thisroundendsthephase elseiffeedback =collision and v istherstinsegment then v becomes current elseiffeedback =amessage then thephasebecomesaone-stationsegment iffeedback =amessagewiththeoverbitattached then thisroundends thephase else if v iscurrent then transmitamessage feedback feedbackfromthechannel iffeedback =amessagewiththeoverbitattached then if thephaseisaone-station-segment or thecurrentstationissecondin segment then thisroundendsthephase elseif v isnextafterthecurrentstation then v becomescurrent last_examined last_examined + 1 if thisroundendsthephase thenlast_examined last_examined )]TJ/F18 11.9552 Tf 10.949 0 Td [(2 if v isstillactive thenwaiting_time waiting_time + 1 Figure9.4: A LGORITHM P AIRED -R OUNDS codeforoneroundofanactivestationv. 111

PAGE 120

ProtocolP AIRED -R OUNDS hasitpseudocodepresentedinFigure9.4.Eachstation hastwoprivateinteger-valuedvariables waiting_time and last_examined ,eachinitializedtozero.Theroleofthesevariablesascountersateachstation,includingpassive ones,issimilartohowtheyareusedbyalgorithmT RIPLED -R OUNDS .Aninstanceofthe variable last_examined getsincrementedbyoneineachroundineverystation,includingpassiveones.Onceastationgetsactivated,thenitsvariable waiting_time alsogets incrementedbyoneineachround,untilthestationgetspassive,whenitisresettozero. Theincrementsbyoneofthesevariableoccurindependentlyofotheroperationsonthe variables,includingdecrementing,whicharediscussednext. Nowweexplainhowphasesareimplemented.If last_examined isatmostone thenaphaseconsistsofasingleroundinwhichnostationtransmits;inthisroundthe variable last_examined getsincrementedbyone.Otherwise,when last_examined isatleasttwo,thena phasewithpossibletransmissions occurs,whichtakescareofthe packetsintheactivestationsthathavewaitedlongestsincetheiractivations.Thesestations areidentiedbytheproperties waiting_time = last_examined and waiting_time = last_examined )]TJ/F18 11.9552 Tf 11.218 0 Td [(1;theformeristherstinthesegmentandtheotheronethesecond inthesegment.Whenaphasebegins,thestationswithoneofthesepropertiestransmit together.Ifasilenceoccurs,thenthisconcludesthephase.Ifamessageisheard,then thestationthattransmitteditkeepsunloadingitspackets,thelastpacketwiththeover bit,whichconcludesthephase.Ifthereisacollision,then,therststationinthepair unloadsitspacketsrst,thelastpacketwiththeoverbit,andthesecondstationinthe pairunloadsitspacketsnext,thelastpacketwiththeoverbit,whichendsthephase. Whensuchaphaseisover,theninitslastroundeachstationdecrementsitsvariable last_examined by2andanewphasestartsfromthenextround. ThefactsanalogoustoLemmas13and14holdtrueforalgorithmP AIRED -R OUNDS sothattheimplementationofalgorithmP AIRED -R OUNDS bywayofusingvariables last_examined and waiting_time iscorrect,byanalogywithalgorithmT RIPLED R OUNDS 112

PAGE 121

Theorem19 Whenalgorithm P AIRED -R OUNDS isexecutedagainsta 1 -activationadversaryoftype 3 4 ; b ,thenthereareatmost 4 3 bpacketsqueuedinanyroundandpacket latencyisatmost 2 b. Proof: Therearethreekindsofphases:ofnoactivestation,ofoneactivestation,andof twoactivestations.Aphaseoftheformertwokindslastoneroundeach,assumingthat anactivestationholdsjustonepacket,andaphaseofthelatterkindtakesthreerounds. Thereforeitisadvantageousfortheadversaryaimingtomaximizethenumberofqueued packetsandpacketlatencytocreateaslonganintervaloftroublingsegments,requiring threeroundstoverifyasegment,aspossible.Letusconsideranintervalof L rounds inwhicheachroundcontributesanactivestationbytheadversaryinjectingonepacket intoit.Then L satisestheequation L = b + 3 4 L ,sothat L = 4 b .Bythetimethelast ofthesestationsisactivated, 2 3 L stationsactivatedrstgetveried.Whatstillremains tobeveriedare 1 3 L = 4 3 b stations,eachholdingonepacket,whichmeansthat 4 3 b isan upperboundonthenumberofqueuedpackets.Ittakes 3 2 4 3 b = 2 b roundstoverifythese stations,whichisanupperboundonpacketlatency. 113

PAGE 122

9.5Conclusion Wehaveintroducedadhocmultipleaccesschannelsalongwithanadversarialmodel ofpacketinjectioninwhichdeterministicdistributedalgorithmscanhandlenon-trivial injectionrates.Theseratesmaketheincreasingsequenceof 1 3 1 2 2 3 ,and 3 4 ,corresponding totheincreasingpowerofalgorithms.Thehighestinjectionratethatwecanhandlewith boundedpacketlatencyis 3 4 anditisshowntothebestpossible,whichmeansthatalgorithmP AIRED -R OUNDS isoptimal.Theoptimalityoftheotherthreeprotocolsintheir respectiveclassesisopen.Onthelowestendofthisspectrum,injectionratesarbitrarilycloseto 1 3 butsmallerthanthisnumberwereshowntobehandledbyanon-adaptive activation-basedalgorithmonchannelswithcollisiondetectionwithaboundedpacket latency.Itisanopenquestionifanon-adaptiveactivation-basedalgorithmcanprovide boundedpacketlatencyforsufcientlysmallpositiveinjectionratesonchannels without collisiondetection. 114

PAGE 123

10.Openproblemsandfuturework Herewegivesomeoftheopenproblemsandfuturework.Lowerboundsforthe deterministicprotocolsisstillopenandneedstobestudied.Themodelwithindividual injectionratescanbefurtherextendedtoleakybucketadversaries. Theexperimentsuserandomizationinpacketinjection.Theoreticalworkthatis closertothesimulationenvironmentthatusesrandomizationisanopenproblem.We haveonlystudiedtheworstcasequeuesandlatency.Onecouldinvestigatetheaverage queuesandlatencyandpossiblyworkondevelopingnewprotocolsthatareoptimalforan averagecaseratherthanaworstcase.Little'sformulaisafundamentalresultthatrelates averagequeues,averagelatencyandaveragerateofarrivalofpacketsinaqueuingsystem.Itisasfollows."Thelong-termaveragequeuesinastablesystem L isequaltothe long-termaverageeffectivearrivalrate, l ,multipliedbytheaveragetimeapacketspends inthesystem, W ;or L = l W ".IfLittle'sformulaholdsforanadversarialmodelofpacket injectionisalsoanopenproblem. 115

PAGE 124

REFERENCES [1]N.M.Abramson.Developmentofthealohanet. IEEETransactionsonInformation Theory ,31:119,1985. [2]W.Aiello,E.Kushilevitz,R.Ostrovsky,andA.Rosn.Adaptivepacketroutingfor burstyadversarialtrafc. J.Comput.Syst.Sci. ,60:482,2000. [3]H.Al-Ammal,L.A.Goldberg,andP.D.MacKenzie.Animprovedstabilitybound forbinaryexponentialbackoff. TheoryofComputingSystems ,34:229,2001. [4]D.J.Aldous.Ultimateinstabilityofexponentialbackoffprotocolfor acknowledgment-basedtransmissioncontrolofrandomaccesscommunicationchannels. IEEETransactionsonInformationTheory ,33:219,1987. [5]C.lvarez,M.J.Blesa,J.Daz,A.Fernndez,andM.J.Serna.Thecomplexity ofdecidingstabilityunderffsintheadversarialqueueingmodel. Inf.Process.Lett. 90:261,2004. [6]C.lvarez,M.J.Blesa,J.Daz,M.J.Serna,andA.Fernndez.Adversarialmodels forpriority-basednetworks. Networks ,45:23,2005. [7]C.lvarez,M.J.Blesa,andM.J.Serna.Universalstabilityofundirectedgraphsin theadversarialqueueingmodel.In SPAA ,pages183,2002. [8]C.lvarez,M.J.Blesa,andM.J.Serna.Theimpactoffailuremanagementon thestabilityofcommunicationnetworks.In Proceedingsofthe10thInternational ConferenceonParallelandDistributedSystemsICPADS ,pages153,2004. [9]C.lvarez,M.J.Blesa,andM.J.Serna.Theimpactoffailuremanagementonthe stabilityofcommunicationnetworks.In ICPADS ,pages153,2004. [10]L.AnantharamuandB.S.Chlebus.Broadcastinginadhocmultipleaccesschannels. 2013.Submitted. [11]L.Anantharamu,B.S.Chlebus,D.R.Kowalski,andM.A.Rokicki.Deterministic broadcastonmultipleaccesschannels.In Proceedingsofthe 29 thIEEEInternationalConferenceonComputerCommunicationsINFOCOM ,pages1,2010. [12]L.Anantharamu,B.S.Chlebus,D.R.Kowalski,andM.A.Rokicki.Mediumaccesscontrolforadversarialchannelswithjamming.In Proceedingsofthe 18 thInternationalColloquiumonStructuralInformationandCommunicationComplexity SIROCCO ,LNCS6796,pages89,2011. 116

PAGE 125

[13]L.Anantharamu,B.S.Chlebus,andM.A.Rokicki.Adversarialmultipleaccess channelwithindividualinjectionrates.In Proceedingsofthe 13 thInternational ConferenceonPrinciplesofDistributedSystemsOPODIS ,LNCS5923,pages 174,2009. [14]M.Andrews,B.Awerbuch,A.Fernndez,F.T.Leighton,Z.Liu,andJ.M.Kleinberg.Universal-stabilityresultsandperformanceboundsforgreedycontentionresolutionprotocols. JournaloftheACM ,48:39,2001. [15]M.AndrewsandL.Zhang.Stabilityresultsfornetworkswithinputandoutput blocking.In STOC ,pages369,1998. [16]M.AndrewsandL.Zhang.Achievingstabilityinnetworksofinput-queued switches. IEEE/ACMTrans.Netw. ,11:848,2003. [17]M.AndrewsandL.Zhang.Routingandschedulinginmultihopwirelessnetworks withtime-varyingchannels. ACMTransactionsonAlgorithms ,3:33,2007. [18]B.Awerbuch,A.W.Richa,andC.Scheideler.Ajamming-resistantmacprotocolfor single-hopwirelessnetworks.In PODC ,pages45,2008. [19]E.Bayraktaroglu,C.King,X.Liu,G.Noubir,R.Rajaraman,andB.Thapa.On theperformanceofIEEE802.11underjamming.In Proceedingsofthe 27 thIEEE InternationalConferenceonComputerCommunicationsINFOCOM ,pages1265 1273,2008. [20]M.A.Bender,M.Farach-Colton,S.He,B.C.Kuszmaul,andC.E.Leiserson.Adversarialcontentionresolutionforsimplechannels.In Proceedingsofthe 17 thAnnualACMSymposiumonParallelAlgorithmsSPAA ,pages325,2005. [21]V.BhandariandN.H.Vaidya.Reliablebroadcastinwirelessnetworkswithprobabilisticfailures.In Proceedingsofthe 26 thIEEEInternationalConferenceonComputerCommunicationsINFOCOM ,pages715723,2007. [22]V.BhandariandN.H.Vaidya.Reliablebroadcastinradionetworkswithlocally boundedfailures. IEEETransactionsonParallelandDistributedSystems ,21:801 811,2010. [23]R.Bhattacharjee,A.Goel,andZ.Lotker.Instabilityoffoatarbitrarilylowratesin theadversarialqueueingmodel. SIAMJ.Comput. ,34:318,2004. [24]G.Bianchi.PerformanceanalysisoftheIEEE802.11distributedcoordinationfunction. IEEEJournalonSelectedAreasinCommunications ,18:535547,2000. [25]M.Bie nkowski,M.Klonowski,M.Korzeniowski,andD.R.Kowalski.Dynamic sharingofamultipleaccesschannel.In Proceedingsofthe 27 thInternationalSymposiumonTheoreticalAspectsofComputerScienceSTACS ,LeibnizInternational ProceedingsinInformatics,vol.5,pages83.SchlossDagstuhlLeibniz-Zentrum fuerInformatik,2010. 117

PAGE 126

[26]A.Borodin,J.M.Kleinberg,P.Raghavan,M.Sudan,andD.P.Williamson.Adversarialqueuingtheory. JournaloftheACM ,48:13,2001. [27]A.Z.Broder,A.M.Frieze,andE.Upfal.Ageneralapproachtodynamicpacket routingwithboundedbuffers. JournaloftheACM ,48:324,2001. [28]B.S.Chlebus,K.Goab,andD.R.Kowalski.Broadcastingspanningforestsona multipleaccesschannel. TheoryofComputingSystems ,36:711,2003. [29]B.S.Chlebus,D.R.Kowalski,andA.Lingas.Performingworkinbroadcastnetworks. DistributedComputing ,18:435,2006. [30]B.S.Chlebus,D.R.Kowalski,andM.A.Rokicki.Maximumthroughputofmultiple accesschannelsinadversarialenvironments. DistributedComputing ,22:93, 2009. [31]B.S.Chlebus,D.R.Kowalski,andM.A.Rokicki.Adversarialqueuingonthe multipleaccesschannel. ACMTransactionsonAlgorithms ,8:5,2012. [32]J.Czy zowicz,L.Gasieniec,D.R.Kowalski,andA.Pelc.Consensusandmutualexclusioninamultipleaccesschannel. IEEETransactiononParallelandDistributed Systems ,22:1092,2011. [33]S.Dolev,S.Gilbert,R.Guerraoui,F.Kuhn,andC.C.Newport.Thewirelesssynchronizationproblem.In PODC ,pages190,2009. [34]S.Dolev,S.Gilbert,R.Guerraoui,andC.C.Newport.Gossipinginamulti-channel radionetwork.In DISC ,pages208,2007. [35]R.G.Gallager.Aperspectiveonmultiaccesschannels. IEEETransactionsonInformationTheory ,31:124,1985. [36]S.Gilbert,R.Guerraoui,D.R.Kowalski,andC.Newport.Interference-resilient informationexchange.In Proceedingsofthe 28 thIEEEInternationalConference onComputerCommunicationsINFOCOM ,pages2249,2009. [37]S.Gilbert,R.Guerraoui,andC.C.Newport.Ofmaliciousmotesandsuspicioussensors:Ontheefciencyofmaliciousinterferenceinwirelessnetworks. Theoretical ComputerScience ,410-7:546,2009. [38]L.A.Goldberg,M.Jerrum,S.Kannan,andM.Paterson.Aboundonthecapacityofbackoffandacknowledgment-basedprotocols. SIAMJournalonComputing 33:313,2004. [39]L.A.Goldberg,P.D.MacKenzie,M.Paterson,andA.Srinivasan.Contentionresolutionwithconstantexpecteddelay. J.ACM ,47:1048,2000. [40]A.G.GreenbergandS.Winograd.Alowerboundonthetimeneededintheworst casetoresolveconictsdeterministicallyinmultipleaccesschannels. J.ACM 32:589,1985. 118

PAGE 127

[41]L.Guang,C.Assi,andA.Benslimane.MAClayermisbehaviorinwirelessnetworks:Challengesandsolutions. IEEEWirelessCommunications ,15:6, 2008. [42]J.Hstad,F.T.Leighton,andB.Rogoff.Analysisofbackoffprotocolsformultiple accesschannels. SIAMJournalonComputing ,25:740,1996. [43]J.HuiandM.Devetsikiotis.AuniedmodelfortheperformanceanalysisofIEEE 802.11eEDCA. IEEETransactionsonCommunications ,53:1498,2005. [44]IEEE.MediumaccesscontrolMACandphysicalspecications. IEEE P802.11/D10 ,January1999. [45]S.S.Jr.Alastwordon L = l W OperationsResearch ,22:417,1974. [46]S.Keshav. AnEngineeringApproachtoComputerNetworking:ATMNetworks,the Internet,andtheTelephoneNetwork .Addison-Wesley,1997. [47]J.KomlsandA.G.Greenberg.Anasymptoticallyfastnonadaptivealgorithmfor conictresolutioninmultiple-accesschannels. IEEETransactionsonInformation Theory ,31:302,1985. [48]Z.Kong,D.H.K.Tsang,B.Bensaou,andD.Gao.PerformanceanalysisofIEEE 802.11econtention-basedchannelaccess. IEEEJournalonSelectedAreasinCommunications ,22:2095,2004. [49]D.Koukopoulos,M.Mavronicolas,S.E.Nikoletseas,andP.G.Spirakis.Theimpact ofnetworkstructureonthestabilityofgreedyprotocols. TheoryComput.Syst. 38:425,2005. [50]B.-J.Kwak,N.-O.Song,andL.E.Miller.Performanceanalysisofexponential backoff. IEEE/ACMTransactionsonNetworking ,13:343,2005. [51]F.T.Leighton. IntroductiontoParallelAlgorithmsandArchitectures:Arrays,Trees, Hypercubes .MorganKaufmannPublishers,1992. [52]J.D.C.Little.Aproofofthequeueingformula L = l W OperationsResearch 9:383,1961. [53]Z.Lotker,B.Patt-Shamir,andA.Rosn.Newstabilityresultsforadversarialqueuing. SIAMJ.Comput. ,33:286,2004. [54]N.A.Lynch. DistributedAlgorithms .MorganKaufmannPublishers,1996. [55]D.Meier,Y.A.Pignolet,S.Schmid,andR.Wattenhofer.Speeddatingdespite jammers.In Proceedingsofthe 5 thIEEEInternationalConferenceonDistributed ComputinginSensorSystemsDCOSS ,LNCS5516,pages1,2009. [56]R.M.MetcalfeandD.R.Boggs.Ethernet:Distributedpacketswitchingforlocal computernetworks. CommunicationsoftheACM ,19:395,1976. 119

PAGE 128

[57]A.Mpitziopoulos,D.Gavalas,C.Konstantopoulos,andG.Pantziou.Asurveyon jammingattacksandcountermeasuresinWSNs. IEEECommunicationsSurveys& Tutorials ,11:42,2009. [58]K.Pelechrinis,M.Iliofotou,andS.V.Krishnamurthy.Denialofserviceattacks inwirelessnetworks:Thecaseofjammers. IEEECommunicationsSurveysand Tutorials ,13:245,2011. [59]P.RaghavanandE.Upfal.Stochasticcontentionresolutionwithshortdelays. SIAM JournalonComputing ,28:709,1998. [60]A.Rosn.Anoteonmodelsfornon-probabilisticanalysisofpacketswitchingnetworks. Inf.Process.Lett. ,84:237,2002. [61]A.RosnandM.S.Tsirkin.Ondeliverytimesinpacketnetworksunderadversarial trafc. TheoryofComputingSystems ,39:805,2006. [62]C.ScheidelerandB.Vcking.Universalcontinuousroutingstrategies. Theoryof ComputingSystems ,31:425,1998. [63]G.Sharma,A.J.Ganesh,andP.B.Key.Performanceanalysisofcontention basedmediumaccesscontrolprotocols. IEEETransactionsonInformationTheory 55:1665,2009. [64]B.S.TsybakovandN.B.Likhanov.Upperboundonthecapacityofarandom multipleaccesssystem. ProblemyPeredachiInformatsii ,23:64,1987. [65]B.S.TsybakovandV.A.Mikhailov.Ergodicityofaslottedalohasystem. Problemy PeredachiInformatsii ,15:301,1979. [66]J.Walrand. AnIntroductiontoQueuingNetworks .PrenticeHall,1988. [67]E.ZiouvaandT.Antonakopoulos.CSMA/CAperformanceunderhightrafcconditions:throughputanddelayanalysis. ComputerCommunications ,25:313, 2002. 120