Abstract :

If you have a CSMA network in which each link can only sense a subset of other links, and they compete for network access using the CSMA protocol, how much throughput will each link get? This talk is about an investigation that started with our accidental discovery of a pattern of throughput distributions among links in IEEE 802.11 networks from experiments. This pattern gives rise to an easy computation method, which we term back-of-the-envelop (BoE) computation. For modest-size networks, very accurate results can be obtained within minutes, if not seconds, by simple hand computation accessible to primary-school kids. BoE beats prior methods in terms of both speed and accuracy. While the computation procedure of BoE is simple, explaining why it works is by no means trivial. In this talk, I will show how BoE can be explained by an ideal CSMA-network model, which models a CSMA link as an on-off process, and the interactions among links as the interactions among their on-off processes. In developing the theory, we discovered a number of analytical techniques and observations that have eluded prior research, such as that the carrier-sensing interactions among links in an ideal CSMA network result in a system state evolution that is time-reversible; and that the probability distribution of the system state is insensitive to the distributions of the "on" and "off" durations given their means, and is a Markov random field. We believe these theoretical frameworks are useful not just for explaining BoE, but could also be a foundation for a fundamental understanding of how links in CSMA networks interact.