Summary: MACAW

V. Bharghavan, A. Demers, S. Shenker, L. Zhang. MACAW: a media access protocol
for wireless LAN's. Sigcomm 94.

This paper describes MACAW, an extension of MACA, itself a MAC for wireless
networks. The MACAW protocol builds on MACA in several ways:

1. The link layer is in a much better position to request retransmits than the
transport layer. This is because it can use its knowledge of the control
frames in order to determine if some other node attempted but failed to send
it data. The transport layer lacks this knowledge, and must instead simply
wait for a timeout. Therefore, a link-level acknowledgement was added.

2. The authors note that the "exposed node" problem is not completely solved
with RTS/CTS. Consider the case where a sender is currently overhearing
someone elses DATA frame. If the sender were to transmit an RTS, he would be
unable to hear the corresponding CTS, and thus no data would be transferred
even though the intended receiver might be open. In other words, there's no
point to sending a RTS if you know that you won't be able to hear the CTS.
This is solvable using carrier sense to determine if another nearby
transmitter is active. The authors provide an alternative solution which
involves having senders transmit a DS frame, which warns all nearby devices
that they are about to transmit a DATA frame, and it would therefore be
pointless to transmit a RTS.

3. The authors make extensive changes to the backoff protocol in order to make
it more fair. For example, they note that dividing bandwidth evenly among
hosts is probably not a "fair" arrangement, especially since the base station
will typically have flows to multiple client devices. Instead, they suggest
that bandwidth should be allocated per flow, and describe how this can be
done.

4. A mechanism was added to allow the receiver to contend for the channel on
behalf of the sender. This is necessary to prevent cases where a receiver
repeatedly finds itself unable to issue a CTS because it knows others are
receiving DATA frames in the area. This causes the sender to backoff, and
not receive a fair chance to transmit. The solution is to add a RRTS frame
which is sent by the receiver if it had to suppress a CTS once the medium
becomes available.

5. The authors used a system to distribute backoff values so that one flow
didn't monopolize the media. This scheme became pretty complicated in order
to keep one congested cell from unnecessarily affecting the performance in
other cells.

This is a pretty interesting paper as it shows how a seemingly small change to
a problem (ie. changing collisions from a global to local phenomenon) can
require an entirely new solution. It also shows the power of simulation for
exploring a complex problem.

One possible problem with this paper might be its "whack-a-mole" approach. I
got the impression that each time the authors found a new unhandled case,
they simply added an extra frame. Later, they discovered that additions
interacted with each other to cause some subtle complication, and therefore
made an additional change, and so on. One example would be the addition of
the ACK complicating the handing of the exposed node problem (see footnote
7). Also consider the fairly complex logic that was needed in the end in
order to compute the backoff value came about because of the "copy BEB"
scheme described earlier in the paper. In the end, the protocol became very
complicated, which can make it difficult to create bug-free implementations.
Received on Thu Sep 21 2006 - 09:55:22 EDT