BackoftheEnvelope
Computation of Throughput Distributions in CSMA
Wireless Networks
By

Prof.
Liew Soung Chang
Department
of Information Engineering

The
Chinese University of Hong Kong

Date:
Feb 9, 2009 
Time:
4:30p.m.  5:30p.m. 
Venue:
Rm. 121, Ho Sin Hang Engineering Building, CUHK 
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 backoftheenvelop
(BoE) computation. For modestsize networks, very
accurate results can be obtained within minutes, if
not seconds, by simple hand computation accessible
to primaryschool 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 CSMAnetwork
model, which models a CSMA link as an onoff process,
and the interactions among links as the interactions
among their onoff processes. In developing the theory,
we discovered a number of analytical techniques and
observations that have eluded prior research, such
as that the carriersensing interactions among links
in an ideal CSMA network result in a system state
evolution that is timereversible; 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.
