Performance Analysis of the IEEE802.11Distributed
Coordination Function
Giuppe Bianchi
Abstract—Recently,the IEEE has standardized the802.11pro-tocol for Wireless Local Area Networks.The primary medium ac-cess control(MAC)technique of802.11is called distributed coor-dination function(DCF).DCF is a carrier n multiple access with collision avoidance(CSMA/CA)scheme with binary slotted exponential backoff.This paper provides a simple,but nevertheless extremely accurate,analytical model to compute the802.11DCF throughput,in the assumption of finite number of terminals and ideal channel conditions.The propod analysis applies to both the packet transmission schemes employed by DCF,namely,the basic access and the RTS/CTS access mechanisms.In addition,it also ap-plies to a combination of the two schemes,in which packets longer than a given threshold are transmitted according to the RTS/CTS mechanism.By means of the propod model,in this paper we pro-vide an extensive throughput performance evaluation of both ac-cess mechanisms of the802.11protocol.
Index Terms—802.11,collision avoidance,CSMA,performance evaluation.
I.I NTRODUCTION
I N recent years,much interest has been involved in the
design of wireless networks for local area communication [1],[2].Study group802.11was formed under IEEE Project 802to recommend an international standard for Wireless Local Area Networks(WLAN’s).The final version of the standard has recently appeared[3],and provides detailed medium access control(MAC)and physical layer(PHY)specification for WLAN’s.
In the802.11protocol,the fundamental mechanism to access the medium is called distributed coordination function(DCF). This is a random access scheme,bad on the carrier n mul-tiple access with collision avoidance(CSMA/CA)protocol.Re-transmission of collided packets is managed according to bi-nary exponential backoff rules.The standard also defines an op-tional point coordination function(PCF),which is a centralized MAC protocol able to support collision free and time bounded rvices.In this paper we limit our investigation to the DCF scheme.
DCF describes two techniques to employ for packet transmis-sion.The default scheme is a two-way handshaking technique called basic access mechanism.This mechanism is character-ized by the immediate transmission of a positive acknowledge-ment(ACK)by the destination station,upon succes
sful recep-tion of a packet transmitted by the nder station.Explicit trans-
Manuscript received November1998;revid July25,1999.this work was supported in part by CNR and MURST,Italy.
The author is with the Universitádi Palermo,Dipartimento di Ingegneria Elet-trica,Viale delle Scienza,90128Palermo,Italy(e-mail:bianchi@elet.polimi.it). Publisher Item Identifier S0733-8716(00)01290-7.mission of an ACK is required since,in the wireless medium,a transmitter cannot determine if a packet is successfully received by listening to its own transmission.
In addition to the basic access,an optional four way hand-shaking technique,known as request-to-nd/clear-to-nd (RTS/CTS)mechanism has been standardized.Before transmit-ting a packet,a station operating in RTS/CTS mode“rerves”the channel by nding a special Request-To-Send short frame. The destination station acknowledges the receipt of an RTS frame by nding back a Clear-To-Send frame,after which normal packet transmission and ACK respon occurs.Since collision may occur only on the RTS frame,and it is detected by the lack of CTS respon,the RTS/CTS mechanism allows to increa the system performance by reducing the duration of a collision when long messages are transmitted.As an important side effect,the RTS/CTS scheme desi
gned in the 802.11protocol is suited to combat the so-called problem of Hidden Terminals[4],which occurs when pairs of mobile stations result to be unable to hear each other.This problem has been specifically considered in[5]and in[6],which,in addition,studies the phenomenon of packet capture.
In this paper,we concentrate on the performance evaluation of the DCF scheme,in the assumption of ideal channel con-ditions and finite number of terminals.In the literature,perfor-mance evaluation of802.11has been carried out either by means of simulation[7],[8]or by means of analytical models with sim-plified backoff rule assumptions.In particular,constant or geo-metrically distributed backoff window has been ud in[5],[9], [10]while[11]has considered an exponential backoff limited to two stages(maximum window size equal to twice the minimum size)by employing a two dimensional Markov chain analysis. In this paper,which revis and substantially extends[12],we succeed in providing an extremely simple model that accounts for all the exponential backoff protocol details,and allows to compute the saturation(asymptotic)throughput performance of DCF for both standardized access mechanisms(and also for any combination of the two methods).The key approximation that enables our model is the assumption of constant and indepen-dent collision probability of a packet transmitted by each station, regardless of the number of retransmissions already suffered.As proven by comparison with simulation,this assumption leads to extremely accura
te(practically exact)results,especially when the number of stations in the wireless LAN is fairly large(say greater than ten).
The paper is outlined as follows.In Section II we briefly re-view both basic access and RTS/CTS mechanisms of the DCF. In Section III we define the concept of Saturation Throughput, and in Section IV we provide an analytical technique to com-
0733–8716/00$10.00©2000IEEE
pute this performance figure.Section V validates the accuracy of the model by comparing the analytical results with that ob-tained by means of simulation.Additional considerations on the maximum throughput theoretically achievable are carried out in Section VI.Finally,the performance evaluation of both DCF ac-cess schemes is carried out in Section VII.Concluding remarks are given in Section VIII.
II.802.11D ISTRIBUTED C OORDINATION F UNCTION This ction briefly summarizes the DCF as standardized by the 802.11protocol.For a more complete and detailed pren-tation,refer to the 802.11standard [3].
A station with a new packet to transmit monitors the channel activity.If the channel is idle for a period of time equal to a dis-tributed interframe space (DIFS),the station transmits.Other-wi,if the channel is nd busy (either immediately or during the DIFS),the station persists to monitor the channel until it is measured idle for a DIFS.At this point,the station generates a random backoff interval before transmitting (this is the Colli-sion Avoidance feature of the protocol),to minimize the prob-ability of collision with packets being transmitted by other sta-tions.In addition,to avoid channel capture,a station must wait a random backoff time between two concutive new packet transmissions,even if the medium is nd idle in the DIFS time.1
For efficiency reasons,DCF employs a discrete-time backoff scale.The time immediately following an idle DIFS is slotted,and a station is allowed to transmit only at the beginning of each slot time.The slot time
size,
is called contention window,and de-pends on the number of transmissions failed for the packet.At the first transmission
attempt,
is doubled,up to a maximum
value
reported in the
final version of the standard [3]are PHY-specific and are sum-marized in Table I.
The backoff time counter is decremented as long as the channel is nd idle,“frozen”when a transmission is detected on the channel,and reactivated when the channel is nd idle again for more than a DIFS.The station transmits when the backoff time reaches zero.
Fig.1illustrates this operation.Two stations A and B share the same wireless channel.At the end of the packet transmis-1As
an exception to this rule,the protocol provides a fragmentation mecha-nism,which allows the MAC to split an MSDU (the packet delivered to the MAC by the higher layers)into more MPDUs (packets delivered by the MAC to the PHY layer),if the MSDU size exceeds the maximum MPDU payload size.The different fragments are then transmitted in quence,with only a SIFS between them,so that only the first fragment must contend for the channel access.
TABLE I
S LOT T IME ,M INIMUM ,AND M AXIMUM
C ONTENTION W INDOW V ALUES FOR THE THREE PHY S PECIFIE
D BY TH
E 802.11S TANDARD :
F REQUENCY H OPPIN
G S PREAD S PECTRUM (FHSS),D IRECT
S EQUENCE S PREAD S PECTRUM (DSSS),AND I NFRARED
(IR)
sion,station B waits for a DIFS and then choos a backoff time equal to 8,before transmitting the next packet.We assume that the first packet of station A arrives at the time indicated with an arrow in the figure.After a DIFS,the packet is transmitted.Note that the transmission of packet A occurs in the middle of the Slot Time corresponding to a backoff value,for station B,equal to 5.As a conquence of the channel nd busy,the backoff time is frozen to its value 5,and the backoff counter decrements again only when the channel is nd idle for a DIFS.
Since the CSMA/CA does not rely on the capability of the sta-tions to detect a collision by hearing their own transmission,an ACK is transmitted by the destination station to signal the suc-cessful packet reception.The ACK is immediately transmitted at the end of the packet,after a period of time called short inter-frame space (SIFS).As the SIFS (plus the propagation delay)is shorter than a DIFS,no other station is able to detect the channel idle for a DIFS until the end of the ACK.If the transmitting sta-tion does not receive the ACK within a specified ACK_Timeout,or it detects the transmission of a different packet on the channel,it reschedules the packet transmission according to the given backoff rules.
The above described two-way handshaking technique for the packet transmission is called basic access mechanism.DCF de-fines an additional four-way handshaking technique to be op-tionally ud for a packet transmission.This mechanism,known with the name RTS/CTS,is shown in Fig.2.A station that wants to transmit a packet,waits until the channel is nd idle for a DIFS,follows the backoff rules explained above,and then,in-stead of the packet,preliminarily transmits a special short frame called request to nd (RTS).When the receiving station detects an RTS frame,it responds,after a SIFS,with a clear to nd (CTS)frame.The transmitting station is allowed to transmit its packet only if the CTS frame is correctly received.
The frames RTS and CTS carry the information of the length of the packet to be transmitted.This information can be read by any listening station,which is then able to update a network allocation vector (NA V)containing the information of the period of time in which the channel will remain busy.Therefore,when a station is hidden from either the transmitting or the receiving station,by detecting just one frame among the RTS and CTS frames,it can suitably delay further transmission,and thus avoid collision.
The RTS/CTS mechanism is very effective in terms of system performance,especially when large packets are considered,as it reduces the length of the frames involved in the contention process.In f
act,in the assumption of perfect channel nsing by every station,collision may occur only when two (or more)packets are transmitted within the same slot time.If both trans-
BIANCHI:PERFORMANCE ANALYSIS OF THE IEEE 802.11DCF
537
Fig.1.Example of basic access mechanism.
mitting stations employ the RTS/CTS mechanism,collision oc-curs only on the RTS frames,and it is early detected by the transmitting stations by the lack of CTS respons.A quanti-tative analysis will be carried out in Section VII.
III.M AXIMUM AND S ATURATION T HROUGHPUT P ERFORMANCE In this paper we concentrate on the “Saturation Throughput”.This is a fundamental performance figure defined as the limit reached by the system throughput as the offered load increas,and reprents the maximum load that the system can carry in stable conditions .
It is well known that veral random access schemes exhibit an unstable behavior.In particular,as the offered load increas,the throughput grows up to a maximum value,referred to as “maximum throughput.”However,further increas of the offered load lead to an eventually significant decrea in the system throughput.This results in the practical impossibility to operate the random access scheme at its maximum throughput for a “long”period of time,and thus in the practical mean-ingless of the maximum throughput as performance figure for the access scheme.The mathematical formulation and interpretation of this instability problem is the object of a wide and general discussion in [13].
Indeed,the 802.11protocol is known to exhibits some form of instability (,[5],and [11]).To visualize the unstable behaviour of 802.11,in Fig.3we have run simulations in which the offered load linearly increas with the simulation time.The general simulation model and parameters employed are summa-rized in Section V .The results reported in the figure are obtained with 20stations.The straight line reprents the ideal offered load,normalized with respect of the channel capacity.The sim-ulated offered load has been generated according to a Poisson arrival process of fixed size packets (payload equal to 8184bits),where the arrival rate has been varied throughout the simulation to match the ideal offered load.The figure reports both offered load and system throughput measured over 20s time intervals,and normalized with respect to the channel rate.
From the figure,we e that the measured throughput follows cloly the measured offered load for the first 260s of sim-ulation,while it asymptotically drops to the value 0.68in the cond part of the simulation run.This asymptotic throughput value is referred to,in this paper,as saturation throughput,and reprents the system throughput in overload conditions.Note than,during the simulation run,the instantaneous throughput temporarily increas over the saturation value (up to 0.74
in
Fig.2.RTS/CTS Access
Mechanism.
Fig.3.Measured Throughput with slowly increasing offered load.
the example considered),but ultimately it decreas and stabi-lizes to the saturation value.Queue build-up is obrved in such a condition.
IV .T HROUGHPUT A NALYSIS
The core contribution of this paper is the analytical evalu-ation of the saturation throughput,in the assumption of ideal channel conditions (i.e.,no hidden terminals and capture [6]).In the analysis,we assume a fixed number of stations,each al-ways having a packet available for transmission.In other words,we operate in saturation ,the transmission queue of each station is assumed to be always nonempty.
The analysis is divided into two distinct parts.First,we study the behavior of a single station with a Markov model,and we obtain the stationary
probability
.
A.Packet Transmission Probability Consider a fixed
number
538IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS,VOL.18,NO.3,MARCH
2000
Fig.4.Markov Chain model for the backoff window size.
for transmission,after the completion of each successful trans-mission.Moreover,being all packets “concutive,”each packet needs to wait for a random backoff time before transmitting.
Let
and
,as it may include a packet
transmission.In what follows,unless ambiguity occurs,with the term slot time we will refer to either the (constant)
value
is non-Markovian.However,define for
convenience .
Let
,and let us adopt the
notation ,
where
w开头的英文名
be the sto-chastic process reprenting the backoff
stage
.
The key approximation in our model is that,at each transmis-sion attempt,and regardless of the number of retransmissions suffered,each packet collides with constant and independent
probability
and will be referred to as
conditional collision probability ,meaning that this is the prob-ability of a collision en by a packet being transmitted on the channel.
Once independence is assumed,
and
;k ;k ;b (t +1)=k ;b (t )=k
BIANCHI:PERFORMANCE ANALYSIS OF THE IEEE802.11DCF539 stage0,and thus the backoff is initially uniformly chon in the
range
,the backoff stage increas,and the new
initial backoff value is uniformly chon in the
range
,it is not incread in subquent
packet transmissions.
ud to的用法Let
,(3)rewrites
abfz
as
(4)
Thus,by relations(2)and(4),all the
values
and of the conditional collision
probability is finally determined by imposing the nor-
malization condition,that simplifies as
姿势用英文怎么说
diversity
follows:
that a station trans-
mits in a randomly chon slot time.As any transmission occurs
when the backoff time counter is equal to zero,regardless of the
backoff stage,it
四级成绩保留几年
experimental
is
,
<,no exponential backoff is considered,the
probability
,and(7)becomes the much simpler
one independently found in[9]for the constant backoff window
problem
(8)
However,in
general,
,which is still unknown.To find the value
of
that a transmitted
packet encounters a collision,is the probability that,in a time
slot,at least one of
the remaining stations transmit.The
fundamental independence assumption given above implies that
each transmission“es”the system in the same ,in
steady state.At steady state,each remaining station transmits a
packet with
probability
(9)
Equations(7)and(9)reprent a nonlinear system in the two
what about loveunknowns,which can be solved using numerical tech-
niques.It is easy to prove that this system has a unique solution.
In fact,inverting(9),we
obtain
defined by(7)is also continuous in
the
range
can be
alternatively written
as
so do iis trivially shown to be a monotone decreasing function that
starts
from and reduces up
to
and
glasswool
be the normalized system throughput,defined as the
fraction of time the channel is ud to successfully transmit pay-
load bits.To
compute
be the probability that there
is at least one transmission in the considered slot time.
Since
(10)
The
probability
(11)
We are now able to
express
,
