Monday, September 29, 2008

Solving problems in the early days of wireless

Is it weird that this paper from '94 feels like ancient CS history? Maybe it is just in my head, but reading any paper from PARC causes me to assume the paper is likely old and likely influential.

This paper picked up where Phil Karn left off with MACA which was "just an idea" that Karn had introduced to handle the hidden terminal scenario more effectively than CSMA.

They proposed that collisions should be detected and avoided at the receivers, an idea pioneered by Karn with Multiple Access Collision Avoidance ("MACA is an acronym, not a spanish word"). This is in contrast to detecting collision from the sender's perspective, as was done with CSMA (Carrier Sense Multiple Access).

As Karn said, "Much simulation and experimental work needs to be done to answer many questions about how well it [MACA] will really work." Shenker et al took this to heart, and proposed MACA for wireless, or MACAW, which addressed some of the issues they observed in MACA, such as the use of Binary Exponential Backoff (BEB) which quickly led to unfairness in collision resolution.

They also address the problem for nodes [A] [B] [C], if C overhears an RTS from B to A, it can't tell if B is sending since "C cannot tell if the RTS-CTS exchange was a success and so does not know if B is indeed transmitting data." They chose to solve this by having the sender emit a Data Sending (DS) packet.

They also introduce, with nearly comic academic timing, the Request-for-Request-To-Send (RRTS) packet, which solves another fairness problem of two receivers in range of each other with senders out of range of each other and with one pair transmitting much smaller packets than the other. The RRTS solves an unfairness problem which feels a lot like the problem introduced by BEB.

  • Multiplicative Increase Linear Decrease (MILD) of the backoff interval seems very similar to the concept of Additive Increase Multiplicative Decrease (AIMD) of cwnd in TCP congestion control.


Ashima Atul said...

I somehow felt that the authors introduced too many modifications to work well for their network and made the protocol very complicated. I wonder what is standard technique is used these days in wireless networks.

beth said...

I love your use of Karn's quotes, grounding the paper in the context of a research discussion amongst academics. I also agree with Ashima about the bombardment of features :)