MACAW: A Media Access Protocol for Wireless LANs PDF

MACAW: A Media Access Protocol for Wireless LAN’s Vaduvur...

MACAW: A Media Access Protocol for Wireless LAN’s Vaduvur Bharghavan Department of Electrical Engineering and Computer Science University of California at Berkeley [email protected]. edu Alan Demers Scott Shenker Lixia Zhang Palo Alto Research Center Xerox Corporation {demers, shenker, lixia}@parc.xerox. com Abstract lation results may only apply to PARC’s particular radio technology, we expect that some of the basic insight gained In recent years, a wide variety of mobile computing devices will be more generally applicable. has emerged, including portables, palmtops, and personal Wireless media access protocols for a single channel can digit al assistants. Providing adequate network connectivity y 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. 1 Our work is based on MACA, tocols for a single channel wireless LAN being developed at a Multiple Access, Collision Avoidance protocol first pro- Xerox Corporation’s Palo Alto Research Center. We start posed by Karn and later refined by Biba. Using with the MACA media access protocol first proposed by packet-level simulations of the wireless network to guide our Karn and later refined by Biba 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 Karn’s original proposal Our design is formance and design issues in such protocols, Our analysis based on four key observations. First we observe, follow- leads to a new protocol, MACAW, which uses an RTS-CTS- ing Karn and others [4, 12], that the relevant contention DS-DATA-ACK message exchange and includes a signifi- is at the receiver, not the sender. This renders the car- cantly 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 wit bout 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 tants, 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 synchronize ation in- Consequently, a new generation of wireless network technol- formation about contention periods, so that all devices can ogy is needed to provide adequate network cormectivitY for cent end effectively. In particular, this means that cent ention these mobile devices. In particular, wireless local area net- for bandwidth should not just be initiated by the sending works (LAN’s) 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 formance (as compared to MACA), we hasten to note that 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 scarce, there are many remaining unresolved design issues. resource; 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 media vide some background on PARC’s radio network and on the access protocols in wireless LAN’s. 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 use in the wireless network infrastructure being developed presenting simulation data for several different network con- in the Computer Science Laboratory at Xerox Corporation’s figurations. We discuss remaining design issues in Section 4 Palo 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 1 We expect in future work to revisit the token-based approach and wireless media access protocols. While our specific simu- make a more in-depth comparison. Permission to copy without fee all or part of this material is that copying is by permission of the Association of Computing granted provided that the copies are not made or distributed for Machinery. To copy otherwise, or to republish, requires a fee direct commercial advantage, the ACM copyright notice and the and/or specific permission. title of the publication and its date appear, and notice is given SIGCOMM 94 -8/94 London England UK @ 1994 ACM 0-89791 -682 -4/94/0008..S3.50 212 2 Background or base station, to know about the presence of other devices besides explicit communication. 2.1 PARC’s Nano-Cellular Radio Network It is important to note that, in the absence of noise, our technology is symmetric; if a station A can hear a station B, The Computer Science Laboratory at Xerox Corporation’s then station B can hear the station A. The presence of noise Palo Alto Research Center has developed 5 MHz “near-field” sources (e.g., displays) may interfere with this symmetry, radio t ethnology ; its low operating frequency eliminates and in our simulations we will consider the effect of noise. multipath effects, and thus it is suitable for use in an indoor However, noise is not so prevalent that we make it the over- wireless LAN. The LAN infrastructure consists of “base sta- riding factor in our design; rather, we design our protocol tions”, which are installed in the ceiling, and “pads”, which to tolerate noise well but we have done most of our testing are custom built portable computing devices (see for a in a noise-free setting. more complete description). There is a single 256kbps chan- There are many different ways to control access to a sin- nel, and all wireless communication is between a pad and a gle channel. Typically, these approaches are either multiple base station (the base stations are connected together by an access or token-based. We chose the multiple access ap Ethernet). All base stations and pads transmit at the same preach over the token approach for two reasons.3 First, signal strength. The range of transmission is 3 to 4 me- multiple access schemes are typically more robust. This is ters, and the near-field signal strength decays very rapidly especially important in a wireless environment where the (X.-3, as opposed tow r-’ in the far-field region). We thus mobile devices span the gamut of reliability. Second, we ex- obtain, around each base station, a very small cell (roughly pect the pads to be highly mobile and, given the small cell 6 meters in diameter) with very sharply defined boundaries: size, these pads will enter and leave cells frequently. This a “nanocell”. Given that the cells are very small and inter- would necessitate frequent token hand-offs or recovery in a cell interference is negligible, the aggregate bandwidth in a token-based scheme. multi-cell environment is quite high. One common wireless multiple access algorithm, cur- A “collision” occurs when a receiver is in the reception rently used in packet radio, is carrier sense (CSMA). In the range of two transmitting stations2, and is unable to cleanly next section we discuss its properties and argue, following receive signal from either station. “Capture” occurs when Karn and others [4, 12], that the CSMA approach is in- a receiver is in the reception range of two transmitting sta- appropriate e for our setting. tions, 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. 2.2 CSMA Perhaps surprisingly, this ratio is rather hard to achieve, In CSMA, every station senses the carrier before transmit- given that the base stations are in the ceiling and the pads ting; if the station detects carrier then the station defers are typically no higher than a meter or so above the floor. transmission (CSMA schemes differ as to when the trans- Roughly, this gives a minimum pad-to-base distance of just mission is tried again). Carrier sense attempts to avoid col- under 2 meters in a cell whose radius is just over 3 meters. lisions by testing the signal strength in the vicinity of the Thus, in our environment, capture will be relatively rare, 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 “Interference” occurs when a receiver is in range of one interfering signals at the receiver that constitutes a colli- transmitting station and slightly out-of-range of another sion. Since the receiver and the sender are typically not transmitting station, but is unable to cleanly receive the co-located, carrier sense does not provide the appropriate closer station’s signal because of the interfering presence of information for collision avoidance. Two examples illustrate the other signal. The rather sharp decay in signal strength 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. station C can hear station B but not A (and, by symmetry, Ignoring both capture and interference leads to a very we know that station B can hear both A and C). simple model in which any two stations are either in-range or out-of-range of one another, and a station successfully receives transmitter a packet within if and range only of it. if there In designing is exactly our one active protocol, (xJ @J)@) we often use this model accompanied by the additional ass- umptions 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 base 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- tification of some of the algorithms given below. First, assume A is sending to B. When C is ready to Controlling access to a shared media is much easier if transmit (perhaps to B or perhaps to some other station), the locations of the various devices are known. However. it does not detect carrier and thus commences transmission; in our setting there is no independent source 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 baae station. Furthermore, there is no way for a pad, 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. ‘We will use the term stat]on to refer to both pads and base stations. 213 “hidden” from it. This is the classic “hidden terminal” sce- In the hidden terminal scenario in Figure I, station C nario. 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, mit ting during A’s data transmission. In the exposed t ermi- when C is ready to transmit, it does detect carrier and there- rral 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 out 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 ex- stations). Station C‘s carrier sense did not provide the nec- change enables nearby stations to avoid collisions at the 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 sion. 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- can be misleading when the configuration is distributed so tion B’s CTS then we assume that that station cannot colhde 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 ance information, we chose to seek another approach based B, it will eventually time out (i. e., stop waiting), assume a on MACA, which we describe below. collision occurred, and then schedule the packet for retrans- mission. MACA uses the binary exponential backoff (BEB) algorithm to select this retransmission time. 2.3 MACA Karn proposed MACA for use in packet radio as an alter- 3 Designing MACAW native to the traditional CSMA media access scheme. MACA is somewhat similar to the protocol proposed in Our purpose here is to re-evaluate some of the basic design and 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. Here we able for use in PARC’s wireless LAN. The MACA algorithm, present a very brief and general description of the algorithm as p~esented in , is a preliminary design and leaves many ( is itself a brief description and does not specify many detads unspecified. We start our investigation by defining details). these details for an initial version. Appendix A gives the MACA uses two types of short, fixed-size signaling pack- pseudo-code we used to implement MACA. ets. When station A wishes to transmit to station B, it sends 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 t ains the length of the proposed data transmission. If station transmission time of these packets defines the ‘slot” time B hears the RTS, and it is not currently deferring (which we for retransmissions. Retransmissions occur if and only if a explain below), it immediately replies with a Clear-to-Send station does not receive a CTS in response to its RTS. Re- (CTS) packet; this CTS also contains the length of the pro- transmission are scheduled an integer number of slot times posed data transmission. Upon receiving the CTS, st ation A after the end of the last deferral period. A station ran- immediately 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 tween 1 and BO, where BO represents the backoff counter. CTS packet would have finished (this includes the time for The backoff algorithm adjusts the value of BO through two transmission of the CTS packet as well as the “turnaround” functions, Fdec and F,m.. Whenever a CTS is received af- time at the receiving st ation4 ). Any station overhearing ter an RTS, the backoff counter is adjusted via the function a CTS packet defers for the length of the expected data Fd~d BO := F~~c(~O). Whenever a CTS is not received af- transmission (which is contained in both the RTS and CTS ter an RTS, the backoff counter is adjusted via the function packets). F tnc: BO := F,. C(BO). For BEB, Fd.c(z) = BO~,~ and With this algorithm, any station hearing an RTS will F,nc(s) = MIN[2z, BO maz ] , w h ere BOmin and BOmaz rep- defer long enough so that the transmitting station can re- resent the lower and upper bounds for the backoff counter, ceive the returning CTS. Any station hearing the CTS will respectively. For our simulations we have chosen BOm,n = 2 avoid colliding wit h the returning data transmission. Since and BOma. = 64. the CTS is sent from the receiver, symmetry assures us that We use packet-level simulations of the protocol to evalu- every station capable of colliding with the data transmission ate our design decisions. The simulator we use is a modifi- is in range of the CTS (it is possible, though, that the CTS cation of the network simulator we have used in a number of may not be received by all in-range stations due to other other studies (for example, ) of wired networks. The simu- transmissions in the area). Notice that stations that hear lator is event-driven and contains the following components: an RTS but not a CTS because they are in range of the a traffic generator (which can generate data streams accord- sender but out of range of the receiver can commence trans- ing to various statistical models), TCP, UDP, 1P, pads, and mission, without harm, after the CTS has been sent; since base stations. The simulator approximates the media by di- they are not in range of the receiver they cannot collide with viding the space into small cubes and then computing the the data transmission. strength of a signal at each cube according to the distance 4 This turnaround time is the time from the reception of the RTS from the signal source to the center of the cube. Errors due at the receiving antenna to the transmission of the CTS; this includes to the cube approach can be made arbitrarily small by re- operating system delays as well as radio transients. ducing the cube size. For the simulations mentioned in this 214  base station /? B Table 1: The EIEilia throughput, in packets per second, achieved by the streams in Figure 2. PI P2 o o Figure 2: A single celI configuration where all stations are generating enough UDP traffic to fully consume the channel. in range of each other and both pads are sending data to the base station (the arrows indicate the direction of the data As shown in Table 1, when using the BEB algorithm even- tually a single pad transmits at channel capacity and the transmission). The pads are each generating data at a rate of 64 packets per second and are using U DP for transport. other pad is completely backed off (i.e., its backoff counter is at BOmac ). This is very similar to the Ethernet behavior noted in. In such a multi-pad single cell environment, if all pads but one have relatively high backoff counters then paper the cubes are 1 cubic foot in size. In our simulations, all pads are 6 feet below the base after every co~lon it is very likely that the less-backed-off pad will retransmit first and “win” the collision and thereby station height. A station (which can be either a pad or a base station) resides at the center of a cube. Whenever a reset its backoff counter to BOrnin. This phenomenon keeps recurring after every collision, with the backed-off pads be- station start& sending, the strength of the signal is added to 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 maximum backoff, one can show that eventually one pad will receive the packet if the signal strength is greater than some permanently capture the channel. This dynamic is driven by having one pad with a significantly lower backoff counter threshold (the signal strength at 10 feet) and is greater than 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 times. pect that the backoff counter should reflect the ambient level We use the term “stream” to refer to the set of pack- of congestion in the cell, which is the same for all pads. Each ets going from a particular sender to a particular receiver 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- formation; this leads to the different stations having widely devices generate data at a constant rate of either 32 or 64 packets per second. All data packets are 512 bytes, and varying views of the level of congestion in the cell. To rectify this, we have modified the backoff algorithm by the control packets (RTS, CTS, etc.) are 30 bytes. Simula- tions are typically run between 500 and 2000 seconds, with including in the packet header a field which contains the cur- rent value of the backoff counter. Whenever a station hears a warmup period of 50 seconds. The simulations use a null turnaround time. a packet, it copies that value into its own backoff counter. We investigate two areas of the media access protocol: Thus, in our single cell scenario where all stations are in the backoff algorithm and the basic RTS-CTS message ex- range of each other, after each successful transmission all change. We should clearly state our evaluation criterion: the pads have the same backoff counter. The results from this media 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- not always compatible, and when they are not we choose to ing the congestion information dwseminated explicitly by deliver fairness6 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). gorithm to allocate bandwidth fairly. An additional minor adjustment to the backoff computation can slightly improve the efficiency of the protocol. The BEB backoff crdcula- 3.1 Backoff Algorithm 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- in which the backoff is doubled after every collision and re- OR counter to BOmin immediately upon a successful trans- duced to the minimal backoff after every successful RTS- mission. 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- cessful transmission we return to the case where all stations 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 is relevant when there are several pads in a cell and demand for the media is high. 5 These parameters are based on the properties of our hardware, To prevent such wild oscillations, we have instead adopted however the specific value should have little effect on the generality a gentler adjustment algorithm; upon a collision, the backoff of the simulation results. interval is increased by a multiplicative factor (1.5) and upon 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, success it is decreased by 1: Fine(z) = JflN[l.5z, Born..] there are deeper allocation questions which do require a more precise and Fa..(z) = MAX[Z — 1, BcL+I. This rnultb~cative in- definition of fairness. crease and linear decrease (MILD) still provides reasonably 215  base station base station (’a Figure 3: A single cell configuration where all stations are in range 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 transport. 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. quick escalation in the backoffs when contention is high but by not resetting the backoff counter to BOm,n 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- successful transmission. We tested the relative performance 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 flow 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, extent possible, we want to allocate bandwidth equally to and illustrates a clear advantage for the MILD algorithm. streams and not to the stations themselves. This distinction The performance of MILD and BEB on the two-pad config- is especially relevant since in our setting all wireless commu- uration above was essentially identical because the level of nications must go through a base station, thus base stations contention is sufficiently low that resetting the counters to are likely to be the source of many streams. BO~:n = 2 does not interfere with performance. 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 BEB MILD each queue. When a station is allowed to send (e.g., after copy copy a deferral wait) and finds that it has data pending for N PI-B 2.96 6.10 destinations, we treat the station as N co-located streams P2-B 3.01 6.18 when resolving contention for the media. This can be done P3-B 2.84 6.05 as follows. For each destination with data pending, the sta- P4-B 2.93 6.12 tion flips a coin to determine, based on the backoff counter, P5-B 3.00 6.14 how long to wait before sending an RTS to this destina- P6-B 3.05 6.09 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 F@re 3. 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 algo- 3.2 Multiple Stream Model rithm produces a fair allocation of bandwidth among the competing streams. 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 Single Stream Multiple Stream the transmission (and retransmissions) of the packet at the B-Pi 11.42 15.07 head of the queue. This design allocates the bandwidth B-P2 12.34 15.82 equally 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 oft he pads, and the t bird pad Table 3: The throughput, in packets per second, achieved is sending packets to the base station. Allocating bandwidth 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 two bcme-station-to-pad streams, The data in Table 3 shows that when using a single queue in this scenario, each transmit- 3.3 Basic Message Exchange ting station (pad or base station) receives an equal share and thus half of the bandwidth goes to the pad-to-base-station In this section we examine the basic RTS-CTS-DATA mes- stream and a quarter to each of the two base-station-to-pad sage exchang