17-08-2012, 04:29 PM
Buffer Sizing for 802.11 Based Networks
buffersizing.pdf (Size: 527.76 KB / Downloads: 43)
INTRODUCTION
In communication networks, buffers are used to accommodate
short-term packet bursts so as to mitigate packet drops
and to maintain high link efficiency. Packets are queued if
too many packets arrive in a sufficiently short interval of time
during which a network device lacks the capacity to process
all of them immediately.
For wired routers, the sizing of buffers is an active research
topic ([31] [5] [27] [32] [9]). The classical rule of thumb for
sizing wired buffers is to set buffer sizes to be the product of
the bandwidth and the average delay of the flows utilizing this
link, namely the Bandwidth-Delay Product (BDP) rule [31].
See Section VII for discussion of other related work.
Surprisingly, however the sizing of buffers in wireless
networks (especially those based on 802.11/802.11e) appears
to have received very little attention within the networking
community. Exceptions include the recent work in [21] relating
to buffer sizing for voice traffic in 802.11e [2] WLANs, work
in [23] which considers the impact of buffer sizing on TCP
upload/download fairness, and work in [29] which is related
to 802.11e parameter settings.
PRELIMINARIES
IEEE 802.11a/b/g WLANs all share a common MAC algorithm
called the Distributed Coordinated Function (DCF)
which is a CSMA/CA based algorithm. On detecting the
wireless medium to be idle for a period DIFS, each wireless
station initializes a backoff counter to a random number
selected uniformly from the interval [0, CW-1] where CW
is the contention window. Time is slotted and the backoff
counter is decremented each slot that the medium is idle.
An important feature is that the countdown halts when the
medium is detected busy and only resumes after the medium
is idle again for a period DIFS. On the counter reaching
zero, a station transmits a packet. If a collision occurs (two or
more stations transmit simultaneously), CW is doubled and the
process repeated. On a successful transmission, CW is reset
to the value CWmin and a new countdown starts.
MOTIVATION AND OBJECTIVES
Wireless communication in 802.11 networks is time-varying
in nature, i.e., the mean service time and the distribution of
service time at a wireless station vary in time. The variations
are primarily due to (i) changes in the number of active
wireless stations and their load (i.e. offered load on the
WLAN) and (ii) changes in the physical transmit rate used
(i.e. in response to changing radio channel conditions). In the
latter case, it is straightforward to see that the service time can
be easily increased/decreased using low/high physical layer
rates. To see the impact of offered load on the service time at
a station, Fig. 2 plots the measured distribution of the MAC
layer service time when there are 2 and 12 stations active. It
can be seen that the mean service time changes by over an
order of magnitude as the number of stations varies. Observe
also from these measured distributions that there are significant
fluctuations in the service time for a given fixed load. This is a
direct consequence of the stochastic nature of the CSMA/CA
contention mechanism used by the 802.11/802.11e MAC.
EMULATING BDP
We begin by considering a simple adaptive algorithm based
on the classical BDP rule. Although this algorithm cannot
take advantage of statistical multiplexing opportunities, it is
of interest both for its simplicity and because it will play a
role in the more sophisticated A algorithm developed in the
next section.
As noted previously, and in contrast to wired networks,
in 802.11 WLANs the mean service time is generally timevarying
(dependent on WLAN load and the physical transmit
rate selected by a station). Consequently, there does not exist a
fixed BDP value. However, we note that a wireless station can
measure its own packet service times by direct observation,
i.e., by recording the time between a packet arriving at the
head of the network interface queue ts and being successfully
transmitted te (which is indicated by receiving correctly the
corresponding MAC ACK). Note that this measurement can
be readily implemented in real devices, e.g. by asking the
hardware to raise an interrupt on receipt of a MAC ACK,
and incurs only a minor computational burden.
CONCLUSIONS
We consider the sizing of network buffers in 802.11 based
wireless networks. Wireless networks face a number of fundamental
issues that do not arise in wired networks. We
demonstrate that the use of fixed size buffers in 802.11
networks inevitably leads to either undesirable channel underutilization
or unnecessary high delays. We present two novel
buffer sizing algorithms that achieve high throughput while
maintaining low delay across a wide range of network conditions.
Experimental measurements demonstrate the utility of
the proposed algorithms in a real environment with real traffic.
The source code used in the NS-2 simulations and the
experimental implementation in MadWifi can be downloaded
from www.hamilton.ie/tianji li/buffersizing.html.