1

H-RCA: 802.11 Collision-aware Rate Control

K. D. Huang, K. R. Duffy and D. Malone

Abstract— Rate control methodologies that are currently avail- have packets to send and are availing of the 802.11a rate-
able in 802.11 network cards seriously under-utilize network set, it plots per-second total network throughput with five
resources and, in addition, per-second throughputs suffer from minute mean reported in the legend. In each experiment, all
high variability. In this article we introduce an algorithm, H-
RCA, that overcomes these shortcomings, giving substantially stations are utilizing one of Minstrel [2], SampleRate, [3],
higher, and less variable, throughput. The approach solely uses AMRR [4] or Onoe [5] as implemented in the MadWiFi
information already available at the driver-level to function and driver for the Atheros chipset or RRAA [6] as implemented
can be implemented on 802.11e commodity hardware. by us. Also plotted is the same scenario but with the stations
H-RCA’s design objective is to minimize the average time each using the paradigm introduced in the present article, H-RCA,
packet spends on the medium (including retries) in order to
maximize total network throughput. It uses a development of a
demonstrating the gains in utilization that are possible with it.
recently proposed estimation scheme to distinguish transmission
failures due to collisions from those caused by channel noise. Saturated, 5STAs
It employs an estimate of the packet loss ratio due to noise in 35
H-RCA (mean 24.5Mb/s)
assessing whether it is appropriate to change rate. We demon- Minstrel (mean 20.4Mb/s)
30 Sample (mean 14.6Mb/s)
strate experimentally that packet loss ratio is not necessarily a RRAA (mean 15.8Mb/s)
AMRR (mean 5.3Mb/s)
monotonic increasing function of rate; this is accounted for in

Network Throughput (Mb/s)

25 Onoe (mean 3.0Mb/s)
H-RCA’s design.
As H-RCA statistically separates noise losses from those caused 20
by collisions, ns-2 simulations show that it is robust to changing
environments. H-RCA does not require specific hardware support 15

nor any change to the IEEE 802.11 protocol. This point is 10

substantiated with results from an experimental implementation.
5
Index Terms— Rate Control, Collision-aware, WLAN, IEEE
802.11, TXOP. 0
0 50 100 150 200 250 300
Time (sec)

I. I NTRODUCTION Fig. 1. WLAN consisting of 5 stations that always have 1,000 B packets
to send using the 802.11a rate-set and a minimum contention window of 16.
IEEE 802.11 is the world’s most commonly deployed Throughputs for five existing rate control algorithms, Minstrel, SampleRate,
WLAN technology. It supports several physical layer transmis- RRAA, AMRR and Onoe, as well as the methodology proposed in this article,
sion rates, with 802.11b having four (1, 2, 5.5 and 11 Mb/s), H-RCA. Experimental data
802.11a having eight (6, 9, 12, 18, 24, 36, 48 and 54 Mb/s),
while 802.11g has all twelve of the 802.11b and 802.11a rates, In this article we propose a principled design for a RC algo-
and 802.11n has eight when using two streams at 20 Mhz rithm, H-RCA, that is applicable to all 802.11 rate-sets and is
and a guard interval of 800ns (13, 26, 39, 52, 78, 104, 117, 130 implementable on commodity hardware that supports 802.11e
Mb/s). A range of rates are available as their modulation and functionality. H-RCA’s objective is to minimize the average
coding schemes give them distinct robustness characteristics time each packet spends on the medium, including MAC
to noise on the medium. To maximize network performance, layer retries, in a fully decentralized fashion with no message
each station needs to select an appropriate rate for its current passing. It employs a development of a recently proposed
channel conditions. Rate Control (RC) algorithms that choose censored data technique based on the IEEE 802.11e TXOP1
modulation and coding scheme pairs are designed for this feature to distinguish transmission failures caused by collisions
purpose. from those caused by noise [7]. H-RCA makes transmission
The 802.11 protocol has been the subject of extensive rate choices based on the Packet Loss Ratio (PLR) due to noise
research since the mid 1990s. Despite this, the RC algo- alone2 , with Bayesian analysis used to determine rate-decrease
rithms that are currently implemented in hardware can be decisions and an opportunity-cost metric used to determine
wasteful of air-time resources, particularly in the presence of the frequency at which rate-increase decisions are made. H-
collision-based losses, leading to poor network performance RCA does not alter the 802.11 MAC and can be implemented
[1]. For example, using the experimental apparatus described on existing network cards that possess 802.11e functionality.
in Appendix I, Fig. 1 provides a representative illustration of We give a concrete guide to the approach through detailed
these shortcomings. In a network of 5 stations that always consideration of the 802.11a rate-set, including performance
Hamilton Institute, NUI Maynooth. SFI grant RFP-07-ENEF530 and The
1 If 802.11e is not supported, this technique can use fragmentation in lieu
research leading to these results has received funding from the European
Community’s Seventh Framework Programme (FP7-ICT-2009-5) under grant of TXOP, but at the expense of increased overhead.
agreement n. 257263 (FLAVIA project). 2 We reserve PLR for failures due to noise, not collision.
2

evaluation in simulation as well as initial results from an back-to-back frames using a fragmentation scheme when chan-
experimental implementation. nel quality is good. CHARM [13] leverages reciprocity of the
The rest of this paper is organized as follows. In Section II wireless channel to estimate average SNR at the receiver using
we describe related work. The H-RCA paradigm is defined in packets overheard from the receiver to avoid the RTS/CTS
Section III and the reasoning behind its settings explained. overhead. It is not trivial, however, for the transmitter to
During our worked example in Section III-A, through the accurately estimate the SNR at the receiver because signal
use of experiments, we demonstrate that for a fixed signal to strength exhibits significant variations on a per-packet basis
noise ratio (SNR) the robustness of 802.11a rates to channel [17].
noise can be, surprisingly, not a monotonic decreasing function
of increasing rate. These experiments support the theoretical
B. Packet-Loss Based Estimates
prediction [8][9] that the 802.11a 9 Mb/s rate is redundant.
As it is not feasible to create an experimental setup with Using packet loss information to infer channel conditions
controllable losses due to noise, Section IV presents ns-2 simu- is the second option. Automatic Rate Fallback (ARF) is a
lation results illustrating H-RCA’s performance for an 802.11a scheme that uses patterns of packet losses as a trigger to
WLAN. These simulations reveal the merits of the approach change the transmission rate [15]. Adaptive ARF (AARF)
in terms of throughput consistency in a fixed environment, continuously changes the threshold that decides when to try
adaptivity to changing channel conditions and robustness to a higher rate to better reflect current channel conditions [4].
collision-based transmission failures. As experimental systems Adaptive Multi Rate Retry (AMRR) is AARF’s practical
can expose difficulties not captured by theory or simulations, realization. Its key idea is to use binary-exponential-backoff to
in Section V we report on an experimental implementation control the probing period to sample other rates. The algorithm
of H-RCA for the 802.11a rate-set where it shows significant initially switches to a higher rate when ten consecutive packets
throughput gains over RC algorithms that are available with have been transmitted without any failure and moves to a
current hardware. The paper concludes with a discussion in lower rate if two consecutive packets are not acknowledged. If
Section VI. packet failure occurs when a higher data rate is sampled, the
interval for the next higher data rate sampling is exponentially
increased. For these approaches to function correctly in a
II. R ELATED W ORK
network with more than one active transmitter, the algorithm
The IEEE 802.11 standard does not specify details of would need a mechanism to distinguish between transmission
the RC algorithm to be used, so that 802.11 card vendors failures caused by collision and those caused by noise on the
and researchers have proposed and implemented a variety channel.
of algorithms. There are two distinct strategies for RC al- Some algorithms use the RTS/CTS scheme to identify
gorithms. The first is the explorative type. In this approach failed transmissions due to collisions. If the first attempted
the entire rate space is explored periodically to empirically transmission of a packet fails, CARA [16] uses RTS/CTS to
identify the optimal rate. Examples of algorithms of this test whether failure is caused by collision or noise. Since
type include SampleRate [3], RBAR [10], OAR [11], WOOF RTS/CTS costs substantial time on the medium, RRAA [6]
[12], CHARM [13] and Smart-rate [14]. The second strategy reduces the frequency of using RTS/CTS. RRAA uses frame
is the incremental type where algorithms record statistics loss information gathered over tens of frames to adapt the
regarding their current rate and its neighboring rates, and rate and compares frame loss statistics both with and without
make incremental changes. Example RC algorithms of this RTS/CTS in order to decide if a loss is caused by collision or
type include ARF [15], AARF [4], CARA [16], RRAA [6], noise. It adaptively enables RTS/CTS more frequently as its
SGRA [17], COLLIE [18], SoftRate [19] and AccuRate [20]. estimate of the rate of failures due to collisions increases.
A number of these, including SampleRate, Minstrel [2], Onoe To avoid using RTS/CTS, WOOF [12] uses Channel Busy
[5] and AMRR [4], are implemented, for example, on the Time (CBT) as an indicator of network load. Higher CBT
Atheros chipset. means heavier traffic in the network, so that a transmission
The choice of rate should be based on current channel failure is more likely to be caused by collision rather than
conditions, so that a good estimate of channel quality is key noise. Running at the sender, COLLIE [18] analyzes the
to all RC algorithms. There are two dominant paradigms to patterns of bit errors in the received packet in order to infer
measure channel conditions: determine SNR directly from whether an error was due to a collision or the channel noise.
physical layer estimates; or estimate channel conditions in- Its rate adaptation protocol then solely depends upon channel
directly through packet loss information. noise failures. To detect bit errors, however, the COLLIE
receiver must echo the entire received frame to the sender,
incurring significant overhead. Running at the receiver, Soft-
A. Physical Layer Based Estimates Rate [19] uses hints exported by the physical layer to compute
The ideal information on which to base the choice of the the average Bit Error Rate (BER) for each received frame. To
transmission rate is SNR at the receiver. RBAR [10] uses an exclude failures due to collisions, it uses the ansatz that a
RTS/CTS exchange immediately prior to packet transmission sudden spike in bit errors is likely to have been caused by
to estimate SNR at the receiver and picks its rate accordingly. collision. The receiver sends its BER estimate to the sender
OAR [11] builds on RBAR and opportunistically transmits where it picks the best rate for the next frame. In order to
 3

observe the impact of collisions more clearly, it also adds a The H-RCA approach is to first evaluate the rate-set with
‘post-amble’ to every frame to enable the receiver to detect theory and experiment to determine if increasing rate nec-
with high probability the portion of the sender’s frame that essarily leads to a deterioration in PLR at each fixed level
lasts after the interference has ended. Thus SoftRate uses more of channel noise. This process identifies problematic rates for
time per frame on the medium and to implement it would incremental RC schemes. Theoretical predictions, for example,
require changes to hardware. suggest that the 9 Mb/s rate is redundant in 802.11a as the
To avoid hardware modifications, in [21] the authors use the higher 12 Mb/s rate always possesses greater robustness to
number of idle slots between two consecutive busy periods to noise [8][9] and we provide experimental evidence in support
estimate the number of active stations in the network. Having of this finding. As we consistently find this redundancy,
obtained an estimate of number of the active stations, using a including in experiments beyond those reported here, our
Bianchi-like model [22], the collision probability conditioned approach is to exclude 9 Mb/s. At a minimum, these results
on transmission can be estimated. Armed with this estimate clearly necessitate that any incremental RC algorithm must
one can estimate the packet loss probability due to noise. sample both the 9 Mb/s and 12 Mb/s rates when investigating
The information on the number of idle slots is not available, rate increase decisions from 6 Mb/s or risk under-performance.
however, in general commodity cards. Therefore, in [23] the RC algorithms need to make two decisions: when to in-
authors overcome this difficulty by using retry information in crease the rate and when to decrease it. Rate-increase deci-
802.11 MAC headers as an indicator of the channel condition, sions are necessarily exploratory as channel performance at
as each station can monitor the medium and get access to the higher rate must be determined from new observations.
the MAC header of every packet transmitted in the medium. Assuming lower rates are more robust, rate-decrease decisions
If a large number of retransmitted packets are observed, it is can be made based on channel observations at the current
inferred that the network is handling a high traffic load. rate. Thus these two decision making processes are distinct in
SampleRate [3] adopts a different strategy. It focuses on nature. We use an opportunity-cost paradigm to dictate the fre-
minimizing the service time required for successful transmis- quency of rate-increase decisions. For rate-decrease decisions,
sion of a packet. SampleRate uses frequent probing of different we employ a recently proposed censored data technique [7]
transmission rates to calculate the Expected Transmission to separate losses due to collisions from those due to noise,
Count (ETC) for each rate. The ETC represents the average followed by Bayesian decision making based on the resulting
number of transmission attempts required for successful re- statistics. The resulting algorithm makes rate change decisions
ception of a packet. The expected transmission time (ETT) based on pre-calculated thresholds that can be stored in a
is calculated using ETC information at a given transmission lookup table. These comparisons are executed by the host CPU
rate and accounts for the back-off time when the ETC metric and not by the wireless card’s firmware, so the algorithm’s
predicts that a retransmission is required. SampleRate then computational burden is, effectively, insignificant.
decides to transmit data packets using the rate with the lowest Use of the censored data technique based on TXOP de-
expected transmission time. Since SampleRate does not distin- veloped in [7] enables us to overcome a serious challenge
guish between transmission failures caused by collisions and common to all algorithms: the base hardware cannot distin-
those caused by noise, it may make erroneous rate selection guish transmission failures that occur due to collisions from
choices in the presence of collisions. those that occur due to noise on the medium. This is important
as if the rate of transmission failure increases there are two
potential explanations, each of which would dictate distinct
III. H-RCA corrective action. If the channel is experiencing increased
noise, transmission failures will result and the station should
An outline of the H-RCA methodology is as follows. change to a lower, more robust rate. If, however, more stations
A. Given a rate-set {r1 , . . . , rK } Mb/s sorted in increasing become active, there will be an increase in transmission failure
order, ri < ri+1 for all i ∈ {1, . . . , K − 1} (e.g. for due to collisions. In this case, the station should not select a
802.11a {6, 9, . . . , 54}), use theory and experiment to lower rate, as to do so would increase the time its packets
identify rates ri such that the PLR in given channel spend on the medium, leading to increased congestion.
conditions at rate ri is higher than the PLR for a higher The primary goal of H-RCA is to maximize throughput of
rate rj . These rates are excluded from H-RCA’s rate-set. the whole network in a decentralized way by minimizing the
B. To estimate PLR, H-RCA uses a technique based on average time each packet spends on the medium. Each station
TXOP to gain observations of packets solely susceptible aims to choose a rate that minimizes the air time that its
to loss through channel noise. packets spend on the medium, including retries. Alternative
C. Use theory or experiment to determine for each rate a objectives, such as each station selfishly maximizing its own
critical PLR value, the rate lowering threshold, above throughput, are discussed in Section VI.
which a lower rate would give higher throughput. To fully illustrate the H-RCA methodology, throughout the
D. Use Bayesian inference to determine if the PLR of the exposition we use the 802.11a rate-set as a working example.
current rate is above a rate lowering threshold. Namely, after the explanation of each H-RCA design step,
E. Set rate increase frequency so that the opportunity-cost we have a brief section specifically related to 802.11a. The
of sampling a higher rate is, in the worst-case, less than, 802.11a parameters are summarized in Table I. Formulae are
say, 5%. presented for H-RCA’s parameterization. In practice these
4

values could be determined dynamically or statically. For the appropriate when there is line of sight between the transmitter
purposes of this paper we use the latter, simpler scheme. and receiver, but no multi-path, no terrain-blocking and no
interference [26]. With packets containing 1,000 B payloads,
TABLE I
Fig. 2 shows the theoretical prediction of PLR vs. SNR for
802.11 A PARAMETERS
different transmission rates in the Rayleigh fading channel.
Parameters Default values Fig. 3 shows the equivalent plot for the Rician fading channel.
Minimum Contention Window 16 Predictions using the Rayleigh fading channel model reveal
Maximum Contention Window 1024 two redundant rates, 9 Mb/s and 18 Mb/s, as the former has a
Long Retry Limit 4
Short Retry Limit 7 higher PLR than the 12 Mb/s rate at every SNR while the latter
Slot Time 9 µs has higher PLR than 24 Mb/s at every SNR. For the Rician
SIFS Time 16 µs channel, only the 9 Mb/s rate appears redundant. Plots for the
DIFS Time 34 µs
Header Time 20 µs AWGN channel can be found elsewhere [8][9][24] and mimic
those shown here for Rician fading. Consequently, all of these
channel models suggest redundancy of the 9 Mb/s rate. The
18 Mb/s rate is only redundant in the Rayleigh channel model.
This suggests that adaptive RC algorithms should take care at
A. Rate-Set Characteristics rate increase/decrease decisions if 18 Mb/s performs poorly,
When employing an incremental algorithm RC approach, as it is possible, but not certain, that 24 Mb/s will perform
such as with H-RCA, it is necessary to determine a pri- better.
ori the relative robustness of rates in the available rate-set.
TABLE II
For the 802.11a and 802.11n rate-sets, it is possible to use
802.11 A T RANSMISSION R ATES
theory, simulation and experiments in this investigation. The
802.11b/g 5.5 and 11 Mb/s rates employ a Complementary Rate (Mb/s) Modulation Scheme FEC Rate
Code Keying modulation scheme. This scheme has proven 6 BPSK 1/2
9 BPSK 3/4
resistent to analytic study so that no theoretical framework 12 QPSK 1/2
for their performance analysis currently exists. Using pseudo- 18 QPSK 3/4
theory with manufacturer-fit curves and detailed experiments, 24 16QAM 1/2
36 16QAM 3/4
elsewhere we have shown that the 11 Mb/s rate in 802.11g is 48 64QAM 2/3
more robust that the 6 Mb/s rate [24]. 54 64QAM 3/4
1) Theoretical Prediction (802.11a): For this part of the
methodology, it is, perhaps, easiest to explain the procedure
by example. We first theoretically determine PLR as a function
of SNR. Table II summarizes the modulation and coding SNR vs. PLR in Rayleigh Channel
information for each rate supported by 802.11a. For RC 0

algorithms, the most significant feature of these rates is their ï1

robustness to noise at a given SNR. ï2
With a fixed transmission rate and a fixed SNR, the PLR
Packet Loss Ratio (Log10)

ï3
is the probability a transmission fails in a communication
between one transmitter and one receiver in the absence of ï4

interference from other stations. For a theoretical calculation of ï5

6 Mb/s
PLR as a function of SNR, we begin by using the well-known ï6 9 Mb/s
relationships between BER and SNR that have been derived 12 Mb/s
ï7 18 Mb/s
for different modulation schemes (BPSK, QPSK and QAM) 24 Mb/s
[25][26]. The 802.11a rates also employ a convolutional code ï8 36 Mb/s
48 Mb/s
to provide Forward Error Correction (FEC) so that decoding ï9
54 Mb/s
errors also need to be taken into account. As recommended in ï10
the IEEE 802.11 standard, we assume a maximum likelihood 0 5 10 15 20 25 30 35 40
SNR (dB)
hard-decision decoding scheme is used.
Our theoretical calculation of PLR, which depends on the Fig. 2. PLR vs. SNR in a Rayleigh Channel. Theoretical prediction
channel model, follows from established reasoning [26] so
we provide a guide rather than extensive details. We report
on three channel models: Rayleigh fading; Rician fading; and 2) Experimental Validation for the 802.11a rate-set: The
Additive White Gaussian Noise (AWGN). The Rayleigh fading theoretical prediction of PLR vs. SNR is based on the analysis
channel mirrors the situation where there is no significant of three diverse theoretical channel models of the environment.
propagation along a line of sight between transmitter and As these channel models are idealized, it is not clear if they can
receiver [27]. Rician fading mimics urban environments where be used with confidence to draw accurate deductions for real
there is partial cancellation of the radio signal by itself due to WLANs. It is, therefore, essential to experimentally validate
multi-path interference [28]. The AWGN model is considered the predictions of possibly redundant rates. Our experimental
 5

Rician Fading Channel, K=10 completely dominates the ccdf of the 12 Mb/s rate. Also shown
0
are the 18 and 24 Mb/s rates. In these indoor experiments one
ï1
might expect the Rayleigh fading model to be appropriate, but
ï2
they do not confirm the second non-monotonic prediction of
ï3
the Rayleigh fading channel of 18 Mb/s compared with 24
Packet Loss Ratio (Log10)

ï4 Mb/s.
ï5 A second collection of indoor experiments were performed
ï6 6 Mb/s at mid-day during a working week to investigate the impact
9 Mb/s of channel conditions driven by human motion as well as
ï7 12 Mb/s
ï8
18 Mb/s the switching on and off of computers with wireless cards.
24 Mb/s Fig. 7 is the autocovariance function for the loss sequence
ï9 36 Mb/s
48 Mb/s corresponding to an indoor daytime experiment at 12 Mb/s
ï10 54 Mb/s and, again, the vertical range is small suggesting little pairwise
ï11 dependency. Fig. 8 reports ccdf for PLR that are typical of
ï10 ï5 0 5 10 15 20 25 30
SNR (dB) multiple experiments we performed. Although the absolute
level of loss changes based on the environmental conditions,
Fig. 3. PLR vs. SNR in a Rician Channel. Theoretical prediction the redundancy of 9 Mb/s and the non-monotonicity feature of
PLR do not change. From our experimental observations, we
consistently find that the 802.11a 9 Mb/s rate is redundant.
Consequently, we choose to eliminate it from the set of
apparatus, which has been subject to substantial quantitative
possible rates for RC. A more conservative scheme would be
validation, is described in Appendix I.
to sample both the 9 Mb/s and 12 Mb/s rates from 6 Mb/s, but
We performed extensive measurements in three distinct the key point is that the monotonicity of robustness to noise
environments: outdoor experiments on an open pitch and of these rates cannot be taken for granted.
indoor experiments in an office environment both at night and The question of the redundancy of the 802.11a 18 Mb/s rate
during the day. For each rate, 20,000 packets with payload of is more subtle, as this has not been supported by any of our
1,000 B were sent. The first 80 bytes of each payload were experiments. Adopting a risk-averse approach we suggest that
used to record experiment sequence number and transmission care needs to be taken by adaptive RC algorithms when the
rate. The remaining payload bits were chosen randomly by a 18 Mb/s rate appears to function poorly. In order to ensure
Bernoulli(1/2) process. The sequence number of correctly de- that in this case H-RCA doesn’t get stuck at the 12 Mb/s rate,
coded packets at the receiver was collected. A binary sequence, on a rate increase decision from 12 Mb/s it samples the 18
which we call the loss sequence, was created with a 0 recorded Mb/s and 24 Mb/s rates in a round-robin fashion. Alternative
for each packet that experiences a transmission failure and sampling schemes to overcome these difficulties are discussed
a 1 for each that is correctly received. Measurements were in Section VI-B.
repeated with the laptops separated by increasing distances to
vary the path SNR. In all experimental environments, we first
0.1
investigated the auto-covariance of the loss sequence. Fig. 4 is
PLR=0.22
a representative plot, the auto-covariance for the loss sequence 0.08

at 12 Mb/s in the night-time indoor environment. The vertical 0.06

range is extremely small and suggests that packet losses occur 0.04

stochastically pairwise independently.

AutoïCovariance

0.02

For the 6, 9, and 12 Mb/s rates Fig. 5 shows the complemen- 0

tary cumulative distribution functions of their PLR per second ï0.02
for an outdoor experiment at a separation of 160 meters. From
ï0.04
this graph it can be clearly seen that at 9 Mb/s nearly every
ï0.06
packet is lost, while the 12 Mb/s rate experiences packet loss of
approximately 50%. Thus, while one intuitively expects lower ï0.08

rates to be more robust, this is not always the case. All higher ï0.1
0 10 20 30 40 50 60
rates experience 100% loss. Time Lag (seconds)

One set of indoor experiments was carried out at midnight

to ensure that there was no human motion, which could Fig. 4. Auto-Covariance of the loss sequence of 12 Mb/s in the night-time
indoor environment at 10m separation. Experimental data
cause variations in channel conditions. The transmitter and
receiver laptops were placed in separate offices approximately
10 meters apart, with several partition walls between them.
Fig. 6 reports complementary cumulative distribution function
(ccdf) for PLR per second for this experiment. The 6 Mb/s B. PLR Estimation
has the lowest PLR most frequently. The ccdf for the 9 Mb/s To distinguish failures due to noise from those caused
rate, however, which is located at the extreme right of the plot, by collisions, H-RCA uses a PLR estimation method based
6

1
1
0.9
0.9 6 Mbps 6 Mbps
9 Mbps 0.8 9 Mbps
0.8 12 Mbps 12 Mbps
0.7 18 Mbps
0.7 24 Mbps

Fraction of PLR > x

0.6
Fraction of PLR > x

0.6
0.5
0.5
0.4
0.4
0.3
0.3
0.2
0.2
0.1
0.1
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 PLR (x)
PLR (x)

Fig. 8. Complementary cumulative distribution functions for PLR in daytime

Fig. 5. Complementary cumulative distribution functions for PLR in the indoor environment at 10m separation. Average PLR: 6 Mb/s 0.13; 9 Mb/s
outdoor environment at 160m separation; 9 Mb/s curve barely visible in top 0.42; 12 Mb/s 0.27; 18 Mb/s 0.95; 24 Mb/s 0.99. Experimental data
right hand corner. Average PLR: 6 Mb/s 0.27; 9 Mb/s 0.99; 12 Mb/s 0.53;
18 Mb/s 1.00; 24 Mb/s 1.00. Experimental data

on the functionality of 802.11e’s TXOP [7]. As defined in

IEEE 802.11e, when a station gains access to the medium
1
and successfully transmits a packet, if the remaining TXOP
0.9
6 Mbps
time is long enough for another packet transmission, the
0.8 9 Mbps
12 Mbps
station can transmit the next packet after a short inter-frame
0.7 18 Mbps space (SIFS, see Appendix II) without an additional back-
24 Mbps
Fraction of PLR > x

0.6 off period. If any packet in the TXOP burst results in an

0.5
unacknowledged transmission, no further packets are sent. At
0.4
the time the second or later packets in the TXOP burst are
transmitted, all other stations in the network see the medium
0.3
as continuously busy so there can be no collision. In other
0.2
words, if transmission of the second or later packets in the
0.1 TXOP burst fails, it can only have been caused by noise3 .
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Transmission failure of the first packet, however, can be due
PLR (x)
to both collision and noise. Thus it is necessary to record
transmission statistics for these two classes of packets.
Fig. 6. Complementary cumulative distribution functions for PLR in the
night-time indoor environment at 10m separation. Average PLR: 6 Mb/s 0.21; TABLE III
9 Mb/s 0.28; 12 Mb/s 0.24; 18 Mb/s 0.73; 24 Mb/s 0.99. Experimental data 802.11 A TXOP PARAMETERIZATION

Rate (Mb/s) TXOP (for 1,000 B packets) STh

6 0.0030s 361
0.1
12 0.0016s 589
18 0.0011s 779
PLR=0.28
0.08 24 0.0009s 893
36 0.0007s 1140
0.06
48 0.0006s 1349
0.04 54 0.0005s N.A.
AutoïCovariance

0.02

ï0.02 In H-RCA, all packets are sent in TXOP bursts4 . The TXOP
ï0.04 value is rate and packet-size dependent. It is set to allow
ï0.06
two packets transmitted in each TXOP burst (for the 802.11a
example, see Table III). For the sequence of first packets
ï0.08
in the bursts, we define F (k) := 1 if the k th packet is
ï0.1
0 20 40 60 80 100 120 successfully received and F (k) := 0 if it is not acknowledged
Time Lag (seconds)
by its intended receiver. For the sequence of second packets
Fig. 7. Auto-Covariance of the loss sequence of 12 Mb/s in the daytime 3 Loses due to hidden nodes are not directly considered in this paper, see
indoor environment at 10m separation. Experimental data
Section VI-D.
4 The question of lightly loaded stations is addressed in Section VI-E.
 7

in the TXOP bursts, which only exist if F (k) = 1, we define most experience M −1 more collisions before being discarded.
S(k) := 1 if the k th packet is successfully received and Thus at rate r Mb/s the expected time on the medium is
S(k) := 0 otherwise. During time periods that rate change M −1
decisions are made, which will be shown to be short, we Ttx (r) − 2σ + pn
X
pil Ttx (r) (2)
assume that {S(k)} forms an i.i.d. sequence. Based on, for i=0
example, Fig. 4 and Fig. 7, this is a reasonable hypothesis.
1 − pM
l
Define = Ttx (r) − 2σ + pn Ttx (r).
1 − pl
P (S(k) = 0) := pn , These two expected waiting times have to be weighted based
where pn is the probability of failure due to noise. Again, on the likelihood that when a packet is first transmitted it is
during the short time intervals during which rate change the first or second packet in a TXOP burst. These two events
decisions are made, we assume that {F (k)} is i.i.d. and that are not equally likely as if a second packet in a TXOP burst
collisions are independent of noise so that experiences transmission failure, it becomes the first packet in
the next burst.
P (F (k) = 0) = 1 − (1 − pn )(1 − pc ) =: pl , Under the above assumptions, the stochastic process that
determines whether a packet is initially a first or second packet
where pc is the probability of failure due to collision and pl in a TXOP burst forms a Markov chain on two states. The first
is the probability of failure due to either collision or noise. state corresponds to a packet initially being a first packet and
Ideally, H-RCA would only make its rate change decisions the second corresponds to it initially being a second packet.
based on the sequence {S(k)}, but it is possible that this The Markov chain’s transmission matrix is
sequence will be completely censored by transmission failures
pM +1
1 − pM +1
 
of the first packets in each TXOP burst (when P (F (k) = 1) = Π= l l .
0). Thus a principled strategy is required to make decisions 1 − pn (1 − pMl ) pn (1 − pl )
M

based on the statistics of the first packets too. The entries of Π can be understood as follows: if a packet is
initially the first packet in a TXOP burst, the next one will also
C. Rate Reduction Decision be if it is discarded, which happens with probability pM l
+1
.
If a packet is initially a second packet in a TXOP burst and
The fundamental goal of H-RCA is to minimize the average
it experiences a failed transmission due to noise, becomes a
time that packets spend occupying the medium, a quantity
first packet and is then not discarded, which happens with
that we now determine as a function of MAC parameters,
probability pn (1 − pM l ), then the next packet will be a second
average packet size, pn and pc . Define Ttx (r) to be the time
packet too. The stationary distribution, λ where λΠ = λ, of
on the medium that a first packet in a TXOP burst during a
this Markov chain gives the likelihood that a packet is initially
transmission with a physical layer (PHY) rate r Mb/s. Then
a first packet in a TXOP burst or a second:
Ttx (r) = DIFS+Header+(Payload)/r+SIFS+Header+ACK/rack , !
1 − pn (1 − pM l ) 1 − pM l
+1
, .
where DIFS is the DCF inter-frame spacing, SIFS is the short 2 − pM +1
− pn (1 − pM M +1
− pn (1 − pM
l l ) 2 − pl l )
inter-frame spacing and rack is the rate at which the ACK is
sent. In ns-2 rack is set to 6 Mb/s. In our 802.11a experimental Thus, with PHY rate r Mb/s, the average time that a packet
apparatus, rack is 6 Mb/s for the 6 and 9 Mb/s rates, 12 Mb/s spends being transmitted is
for the 12 and 18 Mb/s rates, and 18 Mb/s for all higher M M +1
!
rates. In H-RCA, all the re-transmissions are proceeded with Ts (r) = 1 − p n (1 − p l ) 1 − p l
Ttx (r) +
the current rate r with Multi-Rate Retry mechanism disabled. 2 − pM l
+1
− pn (1 − pM l )
1 − pl
From the above assumptions, using analysis along the lines (3)
found in [29][30], if a packet is the first packet in a TXOP 1 − pl M +1 
1 − plM

burst and the PHY rate is r Mb/s, its expected time on the Ttx (r) − 2σ + pn Ttx (r) .
2 − pM +1
− pn (1 − pM l )
1 − pl
medium is5 l

M For a given rate and channel model, the probability of loss

X 1 − pM +1
i
pl Ttx (r) = l
Ttx (r), (1) due to noise pn can be determined as a function of SNR.
i=0
1 − p l 1) Rate-reduction (802.11a): In Fig. 9 the channel is
AWGN and the probability of transmission failure due to
where M is the 802.11 retry limit (see Appendix II). If a
collision is pc = 0.3, corresponding to a station competing
packet is the second in a TXOP burst, its first transmission
with 6 stations that always have packets to send [31]. In Fig. 10
is delayed by a SIFS rather than a DIFS, where SIFS is two
the channel is Rayleigh Fading and pc = 0.01, corresponding
idle slots (σ) shorter than DIFS, SIFS = DIFS-2σµs. Should
to a station competing for access in a lightly loaded network
it experience a collision, which can only be due to noise, it
[29]. These figures are representative of graphs for AWGN
becomes the first packet in the next TXOP burst, but can at
and Rayleigh fading channels and a wide range of conditional
5 If successful and failed transmissions take distinct times, this can readily collision probabilities. In both figures, the rate with the lowest
be taken into account. average transmission time is the optimal rate for H-RCA at
8

that SNR value. The cross-points between these lines are the packet transmissions or 9 failures out of 50 second packet
critical points where H-RCA should decrease its rate. transmissions to be over 95% confident that the pn > 0.1 for
Corresponding to Figs 9 and 10, in terms of pn (log10 scale) the current rate and to decide to choose a lower rate. Note that
vs. SNR, Figs 11 and 12 plot these crossing-points. In both these numbers, based on a principled design, are efficient. If
figures it is clear that those cross-points are distributed around the noise probability pn is small enough that a rate reduction
the value pn = 0.1. This pattern is the same for a wide range of decision is not taken based on F (1), . . . , F (N ), then we will
conditional collision probabilities irrespective of the channel quickly get a sufficient sample of second packets in order to
model and, therefore, for convenience in our simulations and make an accurate decision based on noise-only failures. On
experiments with the 802.11a rate-set H-RCA uses pn > 0.1 = the other hand, if the WLAN has less than 40 stations that
pthresh as the threshold to trigger rate reduction at all rates. H- always have packets to send and H-RCA sees more than 39
RCA could, of course, be set up with a distinct pn threshold transmission failures for 50 first packets, it can confidently
value for each rate. In selecting 0.1 we are typically erring on decide that pn > 0.1 and lower the transmission rate.
the conservative side and demonstrate that this does not come
AWGN Channel, pc=0.3
at a significant performance cost. For each rate, the average
3000
transmission time at the SNR corresponding to the threshold
value pthresh is indicated in Figs 9 and 10.
2500

Average Transmission Time (µs)

D. Rate-reduction: Bayesian inference
2000
Based on observations of {F (k)} and {S(k)}, we adopt
a Bayesian paradigm to the rate lowering decision. First note
1500 6 Mb/s
that the statistics of {F (k)} depend on pc as well as pn , while 9 Mb/s
{S(k)} only depends on pn . Given a sufficient number of 12 Mb/s
1000 18 Mb/s
observations of {S(k)} to enable a good estimate of pn , it is 24 Mb/s
possible to estimate pc from {F (k)}. However, this is not an 36 Mb/s
500 48 Mb/s
approach we use as if pn is large, it is possible that we get 54 Mb/s
no {S(k)} observations. Threshold
0
Instead we will take a rate lowering decision based on the ï10 ï5 0 5 10 15 20 25 30
SNR (dB)
experience of either {F (k)} or {S(k)}, but use a worst-case
a priori upper bound on pc for {F (k)} based on Bianchi’s
well-known model [31]. Assuming that stations always have Fig. 9. Average Transmission Time Ts in AWGN channel with pc = 0.3.
Threshold points correspond to pn = 0.1. Theoretical prediction
packets to send, we use Bianchi’s relationship between the
conditional collision probability, pc , and the number of stations
in the WLAN. In practice, a WLAN is not likely to have a
Rayleigh Fading Channel pc=0.01
network with over 40 stations that always have packets to
3000
send. For such a situation pc ≈ 0.6 and so H-RCA finds the
transmission failure probability, pl , of the first packet in the
2500
TXOP burst over 1−(1−pc )(1−pthresh ) = 0.6+0.4 pthresh then
Average Transmission Time (µs)

pn > pthresh and it should choose a lower rate. For example, for
2000
the 802.11a rate-set with pthresh = 0.1, this value is pl = 0.64.
The Bayesian decision to change rate is based on the
1500 6 Mb/s
following question: using a uniform prior for pn on [0, 1], 9 Mb/s
conditional on the fact that the noise packet loss probability, 12 Mb/s
1000 18 Mb/s
pn , is over pthresh , in N packet transmissions, the Bayesian 24 Mb/s
sampling window, how many failures should be observed 36 Mb/s
48 Mb/s
before H-RCA has over 95% confidence that pn > pthresh ? 500
54 Mb/s
With pl (pc , pn ) := 1 − (1 − pc )(1 − pn ) and pc known, this Threshold
corresponds to finding the minimal value of K that satisfies 0
ï5 0 5 10 15 20 25 30 35 40
the following inequality: SNR (dB)
Z 1  
N
(1 − pl (pc , pn ))N −K pl (pc , pn )K dpn Fig. 10. Average Transmission Time Ts in Rayleigh Fading channel with
pthresh K pc = 0.01. Threshold points correspond to pn = 0.1. Theoretical prediction
Z 1  ≥ 0.95.
N
(1 − pl (pc , pn ))N −K pl (pc , pn )K dpn
0 K
(4)
1) Bayesian inference (802.11a): Using (4), out of N = 50 E. Rate Increase Frequency
transmission samples for each sequence, {F (k)} and {S(k)}, A commonly adopted process [15][4][16] for an adaptive
and assuming pc = 0.6 for {F (k)} and pc = 0 for {S(k)}, algorithm to decide if it should try a higher rate is when
H-RCA should observe at least 39 failures out of 50 first it experiences a fixed number of successful transmissions.
 9

AWGN Channel, pc=0.3

0
transmissions plus the back-off times between them,
PN −1 !
0 0 W i=0 2min(i mod M,m) − N
ï1 H(r ) := N Ttx (r ) + σ .
2

ï2 where W is the minimum contention window, 2m W is the

maximum contention window and M is the discard limit (see
pn (Log10)

ï3 6 Mb/s
Appendix II). Note that if a rate change decision can only
9 Mb/s be made after a packet’s success or discard, as happens in
12 Mb/s
ï4 18 Mb/s
Atheros hardware, then the upper limit in the sum should be
24 Mb/s set to dN/M eM − 1. Assuming no collisions, i.e. pc = 0,
36 Mb/s
48 Mb/s
instead of trying the high rate r0 , during this time H(r0 ), we
ï5
54 Mb/s could successfully transmit
crossïpoints   
ï6 1 (W − 1)
ï10 ï5 0 5 10 15 20 25 X := H(r0 )/ Ttx (r) + Ttx (r) − 2σ + σ
SNR (dB) 2 2
  
(W − 1)
Fig. 11. Slow Down Points in AWGN Channel with pc = 0.3. Theoretical
= H(r0 )/ Ttx (r) − σ + σ
4
prediction
packets at rate r Mb/s, half as first packets and half as second
packets in TXOP bursts. Therefore, if the station can transmit
DX packets at rate r Mb/s with trying rate r0 Mb/s, this station
Rayleigh Fading Channel, pc=0.01 could transmit (D + 1)X packets without trying rate r0 Mb/s.
0
To ensure that the penalty in lost transmission opportunities
ï1 at the higher rate would result in achieving, at worst, we
ï2 pick a target of 95% of the throughput of the current rate
ï3 r Mb/s setting DX/((D + 1)X) = 95% where D = 19.
ï4
Thus, when currently at rate r Mb/s, the station changes to a
pn (Log10)

higher rate r0 Mb/s every time the station observes STh= 19X
ï5 6 Mb/s
9 Mb/s not necessarily consecutive successful transmissions (c.f. Table
ï6 12 Mb/s III).
18 Mb/s
ï7
24 Mb/s 1) Rate-increase frequency (802.11a): For packets of size
ï8 36 Mb/s 1,000 B, these values are given in Table III. Successful
48 Mb/s
ï9 54 Mb/s transmissions are counted over both first and second packets
crossïpoints in each TXOP burst. To enable H-RCA to drop back quickly
ï10
0 5 10 15 20 25 30 35 40 to its current rate if the higher rate proves to have pn > 0.1,
SNR (dB)
during the first instance of observation of a higher rate the
algorithm uses Bayesian sampling window N = 10. Based
Fig. 12. Slow Down Points in Rayleigh Fading Channel with pc = 0.01.
Theoretical prediction on 95% confidence and the Bayesian analysis in equation (4),
this means that the algorithm will drop back to its original rate
if it observes 9 first packet transmission failures or 1 failed
transmission for second packets. Should neither of these events
occur, H-RCA stays at its current rate and resets N to be 50.
However, if the algorithm samples a higher rate that is not
suitable for the current SNR too frequently, it will significantly IV. 802.11 A H-RCA P ERFORMANCE E VALUATION
decrease the station’s throughput. On the other hand, if the The following are three natural characteristics that can be
algorithm samples higher rates rarely, it will be insensitive to used to evaluate the performance of a RC algorithm.
changes in channel quality.
1) Accuracy: can it find the right rate for a given SNR?
The solution that H-RCA employs to overcome this conun- 2) Speed: how quickly does it converges to the right rate?
drum is to employ an opportunity-cost approach and have rate 3) Noise vs. Collisions: is it robust to collision induced
dependent successful transmission thresholds (STh). These transmission failures?
thresholds are decided based on the following logic. The worst As it is challenging to build an experimental wireless
case scenario is if H-RCA is operating at a given rate, r Mb/s, channel with controllable noise characteristics, here we present
with pn =0 and attempts to transmit at a higher rate r0 Mb/s results from ns-2 simulations. Data from an experimental
whose pn =1. Due to our Bayesian inference mechanism, H- implementation is reported in Section V. In simulation we
RCA will not drop back to rate r Mb/s until it observes N used both the AWGN and Rayleigh Fading channel models to
transmission samples, which are all first packet transmissions determine pn , the probability of failure due to noise, at each
due to P (F (k) = 1) = 0. Consequently, the time wasted rate at a given SNR. As results for both channel models are
on trying the high rate r0 Mb/s will be N consecutive similar and our experimental results suggest that the AWGN
10

is the more appropriate of the two, we provide graphs only finding the correct rate and sampling the one above it. The
for the AWGN channel. 30 minute average throughput of the omniscient algorithm is
In existing commodity hardware, the physical layer per- 15.96 Mb/s. H-RCA gets 95% of this figure, as one would
forms automatic re-sends on transmission failure and the expect based on its rate-increase opportunity cost approach.
network card driver is only made aware of the transmission The figure shows that H-RCA is responsive to a sudden change
result at the MAC layer. To mirror this constraint, in ns-2 H- in SNR where it only takes seconds to adapt and stabilize
RCA works on information at the MAC-level, so H-RCA is rate in response to the dramatically different environmental
only informed of the totality of a packet’s transmission results conditions.
after it has been successfully sent or discarded. That is, H- Fig. 14 shows simulation results in the case of SNR gradient
RCA receives new data only when the MAC layer finishes demonstrating that H-RCA still delivers greater and less vari-
servicing each packet. able throughput than SampleRate. H-RCA sustains network
All stations transmit fixed 1,000 B UDP packets to an throughput when SNR decreases slowly (from 200s to 600s),
Access Point (AP) and always have packets to send. H-RCA’s while the throughput of SampleRate drops continuously and
TXOP and STh values are set as in Table III. We have also is highly variable. Sizeable drops in SampleRate’s throughput
implemented SampleRate [3] in ns-2. In order to provide a fair flag instances when SampleRate adapts its rate. H-RCA, how-
comparison we use the same simulation settings, including the ever, makes better decisions more quickly and more accurately.
same rate-set, TXOP values and the redundant 9 Mb/s rate is In comparison to the omniscient algorithm, again H-RCA gets
excluded from SampleRate’s rate list. 95% of this maximum throughput.
We perform two sets of simulations to determine accuracy H-RCA’s decision making process is shown in Fig. 15.
and speed. One set with a single station, so there are no For the second half of the simulation, it plots indicates
collisions. The second set has five stations so that transmission the instances at which rate change decisions were made in
failure can be caused by collisions. the example shown in Fig. 14. The rate at which decisions
We report on H-RCA’s performance under two distinct, to increase rate are made reflect opportunity cost scheme
evolving SNR conditions: 1. step changes in channel quality; where with one station sampling of higher rates can occur
2. gradual changes in channel quality. In the step-change case, frequently without a performance detriment. These simulations
SNR changes with the following discontinuous function: demonstrate that even in the absence of collisions, H-RCA
 exhibits gains over SampleRate.

 (15 + G(t)) dB if 0s ≤ t ≤ 300s
 (10 + G(t)) dB if 300s < t ≤ 600s


25
SNR(t) = (5 + G(t)) dB if 600s < t ≤ 1200s
(10 + G(t)) dB if 1200s < t ≤ 1500s



 20
(15 + G(t)) dB if 1500s < t ≤ 1800s

Network Throughput (Mb/s)

While in the gradient-change case, SNR varies as the following 15

continuous V-shaped function:

   10
t
 15 − + G(t) dB if 0 ≤ t ≤ 900s


90
SNR(t) =  
t 5
 −5 + + G(t) dB if 900s < t ≤ 1800s


90 H-RCA (mean 15.1Mb/s)
Sample (mean 13.3Mb/s)
0
In both cases, {G(t)} is Gaussian Process with mean 0 and 0 200 400 600 800 1000 1200 1400 1600 1800
Time (sec)
variance 1 and the resulting pn is determined from the AWGN
channel model. Fig. 13. Throughput in AWGN channel, SNR Step and 1 station. Simulation
data

A. Single Station, No Collisions

Our first simulation takes place in a WLAN with a single
active client so that it experiences no collisions. In the discon- B. Five Stations With Collision
tinuous SNR scenario, Fig. 13 shows the WLAN’s second-by- As a test of robustness to failures caused by collisions, the
second throughput when using either H-RCA or SampleRate. next simulation models a WLAN with five active stations,
The 30 minute average throughput for each RC algorithm and which is not an unrealistic practical scenario. Fig. 16 reports
shows that H-RCA gets higher throughput than SampleRate. throughput in the SNR step case, while Fig. 17 is for the SNR
SampleRate looses throughput as it frequently samples the gradient case. In comparison to the omniscient algorithm, for
whole rate space. H-RCA’s sampling frequency is restricted Fig. 11 H-RCA gets 98% of its throughput and for Fig. 17 it
by design, so it achieves a consistently higher throughput gets 97%. This demonstrates that H-RCA is accurate, always
than SampleRate. For this simulation we implemented an finding the best rate and sampling the one above it.
omniscient optimal algorithm that knows channel conditions in With the increased packet losses due to collisions in this
advance and can select the best rate at all times. Comparisons network, SampleRate’s decision making has been significantly
with this all-knowing algorithm shows that H-RCA is accurate, affected. The influence of collision packet losses on H-RCA’s
 11

25

25
20
Network Throughput (Mb/s)

20

Network Throughput (Mb/s)

15

15
10

10
5

H-RCA (mean 15.2Mb/s) 5

Sample (mean 14.8Mb/s)
0
0 200 400 600 800 1000 1200 1400 1600 1800 H-RCA (mean 15.3Mb/s)
Time (sec) Sample (mean 10.8Mb/s)
0
0 200 400 600 800 1000 1200 1400 1600 1800
Fig. 14. Throughput in AWGN channel, SNR Gradient and 1 station. Time (sec)

Simulation data
Fig. 16. Total Throughput in AWGN channel, SNR Step and 5 station.
Simulation data

50

40

25
Rate (Mb/s)

30

20
20 Network Throughput (Mb/s)

15
10 Rate
Reason: STh
Reason: FFTh
Reason: SFTh
0 10
900 1000 1100 1200 1300 1400 1500 1600 1700 1800
Time (sec)
5
Fig. 15. Rate change decisions, AWGN channel, SNR Gradient and 1 station.
H-RCA (mean 15.4Mb/s)
UP indicates a rate increase decision, FFTh indicates a rate decrease decision Sample (mean 10.4Mb/s)
based on first packets in a TXOP burst and SFTh indicates a rate decrease 0
0 200 400 600 800 1000 1200 1400 1600 1800
decision based on second packets in a TXOP burst. Simulation data Time (sec)

Fig. 17. Total Throughput in AWGN channel, SNR Gradient and 5 station.
Simulation data
decision making is small. As H-RCA only makes rate change
decisions after it has observed a certain number of packet
transmissions, when the number of active clients in the net-
work increases, this estimation time increases. Therefore, in
this scenario H-RCA’s reaction time is longer in comparison
to the single-station network, but not unacceptably so. 50
The rate change decisions for a single station in the network
are plotted in Fig. 18 in which the round-robin approach to 40
sampling 24 and 36 Mb/s from 18 Mb/s between 900s and
Rate (Mb/s)

1000s is clear. In contrast to Fig. 15 it can be seen that the 30

presence of other active stations necessarily slows down the
real-time adaptivity of the algorithm. This occurs as the rate at 20
which RC algorithms gain channel information is a function
of the rate at which they get to transmit packets. 10 Rate
Reason: STh
Again these simulations demonstrate that H-RCA’s reaction Reason: FFTh
Reason: SFTh
time is short. Most importantly, H-RCA is robust to trans- 0
900 1000 1100 1200 1300 1400 1500 1600 1700 1800
mission failures caused by collisions. Network performance, Time (sec)
therefore, does not degrade in the presence of several active
stations as is common in practice. Fig. 18. Rate change decisions, AWGN channel, SNR Gradient and 5
stations. UP indicates a rate increase decision, FFTh indicates a rate decrease
decision based on first packets in a TXOP burst and SFTh indicates a rate
V. 802.11 A E XPERIMENTS decrease decision based on second packets in a TXOP burst. Simulation data
It is not feasible to construct an experimental scenario with
controllable noise characteristics, so in Section IV we inves-
12

tigated H-RCA’s performance in the controlled environment Saturated, 2STAs

35
of ns-2 simulations. As experiments can reveal difficulties not
predicted by theory or simulation, in this section we report 30

on experiments using the apparatus described in Appendix I.

Network Throughput (Mb/s)

25
We compare H-RCA’s throughput with that of Minstrel [2],
20
SampleRate, [3], AMRR [4] and Onoe [5] as implemented
in the MadWiFi driver for the Atheros chipset, and RRAA 15
[6] as implemented by ourselves in the absence of a publicly
10 H-RCA (mean 26.7Mb/s)
available implementation. In all experiments, stations always Minstrel (mean 23.0Mb/s)
Sample (mean 22.6Mb/s)
have 1,000 B UDP packets to send using the 802.11a rate-set. 5 RRAA (mean 20.7Mb/s)
AMRR (mean 20.9Mb/s)
Onoe (mean 21.3Mb/s)
0
0 50 100 150 200 250 300
Time (sec)
30

Fig. 20. Dynamic throughputs for H-RCA, Minstrel, SampleRate, RRAA,

25
Average Network Throughput (Mb/s)

AMRR and Onoe in a 2-station WLAN. Experimental data

20

15 trip time statistics.

These experiments demonstrate the H-RCA methodology
10

H-RCA
can deliver higher throughput with decreased variability.
Minstrel
5 Sample
RRAA
AMRR Saturated, 2STAs
Onoe 90
0 H-RCA (mean 26.6Mb/s, stddev 0.16Mb/s)
1 2 3 4 5 Minstrel (mean 23.0Mb/s, stddev 0.26Mb/s)
80 Sample (mean 22.6Mb/s, stddev 0.63Mb/s)
Number of Stations
RRAA (mean 20.7Mb/s, stddev 0.34Mb/s)
70 AMRR (mean 20.9Mb/s, stddev 0.69Mb/s)
Onoe (mean 21.3Mb/s, stddev 1.07Mb/s)
Fig. 19. Long run throughput for H-RCA, Minstrel, SampleRate, RRAA, 60
AMRR and Onoe. Experimental data
Frequency

50

40

For a WLAN consisting of between 1 and 5 stations, all of 30

which are running the same RC-algorithm (H-RCA, Minstrel, 20

SampleRate, RRAA, AMRR or Onoe), Fig. 19 reports the 5 10

minute average throughput in each WLAN. As the number of 0
18 19 20 21 22 23 24 25 26 27 28
stations increases, the likelihood of failed transmission due Network Throughput per second (Mb/s)
to collisions, pc , increases. SampleRate, AMRR and Onoe
misinterpret collisions as being a consequence of bad channel Fig. 21. Histogram of dynamic throughputs for H-RCA, Minstrel, SampleR-
conditions resulting in unnecessary increased rate sampling ate, RRAA, AMRR and Onoe in a 2-station WLAN. Experimental data
and, consequently, network resources are underutilized. RRAA
distinguishes noise from collisions, but the overhead in using
RTS/CTS costs throughput. Minstrel has an improved sam-
pling technique over SampleRate and so does not over-react VI. D ISCUSSION AND C ONCLUSION
to increased collisions. The gain in throughput that is available
in H-RCA by distinguishing collisions from noise by using the A. H-RCA’s objective, possible alternatives
TXOP-based methodology is apparent. While stations are not H-RCA is designed to maximize overall network through-
likely to be constantly back-logged for long periods in practice, put, but other objectives are possible. For example, if the
5 back-logged stations would not be an uncommon scenario; station wished to selfishly optimize its own throughput, it
indeed poor rate selection decisions make these periods more could minimize the average service time of its packets. This
likely as they lead to increased congestion. would be achieved by changing (3) through appending to
Fig. 20 and Fig. 1 (in Section I) report the dynamic equations (1) and (2) a term corresponding to the mean
throughput in the 2 and 5 station WLANs, respectively, on MAC back-off time while the packet is at the head of the
a second-by-second basis. These graphs demonstrate that H- line awaiting transmission. This quantity can be calculated
RCA is consistent in its rate selection and its higher throughput based on the model introduced in [31]. In order to implement
does not come with any increased variability. The latter point is this change, the station would need an estimate of the mean
substantiated in Fig. 21 and Fig. 22 which provide histograms busy slot time on the medium, which would be practically
of these dynamic throughputs. As well as offering increased challenging with existing hardware. Assuming this information
mean throughput, it is clear that H-RCA also offers decreased is available, we have implemented this approach in ns-2 and
variance. This consistency is desirable for both real-time the results (data not shown) display little difference from those
applications and TCP as its performance depends upon round- based on equation (3).
 13

Saturated, 5STAs E. Non-saturated stations

90
H-RCA (mean 24.5Mb/s, stddev 0.21Mb/s)
80
Minstrel (mean 20.4Mb/s, stddev 0.27Mb/s) We have focused on stations that have back-to-back packets
Sample (mean 14.6Mb/s, stddev 1.1Mb/s)
RRAA (mean 15.8Mb/s, stddev 0.43Mb/s) to send so that they can be packaged in pairs in TXOP bursts.
70 AMRR (mean 5.3Mb/s, stddev 0.28Mb/s)
Onoe (mean 3.0Mb/s, stddev 0.39Mb/s) This is reasonable as it is when stations have a lot of traffic
60
to send that efficient usage is of particular importance. If
Frequency

50
stations are extremely lightly loaded there are two alternative
40
stratagems. If stations have large packets, the MAC can split
30 them into two fragments the second of which is not subject to
20 collisions. If stations have small packets, this is unnecessary
10 and they can be sent individually as the dominant component
0 of the transmission delay comes from fixed overheads in that
0 5 10 15 20 25 30
Network Throughput per second (Mb/s) case.

Fig. 22. Histogram of dynamic throughputs for H-RCA, Minstrel, SampleR- F. Summary
ate, RRAA, AMRR and Onoe in a 5-station WLAN. Experimental data
We have presented H-RCA, an adaptive collision-aware
wireless rate control methodology. As H-RCA does not require
specific hardware support nor any change in IEEE 802.11
B. The 18 Mb/s 802.11a Rayleigh Fading Issue, other standard, we have implemented it on commodity hardware.
stratagems Due to its TXOP technique used to distinguish the collision
To overcome the possible redundancy of the 802.11a 18 loss, H-RCA adapts appropriately to collision induced losses.
Mb/s rate, which is predicted by theory but not substantiated Its rate decrease decision making process employs Bayesian
by experiments, we employ a round-robin strategy when a analysis to ensure reasonable outcomes. Its increase-rate deci-
rate increase decision occurs from 12 Mb/s. Many other sion frequency is chosen in a way that guarantees near optimal
schemes could be proposed, including adaptive schemes, but performance in an unchanging environment.
the simplest one appears to function adequately in our tests. As well as offering increased mean throughput over existing
For example, we implemented a weighted scheme in which, algorithms, experiments demonstrate that H-RCA also offers
on a rate increase decision the 18 Mb/s and 24 Mb/s rates decreased variance in throughputs. This consistency is desir-
were selected with frequencies related to the potential lost able for real-time applications that rely on high throughput
bandwidth if pn = 1. In all tests, the results from this scheme and low jitter. It is also desirable for non-real-time traffic as
were directly comparable to the round-robin methodology. the performance of TCP is dependent upon stable round-trip
time statistics.

C. Redundancy of 9 Mb/s, other stratagems A PPENDIX I

All theoretical models predict that the 12 Mb/s rate is more E XPERIMENTAL A PPARATUS
robust to noise than the 9 Mb/s rate. Every experiment we For the experiments described in Section III-A, two laptops,
performed was consistent with this prediction, so we elected one used as a transmitter and one as a receiver, were equipped
to remove 9 Mb/s from the set of rates that H-RCA considered. with version 0.9.4 of the MadWifi driver that was modified to
Alternatively, one could employ a dual sampling strategy of enable the selection of a fixed transmission rate for multicast
investigating both 9 Mb/s and 12 Mb/s from 6 Mb/s, as we packets as well as disabling power control. Multicast packets
have advocated for the 18 Mb/s issue in Section VI-B above. were used to circumvent potential additional complexities
caused by MAC level retries. Care was taken to avoid prob-
lems of station disassociation, lease expiry and so forth. In
D. Hidden nodes
addition, it is known that human motion heavily influences
Rate-control in itself isn’t a solution to the problem of measurement outcomes [32], so this was excluded from the
hidden nodes, but can be used to mitigate their impact. clean-environment experiments. A spectrum analyzer was used
The scheme we employ to separate collision and noise-based to check that the channel chosen for the experiments was clear
losses can be extended using standard 802.11e functionality of interference from other signals.
to distinguish between hidden nodes based losses too [7]. By The experimental apparatus used for the results presented
using the echoed NAV values in MAC ACKs, one can test if in Sections I and V employs a PC acting as an Access Point
noise-based losses change in response to virtual carrier sense. (AP) and another 5 PCs acting as client stations. The WLAN
If they do, these noise losses can be classified as losses as is set up in infrastructure mode. All systems are equipped
due to hidden nodes at the receiver. H-RCA can be readily with an Atheros AR5215 802.11 PCI card with an external
modified to make use of this information in order to keep antenna. These cards do not suffer the serious difficulties
transmission rates high when noise is low, but hidden nodes are reported in [33] and [34]. All stations, including the AP, use
present. This is a only partial solution as completely mitigating a version of the MadWiFi wireless driver that supported H-
for hidden nodes is within the remit of power and channel RCA, SampleRate, AMRR, Onoe and Minstral with RTS/CTS
selection. disabled as well as RRAA with RTS/CTS enabled. All stations
14

are equipped with a 100 Mbps wired Ethernet port that is [9] S. Choudhury and J. D. Gibson. Payload Length and Rate Adaptation for
solely used for control of the test bed from a distinct PC. Throughput Optimization in Wireless LANs. In Vehicular Technology
Conference, 2006.
In the experiments, UDP traffic is generated by the Naval [10] G. Holland, N. Vaidya, and P. Bahl. A Rate-Adaptive MAC Protocol for
Research Laboratory’s MGEN in periodic mode. All packets Multi-Hop Wireless Networks. In ACM MobiCom Conference, 2001.
are generated in client stations before being transmitted to the [11] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly. Opportunistic
Media Access for Multirate Ad Hoc Networks. In ACM MobiCom
AP. Conference, 2002.
[12] P. A. K. Acharya, A. Sharma, E. M. Belding, K. C. Almeroth, and D. Pa-
pagiannaki. Congestion-Aware Rate Adaptation in Wireless Networks:
A PPENDIX II A Measurement-Driven Approach. In IEEE SECON Conference, 2008.
A BRIEF OVERVIEW OF 802.11’ S BEB ALGORITHM [13] G. Judd, X. Wang, and P. Steenkiste. Efficient Channel-aware Rate
Adaptation in Dynamic Environments. In ACM MobiSys Conference,
On detecting the wireless medium being idle for a period 2008.
DIFS, each station initializes a counter to a random number [14] M. A. Y. Khan and D. Veitch. Isolating physical PER for smart rate
selection in 802.11. In IEEE INFOCOM, 2009.
selected uniformly in the range {0, 1, . . . , W − 1}. Time is [15] A. Kamerman and L. Monteban. Wavelan II: A High-Performance
slotted and this counter is decremented once during each slot Wireless LAN for the Unlicensed Band. Bell Labs Technical Journal,
that the medium is observed idle. The count-down halts when 2(3):118–133, 1997.
[16] J. Kim, S. Kim, S. Choi, and D. Qiao. CARA: Collision-aware Rate
the medium becomes busy and resumes after the medium is Adapataion for 802.11 Wireless Networks. In IEEE INFOCOM, 2006.
idle again for a period DIFS. Once the counter reaches zero the [17] J. Zhang, K. Tan, J. Zhao, H. Wu, and Y. Zhang. A Practical SNR-
station attempts transmission and if a collision does not occur Guided Rate Adaptation. In IEEE INFOCOM Conference, 2008.
[18] S. Rayanchu, A. Mishra, D. Agrawal, S. Saha, and S. Banerjee.
it can transmit for a duration up to a maximum period TXOP Diagnosing Wireless Packet Losses in 802.11: Separating Collision from
(defined to be one packet except in the Quality of Service Weak Signal. In IEEE INFOCOM Conference, 2008.
MAC extension 802.11e). If two or more stations attempt to [19] M. Vutukuru, H. Balakrishnan, and K. Jamieson. Cross-Layer Wireless
Bit Rate Adaptation. In ACM SIGCOMM, 2009.
transmit simultaneously, a collision occurs. Colliding stations [20] S. Sen, N. Santhapuri, R. R. Choudhury, and S. Nelakuditi. AccuRate:
double their Contention Window (CW), up to a maximum Constellation based rate estimation in wireless networks. In In USENIX
value 2m W , selects a new back-off counter uniformly and the NSDI, 2010.
[21] J. Choi, J. Na, K. Park, and C. Kim. Adaptive optimization of rate
process repeats. If a packet experiences more collisions than adaptation algorithms in multi-rate WLANs. In ICNP, 2007.
the retry limit, M , where M = 7 in 802.11a, the packet is [22] J. Choi, K. Park, and C. Kim. Cross-layer analysis of rate adaptation,
discarded. After the successful transmission of a packet or after DCF and TCP in multi-rate WLANs. In IEEE INFOCOM, 2007.
[23] J. Choi, J. Na, Y. s. Lim, K. Park, and C. k. Kim. Collision-aware
a packet discard, CW is reset to its minimal value W and a design of rate adaptation for multi-rate 802.11 WLANs. Selected Areas
new count-down starts regardless of the presence of a packet at in Communications, IEEE Journal on, 26(8):1366 – 1375, 2008.
the MAC. If a packet arrives at the MAC after the count-down [24] K. D. Huang, D. Malone, and K. R. Duffy. The 802.11g 11 Mb/s
rate is more robust than 6 Mb/s. IEEE Transactions on Wireless
is completed, the station senses the medium. If the medium Communications, 10(4):1015–1020, 2011.
is idle, the station attempts transmission immediately; if it is [25] A. Goldsmith. Wireless Communications. CUP, 2005.
busy, another back-off counter is chosen from the minimum [26] M. K. Simon and M. S. Alouini. Digital Communication over Fading
Channels. Wiley-IEEE Press, 2005.
interval. This bandwidth saving feature is called post-back-off. [27] M. B. Pursley and D. J. Taipale. Error Probabilities for spreadspectrum
The revised 802.11e MAC enables the values of DIFS (called packet radio with convolutional codes and viterbi decoding. IEEE Trans.
the Arbitration Inter-Frame Spacing, AIFS, in 802.11e), CW Commun., 35(1):1–12, 1987.
[28] W C Lindsey. Error probabilities for rician fading multichannel reception
and TXOP to be set on a per-class basis for each station. That of binary and n-ary signals. IEEE Transactions on Information Theory,
is, traffic is directed to up to four different queues at each 10(4):339–350, 1964.
station, with each queue assigned different MAC parameter [29] D. Malone, K. Duffy, and D. J. Leith. Modeling the 802.11 Dis-
tributed Coordination Function in non-saturated heterogeneous condi-
values. tions. IEEE/ACM Transactions on Networking, 15(1):159–172, 2007.
[30] K. Duffy and A. J. Ganesh. Modeling the impact of buffering on 802.11.
IEEE Comm. Lett., 11(2):219–221, 2007.
R EFERENCES [31] G. Bianchi. Performance Analysis of IEEE 802.11 Distributed Coordi-
nation Function. IEEE JSAC, 18(3):535–547, March 2000.
[1] K. Ramach, H. Kremo, M. Gruteser, and P. Spasojevi. Scalability [32] P. Barsocchi, G. Oligeri, and F. Potortia. Validation for 802.11b
analysis of rate adaptation techniques in congested ieee 802.11 networks: Wireless Channel Measurements. Technical report, Istituto di Scienza e
An orbit testbed comparative study. In in Proc. of IEEE WoWMoM, Tecnologie dell’Informazione ‘Ales sandro Faedo’, 2006.
2007. [33] G. Bianchi, A. Di Stefano, C. Gianconia, and L. Scalia. Experimen-
[2] Minstrel rate adaptation algorithm. http://madwifi- tal assessment of the backoff behavior of commercial IEEE 802.11b
project.org/browser/madwifi/trunk/ath rate/minstrel, Jan 2010. network. In IEEE INFOCOM, 2007.
[3] J. Bicket. Bit-Rate Selection in Wireless Networks. Master’s thesis, [34] D. Giustiniano, G. Bianchi, L. Scalia, and I. Tinnirello. An explanation
Massachusetts Institute of Technology, 2005. for unexpected 802.11 outdoor link-level measurement results. In IEEE
[4] M. Lacage, M. Manshaei, and T. Turletti. IEEE 802.11 Rate Adaptation: INFOCOM, 2008.
A Practical Approach. In ACM MSWiM, 2004.
[5] Onoe rate adaptation algorithm. http://madwifi-
project.org/browser/madwifi/trunk/ath rate/onoe, Jan 2010.
[6] S. Wong, H. Yang, S. Lu, and V. Bharghavan. Robust Rate Adaptation
for 802.11 Wireless Networks. In ACM MobiCom Conference, 2008.
[7] D. Giustiniano, D. Malone, D. J. Leith, and K. Papagiannaki. Measuring
transmission opportunities in 802.11 links. IEEE/ACM Transactions on
Networking, 18(5):1516–1583, 2010.
[8] D. Qiao, S. Choi, and K. G. Shin. Goodput Analysis and Link
Adaptation for IEEE 802.11a Wireless LANs. Mobile Computing, IEEE
Transactions, 1(4):278–292, 2002.