V. Bharghavan, A. Demers, S. Shenker, L. Zhang, “MACAW: A Media Access Protocol for Wireless LANs,” ACM SIGCOMM Conference, (August 1994). [PDF]

Summary

The media in a wireless network is a shared and scarce resource; as a result, controlling access to this shared media to maximize performance is one of the key issues in wireless networks literature. This paper presents a media access protocol, MACAW, for single channel wireless LAN building upon preexisting MACA (Multiple Access, Collision Avoidance) protocol with an aim to increase performance and fairness among contending wireless nodes. The design of MACAW is based on four observations:

1. Relevant contention occurs at the receiver; sensing carrier at the sender (as in CSMA) is inappropriate
2. Congestion is location dependent
3. For fair allocation, collision (congestion) information must be shared among devices
4. Information related to contention period must be synchronized among devices to promote fair contention

In this work, the authors also assume that there is no interference nor capture (one signal overpowering another) of signals; a station successfully receives a packet if and only if there is exactly one active transmitter within its range. In addition, they also assume that communication is symmetric.

MACA Briefing

MACA uses two types of short, fixed-length (32 byte) signaling packets: RTS (Request-to-Send) and CTS (Clear-to-Send). When a station wants to send something, it sends an RTS first. If the receiver is free, it replies with an CTS. Upon receiving CTS, the sender immediately sends data. Any station overhearing RTS waits long enough for a CTS to pass through. Anyone, overhearing CTS waits for the length of data (length of data is carried in signaling headers). As a result, hidden-terminal problem is completely avoided and exposed-terminal problem is simplified. If the sender does not receive CTS within some period, it will time out and schedule for retransmission using a binary exponential backoff (BEB).

MACAW

MACAW design is based on the observations mentioned before as well as the limitations of MACA. A brief summary follows:

• Backoff algorithm: MACAW replaces BEB with MILD (multiplicative increase and linear decrease) to ensure that backoff interval grows a bit slowly (1.5x instead of 2x) and shrinks really slowly (linearly to minimum value). To enable better congestion detection, MACAW shares backoff timers among stations by putting this info in headers.
• Multiple stream model: MACAW uses separate queues for each stream in each node for increased fairness. In addition, each queue runs independent backoff algorithms. However, all stations attempting to communicate with the same receiver should use the same backoff value.
• Basic exchange: MACAW replaces RTS-CTS-DATA to RTS-CTS-DS-DATA-ACK with the following extensions:
  1. ACK: An extra ACK at the end ensures that errors can be recovered in the link layer, which is much faster than transport layer recovery. If an ACK is lost, next RTS can generate another ACK for the previous transmission.
  2. DS: This signal ensures a 3-way handshake between sender and receiver (similar to TCP) so that everyone within hearing distance of the two stations know that a data transmission is about to happen. Without the DS packet, stations vying for the shared media cannot compete properly and one is always starved due to the lack of its knowledge of the contention period. In short, DS enables synchronization.
  3. RRTS: RRTS is basically a proxy RTS, when the actual RTS sender is too far away to fight for the contention slot. However, there is one scenario where even RRTS cannot guarantee fair contention.
  4. Multicast: Multicast is handled by sending data right away after the RTS packet, without waiting for CTS. It suffers from the same problems as in CSMA, but the authors leave it as an open challenge.
• Evaluation: This paper presents simulation-based evaluation of MACAW, which shows that MACAW is fairer and gives higher throughput than MACA.

Comments

MACAW proposes significant improvement over MACA in terms performance and fairness. But the authors leave several issues unresolved in the paper: special RRTS scenario, multicast, impact of mobility etc. They also propose several extensions to MACAW as future works; what turned out of those?

To some extent MACAW(sort of) approximates TCP. MILD is similar to AIMD, inclusion of DS is akin to 3-way handshake in TCP, the ending ACK gives a sense of FIN. It would’ve been interesting to know what the authors thought about this.