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).

One line summary: This paper introduces a wireless media access protocol called MACAW that builds off of prior protocols; MACAW is based on the use of RTS, CTS, DS, ACK, and RRTS messages and backoff algorithms for when contention is detected.

Summary

This paper discusses modifications to a previous wireless access protocol called MACA to alleviate problems with performance and fairness. The result of these modifications is MACAW. MACAW is designed based on four key principles: (1) relevant media contention is at the receiver, not the sender, (2) congestion is location dependant and is not a homogonous phenomenon, (3) learning about congestion must be a collective enterprise among devices, and (4) synchronization information should be propagated so all devices can contend fairly and effectively. MACAW was designed and tested with consideration to collision but not capture or interference – it was designed to tolerate noise but mostly tested in a noise-free setting.

This paper first describes problems with the CSMA and MACA protocols. It then describes the ways in which MACA was improved to yield MACAW. The basic principles behind MACA are Request-To-Send (RTS) and Clear-To-Send (CTS) messages, along with a backoff algorithm. The first thing MACAW does is to adjust the backoff algorithm to use multiplicative-increase linear-decrease (MILD) as opposed to binary exponential backoff (BEB) to reduce oscillation in backoff times, and adds backoff copying to prevent starvation. MACAW then adds the notion of keeping separate queues for each stream sent as opposed to one queue for the sender as a whole to achieve a sort of intuitive fairness (not precisely defined here) across flows. It then introduces four changes to the RTS-CTS message exchange algorithm. These are (1) acknowledgment (ACK) messages to avoid transport layer retransmission backoffs, (2) Data-Sending (DS) messages to indicate the beginning of data transmission, (3) Request-for-Request-to-Send (RRTS) to allow a receiver to contend on behalf of a sender when the receiver was previously unable to respond to an RTS due to contention, and (4) a procedure for multicast. MACAW then again refines the backoff algorithm by making each station maintain a backoff counter for each stream that reflects congestion at both the sender and the receiver.

All evaluation of MACAW was done via simulation. The authors mention several design options they chose not to implement, including piggy-backed ACKs, NACKs, and the use of carrier-sense or intermediate options involving clean signals, and they also describe alternative mechanisms that are entirely different from MACAW, such as token-based schemes and polling or reservations. They admit there are problems that arise in certain situations that they have not solved and their solution in the multicast case is not good. They also admit that they don’t have a precise definition of fairness.

Critique

I liked this paper’s candidness about the shortcomings of their approach. I did not like that they performed all evaluations using simulations instead of attempting a real-world evaluation. It would have been nice if they could have implemented some of the design alternatives mentioned, such as NACKs. I would think that since they are only using simulations that this would have been relatively easy to do. I wish they would have said what their ideas were for dealing with the multicast problem better. I’m sure they had some ideas. One obvious idea is to have the sender send a special Multicast-Request-To-Send (MRTS) message to each of the multicast receivers in turn to avoid contention for the CTS messages from the receivers. The MRTS message could indicate to the receivers that they will have to wait some time before receiving the DS message and the data. I’m sure there are problems with this solution and it wouldn’t work for all multicast situations but it just would have been nice if they had talked about some of the potential solutions and their shortcomings at a little more depth. Overall I liked this paper though because it seems like it probably laid the groundwork for a lot of later wireless protocols and it was easy to read. Their explanations and examples were very nice and clean and they explained the evolution and reasoning behind their design well.