Design and Performance Evaluation of an Asymptotically Optimal Backoff
Algorithm for IEEE 802.11 Wireless LANs
L. Bononi*, M. Conti**, E. Gregori**
*Department of Computer Science
University of Bologna
Mura Anteo Zamboni, 7, 40127 Bologna - Italy
e-mail: bononi@cs.unibo.it
Abstract
This paper presents and evaluates a distributed mechanism for
the contention control in IEEE 802.11 Wireless LANs.Specifically, our mechanism named Asymptotically OptimalBackoff (AOB), dynamically adapts the backoff window size tothe current load. AOB guarantees that an IEEE 802.11 WLANasymptotically (i.e. for a large number of active stations)achieves its optimal channel utilization. The proposedmechanism merges the ideas on adaptive backoff presented in[2] with some properties derived from the IEEE 802.11 capacityanalysis (see [3]). AOB can be used on top of the standard802.11 access mechanism without requiring any modification tothe standard or additional hardware. The AOB mechanismadapts the backoff to the network contention level by using twosimple load estimates: the slot utilization and the average sizeof transmitted frames. These estimates are simple and can beobtained with no additional costs or overheads. Theperformance of the IEEE 802.11 protocol with or without theAOB mechanism is investigated in the paper via simulation.Simulative results indicate that our mechanism is very effectiveand brings the utilization of the system close to the optimal levelfor a wide range of load and network configurations.
**Istituto CNUCE
National Research Council (CNR)Via S.Maria, 36, 56100 Pisa - Italye-mail: {M.Conti, E.Gregori}@cnuce.cnr.it
the access protocol should balance these two conflictingcosts [3,9]. Since these costs change dynamically,depending on the network load, the access protocolshould be adaptive to congestion variations in the system.Such an adaptive behavior is currently obtained in theIEEE 802.11 protocol by adopting a binary exponentialbackoff protocol [8, 11, 12]. Specifically, each user is notassumed to have any kind of knowledge about either thetransmission result (success or collision), or the numberof users in the system. Each station, to transmit a frame,accesses the channel within a random self-defined amountof time, whose mean size depends on the number ofcollisions previously experienced by the station for thatframe. This policy has to pay the cost of collisions toincrease the backoff time when the network is congested.Several authors have investigated the enhancement ofthe IEEE 802.11 DCF MAC protocol to increase itsperformance when it is utilized in WLANs. In [5, 7], via aperformance analysis, it is studied the tuning of thestandard parameters. In [21], given the BinaryExponential Backoff scheme adopted by the Standard,solutions have been proposed for a better uniformdistribution of accesses.
Trying to extend backoff protocols, a great amount ofwork has been done to study the information that can beobtained by observing the system’s parameters [10, 14,20]. Some studies try to approximate the knowledgeabout the number of users involved in the accesses byexploiting the history of the system. Example of suchworks (for the IEEE 802.11 DCF MAC protocol) relatesto the attempt to make the reduction of contentionadaptive and optimal by investigating the number of usersin the system [1,3]. It is worth observing how thisinvestigation could result expensive, difficult to obtainand subject to significant errors, especially in highcontention situations.
In this paper we propose and evaluate a mechanism,Asymptotically Optimal Backoff (AOB), for improvingthe efficiency of the IEEE 802.11 standard protocol. Thismechanism does not require any modification to thestandard or additional hardware. The AOB mechanismadapts the backoff to the network contention level by
1. Introduction
In WLANs, the medium access control (MAC) protocol isthe main element that determines the efficiency in sharingthe limited communication bandwidth of the wirelesschannel. In this paper we focus on the efficiency of theIEEE 802.11 standard for wireless LANs.
The IEEE 802.11 access scheme incorporates twoaccess methods: Distributed Coordination Function(DCF) for asynchronous, contention-based, distributedaccess to the channel, and Point Coordination Function(PCF) for centralized, contention-free accesses [8, 17].We will concentrate our study on DCF. The DCF methodadopts an access scheme belonging to the class of theCSMA/CA MAC protocols [4, 8, 12, 19]. The distributedcongestion reaction adopted in the 802.11 DCF isobtained with a variable time-spreading of the users’accesses. A channel utilization wastage is caused both bycollisions and by the idle periods introduced by thespreading of accesses. To optimize the channel utilization
0-7695-0493-0/00 $10.00 (c) 2000 IEEE1
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
using two simple and low-cost load estimates: the slotutilization and the average size of transmitted frames.AOB is based on the results derived by exploiting theanalytical model of the IEEE 802.11 protocol presentedin [1]. These results show that, given the average lengthof the transmitted frames, it exists a value for the channelutilization that maximizes the protocol capacity [6], thisvalue is indicated as optimal value in the following. Inaddition, the optimal value is almost independent on thenetwork configuration (number of active stations). AOB,by exploiting a rough and low cost estimate of theaverage size of transmitted frames, guarantees that thechannel utilization tends to the optimal value when thenetwork is congested. To achieve this goal, AOBschedules the frames’ transmission according to the IEEE802.11 backoff algorithm but adds an additional level ofcontrol before a transmission is enabled. Specifically,when the channel utilization tends to exceed the optimalvalue, AOB forces a station to postpone the transmissionalready enabled by the standard backoff algorithm. Thepostponed transmission is rescheduled as in the case of acollision (i.e., the transmission is delayed of a furtherbackoff interval). The proposed mechanism is applicable,in a transparent way, on top of the IEEE 802.11 DCFaccess mechanism. In this paper, via simulation, the AOBperformance are deeply investigated and compared withthe performance of the standard IEEE 802.11 DCF accessscheme. This performance analysis indicates that: i) underlight traffic conditions (i.e. few active stations), the AOBhas almost no impact on the protocol performance; ii)under heavy traffic conditions, by adopting the AOBmechanism, the channel utilization is close to the(analytically defined) optimal level.
The work is organized as follows: in Section 2 wepresent a brief explanation of the IEEE 802.11 standard,and we sketch the critical aspects connected to thecontention level of the system. In Section 3 the DCCmechanism proposed in [2] is summarized, while inSection 4 we sketch the capacity analysis presented in [3].In Section 5 the AOB mechanism is defined. In Section 6AOB performance are investigated via simulation.Conclusions and future researches are outlined in Section8.
IEEE 802.11 standard we address interested readers to[8,15].
The DCF access method is based on a CSMA/CAMAC protocol that requires every station to perform aCarrier Sensing activity to determine the current state ofthe channel (idle or busy). If the medium is found to bebusy, the station defers its transmission. Whenever thechannel becomes idle for at least a Distributed InterframeSpace time interval (DIFS), the station (re)starts its BasicAccess mechanism. To avoid collisions, as soon as an idleDIFS is sensed on the channel, a Collision Avoidancemechanism is needed. The Collision Avoidancemechanism adopted in the IEEE 802.11 standard is basedon a Binary Exponential Backoff scheme [8,11,12,13].When the channel is idle, time is measured in constantlength units (Slot_Time) indicated as slots in thefollowing.
The Binary Exponential Backoff scheme isimplemented by each station by means of a parameter,named Backoff Counter, which maintains the number ofempty slots the tagged station must observe on thechannel before performing its own transmission attempt.At the time a tagged station needs to schedule a newtransmission, it selects a particular slot among those of itsContention Window, whose size is maintained in the localparameter CW_Size. Specifically, the backoff value isdefined by the following expression [8]:
Backoff_CounterINTRndCW_Size ,where Rnd() is a function which returns pseudo-randomnumbers uniformly distributed in [0..1].
The Backoff_Counter is decreased as long as a slottime is sensed as idle, it is frozen when a transmission isdetected, and reactivated after the channel is sensed asidle for at least a further DIFS. As soon as the BackoffCounter reaches the value Zero the station transmits itsown frame. Positive acknowledgements are employed toascertain a successful transmission. This is accomplishedby the receiver (immediately following the reception ofthe data frame) which initiates the transmission of anacknowledgement frame (ACK) after a time intervalShort Inter Frame Space (SIFS), which is less than DIFS.If the transmission generates a collision1, theCW_Size parameter is doubled for the new scheduling ofthe retransmission attempt thus obtaining a furtherreduction of contention. The Binary Exponential Backoffis then characterized by the expression that gives thedependency of the CW_Size parameter by the number ofunsuccessful transmission attempts (N_A) alreadyperformed for a given frame. In [8] it is defined that thefirst transmission attempt for a given frame is to beperformed with CW_Size equal to the minimum valueCW_Size_min (assuming low contention). After eachunsuccessful (re)transmission of the same frame, the
2. IEEE 802.11 DCF Utilization
The basic access method in the IEEE 802.11 MACprotocol is the Distributed Coordination Function (DCF)which is a Carrier Sense Multiple Access with CollisionAvoidance (CSMA/CA) MAC protocol. In addition to theDCF, the IEEE 802.11 also incorporates an alternativeaccess method known as the Point Coordination Function(PCF) - an access method that is similar to a pollingsystem and uses a point coordinator to determine whichstation has the right to transmit. In this section we onlypresent the aspects of the DCF access method relevant forthe scope of this paper. For the detailed explanation of the
1A collision is assumed whenever the ACK from the
receiver is missing
0-7695-0493-0/00 $10.00 (c) 2000 IEEE2
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
station doubles CW_Size until it reaches the maximalvalue fixed by the standard, i.e. CW_Size_MAX, asfollows:
CW_SizeN_A
N_A1
minCW_Size_MAX,CW_Size_min2
The increase of the CW_Size parameter value after a collision isthe reaction that the 802.11 standard DCF provides to make theaccess mechanism adaptive to channel conditions.
2.1 IEEE 802.11 congestion reaction
Figure 1 shows simulation data regarding the channelutilization of a standard 802.11 system running in DCFmode, with respect to the contention level, i.e. the numberof active stations with continuous transmissionrequirements.
The parameters adopted in the simulation, presented inTable 1, refer to the Frequency Hopping Spread Spectrumimplementation [8].
Table 1: System’s physical parameters
parameter
Number of Stations (M)
CW_Size_minCW_Size_MAXChannel bit ratePayload size
Acknowledgement size
Header sizeSlotTimeSIFSDIFS
Propagation time
value
variable from 2 to 200
1610242 Mb/s
Geometric distribution200 sec (50 Bytes)136sec (34 Bytes)
50sec28sec128sec< 1 sec
These results can be explained as, in the IEEE 802.11backoff algorithm, a station selects the initial size of theContention Window by assuming a low level ofcongestion in the system. This choice avoids long accessdelays when the load is light. Unfortunately, this choicecauses efficiency problems in bursty arrival scenarios,and in congested systems, because it concentrates theaccesses in a reduced time window, and hence it maycause a high collision probability. In high-congestionconditions each station reacts to the contention on thebasis of the collisions so far experienced whiletransmitting a frame. Every station performs its attemptsblindly, with a late collision reaction performed(increasing CW_Size). Each increase of the CW_Size isobtained paying the cost of a collision. Furthermore, aftera successful transmission the CW_Size is set again to theminimum value without maintaining any knowledge ofthe current contention level. To summarize the IEEE802.11 backoff mechanism has two main drawbacks: i)the increase of the CW_Size is obtained paying the costof a collision, and ii) after a successful transmission nostate information indicating the actual contention level ismaintained.
3. Low-cost dynamic tuning of the backoffwindow size
The drawbacks of the IEEE 802.11 backoff algorithm,explained in the previous section, indicate the directionfor improving the performance of a random accessscheme, by exploiting early and meaningful information’sconcerning the actual state of congestion of the channel.The idea involves an estimate of the channel's congestionlevel, given by the utilization rate of the slots (SlotUtilization) observed on the channel by each station. Theestimate of the Slot Utilization must be frequentlyupdated. For this reason in [2] it was proposed anestimate that has to be updated by each station in everyBackoff interval, i.e., the defer phase that precedes atransmission attempt. For the use we considered to makewith, the Slot Utilization estimate has to satisfy only twoconditions:
°values included in [0..1]: the Zero value should
indicate that no slots observed in the backoff intervalresulted as busy, while the value One should indicatethat every slot available for transmission resulted asbusy;
°intermediate values should be distributed in the [0..1]
interval, proportionally to the contention level (e.g.the rate of busy slots compared to the total number ofobserved slots available for transmission).
A simple and intuitive definition of the slot utilizationestimate is then given by:
Num_Busy_Slots
Slot_Utilization ,
Num_Available_Slots
Figure 1 plots the channel utilization versus the number ofactive stations obtained in asymptotic conditions, i.e. assumingthat all the stations have always a frame to transmit. Byanalyzing the behavior of the 802.11 DCF mechanism someproblems could be identified. Specifically, the results presentedin the figure show that the channel utilization is negativelyaffected by the increase in the contention level.
0.90.80.7Average Payload = 2.5 Slot timesAverage Payload = 50 Slot timesAverage Payload = 100 Slot timesChannel Utilization of the Standard 802.11 DCFChannel Utilization0.60.50.40.30.20.10220406080100120140160180200Number of active stationsFigure 1: Channel utilization of the IEEE 802.11 DCFaccess scheme
0-7695-0493-0/00 $10.00 (c) 2000 IEEE3
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
where Num_Busy_Slots is the number of transmissionattempts2 in the backoff interval, andNum_Available_Slots is the total number of slotsavailable for transmission in the backoff interval.
In the 802.11 standard mechanism every stationperforms a Carrier Sensing activity and thus the proposedslot utilization (S_U) estimate is simple to obtain, withzero costs and overheads. The information required toestimate S_U are already available to an IEEE 802.11station, with no additional hardware required.
It is interesting to observe how the slot utilizationprovides a lower bound for the actual contention level ofthe channel. In fact, as some stations may transmit in thesame slot, it provides a lower bound to the effectivenumber of stations trying to access the channel during thelast observed backoff interval. If the value of the slotutilization is high (i.e. near to One), this implies that thelast observed backoff interval was affected by a high levelof contention on the channel.3.1 The DCC mechanism
We have seen that the slot utilization estimate provides toeach station an indication of the network contention level.This information can be utilized by each station toevaluate (before trying a “blind” transmission) theopportunity to perform or to defer its scheduledtransmission attempt. In few words, the only reasonablebehavior of a station that knows there are few possibilitiesfor a successful transmission, is to defer its transmissionattempt. Such a behavior can be achieved in an IEEE802.11 network by exploiting the DCC mechanismproposed in [2]. According to DCC, each station controlsits transmission attempts via a new parameter namedProbability of Transmission P_T(...) which constitutes thecore of the proposed mechanism.
The P_T parameter allows to realize a filtering of theaccesses between the standard access scheme adopted bythe system, and the physical layer. The value of thisparameter is dependent on the contention level of thechannel. Each station, first estimates the slot utilization,then computes the Probability of Transmission value. P_Tis used to evaluate the opportunity to perform atransmission on the shared channel. If the station decidesto defer the transmission, it reschedules a new attempt, asin the case of a collision occurred. We now present theheuristic expression to evaluate the Probability ofTransmission (P_T) adopted in the proposed DCCmechanism [2]:
P_TS_U1S_U ,where, by definition, S_U assumes values in theinterval [0..1].
The slot utilization is interpreted in DCC as aninhibition mechanism of the accesses, depending on thecontention level it represents. However, we can observe
how such a flat definition would conduct the system tofluctuate between two states, with slot utilization zero andone, i.e. no channel utilization and maximum contention,respectively. In fact, if the slot utilization is high, thenevery user would obtain a low P_T value, inducing a lowslot utilization in the next future. This will cause everyuser to obtain a high P_T value, and a future high slotutilization. To avoid this harmful fluctuating behavior, theP_T definition has been extended by introducing a furtherlocal parameter. The idea is to partition the set of activestations in such a way that each stations’ subset isassociated with a different level of privilege to access thechannel. This is achieved by including into the P_Tdefinition the number of attempts already performed forthe current frame (N_A). The N_A parameter is used as anindicator of the dynamic level of privilege achieved by astation:
N_A
P_TS_U, N_A1S_UThe lowest privilege is given to stations performing, for agiven frame, the first transmission attempt, while theprivilege level linearly increases with the number ofcollisions experienced. To better understand what weobtain, we can observe the Figure 2.
Probability of Transmission (Slot_Utilization, N_A)1Probability of Transmission0.80.60.40.2N_A = 1N_A = 2N_A = 4N_A = 8N_A = 16000.20.40.6Slot_Utilization0.81Figure 2: Probability of Transmission
In this figure we show the Probability of Transmissioncurves for users with different numbers of attemptsperformed, and with respect to the S_U values estimated.Assuming a slot utilization near to zero, we can observehow each station, independently by its number ofperformed attempts, obtains a Probability of Transmissionnear to one. This means that the proposed mechanism hasno effect on the system, and each user performs itsaccesses just like in the standard access scheme, withoutany additional contention control. This point is significantas it implies the absence of overhead introduced in low-load conditions. The differences in the user’s behavior asa function of their levels of privilege (related to the valueof the N_A parameter) appear when the slot utilizationgrows. For example, assuming a slot utilization near toone, say 0.8, we observe that the stations with the highestN_A value obtains a Probability of Transmission close to
2It is worth noting that Num_Busy_Slots includes both
successful transmissions and collisions.
0-7695-0493-0/00 $10.00 (c) 2000 IEEE4
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
one while stations at the first transmission attempttransmit with a probability equal to 0.2.
It is worth noting a property of the DCC mechanism:the slot utilization of the channel never reaches the valueOne. Assuming S_U near or equal to One, the DCCmechanism would perform asymptotically (see Figure 2)by reducing the Probabilities of Transmission for everystation. This effect was due to the P_T definition, and inparticular to the explicit presence of the upper bound Onefor the slot utilization estimate. We will exploit thischaracteristic of the P_T definition to construct the AOBmechanism.
of a successful transmission. The protocol capacity is thus[14]:
(1)maxtfttvwhere tft is the average Frame Transmission time, and tvis the average temporal distance between two consecutive
successful transmissions, also referred to as the averagevirtual transmission time. Specifically,the average virtual
transmission time includes (see Figure 3):
i)the average time required for a successful
tst, i.e. the average time intervaltransmission,
including the successful transmission and theoverheads induced by the MAC protocol definition.By denoting with the maximum propagation delay,and with SIFS, ACK, DIFS the corresponding timesconnected to the protocol implementation (see Table1), it results [3]:
tsttft2SIFSACKDIFS;ii)the idle periods. An idle period is made up of a
number of consecutive slots in which thetransmission medium remains idle due to the backoffalgorithm;
iii) the collisions which occur between two consecutive
successful transmissions.4. IEEE 802.11 DCF Capacity Analysisresults
Since a WLAN relies on a common transmission medium,the MAC protocol coordinates the network stations inaccessing the channel by means of control informationthat is carried explicitly by control messages travellingalong the medium (e.g. ACK messages), or can beprovided implicitly by the medium itself by the channelbeing either active or idle (i.e. carrier sensing). Controlmessages, or message retransmission due to collision,remove channel bandwidth from that available forsuccessful message transmission. Therefore, the fractionof channel bandwidth used by successfully transmittedmessages gives a good indication of the overheadrequired by the MAC protocol to perform its coordinationtask among stations. This fraction is known as channelutilization, and the maximum value it can attain is knownas the capacity of the MAC protocol [6].
In this section we briefly present the main results ofthe IEEE 802.11 capacity analysis developed in [3]. TheIEEE 802.11 capacity analysis is performed by assumingan IEEE 802.11 system with M stations working inasymptotic conditions, i.e., each station has always aframe to transmit. The stations transmit frames whosesizes are i.i.d. sampled from a geometric distribution withparameter q. Specifically, the size of a frame is an integermultiple of the slot Size (ts), and hence the Mean Frame
####empty slotsVirtual transmission time= collision= DIFS
= successful transmission
Figure 3: Structure of a virtual transmission timeTaking into consideration i)-iii), it follows that [3]
Size (MFS) isMFSts1q.
To simplify the analysis, in [3], it is assumed ageometrically distributed backoff instead of the uniformsampled backoff of the IEEE 802.11. At the beginning ofan empty slot a station starts the transmission of a framewith probability p, and defers the transmission withprobability 1-p. Hence, the IEEE 802.11 protocol with thenew backoff algorithm is similar to a p-persistent protocol[12].
From the geometric backoff assumption all theprocesses which define the occupancy pattern of thechannel (i.e. empty slots, collisions, successfultransmissions) are regenerative with respect to thesequence of time instants corresponding to the completion
N
_tvEIdlepCollDIFSii
i1 (2)
c
EIdle_pN
whereIdle_pi and Colli are the lengths of the i-th idle
period and collision in a virtual time, respectively; andNc is the number of collisions in a virtual time.
The length of a collision is equal to the maximumlength of colliding frames (depending on the frame sizedistribution), and depends on the Backoff Algorithm. Thelatter determines the number of colliding stations.
As we stated before, we assume that a station for eachtransmission attempt uses a backoff interval sampled froma geometric distribution with parameter p. This means
c
1
Et
st
0-7695-0493-0/00 $10.00 (c) 2000 IEEE5
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
that the average Contention Window size is given by:ECW_Size12p.
The assumption that the backoff interval is sampledfrom a geometric distribution with parameter p impliesthat the future behavior of a station does not depend onthe past. Hence, in a virtual transmission time, i) the idleperiod times Idle_pi are i.i.d. sampled from ageometric distribution with an average EIdle_p; andii) the collision lengths Colli are i.i.d with averageEColl. Thus Equation (2) can be rewritten as
ECollDIFStvENc
EIdle_pENc1ES
.(3)
Closed expressions for EIdle_p and EColl are
derived in [3] together with ENc:ENc
11pMp1p
M
M1
1tslot
EColl
11pMp1p
M
M1
Mp1p1q
M1
hMh1M
pqhpq1 1h1
Hence, tv is a function of the system’s parameters (seeTable 1), the number of active stations M, the parameter pwhich defines the geometric-distribution used in thebackoff algorithm, and the parameter q that characterizesthe frame-size geometric distribution. Fixed the value forM and q, and the system-parameter values, tv is afunction of the p value only, tvp; therefore byexploiting (3) we can analytically investigate the value ofthe p parameter that minimizes tv, named the optimal pvalue (popt). Hence popt is the p value that maximizes theprotocol capacity, see Equation (1).
In [3], it is shown that popt is closely approximated bythe p value that guarantees a balance, in a virtualtransmission time, between collisions and idle periods, i.e.ECollENcENc1EIdle_ptslot .(4)4.1 Theoretical limits vs. IEEE 802.11 and DCCprotocol capacities
In [2] the DCC mechanism effectively enhances thechannel utilization of the standard protocol. However, itscapacity is still far from the optimal capacity. It should benoted that the growth of the contention level (number ofactive stations) implies a reduction of the channelutilization in the IEEE 802.11 protocol (with or withoutthe DCC mechanism). This reduction is more marked
1p.EIdle_pM
11p
M
when long messages are transmitted due to the highcollision cost.
To summarize, results presented in [2] show that thecontention reduction introduced by the DCC mechanismis effective. However, DCC operates in a heuristic way.Its aim is to utilize, when the network congestionincreases, larger windows respect to the standard sizes,but DCC does not have any “idea” of the optimal windowsize given a contention level. Other approaches have beenproposed in the literature to dynamically tune the backoffwindow size [1, 3]. The main limitation of theseapproaches is the need to estimate from the network theinformation on the contention level. On the other hand themain advantage of the DCC approach is its simplicity,low cost, adaptiveness to network congestion levels andtransparency with respect to the standard protocol.
In the next section we define a mechanism namedAOB (Asymptotically Optimal Backoff) that dynamicallytunes the backoff window size to the optimal values stillmaintaining the main advantages of the DCC mechanism.AOB exploits the following observations:
i) the increase in the number of active stations have an
almost negligible impact on the theoretical capacitybounds;
ii) the payload size highly affects the optimal utilization
level. Specifically, decreasing the payload sizeimplies a reduction of the optimal utilization level.This can be expected as reducing the payload sizeproduces a percentage increase of the transmissionoverheads.
5. The AOB mechanism
In this section we exploit the results obtained from theanalysis of the theoretical capacity limits of the IEEE802.11 protocol to develop the AOB mechanism. The aimof this mechanism is to dynamically tune the backoffwindow size to achieve the theoretical capacity limit ofthe IEEE 802.11 protocol.
The proposed AOB mechanism is simpler, morerobust and with lower costs and overheads introducedthan the contention mechanism proposed in [3].Specifically, the AOB mechanism does not require anyestimate of the number M of active stations. Moreover,the AOB mechanism can be used in an IEEE 802.11station without any modification to the standard protocol.5.1 Theoretical capacity limits: an invariant figureIn Section 4 we have pointed out that the increase in thenumber of active stations have an almost negligibleimpact on the theoretical capacity bounds, while thepayload size highly affects the optimal utilization level.Results presented in Table 2, derived from Formulas (3)and (4) explain these effects. In the table we report forvarious network (number M of active stations) and traffic(message length) configurations the analytical values ofthe optimal popt parameter, i.e., the p value minimizes
0-7695-0493-0/00 $10.00 (c) 2000 IEEE6
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
the tv expression (3) given the M and q values. In thetable we also report for each configuration the valueMpopt. It is worth noting that while popt is highlyaffected by the M value, given a q value, the productMpopt is almost constant. This is the reason for namingit as an invariant figure. As we explain below, Mpoptis a measure of the network contention level when thenetwork utilises the optimal window size correspondingto the ongoing network and traffic configuration.
Table 2 : Analytical definition of optimality in function of M
and qMFSM = 2M = 10M = 50(Slots)MpoptpMpoptpMpoptpoptoptoptand hence from (5) it results that Mpopt is a tight upper
bound of S_U in a system operating with the optimalchannel utilization level.
5.2 Considerations about the optimal slot utilizationlevel
In the previous section we show that, given the q value, inthe “ideal case” (i.e. the stations tune the window sizeaccording to the optimal p value) the slot utilization levelis bounded by Mpopt. Now, we compare the slotutilization level of the ideal case with that of the standardIEEE 802.11 with or without the DCC mechanism. Wedefine the optimal slot utilization values exploiting theprevious analyses and considerations. Specifically, wecharacterize the S_U in the ideal case by its upper boundMpopt (see Table 2).
0.90.80.7Slot Utilization obtained: Standard, DCC, optimal valuesSlot Utilization210255082100.2616.1826.1329.1005.0811.0743.5232.3652.2658.2010.1623.1486.0443.0294.0209.0155.0124.0114.4430.2944.2091.1559.1249.1140.0086.0057.0040.0030.0024.0021.4320.2851.2018.150.121.1096
0.60.50.40.30.20.10220406080100120140Number of active stations160180200Standard’s Slot UtilizationDCC’s Slot UtilizationOPT. value, avrg. payload = 2.5 SlotsOPT. value, avrg. payload = 50 SlotsOPT. value, avrg. payload = 100 SlotsIn the following we investigate the meaning of Mpopt.As defined in Section 4, we consider M active stationsscheduling their transmission attempts in a slot selectedaccording to a geometric distribution with parameter p.Furthermore, for each configuration it exists an optimalvalue of parameter p, popt, that guarantees the balancingon the channel between idle periods and collisions. Let usnow assume that each station uses the optimal value popt.In Section 3 we introduce the slot utilization S_Uparameter to estimate the network contention level. Let usnow investigate the relationship, in the tagged contentionwindow, between S_U and Mpopt.
We denote with Ntr the number of stations that makea transmission attempt in a slot. HencePNtri is theprobability that exactly i stations transmit in a slot, andPNtr0 is the probability that a slot remains empty.Let us now observe that Mpopt is the average number ofstations which transmits in a slot:Mpopt
Figure 4: The steady-state slot utilization: DCC, standard802.11 and optimal values
In Figure 4, we compare the optimal S_U values withthe steady-state slot utilization level estimated (viasimulation) in an IEEE 802.11 network with or withoutthe DCC mechanism. It is worth noting that by adoptingthe IEEE 802.11 protocol the slot utilization level doesnot depend on the parameter q value, while it is connectedonly to the number of active stations, M.
Results reported in Figure 4 show that in the standardprotocol the S_U values are generally greater than theoptimal values. This overestimation of the optimal S_Uvalues is marked when the mean frame size is large(frame size greater than 50 slots in the figure). This canbe expected because the standard protocol produces a slotutilization level which does not depend on the frame size.On the other hand, in the optimal case, the increase of theframe size which means an increase in the collision-costthat is balanced by a decrease of the collision probability.Obviously, the decrease of the collision probability isachieved (in the optimal case) by decreasing the S_Uvalue. Even if the DCC mechanism correctly reduces,with respect to standard 802.11, the slot utilization (i.e.the contention level) under high-load conditions, theresults presented in Figure 4 indicate that DCC does notproduce the optimal channel utilization level.
i1PNtr0S_U(5)
i1
hence Mpopt is an upper bound on the probability toobserve a busy slot, i.e., MpoptS_U. Furthermore,results presented in [3] indicate that, if the stations utilizethe optimal p value, the collision probability is low (e.g.in average one collision occurs out of several virtualtimes). This means that
PNtr1Ntr0PNtr1Ntr0
tr
iPN
M
0-7695-0493-0/00 $10.00 (c) 2000 IEEE7
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
Channel UtilizationFurthermore, these results indicate that an algorithmwhich wish to drive the system to the optimal channelutilization must take into consideration the value of the qparameter.
5.3 The AOB mechanism
Let us coming back to the results presented in Table 2.Specifically, by fixing a given value for the frame sizeparameter q, it can be observed that the Mpopt productresults quasi-constant for M greater than 2, and moreprecisely, it shows only a little decrease when M grows.This means that, fixed the system’s parameters of Table 1,it is possible to define a single quasi-optimal value for theMpopt as a function of the single parameter q. To sumup, for each IEEE 802.11 physical layer parameterssetting (e.g. see Table 1), it is possible to define afunction of q, named Asymptotical Contention Limit,ACL(q), such that ACLqMpopt, q12,1. Thisfunction would represent the optimal slot-utilization levelthe system should obtain to guarantee its optimal behaviorfrom the channel utilization viewpoint. The ACL(q)function can be computed off-line by exploiting theanalytical model presented in Section 4. It is worth notingthat ACL(q) identifies the optimal contention level
without requiring the knowledge of the number of active
stations in the system. This is important, because it is thebasis for implementing an optimal window-tuningmechanism which does not require to estimate the numberof active stations in the system. Specifically, in thefollowing we show how to limit the slot utilization byexploiting the Asymptotic Contention Limit. The basicidea is i) to utilize, as in the DCC mechanism, the slotutilization level to control the stations’ transmission, andii) to disable the stations’ transmissions when the slotutilization level is greater or equal to ACL(q).
As far as point i) is concerned it is worth rememberingthat in DCC the control on the station’s transmission viathe slot utilization is obtained by introducing a Probabilityof Transmission (P_T):
Fixed a given ACL(q) value, the P_T values obtainedfluctuates among 0 and 1. We named AsymptoticallyOptimal Backoff (AOB) a mechanism which, by using theP_T defined by Equation (6), guarantees a S_U valuebelow the given ACL(q) value. The optimal ACL valuefor the slot utilization could be only asymptoticallyapproximated, for this reason the mechanism is namedAsymptotically Optimal Backoff.
6. Simulation results
In this section, by means of the discrete event simulation,we investigate the performance of the IEEE 802.11protocol enhanced with the proposed AOB mechanism.Simulation is performed by exploiting the RESQsimulation tool [16].
The main target of this performance study is toinvestigate the relationship between the channelutilization level and the network contention.
To perform this study we run a set of simulativeexperiments in which we change the number M of activestations. Active stations are assumed to operate inasymptotic conditions (i.e., with continuous transmissionrequirements). We use a maximum number of 200 activestations because the number of stations expected in thefuture for such a system could raise the order of hundreds[4]. Using up to 200 active stations enable us toemphasize the system’s characteristics, adaptiveness andscalability. The physical characteristics and parametervalues of the investigated system are reported in Table 1.It is also interesting to note that other interestingperformance indices as the Throughput and the MeanAccess Delay are strongly correlated with the channelutilization level.
0.90.80.70.60.50.40.30.20.10220406080100120140160180200Number of active stationsChannel Utilization obtained: Standard vs. optimal valuesP_TS_U,N_A1S_U
N_A
.
Standard, avrg. payload = 2.5 SlotsStandard, avrg. payload = 50 SlotsStandard, avrg. payload = 100 SlotsOPT. value, avrg. payload = 2.5 SlotsOPT. value, avrg. payload = 50 SlotsOPT. value, avrg. payload = 100 SlotsAs discussed in Section 3.1 the P_T defined aboveguarantees that the S_U asymptotically tends to 1. Theasymptotic effect is due to the P_T definition whichimplies that P_T tends to zero as the slot utilizationapproaches one. Intuitively, if the slot-utilizationboundary value (i.e. one for DCC) would be replaced bythe ACL(q) value, we reduce all the probabilities oftransmission to zero in correspondence of slot utilizationvalues greater or equal to the ACL(q). To this end in theAOB mechanism we introduce a new definition for theProbability of Transmission :
S_UN_A
(6)P_TACL,S_U,N_A1min1,
ACL
Figure 5a: IEEE 802.11 channel utilization vs. optimalvalue
7.1 Channel utilization level
The Figure 5.a shows the channel utilization level of thestandard 802.11 DCF with respect to the optimal valuescalculated by means of the analytical model defined inSection 4. For a given system configuration, the optimalchannel utilization value has been obtained by computingpopt as explained in Section 4. It is immediate to verify
0-7695-0493-0/00 $10.00 (c) 2000 IEEE8
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
0.90.80.7Channel Utilization obtained: AOB vs. optimal values99-th p.ile of MAC access delay (SlotTime units)that the performance of the IEEE 802.11 standardprotocol are negatively (low channel utilization) affectedby high-contention situations. In fact, with the standardprotocol the channel utilization level decreases when thecontention grows; this implies that collisions andretransmissions reduce the amount of user data which ispossible to deliver. Note that this problem occurs for eachpossible value of the mean payload size considered.
The effectiveness of the proposed AOB mechanism isshown in Figure 5.b. This figure shows the channelutilization level achieved by adopting the AOB systemand compares this index with the analytically-definedoptimal utilization levels. The results show that the AOBmechanism leads an IEEE 802.11 network near to itsoptimal behavior at least from the channel utilizationviewpoint. Only a little overhead is introduced when onlyfew stations are active, as we can see in the directcomparison presented in Figure 5.c. Moreover, with theAOB mechanism, the channel utilization remains close toits optimal value even in high-contention situations. Insuch cases, AOB almost doubles the channel utilizationwith respect to the standard protocol.
mechanism, by exploiting the priority effect induced bythe N_A parameter used in the probability oftransmission, increases the stations’ P_T with the increaseof MAC delay. This behavior enhances the fairness andthe queue-emptying behavior of the system.
0.90.80.7Standard, avrg. payload = 2.5 SlotsStandard, avrg. payload = 50 SlotsStandard, avrg. payload = 100 SlotsAOB, avrg. payload = 2.5 SlotsAOB, avrg. payload = 50 SlotsAOB, avrg. payload = 100 SlotsChannel Utilization obtained: Standard vs. AOBChannel Utilization0.60.50.40.30.20.10220406080100120140160180200Number of active stationsFigure 5.c: IEEE 802.11 channel utilization with orwithout the AOB mechanism
600000500000400000300000200000100000099-th percentile of MAC access delay: Standard vs. AOBStandard, avrg. payload = 2.5 SlotsStandard, avrg. payload = 100 SlotsAOB, avrg. payload = 2.5 SlotsAOB, avrg. payload = 100 SlotsChannel Utilization0.60.50.40.30.20.10220AOB, avrg. payload = 2.5 SlotsAOB, avrg. payload = 50 SlotsAOB, avrg. payload = 100 SlotsOPT. value, avrg. payload = 2.5 SlotsOPT. value, avrg. payload = 50 SlotsOPT. value, avrg. payload = 100 Slots406080100120140160180200Number of active stations220406080100120140160180200Number of active stationsFigure 5.b: Channel utilization of the IEEE 802.11protocol with the AOB mechanism vs. optimal value7.2 The 99-th percentile of MAC access delay.
The channel utilization provides information about theefficiency of a MAC protocol in sharing the channelamong several stations. However, to measure the networkQoS from the users’ standpoint other performance indicesmust be used. The delay a user experience to transmit apacket is generally used to estimate the QoS a user canrely upon. In this section we utilize the MAC delay, i.e.the time interval between the first time a packet isscheduled for transmission and the instant at which itssuccessful transmission is completed.
In Figure 6 we report the 99-th percentile of the MACdelay vs. contention level (i.e. number of active stations)for various average sizes of the transmitted frames. Itresults that the AOB mechanism leads to a great reductionof the worst case MAC delay with respect to the standardaccess scheme alone. This gives also a good indication ofthe reduced risk of starvation for transmissions. The AOB
Figure 6: 99-th percentile of MAC delay
By a careful observations of Figures 5c and 6 it is clearthat the N_A priority mechanism is really effective inreducing the tail of the MAC Delay. For example, foraverage payload equal to 100 slots, the ratio between the99-th percentile of the MAC Delay with or without theAOB mechanism is about 6 while the ratio between theaverage MAC Delay is about 2. Note that the averageMAC Delay ratio is exactly the inverse of the channelutilization ratio (see Figure 5c).
Conclusions and future research
In this paper we have proposed and evaluated the AOBmechanism which can be applied on top of an IEEE802.11 network to dynamically control the networkcontention level. This mechanism leads to the optimalchannel utilization level in a fully distributed way. Thenetwork contention level is measured independently byeach stations, by an index simple to estimate (the slot
0-7695-0493-0/00 $10.00 (c) 2000 IEEE9
Proceedings of the 33rd Hawaii International Conference on System Sciences - 2000
utilization), and it has a feedback effect on the stationbehavior. This effect is obtained through the definition ineach station of a probability of transmission which is afunction of the ratio between the measured slot utilizationlevel and an optimal utilization level (i.e., the utilizationlevel which guarantees the maximum channel capacity).The optimal utilization level has been analyticallyderived, and we have shown in the paper that, for a givensystem configuration, it is significantly affected only bythe average size of transmitted frames. Hence toimplement the AOB mechanism we need to estimate boththe slot utilization and the average frame size. Bothestimates can be done with low cost and with nooverheads or further hardware introduced with respect tothe standard protocol.
The AOB mechanism can be used on top of thestandard 802.11 DCF, allowing a quasi-optimal sizing ofthe contention window without paying (as it occurs withthe standard Binary Exponential Backoff mechanismalone) any collision cost. A great improvement in thechannel utilization is thus obtained, which results almostuninfluenced by the contention level in the system. AOBalways maintains the system near to its optimal behavior(from the channel utilization standpoint). From the userstandpoint, the age information introduced in AOB viathe N_A (Number of transmission attempts) parameter,leads to a significant reduction of the 99-th percentile ofthe Access Delay.
Traffic with different priorities’ levels can be alsoeasily introduced in an IEEE 802.11 network with theAOB mechanism. This aspect is currently underinvestigation. Two directions are investigated i) theextension of the probability of transmission with thePrior_Lev parameter, and ii) the use of different ACL(q)functions depending on the size of the frame to transmit.Future research involves the study of the use of theAOB mechanism to introduce power-saving policies(exploiting the reduction of collision cost obtainable withAOB), and the investigation of the AOB advantages inthe transmission of prioritized RTS/CTS messages.
References
[1] Bianchi G., Fratta L., Olivieri M., “Performance
Evaluation and Enhancement of the CSMA/CA MACprotocol for 802.11 Wireless LANs”, proceedings ofPIMRC 1996, 10/1996, Taipei, Taiwan, pp. 392-396.[2] Bononi L., Conti M., Donatiello L., “Design and
Performance Evaluation of a Distributed ContentionControl (DCC) Mechanism for IEEE 802.11 WirelessLocal Area Networks”, Proc. WorkshopWoWMoM’98, MOBICOM’98, Dallas, Texas,October 30 1998.
[3] Cali' F., Conti M., Gregori E., “IEEE 802.11 Wireless
LAN: Capacity Analysis and ProtocolEnhancement”, Proc. INFOCOM'98, San Francisco,CA, March 29 - April 2, 1998, pp. 142-149.
[4] Chen K.C., “Medium Access Control of Wireless
LANs for Mobile Computing”, IEEE Networks, 9-10/1994.
[5] Chhaya H.S., “Performance Evaluation of the IEEE
802.11 MAC Protocol for Wireless LANs”, MasterThesis, Graduate School of Illinois Institute ofTechnology, May 1996.
[6] Conti M., Gregori E., Lenzini L., “Metropolitan Area
Networks”, Springer Verlag Limited Series onTelecommunication Networks and ComputerSystems, November 1996
[7] Crow B.P., “Performance Evaluation of the IEEE
802.11 Wireless Local Area Network Protocol”,Master thesis. University of Arizona, 1996.
[8] IEEE standard for Wireless LAN- Medium Access
Control and Physical Layer Specification, P802.11,November 1997.
[9] Gallagher R.G., “A perspective on multiaccess
channels”, IEEE Trans. Information Theory, vol. IT-31, No.2, 3/1985, pp. 124-142.
[10] Georgiadis L., Papantoni-Kazakos P., “Limited
Feedback Sensing Algorithms for the PacketBroadcast channel”, IEEE Trans. on Info. Theory,Vol IT-31, No.2, 3/1985, pp. 280-294.
[11] Goodman J., Greenberg A.G., Madras N., March P.,
“Stability of Binary Exponential Backoff”, app. inthe Proc. of the 17-th Annual ACM Symp. on Theoryof Comp., Providence, May 1985.
[12] Hammond J.L., O'Reilly P.J.P., Performance
Analysis of Local Computer Networks, Addison-Wesley 1988.
[13] Hastad J., Leighton T., Rogoff B., “Analysis of
Backoff Protocols for Multiple Access Channels”,Siam J. Computing vol. 25, No. 4, 8/1996, pp. 740-774.
[14] D. P. Heyman, M. J. Sobel, \"Stochastic models in
operations research\" Vol. I, McGraw-Hill BookCompany, 1982.
[15] Rivest R.L., “Network Control by Bayesian
Broadcast”, IEEE Trans. on Info. Theory, Vol IT-33,No.3, 5/1987, pp. 323-328.
[16]Sauer C., MacNair E., \"Simulation of Computer
Communication Systems\[17] Stallings W., Local \\& Metropolitan Area Networks,
Fifth Edition, Prentice Hall 1996, pp. 356-383.
[18] W.R.Stevens. TCP/IP Illustrated, Volume 1: The
Protocols, Addison-Wesley, Reading, MA, 1994.[19] Tasaka S., Performance Analysis of Multiple Access
Protocols, MIT Press 1986.
[20] Tsitsiklis J.N., “Analysis on a multiaccess Control
Scheme”, IEEE Trans. on Auto. Contr., Vol AC-32,No. 11, 11/1987, pp. 1017-1020.
[21] Weinmiller J., Woesner H., Ebert J.P., Wolisz A.,
“Analyzing and tuning the Distributed CoordinationFunction in the IEEE 802.11 DFWMAC DraftStandard”, Proc. Int. Workshop on Modeling,MASCOT 96, San Jose, CA.
0-7695-0493-0/00 $10.00 (c) 2000 IEEE10
因篇幅问题不能全部显示，请点此查看更多更全内容