MACAW: A Media Access Protocol for Wireless LaN's Vaduvur Bharghavan Department of Electrical Engineering and Computer Science University of California at Berkeley sharghav@cs. berkeley. edu Alan Demers Scott Shenker Lixia Zhang Palo Alto Research Center Xerox Corporation Idemers,shenkerlixia]@parc.xerox.com Abstract lation results may only apply to PARC's particular radio technology, we expect that some of the basic insight gaine de variety of mobile computing de will be more generally applicabl has emerged, including portables, palmtops, and personal Wireless media access protocols for a single channel can digital assistants. Providing adequate network connectivity typically be categorized as either token-based or multiple ac for these devices will require a new generation of wireless cess. For reasons we explain in the next section, we choose LAN technology. In this paper we study media access pro- the multiple access approach. Our work is based on MACA tocols for a Multiple Access, Collision Avoidance protocol first pro- Xerox Corporation's Palo Alto Research Center. We start posed by Karn [9] and later refined by Biba 3]. Using ith the MACa media access protocol first proposed by packet-level simulations of the wireless network to guide our Karn [9] and later refined by Biba [3] which uses an RTS- design, we suggest several modifications to MACA. We call CTS-DATA packet exchange and binary exponential back the resulting algorithm MACAW, in recognition of its ge- off. Using packet-level simulations, we examine various per nealogical roots in Karns original proposal. Our design is formance and design issues in such protocols. Our analysis bas four key observations. Fi leads to a new protocol, MACAW, which uses an RTS-CTS- ing Karn [9 ]and others [4, 12], that the relevant contention DS-DATA-ACK message exchange and includes a signifi is at the receiver, not sender. This renders the cal antly different backoff algorithm rier sense approach inappropriate. Second, we note that in contrast to Ethernets, congestion is location dependent 1 Introduction in fact, the first observation is irrelevant without the sec- ond. Third, we conclude that, to allocate media access fairly In recent years, a wide variety of mobile computing devices learning about congestion levels must be a collective enter have emerged, including palmtops, personal digital assis- prise. That is, the media access protocol should propagate ants, and portable computers. While the first portables congestion information explicitly rather than having each were designed as stand-alone machines, many of these new device learn about congestion independently. Fourth, the devices are intended to function as full network citizens media access protocol should propagate synchronization in- Consequently, a new generation of wireless network technol- formation about contention periods, so that all devices can gy is needed to provide adequate network connectivity for contend effectively. In particular, this that contention ese mobile devices. In particular, wireless local area net- for bandwidth should not just be initiated by the sending orks (LANs)are expected to be a crucial enabling technol device. While our proposed protocol provides enhanced per ogy in traditional office settings where such mobile devices for compared to MACA), we ha will be initially, and most heavily, utilized it is merely an initial attempt to deal with these challenges The media in a wireless network is a shared, and there are many ren maining unresolved design issues. esource; thus one of the key questions is how access to this This paper has 5 sections. In Section 2 we first pro- shared media is controlled. In this paper, we focus on medi vide some background on PARC's radio network and on the access protocols in wireless LANs. Our research has a dual MACA media access protocol. We then, in Section 3, discuss purpose. One goal is to develop a media access protocol for our modifications to MACA; we motivate these changes by se in the wireless network infrastructure being developed presenting simulation data for several different network con Laboratory at Xero figurations. We discuss remaining design issues in Section 4 alo Alto Research Center [7, 8]. The other goal is to explore and summarize our findings in Section 5. some of the basic performance and design issues inherent in wireless media access protocols, While our specific simu i we expect in future work to revisit the token-based approach and ssion to copy without fee all or part of this therwise, or to republish, requires a fee the ACM copyright le publicat 212
MACAW: A Media Access Protocol for Wireless LAN’s Vaduvur Bharghavan Department of Electrical Engineering and Computer Science University of California at Berkeley bharghav@cs.berkeley. edu Alan Demers Scott Shenker Lixia Zhang Palo Alto Research Center Xerox Corporation {demers, shenker, lixia}@parc.xerox. com Abstract In recent years, a wide variety of mobile computing devices has emerged, including portables, palmtops, and personal digit al assistants. Providing adequate network connectivity y for these devices will require a new generation of wireless LAN technology. In this paper we study media access protocols for a single channel wireless LAN being developed at Xerox Corporation’s Palo Alto Research Center. We start with the MACA media access protocol first proposed by Karn [9] and later refined by Biba [3] which uses an RTSCTS-DATA packet exchange and binary exponential backoff. Using packet-level simulations, we examine various performance and design issues in such protocols, Our analysis leads to a new protocol, MACAW, which uses an RTS-CTSDS-DATA-ACK message exchange and includes a significantly different backoff algorithm. 1 Introduction In recent years, a wide variety of mobile computing devices have emerged, including palmtops, personal digital assistants, and portable computers. While the first portables were designed as stand-alone machines, many of these new devices are intended to function as full network citizens. Consequently, a new generation of wireless network technology is needed to provide adequate network cormectivitY for these mobile devices. In particular, wireless local area networks (LAN’s) are expected to be a crucial enabling technology in traditional office settings where such mobile devices will be initially, and most heavily, utilized. The media in a wireless network is a shared, and scarce, resource; thus one of the key questions is how access to this shared media is controlled. In this paper, we focus on media access protocols in wireless LAN’s. Our research has a dual purpose. One goal is to develop a media access protocol for use in the wireless network infrastructure being developed in the Computer Science Laboratory at Xerox Corporation’s Palo Alto Research Center [7, 8]. The other goal is to explore some of the basic performance and design issues inherent in wireless media access protocols. While our specific simuPermission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given lation results may only apply to PARC’s particular radio technology, we expect that some of the basic insight gained will be more generally applicable. Wireless media access protocols for a single channel can typically be categorized as either token-based or multiple access. For reasons we explain in the next section, we choose the multiple access approach. 1 Our work is based on MACA, a Multiple Access, Collision Avoidance protocol first proposed by Karn [9] and later refined by Biba [3]. Using packet-level simulations of the wireless network to guide our design, we suggest several modifications to MACA. We call the resulting algorithm MACAW, in recognition of its genealogical roots in Karn’s original proposal Our design is based on four key observations. First we observe, following Karn [9] and others [4, 12], that the relevant contention is at the receiver, not the sender. This renders the carrier sense approach inappropriate. Second, we note that, in contrast to Ethernets, congestion is location dependent; in fact, the first observation is irrelevant wit bout the second. Third, we conclude that, to allocate media access fairly, learning about congestion levels must be a collective enterprise. That is, the media access protocol should propagate congestion information explicitly rather than having each device learn about congestion independently. Fourth, the media access protocol should propagate synchronize ation information about contention periods, so that all devices can cent end effectively. In particular, this means that cent ention for bandwidth should not just be initiated by the sending device. While our proposed protocol provides enhanced performance (as compared to MACA), we hasten to note that it is merely an initial attempt to deal with these challenges; there are many remaining unresolved design issues. This paper has 5 sections. In Section 2 we first provide some background on PARC’s radio network and on the MACA media access protocol. We then, in Section 3, discuss our modifications to MACA; we motivate these changes by presenting simulation data for several different network configurations. We discuss remaining design issues in Section 4 and summarize our findings in Section 5. 1 We expect in future work to revisit the token-based approach and make a more in-depth comparison. that copying is by permission of the Association of Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. SIGCOMM 94 -8/94 London England UK @ 1994 ACM 0-89791 -682 -4/94/0008 ..S3.50 212
or base station, to know about the presence of other devices 2.1 PARCs Nano-Cellular Radio Network It is important to note that, in the absence of noise, our The Computer Science Laboratory at Xerox C technology is symmetric; if a station a can hear a station B Palo Alto Research Center has developed 5 MHz en presence of nois radio technology [7; its low operating frequency sources(e. g, displays) may interfere with this symmet multipath effects, and thus it is suitable for use and in our simulations we will consider the effect of noi wireless lan. The lan infrastructure consists of " base sta However, noise is not so prevalent that we make it the over- tions”, which are installed in the ceiling,and“pads”, which riding factor in our design; rather, we design our protocol are custom built portable computing devices(see [8 for a to tolerate noise well but we have done most of our testing more complete description). There is a single 256kbps chan in a noise-free settin base station ( the base stations are connected together by an access or token-based"these approaches are eithess to a sin- are inan signal strength. The range of transmission is 3 to 4 me- proach over the token approach for two reas ters, and the near-field signal strength decays very rapidly multiple access schemes are typically more robust. This is posed to ar-in the far- field region) obtain, around each base station, a very small cell(roughly pect the pads to be highly mobile and, given the sm all cell cell interference is negligible, the aggregate band width in a would state frequent token hand-offs or recovery in a multi-cell environment is quite hi token-based schem A collision"occurs when a receiver is in the reception One common wireless multiple access algorithm, cur- range of two transmitting stations, and is unable to cleanly rently used in radio, is sense(CSMA). In the receive signal from either station. "Capture"occurs when next sectio es and argue, following Karn [9] and [4,12,th CSMA approach is in tions, but is able to cleanly receive signal from the closer appropriate for our setting station; this can only occur if the signal power ratio is larg (a 10db or more). This requires a distance ratio of a 1.5 2.2 CSMA Perhaps surprisingly, this ratio is rather hard to achieve given that the base stations are in the ceiling and the pad In CSMA, every station senses the carrier before transmit- re typically no higher than a meter or so above the floor. ting; if the station detects carrier then the station defers transmission(CSMA schemes differ as to when the tran Roughly, this gives a minimum pad-to-base distance of just under 2 meters in a cell whose radius is just over 3 meters. mission is tried again). Carrier sense attempts to avoid col Thus, in our environment, capture will be relatively rare, lisions by testing the signal strength in the vicinity of the transmitter. However, collisions occur at the receiver, not and is not a primary design consideration the transmitter; that is, it is the presence of two or more n r transmitting station and slightly out-of-range of another transmitting station, but is unable to cleanly receive the ion. Since the receiver and the sender are typically not closer station's signal because of the interfering presence of information for collision avoidance. Two examples illustrate this point in more detail. Consider the configuration de- makes interference rather rare in our environment, and we picted in Figure 1. Station A can hear B but not C, and do not make it a major factor in our design. noring both capture and interference leads to a station C can hear station B but not A(and, by symmetry, we know that station B can hear both a and C or out-of-range of one another, and a station successine mple model in which any two stations are either in-ra receives a packet if and only if there is exactly one active B transmitter within range of it. In designing our protocol we often use this model accompanied by the additional sumptions that no two base stations are within range of each Figure 1: Station B can hear both A and C, but a and C other, and that no pad is within range of two different bas cannot hear each other. A" hidden terminal" scenario re stations. This is an extremely poor model for far-field ra- sults when C attempts to transmit while a is transmitting dios. It is not quite so poor for our near-field radios, but it to B. An "exposed terminal"scenario results if B is trans- is still far from realistic. We have not used this naive model mitting to A when C attempts to transmit in any of our simulations, but we do use it for intuitive jus- 3 Controlling access to a shared media is much easier if transmit(perhaps to B or perhaps to some other station) locations of the various devices are known. However in our setting there is no independe urce of location this produces a collision at B. Station C's carrier sense did information for the pads. There is no way for a pad to know not provide the necessary information since station A was that it is leaving a cell except through the loss of signal from the base station. Furthermore, there is no way for a pad, 3 We will use the term station to refer to both pads and base then can we make a vald comparison between the two approach 213
2 Background 2.1 PARC’s Nano-Cellular Radio Network The Computer Science Laboratory at Xerox Corporation’s Palo Alto Research Center has developed 5 MHz “near-field” radio t ethnology [7]; its low operating frequency eliminates multipath effects, and thus it is suitable for use in an indoor wireless LAN. The LAN infrastructure consists of “base stations”, which are installed in the ceiling, and “pads”, which are custom built portable computing devices (see [8] for a more complete description). There is a single 256kbps channel, and all wireless communication is between a pad and a base station (the base stations are connected together by an Ethernet). All base stations and pads transmit at the same signal strength. The range of transmission is 3 to 4 meters, and the near-field signal strength decays very rapidly (X .-3, as opposed tow r-’ in the far-field region). We thus obtain, around each base station, a very small cell (roughly 6 meters in diameter) with very sharply defined boundaries: a “nanocell”. Given that the cells are very small and intercell interference is negligible, the aggregate bandwidth in a multi-cell environment is quite high. A “collision” occurs when a receiver is in the reception range of two transmitting stations2, and is unable to cleanly receive signal from either station. “Capture” occurs when a receiver is in the reception range of two transmitting stations, but is able to cleanly receive signal from the closer station; this can only occur if the signal power ratio is large (w 10db or more). This requires a distance ratio of x 1.5. Perhaps surprisingly, this ratio is rather hard to achieve, given that the base stations are in the ceiling and the pads are typically no higher than a meter or so above the floor. Roughly, this gives a minimum pad-to-base distance of just under 2 meters in a cell whose radius is just over 3 meters. Thus, in our environment, capture will be relatively rare, and is not a primary design consideration. “Interference” occurs when a receiver is in range of one transmitting station and slightly out-of-range of another transmitting station, but is unable to cleanly receive the closer station’s signal because of the interfering presence of the other signal. The rather sharp decay in signal strength makes interference rather rare in our environment, and we do not make it a major factor in our design. Ignoring both capture and interference leads to a very simple model in which any two stations are either in-range or out-of-range of one another, and a station successfully receives a packet if and only if there is exactly one active transmitter within range of it. In designing our protocol, we often use this model accompanied by the additional assumptions that no two base stations are within range of each other, and that no pad is within range of two different base stations. This is an extremely poor model for far-field radios. It is not quite so poor for our near-field radios, but it is still far from realistic. We have not used this naive model in any of our simulations, but we do use it for intuitive justification of some of the algorithms given below. Controlling access to a shared media is much easier if the locations of the various devices are known. However. in our setting there is no independent source of location information for the pads. There is no way for a pad to know that it is leaving a cell except through the loss of signal from the baae station. Furthermore, there is no way for a pad, ‘We will use the term stat]on to refer to both pads and base stations. or base station, to know about the presence of other devices besides explicit communication. It is important to note that, in the absence of noise, our technology is symmetric; if a station A can hear a station B, then station B can hear the station A. The presence of noise sources (e.g., displays) may interfere with this symmetry, and in our simulations we will consider the effect of noise. However, noise is not so prevalent that we make it the overriding factor in our design; rather, we design our protocol to tolerate noise well but we have done most of our testing in a noise-free setting. There are many different ways to control access to a single channel. Typically, these approaches are either multiple access or token-based. We chose the multiple access ap preach over the token approach for two reasons.3 First, multiple access schemes are typically more robust. This is especially important in a wireless environment where the mobile devices span the gamut of reliability. Second, we expect the pads to be highly mobile and, given the small cell size, these pads will enter and leave cells frequently. This would necessitate frequent token hand-offs or recovery in a token-based scheme. One common wireless multiple access algorithm, currently used in packet radio, is carrier sense (CSMA). In the next section we discuss its properties and argue, following Karn [9] and others [4, 12], that the CSMA approach is inappropriate e for our setting. 2.2 CSMA In CSMA, every station senses the carrier before transmitting; if the station detects carrier then the station defers transmission (CSMA schemes differ as to when the transmission is tried again). Carrier sense attempts to avoid collisions by testing the signal strength in the vicinity of the transmitter. However, collisions occur at the receiver, not the transmitter; that is, it is the presence of two or more interfering signals at the receiver that constitutes a collision. Since the receiver and the sender are typically not co-located, carrier sense does not provide the appropriate information for collision avoidance. Two examples illustrate this point in more detail. Consider the configuration depicted in Figure 1. Station A can hear B but not C, and station C can hear station B but not A (and, by symmetry, we know that station B can hear both A and C). (xJ @J)@) Figure 1: Station B can hear both A and C, but A and C cannot hear each other. A “hidden terminal” scenario results when C attempts to transmit while A is transmitting to B. An ‘exposed terminal” scenario results if B is transmitting to A when C attempts to transmit. First, assume A is sending to B. When C is ready to transmit (perhaps to B or perhaps to some other station), it does not detect carrier and thus commences transmission; this produces a collision at B. Station C’s carrier sense did not provide the necessary information since station A was 3 These ressons are merely intuitive guides for design. We hope, in future work, to explore the token- bssed approach more fully. Only then can we make a vahd comparison between the two approaches. 213
“ hidden” from it. This is the classic“ hidden terminal”sce In the hidden terminal scenario in Figure 1, station C would not hear the Rts from station A, but would hear the An"exposed"terminal scenario results if now we assume CTS from station B and therefore would defer from trans- that b is sending to A rather than A sending to B. Then, mitting during A's data transmission. In the exposed termi hen c is ready to transmit, it does detect carrier and there- nal scenario, station C would hear the rTS from station B, fore defers transmission. However, there is no reason to de- but not the CTS from station A, and thus would be free to fer transmission to a station other than b since station a is transmit during B's data transmission. This is exactly the ut of C's range(and, as we stated earlier, in our environ desired behavior ment there are no "interference effects"from out-of-range Thus, in contrast to carrier-sense this RTS-CTS stations). Station C's carrier sense did not provide the nec- change enables nearby stations to avoid collisions at t essary information since it was exposed to station B even receiver, not the sender. The role of the RTS is to elicit though it would not collide or interfere with B's transmis- from the receiver the CTS, whose reception can be used by other stations as an indication that they are in range and Carrier sense provides information about potential colli- thus could collide with the impending transmission. This sions at the sender, but not at the receiver. This information depends crucially on symmetry; if a station cannot hear sta an be misleading when the configuration is distributed so tion B's CTS then we assume thatthat station cannot collide that not all stations are within range of each other. Because with an incoming transmission to B carrier sense does not provide the relevant collision avoid- If station a does not hear a Cts in response from station nce information, we chose to seek another approach based B, it ventually time out (i.e., stop waiting), assume on maca, which we describe below collision occurred, and then schedule the packet for retrans mission. MACA uses the binary exponential backoff(BEB) 2.3 MACA algorithm to select this retransmission time. Karn proposed MACA for use in packet radio as an alter native to the traditional CSM.A media access scheme [9 3 Designing MACAW MACa is somewhat similar to the protocol proposed in [3 Our purpose here is to re-evaluate some of the basic design ind also to that used in WaveLAN, and both resemble the choices in maca and then produce a revised version suit basic Apple LocalTalk Link Access Protocol [2]. Here we y brief an able for use in PARC's wireless LAN. The MACA algorithm (9] is itself a brief description and does not specify many as presented in [9], is a preliminary design and leaves many details unspecified. We start our investigation by defining f short fixed- these details for an initial version. Appendix a gives t ts. When station A wishes to transmit to station B, it sends pseudo-code we used to implement MACA We mention several aspects of this algorithm here. First a Request-to-Send(RTS)packet to B; this RTS packet con- the control packets (RTS, CTS)are 30 bytes long. The tains the length of the proposed data transmission. If station B hears the RTS, and it is not currently deferring(which transmission time of these packets defines the slot"time explain below), it immediately replies with a Clear-to-Send station does not receive a cts in response to its RTs. Re transmissions are scheduled an integer number of slot times posed data transmission. Upon receiving the CTS, station A after the end of the last deferral period. A station ran mediately sends its data. Any station overhearing an RTS domly chooses, with uniform distribution, this integer be defers all transmissions until some time after the associated TS packet would have finished(this includes the time for ween 1 and BO, where BO represents the backoff counter. ansmission of the Cts packet as well as the "turnare The backoff algorithm adjusts the value of Bo through two time at the receiving station"). Any station overhearing functions, Fdec and Finc. Whenever a Cts is received af. CTS packet defers for the length of the expected data ter an RTS, the backoff counter is adjusted via the function ansmission (which is contained in both the RTS and CTS 0: Fdec(BO). Whenever a CTS is not received af. ter an rts, the backoff counter is adjusted via the function packets With this algorithm, any station hearing an RTS will For BeB, Fdec(r)=BO, defer long enough so that the transmitting station can re (r)=MIN[2T, BOmasl, where BOmin and BOmas rep eive the retur TS, Any CTS will resent the lower and upper bounds for the backoff counter, avoid colliding with the returning data transmission. Since respectively For our simulations we have chosen BOmin=2 y station the cts is sent from the receiver, symmetry assures us that every station capable of colliding with the data transmission We use packet-level simulations of the protocol to evalu ate our design decisions. The simulator we use is a modifi ation of the network simulator we have used in a number of ay not be received by all in-range stations due to other other studies(for example, [5])of wired networks. The simu an RTS but not a CTS because they are in range of the lator is event-driven and contains the following components nder but out of range of the receiver can commence trans- ing to various statistical models ) TCP, UDP, IP, pads,and they are not in range of the receiver they cannot collide with viding the space into small cubes and then computing the strength of a signal at each cube according to the distance AThis turnaround time is the time from \ a hes includes to the cube approach can be made arbitrarily small by re- on of the rrs from the signal source to the center of the cube. Errors due perating system delays as well as radio transients ducing the cube size. For the simulations mentioned in this
“hidden” from it. This is the classic “hidden terminal” scenario. An “exposed” terminal scenario results if now we assume that B is sending to A rather than A sending to B. Then, when C is ready to transmit, it does detect carrier and therefore defers transmission. However, there is no reason to defer transmission to a station other than B since station A is out of C’s range (and, as we stated earlier, in our environment there are no “interference effects” from out-of-range stations). Station C‘s carrier sense did not provide the necessary information since it was exposed to station B even though it would not collide or interfere with B’s transmission. Carrier sense provides information about potential collisions at the sender, but not at the receiver. This information can be misleading when the configuration is distributed so that not all stations are within range of each other. Because carrier sense does not provide the relevant collision avoidance information, we chose to seek another approach based on MACA, which we describe below. 2.3 MACA Karn proposed MACA for use in packet radio as an alternative to the traditional CSMA media access scheme [9]. MACA is somewhat similar to the protocol proposed in [3] and also to that used in WaveLAN, and both resemble the basic Apple LocalTalk Link Access Protocol [2]. Here we present a very brief and general description of the algorithm ([9] is itself a brief description and does not specify many details). MACA uses two types of short, fixed-size signaling packets. When station A wishes to transmit to station B, it sends a Request-to-Send (RTS) packet to B; this RTS packet cont ains the length of the proposed data transmission. If station B hears the RTS, and it is not currently deferring (which we explain below), it immediately replies with a Clear-to-Send (CTS) packet; this CTS also contains the length of the proposed data transmission. Upon receiving the CTS, st ation A immediately sends its data. Any station overhearing an RTS defers all transmissions until some time after the associated CTS packet would have finished (this includes the time for transmission of the CTS packet as well as the “turnaround” time at the receiving st ation4 ). Any station overhearing a CTS packet defers for the length of the expected data transmission (which is contained in both the RTS and CTS packets). With this algorithm, any station hearing an RTS will defer long enough so that the transmitting station can receive the returning CTS. Any station hearing the CTS will avoid colliding wit h the returning data transmission. Since the CTS is sent from the receiver, symmetry assures us that every station capable of colliding with the data transmission is in range of the CTS (it is possible, though, that the CTS may not be received by all in-range stations due to other transmissions in the area). Notice that stations that hear an RTS but not a CTS because they are in range of the sender but out of range of the receiver can commence transmission, without harm, after the CTS has been sent; since they are not in range of the receiver they cannot collide with the data transmission. 4 This turnaround time is the time from the reception of the RTS at the receiving antenna to the transmission of the CTS; this includes operating system delays as well as radio transients. In the hidden terminal scenario in Figure I, station C would not hear the RTS from station A, but would hear the CTS from station B and therefore would defer from transmit ting during A’s data transmission. In the exposed t ermirral scenario, station C would hear the RTS from station B, but not the CTS from station A, and thus would be free to transmit during B’s data transmission. This is exactly the desired behavior. Thus, in contrast to carrier-sense, this RTS-CTS exchange enables nearby stations to avoid collisions at the receiver, not the sender. The role of the RTS is to elicit from the receiver the CTS, whose reception can be used by other stations as an indication that they are in range and thus could collide with the impending transmission. This depends crucially on symmetry; if a station cannot hear station B’s CTS then we assume that that station cannot colhde with an incoming transmission to B. If station A does not hear a CTS in response from station B, it will eventually time out (i. e., stop waiting), assume a collision occurred, and then schedule the packet for retransmission. MACA uses the binary exponential backoff (BEB) algorithm to select this retransmission time. 3 Designing MACAW Our purpose here is to re-evaluate some of the basic design choices in MACA and then produce a revised version suitable for use in PARC’s wireless LAN. The MACA algorithm, as p~esented in [9], is a preliminary design and leaves many detads unspecified. We start our investigation by defining these details for an initial version. Appendix A gives the pseudo-code we used to implement MACA. We mention several aspects of this algorithm here. First, the control packets (RTS, CTS) are 30 bytes long. The transmission time of these packets defines the ‘slot” time for retransmissions. Retransmissions occur if and only if a station does not receive a CTS in response to its RTS. Retransmission are scheduled an integer number of slot times after the end of the last deferral period. A station randomly chooses, with uniform distribution, this integer between 1 and BO, where BO represents the backoff counter. The backoff algorithm adjusts the value of BO through two functions, Fdec and F,m.. Whenever a CTS is received after an RTS, the backoff counter is adjusted via the function Fd~d BO := F~~c(~O). Whenever a CTS is not received after an RTS, the backoff counter is adjusted via the function Ftnc: BO := F,. C(BO). For BEB, Fd.c(z) = BO~,~ and F,nc(s) = MIN[2z, BO maz ] , w h ere BOmin and BOmaz represent the lower and upper bounds for the backoff counter, respectively. For our simulations we have chosen BOm,n = 2 and BOma. = 64. We use packet-level simulations of the protocol to evaluate our design decisions. The simulator we use is a modification of the network simulator we have used in a number of other studies (for example, [5]) of wired networks. The simulator is event-driven and contains the following components: a traffic generator (which can generate data streams according to various statistical models), TCP, UDP, 1P, pads, and base stations. The simulator approximates the media by dividing the space into small cubes and then computing the strength of a signal at each cube according to the distance from the signal source to the center of the cube. Errors due to the cube approach can be made arbitrarily small by reducing the cube size. For the simulations mentioned in this 214
base station B P2 by the streams in Figure 2. packets per second, achieved Table Fi here all stations are sending data to the generating enough UDP traffic to fully consume the channel. base station direction of the data As shown in Table 1, when using the BEB algorithm even ransmlssle enerating data at a rate tually a single pad transmits at channel capacity and the of 64 packets ng UDP for transpor other pad is completely backed off (i. e, its backoff counter is at BOmar). This is very similar to the Ethernet behavi noted in [11]. In such a multi-pad single cell environment, if all pads but one have relatively high backoff counters then In our simulations, all pads are 6 feet below after every collision it is very likely that the less-backed-off station height. A station which can be either a pad or a pad will retransmit first and win"the collision and thereby reset its backoff counter to BOmin. This phenomenon keep station starts sending, the strength of the signal is added to recurring after every collision, with the backed-off pads b the current signal at all nearby cubes. At the end of the coming decreasingly likely to win a collision. If there is no transmission, the designated receiving station can correctly receive the packet if the signal strength is greater than some permanently capture the channel. This dynamic is driven threshold (the signal strength at 10 feet)and is greater than by having one pad with a significantly lower backoff counter the sum of the other signals by at least 10 dB during the than the other pads, even though intuitively one would ex entire packet transmission time pect that the backoff counter should reflect the ambient level e use the term "stream"to refer to the set of pack of congestion in the cell, which is the same for all pads. each pad is doing its own congestion calculation based on its own station. for most of the simulations reported on here. the experience and there is no "sharing"of this congestion in devices generate data at a constant rate of either 32 or 64 formation; this leads to the different stati ackets per second. all data packets are 512 bytes, and arying views of the level of congestion in the cell che control packets(rtS, cts, etc ) are 30 bytes. simula we have modified the backoff algorithm by tions are typically run between 500 and 2000 seconds, with packet header a field which contains the cur a warmup period of 50 seconds. The simulations use a null rent value of the backoff counter. Whenever a station hears turnaround time a packet, it copies that value into its own backoff counter We investigate two are as of the media access protocol Thus, in our single cell scenario where all stations are in he backoff algorithm and the basic RTS-CTS message ex- range of each other, after each successful transmission all We should clearly pads have the same backoff counter. The results from this edia access protocol should deliver high network utilization algorithm are shown in the right column of Table 1. The and also provide fair access to the media. These goals are throughput allocation is now completely fair Thus, hav ng the congestion information disseminated explicitly by leliver fairness over optimal total throughput(note that the media access protocol produced a fairer allocation of often the easiest way to optimize total throughput in shared resources media is to eliminate sharing and turn the media over to one above we modified the basic structure of the backoff al- user exclusively) ithm to allocate bandwidth fairly. An additional adjustment to the backoff computatio 3.1 Backoff Algorithm the efficiency of the protocol. The BeB backe tion adjusts extremely rapidly; it both backs off quickly Recall that MACA uses binary exponential backoff (BEB), when a collision is detected and it also reduces the back n which the backoff is doubled after every collision and re- off counter to BO, duced minimal backoff after every successful RTS- nission. This produces rather large variations in the backoff CTS exchange. We now show that this does not provide an counter; in our simple one-cell configuration, after every suc adequate level of fairness in some simple one-cell configura- tions. For example, consider the case where there are two have a minimal backoff counter and then we must repeat a pads in a cell, as depicted in Figure 2; the pads are within period of contention to increase the backoffs. This is mainly range of each other(and the base station) and each pad relevant when there are several pads in a cell and demand for the media is high are based on the properties To prevent such wild oscillations, we have instead gentler adjustment algorithm; upon a collision, the backoff interval is increased by a multiplicative factor(1.5)and upon defintion orb on of fairness is suffcien of fairness. In this section any intuitive success it is decreased by 1: Fine(c)= MIN[1. 5r, BO, and Fdec(x)= MAX[r-1, BOmin]. This multiplicative in- crease and linear decrease(MILD)still provides reasonably
base station B /? o PI o P2 Figure 2: A single celI configuration where all stations are in range of each other and both pads are sending data to the base station (the arrows indicate the direction of the data transmission). The pads are each generating data at a rate of 64 packets per second and are using U DP for transport. paper the cubes are 1 cubic foot in size. In our simulations, all pads are 6 feet below the base station height. A station (which can be either a pad or a base station) resides at the center of a cube. Whenever a station start& sending, the strength of the signal is added to the current signal at all nearby cubes. At the end of the transmission, the designated receiving station can correctly receive the packet if the signal strength is greater than some threshold (the signal strength at 10 feet) and is greater than the sum of the other signals by at least 10 dB during the entire packet transmission times. We use the term “stream” to refer to the set of packets going from a particular sender to a particular receiver station. For most of the simulations reported on here, the devices generate data at a constant rate of either 32 or 64 packets per second. All data packets are 512 bytes, and the control packets (RTS, CTS, etc.) are 30 bytes. Simulations are typically run between 500 and 2000 seconds, with a warmup period of 50 seconds. The simulations use a null turnaround time. We investigate two areas of the media access protocol: the backoff algorithm and the basic RTS-CTS message exchange. We should clearly state our evaluation criterion: the media access protocol should deliver high network utilization and also provide fair access to the media. These goals are not always compatible, and when they are not we choose to deliver fairness6 over optimal total throughput (note that often the easiest way to optimize total throughput in shared media is to eliminate sharing and turn the media over to one user exclusively). 3.1 Backoff Algorithm Recall that MACA uses binary exponential backoff (BEB), in which the backoff is doubled after every collision and reduced to the minimal backoff after every successful RTSCTS exchange. We now show that this does not provide an adequate level of fairness in some simple one-cell configurations. For example, consider the case where there are two pads in a cell, as depicted in Figure 2; the pads are within range of each other (and the base station) and each pad is 5 These parameters are based on the properties of our hardware, however the specific value should have little effect on the generality of the simulation results. 6 We do not give a precise definition of fairness, In this section any intuitive notion of fairness is sufficient; ss we remark in Section 4, there are deeper allocation questions which do require a more precise definition of fairness. EIEilia Table 1: The throughput, in packets per second, achieved by the streams in Figure 2. generating enough UDP traffic to fully consume the channel. As shown in Table 1, when using the BEB algorithm eventually a single pad transmits at channel capacity and the other pad is completely backed off (i.e., its backoff counter is at BOmac ). This is very similar to the Ethernet behavior noted in [11]. In such a multi-pad single cell environment, if all pads but one have relatively high backoff counters then after every co~lon it is very likely that the less-backed-off pad will retransmit first and “win” the collision and thereby reset its backoff counter to BOrnin. This phenomenon keeps recurring after every collision, with the backed-off pads becoming decreasingly likely to win a collision. If there is no maximum backoff, one can show that eventually one pad will permanently capture the channel. This dynamic is driven by having one pad with a significantly lower backoff counter than the other pads, even though intuitively one would expect that the backoff counter should reflect the ambient level of congestion in the cell, which is the same for all pads. Each pad is doing its own congestion calculation based on its own experience and there is no “sharing” of this congestion information; this leads to the different stations having widely varying views of the level of congestion in the cell. To rectify this, we have modified the backoff algorithm by including in the packet header a field which contains the current value of the backoff counter. Whenever a station hears a packet, it copies that value into its own backoff counter. Thus, in our single cell scenario where all stations are in range of each other, after each successful transmission all pads have the same backoff counter. The results from this algorithm are shown in the right column of Table 1. The throughput allocation is now completely fair. Thus, having the congestion information dwseminated explicitly by the media access protocol produced a fairer allocation of resources. Above we modified the basic structure of the backoff algorithm to allocate bandwidth fairly. An additional minor adjustment to the backoff computation can slightly improve the efficiency of the protocol. The BEB backoff crdculation adjusts extremely rapidly; it both backs off quickly when a collision is detected and it also reduces the backOR counter to BOmin immediately upon a successful transmission. This produces rather large variations in the backoff counter; in our simple one-cell configuration, after every successful transmission we return to the case where all stations have a minimal backoff counter and then we must repeat a period of contention to increase the backoffs. This is mainly relevant when there are several pads in a cell and demand for the media is high. To prevent such wild oscillations, we have instead adopted a gentler adjustment algorithm; upon a collision, the backoff interval is increased by a multiplicative factor (1.5) and upon success it is decreased by 1: Fine(z) = JflN[l.5z, Born..] and Fa..(z) = MAX[Z —1, BcL+I. This rnultb~cative increase and linear decrease (MILD) still provides reasonably 215
base station base station B P5 P4 P2 Figure 3: A single cell configuration where all stations are ange of each other. All six pads are sending data to the Figure 4: A single cell configuration where all stations are base station. Each stream is generating data at a rate of 32 in range of each other. The base station is sending data to packets per second and using UDP for transpor two of the pads, and the third pad is sending data to the base station. Each stream is generating data at a rate of 32 UDP for transport quick escalation in the backoffs when contention is high but by not resetting the backoff counter to BOmin it avoids hav- ing to repeat the escalation in backoff counters after every we can at least state that in a simple single cell configura tion we want to treat all streams equally(as opposed to all of these algorithms in the configuration depicted in Figure stations equally); recall that a stream is the fow of data 3, which has six pads all sending data to the base station packets between a source-destination pair. That is, to the Table 2 shows the data from these two backoff algorithms xtent possible we want to allocate bandwidth The perforates a clear advantage for the mILD algorithm streams and not to the stations themselves. This d is especially relevant since in our setting all wireless tration above was essentially identical because the level of nications must go through a base station, thus base ontention is sufficiently low that resetting the counters to are likely to be the source of many stream BOmin =2 does not interfere with performand This notion of per stream fairness can be implemented by keeping, in each station, separate queues for each stream BEB each queue. When a station is allowed to send (e.g,after BB261 deferral wait) and finds that it has data pending for N destinations, we treat the station as n co-located streams when resolving contention for the media. This can be done P3B‖2.846.05 as follows. For each destination with data pending, the sta P4B‖2.936.12 n lip P5-B‖3.006.,14 how long to wait before sending an rts to this destina P6-B‖305 tion. It then picks the one with the shortest wait time. If more than one of these streams have the same shortest wait Table 2: The throughput, in packets per second, achieved time, the station randomly picks one of them as the winner by the streams in Figure 3 ather than simulating a collision; because of this, streams originating from a multi-stream station may have a slig advantage over streams in a single stream station s can be seen in Table 3, this multiple stream alg 3.2 Multiple Stream Model thm produces a fair allocation of bandwidth among the competing streams Let us return to the notion of fair allocation of bandwidth Our initial design had a single FIFo packet queue at each station, with a single backoff parameter bo which controls I Single Stream Multiple Stream the transmission(and retransmissions) of the packet at the head of the queue. This design allocates the bandwidth B-P2 12.34 qually to all transmitting stations. Consider the configura- P3-B 22.74 15.64 tion in Figure 4 where there are three pads; the base station is sending data packets to two of the pads, and the Table 3: The throughput, in packets per second, achieved is sending packets to the base station. Allocating by the streams in Figure 4. equally to each station gives half of the bandwidth to the pad-to-base-station stream and a quarter to each of the ase-station-to-pad streams, The data in Table 3 shows that when using a single queue in this scenario, each transmit ting station(pad or base station)receives an equal share and 3. 3 Basic Message Exchange thus half of the bandwidth goes to the pad-to-base-station In this section we examine the basic RTS-CTS-DATA me he role of link layer acknowledgment and the need for a Is this the allocation we want to achieve; is this fair"? carrier-sense like functionality (as in CSMA/CA [2])is com- Certainly defining a general definition of fairness for this monly accepted wisdom in the 802.11 community; we repeat wireless setting is beyond our ken at the moment. However the material here for completeness 216
base station base station Figure 3: A single cell configuration where all stations are in range of each other. All six pads are sending data to the base station. Each stream is generating data at a rate of 32 packets per second and using UDP for transport. quick escalation in the backoffs when contention is high but by not resetting the backoff counter to BOm,n it avoids having to repeat the escalation in backoff counters after every successful transmission. We tested the relative performance of these algorithms in the configuration depicted in Figure 3, which has six pads all sending data to the base station. Table 2 shows the data from these two backoff algorithms, and illustrates a clear advantage for the MILD algorithm. The performance of MILD and BEB on the two-pad configuration above was essentially identical because the level of contention is sufficiently low that resetting the counters to BO~:n = 2 does not interfere with performance. PI-B P2-B P3-B P4-B P5-B P6-B BEB copy 2.96 3.01 2.84 2.93 3.00 3.05 MILD copy 6.10 6.18 6.05 6.12 6.14 6.09 Table 2: The throughput, in packets per second, achieved by the streams in F@re 3. 3.2 Multiple Stream Model Let us return to the notion of fair allocation of bandwidth. Our initiaJ design had a single FIFO packet queue at each station, wit h a single backoff parameter BO which cent rols the transmission (and retransmissions) of the packet at the head of the queue. This design allocates the bandwidth equally to all transmitting stations. Consider the configuration in Figure 4 where there are three pads; the base station is sending data packets to two oft he pads, and the t bird pad is sending packets to the base station. Allocating bandwidth equally to each station gives half of the bandwidth to the pad-to-base-station stream and a quarter to each of the two bcme-station-to-pad streams, The data in Table 3 shows that when using a single queue in this scenario, each transmitting station (pad or base station) receives an equal share and thus half of the bandwidth goes to the pad-to-base-station stream and a quarter to each of the two base-station-to-pad streams. Is this the allocation we want to achieve; is this “fair”? Certainly defining a general definition of fairness for this wireless setting is beyond our ken at the moment. However, (’a Figure 4: A single cell configuration where all stations are in range of each other. The base station is sending data to two of the pads, and the third pad is sending data to the base station. Each stream is generating data at a rate of 32 packets per second and using UDP for transport. we can at least state that in a simple single cell configuration we want to treat all streams equally (as opposed to all stations equally); recall that a stream is the flow of data packets between a source-destination pair. That is, to the extent possible, we want to allocate bandwidth equally to streams and not to the stations themselves. This distinction is especially relevant since in our setting all wireless communications must go through a base station, thus base stations are likely to be the source of many streams. This notion of per stream fairness can be implemented by keeping, in each station, separate queues for each stream and then running the backoff algorithm independently for each queue. When a station is allowed to send (e.g., after a deferral wait) and finds that it has data pending for N destinations, we treat the station as N co-located streams when resolving contention for the media. This can be done as follows. For each destination with data pending, the station flips a coin to determine, based on the backoff counter, how long to wait before sending an RTS to this destination. It then picks the one with the shortest wait time. If more than one of these streams have the same shortest wait time, the station randomly picks one of them as the winner, rather than simulating a collision; because of this, streams originating from a multi-stream station may have a slight advantage over streams in a single stream station. As can be seen in Table 3, this multiple stream algorithm produces a fair allocation of bandwidth among the competing streams. Single Stream Multiple Stream B-Pi 11.42 15.07 B-P2 12.34 15.82 P3-B 22.74 15.64 Table 3: The throughput, in packets per second, achieved by the streams in Figure 4. 3.3 Basic Message Exchange In this section we examine the basic RTS-CTS-DATA message exchange and propose four changes. The material on the role of link layer acknowledgment and the need for a carrier-sense like functionaht y (as in CSMA/ CA [2] ) is commonly accepted wisdom in the 802.11 community; we repeat the material here for completeness. 216