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 Network (WLAN) technology, commonly known as Wi-Fi. IEEE 802.11 uses an Ethernetlike 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 nonsaturated, 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 qualityof-service enabled WLAN described by the IEEE 802.1 le 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 onfinite-loadmodels by presenting a more accurate model for IEEE 802.lie WLANs operating under saturation, and propose a few adaptive contentionwindow 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. Table of Contents Abstract • Table of Contents ii 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 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 9 24 3.1 Introduction 24 3.2 System Model and Assumptions 26 3.3 Basic Analysis 28 iv TABLE OF CONTENTS 3.4 3.5 3.6 3.7 3.8 4 The Tagged Node Queuing Model 33 3.4.1 33 Service Time Estimation 3.4.2 Service Time Distribution (Tagged Node Queuing Model) 3.4.3 Throughput and Delay 41 3.4.4 Bursty Source 42 . . . . Whole Network Queuing Model 37 43 3.5.1 Estimation of the Network Service Time and Utilization Rate 3.5.2 Estimation of P I D L E and P B U S Y . . 43 45 Multi-Load and Multi-Rate Wireless LANs 46 3.6.1 Multi-Load Wireless LANs 46 3.6.2 Multi-Rate Wireless LANs . . 48 Simulation versus Numerical Results 49 3.7.1 Numerical Example of the Service Time 50 3.7.2 Results 50 Conclusion A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 53 60 4.1 Introduction 60 4.2 System Model and Assumptions 63 4.3 Basic Analysis 64 4.3.1 Estimation of the Collision Probability 64 4.3.2 Different AIFS Periods and Slot Occupancy Weighting 66 4.4 Tagged Node Queuing Model 69 4.4.1 Service Time Estimation (Node Queuing Model) 70 4.4.2 Ratio Selection 75 4.4.3 Service Time Distribution 80 4.5 Whole Network Queuing Model 82 4.6 Extending the Model to Multiple Priorities 83 4.7 Numerical Results 84 4.7.1 Numerical Example for Service Time 85 4.7.2 Results 85 4.8 5 v Conclusion An Improved Saturation Model for IEEE 802.11e WLANs 87 92 5.1 Introduction 92 5.2 Model Development 94 5.3 Slot Occupancy 96 5.4 Throughput Analysis 99 5.5 Simulation Results 101 TABLE OF CONTENTS 6 7 vi 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 . Ill 6.3.1 The Station-Count Algorithm (SCA) Ill 6.3.2 The Throughput Derivative Algorithm (TDA) 113 6.3.3 The Analytical Algorithm 116 6.4 Simulation Results 6.5 Conclusion . Conclusions and Future Research 117 119 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 8 0 2 . 1 1 Layer Model [5] 9 2.2 AIFS Relationships [7] 13 2.3 EDCATXOP[8] 14 2.4 Exponential Distribution Error 22 3.1 Tagged Node Queuing Model 26 3.2 Network Queuing Model . 27 3.3 Finite Load Model Architecture 29 3.4 Service Time Distribution Approximation for Typical p 38 3.5 Service Time Distribution Approximation for Large p 39 3.6 Utilization vs. load for W L A N with 4 , 12, and 2 0 stations 54 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 56 3.9 Waiting time T Q 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 . 57 3.11 Key Quantities vs. load for a Multi-Load W L A N with 4 stations 58 3 . 1 2 Waiting time T Q vs. load for a Multi-Load W L A N with 4 stations . . . . 59 4.1 Tagged Node Queuing Model 62 4.2 Network Queuing Model 62 4.3 Slot Occupancy Markov Chain (taken from [3]) 67 4.4 Demonstration of the Class Ratio 76 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 90 4.8 Waiting time, or Delay, W Q for Priority A vs. load for W L A N with 4 , 12, 5.1 and 2 0 stations 91 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 T D A 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 w 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 p X LIST OF SYMBOLS xi queueTx Average Number of Successful Transmission Slots from the Tagged Q otherrx Average Number of Successful Transmission Slots from Other Nodes Px Portion of Frames Arriving to an Empty Queue with Busy Medium px Portion of Frames Arriving to an Empty Queue x with Busy Medium PotherCx Average Number of Collisions from Other Nodes P otherTx Average Number of Successful Transmissions from Other Nodes Po Portion of Transmissions from Other Nodes that results in Collisions T Number of Slots that a Successful Transmission takes to complete s Number of Slots that a Collision takes to complete b(t) Proposed Service Time Distribution of the Tagged Node bnetit) Proposed Service Time Distribution of the Wireless Medium Bis) Laplace Transform of the Proposed Service Time Distribution Qiz) PGF of the Queue Length Distribution of the Tagged Node QnetiZ) PGF of the Queue Length Distribution of the Wireless Medium Queue Length Probabilities of the Tagged Node nnet k Queue Length Probabilities of the Wireless Medium Average Queue Length Variance of the Average Service Time Average Waiting Time Average Delay pN 1 Probability of Counting j Slots before the first Backoff-Counter fires net Expected Value of P . N Ratio of Idle Slots in a Wireless Medium Transmission Cycle Rs P, Zonej Probability of Transmission in Contention Zone i P. Z=l Pc Zonei Probability of Transmission in Contention Zone i r tr x £ Pc Probability of Collision of Priority x in Contention Zone i Probability of Collision of Priority x in Contention Zone / b Steady State Probabilities of the Slot Occupancy Markov Chain RatioxY Av. Number of Successful Transmissions from Y in X's Service Time btjc Steady State Probabilities of the Backoff Markov Chain t LIST OF SYMBOLS Pj Average Probability of Collision for Priority j E Expected Length of the Transmission Duration D 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 E Expected Length of the Transmission Duration D Expected Payload of Priority j Tj Average Throughput of Priority j xii List of Abbreviations AC Access Category ACK Acknowledge Frame AIFS Arbitration Inter-Frame Spacing AP Access Point CFP Contention-Free Period CP Contention Period CSMA/CA Carrier Sense Multiple Access/Collision Avoidance CTS Clear To Send CW Contention Window DCF Distributed Coordination Function DIFS D C F Inter-Frame Spacing DVD Digital Video Disc EDCA Enhanced Distributed Channel Access EFL Enhanced Finite-Load EIFS Extended Inter-Frame Spacing FIFO First In First Out HCCA H C F Controlled Channel Access HCF Hybrid Coordination Function IFS Inter-Frame Spacing IP Internet Protocol IT Information Technology LAN Local Area Network MAC Medium Access Control xiii LIST O F ABBREVIATIONS 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 I E E E 8 0 2 . i l Task Group N TXOP Transmission Opportunity VoIP Voice Over IP Wi-Fi IEEE 802.11 Wireless Local Area Network WLAN Wireless Local Area Network WWiSE World-Wide Spectrum Efficiency xiv Acknowledgements I would like to thank my supervisor, Dr. Hussein Alnuweiri, for all the guidance, support, and time that he offered. Ifirmlybelieve that without all his expertise and understanding, 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, atmosphere 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 thefirstcity 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 certainly 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 simulation models for wireless local area networks, especially that the literature was lacking accurate models in this area. Also, with the new wireless revolution being multimediacentric, 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, transmitting 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 wireless medium. Typical bit rates range from 11 Mbps for 802.1 lb networks, to 54 Mbps for 802.1 l g 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-ofService (QoS) in W L A N s 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 D V D 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 reception 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 general, 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 wireless 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 number 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. 5 Chapter 1. Introduction 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 Outputs: Waiting Time, Queue Length, etc -Probability of Busy Medium Wireless Medium Modeling Framework BO Wireless Medium Queuing Model 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 W L A N s 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 W L A N s operating 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 1.4 7 Thesis Outline Chapter 2 gives an overview of 802.11 networks and its underlying technology. It describes the modes of operations, and access protocols. The same is done for 802.1 le networks. 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 thefinite-loadcondition. Chapter 4 extends the model in Chapter 3 to 802.lie networks. Chapter 5 introduces the improved mathematical 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 L A N s 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 OSI Logical Link Control (LLC) IEEE 802.11 Media A c c e s s Control (MAC) Frequency Hopping Spread Spectrum PHY Direct Sequence Spread Spectrum PHY Infared PHY MAC XPHY 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 Access 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 D C F 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 P C F mode. D C F 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 D C F 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. D C F 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 D C F function, now called the H C F function (Hybrid Coordination Function), supports on top of it two other functions: the E D C A and the H C C A . 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 InterFrame Spacing (AIFS) periods according to their traffic type. Furthermore, each A C has a different minimum and maximum C W periods ( C W M I N and C W M A X ) , as well as separate C W variable for each A C . 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. 13 C h a p t e r 2. O v e r v i e w of Wireless L o c a l A r e a N e t w o r k s °f77777 H77777 AIFSQ] Immediate access when .AIFS[i] Medium is free >= DIFS/A1FS[i] DIFS kO- DIFS/AIFS 1 Contention Window O f PIFS »—is S1FS Busy Medium Defer Access E f T I T Backoff Slots I l I In 22 Next Frame i Slot time Select Slot and Decrement Backoff as long ~ as medium is idle IS3 Figure 2.2: AIFS Relationships [7] C o n t e n t i o n W i n d o w 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 O p p o r t u n i t y The Transmission Opportunity (TXOP) is a new concept introduced in the 802.1 le specification. After contending for and winning the wireless medium, a station is granted a predetermined amount of time equal to the T X O P value of the winning A C . In this T X O P 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 exchanges (RTS, CTS, Data-ACK) should not overstep the T X O P 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 14 Chapter 2. Overview of Wireless Local Area Networks SIFS AIFS( UPJ + Backoff [M SIFS AlFSfUP) SIFS Post Backoff QoS Data(UP) ACK QoS Data(UP) ACK EDCF TXOP Umit ML >= 0 time gap' Figure 2.3: E D C A T X O P [8] sources. The T X O P concept also enhances the throughput, for the station spends more time sending frames, and less time contending for the medium. In mathematic-like descriptions, 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 effective 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 M A C - r e l a t e d probabilities is necessary to complete the mathematical 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 i n 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 i n hand. O n 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 a l l 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 i n the wireless channel without modeling the post-collision backoff 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 W L A N s 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 networkcentric, 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 chapters 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 transmissions 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 D C F 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 mathematical 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. A n 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 Appendix 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 transmission 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 W L A N s 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 2.5 19 IEEE 802.11e WLAN Saturation Models and Algorithms 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], X u , 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 differentAIFS-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 W L A N s , 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 C W Parameters 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 C W 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 statistics, 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 D C F 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 probability of collision. The approach in [35] uses different network parameters for optimization which are the D C F 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 parameters: C W M I N and C W M A X . Our improvement over other available algorithms was the amount of Saturation Throughput 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 flexibility and reduce long simulation times. A version of the software has been also evolved Chapter 2. Overview of Wireless Local Area Networks 22 E x p o n e n t i a l Distribution : M e a s u r e d and Ideal T 1 1— 1 i i — Exponential 0.032 - Ideal E x p o n e n t i a l 0.03 0.028 0.026 0.024 | 0.022 0.02 0.018 • 0.016 0.014 0.012 L J i i i i i 0 5 10 15 20 25 30 * V1 r > slots Figure 2.4: Exponential Distribution Error into a working M A C stack and ported to run on VxWorks. The simulator used in this thesis 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 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 interarrival 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 W L A N s rely on to operate properly. We also surveyed the finite-load models, saturation throughput models, 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. A n Access Point uses P C F to schedule transmissions of real-time traffic and important data in a collision-free environment. D C F 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. Thefirstmodel 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 saturates. 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 between two distinct queuing models, one representing the the other representing the tagged node (or user) view and 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 cumulative 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 simplifying 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 (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 (3.1) l 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... to Wireless Node Modeling Framework (Supplies the Node Queuing Model with accurate means and distributions) HUtilizationH Node Queuing Model -Probability of Busy Medium Wireless Medium Modeling Framework HO Wireless Medium Queuing Model Figure 3.3: Finite Load Model Architecture Outputs: Waiting Time, Queue Length, etc 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] + = l - ( l - p ) + (l-rP = 1 P[NT\QNE]P[QNE] b a c k o f f ).p (3-2) -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 transmission during a given time slot and (T? Pbackotr T A C K O F F ) where r is the probability of 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 W be the average backoff counter value used by the backoff process for every p transmission, or retransmission. The backoff process will virtually draw a number between 1 and 2 W after a successful transmission (or a collision) occurs. If the node has a nonp 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 W . The expression of the mean of this Geometric distribution is: p Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 31 which results in the following expression for r (3.4) l + W p Let I be the average backoff window size when a succesful transmission occurs given w a collision probability p. Then, I = CWmin{\ -p) + 2p(\- w p)CWmin + 4p (l - p)CWmin + .:. + (IpT^CWmin (3.5) 2 = CWmin m-2 (\- )J](2p) + (2prk 1 P k=0 and, W p (3.6) = IJ2 The variable m is the maximum number of retransmissions. We assume that 2 CWmin m 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 •W p (3.7) Note that for the purpose of computing the probability of collision p, the expression derived for W excludes direct frame transmissions (i.e. without backoff). In general, a p 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 W . p 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 i d e be the complement of Pbusy Then the portion of the transmitted frames that will go through a backoff process is given by: Pbackoff In other words, the probability — Pbackoff (3-8) (Pbusy+pPidle) 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 < W , because W is the average backoff window when direct transmission p are also included. From the network model point of view, P koff bac contributes to the accu- racy of calculating the time slots for the average network service time ( l / / i „ , ) , hence its e inclusion in computing W but not W . p 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 + 3p + ...\ + mp ~ = l + p + p + .. + p ~ = £ p , 2 1 m ' l 2 m 1 k=0 with m being the maximum number of retransmissions. Therefore, the expected number of transmission cycles that end in collisions is k Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 34 m-l CycleCx = J]p (3.9) k 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 P denote the portion of frames that arrive to an empty queue x 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. T is the time it takes to detect a collision, including PHY headers, RTS frame, c and then a deference period. Then, />, = ( l - p ) . P b u s y p + (l-p) N-l The factor p + (1 - p ) ^ is empirically included to adjust the impact of (3.11) 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 arc the other N - l nodes. But as p gets Pbusy 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 P busy 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 (P therTx) 0 and collisions arising from other nodes during (P therCx) 0 the service time of a single frame are given by the following probabilities, PotherT* = ^otherC* = P(N P(N- ~ 1) (3.12) 1) Po (3.13) O Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 36 The probability p represents the portion of transmissions from other nodes that results 0 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 following relations: othersS um Therefore, To illustrate the derivation of p , we will give a small example. Assume a W L A N with a 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 p which equals 0 P Po = 2(\-p) P 2-p +p (3.14) 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.T (3.15) c otherCx = (P - J ° )T 2(1 - p ) P otherCx i C (3.16) 0 Backoff = W + CycleCx.W p node7x = (1 - p )T (3.18) m s other7x = (P othaTx (3.17) - ^)T S (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 T , as follows: s b{t)=p .e-^'-^.u(t-T ) p s (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 T , which yields a non-Markovian service time distribution. The s function u(t - T ) is the Heaviside (or step) function shifted by T , and p s s p is the constant of the n.e.d. before shifting, expressed as a function of T and the average service time, p, s as follows, „.(HThis distribution captures the nature of the true service time PDF computed as the cascaded 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 X IQ" 39 True pdf v s . P r o p o s e d pdf 3 -2 -4 _j 100 1 150 1 200 1 250 1 300 i 350 1 400 i 450 i 500 i 550 slots 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 M A T L A B ) . 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~ 'b(t)dt = f e- p. .e-»" - ° u(t J J s s, (t T - T )dt = ^ ) p s MP o — (3.22) + S From which we can derive the PGF of the new service time PDF, as follows -M.i-z).T . c <Kz) = B [A(l - z)] = — - A(l-z) (3.23) + u p 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 1 + A(l _ )| *T (z-l)_ e s Z 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 N , q p + 2A V 2 2 U <'" N The quantity + ^a^f ' (3 26) 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 H = fn e-^ '- °Xt ( J T P Ts - V -fdt (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 increase dramatically as the network moves towards saturation. In queuing theory, delay is defined as the waiting time T of a queued frame from the instant it enters the queue until q the start of service. Similar to average queue size N , the average waiting time T is one q q of the Pollaczek-Khintchine formulae, expressed as follows 1 \p + 2A V„ 2 A[ 2 (3.28) 2(1 -p) _ In our wireless networks, delay is defined as the waiting time W of a frame from the q 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 W is equal to T plus the service time l/fi, minus the q q time it takes to successfully transmit a frame, T . Therefore the average waiting time, or s delay, has the following expression W = T + --T q q (3.29) s The next and important step of our analysis is to derive formulas for the important probabilities, P ie 3.4.4 B u r s t y Source id and Fbusy For that, we revert to the whole-network queuing model. 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 cr . The E F L model can be used as it is, and all of the above analysis is still 2 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: ' Batch _ AbB 1 ~ 2/i 2 (l-p) Bo- + o- l i \ 2 2 2 f a JH 2 2 (3.30) 1 + The average queue size can be derived by using Little's Law N 3a,ch q = AT q Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 3.5 43 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/fi net has three components: the average time of all backoff processes for all stations (nodes), the average frame length T expressed in time s slots, and the delay overhead introduced by collisions. Thefirstof 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: P j = P j slots N min (backoff_counter(i)) (3.31) 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 counters) fires. Let T„ be the expected value of the random variable P*J, i.e. et (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: — =T T N ml + p(T N s + net + (3.33) T) c Pnet and following a derivation process similar to that of the tagged node model, we have Pnetp = Pnet — ~ — (3-34) ~T S (3.35) = Pnet The probability distribution function of the network service time is: Ket(t) = Pne .e-^ '- .u(t ( - T) Ts) W (3.36) s This leads to an expression similar to that of the tagged node model but with different parameters: (l_^)(l_ ) TO-i) Qne,(z) - *NT (z-l) e z Unet s - U r Z e , TTT~. TT JN_fl- )] + y-nelp P-nelp (3-37) z J Taking the moments of Q ,(z) , we get the steady-state probabilities of the network ne nnetk, indicating that there are k frames in the network. *net = k {Qne,{z)y ., ° 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. Estimation of PIDLE and PBUSY 3.5.2 In this section, we complete our analytical model by deriving formulas for P i and i d e 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/p ,, and it includes the time for resuming backoff counters for an average ne 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 nnet s multiplied by the expected value of the first backoff counter to k fire (T ). k et This is not absolutely accurate since nnet s do not represent the probability of k 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 I is: s (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 = I + s 'T + s (3.40) p T c and we have, Pidle = 1- Pnel + Pnet Pbusy • R 1 - = s _ I ~ PnetiX ~ Rs) Pidle (3.41) (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 conclusion 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-p TjPi J i (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, W , Wj, P J Pj, etc ff, j p backo etc..., use the variables pj, 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 P ther7* and 0 P therCx 0 become PL*r, = Z PJ ( 3 - 4 5 ) i'=l, i*j and PothtiCxi = — 1 - J P ^' ^ 3 46 Po i= l,i*y The probability of collisions arising from other stations p becomes Q N 1 Pj Pi ^ 2(TV-1)- h v 2 P — (3-47) j .i=l,i*7 These changes will enable us to derive the Uj and p for each node. On the other hand, it y 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 p) + 2A*VZ q 2(1 *i 48 (3.48) -pj) 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 W - The equation in question becomes Av Pf = P j slots = min (backofLcounter(O) =z k=\ N k 1 \ (2W -p k N k (3.49) Av 2W.Av 2W Av with N w = Av 1=1 (3.50) N 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 P H Y rate, and therefore wireless nodes are synchronized to slot boundaries by pre-defined parameters relating to the underlying technology in operation. The only quantity that change in multi-rate W L A N s is the success duration T , which becomes specific to each node (T ). Therefore, a logic similar J s S 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 p , and other sa 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 3.7.1 50 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 CWMIN 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 otherC* backoff noder* otherr* Service Time (1/u) Collision probability p Utilization p 4.232877 8.668607 21.841324 94.978311 326.374658 453.704449 0.1480 0.199770 4.1656 6.8908 19.9435 94.9540 340.2596 449.8883 0.1483 0.2051 9.8937 87.7486 25.9287 95 842.5684 1061.1 0.2919 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. A l 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 T c and T have been calculated as the approximate sum of RTS, CTS, frame size, physical s 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 CW ¥ Y mm CWmax Retransmissions PHY Header RTS Size ACK Size 11 Mbps 32 1024 4 192 bits 160 bits 112 bits Slot Time Data Payload T T •*• s MAC Header CTS Size DIFS Time 20 microseconds 2304 bytes 24 slots 95 slots 272 bits 112 bits 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 number 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 T for a W L A N with batch arrivals for 4 q 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 ro vs. load with 04 stations —* —i O Enhanced F L Queueing Model Tickoo and Sikdar De-coupled Node Queuing Model Simulation f fl 20 40 60. . 80 load frames/sec 100 120 140 ro vs. load with 12 stations —* —I Enhanced F L Queueing Model Tickoo and Sikdar —De-coupled Node Queuing Model O Simulation Figure 3.6: Utilization vs. load for WLAN with 4, 12, and 20 stations 54 Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs p vs. load with 04 stations Q.1B , 0.14 0.12 0.1 Bianchi Satuartion Collision Probability —* Enhanced F L Queueing Model —I Tickoo and Sikdar -A—De-coupled Node Queuing Model O Simulation 0.08 0.06 • .04 0.02 60 80 load frames/sec p vs. load with 12 stations 0.35 0.3 0.25 •* —I O Bianchi Satuartion Collision Probability Enhanced F L Queueing Model Tickoo and Sikdar De-coupled Node Queuing Model Simulation 0.2 0.15 0.1 0.05 20 25 30 load frames/sec p vs. load with 20 stations 0.35 o2 0.3 -Bianchi Satuartion Collision Probability -Enhanced F L Queueing Model -Tickoo and Sikdar —De-coupled Node Queuing Model O Simulation 025 O CL I S 0 2 0.15 0.1 0.05 10 15 load frames/sec Figure 3.7: Collision probability,/? vs. load for WLAN with 4, 12, and 20 stations 55 Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 1/mu vs. toad with 04 stations 450 400 —* Enhanced F L Queueing Model —H—Tickoo and Sikdar A De-coupled Node Queuing Model O Simulation "5 1 300 ni e i- a o> 250 <*> 200 150 4 l - 120 60 80 load frames/sec 1/mu vs. load with 12 stations 1400 1200 140 —* —I Enhanced F L Queueing Model Tickoo and Sikdar — De-coupled Node Queuing Model O Simulation 1000 20 25 30 load frames/sec 2500 2000 1/mu vs. load with 20 stations —* Enhanced F L Queueing Model —I Tickoo and Sikdar -"=<—De-coupled Node Queuing Model O Simulation 1500 ?> 1000 500 10 15 load frames/sec 20 30 Figure 3.8: Service time vs. load for W L A N with 4, 12, and 20 stations 56 Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs 57 Wailing Time in Queue vs. load 40 60 load frames/sec 120 80 Figure 3.9: Waiting time T Q VS. load for W L A N with 4, 12, and 20 stations Waiting Time in Queue vs. load with 04 stations 800 - * — E n h a n c e d F L Queueing Model 700 O Simulation 600 CO I 500 ? £• 400 a> O 300 200 10 100 15 20 25 load batches/sec with 3 frames/batch 30 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 o vs. l o a d with 04 s l a t i o S i m of M e d i u m M o d a l of M e d i u m 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 a l of B S i m u l a t i o n of C M o d a l of D S i m u l a t i o n of C M o d e l of D O * * +• " :k— p v s . load with 04 - stations 0.1 O • .•9 S i m of A - * M o d e l of A S i m u l a t i o n of B 0.08 ( •I- 0.07 — M o d e l of B S i m u l a t i o n of C M o d e l of D x • .OS - S i m u l a t i o n of C 0.05 0.04 0.i.oaip0.02 • f .•1 120 140 160 load f r a m e s / s e c 1 / m u v s . l o a d with 04 180 200 stations r?- 250 JS 220 -J 200 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 g 100 —I 4- * 50 * M o d e l of B 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 80 100 120 140 160 load f r a m e s / s e c 180 200 220 Figure 3.11: Key Quantities vs. load for a Multi-Load WLAN with 4 stations 58 Chapter 3. An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs Waiting Time in Queue vs. load with 04 stations O 200 Sim of A - * — M o d e l of A + Simulation of B - M o d e l of B + 150 Simulation of C - * — M o d e l of D * Simulation of C Model of D 100 50 80 100 120 140 160 180 200 220 load frames/sec Figure 3.12: Waiting time TQ vs. load for a Multi-Load WLAN with 4 stations 59 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 security, has lead to the wide proliferation of wireless local area networks (WLANs) into the enterprise and consumer markets. Currently, W L A N s have become more than just a niche solution of extending the enterprise or institution network to unwired areas. For businesses, W L A N s 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 W L A N s are voice/video over W L A N and high bandwidth TCP connections. As it became commonly evident, joining data and multimedia 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 W L A N s 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 Application Transport Network Figure 4.1: Tagged Node Queuing Model Figure 4.2: Network Queuing Model 62 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 4.2 63 System Model and Assumptions We have based our finite-load analysis on an approach that requires the interaction between 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 cumulative 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 steadystate 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 simplifying 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 manner. 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 A C . 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 E s t i m a t i o n of the C o l l i s i o n P r o b a b i l i t y Let P[NT ] be the probability that the A queue, in a finitely-loaded (or non-saturated) A wireless network of N nodes (N = N + N ), is not transmitting in a given idle slot. Then A B as was established in [14], the probability of no transmission is: 65 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs P[NT ] = P[NT \QE ]P[QE ] A A A + A = 1.(1 -p )+p (l A — 1 — PA-T - A where P[QE ] A - A P[NT \QNE ]P[QNE ] A A A (4.1) T . Pbackoff/l) A PbackofiA denotes the probability that queue A is empty, P[QNE ] A that queue A is non-empty, and p = A /u A Category A). Clearly, P[QNE ] A =p A A A is the probability is the utilization parameter for AC A and P[QE ] A (Access = 1 - p . Note that P[NT \QNE ] A A is A expressed as the complement of the product (T Pbackoff/0, where T is the probability of A A frame transmission by queue A during a given time slot and v°back ffA is the probability that 0 a frame arrives from higher layers then waits through the backoff process in the station's A queue. Therefore, T P ackofM represents the probability of transmission given that the A b 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[NT ] B is, P[NT ] B = 1 - p .T . B B (4.2) Pbackofffi The backoff probability for AC , PbackotTA can be computed from the probabilities for the A busy and idle periods, using the approach given in Chapter 3. Let Pb usy be the probability that the medium is busy in a given time slot and let P n be the complement of Pbusy Then it e the portion of the transmitted frames that will go through a backoff process is given by: Chapter 4. A Finite-Load Model for QoS^Enabled IEEE 802.11e WLANs and for 66 ^backoff/1 - (Pbusy + PAPidle) (4.3) Pbackoffs - (Pbusy + pBPidle) (4.4) ACB, 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 Weighting 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 network 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 characteristic transmission and collision probabilities. To obtain the final average collision probability (p or p ), the collision probabilities of A B the contention zones are weighted by fe„ a discrete probability function, representing Slot Occupancy, and then summed. The slot occupancy p.d.f. b is modeled as a Markov chain t (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 defined in [9] for the sake of completeness. Assuming that there exists an AIFS. period difference between priority A and priority B queues, let P Zonei Tr transmission from any queue in Zone i, then be the probability of Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs P Zone Tr = 1 - P[NT f (4.5) A x 68 A and P Zone Tr = 1 - P[NT ] \P[NT ] ° N 2 (4.6) N A B Let PC Zonei be the probability of collision for priority x queue, in contention Zone /. x Then Pc Zone A = 1 - P[NT f A x (4.7) 1 A and Pc Zone A = 1 - P[NT ] *~ N 2 .P[NT ] ' L N A B (4.8) Also, for priority B, Pc Zone B = 1 - P[NT ] \P[NT \ N 2 A NB 1 B (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 b o = 1 mm(CWmaxA 1+ : 69 (4.io) .CWmaxa) Z IX-=i (1 - PrrZonej) and bi: = (1 - P rZonei-i).bi-i (4.11) T Therefore the final average collision probabilities p and p are then expressed as A min(C WmaXA p= A B ,CWmaxa) ^ Pc Zonei.bi A (4.12) i=i and PB = Pc Zone B 4.4 2 (4.13) Tagged Node Queuing Model As explained earlier, ourfiniteload 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. All other messages, transmissions, and interference from other nodes' queues or from co-located queues sharing the wireless medium will be modeled as delays in the service time. 70 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 4.4.1 Service Time Estimation (Node Queuing Model) In this section, we will derive a compound equation for the expected service-time (l/p ) x of queue x for the Tagged Node Queue server, using the basic queuing relation p = A /p . x x x 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 p . x 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 ( 1 + 2p . + 3p + ...l+mp ^" = \+p +p +..+p ~ ' 2 x 1 x 1 2 x l x x l m-l = £ P, k=0 k x with m being the maximum number of retransmissions. Therefore, the expected number of transmission cycles that end in collisions is m-l CycleCx = x YP J x (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. 71 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs The service time can be expressed in terms of its component delays as follows: 1 (4.15) = queueCx + otherCx^ + backoff + queueTx + o\hevTx x x x x 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 (otherTx ) in C cycles, the accumulated collisions (otherCx ) from other queues in x x C cycles, the accumulated collisions made by the tagged node queue (queueCx ) throughx out C cycles, and the successful transmission (queueTx ) or discarding of the frame by the x tagged node queue when the maximum number of retransmissions is exceeded. Now, let the probability P A denote the portion of frames that arrive to an empty queue EB 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, T is the time it takes to complete a successful transmission, s including the PHY headers overhead, RTS, CTS, and A C K frames, and finally the frame payload. T is the time it takes to detect a collision, including PHY headers, RTS frame, c and then some deference period. Then, N -l (4.16) P$ = (1 -P/O-JW PA + (1 -PA) A N B A also for class B , Pf = ( l - p ) . P fc B b u s y p + (l-p ) B Ng-1 B N B (4.17) Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs The factor p A + (1 - PA)^J^- is included to adjust the impact of view of the tagged node queue. When the queue utilization p Pbusy o u s y from the point of is small and the Tagged A Queue is empty, then the real contributors to P 72 are the other NA - 1 queue. But as p A gets larger, this equation becomes non-linear because of the inter-dependence between p A 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 successful transmissions (Pg and collisions ) lherTx (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, - PA{N KherTx = KherT* = PB(N A 1) + RatioAB.pBNB (4.18) and for class B, B - 1) + Ratio u .p N A A (4.19) and Kkercx = \PA(NA - D + Ratio .p N ] AB B (4.20) B also for class B, Kthercx = \PB(N - 1) + Ratio .p N ] B BA A (4.21) A 1 The ratios Ratio AB ' P o and Ratio A are quantities that indicate how each class "views" the B 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 Ratio BA 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 p represent the portions of transmissions from other nodes that B 0 result in collisions. But because of the existence of different zones, these probabilities have to go through the same process as p and p . However, a simple and logical approximation A B with an acceptable margin of error, is to get the average probability of collision p = (PA + p )/2 and proceed as if the probability of collisions from other stations is the same for all B classes. The expressions for p% and p are B 0 (4.22) PotherTx * sa 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 pA nt otherTx otherSum 1 and otherCx (4.23) (4.24) 74 Chapter 4. A Finite-Load ModelforQoS-Enabled IEEE 802.11e WLANs P^therCx ~ ^otherS unf Pt Therefore, pA olherCx _ pA ~ otherTx (4-25) A fo jjA Of^ I_ 1 from which the equations of p^ and p follow. B Now, the main quantities of the service time (1/UA) for class A are derived directly: queueCxA = CycleCxA-T (4.27) c A ^t^ < ^- > = W + CycleCxA.W^ (4.29) otherCxA = (Khercx backoff DA PoP\eb T - 4 A A queueTxA = (1 - p%)T (4.30) s otherTx = (P -^f).T A A otherTx (4.31) s — = queueCx + otherCxA + backoff A + queueTx + otherTx PA and for class B, A 28 A A (4.32) 75 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs — = queueCx + otherCx + backoffs + queueTx + otherTx B B B B (4.33) P-B 4.4.2 Ratio Selection Broadly speaking, Ratio AB 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 transmissions 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 CWMIN 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 decreasing its backoff counter by one, while queue Bfinishesits AIFS period, marked by an X in C h a p t e r 4. A F i n i t e - L o a d M o d e l for Q o S - E n a b l e d I E E E 802.11e W L A N s Queued Backoff Counter 1 2 3 Queue B Backoff Counter X 1 2 76 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 collision 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 i n the first timeslot, the counter combination changes to (2, 1), then to (1, 0) in the second timeslot. Thus, i n 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 regenerated 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 following 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 oo (4.34) where Total is the total number of combinations which is in this case equal to 3, meaning c 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 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 RatioAB = S uccesses 4 - = —— = 0.202 B b uccesses A 19.75 and 1 Successes RatiosA = Successes A = 4.937 RatioAB B The ratios calculated above match approximately the ratio values measured in simulations, which are Ratio ssim - 0.2152 and A Ratio ASim B = 4.462. (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) Queue A Successes Collisions 0 1.75 1.75 0 0 1.75 1 0 1 3.75 1 6 0 1 1 0 1 3.75 Total 19.75 Combinations Queue B Successes 0 0 0 0 1 1 1 0 1 4 5 Table 4.1: Successes and Collisions of the (3,3) pair combinations On the other hand, when the contention window CWMIN is greater than 3, then more complications arise. Assume the same example as above, but with CWMIN equal to 4 79 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 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. Ratio AB and Ratio BA have a strong relationship with the utilization rate p of their respective queues. When p and p are small A enough (i.e. light load supplied to the W L A N ) , then Ratio AB approximately to 1. It is when p and p A B and Ratio BA B get to be equal 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 p B Ratio = 1 - (1 - Ratio t)PA Ratio = 1 + (1 - ABSa AB BA (4.35) ABSa Ratio < 0.98: ,)p A (4.36) Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs on the other hand, if p 80 > 0.98, meaning that class B queues are saturated, then B Ratio AB = 1 + RatioABSM ~ PA (4.37) 1 RatiosA (4.38) I + RatioABS at PA RatioABSat is the ratio that exists when the queues are backlogged, i.e. saturated. Retransmissions and the number of queues are also factors of influence on the two ratio quantities. All 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), b (t), of any queue, x as a shifted negative exponential distribution (n.e.d.), where the amount of shift is equal to the average frame length T , as follows: s b (t)=p .e-^ •u(t - T ) A A p s (4.39) and for class B, bB(i) =i u.e-^- *\u(t-T ) B T p s (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. is: p 1 The PGF of the queue length distribution is: exruz-i) - z [l + ^ (1 - z)J <p(z) - z The average queue size N is: q p + i v„ 2 2 <' ~W^ N P+ <443) The variance V is: p V„ = 4 The average system time <-) 4 4 is: P + AV 2 T = A 2 P 2(1-p) q And finally, the average network delay V is: p (4.45) 82 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs W q 4.5 = T + q - - (4.46) T s 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 W in the expression of A P .. N The error introduced in this simplification is very small, especially that P,y/ and e Pbusy, which are the target probabilities of this section, are stable quantities and do not change with small variations of W . A The expression for P'J becomes P] = P . ; j slots = min (backoff_counter(/)) Ki<N =z 4=1 N k 1 \ (2W -f k N k (4.47) A 2W 2W A A Where /V is the total number of queues (N + N ) in the network, and j is the minimum A B number of time slots elapsed since the medium became idle until thefirstbackoff-counter (among iV counters) fires. Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 4.6 83 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 p , the same steps should be followed as before, by dividing the timeslots into x 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 Pc Zon A = 1- ei P Zonei = 1 Tr P[NT ] *-\P[NT ] '.P[NTC] .P[NT ] (4.48) P[NT ] \P[NT ] .P[NT ] .P[NT ] (4.49) N N A NC ND B N D NB A NC B C ND D Then the P Zonei probabilities are used to calculate the Slot Occupancy probabilities Tr bj, which in turn are used to weight the Pc Zonej probabilities to get the final average x collision probabilities p . x Additionally, the number of successful transmissions from other queues P x otherTx should be adjusted to take into consideration the presence of more priorities. The expression becomes KherT X = PA(N A - 1) + Ratio .p N AB B B + Ratio .p N AC C C + Ratio .p N AD D D (4.50) 84 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs The same should be done to Pt as follows otherCx pA = \PA(N otherCx 4.7 A - 1) + RatioAB-PBNB + Ratio .pcN AC c + Ratio .p N ] (4.51) AD D D 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 Rhandawa's collision probabilities in saturation ~p~ and A for each queue and other quantities to a high level of accuracy (confidence interval above 95%)[3]. Except for the collision probabilities p , we found all other quantities' to be stable, and x 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 p approaches 1 and the laws of queuing theory do not hold x 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 4.7.1 85 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. A l l 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 otherCx backoff nodeT!*: other Tx 15.03 26.28 19.64 14.78 31.05 19.05 230.42 12.96 108.8 94.16 367.79 522.93 0.3873 0.2646 94.18 376.24 529.21 93.28 3025.18 3476.75 0.4472 p Utilization p 0.3866 0.2589 0.999 20.06 238.94 137.4 92.87 3035.05 3524.3 0.4676 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 analytical model for QoS-Enabled W L A N s compared to simulations. A l 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 W versus input load for both queues q 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 number 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 CWminA 8 CWmaxA 128 CWminB 32 1024 CWmaxB Retransmissions 4 192 bits PHY Header 160 bits RTS Size 112 bits ACK Size Slot Time Frame Size Tc Ts MAC Header CTS Size DIFS Time AIFSA Period AIFSB Period 20 microseconds 2304 bytes 24 slots 95 slots 272 bits 112 bits 50 microseconds 0 slot + DIFS 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 probabilistic 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 varying 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 ro vs. load with 04 stations Simulation of A - E F L Q M of A Simulation of B E F L Q M of B 0.9 0.8 0.7 S. 0.6 fx! I § 0.4 0.3 0.2 0.1 h 020 load frames/sec eo 90 100 ro vs. load with 12 stations 0.9 Simulation E F L Q M of Simulation E F L Q M of of A A of B B 0.8 0.7 r? 0.6 j 0 5 0.3 0.2 0.1 load frames/sac ro vs. load with 20 stations 0.9 Simulation E F L Q M of Simulation E F L Q M of of A A of B B 0.8 h 0.7 r? 0.6 g 0.5 I s °-« 0.3 0.2 0.1 load frames/sec Figure 4.5: Utilization vs. load for WLAN with 4, 12, and 20 stations 88 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs p vs. load with 04 stations o —* o I Simulation E F L Q M of Simulation E F L Q M of of A A of B a |0.25f- I 0.2 V CL 0.151- 5 0.1 50 90 60 load frames/sec 100 p vs. load with 12 stations o * o + Simulation E F L Q M of Simulation E F L Q M of of A A of B B 9-- Si--" load frames/sec p vs. load with 20 stations o * o 4 S I Simulation of A EFLQM Of A Simulation of B E F L Q M of B 0.4 \ load frames/sec Figure 4.6: Collision probability, p vs. load for WLAN with 4, 12, and 20 stations 89 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 1/mu vs. load with 04 stations Simulation - E F L Q M of Simulation E F L Q M of of A A of B B •| 1000|- load frames/sec 80 90 100 1/mu vs. load with 12 stations Simulation E F L Q M of Simulation E F L Q M of & of A A of B B 4000 h load frames/sec 1/rnu vs. load with 20 stations Simulation E F L Q M of Simulation E F L Q M of 2. 1 of A A of B B 1.2 load frames/sec Figure 4.7: Service time vs. load for WLAN with 4, 12, and 20 stations 90 Chapter 4. A Finite-Load Model for QoS-Enabled IEEE 802.11e WLANs 91 Waiting Time in Queue vs. load with 20 stations 1200 • E F L Q M 4 stations o Simulation 4 stations —I— E F L Q M 12 stations 1000 Simulation 12 stations E F L Q M 20 stations Simulation 20 stations 800 600 400 / O 200 h 0* 0 j 10 i > j -» 20 =*= 30 40 =31 50 60 / 70 80 load frames/sec 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, developed by Robinson and Randhawa, considered both parameters and provides a solution for combining the effects of both parameters. However, this model assumes a post collision 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 5.2 94 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 parameters 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 duration is chosen randomly between 1 and C W (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 C W to its minimum. Given the above description of the E D C A function, we introduce our model by mathematically 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. 95 Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 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 priority. 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 different 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,* = . C Wmin b = b .p i iJc Qil 0o,i (5.1) (5.2) w, YiYj * bi =1 i=0 k=\ - (5 3) m III T = J]b i'=0 The probabilities b iyj iA (5.4) are the steady-state probabilities of the two-dimensional Markov Chain that models the backoff process [9] [3]. Obviously, the bjj probabilities are strongly 96 Chapter 5. An Improved Saturation Model for IEEE 802.1le WLANs 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\ + « stations, 4 slot 7 and after will have all ri\ + n + w stations contending. Note that we set rij for other 4 7 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. W „ is the minimum of all maximum contention window sizes ( C W M A X ) , ! and M is the mi lowest priority. If rij stations of priority i exist, then the equations that govern this model are as follows. For thefirstzone, 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 n +n r 1_L 97 n +n +n r 2 2 3 _J I M Slot 1 L_ M+1 Figure 5.1: Modeling Slot Occupancy for different contention zones p ^ i - a - T , ) 1 (5.5) " For the second zone, PU = \ - ( l - r r . ( \ - r f t l 2 (5.6) It follows that, for an arbitrary zone, the general expression is p' r z=z = 1 -rT}=,(l - T - r y ifKz<M (5.7) 1 - n>i (1 - T ; ) " J ifz>M Knowing P" and assuming that the Markov chain is in equilibrium, the relationship =z 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 2 bt = Wmin 1 (5.9) i=0 It follows that M b -a- PU) = E 0 i=l Wmin b i • + i=M+\ Z b ' • ( 5 - 1 Therefore leading to b= 0 777-.— i + z*rn;-=.a-^) (5.11) Next, we derive the average conditional collision probability Pj for each priority j (probability 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: Pc =\ = 1 - d - n ) " ' j 1 (5.12) The second priority is not active in this region, so it follows that PcjZ] = 0 In the second zone, (5.13) 0 ) Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs pcjj = i - ( i - T 1 r - - ( i - T i 2 99 r (5.i4) and, p % = i-a-Tir-(i-T r i c 1 (5.15) 2 The general expression for the conditional collision probability is z PC{=1 - (1 - T,-)"'- • n -^ - (i 1 k=\,k±j (5 i6) Knowing the probability of collision within stations for a specific zone, we canfindthe average conditional probability of collision for class j stations (probability that in any zone, a collision occurs by class j stations' transmission): Wmin pj=Yi * - brPcl (5 17) 1=1 Using the above equations we can derive the average collision and transmission probabilities for each priority class (Pj, r,). Using these probabilities we can derive the achievable 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 (P , P^°j)- We s z=j Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 100 can then use these probabilities andfindthe 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 duration 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: \-ptr P. 5 J,Z=l = (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: P % = Pti c ! ~ 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 P refers to the average payload L size in a frame. The expected payload size is: Wmin E = n .P Y bi-P *= j S p j L J j 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: E Tj = -=^ j (5.23) ED 5.5 Simulation Results In this section, we present the simulation results, which are generated using a very accurate 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 simulation 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 Value Parameter 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 ACK 112bits + P H Y Retry limit 4 RTS 160 bits + P H Y CTS 112 bits + P H Y AIFS1 SIFS + Slot Time AIFS 2 SIFS + Slot Time AIFS 3 SIFS + Slot Time AIFS4 SIFS + Slot Time CWMIN1 8 CWMIN2 16 CWMIN3 24 CWMIN3 32 CWMAX 1 16 CWMAX2 32 CWMAX3 48 CWMAX4 64 Parameter Value Table 5.1: Simulation Parameters for Batch 1 Value Parameter 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 4 Parameter Value ACK 112 bits + P H Y Retry limit RTS 160 bits + P H Y CTS 112 bits + P H Y AIFS1 SIFS + Slot Time AIFS2 SIFS + 2*Slot Time AIFS 3 SIFS + 3*SlotTime AIFS4 SIFS + 4*Slot Time CWMIN1 32 CWMIN2 32 CWMIN3 32 CWMIN3 32 CWMAX 1 64 CWMAX2 64 CWMAX3 64 CWMAX4 64 Table 5.2: Simulation Parameters for Batch 2 102 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 • * — M o d e 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 104 Chapter 5. An Improved Saturation Model for IEEE 802.11e WLANs 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 security, 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, W L A N s offer true economic advantage by helping enterprises maintain a flexible 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 contribute 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 Throughput 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 operation. 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 following 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 network. In [9] [12], Bianchi showed that beyond a certain traffic load threshold, the throughput of an 802.11 W L A N remains constant for a constant number of stations. The throughput 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 C W 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 i th 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 M A C header PHY header ACK 8000 bits 224 bits 192 bits 112 bits + PHY 160 bits + PHY 112 bits + PHY Bit Rate Slot Time SIFS Retry limit AIFS1 RTS CTS AIFS2 1 Mbps 20 ps 10 us 5 SIFS + Slot Time 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 CftJTLin =7, CWirex = 15 Nirriber of Stations (a) Saturation Throughput (Mbps) with -p (7,15) CWMIN, CWMAX = atfrriri = 15, Oiirax = 31 1 •-,—i—i—i—,—i—i—i—,—i—i—.—.—.—,—i—.—.—.—.—I—•—i—i—i—r r 0 10 20 30 40 Niirter • of Stations (b) Saturation Throughput (Mbps) withCWMiN, C W M A X Figure 6.1: Effect of C W M I N and CWMAX = 50 (15,31) on the Saturation Throughput 109 Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs CKttiin =7, CUnax Number: = 15 o f Stations (a) Probability of Collision with C W M I N , C W M A X = (7,15) CKhiin = 15 , Clitaax Number - 31 o f 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 110 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 Contention 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 A P algorithms are capable of overcoming the "Saturation Throughput" problem. A l l algorithms are based on the same fundamental concept of using adaptive C W size control 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 S C A works Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 112 as follows. For the highest priority A C , S C A 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 C W S C A also keeps the ratio C W M A X [ A C ] / C W M I N [ A C ] as compared to low priority ACs. constant. It performs better than the static case of the 802.lie (i.e. same network having same parameters except for the C W parameters) Algorithm 1 - The Station Count Algorithm % Stations[AC] i s the number o f s t a t i o n s that has % t h i s type o f traffic CWmin[highest AC] = CI * S t a t i o n s [ h i g h e s t AC] % Compute the CWmin o f the next p r i o r i t y r e c u r s i v e l y % based on the CWmin o f t h i s priority FOR i = highest AC -1 ; i >Q; i — CWmin[i] = CWmin[i+l] + C2 * END FOR FOR i = highest AC; i >0; CWmax[i] = CWmin[i] Stations[i] i ~ * CWratio[i] END FOR UPDATE data s t r u c t u r e s i n the beacon frame SEND beacon frame Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.11e Wireless LANs 6.3.2 113 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 C W parameters is essentially trying to track the optimum C W size for maximizing the W L A N throughput. In reality, the T D A only calculates C W M I N [ A C ] for each access category and calculate C W M A X [AC] by keeping the ratio CWMAX[AC]/CWMIN[AC] constant. The AP updates the values of.CW parameters in every beacon frame. The operation of the T D A is best described with Figure 6.3, where the throughput derivative 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 T D A 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 difference between the current derivative measurement and the past derivative measurement 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 derivative 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 Throughput Derivative V a l u e v s . T i m e 1 = 1 —i— 0.8 - \ 0.6 0.4 0.2 3 0 3 -0.2 CL. Qi Q2 -0.4 -0.6 -0.8 -1 -- 3 Time Figure 6.3: The T D A Operation Zones Algorithm 2 - The Throughput Derivative Algorithm % mean i s the average value o f throughput measurements % f o r l a s t few o b s e r v a t i o n s d e r i v a t i v e [ A C ] = (mean[AC] - old_mean[AC])/beacon_int IF d e r i v a t i v e [ A C ] < o l d _ d e r i v a t i v e [ A C ] & d e r i v a t i v e [ A C ] < Q THEN d i f f _ s i g n [ A C ] *= - 1 % Update every AC w i t h the f o l l o w i n g equations. % i s a constant value CWmin[AC] = CWmin[AC] + d i f f _ s i g n [ A C ] * step CWmax[AC] = CWmin[AC] * CWratio[AC] UPDATE data s t r u c t u r e s i n the beacon frame SEND beacon frame CWratio[AC] Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 6.3.3 116 The A n a l y t i c a l A l g o r i t h m The Analytical Algorithm uses mathematical calculations to estimate the optimum C W 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 C W parameters right away, without further searching. It may even give some surprising result, such as interchanging of the C W 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 C W parameters of all priorities, 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 C W 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] = m i n P r i o r i t y A ; CWmin[B] = m i n P r i o r i t y B ; Maxthrup = Sat_thrup(A, B, CWmin[A], CWmin[B]); FOR i = m i n P r i o r i t y A ; i < maxPriorityA; i = i + i n c r FOR j = m i n P r i o r i t y A ; j < maxPriorityA; j = j + i n c r 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 s t r u c t u r e s i n the beacon frame SEND beacon frame It is to be noted here that full enumeration of all possible solutions results in a large computation 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 C W 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 C W 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 adaptive 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 S C A is activated at t = 1000 sec. In this scenario, we applied the T D algorithm to the C W of the higher priority, and fixed the C W of the lower priority with respect to the higher one. The T D algorithm can be applied separately to the two priorities, but it seems that only the C W of the higher priority will significantely change the ST. Figure 6.6 shows the results of the throughput using the Throughput Derivative Algorithm: the Saturation Throughput (ST) is plotted versus time for both Static E D C A and Adaptive E D C A using the T D 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 T D A algorithm has the same improvement as the S C A in this case, it is worth noting that the T D A 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 T D A . 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 C W 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 E D C A . 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 C W 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 wireless 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 thefixed-parameter802.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 network can have under optimal conditions. It could be used as a benchmark for other adaptive schemes. Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1le Wireless LANs 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 Time (sec) 2000 2500 3000 Figure 6.5: Static vs. Station-Count Algorithm - C W M I N Change 121 Chapter 6. Adaptive Contention-Window M A C Algorithms for IEEE 802.1le Wireless LANs 122 Wireless Network Saturation Throughput vs Time 900 I 1 0 500 1 1000 1 1500 Time (sec) 1 2000 2500 3000 Figure 6.6: Static vs. Throughput Derivative Algorithm - Throughput Low P a s s 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 x in 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 123 Chapter 6. Adaptive Contention-Window MAC Algorithms for IEEE 802.1 le Wireless LANs Static vs. Adaptive EDCA for Priority A Throughput 0.9 0.8 0.7 a 0.6 a o 0.5 h -Analysis - Priority A Throughput 5= 0.4 0.3 0.2 -Simulation Adaptive - Priority A Throughput Simulation Static - Priority A Throughput 0.1 0 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 124 Chapter 6. Adaptive Contention-Window M A C Algorithms for IEEE 802.11e Wireless LANs 125 Proof of Optimization of Priority A Throughput -Simulation Adaptive • Priority A Throughput 0.8 0.7 • t -Analysis • CWminA = 7 CWmax^l = 15 0.6 Analyse - CWminA = 12 CWma<A = 25 Analysis • CWminA=27 CWmaxA = 55 -Analysis - CWminA CWma>cA=55 : 37 -Analysis - CWmin A = 57 1 4 7 1013 1619 22 25 28 313437 43 4346 4952 55 58 Stations CWmaxA=115 - Analysis - CWminA CWmaxA=145 Figure 6.12: Proof of Optimization for the Analytical Algorithm 72 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. A n 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 P H Y layer effects. Key aspects of P H Y 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 deciding 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 A P 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 underfinite-loadand saturation conditions, and the enhancement of the Saturation Throughput in 802.1 le WLANs. In Chapter 3, we presented an accurate and fairly complicated mathematical model for 802.11 W L A N s called the "Enhanced Finite-Load Model (EFLM) for IEEE 802.11 Wireless LANs". E F L M uses a dual queuing model where a node is represented by one queueing 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, transmissions from other stations P . x and the probability of witnessing incomplete 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 W L A N s , and introduced 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 W L A N s is more complicated because of the prioritization mechanisms that were introduced in [7] such as the AIFS, and the different C W parameters for each A C . In Chapter 5, we presented a mathematical model for saturated 802.1 le W L A N s , 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 assumptions. Chapter 6 presented three algorithms, that were devised to enhance the Saturation Throughput in saturated 802. l i e WLANs. The proposed algorithms are based on adaptively changing the Contention Window (CW) parameters, trying to find the optimimum C W parameter values. The Station-Count Algorithm (SCA) is a very simple algorithm and one of the earliest 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. 129 Chapter 7. Conclusions and Future Research 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, T and s T. c 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 transmissions 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", B B C 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. E l Housseini, and H. Alnuweiri, "Adaptive Contention-Window M A C Algorithms for QoS-Enabled Wireless LANs", IEEE International Conference on Wireless Networks, 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 D C F using RTS/CTS", in IEEE Thirteenth Workshop on Local and Metropolitan Area Networks, pp. 33 - 38, April 2004 [12] G. Bianchi, "IEEE 802.11 Saturation Throughput Analysis", in IEEE Communications Letters, vol. 2, issue 12, pp. 318 - 320, December 1998 [13] A . N . Zaki, M.T. El-Hadidi, "Throughput Analysis of IEEE 802.11 D C F 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 M A C " , 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 Queueing Model", International Conference on Information Technology: Coding and Computing, 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 Electrotechnical 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 Conference, 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 E D C F under Saturation Condition", 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 International Conference on Communications, vol. 5, pp. 3474 - 3478, May 2005 [27] H . Zhu, I. Chlamtac, "An Analytical Model for IEEE 802.lie E D C F Differential Services", in Proceedings of the 12th International Conference on Computer Communications 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 Supported 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 136 BIBLIOGRAPHY IEEE International Conference on Local Computer Networks, pp. 682-690, October 2003 [36] Y. Pourmouhammadi, S. E l 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 D C F via Distributed Reservation", in IEEE Transactions on Mobile Computing, vol. 4, pp. 378-390, July 2005 [38] E . Winands, T. Denteneer, J. Resing, R. Rietman, "A Finite-Source Feedback Queueing 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 Coordination Function Under Sporadic Traffic", JFIP Networking Technical Report, May 2005 [40] Danielle Dunne, "What is a wireless LAN?", C N N , 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. E l Housseini, and H . Alnuweiri, "An Enhanced Finite-Load Model for IEEE 802.11 Wireless LANs", Submitted to IEEE Transactions on Communications, December 2005 BIBLIOGRAPHY 137 [44] S. E l Housseini, and H . Alnuweiri, "A Finite-Load Model for QoS-Enabled IEEE 802.1 le W L A N s " , 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, W , nnetk] - FiniteLoad (p, P , p, W, W , nnet ) idle p p k We laid the equations in FiniteLoad in the following order (Equation numbers are different for 802.lie WLANs): 1. /v,(Eq. 3.5) 138 139 APPENDIX A 2. W (Eq. 3.6) p 3. W(Eq. 3.7) 4. /, (Eq. 3.39) 5. nnet (Eq. 3.38) k 6. P idle 7. P busy (Eq. 3.41) (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 = ® I t e r a t i o n s L o o p : For j = 1 t o 9 d = d / 2 X =Xi S o l v e L o o p l : For i = 1 t o 5 X(3) = Oldro + d X = F i n i t e L o a d (X) End SolveLoopl D i f f l = AbsoluteValue ( o l d r o + d - X ( 3 ) ) X =Xi SolveLoop2: For i = 1 t o 5 X(3) = Oldro - d X = F i n i t e L o a d (X) End SolveLoop2 D i f f 2 = AbsoluteValue ( o l d r o - d - X ( 3 ) ) I f D i f f l > Diff2 Oldro = Oldro - d Else Oldro = Oldro + d End I f End I t e r a t i o n s L o o p S a t u r a t i o n C o n d i t i o n : I f Minim > Q.01 B e s t r o = 8.999 End I f S a t u r a t i o n C o n d i t i o n X =Xi F i n a l L o o p : For i = 1 t o 6 X(3) = B e s t r o X = F i n i t e L o a d (X) End F i n a l L o o p 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 respectively, 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 |
Graduation Date | 2006-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | 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