Back-of-the-Envelope Computation of Throughput Distributions in CSMA Wireless Networks

Speaker:	Professor Soung Chang LIEW
		Chairman, Department of Information Engineering
		The Chinese University of Hong Kong

Title:		"Back-of-the-Envelope Computation of Throughput
	 	 Distributions in CSMA Wireless Networks"

Date:		Monday, 18 February 2008

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F
		(Leung Yat Sing Lecture Theatre, near lifts 25/26)
		HKUST

Abstract:

If you have a CSMA network in which each link can only sense a subset of
other links, how much throughput will each link get? This talk is about an
investigation that was triggered by 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 throughput computation
method accessible even to primary-school kids, which we term
back-of-the-envelop (BoE) computation. For modest-size networks, very
accurate results (close-to-perfect match with NS2 simulation results) can
be obtained within minutes, if not seconds. 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 theoretically
by an ideal CSMA-network model. 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 system-state probability distribution is
insensitive to the distributions of countdown and transmission times given
their means, and is a Markov random field. We believe the ideal CSMA
network model is useful not just for explaining BoE, but also provides a
quantitative foundation for tackling other problems in CSMA networking
(e.g., resource allocation).  This talk will also present the relationship
between the mathematics of CSMA networks and statistical physics.


******************
Biography:

Prof. Soung LIEW received his undergraduate and Ph.D. degrees from MIT.
From March 1988 to July 1993, Soung worked at Bellcore (now Telcordia),
New Jersey. He is currently Professor and Chairman of the Department of
Information Engineering, CUHK. Soung's current research focuses on
wireless networking. Some recent papers from his research group are as
follows (Complete publications can be found in www.ie.cuhk.edu.hk/soung):

[1] "TCP Veno: TCP Enhancement for Transmission over Wireless Access
Networks," IEEE JSAC, vol. 21, no. 2, Feb 2003. [TCP Veno has recently
been incorporated into the Linux OS release. According to Web of Science,
it was among the top ten cited SCI papers related to TCP from 2003 to
2007. ]

[2] "Solutions to Performance Problems in VoIP over 802.11 Wireless LAN,"
IEEE Trans. Vehic. Tech., vol. 54, no. 1, Jan 2005. [Most cited paper in
google.scholar under the keywords "VoIP WLAN".]

[3] "Offered Load Control in IEEE 802.11 Multi-hop Ad-hoc Networks," IEEE
MASS, Oct 2004 [Best Paper Award]. Journal version, "Throughput Analysis
of IEEE802.11 Multi-hop Ad-hoc Networks," IEEE/ACM Trans. Networking, vol.
15, no. 2, June 2007.

[4] "Re-routing Instability in IEEE 802.11 Multi-hop Ad-hoc Networks,"
IEEE WLN, Nov 2004 [Best Paper Award].

[5] "Physical-Layer Network Coding," ACM Mobicom 2006, Sept 2006.