Analytical Modeling of Medium Access Control in Finite-Load and Saturated Wireless LANs by Samer El Housseini B.E., American University of Beirut, 2001 M.Sc, North Carolina State University, 2002 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA July 2006 ©Samer El Housseini, 2006 Abstract The IEEE 802.11 standard provides the specifications for a Wireless Local-Area Net-work (WLAN) technology, commonly known as Wi-Fi. IEEE 802.11 uses an Ethernet-like contention-window mechanism to resolve the multiple-access problem to the wireless channel. Essentially, a wireless station doubles its contention window size after detecting a frame collision. Although this method is effective in reducing collisions on the channel, it increases packet overhead which results in reducing the throughput. In general, the performance of the W L A N varies widely depending on the number of customers in the network coverage area and the shape of the traffic on the channel. A few analytical models have been proposed over the past few years to understand the behavior of WLANs. Although insightful, most of these models were based on a highly-simplified "saturated" networks model in which all wireless stations behave like traffic source with infinite number of frames to transmit. The saturation assumption is useful in that it leads to simple steady-state models with fixed transition probabilities. However, it is not realistic to assume that wireless stations are always attempting to transmit frames, in real networks. This thesis is concerned with the development of improved analytical models for non-saturated, or finite-load, WLANs and also propose enhancements to existing saturation ii Abstract iii WLAN models. In particular, we have developed two analytical models for WLANs with finite load. One model for the standard IEEE 802.11 WLAN and the second for the quality-of-service enabled WLAN described by the IEEE 802.1 le standard. The proposed models capture the probabilistic nature of wireless networks and the inter-dependencies among wireless stations. In our analysis, we rely on novel schemes that use coupled station-view and network-view models to compute the overall throughput, colli-sion probability, and delay in a WLAN. When compared to other recent work, our results prove to be the most accurate. We complement our work on finite-load models by presenting a more accurate model for IEEE 802.lie WLANs operating under saturation, and propose a few adaptive contention-window algorithms for maximizing the frame transmission rate and consequently the satu-ration throughput. We show through simulation that the proposed algorithms increase the throughput by several multiples. Table of Contents Abstract • ii Table of Contents iv List of Tables vii List of Figures viii List of Symbols x List of Abbreviations xiii Acknowledgements xv Dedication xvi Co-Authorship Statement xvii 1 Introduction 1 1.1 Motivation 1 1.2 Performance Issues in Wireless Local Area Networks 2 1.2.1 Standard 802.11 Wireless Networks 2 1.2.2 QoS in Wireless Networks 3 1.3 Contributions 3 1.4 Thesis Outline V 2 Overview of Wireless Local Area Networks 8 2.1 Overview the IEEE 802.11 M A C Protocol 9 2.2 The IEEE 802.1 ie M A C Protocol Extension 11 2.3 Mathematical Modeling of Wireless Networks 14 2.4 Finite-Load Models for IEEE 802.11 and 802.1 le WLANs 15 2.5 IEEE 802.lie W L A N Saturation Models and Algorithms 19 2.6 The Simulator 21 2.7 Concluding Remarks 23 3 An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 24 3.1 Introduction 24 3.2 System Model and Assumptions 26 3.3 Basic Analysis 28 iv TABLE OF CONTENTS v 3 .4 The Tagged Node Queuing Model 3 3 3 .4 .1 Service Time Estimation 3 3 3 . 4 . 2 Service Time Distribution (Tagged Node Queuing Model) . . . . 3 7 3 .4 .3 Throughput and Delay 4 1 3 . 4 . 4 Bursty Source 4 2 3 .5 Whole Network Queuing Model 4 3 3 .5 .1 Estimation of the Network Service Time and Utilization Rate . . 4 3 3 . 5 . 2 Estimation of P IDLE and P B U S Y 4 5 3 . 6 Multi-Load and Multi-Rate Wireless LANs 4 6 3 .6 .1 Multi-Load Wireless LANs . . 4 6 3 . 6 . 2 Multi-Rate Wireless LANs 4 8 3 .7 Simulation versus Numerical Results 4 9 3.7 .1 Numerical Example of the Service Time 5 0 3 . 7 . 2 Results 5 0 3.8 Conclusion 5 3 4 A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 60 4 . 1 Introduction 6 0 4 . 2 System Model and Assumptions 6 3 4 . 3 Basic Analysis 6 4 4 . 3 . 1 Estimation of the Collision Probability 6 4 4 . 3 . 2 Different AIFS Periods and Slot Occupancy Weighting 6 6 4 . 4 Tagged Node Queuing Model 6 9 4 . 4 . 1 Service Time Estimation (Node Queuing Model) 70 4 . 4 . 2 Ratio Selection 7 5 4 . 4 . 3 Service Time Distribution 8 0 4 . 5 Whole Network Queuing Model 8 2 4 . 6 Extending the Model to Multiple Priorities 8 3 4 . 7 Numerical Results 8 4 4 . 7 . 1 Numerical Example for Service Time 8 5 4 . 7 . 2 Results 8 5 4 . 8 Conclusion 8 7 5 An Improved Saturation Model for IEEE 802.11e WLANs 92 5.1 Introduction 9 2 5 . 2 Model Development 9 4 5.3 Slot Occupancy 9 6 5 .4 Throughput Analysis 9 9 5.5 Simulation Results 101 TABLE OF CONTENTS vi 6 Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 105 6.1 Introduction 105 6.2 Effect of the C W Parameters on the Saturation Throughput 106 6.3 M A C Adaptation Algorithms . I l l 6.3.1 The Station-Count Algorithm (SCA) I l l 6.3.2 The Throughput Derivative Algorithm (TDA) 113 6.3.3 The Analytical Algorithm 116 6.4 Simulation Results . 117 6.5 Conclusion 119 7 Conclusions and Future Research 126 Appendices A MATLAB Algorithm for Solving Finite-Load Models - The Non-Linear Set of Equations 138 List of Tables 3.1 Numerical Example of the components of the Service Time 50 3.2 Simulation and Mathematical Models Parameters 51 4.1 Successes and Collisions of the (3,3) pair combinations 78 4.2 Numerical Example of the components of the Service Time 85 4.3 Simulation and Mathematical model Parameters 86 5.1 Simulation Parameters for Batch 1 102 5.2 Simulation Parameters for Batch 2 102 6.1 Simulation parameters 108 vii List of Figures 1.1 Finite Load Model Architecture 5 2.1 OSI 802.11 Layer Model [5] 9 2.2 AIFS Relationships [7] 13 2.3 E D C A T X O P [ 8 ] 14 2.4 Exponential Distribution Error 2 2 3.1 Tagged Node Queuing Model 2 6 3.2 Network Queuing Model . 2 7 3.3 Finite Load Model Architecture 2 9 3.4 Service Time Distribution Approximation for Typical p 3 8 3.5 Service Time Distribution Approximation for Large p 3 9 3.6 Utilization vs. load for W L A N with 4 , 12, and 2 0 stations 5 4 3.7 Collision probability, p vs. load for W L A N with 4 , 12, and 2 0 stations . . 55 3.8 Service time vs. load for W L A N with 4 , 12, and 2 0 stations 5 6 3.9 Waiting time TQ vs. load for W L A N with 4, 12, and 2 0 stations 57 3 . 1 0 Waiting time T Q vs. load for W L A N with 4 stations with Batch Arrivals . 5 7 3.11 Key Quantities vs. load for a Multi-Load W L A N with 4 stations 5 8 3 .12 Waiting time T Q vs. load for a Multi-Load W L A N with 4 stations . . . . 5 9 4.1 Tagged Node Queuing Model 6 2 4.2 Network Queuing Model 6 2 4.3 Slot Occupancy Markov Chain (taken from [3]) 6 7 4.4 Demonstration of the Class Ratio 7 6 4.5 Utilization vs. load for W L A N with 4 , 12, and 2 0 stations 88 4.6 Collision probability, p vs. load for W L A N with 4 , 12, and 2 0 stations . . 89 4.7 Service time vs. load for W L A N with 4 , 12, and 2 0 stations 9 0 4.8 Waiting time, or Delay, W Q for Priority A vs. load for W L A N with 4 , 12, and 2 0 stations 91 5.1 Modeling Slot Occupancy for different contention zones 97 viii LIST O F FIGURES ix 5.2 Collision Probability vs. Number of Stations for Batch 1 103 5.3 Saturation Throughput vs. Number of Stations for Batch 1 103 5.4 Collision Probability vs. Number of Stations for Batch 2 104 5.5 Saturation Throughput vs. Number of Stations for Batch 2 104 6.1 Effect of C W M I N and C W M A X on the Saturation Throughput 109 6.2 Effect of C W M I N and C W M A X on the Probability of Collision 110 6.3 The TDA Operation Zones 115' 6.4 Static vs. Station-Count Algorithm - Throughput 121 6.5 Static vs. Station-Count Algorithm - C W M I N Change 121 6.6 Static vs. Throughput Derivative Algorithm - Throughput 122 6.7 Static vs. Throughput Derivative Algorithm - Low Pass Filtered Throughput 122 6.8 Static vs. Throughput Derivative Algorithm - Derivative 123 6.9 Static vs. Throughput Derivative Algorithm - C W M I N Change 123 6.10 Static vs. Analytical Algorithm for Priority A 124 6.11 Static vs. Analytical Algorithm for Priority B 124 6.12 Proof of Optimization for the Analytical Algorithm 125 List of Symbols p Probability of Collision N Number of Wireless Stations or Nodes A Frame Arrival Rate P[NT] Probability of No Transmission P- Tagged Node Service Rate Pnet Wireless Medium Service Rate P Tagged Node Utilization Rate Pnet Wireless Medium Utilization Rate T Probability of Transmission when Wireless Station is not empty Pbacko ff Portion of Frames going through Backoff Minimum Contention Window CWmax Maximum Contention Window wp Average Backoff Counter Value excluding Direct Transmissions w Average Backoff Counter Value including Direct Transmissions Iw Average Backoff Contention Window Size Pbusy Probability of Busy Wireless Medium Pidle Probability of Idle Wireless Medium CycleCx Average Number of Transmission Cycles Ending in Collisions nodeCx Average Number of Collision Slots involving the Tagged Node queueCx Average Number of Collision Slots involving the Tagged Queue otherCx Average Number of Collision Slots from Other Nodes backoff Average Number of Backoff Slots nodeTx Average Number of Successful Transmission Slots from the Tagged Node X LIST OF SYMBOLS xi queueTx otherrx Px px PotherCx P otherTx Po Ts b(t) bnetit) Bis) Qiz) QnetiZ) nnetk pN 1 net Rs P,rZonej Ptr. Z=l PcxZonei Pc£ bt RatioxY btjc Average Number of Successful Transmission Slots from the Tagged Q Average Number of Successful Transmission Slots from Other Nodes Portion of Frames Arriving to an Empty Queue with Busy Medium Portion of Frames Arriving to an Empty Queue x with Busy Medium Average Number of Collisions from Other Nodes Average Number of Successful Transmissions from Other Nodes Portion of Transmissions from Other Nodes that results in Collisions Number of Slots that a Successful Transmission takes to complete Number of Slots that a Collision takes to complete Proposed Service Time Distribution of the Tagged Node Proposed Service Time Distribution of the Wireless Medium Laplace Transform of the Proposed Service Time Distribution PGF of the Queue Length Distribution of the Tagged Node PGF of the Queue Length Distribution of the Wireless Medium Queue Length Probabilities of the Tagged Node Queue Length Probabilities of the Wireless Medium Average Queue Length Variance of the Average Service Time Average Waiting Time Average Delay Probability of Counting j Slots before the first Backoff-Counter fires Expected Value of PN. Ratio of Idle Slots in a Wireless Medium Transmission Cycle Probability of Transmission in Contention Zone i Probability of Transmission in Contention Zone i Probability of Collision of Priority x in Contention Zone i Probability of Collision of Priority x in Contention Zone / Steady State Probabilities of the Slot Occupancy Markov Chain Av. Number of Successful Transmissions from Y in X's Service Time Steady State Probabilities of the Backoff Markov Chain LIST OF SYMBOLS xii Pj Average Probability of Collision for Priority j ED Expected Length of the Transmission Duration Probability of any given Transmission being Successful Probability of Priority j's Transmission being Successful Pt-fii Probability of any given Transmission being a Collision ED Expected Length of the Transmission Duration Expected Payload of Priority j Tj Average Throughput of Priority j List of Abbreviations A C Access Category A C K Acknowledge Frame AIFS Arbitration Inter-Frame Spacing AP Access Point CFP Contention-Free Period CP Contention Period C S M A / C A Carrier Sense Multiple Access/Collision Avoidance CTS Clear To Send CW Contention Window DCF Distributed Coordination Function DIFS DCF Inter-Frame Spacing DVD Digital Video Disc E D C A Enhanced Distributed Channel Access E F L Enhanced Finite-Load EIFS Extended Inter-Frame Spacing FIFO First In First Out H C C A HCF Controlled Channel Access HCF Hybrid Coordination Function IFS Inter-Frame Spacing IP Internet Protocol IT Information Technology L A N Local Area Network M A C Medium Access Control xiii LIST O F ABBREVIATIONS xiv NAV Network Allocation Vector PC Personal Computer PCF Point Coordination Function PDA Personal Digital Assistant PDF Probability Distribution Function PGF Probability Generating Function PHY Physical Layer QoS Quality of Service RTS Request To Send RV Random Variable SCA The Station-Count Algorithm SIFS Short Inter-Frame Spacing ST Saturation Throughput TCP Transmission Control Protocol TDA The Throughput Derivative Algorithm TGe IEEE 802.11 Task Group E TGn IEEE802.i l Task Group N TXOP Transmission Opportunity VoIP Voice Over IP Wi-Fi IEEE 802.11 Wireless Local Area Network W L A N Wireless Local Area Network WWiSE World-Wide Spectrum Efficiency Acknowledgements I would like to thank my supervisor, Dr. Hussein Alnuweiri, for all the guidance, sup-port, and time that he offered. I firmly believe that without all his expertise and understand-ing, I wouldn't have completed my Ph.D. And for this, I am eternally grateful. I would like to thank the other members of my committee for the invaluable help they provided during my research journey: Dr. Victor Leung, Dr. Vikram Krishnamurthy, Dr. Vincent Wong, and Dr. Dave Michelson. Being totally honest, my experience with each and every professor was a very pleasant one. I also received lots of support and guidance from my group members. And any work would be terribly boring without the friendly, sometimes too-much-fun-to-work, atmo-sphere in our lab. The friendships of these people mean a lot to me: Ayman Kaheel, Junaid Khan, Tamer Khattab, Yasser Pourmouhammadi, Tariq Al-Khasib, Amr Salem, Zaman Mollah, Salman Khan and Mahmood Minhas. I would also like to thank all the other people whose non-technical help made the writing of this thesis possible. xv To my parents whose immense support was illogical by all scientific standards . xvi Co-Authorship Statement Chapter 5 has been taken from a paper that was submitted as an IEEE Communication Letter. The co-authors of this paper are Yasser Pourmouhammadi, Hussein Alnuweiri, and myself. As a research group, we have been working on modeling IEEE 802.11 and 802.lie WLANs, and this was a common area where we shared our knowledge and work. The research and model analysis have been done in long group sessions on a round table. Yasser wrote the greater part of the paper, while I implemented the mathematical model in C, generated the simulation data and plots, and finished writing the last part of the paper. xvii Chapter 1 Introduction 1.1 Motivation The most common technology that allows wireless communication is a wireless local area network, also known as 802.11 network, W L A N , and wi-fi network. Grand Haven, Michigan has been the first city in the US to deploy a Wi-Fi network with full-city coverage in 2004 [1]. The metropolitan city of Philadelphia is comparing Wi-Fi networks to water and electricity networks, and is planning to cover its 135-square-mile neighborhoods with high speed wireless internet. The city of San Francisco is soon to follow [2]. With such massive and expansive deployments, wireless local area networks will cer-tainly become a legacy technology in the future. But until that day, more research needs to be conducted to identify and harness the true limits of this technology. Academic and industrial research sometimes takes years to fine-tune a certain technology to befit the commercial market, forcing early releases to evolve over time. 1 Chapter 1. Introduction 2 In the complex phases of research and development, modeling is the most time-consuming albeit rewarding phase and can even outlast the design phase. Models are often built to foretell the behavior of the system under study, thereby giving designers the freedom to alter the design, without any further cost and time. For all the reasons mentioned, we found it beneficial to build mathematical and simu-lation models for wireless local area networks, especially that the literature was lacking accurate models in this area. Also, with the new wireless revolution being multimedia-centric, we decided to extend our models to cover Quality-of-Service enabled WLANs, or 802.lie wireless networks. 1.2 Performance Issues in Wireless Local Area Networks 1.2.1 Standard 802.11 Wireless Networks A wireless local area network is a network of stations that use radio frequencies, trans-mitting through the air as a means of communication. With today's wireless network cards, each station has a maximum range of about two hundred meters, and a varying bandwidth that depends on the communication hardware capabilities and the conditions of the wire-less medium. Typical bit rates range from 11 Mbps for 802.1 lb networks, to 54 Mbps for 802.1 lg networks, and upwards of 100-200 Mbps in 802.1 In (up to 540 Mbps for WWiSE and 630 Mbps for TGn). A W L A N is normally deployed as the last-mile carrier of the traffic, with data traveling in wired networks until the last hop, which is then transmitted wirelessly. A W L A N could Chapter 1. Introduction 3 also very well replace the backbone of the network, through a multi-hop wireless network, connecting both ends of the data exchange. Wireless LANs functioning without an Access Point are called Ad-Hoc networks. These networks have special routing algorithms to allow the exchange of data frames between two wireless stations. Wireless LANs operating with an Access Point are called to be working in infrastructure mode. The Access Point acts as the center of the network. Since it often has double the signal range, all frames are forwarded to the Access Point, which then sends the frames to their final destination. 1.2.2 QoS in Wireless Networks Since the approval and standardization of the 802.1 le specification in 2005, Quality-of-Service (QoS) in WLANs has become more reality, rather than just an optional extension. Recent trends of the industry have placed more emphasis on voice and video transmission in laptops and hand-held devices, such as cell phones and PDAs. The more illustrious example is the recently manufactured Wireless DVD Player. Towards this purpose, the 802.lie standard defines multiple classes of service in the network traffic in WLANs. These classes are treated with different priorities, such as setting higher priorities to voice and video traffic over data traffic, to ensure its correct and timely transmission and recep-tion of time-critical multimedia services. 1.3 Contributions The major contributions of our research are: Chapter 1. Introduction 4 1. The development of a new accurate mathematical model for 802.11 networks under the finite load condition called Enhanced Finite-Load Model. The proposed model is, in our view, the most accurate in the literature, as will be illustrated by the results presented in Chapter 3. Many papers tried to tackle the finite load problem while focusing on only one aspect of their model, while over-simplifying the rest. In gen-eral, the studies followed one of four different trends: a few studies tried to solve it as a queuing problem with over-simplified averages, while others used only average quantities to solve a non-linear set of equations that describe the system. And out of both, some argued for using the wireless station as the system under study, while others insisted on studying the wireless medium. In Figure 1.1 which represents our work, we show that by merging the four perspectives, each represented by its own block, we have a logically more complete model. The key contribution of this thesis is the development of a highly detailed wire-less modeling framework (the top left block in Figure 1.1) that can be applied to queuing models, mainly M / G / l , and can lead to a much more accurate prediction of the wireless network behavior. The modeling framework incorporates a large num-ber of parameters that are either inputs to the system, or Medium Access Control (MAC) transmission protocol specifics. We have also approximated the service time distribution of frame transmissions with a closed-form equation. This can provide basic analysis and close approximations for QoS purposes, such as minimum and maximum delay and buffer bounds. Chapter 1. Introduction 5 Intermediate Values: Average Service Time, Probability of Collision, etc. Inputs: Load, DCF Protocol | Parameters, etc... Wireless Node Modeling Framework {Supplies the Node Queuing Model with accurate means and distributions) V ^Utilization-KO Node Queuing Model -Probability of Busy Medium Wireless Medium Modeling Framework BO Wireless Medium Queuing Model Outputs: Waiting Time, Queue Length, etc Figure 1.1: Finite Load Model Architecture The improved accuracy of our model can be also attributed to the fact that we incorporated most of the relevant MAC parameters in our analysis. For example, our model employs different probabilities for direct frame transmissions (i.e. without backoff), transmissions after backoff, incomplete transmissions, etc. As a result, our model provides more accurate expressions for the channel busy-period and the average service time. 2. The other key contribution of this thesis is the extension of our finite load model to 802.1 le WLANs. The extended model is presented in Chapter 4. The few papers that were published in this area mostly had the same shortcomings done in 802.11 models. However, due to the prioritized nature of the Access Categories, these short-Chapter 1. Introduction 6 comings had a huge effect on the final calculations, and the system converged to a wrong set of values. We also discuss in detail the complexities of a probabilistic multi-priority system, such as the transmission interference between traffic classes. The development of this finite-load model for QoS-enhanced WLANs is important for the emerging research on transporting multimedia traffic over WLANs. Our work helps to identify wireless networks delays and buffer distributions. 3. To complete the modeling of WLANs in all its operation cases, we have improved an existing model for 802.lie networks under saturation. The improved model corrects invalid assumptions published previously for the Backoff Process [3]. The improved model has high accuracy and will be presented in Chapter 5. 4. The development of three Throughput Improvement Algorithms for WLANs oper-ating in saturation mode. Three algorithms are presented in Chapter 6, and in [4]. These adaptive algorithms monitor the wireless network conditions in an Access Point. Based on the measured quantities, the algorithms peform their calculations, taking into account the number of nodes and the type of their traffic, and decide on a set of 802.1 le M A C Protocol values that will maximize the Saturation Throughput. These values are then broadcast to the wireless stations in the network to be used immediately. Chapter 1. Introduction 7 1.4 Thesis Outline Chapter 2 gives an overview of 802.11 networks and its underlying technology. It de-scribes the modes of operations, and access protocols. The same is done for 802.1 le net-works. Chapter 2 also surveys all previous and related major studies, and introduces our models with a comparison to previous models. Chapter 3 presents a new highly accurate mathematical model of 802.11 networks under the finite-load condition. Chapter 4 extends the model in Chapter 3 to 802.lie networks. Chapter 5 introduces the improved mathe-matical model for 802.lie networks under saturation, and proposes three new algorithms to improve the throughput in 802.1 le networks operating in infrastructure-mode. Chapter 6 presents three adaptive algorithms that are used to improve the Saturation Throughput in overloaded WLANs. Chapter 7 concludes this thesis, and presents some open research problems that can be the starting points for other studies. Chapter 2 Overview of Wireless Local Area Networks The IEEE 802.11 standard for wireless LANs was approved in 1997. It denned two of the seven layers of the OSI model, which are the Medium Access Control (MAC), and the Physical (PHY) layers, as shown in Figure 2.1. The 802.11 standard was intended to replace the 802.3 Ethernet standard where wiring was not desired or possible, by offering the same services needed for the upper layers. To deal with the variable and less predictable conditions of the wireless medium, the M A C layer function is more complex in the 802.11 standard, and is therefore still the subject of much recent research. In this chapter, we will present an overview of the 802.11 M A C , as well as the 802.1 le M A C . 8 Chapter 2. Overview of Wireless Local Area Networks IEEE 802.2 Logical Link Control (LLC) IEEE 802.11 Media A c c e s s Control (MAC) Frequency Direct Hopping Sequence Infared PHY Spread Spread Spectrum PHY Spectrum PHY X-MAC PHY OSI Layer 2 (Data Link) OSI Layer 1 (Physical) Figure 2.1: OSI 802.11 Layer Model [5] 2.1 Overview the IEEE 802.11 MAC Protocol The basis for the 802.11 M A C is a C S M A / C A mechanism (Carrier Sense Multiple Ac-cess with Collision Avoidance). Carrier sensing is done through physical sensing of the Radio Frequency (RF) carrier as well as a virtual carrier sensing in the M A C itself. Virtual carrier sensing is done through maintaining a Network Allocation Vector signal (NAV) that determines for how long the channel remains busy. NAV is set in a duration field of the M A C messages. Collision avoidance in 802.11 M A C is performed by a mechanism called Distributed Coordination Function (DCF). The M A C has two modes of operation, Contention Period (CP) in which any one or more stations may try to access the medium according to DCF rules, and Contention Free Periods (CFP), in which the stations are only allowed to respond to the poll messages sent by the access point operating in PCF mode. DCF is a protocol that describes how stations can contend for the wireless medium in a distributed manner. PCF, on the other hand, is a protocol that specifies a centralized contention-free access to the wireless medium organized by the access point. In the DCF mode, otherwise known as the contention period (CP), all wireless stations compete for access to the channel by applying a C S M A / C A protocol. If the channel is busy, Chapter 2. Overview of Wireless Local Area Networks 10 the station will freeze its operation and wait for the channel to become available. DCF provides best-effort, asynchronous data transfer and is mandatory in all 802.11 wireless stations. Medium access control in ad-hoc networks is implemented by means of DCF only. In order to access the channel under DCF, prior to transmitting, a wireless station must first sense the channel to determine if another station is currently transmitting. If no other station is found to be transmitting, the station waits a DCF Inter-Frame Spacing (DIFS) time period and starts the backoff process if the channel is still free after the DIFS period. If a second station is transmitting, or if one starts to transmit during the DIFS period, the first station will wait for the channel to become free for a DIFS period. After the channel has been idle for a DIFS period, a random backoff timer is started. If the channel becomes busy while the timer is running, the timer will pause. The timer will then restart after the channel has been free for a DIFS period. When the timer expires, the station will begin transmission of its data. The timer is selected using a slotted binary exponential backoff technique. The time following the idle DIFS is slotted and stations can only transmit at the beginning of a slot. The backoff time is uniformly chosen in the interval [0, CW-1] where CW is the Contention Window. At the first transmission attempt, CW is set to be equal to Contention Window Minimum C W M I N , then it is doubled at each retransmission attempt up to Contention Window Maximum C W M A X . Typical values of C W M I N and C W M A X are 32 and 1024 slots respectively [6]. Upon successful reception of a frame, the receiver waits a Short Inter-Frame Spacing (SIFS) interval and then transmits an Acknowledge Frame (ACK) for the received frame. Chapter 2. Overview of Wireless Local Area Networks 11 When the A C K is received, the station must wait a random backoff time before attempting to access the channel again. If the A C K is not received within a timeout period, the station assumes a lost frame and must contend for channel access again and try a retransmission of the frame. If the maximum number of retransmission attempts is exhausted, the station must drop the frame. 2.2 The IEEE 802.1 le MAC Protocol Extension The 802.1 le committee or Task Group E (TGe) has been conceived for the purpose of enabling Quality of Service (QoS) support on 802.11. The 802.1 le DCF function, now called the HCF function (Hybrid Coordination Function), supports on top of it two other functions: the E D C A and the HCCA . The E D C A (Enhanced Distributed Channel Access) operates as a Contention Period (CP), and the H C C A (HCF Controlled Channel Access) operates as a Contention-Free Period (CFP). In CP, the E D C A functions of all the stations contend for the medium; whereas in H C C A , the Access Point (AP) controls the medium, and polls the stations based on the decisions of a scheduler. The IEEE 802.1 le specification [7] supports 8 priority queues or User Priorities (UPs), divided among 4 Access Categories (ACs) per station. The 4 ACs are voice, video, data, and background traffic in decreasing priority. The queues have different Arbitrary Inter-Frame Spacing (AIFS) periods according to their traffic type. Furthermore, each A C has a different minimum and maximum CW periods ( C W M I N and C W M A X ) , as well as separate CW variable for each AC. This provides better prioritized access to the wireless medium. Therefore, the service differentiation in E D C A is provided by a combination of the follow-Chapter 2. Overview of Wireless Local Area Networks 12 ing three mechanisms [7]: 1. the Arbitrary Inter Frame Space period (AIFS), 2. the Contention Window parameters (CWMIN, C W M A X ) , 3. and the Transmission Opportunity (TXOP). In EDCA, each queue or AC operates independently as if 8 contending stations reside in the same physical stations. This mode of operation classifies collisions into internal and external collisions. Internal collisions are handled inside the station, whereby the higher priority queue transmits, and the lower priority one backs off again. External collisions are the normal collisions that happen physically in the wireless transmission medium. Arbitrary Inter Frame Space (AIFS) In EDCA, each queue will defer for a number of slots that is equal to the AIFS period specific to the queue's AC, every time the medium turns idle, as shown in Figure 2.2. This deffering mechanism precedes the backoff mechanism, which may not be reached, if the medium turns busy before the AIFS period ends. By using different AIFS period values, higher priority ACs will have a lower AIFS values, therefore getting access to the medium before a lower priority AC does. Another aspect of the differing AIFS periods, the backoff counter of a higher priority AC starts decrementing before lower priority backoff counters. For this, consider the scenario where two queues belonging to two different ACs choose the same backoff value. In this case the AC with the lower AIFS period will transmit first with no collision. Chapter 2. Overv iew of Wireless Loca l A r e a Networks 13 Immediate access when Medium is free >= DIFS/A1FS[i] DIFS/AIFS 1 B u s y M e d i u m AIFSQ] .AIFS[i] DIFS k O - O f PIFS »—is S1FS H77777 °f77777 Contention Window Ef T I T Backoff Slots Defer Access I l I In 22 Next Frame i Slot time Select Slot and Decrement Backoff as long I S 3~ as medium is idle Figure 2.2: AIFS Relationships [7] Content ion W indow Size Each A C has a separate minimum and maximum contention window parameters ( C W M I N and C W M A X ) , in addition to keeping a separate current contention window variable (CW[AC]). This also contributes to the prioritized access to the wireless medium. Furthermore, the backoff counter in E D C A is chosen in the range [1, CW[AC]+1] instead of [0,CW], to avoid the case where an A C with AIFS[AC] = 0 preempts other ACs. Transmission Oppor tun i ty The Transmission Opportunity (TXOP) is a new concept introduced in the 802.1 le spec-ification. After contending for and winning the wireless medium, a station is granted a pre-determined amount of time equal to the TXOP value of the winning A C . In this TXOP time window, the station can send as many frames as possible from the corresponding queue. However, the station must ensure that all the frames with their corresponding frame ex-changes (RTS, CTS, Data-ACK) should not overstep the TXOP time limit (see Figure 2.3). TXOPs introduce the ability to transmit a burst of frames between a station and the AP, and offer a definite advantage for bursty multimedia sources or low-payload per frame Chapter 2. Overview of Wireless Local Area Networks 14 AIFS( UPJ + Backoff SIFS SIFS SIFS AlFSfUP) Post Backoff [M QoS Data(UP) ACK QoS Data(UP) ACK ML EDCF TXOP Umit >= 0 time gap' Figure 2.3: E D C A TXOP [8] sources. The TXOP concept also enhances the throughput, for the station spends more time sending frames, and less time contending for the medium. In mathematic-like de-scriptions, less contention means lower transmission overhead and higher throughput, and fewer collisions means better service and lower frame delay. 2.3 Mathematical Modeling of Wireless Networks A mathematical model captures the behavior of the wireless network, and provides ef-fective means to estimate network performance under various loading conditions. One of the crucial parameters of the model is the backoff process of the M A C layer, which governs the activities of a wireless station. The backoff process decrements a randomly generated number with each slot. This time slotted process makes it possible to model the backoff function as a discrete Markov Chain [9] [3]. The success and failure of each frame transmission relies on the interaction between different backoff processes that are running independently in each station/queue sharing the same wireless channel. If two contending stations choose the same initial number, then as they count down to zero, their corresponding transmissions will collide. Therefore Chapter 2. Overview of Wireless Local Area Networks 15 a careful scrutiny of MAC-related probabilities is necessary to complete the mathemat-ical model especially since the backoff process chooses its initial counter values from a contention window with a uniform distribution. Two types of models have been proposed for W L A N s . In a finite-load W L A N model, the queues in a wireless network are seldom full . A s the rate of frame arrival and the manner with which they arrive change from network to another, the mathematical model normally needs queuing theory to solve the problem in hand. On the other hand, in a saturated W L A N model, the system is modeled using only averages, and does not use a queueing model. The reason is, since all the queues are backlogged at all times, the server has a utilization of 1, and therefore quantities such as the average queue size and the average waiting time are not valid. Such studies mainly focus on deriving three quantities: the probability of transmission, the probability of collision, and the saturation throughput. 2.4 Finite-Load Models for IEEE 802.11 and 802.11e WLANs Zeng and Chlamtac [10] constructed a queuing model for W L A N s with finite load using the network as the queuing server, and made several over-simplified assumptions regarding the collision probability in the wireless channel without modeling the post-collision back-off process. Although their model produced crude approximations of the system values, it has the advantage of useful simplicity. Ozdemir and M c D o n a l d [11] provide a useful model for the backoff process and service-time distribution, but their work models the sat-Chapter 2. Overview of Wireless Local Area Networks 16 urated network case and is similar to the models proposed earlier by Bianchi [9][12] and Robinson and Randhawa [3]. Zaki and Al-Hadidi [13] proposed another useful model, but as in [14][15], they did not consider the case of directly transmitted frames, and did not provide an expression for service time distribution, as well as a simplified average service time expression. Cheng and Wu [16] proposed a finite-load model, but neglected to include successful transmissions from other stations during the transmitting cycles of a particular station. This led to a distorted value of the service-time and other key quantities. The same simplifying assumption appeared in [17], [18], [19], [20] and [21]. Recently, Tickoo and Sikdar [14][15], proposed a simpler, and fairly accurate, finite-load analysis using only a node (user) model, but did not include the network model. Some of our node model derivations were based on their work. Cantieni et al. [20] have also developed a fairly detailed finite-load model for multirate WLANs but using a different approach that does not rely on the dual-model symbiosis. A concept based on using two queuing models, one user-centric and another network-centric, has been explored before by Medepalli and Tobagi [22], where they demonstrated how a W L A N can be modeled using both views. The model we develop in the next chap-ters is also based on using two queuing models. However, their approach differs from ours in that their two queuing models are applied independently, thus leading to less accurate results. We will show that by coupling the two models, our method leads to much more accurate results that match very closely those produced by detailed W L A N simulators. Chapter 2. Overview of Wireless Local Area Networks 17 There is relatively little reported work on modeling QoS-enabled finite-load 802.lie WLANs. In [23], Engelstad and Osterbo built a good model that took into account the different AIFS periods for each priority. However, they did not include successful trans-missions from other stations in their service time expressions. Tickoo and Sikdar extended their model in [15] to 802.lie networks. However, since we used their work as a starting point, our approach yielded more accurate and varied quantities, especially when modeling the "presence" of each priority compared to other priorities and its impact on the average service time of the queue. But the most notable study on finite-load 802.lie WLANs was delivered by Vassis and Kormentzas in [24]. Their expression of the average service time was fairly detailed, and they followed the same procedure to derive quantities such as the average waiting time. However, they made the simplifying assumptions of overlooking the effect of the AIFS on the probability of collision, and the effect of the interference of transmissions between multiple ACs on the average service time. The improvement accomplished in our finite load model, labeled the E F L model in this thesis, over the available models, was to use a complete and extensively detailed model as was depicted in Figure 1.1. We represented most of the relevant details of the DCF protocol with mathematical expressions, whether it be a probability, a queueing theory average, or just an obvious approximation, to form a complete mathematical picture. The mathemati-cal expressions for the Node Modeling Framework and the Medium Modeling Framework are grouped in a complementary fashion to form a non-linear set of equations. An efficient Chapter 2. Overview of Wireless Local Area Networks 18 algorithm would exploit some special feature in this set to solve it using iterations and generate all the final values when the system converges, as will be demonstrated in Ap-pendix A. The results of each iteration are fed into two M / G / l queuing models, to evaluate quantities such as the server utilization. The queuing models then feedback these resulting quantities to the frameworks in the next iteration to refine the results. Derived expressions such as the average queue length and the average queue waiting time are evaluated in the last iteration. Since the station's behavior changes when the wireless medium is busy with a trans-mission from another station, it was necessary to derive the probability of a busy medium. This expression can only be derived if the medium was treated as the server in a queueing model. The busy probability would then be equal to a fraction of the utilization rate of this wireless medium server. This detail justifies the use of a double queuing model. The E F L model was extended in Chapter 4 to heed the changes of the 802.1 le newly approved standard. This model is one of the first few models available in the literature for the 802.lie WLANs and, to the best of our knowledge, the most accurate yet. The same algorithm in Appendix A was used to solve the non-linear set of equation generated by this model. Chapter 2. Overview of Wireless Local Area Networks 19 2.5 IEEE 802.11e WLAN Saturation Models and Algo-rithms Numerous 802.1 le saturation models have been published, the most notable ones by Xiao in [25], Tsai and Wu in [26], Zhu and Chlamtac in [27], Hui and Devetsikiotis in [28], Tantra, Foh, and Mnaouer in [29], Xu, Wang and Hassanein in [30], and Kong, Tsang, Bensaou, and Gao in [31]. But the most accurate model by far was that published by Robinson and Randhawa in [3] due to their correct handling of the delicate different-AIFS-period issue. Our improvement was to alter the already existing mathematical model in [3] to fit the latest changes in the 802.1 le standard under study by the TGe. Robinson and Randhawa have put together a robust mathematical model for 802.lie WLANs, but the model has included misinterpretations of details in the 802.lie specification, which has skewed the results. To set things aright, we reconstructed the model with the right assumptions. In [32], Zhao et al. described a distributed scheme to adaptively change the CW Pa-rameters in order to increase the throughput. They used statistics recorded by the wireless network card to update their probability variables. According to some rules, these variables are used to update the CW Parameters following a mapping function that they derived from simulations. Using the mapping function, they get a Target CWMIN[1], which the current CWMIN[1] converges to by using an adaptive step size. Chapter 2. Overview of Wireless Local Area Networks 20 In [33], Cali, Conti and Gregori used a mathematical model that is very similar to Bianchi's model to derive the optimum C W Parameters for a 802.11 congested W L A N . The scheme is again distributed, and it is used for ad-hoc networks, where each station has no complete knowledge of the network. Stations gather statistics from successful and collided transmissions to have a clearer view of the network, and depending on these statis-tics, the new optimal C W Parameters are calculated. Instead of differentiating the original equation by the C W Parameters, the authors approximated the model with a simplified one, and then differentiated it to get the near-optimum C W values. In [34], Romdhani et al. have written a new algorithm to change the C W parameters. CW\iiN[i] and CWMAX[1] are left constant, but CW[i] is not reset to CWMiN[i] after each successful transmission but is reset adaptively to a different value. Similarly, after each failed transmission, the CW[i] is not doubled, but multiplied by a different factor for each priority. In [35], Dong et al. derived a new scheme to reach the theoretical capacity of the network by creating a Superframe. By adapting the M A C to change the DCF and PCF intervals, the system performs optimally for any kind of traffic demands. Their study is very similar to ours in the sense that the M A C changes the Superframe values to follow the highest of three overlapping curves (Refer to Figures 6 and 8 in [35], and Figure 6.12 in this study). The proposals in [32], [34], [33], and [35] differ from our algorithms because these schemes were developed for ad-hoc networks. Furthermore, the method reported in [33] Chapter 2. Overview of Wireless Local Area Networks 21 was derived for the IEEE 802.11 standard. The algorithm proposed in [34] keeps the CWMIN[1] and CWMAX[1] constant, and changes only the way CW[i] is reset. The study in [32] is the closest to ours, but instead of using a mathematical model, it has a mapping function derived from heavy simulations to get the Target C W as a function of the proba-bility of collision. The approach in [35] uses different network parameters for optimization which are the DCF and PCF intervals. Our Throughput Improvement Algorithms are based on the same fundamental concept of using adaptive Contention Window size control for maximizing the throughput in a saturated 802.1 le W L A N . The Contention Window Parameters (CW) consist of two pa-rameters: C W M I N and C W M A X . Our improvement over other available algorithms was the amount of Saturation Through-put added to the W L A N . Three different algorithms have been developed for handling the optimal Contention Window parameters problem. In all three algorithms, the Access Point (AP) takes the responsibility of collecting measurements, computing average throughputs, calculating Contention Window parameters, and then broadcasting the results back to the stations in the network, using Beacon frames. 2.6 The Simulator A detailed simulator has been developed for the purpose of modeling wireless LANs. The simulator was originally developed in OPNET, then migrated to C to improve flexi-bility and reduce long simulation times. A version of the software has been also evolved Chapter 2. Overview of Wireless Local Area Networks 22 0.032 -0.03 -0.028 -0.026 -0.024 -| 0.022 -0.02 -0.018 • 0.016 -0.014 -0.012 L 0 Figure 2.4: Exponential Distribution Error into a working M A C stack and ported to run on VxWorks. The simulator used in this the-sis inherits most of its functions from the M A C stack, but has a discrete-event simulator representing the PHY layer. On the other hand, it was worth noting that generating a Random Variable (R.V.) from an Exponential Distribution introduced an error to our simulations. The rand() function of the C language was used to generate an R.V. with a Uniform Distribution. This R.V. was then passed to another function that produced an Exponential Distribution out of a Uniform one. The inter-arrival times are sampled from this distribution, with an integer number of slots. The operation of discretization, along with the imperfection of the rand() function, introduced an error that is plainly visible in Figure 2.4. The dotted-line plot is the exponential distribution generated by the simulator which starts at probability 0.032, the continuous-line plot is an ideal exponential distribution that starts at 0.03. The A parameter Exponent ia l Distribution : Measured and Ideal T 1 1 1— i i — Exponent ia l Ideal Exponent ia l J i i i i i * r > V 1 5 10 15 20 25 30 slots Chapter 2 . Overview of Wireless Local Area Networks 23 in both distributions is equal to 0.03. Such a small difference of 0.002 will cause inter-arrival times to be closer than usual, or lumped together. Because of this, in the finite-load models, the simulation will have slightly higher values for the mean service times, the probability of collision, and the utilization probability, than the mathematical models, and that is especially visible when the load approaches the saturation threshold, i.e. the network approaches the saturation case. 2.7 Concluding Remarks In this chapter, we introduced the technology and infrastructure that WLANs rely on to operate properly. We also surveyed the finite-load models, saturation throughput mod-els, and adaptive algorithms for throughput enhancement. We also introduced our own improvements to these models and algorithms. Our aim for creating these models was to improve accuracy, and as the results will show in the end of each chapter, we met that goal. Chapter 3 An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 3.1 Introduction Today's world of technology has seen a proliferation of wireless networks. The ac-cess protocol upon which these wireless networks rely to transmit and receive is called C S M A / C A (Carrier Sense Multiple Access with Collision Avoidance). This protocol has been created to make use of the medium that all wireless transceivers share. The IEEE 802.11 standard [6] defines two modes of medium access for WLANs: Point Coordination Function, PCF, and Distributed Coordination Function, DCF. An Access Point uses PCF to schedule transmissions of real-time traffic and important data in a collision-free envi-ronment. DCF is used when all stations are contending for the medium using their backoff processes, which is the case in this study. The backoff process uses a backoff counter that is chosen uniformly from a contention window, then decremented with every idle slot, and 24 Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 25 frozen when the medium gets busy. When the timer reaches zero, and if the medium is still idle, the station begins its transmission. Good modeling of this backoff process is key to constructing an accurate model. In this chapter, we derive an accurate finite-load analytical model for IEEE 802.11 WLANs and substantiate the validity of the model by comparing it to results obtained from a very realistic W L A N simulator. Our approach is based on combining two queuing models. The first model represents each station (or node) in the network as an M / G / l queue (single station queue), while the second models the wireless network as an M / G / l queue (wireless medium queue). The wireless medium queue has a total rate of NA , where /V is the number of stations and A is the incoming traffic rate per station. In the second model, the network is considered to be the queuing system, with the frames from all the stations as its input. We will show that the combined model provides a powerful analytical tool for estimating the performance of the individual stations and the entire W L A N (wireless channel). For example, the model can be used to determine what traffic load levels from the stations will cause the network to saturate. Also, when the stations generate different loads (i.e. they have different A's), an individual node can not saturate before the wireless network sat-urates. Our methodology leads to closed-form equations for the service-time distribution and other related steady state probabilities. The reader can refer to Section 2.1 for an overview of the underlying technology, and to Section 2.4 to know more about related work on finite-load models. Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 26 Application Transport Network Figure 3.1: Tagged Node Queuing Model 3.2 System Model and Assumptions We have based our finite-load analysis on an approach that requires'the interaction be-tween two distinct queuing models, one representing the tagged node (or user) view and the other representing the whole network (or W L A N medium) view. In the former case, the node is a special wireless station which is mathematically separated from the network by modeling other nodes' interactions, such as collisions and frame transmissions, as a cu-mulative delay in the service time of the frame ready for transmission in the tagged node. The tagged node server essentially models the processing done at the IEEE 802.11 M A C and PHY layers (see Figure 3.1). The tagged node queuing model is logically divided into two parts: the Wireless Node Modeling Framework which supplies averages such as the average service time and the probability of collision, and the Node Queuing Model which uses these averages to output final quantities such as average waiting time and average queue length. This is illustruted in Figure 3.3 by the upper two blocks. Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 27 Figure 3.2: Network Queuing Model By contrast, the whole network model has the shared wireless L A N medium as the server (see Figure 3.2). In a manner that is similar to the tagged node queuing model, the wireless medium queuing model is logically divided into two parts: the Wireless Medium Modeling Framework which supplies key averages, and the Wireless Medium Queuing Model which uses these averages. This is illustrated in Figure 3.3 by the lower two blocks. Figure 3.3 also shows the interaction between the two queuing models, and represents the general architecture of our Enhanced Finite Load (EFL) model. As a result of this logical partitioning, our analysis leads to a set of non-linear equations (Wireless Node Modeling Framework and Wireless Medium Modeling Framework) that we solve to derive the steady-state probabilities which are then applied to M / G / l queuing models for the tagged node and the whole network (Node Queuing Model and Wireless Medium Queuing Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 28 Model). In congruence with similar analysis in the literature, we will make the following sim-plifying assumptions. We assume all stations, or nodes, are within each others reach and there are no hidden terminal problems. We also ignore the effects of bit-errors due to noise. Therefore, transmitted frames are lost only as a result of collisions caused by other simul-taneous transmissions. This also implies that each node has an infinite buffer, which, with today's buffer sizes, is almost realistic. We assume that the packets/frames arrive to the buffer according to a Poisson process (unless stated otherwise) with rate A, and are queued in a FIFO manner. In addition, after transmission and successful reception, the frames are destroyed on the receiver's side and do not enter any queue again. We also assume constant collision probability p for a given set of input parameters. 3.3 Basic Analysis The conditional probability of collision p in a finite-load (i.e. non-saturated) wireless network of N nodes has already been established in [9], as follows: p= l-P[NT]N~l (3.1) where P[NT] is the probability that a node is not transmitting in a given idle slot. The intuition behind calculating p as above is that P[NT]N~l is the probability that none of the other N- 1 stations are transmitting during a time slot, and 1 - PINT^'1 is the probability that one or more of the non-tagged nodes are transmitting in the current time slot. Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 29 Intermediate Values: Average Service Time, Probability of Collision, etc.. Inputs: Load, DCF Protocol Parameters, etc... Wireless Node Modeling Framework (Supplies the Node Queuing Model with accurate means and distributions) HUtilizationH to Node Queuing Model Outputs: Waiting Time, Queue Length, etc -Probability of Busy Medium Wireless Medium Modeling Framework HO Wireless Medium Queuing Model Figure 3.3: Finite Load Model Architecture Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 30 The probability P[NT] can be calculated as follows: P[NT] = P[NT\QE]P[QE] + P[NT\QNE]P[QNE] = l - ( l - p ) + ( l - r P b a c k o f f ) . p (3-2) = 1 -pTPbackoff where P[QE] denotes the probability that the tagged node queue is empty, P[QNE] is the probability that the node's queue is non-empty, and p = A/fi . Note that P[NT\QNE] is expressed as the complement of the product ( T ? T A C K O F F ) where r is the probability of transmission during a given time slot and Pbackotr is the probability that a frame arrives from higher layers then waits through the backoff process in the node's queue. Therefore, T-Pbackoff represents the probability of transmission given that the frame goes through a backoff process. On the other hand, if a frame finds the system empty and the medium idle, then it gets transmitted directly without going through the backoff process. Let Wp be the average backoff counter value used by the backoff process for every transmission, or retransmission. The backoff process will virtually draw a number between 1 and 2 Wp after a successful transmission (or a collision) occurs. If the node has a non-empty queue, it should transmit during every idle slot with a probability r . This forms a Geometric Distribution, where the probability of success is T and the probability of failure is 1 - r . The first moment of this distribution represents the period within which the node transmits, which is Wp . The expression of the mean of this Geometric distribution is: Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 31 which results in the following expression for r l + Wp (3.4) Let Iw be the average backoff window size when a succesful transmission occurs given a collision probability p. Then, Iw = CWmin{\ -p) + 2p(\- p)CWmin + 4p2(l - p)CWmin + .:. + (IpT^CWmin (3.5) = CWmin m-2 (\-P)J](2p)k + (2pr-1 k=0 and, Wp = IJ2 (3.6) The variable m is the maximum number of retransmissions. We assume that 2mCWmin is equal or less than CWmax, otherwise the previous equation can be easily changed to accomodate this. On the other hand, from the network model point of view, it is more accurate to calculate an average backoff counter value, we call it W , that includes direct transmissions in addition to transmission following a backoff period, such that W = Pbackoff • IJ2 = P b a c k o f f • Wp (3.7) Note that for the purpose of computing the probability of collision p, the expression derived for Wp excludes direct frame transmissions (i.e. without backoff). In general, a very small proportion of direct transmissions will collide, with a rate much lower than p. Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 32 For this reason, the expression of the collision probability p would prove non-accurate if we used W instead of Wp. The backoff probability, ^backoff, can be computed from the probabilities for the busy and idle periods. Let /"busy be the probability that the medium is busy in a given time slot and let P i d i e be the complement of Pbusy Then the portion of the transmitted frames that will go through a backoff process is given by: Pbackoff — (Pbusy+pPidle) (3-8) In other words, the probability Pbackoff represents the portion of the frames that will go through a backoff period because either the medium was busy (with probability Pbusy). or because the node had some frames buffered ahead of the incoming frames while the medium is idle (p Pidie)- The complement of Pbackofr is the portion of the frames that will be transmitted directly without going through a backoff process, because the node buffers are empty and the medium is idle. Note that W < Wp, because W is the average backoff window when direct transmission are also included. From the network model point of view, P b a c koff contributes to the accu-racy of calculating the time slots for the average network service time ( l / / i „ e , ) , hence its inclusion in computing W but not Wp . Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 33 3.4 The Tagged Node Queuing Model The first queuing model we will present is that of the Tagged Node. Because the service time distribution for this model is not Markovian, we use an M / G / l queuing model. This section's model considers the node as the server. All other messages, transmissions, and interference from other nodes sharing the wireless medium will be modeled as delays in the service time. 3.4.1 Service Time Estimation In this section, we will derive a compound equation for the expected service-time for the Tagged Node server, using the basic queuing relation p = A/p. Essentially, the server represents the processing of the M A C and physical layers of an 802.11 station, and the server queue contains frames received from these higher layers. The service time is defined by the frame length distribution, the backoff process, the number of stations (transmissions and collisions of other nodes), and the collision probability p. We start by defining the transmission cycle as the time it takes a node to transmit a frame, whether this attempt results in a collision or in a successful attempt. The total time it takes a node to transmit a frame successfully may consist of several cycles each ending in a collision except for the last one. The expected number of cycles a node takes to transmit a frame successfully is (l-p) 1 + 2p + 3p2 + ...\ + mpm~l = l + p + p2 + .. + pm~1 = £ pk, 1 ' k=0 with m being the maximum number of retransmissions. Therefore, the expected number of transmission cycles that end in collisions is Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 34 m - l CycleCx = J]pk (3.9) In each transmission cycle, the node counts down backoff slots, but may be interrupted by either collisions or successful transmissions from other nodes, and finally ends the cycle either with a collision or a successful transmission of its own. The service time can be expressed in terms of its component delays as follows: - = nodeCx + otherCx + backoff + nodeTx + other^x (3.10) Thus, the service time is comprised of: • the accumulated backoff through the expected number of cycles (say C cycles), • the accumulated successful transmissions from other stations (otherTx) in C cycles, • the accumulated collisions (otherCx) from other stations in C cycles, • the accumulated collisions made by the tagged node (nodeCt) throughout C cycles, • the successful transmission (node7Y) or discarding of the frame by the tagged node when the maximum number of retransmissions is exceeded. Now, let the probability Px denote the portion of frames that arrive to an empty queue when the medium is busy. These frames will experience only a portion of a transmission from other stations, an average period of TJ2 in case of a successful transmission, and TJ2 in case of a collision. Here, 7^ is the time it takes to complete a successful transmission, Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 35 including the PHY headers overhead, RTS, CTS, and A C K frames, and finally the frame payload. Tc is the time it takes to detect a collision, including PHY headers, RTS frame, and then a deference period. Then, The factor p + (1 - p ) ^ is empirically included to adjust the impact of P b u s y from the point of view of the tagged node. When the node utilization p is small and the Tagged Node is empty, then the real contributors to Pbusy arc the other N - l nodes. But as p gets larger, this equation becomes non-linear because of the inter-dependence between p and When the queue utilization p is small and the Tagged Queue is empty, then the real contributors to Pbusy are the other N-l queue. But as p gets larger, this equation becomes non-linear because of the inter-dependence between p and Pbusy Given the fairness of the backoff process over a long time period, each station will have a chance to transmit given that its buffers are not empty. In this case, the number of successful transmissions (P0therTx) and collisions (P0therCx) arising from other nodes during the service time of a single frame are given by the following probabilities, />, = ( l - p ) . P b u s y p + ( l - p ) N-l (3.11) PotherT* = P(N- 1) (3.12) ^otherC* = P(N ~ 1) Po (3.13) O Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 36 The probability p0 represents the portion of transmissions from other nodes that results in collisions. Equation 3.12 is an expression of the complement of the portion of frames that get transmitted successfully given that there is a transmission, derived from the fol-lowing relations: To illustrate the derivation of pa, we will give a small example. Assume a W L A N with two nodes A and B. A and B have both managed to transmit 9 frames successfully. In their tenth attempt, node A s transmission collided with node B's transmission. From the node's point of view, the probability of collision is 10%. However, from the system's point of view, the wireless medium has witnessed 18 successful transmissions, and only one collision. Therefore, the probability of collision of nodes from an outsider's point of view is 5.26%. For simplicity's sake, we neglect the portion of collisions that are caused by 3 or more same-time transmissions because of their very low probability of occurrence. This example illustrates the derivation of p0 which equals othersS um Therefore, P Po = 2(\-p) + p (3.14) P 2-p Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 37 Now, the main quantities of the service time (I/p.) can be derived directly: nodeCx = CycleCx.Tc (3.15) otherCx = (PotherCx - J ° P i )TC (3.16) 2(1 - p0) Backoff = W + CycleCx.Wp (3.17) node7x = (1 - pm)Ts (3.18) other7x = (PothaTx - ^)TS (3.19) A detailed example of p with numerical results will be given in Section 3.7.2. 3.4.2 Service Time Distribution (Tagged Node Queuing Model) We model the service time probability distribution function (PDF), b(t), as a shifted negative exponential distribution (n.e.d.), where the amount of shift is equal to the average frame length Ts, as follows: b{t)=pp.e-^'-^.u(t-Ts) (3.20) Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 38 True pdf vs. P r o p o s e d pdf •.02 -•.018 -20 40 60 SO 100 120 140 160 160 200 220 glotg Figure 3.4: Service Time Distribution Approximation for Typical p The shift happens because any frame can not be discarded from the buffer (whether it be the result of a successful transmission or the exceeding of the maximum retransmissions threshold) unless it undergoes at least one transmission. Therefore, the service time of any frame can not be less than Ts, which yields a non-Markovian service time distribution. The function u(t - Ts) is the Heaviside (or step) function shifted by Ts, and pp is the constant of the n.e.d. before shifting, expressed as a function of Ts and the average service time, p, as follows, „ . ( H -This distribution captures the nature of the true service time PDF computed as the cas-caded convolution of the PDFs of the cumulative backoff-counter distribution, other nodes' transmission time distribution and the node's transmission time distribution. The resulting PDF will typically have the shape of a shifted negative exponential distribution. To validate this observation, Figures 3.4 and 3.5 show plots of the true service time PDF, obtained by Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 39 X IQ"3 True pdf vs. P r o p o s e d pdf -2 --4 -_j 1 1 1 1 i 1 i i i 100 150 200 250 300 350 400 450 500 550 s lo ts Figure 3.5: Service Time Distribution Approximation for Large p simulation, versus the n.e.d. in our model, for a typical value of the probability of collision and for an unsually large value of the probability of collision, respectively. Few papers have tried to derive the true service time distribution, and none, as yet, had it derived completely. In general, the concept is simple: the service time distribution could be derived by convolving the distributions of the five components of the service time. But the final expression is too complex to be derived, or to be manipulated in a mathematical derivation (exponentially increasing time to solve system in MATLAB). And even if the final expression is derived in the s-domain or the z-domain, it is impossibly complex to convert back to the time-domain. It was for this reason that we preferred to model the service time with a shifted exponential distribution. One key observation is that the variance of the actual service time is larger than that of the simplified distribution we proposed, although the mean is the same. To compensate for the error introduced, we apply a variance of V = 2V^. Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 40 Applying the Laplace Transform to b(t), we obtain B(s) = f e~s'b(t)dt = f e-s,p.p.e-»"(t-T°)u(t - Ts)dt = ^ — (3.22) J J MP + S o From which we can derive the PGF of the new service time PDF, as follows -M.i-z).Tc. <Kz) = B [A(l - z)] = — - (3.23) A(l-z) + up Let Q(z) be the PGF of the steady state probability, , the latter indicating that there are k frames in the node queue. Considering that we are using Poisson arrivals, we have .^q-px.-^ <i-jxi-»™> <P(Z)-Z e*Ts(z-l)_z 1 + A ( l _ Z ) | Now taking moments of Q(z) will give us the steady-state probabilities (the queue length distribution), as follows: (G(z))*U " k = it! ( 3 - 2 5 ) Another quantity of interest is the average queue size Nq , p 2 + 2A2VU N<'" + ^a^f (3'26) The quantity is the variance of the service time distribution, which is defined as Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 41 follows oo oo b(t)(t - -fdt = fnPe-^('-T°Xt - -fdt H J V Ts (3.27) 1 3.4.3 Throughput and Delay The throughput of the network, also called utilization, is defined as the number of data bytes that are successfully transmitted per second. Throughput is an important criterion in some situations; it allows us to measure the network responsiveness to the load it is subject to. In the case of networks with non-saturated finite-load networks, calculating throughput is trivial since it is essentially equal to the input rate. On the other hand, delay computation is more consequential, since delay tends to in-crease dramatically as the network moves towards saturation. In queuing theory, delay is defined as the waiting time Tq of a queued frame from the instant it enters the queue until the start of service. Similar to average queue size Nq , the average waiting time Tq is one of the Pollaczek-Khintchine formulae, expressed as follows 1 \p2 + 2A2V„ A[ 2(1 -p) _ (3.28) In our wireless networks, delay is defined as the waiting time Wq of a frame from the instant that it enters the queue until the start of being successfully transmitted. It follows Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 42 then that the waiting time of a frame Wq is equal to Tq plus the service time l/fi, minus the time it takes to successfully transmit a frame, Ts. Therefore the average waiting time, or delay, has the following expression The next and important step of our analysis is to derive formulas for the important prob-abilities, P i d ie and Fbusy For that, we revert to the whole-network queuing model. 3.4.4 Bursty Source In the case where we need to simulate a Bursty Source in each node, we can simplify the analysis and still get good approximations by using an M / G / l queuing model with batch arrivals. The batches inter-arrival time is distributed exponentially with a rate of At,, and each batch has an arbitrary number of frames, with an average of B frames/batch and a variance of cr2. The E F L model can be used as it is, and all of the above analysis is still valid with the M / G / l queue with batch arrivals, except that now A is equal to BAb. Also, the expressions of the waiting time, and of the average queue size change. The following is the waiting time expression: Wq = Tq + - - T s (3.29) ' Batch _ 1 ~ AbB2 1 + Bo-2 + o-2lfi2\ a2 JH (3.30) 2/i 2(l-p) The average queue size can be derived by using Little's Law Nq3a,ch = ATq Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 43 3.5 Whole Network Queuing Model In the Whole Network Queuing model, the shared wireless medium is considered as the server. The service time is modeled as a shifted exponential distribution. 3.5.1 Estimation of the Network Service Time and Utilization Rate The average service time of this model l/finet has three components: the average time of all backoff processes for all stations (nodes), the average frame length Ts expressed in time slots, and the delay overhead introduced by collisions. The first of these three components is the average time it takes for the first backoff-counter to fire from the group of stations present in the network. The expression for this can be derived from probability theory and combinatorics, as in [3], as follows: where N is the number of stations in the network, and j is the minimum number of time slots elapsed since the medium became idle until the first backoff-counter (among N coun-PNj = P j slots min (backoff_counter(i)) (3.31) ters) fires. Let T„et be the expected value of the random variable P*J, i.e. (3.32) Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 44 Then, the expression for the average network service time is: — = TNml + Ts + p(TNnet + Tc) (3.33) Pnet and following a derivation process similar to that of the tagged node model, we have Pnetp = ~ — (3-34) — ~TS Pnet = ( 3 . 3 5 ) Pnet The probability distribution function of the network service time is: Ket(t) = PneW.e-^('-Ts).u(t - Ts) (3.36) This leads to an expression similar to that of the tagged node model but with different parameters: ( l _ ^ ) ( l _ z ) e T O - i ) Unet e*NTs(z-l) - ZU + JN_fl-z)] P-nelp J Qne,(z) - r , TTT~. TT (3-37) y-nelp Taking the moments of Qne,(z) , we get the steady-state probabilities of the network nnetk, indicating that there are k frames in the network. {Qne,{z)y *netk = . , lz=° (3.38) Note that in the network model, k frames can be queued all in one node or in up to k different nodes, and k can be 0 indicating an empty network. This network model is Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 45 particularly useful for estimating network wide performance such as maximum throughput, and the impact of the combined load from all stations results on throughput, average delay and collision probability. 3.5.2 Estimation of PIDLE and PBUSY In this section, we complete our analytical model by deriving formulas for P i d i e and Pbusy Recall that these two important probabilities appear in the derivation of several key parameters such as the collision probability p and average backoff window W . Let us define a service cycle as the time period that begins with the start of the wireless medium turning idle and ending with a successful transmission. The average service cycle time is equal to l/pne,, and it includes the time for resuming backoff counters for an average number of collisions. The number of idle slots is then the weighted sum of the probability of i active stations at a given slot multiplied by the expected value of the first backoff counter to fire a count-down given i active nodes. We can approximate this by having the weighted sum of the nnetk s multiplied by the expected value of the first backoff counter to fire (Tket). This is not absolutely accurate since nnetk s do not represent the probability of i active stations, but it represents the steady state probabilities of the network queue. The network queue could have two or more frames belonging to the same node. But still this approximation yields an accurate enough value (with an average error value of 1%). So the equation for the average number of idle slots Is is: (3.39) k=\ k=\ Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 46 Then with this value, we derive the ratio of idle slots in each cycle: Rs = '- (3.40) Is + Ts + p T c and we have, Pidle = 1 - Pnel + Pnet • R s = I ~ PnetiX ~ Rs) (3.41) Pbusy - 1 _ Pidle (3.42) 3.6 Multi-Load and Multi-Rate Wireless LANs 3.6.1 M u l t i - L o a d Wireless L A N s In this section, we will describe how to alter the model in order to accomodate a W L A N with stations having different loads. Nodes having different loads will lead us to the con-clusion that each node j in the W L A N has its own set of variables. Therefore, the index j will indicate that this variable is specific to node j. We will derive again the equations that are subject to change, and unless stated otherwise, the rest of the equations remain unchanged except for the addition of the index j. In the case of different loads, the probability of no transmission P [ N T ] becomes different for each node, therefore: P[NT]j=l-pJTjPii (3.43) Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 47 and Pj=l - fl P[NT]j (3.44) It follows then that the equations of T,-, ii, WJp, Wj, Pjbackoff, etc..., use the variables pj, Pj, etc that are specific to node j. For the average service time estimation, several equations have to be changed. The number of successful transmissions and collisions from other stations P0ther7* and P0therCx become PL*r, = Z PJ ( 3 - 4 5 ) i'=l, i*j and PothtiCxi = — P J ^3'46^ 1 - Po i= l,i*y The probability of collisions arising from other stations pQ becomes N 1 Pj Pi ^ h v — (3-47) 2(TV -1) - 2 P j .i=l,i*7 These changes will enable us to derive the Uj and p y for each node. On the other hand, it was worth noting that having a different pj for each node means that we applied the Node Queuing Model N times for each node in our calculations, while still applying the Wireless Medium Queueing Model only once for the whole wireless network. Therefore, Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 48 q *i p) + 2A*VZ 2(1 -pj) (3.48) The same can be done for the average queue length. The last change to be made is to replace the W in Equation 3.31 to get P'J with the average of all average backoff counters WAv- The equation in question becomes Pf = P j slots = min (backofLcounter(O) =z k=\ N k 1 \k(2WAv-pN-k 2W. Av 2WAv (3.49) with N wAv = 1=1 N (3.50) 3.6.2 Multi-Rate Wireless LANs It is interesting to note that wireless LANs with nodes having different physical rates (i.e. different bandwidth) have basically the same behavior as single-rate WLANs. The backoff process in the M A C is independent from the PHY rate, and therefore wireless nodes are synchronized to slot boundaries by pre-defined parameters relating to the under-lying technology in operation. The only quantity that change in multi-rate WLANs is the success duration Ts, which becomes specific to each node (TJS). Therefore, a logic similar Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 49 to the one in Section 3.6.1 can be used to derive the now different pj and pj quantities. 3.7 Simulation versus Numerical Results In this section, we compare numerical results obtained from the analytical model with results obtained from a simulator. We have implemented a detailed simulator based on the IEEE 802.11 standard and implementation notes. For further validation, we have compared our results with commercial simulators such as OPNET to ensure accuracy. Furthermore, we have verified that the simulator operating in saturation matches Bianchi's psa, and other quantities to a high level of accuracy (confidence interval above 95%) [9]. In our constructed system, the probability of collision p parameter is the most sensitive to the choice of random seeds in the initialization process. The main reason is that p is derived from P[NT] raised to the power N - l (see equation 3.1) where N is the number of stations in the network. Therefore, small differences between the simulated P[NT] and the analytical P[NT], amplify the corresponding difference between the simulated p and analytical p. In real systems, the probability p is typically in the range [0.01, 0.2]. Except for the collision probability p, we found all other quantities to be stable, and give very accurate results when compared to simulation. Most of the calculated results and simulations overlap with exact values for large spans of A, representing the input rate. For large values of A , the network utilization p approaches 1 and the laws of queuing theory do not hold accurately. Only in this high utilization range do we observe the largest divergence between our analytical model and simulation results. Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 50 3.7.1 Numerical Example of the Service Time The following example shows how good each component of p is represented in our model. The example shown in Table 3.1 if for a network with 20 stations or nodes, where C W M I N is equal to 32, and the load per-station is equal to 22 frames/sec. In combination with these values, setting p to equal 0.2 causes the maximum margin of error between simulation and our model, especially in the collision probability p. In Table 3.1, the E F L (Enhanced Finite Load ) model refers to the model developed in this chapter, which is compared to the model given in [14]. A l l the quantities in the table are given in terms of time-slot units. See Table 3.2 for details. Parameter Simulation EFL Model Tickoo & Sikdar [14] nodeCx 4.232877 4.1656 9.8937 otherC* 8.668607 6.8908 87.7486 backoff 21.841324 19.9435 25.9287 noder* 94.978311 94.9540 95 otherr* 326.374658 340.2596 842.5684 Service Time (1/u) 453.704449 449.8883 1061.1 Collision probability p 0.1480 0.1483 0.2919 Utilization p 0.199770 0.2051 0.4669 Table 3.1: Numerical Example of the components of the Service Time 3.7.2 Results In this section, we present our simulation and model results. The W L A N is assumed to operate in DCF with no "hidden station" problems. Whether the W L A N operates in ad-hoc or infrastructure mode does not matter in our scenarios because we assume all the stations are in each other's range. Figures 3.6 to 3.8 show plots of numerical results from our E F L Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 51 analytical model compared to simulations, to results from the analytical model in [14], and to results from a de-coupled Tagged Node Queuing Model (i.e. Node Queuing Model only, without the help of a Wireless Medium Queueing Model and its feedback Pbusy)- All plots and simulations used the same parameter set given in Table 3.2. Figure 3.6 plots the utilization p versus input load. Figure 3.7 plots the collision probability p versus input load, with the saturation collision probability derived from [9] as reference. We can see that as p —> 1, our collision probability converges to Bianchi's saturation collision probability. Figure 3.8 plots the average service time l/p. versus input load. Figure 3.9 plots the average waiting time, or delay, versus input load. All plots cover three W L A N sizes: 4 stations, 12 stations, and 20 stations. Al l nodes have the same input rate/load A , and the data frame payload size is fixed at 2304 bytes, whihc is the M T U for a W L A N . The parameters Tc and Ts have been calculated as the approximate sum of RTS, CTS, frame size, physical and M A C headers, A C K , and DIFS. For simplicity, we have quantized the frame lengths to align with slot boundaries. The error due to this quantization is negligible especially considering that frame length is much larger than the slot size. Bandwidth 11 Mbps Slot Time 20 microseconds CW ¥ Y mm 32 Data Payload 2304 bytes CWmax 1024 T 24 slots Retransmissions 4 T •*• s 95 slots PHY Header 192 bits MAC Header 272 bits RTS Size 160 bits CTS Size 112 bits ACK Size 112 bits DIFS Time 50 microseconds Table 3.2: Simulation and Mathematical Models Parameters Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 52 The figures show clearly that our E F L model is very accurate especially when the num-ber of stations in the network is less than 20, which is typically the case for real WLANs. The accuracy degrades slightly as the number of nodes increases, but the model is still highly precise, especially for the key quantities: p (utilization), and l/p (service time). In Figures 3.6 to 3.9, we compare our results against the model proposed by Tickoo and Sikdar [14]. Their analysis, although considers the node queuing model only, actually produces results with the same trend as our results, albeit with less accuracy. In Figure 3.6, for example, our model and the one in [14] follow the same trend as the load is increased. However, the model in [14] overestimates the utilization by 20% for 4 stations (especially at higher loads, e.g. 90 frames/sec), and by more than 50% for 20 stations when the load is above 20 frames/sec. In all cases, our model matches the simulation results to within a maximum of 5%. Similar observations can be deduced from graphs 3.7, 3.8, and 3.9. In the Figure 3.10, we have plotted the waiting time Tq for a W L A N with batch arrivals for 4 stations. Now, we compare the E F L model results with simulations results for a Multi-Load W L A N in which the network has 4 stations (nodes), each having a different load. In this setup, the load of node A varies while the load of the other nodes remains constant. Specifically, the load on node B, C, and D is 70, 50 and 120 frames/sec, respectively. The rest of the parameters are the same as in Table 3.2. In Figure 3.11, we plot the utilization Pj, the probability of collision pj, and the average service time V/pj for all 4 stations as the load on node A increases. Figure 3.12 shows the average waiting-time for each of the nodes. Chapter 3. An Enhanced Finite-Load Model for IEEE 802:11 Wireless LANs 53 It is interesting to note that the utilization rate of the wireless medium was plotted in the first plot of Figure 3.11 to support our claim that a node can not saturate before the W L A N saturates. This is harder to show when simulating a homogeneous-load W L A N . 3.8 Conclusion In this chapter, we have developed a novel finite-load queuing model for more accurate analysis of 802.11 WLANs. When compared to other models in the literature, our model provides substantially more accurate results that closely match those obtained from highly detailed W L A N simulators. The accuracy of our model is attributed mainly to the use of a coupled queuing model which proved to be very useful for studying the effect of varying parameters on the micro-scale (station level) and on the macro-scale (network level). We have derived closed form equations for the Q(z) functions representing the steady-state probabilities. Our model takes for input the load, the number of stations, the contention window parameters, the bandwidth, and the frame size, and generates all the average and steady state probabilities. The proposed model can be easily extended to get the throughput and utilization of the network. The model is very flexible and allows also for easily changing the input traffic model from Poisson to other useful distributions by modifying the expression for Q(z), and applying a G/G/ l queuing model. Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 54 ro vs. load with 04 stations —* Enhanced FL Queueing Model —i Tickoo and Sikdar De-coupled Node Queuing Model O Simulation f fl 20 40 60. . 80 load frames/sec 100 120 140 ro vs. load with 12 stations —* Enhanced FL Queueing Model —I Tickoo and Sikdar —De-coupled Node Queuing Model O Simulation Figure 3.6: Utilization vs. load for WLAN with 4, 12, and 20 stations Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 55 Q.1B , p vs. load with 04 stations 0.14 0.12 0.1 0.08 0.06 • .04 0.02 Bianchi Satuartion Collision Probability —* Enhanced FL Queueing Model —I Tickoo and Sikdar -A—De-coupled Node Queuing Model O Simulation 60 80 load frames/sec 0.35 0.3 0.25 0.2 0.15 0.1 0.05 p vs. load with 12 stations Bianchi Satuartion Collision Probability •* Enhanced FL Queueing Model —I Tickoo and Sikdar De-coupled Node Queuing Model O Simulation 20 25 30 load frames/sec p vs. load with 20 stations 0.35 o- 0.3 2 0 2 5 O C L I 0 2 S 0.15 0.1 0.05 -Bianchi Satuartion Collision Probability -Enhanced FL Queueing Model -Tickoo and Sikdar —De-coupled Node Queuing Model O Simulation 10 15 load frames/sec Figure 3.7: Collision probability,/? vs. load for WLAN with 4, 12, and 20 stations Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 56 1/mu vs. toad with 04 stations 450 400 "5 1 300 ni e i - 250 a> o <*> 200 150 —* Enhanced FL Queueing Model —H—Tickoo and Sikdar A De-coupled Node Queuing Model O Simulation 4 l -60 80 load frames/sec 120 140 1/mu vs. load with 12 stations 1400 1200 1000 —* Enhanced FL Queueing Model —I Tickoo and Sikdar — De-coupled Node Queuing Model O Simulation 20 25 30 load frames/sec 1/mu vs. load with 20 stations 2500 2000 1500 ?> 1000 500 —* Enhanced FL Queueing Model —I Tickoo and Sikdar -"=<—De-coupled Node Queuing Model O Simulation 10 15 20 load frames/sec 30 Figure 3.8: Service time vs. load for W L A N with 4, 12, and 20 stations Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 57 Wailing Time in Queue vs. load 40 60 80 load frames/sec 120 Figure 3.9: Waiting time T Q VS. load for W L A N with 4, 12, and 20 stations 800 700 600 CO I 500 ? £• 400 a> O 300 200 100 Waiting Time in Queue vs. load with 04 stations - * — E n h a n c e d FL Queueing Model O Simulation 10 15 20 25 30 load batches/sec with 3 frames/batch 35 Figure 3.10: Waiting time T Q VS. load for W L A N with 4 stations with Batch Arrivals Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 58 o vs. load with 04 s la t io S i m of M e d i u m M o d a l of M e d i u m O S i m of A * M o d e l of A * S imu la t i on of B M o d a l of B +• S imu la t i on of C - M o d a l of D " S imu la t i on of C M o d e l of D :k— -0.1 • . • 9 0 .08 0 .07 • .OS 0 .05 0 .04 0. 0 .02 f • .•1 p v s . load with 04 s t a t i o n s i.oaip-O S i m of A - * M o d e l of A S i m u l a t i o n of B ( - M o d e l of B •I- S i m u l a t i o n of C — M o d e l of D x S i m u l a t i o n of C 120 140 160 load f r a m e s / s e c 180 2 0 0 220 2 5 0 JS 2 0 0 g 100 5 0 1 / m u vs . load with 04 s t a t i o n s r?- -J o - + -S i m of A - M o d e l of A S i m u l a t i o n of B —I M o d e l of B 4- S i m u l a t i o n of C - * M o d e l of D * S i m u l a t i o n of C M o d e l of D 8 0 100 120 140 160 load f r a m e s / s e c 180 2 0 0 220 Figure 3.11: Key Quantities vs. load for a Multi-Load WLAN with 4 stations Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 59 Waiting Time in Queue vs. load with 04 stations 200 150 100 50 O Sim of A - * — M o d e l of A + Simulation of B -Model of B + Simulation of C - * — M o d e l of D * Simulation of C Model of D 80 100 120 140 160 180 200 220 load frames/sec Figure 3.12: Waiting time T Q vs. load for a Multi-Load WLAN with 4 stations Chapter 4 A Finite-Load Model for QoS-Enabled IEEE 802.1le WLANs 4.1 Introduction The rapid development of switching architectures, new smart antennas, and robust se-curity, has lead to the wide proliferation of wireless local area networks (WLANs) into the enterprise and consumer markets. Currently, WLANs have become more than just a niche solution of extending the enterprise or institution network to unwired areas. For busi-nesses, WLANs offer true economic advantage by helping enterprises maintain a flexible reusable local wireless networks that can improve employee mobility. Some of the rising application drivers for WLANs are voice/video over W L A N and high bandwidth TCP connections. As it became commonly evident, joining data and mul-timedia traffic in one system has forced us to think about classes of service. The 802.1 le 60 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 61 committee has been formed to address this very issue. However, before main stream IT and VoIP applications migrate to the QoS-enabled wireless LANs, good modeling tools should be available in order to study and enhance the performance of these multimedia QoS-enabled wireless networks. In this chapter, we extend the finite-load model of Chapter 3 to 802.lie WLANs and substantiate the validity of the model by comparing its results to those obtained from a very realistic W L A N simulator. Our approach is based on combining two queuing models. The first model represents each station's queue in the network as an M / G / l queue, while the second models the shared wireless medium, but also as an M / G / l queue (channel queue). The channel queue has a total rate of NA, where N is the total number of queues and A is the incoming traffic rate per queue. In the second model, the network is considered to be the queuing system, with the frames from all the queues as its input. We will show that the combined model provides a powerful analytical tool for estimating the performance of the individual queues and the entire W L A N (wireless channel). For example, the model can be used to determine what traffic load levels from the queues will cause the network to saturate. Also, when the queues generate different loads (i.e. they have different /Ts), an individual queue can not saturate before the wireless network saturates. The reader can refer to Section 2.2 for an overview of the technology used in the 802. l i e M A C , and to Section 2.4 to know more about related work of 802.1 le finite-load models. Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 62 Application Transport Network Figure 4.1: Tagged Node Queuing Model Figure 4.2: Network Queuing Model Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 63 4.2 System Model and Assumptions We have based our finite-load analysis on an approach that requires the interaction be-tween two distinct queuing models, one representing the tagged node (or user) view and the other representing the whole network (or W L A N medium) view. In the former, the node is a special wireless station which is (mathematically) isolated from the network by modeling other nodes' interactions (such as collisions and frame transmissions) as a cu-mulative delay in the service time of the frame ready for transmission in the tagged node. The tagged node server essentially models the processing done at the IEEE 802.11 M A C and PHY layers (see Figure 4.1). By contrast, the whole network model has the shared wireless L A N medium as the server (Figure 4.2). Our analysis leads to a set of non-linear equations that we solve to derive the steady-state probabilities that will be applied to M / G / l queuing models for the tagged node and the whole network. In congruence with similar analysis in the literature, we will make the following sim-plifying assumptions. We assume all stations, or nodes, are within each others reach and there are no hidden terminal problems. We also ignore the effects of bit-errors due to noise. Therefore, transmitted frames are lost only as a result of collisions caused by other simultaneous transmissions. This also implies that each node has an infinite buffer, which, with today's buffer sizes, is almost realistic. We assume that the packets/frames arrive to the buffer according to a Poisson process with rate A, and are queued in a FIFO man-ner. In addition, after transmission and successful reception, the frames are destroyed on Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 64 the receiver's side and do not enter any queue again. We also assume constant collision probability p for a given set of input parameters. 4.3 Basic Analysis IEEE 802.lie standard specifies the use of four distinct queues, one for each access category. To simplify presentation and avoid unnecessary complicated formulas, we will base our analysis on the behavioral study of two queues, labeled A and B. Queue A will be assigned to the higher priority A C while queue B will be assigned to the lower priority AC. We will show in a later section how the model can be easily extended to an arbitrary number of priority queues. Remark on notation: We will refer to priority queues with different expressions. In general, queue A, priority A queue, class A, and class A. queue, all point to the same QoS queue with the highest possible priority. In many cases the expressions for both A C queues are identical, in which case, we will show the derivations for the A queue only, and the expression for queue B will be stated with no further explanation. 4.3.1 Est imat ion of the Col l is ion Probabi l i ty Let P[NTA] be the probability that the A queue, in a finitely-loaded (or non-saturated) wireless network of N nodes (N = NA + NB), is not transmitting in a given idle slot. Then as was established in [14], the probability of no transmission is: Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 65 P[NTA] = P[NTA\QEA]P[QEA] + P[NTA\QNEA]P[QNEA] = 1.(1 -pA)+pA(l - TA. Pbackoff/l) (4.1) — 1 — PA-TA - PbackofiA where P[QEA] denotes the probability that queue A is empty, P[QNEA] is the probability that queue A is non-empty, and pA = AA/uA is the utilization parameter for ACA (Access Category A). Clearly, P[QNEA] = pA and P[QEA] = 1 - pA. Note that P[NTA\QNEA] is expressed as the complement of the product (TA Pbackoff/0, where TA is the probability of frame transmission by queue A during a given time slot and v°back0ffA is the probability that a frame arrives from higher layers then waits through the backoff process in the station's A queue. Therefore, TA P b ackofM represents the probability of transmission given that the frame goes through a backoff process. On the other hand, if an arriving frame finds the queue empty and the medium idle, then it gets transmitted directly without going through the backoff process. The same applies to priority B queue, in which the final expression for P[NTB] is, The backoff probability for ACA, PbackotTA can be computed from the probabilities for the busy and idle periods, using the approach given in Chapter 3. Let Pbusy be the probability that the medium is busy in a given time slot and let Pitne be the complement of Pbusy Then the portion of the transmitted frames that will go through a backoff process is given by: P[NTB] = 1 - pB.TB. Pbackofffi (4.2) Chapter 4. A Finite-Load Model for QoS^Enabled IEEE 802.11e WLANs 66 ^backoff/1 - (Pbusy + PAPidle) (4.3) and for ACB, Pbackoffs - (Pbusy + pBPidle) (4.4) In other words, the probability Fbackoff/i represents the portion of the frames that will go through a backoff period because either the medium was busy (with probability Pbusy), or because the priority A queue had some frames buffered ahead of the incoming frames while the medium is idle (pAPidie)- The complement of PbackoffA is the portion of the frames from queue A that will be transmitted directly without going through a backoff process, because the queue buffers are empty and the medium is idle. 4.3.2 Different A I F S Periods and Slot Occupancy Weight ing Robinson and Randhawa proposed a saturation model for the 802.11 wireless networks that accounts for the different AIFS periods in the backoff process of each priority class [3]. Lower priority queues have larger AIFS periods than higher priority queues. These differences among AIFS periods were modeled by separating the network idle time into distinct contention zones , and therefore distinct collision zones, one for each priority (or access category) level (equations 11-13, in [3]). After the medium becomes idle, and as the time increases in slot number, then the net-work progresses from one contention zone to the other, as lower priority queues are now Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 67 Figure 4.3: Slot Occupancy Markov Chain (taken from [3]) able to backoff and transmit due to the end of their AIFS period. For example, in zone 1 only frames from the A queues can contend for channel. This will continue until the AIFS B timer expires, and frames from the B queues join in the contention for the medium, thus moving the system into contention Zone 2. Every contention zone has its own char-acteristic transmission and collision probabilities. To obtain the final average collision probability (pA or pB), the collision probabilities of the contention zones are weighted by fe„ a discrete probability function, representing Slot Occupancy, and then summed. The slot occupancy p.d.f. bt is modeled as a Markov chain (see Figure 4.3), where each state represents a timeslot. The transition from state i to state i+1 represents the probability of no transmission in the previous slot, and the transition from state i to the initial state represents the probability of transmission in slot i. Using this technique as part of our model, we summarize the probabilities already de-fined in [9] for the sake of completeness. Assuming that there exists an AIFS. period difference between priority A and priority B queues, let PTrZonei be the probability of transmission from any queue in Zone i, then Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 68 PTrZonex = 1 - P[NTAfA (4.5) and PTrZone2 = 1 - P[NTA]N\P[NTB]N° (4.6) Let PCxZonei be the probability of collision for priority x queue, in contention Zone /. Then PcAZonex = 1 - P[NTAfA-1 (4.7) and PcAZone2 = 1 - P[NTA]N*~L .P[NTB]N' (4.8) Also, for priority B, PcBZone2 = 1 - P[NTA]N\P[NTB\NB-1 (4.9) The reason why there is two collision probabilities for priority A queues, while only one for priority B queues, is that contending A queues span two zones, Zone 1 and Zone 2. Priority B queues contribute to the contention only in Zone 2 after the expiry of their AIFS period. The solution to the Slot Occupancy Markov Chain, after defining the needed probabilities is Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 69 b o = 1 : (4.io) mm(CWmaxA .CWmaxa) 1 + Z IX-=i (1 - PrrZonej) and bi: = (1 - PTrZonei-i).bi-i (4.11) Therefore the final average collision probabilities pA and pB are then expressed as min(C WmaXA ,CWmaxa) pA= ^ PcAZonei.bi (4.12) i=i and PB = PcBZone2 (4.13) 4.4 Tagged Node Queuing Model As explained earlier, our finite load analysis is based on the interaction of two queuing models; one based on a user view (node model) and the other on the network/channel view (network model). In this section we derive important expressions for the node model. The network model is analyzed in the next section. Because the service time distribution for this model is not Markovian, we use an M / G / l queuing model. This section's model considers the node's queue as the server. Al l other messages, trans-missions, and interference from other nodes' queues or from co-located queues sharing the wireless medium will be modeled as delays in the service time. Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 70 4.4.1 Service Time Estimation (Node Queuing Model) In this section, we will derive a compound equation for the expected service-time (l/px) of queue x for the Tagged Node Queue server, using the basic queuing relation px = Ax/px. Essentially, the server represents the processing of the M A C and physical layers of an 802.lie station, and the server queue contains frames received from its higher layers. The service time is defined by the frame length distribution, the backoff process, the number of stations (transmissions and collisions of other nodes), and the collision probability px. We start by defining the transmission cycle as the time it takes a queue to transmit a frame, whether this attempt results in a collision or in a successful attempt. The total time it takes a queue to transmit a frame successfully may consist of several cycles each ending in a collision except for the last one. The expected number of cycles a node takes to transmit a ( . m-l 1 + 2px + 3p2x + ...l+mp1^"1 = \+px+p2x+..+pxl~l = £ Pkx, ' k=0 with m being the maximum number of retransmissions. Therefore, the expected number of transmission cycles that end in collisions is m-l CycleCxx = YJPx (4-14) k=\ In each transmission cycle, the queue counts down backoff slots, but may be interrupted by either collisions or successful transmissions from other queues, and finally ends the cycle either with a collision or a successful transmission of its own. Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 71 The service time can be expressed in terms of its component delays as follows: 1 = queueCxx + otherCx^ + backoff x + queueTxx + o\hevTxx (4.15) Thus, the service time is comprised of the accumulated backoff through the expected number of cycles (say C cycles), the accumulated successful transmissions from other queues (otherTxx) in C cycles, the accumulated collisions (otherCxx) from other queues in C cycles, the accumulated collisions made by the tagged node queue (queueCxx) through-out C cycles, and the successful transmission (queueTxx) or discarding of the frame by the tagged node queue when the maximum number of retransmissions is exceeded. Now, let the probability PAEB denote the portion of frames that arrive to an empty queue A when the medium is busy. These frames will experience only a portion of a transmission from other queues, an average period of TJ2 in case of a successful transmission, and TJ2 in case of a collision. Here, Ts is the time it takes to complete a successful transmission, including the PHY headers overhead, RTS, CTS, and A C K frames, and finally the frame payload. Tc is the time it takes to detect a collision, including PHY headers, RTS frame, and then some deference period. Then, P$B = (1 -P/O-JW PA + (1 -PA) NA-l NA (4.16) also for class B, Pf f c = ( l - p B ) . P b u s y p B + ( l - p B ) Ng-1 N B (4.17) Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 72 The factor pA + (1 - PA)^J^- is included to adjust the impact of P o u s y from the point of view of the tagged node queue. When the queue utilization pA is small and the Tagged Queue is empty, then the real contributors to Pbusy are the other NA - 1 queue. But as pA gets larger, this equation becomes non-linear because of the inter-dependence between pA and Pbusy-Given the fairness of the backoff process over a long time period, each queue will have a chance to transmit given that its buffers are not empty. In this case, the number of suc-cessful transmissions (PglherTx) and collisions ( P ^ t h e r C x ) arising from other queues during the service time of a single frame are given by the following probabilities, KherTx = PA{NA - 1) + RatioAB.pBNB (4.18) and for class B, and KherT* = PB(NB - 1) + Ratio u .pANA (4.19) Kkercx = \PA(NA - D + RatioAB.pBNB] (4.20) also for class B, Kthercx = \PB(NB - 1) + RatioBA.pANA] (4.21) 1 ' P o The ratios RatioAB and RatioBA are quantities that indicate how each class "views" the other class in terms of transmissions. Since class A has higher priority over B, the class Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 73 B will see much more transmissions from A queues than from other B queues. Therefore, class B views class A as having more queues, and the RatioBA captures this effect. In contrast, class A views class B as having fewer transmissions which will consider class B to have less queues. Hence the inclusion of RatioAB in the above formula. The next section will explain how these ratios are derived. The probabilities and pB0 represent the portions of transmissions from other nodes that result in collisions. But because of the existence of different zones, these probabilities have to go through the same process as pA and pB. However, a simple and logical approximation with an acceptable margin of error, is to get the average probability of collision p = (PA + pB)/2 and proceed as if the probability of collisions from other stations is the same for all classes. The expressions for p% and pB0 are (4.22) PotherTx * s a n expression of the complement of the portion of frames that get transmitted successfully given that there is a transmission, derived from the following relations. pA otherSum otherTx otherCx (4.23) pA 1 nt otherTx otherSum (4.24) and Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 74 P^therCx ~ ^otherS unf Pt (4-25) Therefore, pA A olherCx _ fo Of^ pA ~ I _ jjA 1 otherTx from which the equations of p^ and pB follow. Now, the main quantities of the service time (1/UA) for class A are derived directly: queueCxA = CycleCxA-Tc (4.27) A DA eb PoP\ otherCxA = (Khercx - ^t^T< ^4-28> backoffA = WA + CycleCxA.W^ (4.29) queueTxA = (1 - p%)Ts (4.30) otherTxA = (PAotherTx-^f).Ts (4.31) — = queueCxA + otherCxA + backoff A + queueTxA + otherTxA (4.32) PA and for class B, Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 75 — = queueCxB + otherCxB + backoffs + queueTxB + otherTxB (4.33) P-B 4.4.2 Ratio Selection Broadly speaking, RatioAB and Ration are a measure of the presence of one priority class relative to the other. Each ratio is the proportion of the number of successful transmis-sions from one class divided by the proportion of the number of successful transmissions from the other class while traversing all possible combinations of the backoff counters. Each ratio is a direct product of several parameters: the contention window size of each class, the AIFS period specific to each class, the number of retransmissions, the utilization p of each queue, and the number of total queues contending for the medium. We present a small example to clarify the above concept. Let there be 1 station in the network with 2 queues, the first for priority A, and the second for priority B. Both queues have C W M I N equal to 3 slots, with no retransmissions, and an AIFS difference of 1 slot. Because there are no retransmissions, doubling the Contention Window size is not possible even if collision occurs. We also assume that the queue is continuously backlogged, i.e. always has some packets to send, and that the backoff counters are decremented at the start of each idle time slot. We define a round of the backoff counters when both counters have just been re-generated (i.e. re-initialized with a random start value). As illustrated in Figure 4.4, every time the medium gets idle, queue A can start decreas-ing its backoff counter by one, while queue B finishes its AIFS period, marked by an X in Chapter 4. A F in i te -Load M o d e l for QoS-Enab led I E E E 802.11e W L A N s 76 Queued Backoff Counter Queue B Backoff Counter 1 2 3 X 1 2 3 Figure 4.4: Demonstration of the Class Ratio the figure. R o u n d 1: If, initially, queue A chooses a value of 2 for its backoff counter, and queue B chooses a value of 1, then collision w i l l follow. This combination of backoff counters for the A and B queues w i l l be denoted (2, 1). In the first timeslot after the medium gets idle, queue A w i l l decrement its counter from 2 to 1, while queue B is still waiting for the end of its A I F S . A t the beginning of the second timeslot, both queues A and B w i l l have their backoff counters equal to 1, i.e. (1, 1) counter combination, and w i l l be both decremented to 0 within the same timeslot, resulting in a definite coll ision between their transmissions. This marks the end of this round, and both counters w i l l be initialized again in the following timeslot. Therefore, the combination (2, 1) of the backoff counter w i l l end up in a collision. R o u n d 2: Assuming that in the next round, queues A and B choose the combination (3, 1). Then in the first timeslot, the counter combination changes to (2, 1), then to (1, 0) in the second timeslot. Thus, in the second timeslot, queue B w i l l have a successful transmission, while queue A counter gets decremented to 1. Since only queue B counter has been re-generated after the successful transmission, then we are still in the same round, and queue A counter has a residual value of 1, which we call it residual count (1, 0). Whatever the Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 77 value that queue B chooses afterwards, queue A will transmit successfully before the end of the AIFS period of queue B, thus concluding that the combination (3, 1) will lead to 1 success for A and 1 success for B. Round 3: For the next round, assume we start with the combination (1, 1), then follow-ing the same logic as before, queue A will have a successful transmission, resulting in a residual count (0, 1). Afterwards, queue A will choose a new value, which will lead us to three possibilities: a) either queue A initializes to 1, leading to a (1, 1) combination which takes us to where we started in the 3rd round (recurrence); b) A initializes to 2 which will lead to collision and the round ends; c) A initializes to 3, in which case queue B will have a successful transmission with a residual of (1, 0), as in round 2. The possibility of having the same counter combination recurring happening many times in one round, such as the possibility of having the same residual (0, 1) occurring many times in the same round, has led us to define a new quantity R, short for "recurrent" as follows where Totalc is the total number of combinations which is in this case equal to 3, meaning the number of members in the set (x,y): 1 < x < 3,1 < y < 3, where y is fixed and only x is being regenerated. In the case where recurrence is possible, such as in round 3 where residual (0, 1) can happen again as a success for the higher priority, then all recurrences are counted as R oo (4.34) Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 78 which translates into having the total successes of queue A in the combination (1,1) equal to 1 + R. In this example, R is equal to 0.75. Table 4.1 shows all the combinations of the above example. After calculating the total successes of both queues for all combinations, we define S uccessesB 4 Ratio AB = - = —— = 0.202 b uccessesA 19.75 and Ratios A = SuccessesA 1 = 4.937 SuccessesB Ratio AB The ratios calculated above match approximately the ratio values measured in simula-tions, which are RatioAssim - 0.2152 and RatioBASim = 4.462. Combinations Queue A Successes Collisions Queue B Successes (1,1) 1.75 0 0 (1,2) 1.75 0 0 (1,3) 1.75 0 0 (2,1) 0 1 0 (2,2) 3.75 1 1 (2,3) 6 1 1 (3,1) 1 0 1 (3,2) 0 1 0 (3,3) 3.75 1 1 Total 19.75 5 4 Table 4.1: Successes and Collisions of the (3,3) pair combinations On the other hand, when the contention window C W M I N is greater than 3, then more complications arise. Assume the same example as above, but with C W M I N equal to 4 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 79 instead of 3 for both priorities, and let's study the combination (4, 4), also called counter pair. Then in the first timeslot, the counters become 3 for class A, and class B counter remains at 4. After 3 timeslots, class A queue successfully transmits the frame, which leaves a residual of (0,1). Since we have 4 possibilities, let's examine the case where priority A queue chooses 4. The counter pair becomes (4, 1), which leads to a priority B successful transmission in the slot after the next, leaving a residual of (2,0). Assuming that priority B backoff procedure chooses a value of 2 for its counter, the counter pair becomes (2, 2). This pair leads again to a residual of (0, 1), returning us to our start point. This re-entrancy complicates matters substantially, making the combinational calculations of the correct and exact ratios almost impossible. In both the above mentioned examples, we assumed that the queues are backlogged. But as a finite-load model, this is not always the case. RatioAB and RatioBA have a strong relationship with the utilization rate p of their respective queues. When pA and pB are small enough (i.e. light load supplied to the WLAN), then RatioAB and RatioBA get to be equal approximately to 1. It is when pA and pB increase, that both ratios diverge, to finally have one equal the inverse of the other, in the manner explained above. We have extracted an empirical relationship between the utilization rates and the ratios as follows, if pB < 0.98: RatioAB = 1 - (1 - RatioABSat)PA (4.35) RatioBA = 1 + (1 - RatioABSa,)pA (4.36) Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 80 on the other hand, if pB > 0.98, meaning that class B queues are saturated, then RatioAB = 1 + RatioABSM ~ PA (4.37) 1 (4.38) Ratios A I + Ratio ABS at PA RatioABSat is the ratio that exists when the queues are backlogged, i.e. saturated. Re-transmissions and the number of queues are also factors of influence on the two ratio quan-tities. Al l in all, too many complex parameters affect the value of the ratios, and therefore a mathematical solution for this problem is still under study, and is out of the scope of this thesis. 4.4.3 Service Time Distribution We model the service time probability distribution function (PDF), bx(t), of any queue, as a shifted negative exponential distribution (n.e.d.), where the amount of shift is equal to the average frame length Ts, as follows: bA(t)=pAp.e-^ •u(t - Ts) (4.39) and for class B, bB(i) = u iBp.e-^-T*\u(t-Ts) (4.40) Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 81 For conciseness's sake, and because the analysis continues just as in Chapter 3, we'll only mention the final equations, which apply for both ACs. We will also drop the indexes. The n.e.d. constant y.p is: 1 The PGF of the queue length distribution is: <p(z) - z exruz-i) - z [l + ^ (1 - z)J The average queue size Nq is: p 2 + i2v„ N<'P+~W^ <443) The variance Vp is: V„ = 4 <4-4) The average system time is: T = -q A P2 + A2VP 2 ( 1 - p ) (4.45) And finally, the average network delay Vp is: Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 82 Wq = Tq + - - Ts (4.46) 4.5 Whole Network Queuing Model We adopt a similar methodology for the derivation of the expressions for P W t e and P b u s y as in Chapter 3, given that the highest priority class is equal in presence with the lower priorities at light loads and is the most present at high loads (the "Ratio" component), it was sufficient to use only class A average backoff counter value WA in the expression of P N . . The error introduced in this simplification is very small, especially that P,y/e and Pbusy, which are the target probabilities of this section, are stable quantities and do not change with small variations of WA. The expression for P'J becomes ;. P ] = P j slots = min (backoff_counter(/)) Ki<N =z 4=1 N k 1 \k(2WA-fN-k 2WA 2WA (4.47) Where /V is the total number of queues (NA + NB) in the network, and j is the minimum number of time slots elapsed since the medium became idle until the first backoff-counter (among iV counters) fires. Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 83 4.6 Extending the Model to Multiple Priorities The model introduced in this chapter was derived assuming two priority classes. We now show it can be easily extendible to multiple priorities by only modifying key quantities. The IEEE 802.lie standard defines 4 priorities (or Access Categories). As to the collision probability px, the same steps should be followed as before, by dividing the timeslots into more contention zones depending on the AIFS periods of the multiple priorities. For each contention zone, if applicable for priorities A, B, C, and D in a specific contention zone, the following quantities become PcAZonei = 1 - P[NTA]N*-\P[NTB]N'.P[NTC]NC.P[NTD]ND (4.48) PTrZonei = 1 - P[NTA]N\P[NTB]NB.P[NTC]NC.P[NTD]ND (4.49) Then the PTrZonei probabilities are used to calculate the Slot Occupancy probabilities bj, which in turn are used to weight the PcxZonej probabilities to get the final average collision probabilities px. Additionally, the number of successful transmissions from other queues PxotherTx should be adjusted to take into consideration the presence of more priorities. The expression becomes KherTX = PA(NA - 1) + RatioAB.pBNB + RatioAC.pCNC + RatioAD.pDND (4.50) Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 84 The same should be done to Pt otherCx as follows pA otherCx = \PA(NA - 1) + RatioAB-PBNB + RatioAC.pcNc + RatioAD.pDND] (4.51) 4.7 Numerical Results In this section, we compare numerical results obtained from the analytical model with results obtained from our simulator. We have implemented a detailed simulator of the IEEE 802.lie standard and its associated devices. We have validated our simulator by comparing our results with commercial simulators such as OPNET to ensure accuracy. We have also verified that the simulator operating in saturation matches Robinson and Rhan-dawa's collision probabilities in saturation ~p~A and for each queue and other quantities to a high level of accuracy (confidence interval above 95%)[3]. Except for the collision probabilities px, we found all other quantities' to be stable, and give very accurate results when compared with simulations. Most often, the calculated results and simulations overlap with exact values for large spans of As. For large values of A, the network utilization px approaches 1 and the laws of queuing theory do not hold accurately. In this high utilization range, we observe the largest divergence between our analytical model and simulation results. Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 85 4.7.1 Numerical Example for Service Time The following example shows how well each component of p is represented in our model. Although there are some minimal differences, we note that simulation results vary with the initial random seed, and that some of our proposed equations are good estimations rather than real probabilities. The example is given with 12 nodes in the network, C W M I N A is equal to 8, C W M I N B is equal to 32, C W M A X A is equal to 128, C W M A X B is equal to 1024, A I F S A is equal to 0 and A I F S B is equal to 1, and the load is equal to 50 frames/sec. All quantities units are represented in time slots. See Table 3 for details. Parameter Simulation of A EFLM of A Simulation of B EFLM ofB nodeCx 15.03 14.78 19.05 20.06 otherCx 26.28 31.05 230.42 238.94 backoff 19.64 12.96 108.8 137.4 nodeT!*: 94.16 94.18 93.28 92.87 other Tx 367.79 376.24 3025.18 3035.05 522.93 529.21 3476.75 3524.3 p 0.3873 0.3866 0.4472 0.4676 Utilization p 0.2646 0.2589 0.999 0.999 Table 4.2: Numerical Example of the components of the Service Time 4.7.2 Results Figures 4.5 to 4.8 show plots of numerical results from our extended finite-load analyt-ical model for QoS-Enabled WLANs compared to simulations. Al l plots and simulations used the same parameter set given in Table 4.3. Figure 4.5 plots the utilization rate p versus input load for queues A and B . Figure 4.6 plots the collision probability p versus input load for both queues. Figure 4.7 plots the average service time 1 /p versus input load for both Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 86 queues. Figure 4.7 plots the average waiting time Wq versus input load for both queues respectively. All plots cover three W L A N sizes: 4 stations, 12 stations, and 20 stations, each station hosting one class A queue, and one class B queue. All queues have the same input rate/load A, which is the same for both priorities, and the data frame payload size is fixed at 2304 bytes, which is the M T U for W L A N . The parameters Tc and Ts have been calculated as the approximate sum of RTS, CTS, frame size, physical and M A C headers, A C K , and DIFS. For simplicity, we have quantized the frame lengths to align with slot boundaries. The error due to this quantization is negligible especially considering that frame length is much larger than the slot size. The figures show clearly that our E F L model is very accurate especially when the num-ber of stations in the network is less than 20, which is typically the case for real WLANs. The accuracy degrades slightly as the number of nodes, and therefore queues, increases, but the model is still highly precise, especially for the key quantities: p (utilization), and l/u (service time). Bandwidth 11Mbps Slot Time 20 microseconds CWminA 8 Frame Size 2304 bytes CWmaxA 128 Tc 24 slots CWminB 32 Ts 95 slots CWmaxB 1024 MAC Header 272 bits Retransmissions 4 CTS Size 112 bits PHY Header 192 bits DIFS Time 50 microseconds RTS Size 160 bits AIFSA Period 0 slot + DIFS ACK Size 112 bits AIFSB Period 1 slot + DIFS Table 4.3: Simulation and Mathematical model Parameters Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 87 4.8 Conclusion In this chapter, we have extended the E F L model in the previous chapter to QoS-Enabled WLANs. The model has more accuracy compared to the other models in the literature when matching with results obtained by a detailed W L A N simulator. Our model is also the first to explain in details the consituting components of the service time in a proba-bilistic multi-priority system. The accuracy of our model is attributed mainly to the use of a coupled queuing model which proved to be very useful for studying the effect of vary-ing parameters on the micro-scale (queue level) and on the macro-scale (network level). The proposed model gives numerical results for the average Waiting Time (Delay) and the average Queue Length (Buffer Size) which are crucial information for enforcing QoS guarantees. The model is very flexible and allows also for easily changing the input traffic model from Poisson to other useful distributions by modifying the expression for Q(z), and applying a G/G/ l queuing model. Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 88 ro vs. load with 04 stations 0.9 0.8 0.7 S. 0.6 fx! I § 0.4 0.3 0.2 0.1 h 0 20 Simulation of A - EFLQM of A Simulation of B EFLQM of B eo 90 100 load frames/sec ro vs. load with 12 stations 0.9 0.8 0.7 r? 0.6 j 0 5 0.3 0.2 0.1 Simulation of A EFLQM of A Simulation of B EFLQM of B load frames/sac ro vs. load with 20 stations 0.9 0.8 h 0.7 r? 0.6 g 0.5 I s °-« 0.3 0.2 0.1 Simulation of A EFLQM of A Simulation of B EFLQM of B load frames/sec Figure 4.5: Utilization vs. load for WLAN with 4, 12, and 20 stations Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 89 p vs. load with 04 stations o Simulation of A —* EFLQM of A o Simulation of B I EFLQM of a | 0 . 2 5 f -I CL 5 0.151-0.2 V 0.1 50 60 load frames/sec 90 100 p vs. load with 12 stations o Simulation of A * EFLQM of A o Simulation of B + EFLQM of B 9--Si--" load frames/sec o Simulation of A * EFLQM O f A o Simulation of B 4 EFLQM of B p vs. load with 20 stations S 0.4 \ I load frames/sec Figure 4.6: Collision probability, p vs. load for WLAN with 4, 12, and 20 stations Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 90 •| 1000|-& 4000 h 1/mu vs. load with 04 stations Simulation of A - EFLQM of A Simulation of B EFLQM of B 80 90 100 load frames/sec 1/mu vs. load with 12 stations Simulation of A EFLQM of A Simulation of B EFLQM of B load frames/sec 1/rnu vs. load with 20 stations 2. 1.2 1 Simulation of A EFLQM of A Simulation of B EFLQM of B load frames/sec Figure 4.7: Service time vs. load for WLAN with 4, 12, and 20 stations Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 91 1200 1000 800 600 400 200 h Waiting Time in Queue vs. load with 20 stations 0 * 0 i > j j -» =*= o —I— • E F L Q M 4 stations Simulation 4 stations E F L Q M 12 stations Simulation 12 stations E F L Q M 20 stations Simulation 20 stations / O / =31 10 20 30 40 50 60 load frames/sec 70 80 Figure 4.8: Waiting time, or Delay, W Q for Priority A vs. load for WLAN with 4, 12, and 20 stations Chapter 5 An Improved Saturation Model for IEEE 802.11e WLANs 5.1 Introduction As mentioned before, IEEE 802.lie standard introduces several enhancements to the M A C layer of the original 802.11 standard. The E D C A M A C function is built on top of the distributed coordination function (DCF) of the original standard. The E D C A introduces class specific contention window sizes and initial deferment time (Inter Frame Space, IFS) [36]. There have been several efforts to analyze the behaviour of the E D C A mechanism. These efforts mostly consider the saturation conditions in which all stations and queues are always backlogged. In particular we found models developed by Robinson and Randhawa [3] and Xiao [25] noteworthy. However, the model developed by [25] only considers the 92 Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 93 contention window size for prioritizing frames, ignoring the effect of different IFS times for different traffic classes (using Arbitration IFS: AIFS). The other important model, de-veloped by Robinson and Randhawa, considered both parameters and provides a solution for combining the effects of both parameters. However, this model assumes a post colli-sion behaviour that does not reflect the reality of 802.11 or 802.1 le networks. For further material on related work, the reader can refer to Section 2.5. In 802.11 when a collision happens stations who are involved in collision will wait for an Ack Timeout after the end of collision before they can realize that a collision happened, they will then resume normal contention; the other stations only wait until the end of the collided transmission and resume operation normally. This is different from assumptions in [3] that presume non-colliding stations will wait for an EIFS before resuming normal contention. Apart from this assumption, the study published in [3] presents a novel way of modeling the behaviour of contending stations with different priorities. However, [3] only presents a case with two priorities and a generalized model is not offered. The ideas presented in [3] are the basis for our model. We correct the assumptions made in [3] and generalize the model for an arbitrary number of priorities instead of only two. Our model provides a complete solution for modeling 802.1 le E D C A under saturation mode [36]. The reader can refer to Section 2.2 for information about the underlying technology of 802.1 le networks. Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 94 5.2 Model Development The E D C A function is a contention-based method in which stations desiring to access the medium have to wait for a random duration of time before they are allowed to start a transmission on the channel. This random waiting time is different for each priority and consists of two components: first the IFS which is a predetermined value for each priority level, and the second is the contention window size specified by priority-specific parame-ters C W M I N and C W M A X , defined as the minimum and maximum sizes of the contention window, which define the backoff procedure. Each queue that wants to access the medium has to sense it idle for AIFS plus a randomly chosen backoff duration. The backoff du-ration is chosen randomly between 1 and CW (Contention Window). C W is intiailly set to C W M I N but after each collision it is doubled until it reaches C W M A X . A successful transmission will reset CW to its minimum. Given the above description of the E D C A function, we introduce our model by mathe-matically defining the backoff process behaviour. We assume saturation situation in which all queues are always backlogged. As a result, all transmissions consist of two stages: waiting for the AIFS expiry, and waiting for the backoff counter to reach zero. To model the backoff process we first model the process for one queue with given E D C A parameters. This could be done following the same method described in earlier works by Bianchi [9] and Robinson [3]. As described in [9] and [3], the backoff value can be modeled as a two dimensional Markov Process. Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 95 For such a model to be correct there are two fundamental assumptions. One is that in each idle slot, each queue may attempt to transmit with an independent and constant prior-ity. The other assumption is that at each transmission attempt, regardless of the number of collisions suffered, a packet may collide with an independent and constant probability p. However, since in E D C A the slots after a busy period are not all available to all priorities due to the AIFS differentiation mechanism, the number of contending stations may be dif-ferent in each slot. Therefore to overcome this complexity we use an average conditional collision probability p (as is used in [3]). The model that yields from such assumptions is a bi-dimensional Markov chain (refer to [9] for a detailed examination of this model). From this model we derive the following equation that describes r as a function of p for each priority level (therefore we dropped the priority subscript): CWmin + 1 - k, 0o,* = . 0o,i ( 5 . 1 ) C Wmin biJc = bQil.pi ( 5 . 2 ) w, YiYjbi*= 1 (5-3) i=0 k=\ m T = i'=0 III J]biA ( 5 . 4 ) The probabilities biyj are the steady-state probabilities of the two-dimensional Markov Chain that models the backoff process [9] [3]. Obviously, the bjj probabilities are strongly Chapter 5. An Improved Saturation Model for IEEE 802.1le WLANs 96 dependent on p. To solve for p and we need to find p in each slot after a busy period and using the second set of equations we can derive p and and consequently the throughput. 5.3 Slot Occupancy We assume that each priority level may have its own AIFS and Contention Window. To examine the contention behaviour after busy periods, we assume that there are K possible priority levels with each slot containing rij {j : (l,K)} contending stations (or queues). Each priority level has an AIFS value equal to j slots, meaning that priority level j will start contention in the/th idle slot. For example if there are only three priorities 1, 4, and 7; slots 1-3 will only have n\ stations contending, while slots 4-6 will have ti\ + « 4 stations, slot 7 and after will have all ri\ + n4 + w7 stations contending. Note that we set rij for other priorities to zero. We model the contention slots after a busy period in a separate Markov Chain in order to derive the slot occupancy and probabilities of collision in each slot. Our model is a generalization of the model presented in [3]. The following Figure 5.1 describes our model. Wmi„ is the minimum of all maximum contention window sizes ( C W M A X ) , ! and M is the lowest priority. If rij stations of priority i exist, then the equations that govern this model are as follows. For the first zone, where only the highest priority is active, the expression of the probability of transmission is: Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 97 1 _ L n r+n 2 nr+n2+n3 S l o t 1 _J I L_ M M+1 Figure 5.1: Modeling Slot Occupancy for different contention zones p ^ i - a - T , ) 1 " ( 5 . 5 ) For the second zone, PtU = \ - ( l - r l r . ( \ - r 2 f ( 5 . 6 ) It follows that, for an arbitrary zone, the general expression is p'r = z=z 1 -rT}=,(l - T y - r i f K z < M 1 - n>i (1 - T ; ) " J i f z > M ( 5 . 7 ) Knowing P"=z and assuming that the Markov chain is in equilibrium, the relationship between the slot occupancy steady-state probabilities is ( 5 . 8 ) Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 98 And with the condition that Wmin 2 bt = 1 (5.9) i=0 It follows that M Wmin b0-a- PU) = E b i • + Z b ' • ( 5 - 1 0 ) i=l i=M+\ Therefore leading to b0= 777-.— (5.11) i + z*rn;-=.a-^) Next, we derive the average conditional collision probability Pj for each priority j (prob-ability that a transmitted packet of class j encounters collision). As before, we give the example of two priorities, then the general expression for the probability. We know the probability of a collision happening amongst class j stations in zone z, where j = 1 and z = l : Pcj=\ = 1 - d - n ) " ' - 1 (5.12) The second priority is not active in this region, so it follows that PcjZ] = 0 (5.13) In the second zone, Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 99 p c j j = i - ( i - T 1 r - i - ( i - T 2 r ( 5 . i 4 ) and, pc% = i-a-Tir-(i-T2ri-1 (5.15) The general expression for the conditional collision probability is z PC{=1 - (1 - T,-)"'-1 • n ( i - ^ (5-i6) k=\,k±j Knowing the probability of collision within stations for a specific zone, we can find the average conditional probability of collision for class j stations (probability that in any zone, a collision occurs by class j stations' transmission): Wmin pj=YibrPcl* (5-17) 1=1 Using the above equations we can derive the average collision and transmission proba-bilities for each priority class (Pj, r,). Using these probabilities we can derive the achiev-able throughput for each class as well as the total throughput of the system. 5.4 Throughput Analysis To find the total throughput we need to find out the average probability of successful transmissions as well as the average probability of collisions in each slot i (Psz=j, P^°j)- We Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 100 can then use these probabilities and find the expected length of the transmission duration (including the time spent in probable collisions). For this purpose we find the average of the transmission periods initiated in each slot weighted according to the slot occupancy probabilities found in the previous section. The expected length of the transmission dura-tion is expressed as follows: W min To find the average probabilities of successful transmissions or collisions in each zone /, we can use the probability of transmission in each slot, TJ for class j, found in the previous section. The probability of a given class j transmission in zone / is successful is expressed as follows: P5. = J,Z=l > \-ptr (5.19) 0 otherwise The probability of any given transmission in zone z' is successful is written as follows: ^ = I> ' ^ (5-20) 7=1 The probability of any given transmission in zone i encounters a collision is expressed as follows: Pc!% = Pti ~ Pf=i (5-21) Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 101 The expected payload size indicates how much useful data is transmitted during the expected length of the transmission duration. The quantity PL refers to the average payload size in a frame. The expected payload size is: Wmin Ejp = nj.PLYJbi-PSj*=i (5-22) i=l Using the expected length of transmission duration and the expected payload length we can derive the throughput for class j: Ej Tj = -=^ (5.23) ED 5.5 Simulation Results In this section, we present the simulation results, which are generated using a very accu-rate discrete-event simulator, using the parameters in Table 5.1 and Table 5.2. The reader can also refer to [36]. As the figures show, the mathematical model results and the simula-tion results are almost identical. In Figures 5.2 and 5.4, we plotted the collision probability p versus the number of stations for four priorities (A being the higher priority). In Figures 5.3 and 5.5, we plotted the Saturation Throughput versus the number of stations with a different set of input parameters. Figures 5.2 and 5.3, labeled Batch 1, are plotted with the parameters in Table 5.1, and Figures 5.4 and 5.5, labeled Batch 2, are plotted with the parameters in Table 5.2. Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 102 Parameter Value Parameter Value Frame Payload 12000 bits Bit Rate 1 Mbps M A C header 224 bits Slot Time 20 ps PHY header 192 bits SIFS 10 /is A C K 112bits + PHY Retry limit 4 RTS 160 bits + PHY CTS 112 bits + PHY AIFS1 SIFS + Slot Time AIFS 2 SIFS + Slot Time AIFS 3 SIFS + Slot Time AIFS4 SIFS + Slot Time C W M I N 1 8 C W M I N 2 16 C W M I N 3 24 C W M I N3 32 C W M A X 1 16 C W M A X 2 32 C W M A X 3 48 C W M A X 4 64 Table 5.1: Simulation Parameters for Batch 1 Parameter Value Parameter Value Frame Payload 12000 bits Bit Rate 1 Mbps M A C header 224 bits Slot Time 20 /is PHY header 192 bits SIFS 10 /is A C K 112 bits + PHY Retry limit 4 RTS 160 bits + PHY CTS 112 bits + PHY AIFS1 SIFS + Slot Time AIFS2 SIFS + 2*Slot Time AIFS 3 SIFS + 3*SlotTime AIFS4 SIFS + 4*Slot Time C W M I N 1 32 C W M I N 2 32 C W M I N 3 32 C W M I N3 32 C W M A X 1 64 C W M A X 2 64 C W M A X 3 64 C W M A X 4 64 Table 5.2: Simulation Parameters for Batch 2 Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 103 Collision Probability p vs. Number of Stations -i 1 1 r-10 12 14 Number of Stations Figure 5.2: Collision Probability vs. Number of Stations for Batch 1 Throughput in Kbits vs. Number of Stations O Sim of A • *—Mode l of A * Simulation of B Model of B + Simulation of C Model of D Simulation of C Model of D 8 10 12 Number of Stations 16 18 Figure 5.3: Saturation Throughput vs. Number of Stations for Batch 1 Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 104 Collision Probability p vs. Number of Stations Sim of A •Model of A Simulation of -Model of B Simulation of -Model of D Simulation of Model of D 10 12 Number of Stations 18 Figure 5.4: Collision Probability vs. Number of Stations for Batch 2 ¥ Throughput in Kbits vs. Number of Stations o Sim of A -Model of A . Simulation of B -Model of B Simulation of C -Model of D Simulation of C Model of D 8 10 12 Number of Stations 14 16 18 Figure 5.5: Saturation Throughput vs. Number of Stations for Batch 2 Chapter 6 Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 6.1 Introduction The rapid development of switching architectures, new smart antennas, and robust se-curity, has lead to the wide proliferation of wireless local area networks (WLANs) into the enterprise and consumer markets. Currently, WLANs have become more than just a niche solution of extending the enterprise or institution network to unwired areas. For businesses, WLANs offer true economic advantage by helping enterprises maintain a flex-ible reusable local wireless networks that can be moved with the enterprise, or to improve employee mobility. 105 Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 106 Some of the major problems that have been challenging WLANs, and wireless networks in general, are the imperfections and the time-varying characteristics of wireless channels. The high bit error rate, fading effect, and multipath propagation of the same signal, all con-tribute to the complexity of handling wireless channels. This motivates the development of new techniques to improve the performance. These new techniques rely on adapting the MAC to the present conditions of the wireless network. In this chapter, we study the effect of changing the Contention Window Parameters (CW) on the Saturation Throughput (ST) of the wireless network. We use a modified version of the mathematical model developed in [3], which we published in [36], in one of our algorithms to optimize the performance. The reader can refer to Section 2.2 for information about the underlying technology of 802.1 le WLANs. Also, to know more about the related work, the reader can refer to Section 2.5. 6.2 Effect of the CW Parameters on the Saturation Through-put The 802.11 MAC overhead includes access deference, transmission of RTS, CTS, and ACK packets which are specified by timing parameters that ensure correct network oper-ation. When added to collisions, these parameters constitute a significant bandwidth and delay overheads, especially when the number of contending stations increases or demand more bandwidth. In this research we are concerned with the problem of the low Saturation Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 107 Throughput phenomenon, both for access point and wireless (client) station. In the follow-ing discussion, the term "network" will be used to refer to area covered by a single Access Point and its associated stations. The Saturation Throughput gets divided among the stations that are active in the net-work. In [9] [12], Bianchi showed that beyond a certain traffic load threshold, the through-put of an 802.11 W L A N remains constant for a constant number of stations. The through-put value at this point is called saturation throughput. The value of the Threshold depends on the network dynamics, and can vary considerably from one network to the other. In the following we investigate the impact of the CW period on the performance of the satuation throughput. When executing the backoff procedure, a station chooses a random value with a uniform distribution over the interval [1, C W M I N +1] for the first transmission attempt. After each collision, the contention window is doubled, which means that the random value is chosen from the interval [1, 2'.(CWMIN+1)], after the ith collision. But the maximum limit of the contention window is not allowed to grow indefinitely, , as the minimum of the two quantities 2'.(CWMIN-I-1) and C W M A X is chosen. Therefore the two values C W M I N and C W M A X define completely the backoff procedure. In Figures 6.1 and 6.2, the network is constructed of stations that have backlogged queues i.e. the buffers of each station never get empty. The parameters of the network are those shown in Table 6.1 unless otherwise specified. The Contention Window pa-rameters, C W M I N and C W M A X are 7 and 15 respectively. As shown in Figure 6.1(a), the Saturation Throughput goes practically to zero as the number of stations increases in the Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 108 network. This is due to the Probability of Collision which approaches 1 as the number of stations in the network increases as shown in Figure 6.2(a). To illustrate the effect of the Contention Window on the Saturation Throughput, we change C W M I N and C W M A X values to 15 and 31 respectively. The result is shown in Figures 6.1(b) and 6.2(b). This seemingly minor change in the Contention Window parameters greatly enhances the Saturation Throughput, increasing it by almost ten folds when the number of stations in the network reaches 50. Parameter Value Parameter Value Frame Payload 8000 bits Bit Rate 1 Mbps M A C header 224 bits Slot Time 20 ps PHY header 192 bits SIFS 10 us A C K 112 bits + PHY Retry limit 5 RTS 160 bits + PHY AIFS1 SIFS + Slot Time CTS 112 bits + PHY AIFS2 SIFS + 2*Slot Time Table 6.1: Simulation parameters Finding an optimal values of C W M I N and C W M A X for a single A C may not be hard, however with multiple ACs the problem becomes harder to solve, because we have to find a set of optimal C W M I N and C W M A X pairs and not just a single pair. To understand this, suppose there are n discrete possible values of C W M I N and k possible priority levels, then number of possible permutations for k C W M I N values, one for each priority levels are n\/(n - k)\. This means that for 2 priority levels and 32 discrete possible values of each C W M I N number of possible solutions are 32!/(32-2)!=992. However, when we change the number of priorirty levels to 8 then the solution space drastically increased to 32!/(32-8)! = Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 109 CftJTLin =7, CWirex = 15 Nirriber of Stations (a) Saturation Throughput (Mbps) with C W M I N , C W M A X = ( 7 , 15 ) atfrriri = 15, Oiirax = 31 1 •-,—i—i—i—,—i—i—i—,—i—i—.—.—.—,—i—.—.—.—.—I—•—i—i—i—r -p r 0 10 20 30 40 50 Niirter • of Stations (b) Saturation Throughput (Mbps) withCWMiN, C W M A X = ( 1 5 , 3 1 ) Figure 6.1: Effect of C W M I N and C W M A X on the Saturation Throughput Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 110 CKttiin =7, CUnax = 15 Number: of Stations (a) Probability of Collision with C W M I N , C W M A X = (7,15) CKhiin = 15 , Clitaax - 31 Number of Stations (b) Probability of Collision with C W M I N , C W M A X = (15,31) Figure 6.2: Effect of C W M I N and C W M A X on the Probability of Collision Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 111 4.2410e+011. In this study, we have developed algorithms to find the near optimal values of C W M I N and C W M A X for each priority level. 6.3 MAC Adaptation Algorithms So far, three different algorithms have been developed for handling the optimal Con-tention Window parameters problem. In all three algorithms, the Access Point takes the responsibility of collecting information, computing throughputs, calculating Contention Window parameters, and then broadcasting the results back to the stations in the network, using Beacon frames. In this section, we will describe the developed algorithms. The three AP algorithms are capable of overcoming the "Saturation Throughput" problem. Al l algorithms are based on the same fundamental concept of using adaptive CW size con-trol for maximizing the throughput. The three algorithms differ mainly in the adaptation mechanism. 6.3.1 The Station-Count Algorithm (SCA) The Station-Count Algorithm establishes a linear equation between the CW parameters and the number of stations in the network. It takes the number of stations having the highest priority and multiplies by a constant to get the new value of CWMiN[highest], then for the subsequent priority, it adds the number of stations of this priority multiplied by a constant to the C W M I N of the highest priority, and so on. Algorithm 1 illustrates the SCA. The Station-Count Algorithm is a very simple algorithm. It is a deterministic algorithm, and doesn't have the kind of uncertainty that the Derivative Algorithm has. The SCA works Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 112 as follows. For the highest priority A C , SCA multiplies the number of stations using this A C by a constant to get the value of C W M I N . The C W M I N for other ACs are calculated recursively as follows CWMIN[» - 1] = CWMiN[i] + C2 where C2 is a user defined parameter and A C i-1 has lower priority than A C i. This recursive calculation assures that higher priority ACs always have lower value of CW as compared to low priority ACs. SCA also keeps the ratio C W M A X [ A C ] / C W M I N [ A C ] constant. It performs better than the static case of the 802.lie (i.e. same network having same parameters except for the CW parameters) Algorithm 1 - The Station Count Algorithm % Stations[AC] i s the number of stations that has % th i s type of t r a f f i c CWmin[highest AC] = CI * Stations[highest AC] % Compute the CWmin of the next p r i o r i t y recurs ive ly % based on the CWmin of th i s p r i o r i t y FOR i = highest AC -1 ; i >Q; i — CWmin[i] = CWmin[i+l] + C2 * Stat ions[ i ] END FOR FOR i = highest AC; i >0; i ~ CWmax[i] = CWmin[i] * CWratio[i] END FOR UPDATE data structures i n the beacon frame SEND beacon frame Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 113 6.3.2 The Throughput Derivative Algorithm (TDA) After each C W change, the Throughput Derivative Algorithm employs measurements of the throuhgput taken in the Access Point (AP). It then tentatively changes the C W M I N of the system, and observes the derivative of the throughput. C W M A X is also changed while keeping the same ratio (new C W M A X / new C W M I N ) , as the original ( C W M A X / C W M I N ) ratio. The throughput derivative is taken over the present and a few past measurements of the throughput. We used the last 80 measurements in our simulations, with the frequency of 1 beacon/second. Algorithm 2 presents the Throughput Derivative Algorithm. Note that the AP, by controlling the CW parameters is essentially trying to track the opti-mum CW size for maximizing the W L A N throughput. In reality, the T D A only calcu-lates C W M I N [ A C ] for each access category and calculate C W M A X [AC] by keeping the ratio C W M A X [ A C ] / C W M I N [ A C ] constant. The AP updates the values of.CW parameters in every beacon frame. The operation of the TDA is best described with Figure 6.3, where the throughput deriva-tive is plotted versus time. We have divided the plot into four quarters for illustrative purposes: 1. The first quarter Q l shows the derivative increasing, therefore the difference between the current derivative measurement and the past derivative measurement is positive, and the value of the current derivative is also positive, representing a throughput improvement. In such a case, the TDA keeps adding the predefined increment mul-Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 114 tiplied by the sign of each AC (diffsign), to the CW parameter values in subsequent beacon frames. 2. In the second quarter Q2, although the difference between the current derivative measurement and the past derivative measurement is negative, but the value of the current derivative is positive, therefore it means the throughput is still increasing. The sign of diffsign is not reversed. 3. In the third quarter Q3, the difference between the current derivative measurement (P2) and the past derivative measurement (PI) is negative and the value of the current derivative (P2) is negative, indicating a throughput decrease. This is the only case where the sign of diff^sign is reversed. 4. In the fourth quarter Q4, the value of the current derivative is negative, but the differ-ence between the current derivative measurement and the past derivative measure-ment is positive. While the current derivative measurement is negative indicating a decrease in the throughput, it also indicates that the throughput is decreasing less sharply than the past measurement since the difference of the current and past deriva-tive measurements is positive. Therefore, it means that the addition of the increment multiplied by the current sign of the diff^sign variable is working towards increasing the throughput. This is why. the sign of diffjsign is not reversed in the fourth quarter. The TDA has a real potential for being a smart solution for the ever-changing condition of the wireless medium, as well as the wireless network. Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 115 3 CL. 3 1 = 0.8 -0.6 -0.4 0.2 0 -0.2 -0.4 -0.6 -0.8 --1 --Throughput Derivative V a l u e vs. T i m e 1 Qi —i— \ Q2 3 Time Figure 6.3: The TDA Operation Zones Algorithm 2 - The Throughput Derivative Algorithm % mean i s the average value of throughput measurements % f o r l a s t few observations derivative[AC] = (mean[AC] - old_mean[AC])/beacon_int IF derivative[AC] < old_derivative[AC] & derivative[AC] < Q THEN diff_sign[AC] *= -1 % Update every AC with the following equations. CWratio[AC] % i s a constant value CWmin[AC] = CWmin[AC] + diff_sign[AC] * step CWmax[AC] = CWmin[AC] * CWratio[AC] UPDATE data structures i n the beacon frame SEND beacon frame Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 116 6.3.3 The Analyt ica l A lgor i thm The Analytical Algorithm uses mathematical calculations to estimate the optimum CW parameters. It is based on a modified version of Robinson's model [3], which we published in [36], and is a typical optimization problem. Deriving the equations from the analytical model, we came out with a system of non-linear equations, with as many unknowns, and is presented in Algorithm 3. The Analytical model is very accurate and provides the optimum value of the CW pa-rameters right away, without further searching. It may even give some surprising result, such as interchanging of the CW parameters values between the highest and lowest priority, which will still lead to the highest possible throughput of the system. Solving this system of non-linear equations may take long time. For example, it takes up to 2 seconds on a 2 GHz PC, which is not practical for a wireless Access Point, unless accelerated by hardware, or unless performing the calculations offline. The algorithm changes with predetermined increments the CW parameters of all prior-ities, evaluates the throughput with these values and then records it in memory. Then a simple search of memory for the largest throughput yields the optimum we're searching for. In this system, only two priorities exist, priority A and priority B. The minPriorityA and maxPriorityA values are the range of priority A that we want the algorithm to search for the optimum in. The same applies to the minPriorityB and maxPriorityB values. The "incr" constant is the increment we want to add to the CW parameters on every evaluation. Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 117 Algorithm 3 - The Analytical Algorithm for access categories A and B CWmin[A] = minPriorityA; CWmin[B] = minPriori tyB; Maxthrup = Sat_thrup(A, B, CWmin[A], CWmin[B]); FOR i = minPriorityA; i < maxPriorityA; i = i + incr FOR j = minPriorityA; j < maxPriorityA; j = j + incr Thrup = Sat_thrup(A, B, i , j ) ; IF Maxthrup < Thrup THEN Maxthrup = Thrup; CWmin[A] = i ; CWmin[B] = j ; END IF END FOR END FOR UPDATE data structures in the beacon frame SEND beacon frame It is to be noted here that full enumeration of all possible solutions results in a large com-putation time. However, this can be reduced by properly adjusting the range [minPriorityA, maxPriorityA] and the value of constant "incr" in the analytical algorithm. Currently we propose to use Analytical Algorithm for at most two priority levels (ACs), however, we are working on enhancing the algorithm to accommodate all possible priority levels. 6.4 Simulation Results All the simulations and the analysis were done with the same parameters as in Table 6.1, except for priority 2 (or B) which the C W M I N is equal to 32, and the C W M A X is equal to 1024. It's worth noting that the CW Parameters in Table 6.1 are the initial values. These will be changed later by the adaptive algorithm. In the Adaptive E D C A simulations, the Analytical Algorithm decides which CW parameters are the most suitable for the network. All the queues of all the stations are backlogged. Also unless it is mentioned in the figure, Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 118 all simulation scenarios use 50 user stations and a single AP. We have compared our adap-tive algorithms with the standard IEEE 802.lie E D C A static parameter scheme; we call it static in our simulation results. Figure 6.4 shows the ST of the Static E D C A and of the Adaptive E D C A using the Station-Count Algorithm plotted versus time. It was also simulated for 50 stations and shows approximately 7 times improvement of the ST. Figure 6.5 shows the change in the Contention Window Parameters, specifically in C W M I N , when the SCA is activated at t = 1000 sec. In this scenario, we applied the TD algorithm to the CW of the higher priority, and fixed the CW of the lower priority with respect to the higher one. The TD algorithm can be applied separately to the two priorities, but it seems that only the CW of the higher priority will significantely change the ST. Figure 6.6 shows the results of the throughput using the Throughput Derivative Algo-rithm: the Saturation Throughput (ST) is plotted versus time for both Static E D C A and Adaptive E D C A using the TD Algorithm. This figure has been plotted for 50 stations, and shows approximately 7 times improvement of the ST. The T D A algorithm has been enabled to work when time reaches 1000 seconds, and the difference is obvious before and after this point. However, since the TDA algorithm has the same improvement as the SCA in this case, it is worth noting that the TDA performs generally much better than the SCA, because of its adaptability and flexibility. Figure 6.7 shows the same throughput but after being smoothed by a low-pass filter to prepare it for the use of the TDA. Figure 6.8 shows the derivative values derived from the Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 119 throughput that the T D A uses to calculate the changes in the CW parameters. Figure 6.9 shows the change in the Contention Window Parameters, specifically in C W M I N , when the T D A is activated at t = 1000 sec. Figure 6.10 shows the results of the simulation of the Analytical Algorithm along with the analysis and simulation results for the Static EDCA. This figure shows approximately 7 times improvement over the Static E D C A for 50 stations for the highest priority. Figure 6.11 shows the simulation results for priority B. Figure 6.12 shows the proof of optimization for Priority A. In this figure, we plotted all the analysis results for the different CW parameters that the Analytical Algorithm has chosen, and compared them with the Adaptive simulation results. It shows that for different number of stations, the Analytical Algorithm chooses the optimal throughput value for Priority A and tracks the optimum of all the curves. We have chosen to optimize for Priority A instead of the Overall Throughput because of the focus of our group on QoS and Multimedia. Optimizing for the Overall Throughput is just as easy, and required to set a flag in both the analysis and the simulations. 6.5 Conclusion In this chapter, we proposed centralized M A C adaptation algorithms for 802.1 le wire-less networks. The algorithms change the Contention Window Parameters following the present condition of the network. This study shows clearly the advantage of the adaptive schemes over the fixed-parameter 802.1 le wireless networks. Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 120 The analytical algorithm calculates the maximum theoretical throughput that the net-work can have under optimal conditions. It could be used as a benchmark for other adap-tive schemes. Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 121 Figure 6.4: Static vs. Station-Count Algorithm - Throughput Contention Window Parameters vs Time CWmin of Priority A CWmin of Priority B 500 1000 1500 2000 Time (sec) 2500 3000 Figure 6.5: Static vs. Station-Count Algorithm - C W M I N Change Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 122 Wireless Network Saturation Throughput vs Time 900 I 1 1 1 1 0 500 1000 1500 2000 2500 3000 Time (sec) Figure 6.6: Static vs. Throughput Derivative Algorithm - Throughput Low Pass Filtered Saturation Throughput vs Time 800 i 1 1 1 1 Time (sec) Figure 6.7: Static vs. Throughput Derivative Algorithm - Low Pass Filtered Throughput Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 123 x i n 4 Throughput Derivative of Priority A vs Time Time (sec) Figure 6.8: Static vs. Throughput Derivative Algorithm - Derivative Figure 6.9: Static vs. Throughput Derivative Algorithm - C W M I N Change Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1 le Wireless LANs 124 Static vs. Adaptive EDCA for Priority A Throughput 0.9 0.8 0.7 a 0.6 a 0.5 o 0.4 h 0.3 0.2 0.1 0 5= -Analysis - Priority A Throughput -Simulation Adaptive - Priority A Throughput Simulation Static - Priority A Throughput 1111111111111111111111 11111111111 M 111111111111111111 nTTTi i 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 Stations Figure 6.10: Static vs. Analytical Algorithm for Priority A Static vs. Adaptive EDCA for Priority B Throughput 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 Stations Figure 6.11: Static vs. Analytical Algorithm for Priority B Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 125 Proof of Optimization of Priority A Throughput 0.8 0.7 0.6 • t 1 4 7 1013 1619 22 25 28 313437 43 4346 4952 55 58 Stations -Simulation Adaptive • Priority A Throughput -Analysis • CWminA = 7 CWmax^l = 15 Analyse - CWminA = CWma<A = 25 12 Analysis • CWminA=27 CWmaxA = 55 -Analysis - CWminA: CWma>cA=55 -Analysis - CWmin A CWmaxA=115 - Analysis - CWminA CWmaxA=145 37 = 57 72 Figure 6.12: Proof of Optimization for the Analytical Algorithm Chapter 7 Conclusions and Future Research In this thesis, we proposed a new analytical model for finite-load wireless LANs, based on IEEE 802.11 and 802.1 le MACs. An elaborate and detailed framework has given the model a high degree of accuracy which was observed when matching the results with a highly detailed W L A N simulator. Because of the ability to compute results for any amount (and type) of input traffic, our Enhanced Finite-Load (EFL) model approximates WLANs behaviour more realistically than Saturated models which assume backlogged queues. The highly-accurate Saturation model that we propose can help study congested WLANs, where multiple users are attempting to access the wireless network with high volumes of traffic. The models are very accurate from the M A C layer point of view. However, the models currently do not include all details of PHY layer effects. Key aspects of PHY effects such as multi-rate operation and bit errors can be easily incorporated in our model. 126 Chapter 7. Conclusions and Future Research 127 The models and the proposed algorithms can be used in a variety of applications, ranging from wireless multimedia to network design. The models can help researchers understand better the complex behavior of probabilistic system such as WLANs. The models can be easily integrated as algorithmic procedures in an Access Point to help the scheduler take its decisions, and enforce Quality-of-Service guarantees or Access Control policies. For example, the Enhanced Finite-Load models are especially efficient if used in decid-ing Access Control. As the shift from finite-load to saturation happens quite rapidly and in an exponential way, the Access Point can accept a new traffic flow or reject it if it causes a degradation in network performance. The AP can use the E F L to take such decisions and many other applications are also possible. The main objectives of this work were to develop an accurate modeling platform for 802.11 and 802.lie WLANs under finite-load and saturation conditions, and the enhance-ment of the Saturation Throughput in 802.1 le WLANs. In Chapter 3, we presented an accurate and fairly complicated mathematical model for 802.11 WLANs called the "Enhanced Finite-Load Model (EFLM) for IEEE 802.11 Wire-less LANs". E F L M uses a dual queuing model where a node is represented by one queue-ing model, and the wireless medium by the other. The model introduces many probabilities and quantities that were not used in previously published finite-load models, such as the probability of direct transmissions Pbackoff, and the probability of witnessing incomplete transmissions from other stations Px. The model yields a set of non-linear equations, which can be solved with the algorithm listed in Appendix A. Chapter 7. Conclusions and Future Research 128 Chapter 4 presented a mathematical finite-load model for 802.lie WLANs, and intro-duced new quantities to account for multiple priorities, such as the ratio of the presence of the traffic from one priority compared to another, and contention zones that depend on the AIFS periods of the priorities. The model was contracted with the same concepts as E F L M in Chapter 3, but the extension of the E F L M model to 802.lie WLANs is more complicated because of the prioritization mechanisms that were introduced in [7] such as the AIFS, and the different CW parameters for each AC. In Chapter 5, we presented a mathematical model for saturated 802.1 le WLANs, that corrects the model proposed by Robinson and Randhawa in [3]. Due to a misinterpretation of the 802.1 le draft, the model had a flaw. We removed the probabilities of post-collision that Robinson and Randhawa had included, and re-built the model based on the new as-sumptions. Chapter 6 presented three algorithms, that were devised to enhance the Saturation Through-put in saturated 802. l i e WLANs. The proposed algorithms are based on adaptively chang-ing the Contention Window (CW) parameters, trying to find the optimimum CW parameter values. The Station-Count Algorithm (SCA) is a very simple algorithm and one of the ear-liest of our work. The Analytical Algorithm uses the the mathematical model of Chapter 5 to find directly the optimum values. The Throughput Derivative Algorithm (TDA) is the algorithm that has the most potential, due mainly to its extreme adaptability and flexibility. We will also list the possible research problems that could constitute a continuation of the work in this thesis. Chapter 7. Conclusions and Future Research 129 1. In Chapters 3, 4 and 5, the mathematical models of 802.11 and 802.lie WLANs assume ideal wireless channel conditions. In real networks, different stations can send with different bit rates. To address the issue of differing bit rates, the stations in the models can be extended to have different success and collision times, Ts and Tc. But when two stations with two different collsion times collide, what is the resulting collision time? Surely, the longer one, but what are the probabilities of such collisions happening, and how could the average collision time be calculated from the stations' collision times? Some of these questions have been partially answered in [9] and [12]. But much more work is still needed. 2. The same can be noted for bit errors. In real networks, the radio links that are established between pairs of stations will certainly undergo bit errors. Compared to differing bit rates, it seems easier to solve the issue of bit errors, where stations respond to bit errors the same way they respond to collisions. However, unlike the probability of collision which depends on the number of stations in the network, the bit error probability is usually assumed constant for a given radio link, and can differ from one link to another. 3. Chapter 4 has introduced the concept of the ratio of the presence of one priority compared to another, called Ratioxy- This ratio quantifies the presence of priority X compared to the presence of priority Y, which can be explained as the ratio of the number of transmissions from all queues of priority X over the number of trans-missions from all queues of priority Y in a unit time. This ratio consists of several components that affect its value, and their inter-dependence is still a mystery. It Chapter 7. Conclusions and Future Research 130 would be interesting to research the correct expression of this quantity. 4. In Chapter 6, the algorithms also use the ideal-condition assumptions. More robust and adaptive algorithms can be devised to handle realistic channel conditions, such as bit errors, and different bit rates. Bibliography [1] G. Fleishman, "Grand Haven, Michigan, Cuts the Cord", Wi-Fi Networking News, July 29, 2004, http://wifinetnews.com/archives/004039.html [2] Matthew Davis, "Wi-fi cities spark hotspot debate", BBC News, October 20, 2005, http://news.bbc.co.Uk/l/hi/technology/4351400.stm [3] J. Robinson, and T. Randhawa, "Saturation Throughput Analysis of IEEE 802.lie Enhanced Distributed Coordination Function", in IEEE Journal on Selected Areas in Communications, pp. 917 - 928, June 2004 [4] S. El Housseini, and H. Alnuweiri, "Adaptive Contention-Window M A C Algorithms for QoS-Enabled Wireless LANs", IEEE International Conference on Wireless Net-works, Communications and Mobile Computing, vol. 1, pp. 368 - 374, June 2005 [5] IntelliGraphics, "Introduction to IEEE 802.11", http://www.intelligraphics.com/articles/80211 _article.html [6] IEEE P802.11, IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, November 1997 131 BIBLIOGRAPHY 132 [7] IEEE P802.11 Task Group E, MAC Enhancements for Quality of Service, IEEE P802.11,2005 [8] S. Choi, J. Del Prado, S. Shankar, S. Mangold, "IEEE 802.lie Contention-Based Channel Access (EDCF) Performance Evaluation", in Proceedings IEEE ICC03, vol. 2, pp. 1151 - 1156, May 2003 [9] G. Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function", in IEEE Journal on Selected Areas in Communications, vol. 18, issue 3, pp. 535 - 547, March 2000 [10] G. Zeng, I. Chlamtac, "A Finite Queueing Model for IEEE 802.11 M A C Protocol", in IEEE Vehicular Technology Conference, vol. 4, pp. 2037- 2041, May 2004 [11] M . Ozdemir, A.B. McDonald, "A Queuing Theoretic Model for IEEE 802.11 DCF using RTS/CTS", in IEEE Thirteenth Workshop on Local and Metropolitan Area Net-works, pp. 33 - 38, April 2004 [12] G. Bianchi, "IEEE 802.11 Saturation Throughput Analysis", in IEEE Communica-tions Letters, vol. 2, issue 12, pp. 318 - 320, December 1998 [13] A.N. Zaki, M.T. El-Hadidi, "Throughput Analysis of IEEE 802.11 DCF under Finite Load Traffic", in First International Symposium on Control, Communications and Signal Processing, pp. 535 - 538, March 2004 [14] O. Tickoo, B. Sikdar, "A Queueing Model for Finite Load IEEE 802.11 Random Access MAC", in IEEE International Conference on Communications, vol 1, pp. 175 - 179, June 2004 BIBLIOGRAPHY 133 [15] O. Tickoo, B. Sikdar, "Queueing Analysis and Delay Mitigation in IEEE 802.11 Random Access M A C Based Wireless Networks", in The Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 1404 -1413, March 2004 [16] S.-T. Cheng, M . Wu, "Performance Evaluation of Ad-Hoc W L A N by M / G / l Queue-ing Model", International Conference on Information Technology: Coding and Com-puting, vol. 2, pp. 681 - 686, April 2005 [17] J. Sudarev, L. White, S. Perreau, "Performance Analysis of 802.11 C S M A / C A for Infrastructure Networks under Finite Load Conditions", in The 14th IEEE Workshop on Local and Metropolitan Area Networks, pp. 1- 6, September 2005 [18] Y. Zhu, Z. Niu, "A Novel Queueing Model for Finite Load IEEE 802.11 WLANs", in IEEE Vehicular Technology Conference, vol. 4, pp. 1352 - 1356, September 2005 [19] E. Ziouva, T. Antonakopoulos, "The Effect of Finite Population on IEEE802.il Wireless LANs Throughput/Delay Performance", in The 2002 Mediterranean Elec-trotechnical Conference, May 2002 [20] G. R. Cantieni, Q. Ni, C. Barakat, T. Turletti, "Performance Analysis under Finite Load and Improvements for Multirate 802.11", INRIA R&D, vol. 28, issue 10, pp. 1095 - 1109, June 2005 [21] O. Abu-Sharkh, A. H. Tewfik, "Performance Analysis of Multi-Rate 802.11 WLANs Under Finite Load and Saturation Conditions", in IEEE Vehicular Technology Con-ference, vol. 4, pp. 2652 - 2657, September 2005 BIBLIOGRAPHY 134 [22] K. Medepalli, F. A. Tobagi, "System Centric and User Centric Queuing Models for IEEE 802.11 based Wireless LANs", in Proceedings of IEEE Second International Conference on Broadband Networks, October 2005 [23] P. E . Engelstad, O. N. Osterbo, "Analysis of QoS in W L A N " , Telenor R&D, pp. 132-147, January 2005 [24] D. Vassis, G. Kormentzas, "Delay Performance Analysis and Evaluation of IEEE 802.1 le E D C A in Finite Load Conditions", in IEEE International Conference on Wireless Personal Communications, vol. 34, pp. 29-43, August 2005 [25] Y. Xiao, "Performance Analysis of IEEE 802.1 le EDCF under Saturation Condi-tion", IEEE International Conference on Communications, vol. 1, pp. 170 - 174, June 2004 [26] T.-C. Tsai, M.-J. Wu, "An Analytical Model for IEEE 802.lie EDCA", in IEEE In-ternational Conference on Communications, vol. 5, pp. 3474 - 3478, May 2005 [27] H. Zhu, I. Chlamtac, "An Analytical Model for IEEE 802.lie EDCF Differential Services", in Proceedings of the 12th International Conference on Computer Com-munications and Networks, pp. 163 - 168, October 2003 [28] J. Hui, M . Devetsikiotis, "A Unified Model for the Performance Analysis of IEEE 802.1 le EDCA", in IEEE Transactions on Communications, vol. 53, issue 9, pp. 1498- 1510, September 2005 BIBLIOGRAPHY 135 [29] J.W. Tantra, C. H. Foh, A. B. Mnaouer, "Throughput and Delay Analysis of the IEEE 802.1 le E D C A Saturation", in IEEE International Conference on Communications, vol. 5, pp. 3450 - 3454, May 2005 [30] K. Xu, Q. Wang, H. Hassanein, "Performance Analysis of Differentiated QoS Sup-ported by IEEE 802.1 le Enhanced Distributed Coordination Function (EDCF) in W L A N " , in IEEE Global Telecommunications Conference, vol. 2, pp. 1048 - 1053, December 2003 [31] Z.-N. Kong, D.H.K. Tsang, B. Bensaou, D. Gao, "Performance Analysis of IEEE 802.1 le Contention-Based Channel Access", in IEEE Journal on Selected Areas in Communications, vol. 22, issue 10, pp. 2095 - 2106, December 2004 [32] J. Zhao, Z. Guo, Q. Zhang, and W. Zhu, "Distributed M A C Adaptation for W L A N QoS Differentiation", in IEEE Global Telecommunications Conference, vol. 6, pp. 3442-3446, December 2003 [33] F. Cali, M . Conti, and E. Gregori, "IEEE 802.11 Protocol: Design and Performance Evaluation of an Adaptive Backoff Mechanism", in IEEE Journal on Selected Areas in Communications, vol. 18, issue 9, pp. 1774-1786, September 2000 [34] L. Romdhani, Q. Ni, T. Turletti, "Adaptive EDCF: Enhanced Service Differentiation for IEEE 802.11 Wireless Ad-hoc Networks", in IEEE Wireless Communications and Networking, vol. 2, pp. 1373 - 1378, March 2003 [35] X. J. Dong, M . Ergen, P. Varaiya, and A. Puri, "Improving the Aggregate Throughput of Access Points in IEEE 802.11 Wireless LANs", in Proceedings of the 28th Annual BIBLIOGRAPHY 136 IEEE International Conference on Local Computer Networks, pp. 682-690, October 2003 [36] Y. Pourmouhammadi, S. El Housseini, and H. Alnuweiri, "An Improved Saturation Model for IEEE 802. l i e WLANs", To be submitted to IEEE Communications Letters [37] J. Choi, J. Yoo, S. Choi, and Chongkwon Kim, "EBA: An Enhancement of the IEEE 802.11 DCF via Distributed Reservation", in IEEE Transactions on Mobile Comput-ing, vol. 4, pp. 378-390, July 2005 [38] E. Winands, T. Denteneer, J. Resing, R. Rietman, "A Finite-Source Feedback Queue-ing Network as a Model for the IEEE 802.11 Distributed Coordination Function", in The Fifth European Wireless Conference, February 2004 [39] M . Garetto, C.-F. Chiasserini, "Performance Analysis of the 802.11 Distributed Coor-dination Function Under Sporadic Traffic", JFIP Networking Technical Report, May 2005 [40] Danielle Dunne, "What is a wireless LAN?", CNN, May 10, 2001, http://archives.cnn.com/2001/TECH/ptech/05/10/what.is.WLAN.idg/index.html [41] Wikipedia, "Wireless L A N " , Wikipedia, http://en.wikipedia.org/wiki/WLAN [42] D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1987 [43] S. El Housseini, and H. Alnuweiri, "An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs", Submitted to IEEE Transactions on Communications, De-cember 2005 B I B L I O G R A P H Y 137 [44] S. E l Housseini, and H. Alnuweiri, "A Finite-Load Model for QoS-Enabled IEEE 802.1 le WLANs" , To be submitted to IEEE Transactions on Communications 137 Appendix A MATLAB Algorithm for Solving Finite-Load Models - The Non-Linear Set of Equations All these equations form a non-linear set. This set could be solved with MATLAB. Since this set is not the usual one of k equations with k unknowns, a different approach should be taken. We used iterations to solve this set, and organized the equations into a large function. This function takes as argument a vector of values, and returns the same vector with the new updated values. Say the function's name is FiniteLoad, then: [p, Pidie, P, W, Wp, nnetk] - FiniteLoad (p, Pidle, p, W, Wp, nnetk) We laid the equations in FiniteLoad in the following order (Equation numbers are dif-ferent for 802.lie WLANs): 1. /v,(Eq. 3.5) 138 APPENDIX A 139 2. Wp (Eq. 3.6) 3. W(Eq. 3.7) 4. /, (Eq. 3.39) 5. nnetk (Eq. 3.38) 6. Pidle (Eq. 3.41) 7. Pbusy (Eq. 3.42) 8. P[NT] (Eq. 3.2) 9. p(Eq. 3.1) 10. l/u(Eq. 3.10) 11. p = ,l/p Note that p was placed the last equation in FiniteLoad. The return vector returns the new values computed with the old ones. Proceeding with solving this set, we devised a smart algorithm that takes advantage of the structure of FiniteLoad. The algorithm goes as follows: We should note that if the arrival rate is larger than the service rate, the system won't converge. This is why we placed the SaturationCondition If statement in the algorithm. The algorithm assigns in each of the SolveLoops, and in the FinalLoop, p to a fixed value (the third member of vector X which is p is assigned to a fixed value in each iteration). The other arguments of X are passed to FiniteLoad and then saved into X again from the previous iteration. 139 APPENDIX A 140 Algorithm 4 - The Non-Linear Set of Equation Solving Algorithm X i = [ p _ i n i t , P i d l e _ i n i t , r o _ i n i t , Wp_init, W_init, P i _ k n e t _ i n i t ] d = 6.5 Oldro =0.5 Minim = 1 Bestro = ® IterationsLoop: For j = 1 to 9 d = d / 2 X = X i SolveLoopl: For i = 1 to 5 X(3) = Oldro + d X = FiniteLoad (X) End SolveLoopl D i f f l = AbsoluteValue (oldro + d - X (3)) X = X i SolveLoop2: For i = 1 to 5 X(3) = Oldro - d X = FiniteLoad (X) End SolveLoop2 D i f f 2 = AbsoluteValue (oldro - d - X (3)) I f D i f f l > D i f f 2 Oldro = Oldro - d Else Oldro = Oldro + d End I f End IterationsLoop SaturationCondition: I f Minim > Q.01 Bestro = 8.999 End I f SaturationCondition X = X i FinalLoop: For i = 1 to 6 X(3) = Bestro X = FiniteLoad (X) End FinalLoop 140 APPENDIX A 141 The algorithm works as follows: it searches for the value of p in the range [0,1] that causes the least error compared with X(3). First, the algorithm evaluates two values of p, 0.75 and 0.25. Then it computes the differences of the results with 0.75 and 0.25 respec-tively, and stores the differences in Diff 1 and Diff2. Say for example Diff2 is smaller. The algorithm takes 0.25 then as the center, and the next two values of p that are evaluated are 0.125 and 0.375. As the algorithm goes through its iterations, it closes on the value of p that causes the least error from the constant value that is fed to it. 141
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Analytical modeling of medium access control in finite-load...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Analytical modeling of medium access control in finite-load and saturated wireless LANs El Housseini, Samer 2006
pdf
Page Metadata
Item Metadata
Title | Analytical modeling of medium access control in finite-load and saturated wireless LANs |
Creator |
El Housseini, Samer |
Date Issued | 2006 |
Description | The IEEE 802.11 standard provides the specifications for a Wireless Local-Area Network (WLAN) technology, commonly known as Wi-Fi. IEEE 802.11 uses an Ethernet-like contention-window mechanism to resolve the multiple-access problem to the wireless channel. Essentially, a wireless station doubles its contention window size after detecting a frame collision. Although this method is effective in reducing collisions on the channel, it increases packet overhead which results in reducing the throughput. In general, the performance of the WLAN varies widely depending on the number of customers in the network coverage area and the shape of the traffic on the channel. A few analytical models have been proposed over the past few years to understand the behavior of WLANs. Although insightful, most of these models were based on a highly-simplified "saturated" networks model in which all wireless stations behave like traffic source with infinite number of frames to transmit. The saturation assumption is useful in that it leads to simple steady-state models with fixed transition probabilities. However, it is not realistic to assume that wireless stations are always attempting to transmit frames, in real networks. This thesis is concerned with the development of improved analytical models for nonsaturated, or finite-load, WLANs and also propose enhancements to existing saturation WLAN models. In particular, we have developed two analytical models for WLANs with finite load. One model for the standard IEEE 802.11 WLAN and the second for the quality-of-service enabled WLAN described by the IEEE 802.11e standard. The proposed models capture the probabilistic nature of wireless networks and the interdependencies among wireless stations. In our analysis, we rely on novel schemes that use coupled station-view and network-view models to compute the overall throughput, collision probability, and delay in a WLAN. When compared to other recent work, our results prove to be the most accurate. We complement our work on finite-load models by presenting a more accurate model for IEEE 802.11e WLANs operating under saturation, and propose a few adaptive contention-window algorithms for maximizing the frame transmission rate and consequently the saturation throughput. We show through simulation that the proposed algorithms increase the throughput by several multiples. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-01-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0064899 |
URI | http://hdl.handle.net/2429/18528 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2006-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2006-199695.pdf [ 5.94MB ]
- Metadata
- JSON: 831-1.0064899.json
- JSON-LD: 831-1.0064899-ld.json
- RDF/XML (Pretty): 831-1.0064899-rdf.xml
- RDF/JSON: 831-1.0064899-rdf.json
- Turtle: 831-1.0064899-turtle.txt
- N-Triples: 831-1.0064899-rdf-ntriples.txt
- Original Record: 831-1.0064899-source.json
- Full Text
- 831-1.0064899-fulltext.txt
- Citation
- 831-1.0064899.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0064899/manifest