69 Analytical Modeling of the IEEE 802.11e EDCA Network with Contention Free Burst Mohand Yazid Nassim Sahki Louiza Medjkoune-Bouallouche LAMOS Laboratory Department of Operations Research LAMOS Laboratory University of Bejaia University of Bejaia University of Bejaia 06000 Bejaia, Algeria 06000 Bejaia, Algeria 06000 Bejaia, Algeria yazid.mohand@gmail.Com nass mi@yahoo.fr louiza medjkoune@yahoo.fr Djamil Aı̈ssani LAMOS Laboratory University of Bejaia 06000 Bejaia, Algeria lamos bejaia@hotmail.com Contention Free Burst (CFB) is a promising burst transmission scheme defined in the IEEE 802.11e Medium Access Control (MAC) protocol to achieve differentiated Quality of Service (QoS) and improve the utilization of the wireless scarce bandwidth. Although modeling and performance analysis of the IEEE 802.11e network have attracted tremendous research efforts from both the academia and industry, most existing analytical models do not give attention to the CFB QoS parameter. In this paper, we aim to propose a simple analytical model of the IEEE 802.11e Enhanced Distributed Channel Access (EDCA) function including mainly the CFB, in order to study its effect on the improvement of the achievable throughput of Video and Voice Access Categories (ACs). Therefore, we propose a new two-dimensional Markov chain model of the IEEE 802.11e EDCA function with CFB. Then, we develop a mathematical model to derive the saturation throughput. Finally, performance analysis has allowed us to estimate the maximum sustainable throughput with CFB in an IEEE 802.11e-EDCA network under infinite load conditions. IEEE 802.11e EDCA Function, CFB, Markov Chains, Modeling, Throughput Analysis 1. INTRODUCTION defines the Hybrid Coordination Function (HCF) access mechanism, which uses two mechanisms The IEEE 802.11 standard is currently one of for the support of QoS differentiation. They are the most popular wireless access technologies. It Enhanced Distributed Channel Access (EDCA) and allows for quick and simple configuration of local, HCF Controlled Channel Access (HCCA) (Lee et al. broadband networks at home, in offices, or in public (2007)). places and greatly facilitates Internet access (Kosek- Szott et al. (2011)). With the increasing demand of The EDCA function defines several QoS enhance- Wireless Local Area Networks (WLANs), especially ments to the legacy IEEE 802.11 Distributed Coor- of the IEEE 802.11 (IEEE 802.11 Standard (1999)), dination Function (DCF). EDCA operation is based the support of differentiated Quality of Service (QoS) on different priority levels through the definition of has become one of the recent critical challenges Access Categories (ACs). There are four ACs (Voice for the success of IEEE 802.11 Medium Access – VO, Video – VI, Best Effort – BE, and Background Control (MAC) protocols for the future wireless – BK), each with a separate queue. To provide traffic communications. It is important to develop a new differentiation, the following medium access parame- medium access scheme that can support the ters are defined for each AC: the Contention Window differentiated QoS requirements over IEEE 802.11 minimum (CWmin ) and maximum (CWmax ) size, the WLANs, which is specified by the IEEE 802.11e Arbitration Inter-Frame Space Number (AIF SN ), (IEEE 802.11e Standard (2005)). The IEEE 802.11e and the Contention Free Burst (CFB). The functions standard specifies differentiated service classes in of the access parameters are as follows: CWmin and the MAC layer to enable different kind of packet CWmax determine the initial size of the contention priorities and have drawn tremendous interest window and the maximum possible backoff value, from both industry and academia. IEEE 802.11e 70 respectively. AIF SN determines the minimum num- of throughput, delay, delay jitter, and frame loss ber of idle slots before a frame transmission may probability are derived. begin. The CFB allows consecutive frame transmis- sions after gaining channel access (Kosek-Szott et In this paper, we propose a simple analytical model al. (2011)). A comprehensive description of EDCA of the IEEE 802.11e EDCA function with Contention function can be found in (IEEE 802.11e Standard Free Burst. Therefore, we use a two-dimensional (2005)). Markov chain to model the behavior of a single access category. Then, we develop a mathematical After the new EDCA function was defined, the model to derive the saturation throughput of a given previously proposed analytical models of the IEEE access category. 802.11 DCF became unsatisfactory because they lacked traffic differentiation. However, they were The remainder of this paper is organized as a solid starting point for further research. Most following: an overview of the CFB scheme is given of all, they resolved the complicated problem in section 2. In section 3, we describe the proposed of representing multiple states of the channel analytical model of the IEEE 802.11e ECDA function access procedure by using Markov chains (Kosek- with CFB. The obtained analytical results about the Szott et al. (2011)). In this area, Kong et al. sustainable overall throughput in an IEEE 802.11e- (2004) presented an analytical model of the IEEE EDCA network, are presented in section 4. In section 802.11e EDCA taking into account AIFS and CW. 5, we conclude the paper. The authors analyzed the throughput performance of differentiated service traffic and proposed a 2. OVERVIEW OF THE CFB SCHEME recursive method enable to provide the mean access delay. Vassis and Kormentzas (2005) presented In DCF, the system efficiency is considerably an analytical model for the performance evaluation affected by various overheads referred to as Physical of IEEE 802.11e EDCA scheme under finite load (PHY) layer headers, control frames, backoff, and conditions on the basis of various instances of delay inter-frame space. The overhead problem becomes metric (access delay, queuing delay and total delay). more serious as the data rate increases. To mitigate Banchs and Vollero (2006) presented an analytical the impact of the overheads and improve the system model to analyze the throughput performance of efficiency, the TXOP scheme has been proposed in an EDCA WLAN as a function of its parameters the IEEE 802.11e protocol (Min et al. (2011)). (AIF S, CWmin , CWmax and TXOPLimit). The authors searched for the optimal EDCA configuration SIFS SIFS SIFS which maximizes the throughput performance of the DATA DATA DATA CW WLAN. Serrano et al. (2007) presented a model ACK ACK ACK to analyze the throughput and delay performance SIFS SIFS AIFS of the EDCA mechanism under non-saturation CFB conditions. The proposed model can be used to Figure 1: Contention Free Burst scheme. analyze generic source models, as it neither makes any assumption on the source’s arrival process nor requires all packets be of the same length. Different from DCF where a station can transmit Varposhti and Movahhedinia (2009) analyzed the only one frame after winning the channel, the effect of loss and delay caused by fading channel TXOP scheme allows a station gaining the on EDCA performance. Then, they proposed a channel to transmit the frames available in its modification to the media access scheme, called buffer successively provided that the duration of Collision Avoidance with Fading Detection (CAFD) transmission does not exceed a certain threshold, to enhance performance in wireless environments namely the CFB. As shown in Figure 1, each subject to failure. Hu et al. (2011) proposed an frame is acknowledged by an ACKnowledgement analytical model for the TXOP service differentiation (ACK) after a Short Inter-Frame Space (SIFS) upon scheme in single-hop ad hoc networks in the receiving this ACK. If the transmission of any presence of unbalanced stations with different traffic frame fails, the burst is terminated and the station loads. The QoS metrics including throughput, end- contends again for the channel to retransmit the to-end delay, frame dropping probability, and energy failed frame. The TXOP scheme is an efficient consumption are derived. Hu et al. (2012) proposed way to improve the channel utilization because the an analytical model to accommodate the integration contention overhead is shared among all the frames of the three QoS schemes including AIFS, CW and transmitted in a burst. Moreover, it enables service TXOPLimit in an IEEE 802.11e-EDCA network with differentiation between multiple traffic classes by finite buffer capacity under unsaturated traffic loads. virtue of various CFBs. Another advantage of using The important QoS performance metrics in terms the TXOP scheme is that the channel occupation time in multi-rate WLANs can be fairly distributed by 71 allocating the larger CFB to faster stations. The slow the packets available in its queue consecu- stations, therefore, no longer severely degrade the tively, provided that the duration of transmis- performance of those with the higher rate (Min et al. sion does not exceeds the specific CFB. (2011)). 2. We assume a fixed number of wireless stations, where each access category h always 3. MODELING 802.11E EDCA WITH CFB having a packet available for transmission. In other words, we operate in saturation In this section, we describe a new two-dimensional conditions. discrete time Markov chain model for the IEEE 802.11e EDCA function including the CFB. The 3. The collision probability of a packet of resolution of stationary probabilities equations of any access category h is constant and is this Markov chain model allows us to compute the independent of the number of retransmissions. packet transmission probability τ [h] of each access category h (AC[h]), where h ∈ {V O, V I, BE, BK}. 3.2. Packet Transmission Probability This probability will be used to develop a mathe- We study the behavior of a single access category matical model to derive the overall throughput of a h with a Markov chain model, and we obtain the given access category h in an IEEE 802.11e-EDCA stationary probability τ [h] that the AC[h] transmits a network. packet in a generic slot time. This probability will be 3.1. Assumptions of 802.11e ECDA Analytical used to determine the saturation throughput of the Model IEEE 802.11e-EDCA network. 1/W0 [h] The following is a list of assumptions of our analytical model for the IEEE 802.11e EDCA 0, - TL[h]+1 ... 0, -1 0, 0 0, 1 .... 0, W0 [h]- 1 function. Table 1 (resp. Table 2) includes Parameters 1 1 1-P[h] 1 1 (resp. Probabilities) of the 802.11e analytical model. P[h] 1/W1 [h] Table 1: Parameters of the 802.11e analytical model. 1, - TL[h]+1 ... 1, -1 1, 0 1, 1 .... 1, W1 [h]- 1 1 1 1-P[h] 1 1 Parameter Description P[h] n Number of stations in the network. 1/W2 [h] m[h] Maximum backoff stage of the AC[h]. W0 [h] Minimum contention window of the AC[h]. Wm [h] Maximum contention window of the AC[h]. Wi [h] Contention window size of the AC[h] at ith transmission attempt. i, - TL[h]+1 ... i, -1 i, 0 1 i, 1 .... 1 i, Wi [h]- 1 1 1 1-P[h] T L[h] Maximum number of packets can be P[h] transmitted in burst during the 1/Wi+1 [h] CF B[h] of the AC[h]. P Packet payload length. TP Time of a packet payload transmission. TM AC Time of a MAC layer header transmission. TP HY Time of a PHY layer header transmission. m[h],-TL[h]+1 ... m[h], -1 m[h], 0 m[h], 1 .... m[h],Wm[h]- 1 1 1 1-P[h] 1 1 ACK Time of an acknowledgment transmission. AIF S[h] Time interval of AIFS of the AC[h]. P[h] 1/Wm [h] SIF S Time interval of SIFS. δ Time of a signal propagation. Figure 2: Markov chain model of an access category h σ An empty slot time. running the 802.11e EDCA function. Table 2: Probabilities of the 802.11e analytical model. Let S[h] (t) be the stochastic process representing the backoff stage i (i = 0, 1, . . . , m[h]) of the AC[h] at the Probability Definition time t. τ Packet transmission probability of a wireless station. Let B[h] (t) be the stochastic process representing ei- τ [h] Packet transmission probability of a AC[h]. P [h] Packet collision probability of a AC[h]. ther the backoff time counter j (j = 0, 1, . . . , Wi [h]) or the k th transmitted packet (k = 0, −1, . . . , −T L[h]+1) during the CF B[h] for a given AC[h]. 1. All packets are of the same length. Each sta- tion that gains the channel access transmits For a given AC[h], the Wi [h] and the T L[h] are given by the Equations 1 and 2, respectively. 72 Wi [h] = 2i · W0 [h]. (1) ∑ ∑ m[h] Wi [h]−1 ∑ ∑ m[h] T L[h]−1 1 = πi,k + πi,−k , i=0 k=0 i=0 k=1 [ ] λ1 + λ2 = π0,0 · + (T L[h] − 1) . (5) CF B[h] λ3 T L[h] = . TP HY + TM AC + TP + 2 × SIF S + ACK + 2δ (2) Where, •λ1 = (W0 [h] + 1) · (1 [ − 2P [h]). ] Once the key approximation in Bianchi’s Markov m[h] chain model (Bianchi (2000)) is assumed (which •λ2 = P [h] · W0 [h] · 1 − (2P [h]) . means that, at each transmission attempt, and •λ3 = 2 · (1 − 2P [h]) · (1 − P [h]). regardless of the number of retransmissions suffered, each packet collides with constant and Hence, we have: independent probability P [h]) it is possible to model the bi-dimensional process {S[h] (t), B[h] (t)} with the λ3 discrete-time Markov chain depicted in Figure 2. π0,0 = . (6) λ1 + λ2 + λ3 · (T L[h] − 1) In this Markov chain, the only non null one-step transition probabilities are: We can now express the probability τ [h] that an AC[h] transmits in a random chosen slot time. It is the sum of all the steady-state probabilities of states   P {i, k/i, k + 1} = 1, i ∈ (0, m[h]), k ∈ (−T L[h] + 1, −2). πi,k , i = 0, 1, · · · m[h], and k = 0, −1, · · · − T L[h] + 1.     P {i, k/i, k + 1} = 1, i ∈ (0, m[h]), k ∈ (0, Wi [h] − 2). In these states, an AC[h] attempts to transmit its     packets. Thus:   P {i, −1/i, 0} = 1 − P [h], i ∈ (0, m[h]).     1 P {0, k/i, −T L[h] + 1} = , i ∈ (0, m[h]), k ∈ (0, W0 [h] − 1). W0 [h]     P [h]   P {i, k/i − 1, 0} = , i ∈ (1, m[h]), k ∈ (0, Wi [h] − 1). (3a) ∑ ∑ m[h] T L[h]−1 ∑ m[h]     W i [h] τ [h] = πi,−k + πi,0 ,     P [h] i=0 k=1 i=0  P {m[h], k/m[h], 0} = , k ∈ (0, Wm [h] − 1). Wm [h] T L[h] · (1 − P [h]) + P [h] = · π0,0 , 1 − P [h] Let πi,k = limt→∞ P {S[h] (t) = i, B[h] (t) = k}, i ∈ λ4 = . (7) (0, m[h]), k ∈ (−T L[h]+1, Wi [h]−1) be the stationary λ1 + λ2 + λ3 · (T L[h] − 1) distribution of the chain. The closed-form solution for this Markov chain is: Where, •λ4 = 2 · (1 − 2P [h]) · (T L[h] · (1 − P [h]) + P [h])  i   α · γ · π0,0 , i ∈ (0, m[h] − 1), k ∈ (0, Wi [h] − 1); From the viewpoint of a wireless station, the    θ · γ · π0,0 , i = m[h], k ∈ (0, Wi [h] − 1); probability τ that the wireless station accesses the πi,k =   αi · β · π0,0 , i ∈ (0, m[h] − 1), k ∈ (−1, −T L[h] + 1); channel is given by the Equation 8, where the access    categories VO, VI, BE and BK are represented by the θ · β · π0,0 , i = m[h], k ∈ (−1, −T L[h] + 1). (4) priorities 3, 2, 1 and 0, respectively. ∏ 3 Where, τ =1− (1 − τ [h]) (8) •α = P [h]. h=0 •β = 1 − P [h]. •γ = WWi [h]−k i [h] . The probability P [h] that a transmitted packet of a [h]m[h] given AC[h] encounters a collision, is the probability •θ = P1−P [h] . that, in a time slot, at least one of n − 1 remaining Thus, by the relation (4), all the values πi,k are wireless stations transmits, or at least one of AC[i] expressed as a function of the value π0,0 and packet (i > h) of the same wireless station transmits. i > h collision probability P [h]. π0,0 is finally determined means that, AC[i] has higher priority than AC[h]. by imposing the normalization condition, that can be Hence, we have: simplified as follows: 73 ∏ P [h] = 1 − (1 − τ )n−1 · (1 − τ [i]). (9) EI [h] = Ps [h] · P · T L[h]. (15) i>h The average length of a slot time E[σ], is obtained Equations 7, 8 and 9 form a set of nonlinear by considering that: equations. It can be solved by means of numerical • With the probability (1−Ptr ), the slot time is empty; methods. All the transition probabilities and steady- ∑3 state probabilities can be obtained. • With the probability Ptr (1 − Ps [h]), the slot time h=0 contains a collision; 3.3. Saturation Throughput (T H[h]) ∑ 3 • With the probability Ptr Ps [h], the slot time We study the events that can occur within a generic h=0 slot time, and we express the saturation throughput contains T L[h] packets successfully transmitted. of a given AC[h] in an IEEE 802.11e-EDCA network, as a function of the computed value τ [h]. ( ) ∑ 3 We express the elementary parameters of T H[h]: E[σ] =(1 − Ptr ) · σ + Ptr 1− Ps [h] · T c+ h=0 • Let Ptr be the probability that there is at least a ( 3 ) ∑ transmission in the considered slot time: Ptr Ps [h] · Ts [h]. (16) h=0 Ptr = 1 − (1 − τ )n . (10) Now, we are able to express the saturation throughput (T H[h]) of a given AC[h], as the • Let Ps [h] be the probability that the AC[h] gets ratio of the average amount of useful information the channel access. It is given by the probability that successfully transmitted EI [h] to the average length exactly one AC[h] transmits on the channel: of a slot time E[σ]: EI [h] ∏ 3 T H[h] = . (17) Ps [h] = nτ [h](1 − τ [h])n−1 · (1 − τ [i])n . (11) E[σ] i=0,i̸=h 4. SATURATION THROUGHPUT ANALYSIS • Let Tc be the time that the channel is sensed busy by a collided transmission of the first packet of any In this section, we present and analyze the obtained AC[h]: analytical results about the overall throughput of the IEEE 802.11e-EDCA network. These results are obtained after solving and programming the analytical model described in section 3 under Matlab Tc = min{AIF S[h]} + TM AC + TP HY + TP + δ (12) software. The numerical values of parameters used to get the below figures, are listed in Tables 3 and 4. Where, The throughput analysis of the IEEE 802.11e-EDCA network provided in this section, is done with AIF S[h] = AIF SN [h] × σ + SIF S. (13) different BER values, packet lengths and network sizes, in cases of aggregated and non-aggregated packets. This analysis is original and leads to new • Let Ts [h] be the time that the channel is sensed conclusions that could not be intrusively expected. busy by a successful transmission of all the packets of the AC[h]: In Figure 3, we compare the overall throughput of AC[VO] and AC[VI] obtained with and without CFB according to the number of stations in the network. Ts [h] =AIF S[h] + T L[h] · [TM AC + TP HY + TP + We observe that, the overall throughput of both AC[VO] and AC[VI] is decreasing with the increase 2SIF S + 2δ + ACK] − SIF S. (14) of the network size. This due to the number of collisions which increases with the increase of the We define EI [h], as the average amount of useful number of stations in the network. We note on Figure information successfully transmitted by the AC[h] in 3 that, the use of CFB allows significant channel a slot time. It is given as follows: utilization improvement of both AC[VO] and AC[VI]. 74 Table 3: 802.11b PHY and MAC parameters. Parameter Numerical value δ 1 µs σ 20 µs SIF S 10 µs Basic rate (PHY header) 1 Mbits/s Basic rate (MAC header) 2 Mbits/s Data rate 11 Mbits/s PHY header length 192 bits MAC header length 34 bytes ACK length 14 bytes Maximum payload length 2304 bytes Figure 4: Overall throughput variation according to the packet length. Table 4: 802.11e-EDCA default parameters. AC[h] m AIFSN W0 Wm CFB In Figure 5, we analyze the overall throughput of AC[BK] 5 7 32 1024 0 AC[VO] and AC[VI] according to the number of AC[BE] 5 3 32 1024 0 MPDUs in cases of middle and maximum packet AC[VI] 1 2 16 32 6016 s length (1500 bytes and 2312 bytes, respectively). AC[VO] 1 2 8 16 3264 s We show clearly that, the overall throughput of both AC[VO] and AC[VI] increases with the increase of the number of MPDUs allowed to be transmitted during a We also note that, when CFB is used, the overall CFB. We also note that, increasing the packet length throughput obtained with AC[VI] is greater than the allows to increase the efficiency of CFB. Through the one obtained with AC[VO]. This is due to the number presented analytical results, we can affirm that, the of consecutive MPDUs sent by the AC[VI] which is CFB is a promising burst transmission scheme which greater than the one sent by the AC[VO]. allows to enhance the utilization of the bandwidth and to achieve QoS differentiation. Figure 3: Overall throughput variation according to the network size. Figure 5: Overall throughput variation according to the CFB. In Figure 4, we compare the overall throughput of both AC[VO] and AC[VI] obtained with and without CFB according to the packet length. We 5. CONCLUSION show on this figure that, on one hand, the use of CFB permits considerably to improve the channel In this paper, we have proposed a simple analytical utilization compared to the case without CFB. On model of the IEEE 802.11e-EDCA network taking other hand, with CFB the overall throughput of into account the CFB. So, we have proposed a AC[VO] and AC[VI] increases considerably with the new two dimensional discrete time Markov chain increase of packet length. When the CFB is used, model. Then, we have developed a mathematical the collision can occur only on the first packet in model to compute the saturation throughput with burst and the other packets are spared from collision CFB of a given AC[h]. The obtained analytical related losses. This is why the throughput in case of results have allowed us to estimate the maximum CFB increases significantly with the increase of the throughput of the IEEE 802.11e-EDCA network with packet length. CFB. Particularly, the presented analytical results show how the Contention Free Burst permits to 75 increase significantly the throughput of video and Varposhti M. and Movahhedinia N. (2009) Support- voice access categories. ing QoS in IEEE 802.11e Wireless LANs over Fading Channel. Computer Communications, 32, 985–991. REFERENCES Vassis D. and Kormentzas G. (2005) Delay Banchs A. and Vollero L. (2006) Throughput Analysis Performance Analysis and Evaluation of IEEE and Optimal Configuration of 802.11e EDCA. 802.11e EDCA in Finite Load Conditions. Wireless Computer Networks, 50, 1749–1768. Personal Communications, 34, 29–43. Bianchi G. (2000) Performance Analysis of the IEEE 802.11 Districuted Coordination Function. IEEE Journal on Selected Areas in Communications, 18, 535–547. Hu J., Min G. and Woodward M. E. (2011) Perfor- mance Analysis of the TXOP Burst Transmission Scheme in Single-Hop Ad Hoc Networks with Unbalanced Stations. Computer Communications, 34, 1593–1603. Hu J., Min G., Jia W. and Woodward M. E. (2012) Comprehensive QoS Analysis of Enhanced Distributed Channel Access in Wireless Local Area Networks. Information Sciences, 214, 20–34. IEEE 802.11 Standard Part II (1999) Wireless LAN Medium Access Control (MAC) and Physical (PHY) Specifications. IEEE 802.11e Standard Part II (2005) Wireless LAN Medium Access Control (MAC) and Physi- cal (PHY) Specifications. Amendement 8: Medium Access Control (MAC) Quality of Service En- hancements. Lee Y., Lee K. S. and Jang J. M. (2007) Saturation Throughput Analysis of IEEE 802.11e EDCA. Springer-Verlag, Berlin Heidelberg, 1223–1232. Min G., Hu J. and Woodward M. E. (2011) Modeling and Analysis of TXOP Differentiation in Infrastructure-Based WLANs. Computer Net- works, 55, 2545–2557. Kong Z. N., Tsang D. H. K., Bensaou B. and Gao D. (2004) Performance Analysis of IEEE 802.11e Contention-Based Channel Access. IEEE Journal on Selected Areas in Communications, 22(10), 2095–2106. Kosek-Szott K., Natkaniec M. and Pach A. R. (2011) A Simple but Accurate Throughput Model for IEEE 802.11 EDCA in Saturation and Non-Saturation Conditions. Computer Networks, 55:622–635. Serrano P., Banchs A. and Azcorra A. (2007) A Throughput and Delay Model for IEEE 802.11e EDCA under Non Saturation. Wireless Personal Communications, 43, 467–479.