MACAW: A Media Access Protocol for Wireless LANs

V. Bharghaven, A. Demers, S. Shenker, L. Zhang, "MACAW: A Media Access Protocol for Wireless LANs," ACM SIGCOMM Conference, (August 1994)

This paper analyzed CSMA and MACA, two possible media access protocols for single channel wireless LANs and highlighted the problems associated with both of them. While CSMA suffered from the hidden terminal and exposed terminal problems, the MACA which proposed RTS-CTS-DATA with BEB suffered from basic fairness problems and had the potential of even starving a connection. This led the authors to propose MACAW which used an RTS-CTS-DS-DATA-ACK message exchange and had a better backoff algorithm. The following were its key features:

• Fairness: MACA used the binary exponential backoff algorithm which resulted in each end host doubling its backoff time on every unsuccessful transmission/collision detection. Due to this, it was possible to have 1 connection always backing off and the other taking full available bandwidth thereby raising fairness concerns. MACAW proposed BEB copy algorithm which enabled all stations in the range having the same backoff value thereby having fairness. Further to prevent wild oscillations, MILD was introduced in the protocol. As a further optimization, fairness was defined in terms of streams and not stations.

• Basic Message Exchange: To start with, the authors realized that since noise is likely to be present, an RTS-CTS-DATA-ACK exchange should be used for reliable communication. Further, to provide synchronization among stations, before sending a DATA packet, the station sent a 30 byte Data-Sending packet (DS). The idea was that every station which overheard the packet would know that RTS-CTS exchange was successful. Further the authors proposed RRTS (Request-for-Request-to-Send packet).

• Multicast: Due to the inherent nature of RTS-CTS, multicast cannot be implemented straightaway. So, as a hack, the authors proposed sending RTS immediately followed by the DATA packet. Obviously, this design had the same flaws as CSMA. 

• 'Leakage' of backoff values: Due to the inherent nature of the BEB copy algorithm, all nodes in the same cell were required to have the same backoff value. This resulted in some cases were due to proximity of nodes on the edges of the cells led to 'leaking' of backoff values into adjacent cells which led to wasteful idle time or wasteful collisions. Secondly there is also an inherent problem with BEB that absence of CTS implied a collision/congestion while it may very well be due to noise or a source being offline. This led the authors to propose that each station should maintain a separate backoff counter for each stream and also all stations attempting to communicate with the same receiving station should use the same backoff value. 

Critique

Overall, this paper was nicely written, talked about the state of art in wireless technology at that time and then proposed their solution in an incremental fashion thereby clearly highlighting the need for each and every design decision they had taken. One of my concerns was regarding the lack of good solutions for multicast. The solution proposed by the authors was more of a working hack. Can a spanning tree like solution be implemented? Further, since all the evaluation was simulated in a controlled environment, it may not clearly reflect the practical environment. Thirdly, I was intrigued by the fact that MILD had a multiplicative factor of 1.5 (and not 2 which is just bit left shift operation). Since we had discussed in class while reading about AIMD, these factors are chosen more of due to ease of implementation, I am curious as to what was the motivation behind choosing a factor of 1.5. Lastly, all the analysis was done for fixed stations. (Why) Weren't the authors concerned about moving end points in 1994?