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 Tue Sep 26 2006 - 02:20:22 EDT