“MACAW: A Media Access Protocol for Wireless LAN’s”

This paper proposes an improved media access protocol for wireless LANs. A “media access protocol” is a link-layer protocol for allocating access to a shared medium (i.e. a wireless channel) among multiple transmitters. MACAW is a media access protocol for mobile pads that communicate wirelessly with base stations; each base station can hear transmission from pads within a certain range of its location, called a cell.

This is a challenging problem for several reasons:

  • Transmitters are mobile, but location information is not communicated explicitly: a transmitter simply moves or a new transmitter comes into the area, and the media access protocol must adapt.
  • Connectivity is not transitive. For example, A and B can communicate, as can B and C, but A and C might not be able to; the protocol must be designed so that communications between B and C do not disrupt A, even though A has no direct knowledge of C.
  • Due to noise, communication may not be symmetric (A can hear B, but B cannot hear A), and transmitters may interfere with one another (A might be out of range of B, but A’s transmissions might still disrupt B’s ability to communicate).

The MACAW paper ignores both asymmetry and interference: they assume a simplified model in which two stations are either in range of one another or they aren’t; a transmission is successfully received iff there is only one active transmitter in range of the receiver; and no two base stations are within range of one another. Importantly, contention between transmissions occurs at the receiver of the transmission, not the sender: that is, two nodes can transmit different messages from the same area at once, but two nodes in the same area cannot simultaneously receive different messages. Their goal is a media access protocol that is both efficient (high utilization of the available media), and fair (each station gets its “fair share”).

MACA

MACAW is an improved version of an earlier wireless media access protocol called MACA. MACA proceeds as follows:

  • Before sending a message, the transmitter sends a RTS control message (“ready to send”), containing the length of the upcoming data message. The time taken to transmit a control message (~30 bytes) is called a slot.
  • If the receiver hears the RTS and is not currently “deferring,” it replies with a CTS control message (“clear to send”), which includes a copy of the length field from the RTS.
  • Any station that hears a CTS defers any transmissions for long enough to allow someone to send a data message of the specified length. This avoids colliding with the CTS sender (the receiver of the upcoming data message).
  • Any station that hears an RTS defers any transmissions for a single slot (long enough for the reply CTS to be received, but not long enough for the actual data message to be sent, because contention is receiver-local).
  • Backoff: if no CTS response is received for an RTS, the sender must retransmit the RTS. It waits an integer number of slots before retransmitting, where that integer is chosen randomly between 1 and BO, the backoff counter. BO is doubled for every retransmit, and reduced to 1 for every successful RTS-CTS pair.

MACAW

MACAW is proposed as a series of improvements to the basic MACA algorithm. First, they suggest a less aggressive backoff algorithm: the exponential increase / reset to 1 policy of MACA leads to large oscillations in the retransmission interval. They propose increasing BO by 1.5 after a timeout, and decreasing it by 1 after a successful RTS-CTS pair. They also arrange for the value of the backoff counter to be communicated between clients: this avoids a client with a lower backoff counter starving other clients from accessing the media. Finally, they changed the backoff counter to be per-destination, rather than a single counter: the observation here is that the backoff counter should measure congestion, and there is not a single homogeneous level of congestion in a typical wireless deployment.

Second, they propose that receivers should send an ACK to the sender after successfully receiving a data message. This is suggested because the minimum TCP retransmission timeout is relatively long (0.5 seconds at the time), so it takes a long time to recover from lost or corrupted messages. A link layer timeout can be more aggressive, because it can take advantage of knowledge of the latency of the individual link (rather than the end-to-end timeout in TCP). This isn’t inconsistent with the end-to-end argument: the link-layer timeout is not necessary for the correctness of TCP; it is just a performance optimization.

Third, they propose two related techniques for allowing transmitters to avoid contention more effectively:

  1. A DS packet should be sent after a successful RTS-CTS exchange, just before the data message itself. The idea here is to explicitly announce that the RTS-CTS succeeded, so that if a pad can hear an RTS but not the CTS response, it does not attempt to transmit a message during the subsequent data transfer period. The reasoning here is subtle: as noted before, contention is only at the receiver, so one wouldn’t think that a node that can hear the RTS but not the CTS should avoid transmitting. However, sending a message requires that the sender hear the CTS response (as well as the eventual ACK); therefore, if another node within range is sending, it would be pointless to also try to transmit.
  2. Suppose that two pads A and B in different cells both want to receive rapidly, but are close enough that they contend with one another. If pad A “wins” (completes the RTS-CTS pair), and it will effectively monopolize the channel: B will be unlikely to ever send a CTS response, because to do so it would need to receive the RTS at exactly the right time (just after A has finished receiving a data message). The authors propose a fix: if a receiver hears an RTS while it is deferring any transmissions, at the end of the deferral period it replies with an RRTS (“ready for RTS”) packet, prompting the sender to resend the RTS. However, the authors note that this solution is imperfect: if A is receiving data constantly, it is unlikely that B will ever hear the RTS, so it won’t know to send the RRTS.

Note that the best-case performance of MACAW is actually lower than that of MACA, because the additional ACK and DS messages sent by MACAW incur overhead. However, MACAW is much more resistant to interference, and ensures much fairer allocation of the medium among different transmitters.

Comments

I thought the paper was quite readable, and is a clear improvement over the prior work. However, there’s a downside to their presentation style: they begin with MACA, and then propose a series of incremental improvements that are each designed to address a shortcoming of MACA in a particular situation. However, some of their improvements actually degrade performance in other situations. It is hard to get an idea of how a given protocol change will behave in the full complexity of a field deployment from the paper.

Advertisements

1 Comment

Filed under Paper Summaries

One response to ““MACAW: A Media Access Protocol for Wireless LAN’s”

  1. Pingback: “ExOr: Opportunistic Multi-Hop Routing for Wireless Networks” « Everything is Data

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s