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.

Analysis and Simulation of a Fair Queueing Algorithm

A. Demers, S. Keshav, S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," Internetworking: Research and Experience, 1 (1990), pp. 3-26.

One line summary: This paper proposes a fair queueing algorithm for congestion control at gateways and provides analysis and simulation results for this algorithm.

Summary

This paper proposes a fair queueing algorithm for congestion control at gateways. As the authors point out, there are two points at which congestion control can be implemented. The first is at the source and the second is at the gateways. At the source, flow control algorithms, while not directly designed to control congestion, do affect overall network traffic. At the gateways, congestion control can be implemented through routing algorithms, such as adaptive routing, and through queueing algorithms, which affect congestion indirectly. This paper focuses on the latter.

The authors note that queueing algorithms can be thought of as allocating bandwidth, promptness, and buffer space. The most commonly used queueing algorithm, first-come-first-served (FCFS) does not address each of these things separately. The authors argue that it is important to consider how flow control algorithms interact with queueing algorithms to affect network congestion. With this in mind, a major shortcoming of FCFS is that it does not provide good congestion control in the presence of ill-behaved sources in the network i.e. sources that do not provide good flow control and thus flood the network with packets. Such ill-behaving sources can unfairly capture high portions of the outgoing bandwidth of gateways implementing FCFS. In response to this, the authors propose a fair queueing (FQ) algorithm.

The authors’ requirements of their algorithm are: it must be able to allocate bandwidth and buffer space fairly; it must be able to control promptness/delay somewhat independently of bandwidth and buffer space; and it should provide service that does not depend discontinuously on a packet’s time of arrival. To define fair, the authors use the max-min fairness criteria, which state that an allocation is fair if (1) no user receives more than it requests, (2) no other allocation satisfying the first condition has a higher minimum allocation, and (3) the second condition remains recursively true as the minimal user is removed and the total resource amount reduced accordingly. The authors define a user as a source-destination pair, or a conversation. They then define their algorithm, which is based on a packetized version of a bit-by-bit round-robin scheme. Essentially, they first allocate a queue to each conversation. Then they consider the packets at the head of the queue, and estimate what they call the ‘finish time’ for these packets, which is the time at which the packet would finish being serviced. Finally, the algorithm selects the packet with the lowest finish time for transmission. The authors build upon this algorithm by introducing an additional factor that they call the bid. In this improved version of the algorithm, the packets are selected for transmission based on their bid, which is calculated in such a way as to provide less delay to users using less than their fair share of bandwidth. When the gateway’s buffers begin to fill, it must choose packets to drop. The way the authors’ algorithm selects a packet to drop is by choosing the last packet from the user currently using the most buffer space.

The authors then analyze their algorithm with respect to two types of sources: FTP-like sources and telnet-like sources. They do a bunch of annoying math and conclude that their algorithm is indeed able to provide lower delay to lower throughput sources. They then consider their algorithm with respect to flow control algorithms. They consider three types, (1) generic flow control algorithms using a timeout mechanism and a sliding window of set size, (2) second generation flow control algorithms using dynamic window sizes, fast retransmits, improved timeout calculation, and congestion signals, and (3) third generation flow control algorithms, which are similar to the second except that congestion signals are sent selectively. They select one flow control algorithm from each category and use them each with their FQ algorithm and with the FCFS algorithm to compare the two via simulation. They provide a lot of results but the main lesson from these is that FQ gateways cannot control congestion by themselves but can help protect from ill-behaved sources. Their FQ algorithm isn’t perfect and its performance depends a lot on the flow control algorithm used and the specific network dynamics, but it still provides much better fairness than FCFS.

Critique

There are a few things I didn’t like about this paper. I found all their mathematical analysis a bit much. It was annoying to read, especially the preemptive versus nonpreemtive bit, which didn’t factor in much anywhere else in the paper. I think it would have been better if the authors included all the mathematical details in an appendix and used the space instead to state their main point and conclusion of all that analysis, which as far as I can tell, they did in just one sentence out of 3-5 pages. The unused space then could have been used to provide some psuedocode or examples of their algorithm in action. These things would have made their paper much more appealing.

The authors also point out that there are objections to their algorithm, which might be interesting to discuss. The first objection is that some source-destination pairs, such as mail servers, need more than their fair share of bandwidth. The second is that their algorithm is too complicated to implement on routers in a such a way that it could run fast enough to match the speed of the links. It wouldn’t be very useful or compelling if their algorithm slowed the routers down.