1
MACA- ANew Channel Access Method for Packet Radio
Phil Karn, KA9Q ABSTRACT
naTheexistingCarrierSenseMultipleAccess(CSMA) methodwidelyusedimateur packet radio on shared simplex packet radio channels frequently suffers from-lthe well-known"hiddenterminal problem" andthe less wellknown but related probemofthe"exposedterminal."Thispaperproposesanewscheme,MultipleAccesscwith Collision Avoidance(MACA), that couldgreatly relieve these problems.MACAan also be easily extended to provide automatic transmitter power control. This couldincrease the carrying capacity of a channel substantially.
n1.Introductio
Intheclassichiddenterminalsituation,astation Y can hear both stations X and Z, but Xnd Zcannotheareachother.XandZareothereforeunabletoavoidcollidingwitheachther at Y. (See figure 1.)Inthe exposedterminalcase(figure 2),a.Ewell-sited station X can hear far away station YventhoughXis toofarfromYtointerfereldwithits traffictoothernearby stations,Xwilefer to it unnecessarily, thus wasting an oppor-ttunitytoreusethechannellocally.Sometimeshere can be so much traffic in the remote areasithat the well-sited station seldom transmits. This a common problem with hilltop digipeaters.saThis paper suggests a new channel acceslgorithm for amateur packet radio use that caneAminimizeboth problems.This method,Multiplccess with Collision Avoidance (MACA), wasAinspired by the CSMA/CA method (used by thepple Localtalk network for somewhat differentsreasons)andbythe"prioritizedACK"schemeuggested by Eric Gustafson, N7CL, for AX.25.aItis notonlyan elegantsolution tothe hiddenndexposedterminalproblems,butwiththetnecessaryhardwaresupportitcanbeextendedodoautomaticper-packettransmitterpower"control.Thiscouldsubstantiallyincreasethecarryingcapacity"ofasimplexpacketradioa
channelusedforlocalcommunicationsin
MACA is an acronym, not a Spanish word.
1
denselypopulated area,thus satisfying boththernFCCmandatetouse"theminimumpoweecessarytocarryoutthedesiredcommunica-ations"(Part97.313)and to"contributetothedvancement of the radio art" (Part 97.1 (b)).
2.How CSMA/CA Works
CSMA/CA as used by Localtalk works asafollows.Whenastationwantsto senddatatonother,itfirstsendsashortRequestToSendrr(RTS)packettothedestination.ThereceiveespondswithaCleartoSend(CTS)packet.qOnreceiptoftheCTS,thesendersendsitsueueddatapacket(s).IfthesenderdoesnotRreceiveaCTSafteratimeout,itresendsitsTS andwaits alittle longerfor areply. This)ithree-step process (notcounting retransmissionsscalleda
dialogue
.Sinceadialogueinvolves-f transmissions by both stations, I will avoid conusion by referring to the station that sends theesRTS anddatapacketsasthe
initiator
, and thtation that sends the CTS as the
responder
.af The RTS packet tells a responder that datollows.Thisgivesthe responderachancetoyeprepare,e.g.,byallocatingbuffer space orbnteringa"spinloop"onaprogrammed-I/Ok uinterface.ThisisthemainreasonLocaltalses theCSMA/CAdialogue.TheZilog8530nbHDLCchipusedintheAppleMacintoshcaufferthe3-byteLocaltalkRTSpacketinitstnFIFO,butwithoutaDMApathtomemoryieeds the CPU to transfer data to memory as itarrives.TheCPU responds tothe arrival ofan
tRTS packetby returningaCTS andenteringa-2-ight read loop, waiting for the data to arrive.
2
n(A timeout prevents a system lockup if the dataever arrives.)AsisstandardforCSMAschemes,nCSMA/CA requires stations to stay off the chan-el when another transmission is already in pro-togress.CSMA/CAalsorequiresany station thaverhears an RTS or CTS packet directed else-twheretoinhibitits transmitter foraspecifiedime.This helps reduce the probability of acol-.TlisionwithasubsequentCTSordatapackethis is the CA or
CollisionAvoidance
partof rpCSMA/CA. However, collisions are not a majoroblem on Localtalk; the network is physicallyarsmall,carriersensingisfairlyrapid,thedatateisrelativelylow,and(ifthenetworkis.Pproperlybuilt)therearenohiddenterminalslain CSMA would work well, but there was lit-Rtle extra cost tothe CAfeature(given that theTS/CTS dialogue was already needed for other
3
reasons) so it was included.
.Turning CSMA/CA into MACA
nsHiddenandexposedterminalsaboundoimplexpacketradiochannels,andthismakestothemverydifferentfromLocaltalkandmosthertypes oflocal area networks.Whenhid-tadenterminalsexist,lackofcarrierdoesn’lwaysmeanit’sOKtotransmit.Conversely,rwhenexposedterminalsexist,presenceofcar-ierdoesn’talwaysmeanthatit’sbadtotltransmit. Inother words, the datacarrier detecine from yourmodemis often useless. SoI’llomakearadicalproposal: let’signore DCD!Intherwords,let’sgetridoftheCSincCSMA/CA.(It’stoohardtobuildgoodDCDircuits anyway...)Instead we’ll extend the CA part of whatk we’ll call MA/CA (or just plainMACA).Theey to collision avoidance is the effect that RTSntand CTS packets have on the other stations ohechannel.Whenastationoverhears anRTSntaddressedtoanotherstation,itinhibitsits owransmitter long enough for the addressed stationn
torespondwithaCTS.Whenastatio
It wouldbe nice ifwe could use this feature onp
2
acket radio with our programmed-I/O HDLC interfaces,i(e.g.,DRSI PCPA,PaccommPC-100).Unfortunatelyfour RTS/CTS packetscarry full source and destina-Ftion call signs, they would not fit into the 3-byte 8530IFOs.So high speed operation will still require eitherDMA oradedicated I/O processor.
overhears a CTS addressed to another station, itoinhibits itsown transmitter longenoughfor thetherstationto send its data.The transmitter isshinhibitedfor theproper time evenifnothingieard in response to an RTS or CTS packet.ZcFigure3showsanexample.StationannothearX’s transmissionstoY,but it
can
aChearY’sCTSpacketstoX.If ZoverhearsTS packet fromYto X,it willknow not toXtransmit until after Y has received its data from.Buthowdoes Zknow how long towaithafteroverhearingY’sCTS?That’s easy.Weave X, the initiator of the dialogue, include inositsRTSpackettheamountofdataitplanstend,and wehaveY, theresponder,echothatoinformationinitsCTSpacket.NoweveryoneverhearingY’sCTSknowsjusthowlongtotmwaittoavoidclobberingadatapacketthatiight not even hear.As long as the link between each pair of sstations in the network is reciprocal (i.e., all thetations have comparable transmitter powers andpreceivernoiselevels),thereceiptofaCTSacket by a station not party to a dialogue tellsiitthatif itwereto transmit,it would probablynterferewiththereceptionofdatabythesiresponder (the sender of the CTS). MACA thunhibitstransmissionwhenordinaryCSMAsrwouldpermitit(andallowacollision),thuelievingthehiddenterminalproblem.(Colli-tlsions are not
totally
avoided; more on this poinater.)Conversely, if a station hears no responsettto anoverheard RTS,thenit mayassume thahe intended recipient of the RTS is either downe4or out of range.An example is shown in figur.StationXis withinrangeof Y,butnotZ.pWhen Y sends traffic to Z, X will hear Y’s RTSacketsbutnotZ’sCTSresponses.Xmayf itherefore transmit on the channel without fear onterferingwithY’sdatatransmissionstoZ,Meventhoughitcanhearthem.In thiscaseACAallowsatransmissiontoproceedwhen,tordinaryCSMA wouldpreventitunnecessarilyhusrelievingtheexposedterminalproblem.a(Because modems have a capture effect, hearingCTS doesn’t
always
mean that you’d cause atycollisionifyoutransmit,sotheproblemisn’et completely solved. More on this point later.)
4.Metaphors for MACA
-3-MACAisnotreallyanovelidea;itt jmerely formalizes a procedure many people (noust radio amateurs) instinctively use in personalsconversation.Atypicalcocktailparty has manyimultaneous conversations.Theaverageguesthseldom waits for total silence in the room beforeespeaks,butifsomeoneasks himtopauseewbecauseheistryingtohearsomeoneelse,hillusuallydoso.TheMACA RTSpacketispanalogous to Bob saying "Hey, Tom!" and CTSacketisanalogoustoTomrespondingwithpt"Yeah,Bob?".Thiscauses mostpeople tostoalkingiftheyareclosetoTom(except,of -pcourse,for Bob).Thesamething(should)hapeninmanualamateurradiooperationwhen-oeverastationfinishesatransmission with"gonly" (or "KN" on CW or RTTY).soThe Prioritized ACK scheme also involveverheardpacketsthat inhibitother stationsfor-bspecified periods oftime.In this case,the inhiitingpacketisadatapacketand theprotectedynstation is sending an acknowledgement that maotbeaudibleattheinhibitedstations.Full(protectionagainstcollisionsisnotprovideddatapacketscanstillcollide)but theperfor-rmance improvement due to the lower ACK lossate is reported to be substantial.naMoreformally,MACAcan also beseesasingle-channel,time-multiplexedformof BBusyToneMultipleAccess(BTMA).InTMA,receiverstransmit"busytones"oneasecondarychannelswhenevertheirreceiversarctive.Thiswarnstheotherstationsinrangernthattheyshould nottransmitevenif theyheaothing on the data channel. On the other hand,tstationsnothearingbusytonesarefreetoransmit even if there is already a signal on theadata channel.Indeed, stations need not payanyttention at all to the data channel when decid-.Aingtotransmit;onlythebusychannelmattersslongasthepropagationcharacteristicsaretidentical between the main and secondary (busyone)channels,BTMAiseffective.Unfor--qtunately,theneedtouse widelyseparatedfreuenciestoavoidself-interferencetendsto.BmakethelinkcharacteristicslesssymmetricalTMAalsoobviouslyincreasesthehardwareucomplexityandspectrumrequirementsofeachser station. On the other hand, because MACAddusesthe samechannelfor the"busy tone" anata,pathsbetweenpairsofstationsare muchmore likely to be symmetrical.
5.Collisions in MACA
UnlikeBTMA,however,collisions.Tbetween RTS packets can still occur in MACAheseareminimizedwitharandomizedtuexponentialback-offstrategysimilartothased in regular CSMA.Since there is no carrierrsensinginMACA,eachstationsimply addsaandomamounttotheminimumintervaleachnRstationisrequiredtowaitafteroverhearingaTS or CTS packet. As in regular CSMA, this-tstrategyminimizesthechancethatseveralstaions will all jump on the channel at the instantlwitbecomesfree.Theextrarandomintervaould be an integral multiple of the "slot time",Rand in MACA the slot time is the duration of anTSpacket.IftwoRTSpacketscollidecnonetheless,eachstationwaitsarandomlyhosenintervalandtriesagain,doublingthe.Eaverageintervaloneachsuccessiveattemptventually one of them will "win" (i.e., transmitttfirst) and the CTS from its responder will inhibihe "losing" station until the winning station cancomplete its dialogue.Even though collisions can occur betweeneoRTSpackets,MACAstillhastheadvantagverCSMAaslongastheRTSpacketsareslsignificantlysmallerthanthedatapackets.Aongasthisistrue,collisionsbetweenRTS-spacketsare muchless"costly"thanthe colliionsthatwouldotherwiseoccurbetweendatasf packets. The savings in collision time also payor the overhead of the RTS and CTS packets.ApAsmentionedearlier,thebasicMACrotocolonly reduces thechancesof collisionstinvolvingdatapackets;itdoesnotguaranteehattheywillneveroccur.Thisisbecausea-tCTS packet requires acertainminimum signalo-noise ratio at a station for it to be understoodlmand obeyed.Even if the station powers are welatched,apairofstationsmighthavejustienough of a path between them to allow them tonterferewitheachother’sreceptionofweak tsignals, but not enough of a path to allow themo hear each other’s CTS packets.Although thesaseriousness of this problem is unknown, it doeppearthatthepower-controlledversionof
6
MACA discussed later would greatly reduce it.
.Bypassing the MACA Dialogue
etIf the data packets are of comparable sizotheRTSpackets,theoverheadofthescRTS/CTSdialoguemaybeexcessive.Inthiase, a station may choose to bypass the normal