UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Per-session weighted fair scheduling for real time multimedia in multi-rate wireless local area networks Fallah, Yaser Pourmohammadi 2007

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-ubc_2007-267769.pdf [ 11.59MB ]
Metadata
JSON: 831-1.0100418.json
JSON-LD: 831-1.0100418-ld.json
RDF/XML (Pretty): 831-1.0100418-rdf.xml
RDF/JSON: 831-1.0100418-rdf.json
Turtle: 831-1.0100418-turtle.txt
N-Triples: 831-1.0100418-rdf-ntriples.txt
Original Record: 831-1.0100418-source.json
Full Text
831-1.0100418-fulltext.txt
Citation
831-1.0100418.ris

Full Text

Per-Session Weighted Fair Scheduling for Real Time Multimedia in Multi-Rate Wireless Local Area Networks by YASER POURMOHAMMADI F A L L A H B . S c , Sharif University of Technology, 1998 M . A . S c , University of British Columbia, 2001 A THESIS S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F D O C T O R O F P H I L O S O P H Y in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A March 2007 © Yaser Pourmohammadi Fallah, 2007 Abstract Supporting real time multimedia applications is of utmost importance for future wireless data networks. In particular, it is crucial to support such applications in widely deployed and fast growing wireless local area networks ( W L A N ) that are based on I E E E 802.11 standard. However, achieving this goal requires features and mechanisms that have not been offered by the original I E E E 802.11 standard. To address this issue, several Quality of Service (QoS) enabling features have been added to the Medium Access Control ( M A C ) layer in the new I E E E 802 . l i e standard. Nevertheless, the new standard does not mandate a specific QoS solution, and intentionally leaves such task to developers and equipment vendors. Devising mechanisms that can efficiently provide the required QoS in W L A N s has proved to be a challenging task. This is mainly due to the fact that W L A N s such as 802.1 le are based on the C S M A / C A (Carrier Sense Multiple Access with Coll is ion Avoidance) access method, which is . inherently a distributed mechanism with random uplink or downlink access. Moreover, the physical layer of a W L A N allows each station to use a different transmission rate. The transmission rate could also dynamically change from one packet to the next, for the same station. The general problem of packet loss in wireless networks is also present in W L A N s . The existing solutions and the prioritized contention based mechanism provided by the standard are found to be inadequate for providing the required services, especially in heavily loaded networks. Considering the issues mentioned above, we present a solution in this thesis that employs the controlled access mechanisms of the 802.1 le standard to provide per-session guaranteed QoS to multimedia sessions. We introduce a framework that centralizes the task of scheduling uplink and downlink flows in the access point through the concept of virtual packets. We propose a new queuing structure that works with a fair generalized processor sharing based scheduler, integrated with a traffic shaper, for scheduling controlled (polling) and contention access durations. To address the issues of physical channel impairment and variable rate operation of a W L A N , we extend our scheduling framework to provide throughput or temporal fairness in multirate W L A N s . Through analysis and experiments, we demonstrate that our solution provides guaranteed fair access for multimedia sessions over W L A N s . ii Table of Contents Abstract » Table of Contents iii List of Tables vi List of Figures vii Dedication ix Co-Authorship Statement x Chapter 1. Introduction and Background 1 1.1 Introduction and Motivation 1 1.2 Thesis Contributions 5 1.3 Background: I E E E 802.1 le Wireless Local Area Networks 6 1.3.1 IEEE 802.11 MAC Layer 8 1.3.2 IEEE 802.1 le MAC Layer 11 1.4 Previous Work 15 1.5 Thesis Scope and Organization 19 1.6 References 22 Chapter 2. Generalized Saturation Throughput Analysis of EDCA 27 2.1 Introduction 27 2.2 Model Development 28 2.3 Slot Occupancy 31 2.4 Throughput Analysis 33 2.5 Simulation Evaluation 34 2.6 References 37 Chapter 3. Per Session QoS Provisioning in WLANs 38 3.1 Introduction 38 3.1.1 IEEE 802.lie MAC Specifications ' 42 3.2 C A P S : Controlled Access Phase Scheduling 46 3.2.1 Centralizing the Scheduling Task: Combined Downlink/Uplink Scheduling 47 3.2.2 Scheduling, and Traffic Shaping 49 3.2.3 Implementing the Traffic Shaper 54 3.2.4 Lost Service Compensation for Uplink Flows 56 3.2.5 Adapting to Wireless Channel 57 3.3 Performance Guarantee Analysis 59 3.3.1 Long Response Case: Immediate and Deferred Compensation 60 3.3.2 Performance Analysis of CAPS with Deferred Compensation 66 3.4 Performance Evaluation 74 3.5 Concluding Remarks 80 3.6 References 81 Chapter 4. Fair Scheduling in Multi-Rate W L A N s 84 4.1 Introduction 84 4.1.1 Scheduled Access in IEEE 802. lie MAC 87 4.1.2 MultiRate Operation of a WLAN. 89 4.2 Centralized Hybrid Scheduling in W L A N s 91 4.2.1 Combining Downlink and Uplink Scheduling 92 4.2.2 Scheduling and Switching between HCCA and EDCA 93 4.2.3 Service Compensation for Uplink Flows 96 4.2.4 Adapting to Wireless Channel Quality. 97 4.3 Fairness and Multirate operation of W L A N s 99 4.3.1 Fair Generalized Processor Sharing with MultiRate Operation 100 4.3.2 Throughput and Temporal Fair WFQ and WF2Q 102 4.3.2.1 Throughput Fair W F Q and W F 2 Q 102 4.3.2.2 Temporal Fair W F Q and W F 2 Q 105 4.3.3 Throughput and Temporal Fair SFQ in a MultiRate Scenario 106 4.4 Delay Bound Analysis of C A P S - S F Q 109 4.4.1 Delay Bound Analysis of Throughput Fair SFQ in Static Multirate Case 110 4.4.2 Delay Bound Analysis of Throughput Fair SFQ in Dynamic Multirate Case.... 115 4.4.3 Delay Bound of Temporal-Fair SFQ in Static and Dynamic Multirate Cases... 117 4.5 Performance Evaluation 119 4.6 Concluding Remarks 122 iv 4.7 References 123 Chapter 5. Summary and Conclusions 127 5.1 Summary and Concluding Remarks 127 5.2 Summary of Contributions 129 5.3 Future Research Directions 131 A P P E N D I C E S 133 Appendix A . Modeling 802.11 D C F 133 Appendix B . Performance of H.264 Video over 802.11 e W L A N 135 Appendix C . Analysis of Throughput and Temporal Fair W F Q and W F 2 Q 139 v List of Tables T A B L E 1-1 3 G P P E N D - U S E R P E R F O R M A N C E E X P E C T A T I O N S - C O N V E R S A T I O N A L / R E A L - T I M E S E R V I C E S ( M O D I F I E D F R O M S O U R C E : 3 G P P T S 2 2 . 1 0 5 V 8 . 0 . 0 ) 3 vi List of Figures F I G U R E 1-1 D I F F E R E N T W L A N T O P O L O G I E S : A D H O C V S . I N F R A S T R U C T U R E 7 F I G U R E 1-2IFS T I M I N G R E L A T I O N S H I P S IN DCF 9 F I G U R E 1-3 DCF O P E R A T I O N 10 F I G U R E 1-4 P E R I O D I C C O N T E N T I O N A N D C O N T E N T I O N F R E E P E R I O D S , PCF O P E R A T I O N 11 F I G U R E 1-5 IFS R E L A T I O N S H I P S IN 802.1 1E EDCA (DCF) 12 F I G U R E 1-6 TXOP O P E R A T I O N IN 802.1 1E M A C 13 F I G U R E 1-7 H C C A O P E R A T I O N W I T H PERIODIC CFP 14 F I G U R E 1-8 H C C A O P E R A T I O N W I T H O U T CFP 14 F I G U R E 2-1 M O D E L I N G S L O T - O C C U P A N C Y F O R D I F F E R E N T C O N T E N T I O N Z O N E S 30 F I G U R E 2-2: C O L L I S I O N P R O B A B I L I T Y & S A T U R A T I O N T H R O U G H P U T V S . N U M . O F S T A T I O N S (PER C L A S S ) 35 F I G U R E 3-1 S O M E IFS R E L A T I O N S H I P S IN DCF A N D E D C A 43 F I G U R E 3-2 802.1 1E HCCA: C A P G E N E R A T I O N W I T H CFP ( L E F T ) , W I T H O U T CFP (RIGHT) 45 F I G U R E 3-3 A R C H I T E C T U R E A N D Q U E U I N G M O D E L O F CAPS A C C E S S P O I N T A N D S T A T I O N 48 F I G U R E 3-4 P S E U D O C O D E F O R T H E S C H E D U L I N G T A S K 54 F I G U R E 3-5 SR C A S E F O R WFQ, WF 2 Q A N D SFQ 67 F I G U R E 3-6 M A X D E L A Y O B S E R V E D F O R D I F F E R E N T INNER S C H E D U L E R S 76 F I G U R E 3-7 CDF O F D E L A Y F O R A N U P L I N K V I D E O F L O W (CAPS vs EDCA) 77 F I G U R E 3-8 CAPS A B I L I T Y T O G U A R A N T E E B I T R A T E (FOR A L L CAPS OPTIONS) 77 F I G U R E 3-9 A V O I C E O N L Y W L A N , M A X I M U M A N D A V E R A G E D E L A Y F O R (CAPS vs. EDCA) 78 F I G U R E 3-10 D E L A Y O F A S I N G L E V I D E O SESSION A S B A C K G R O U N D T R A F F I C I N C R E A S E S 79 F I G U R E 3-11 P R O T E C T I O N F R O M S A M E C L A S S T R A F F I C : P E R F L O W V S . A G G R E G A T E QoS 80 F I G U R E 4-1 H C C A CAP G E N E R A T I O N 88 F I G U R E 4-2 A R C H I T E C T U R E A N D Q U E U I N G M O D E L O F A CAPS A C C E S S P O I N T 93 F I G U R E 4-3 D E L A Y A N A L Y S I S O F CAPS-SFQ 112 F I G U R E 4-4 T H E A B I L I T Y O F T H R O U G H P U T F A I R CAPS-SFQ T O G U A R A N T E E B I T R A T E 120 F I G U R E 4-5 T H R O U G H P U T F A I R N E S S V S . T E M P O R A L F A I R N E S S 120 F I G U R E 4-6 D E L A Y DISTRIBUTION F O R CAPS ( T E M P O R A L & T H R O U G H P U T F A I R ) A N D EDCA121 F I G U R E A - l M A R K O V M O D E L FOR T H E B A C K O F F P R O C E D U R E . 134 F I G U R E B-l O F F L I N E V I D E O C O M M U N I C A T I O N S I M U L A T O R 135 vii F I G U R E B - 2 C D F O F D E L A Y I N A W L A N W I T H A N D W I T H O U T P H Y E R R O R S 1 3 6 F I G U R E B - 3 S N A P S H O T S O F F O R E M A N V I D E O , T R A N S M I T T E D I N F O U R D I F F E R E N T W L A N S C E N A R I O S 1 3 8 viii Dedication To my wife, Mahsa, and my parents, Ziba and Ali Co-Authorship Statement Chapter 2 of this dissertation has been taken from a paper co-authored by Yaser Pourmohammadi Fallah (the author of this thesis), Samer El-Housseini and Hussein Alnuweiri . As a research group, we have been working on modeling I E E E 802.11 and 802.1 le W L A N s , 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. The greater part of the paper was written by Yaser who contributed to identification and design of the research work presented in the chapter, and developed the mathematical model presented therein; while Samer implemented the mathematical model in C, generated the simulation data and plots, and finished writing the last part of the paper. Prof. Alnuweiri has supervised the research work and contributed in directing and refining the work, as well as revising the manuscript. Chapters 3 and 4 of this dissertation are co-authored by the author of this thesis, Yaser Pourmohammadi Fallah, and his PhD research supervisor, Prof. Hussein Alnuweiri . Yaser, the author of this thesis, is the primary author of these chapters and has contributed to identification and design of the research work presented in the chapters, as well as performing the presented research, data analysis and manuscript preparation. Prof. Alnuweiri has supervised the research work and contributed in directing and refining the work, as well as revising the manuscripts. Chapter 1. Introduction and Background 1.1 Introduction and Motivation Research towards new technologies is driven by the desire to improve the quality of life. Advancements in telecommunication technology in the past few decades certainly account for some of the most important instances of such improvements. The latest research efforts in this field have been focused on enabling true multimedia communication services, anywhere, anytime. To achieve this goal, many new communication technologies have been developed to provide higher communication speeds and better services to users. One of these technologies that provides broadband wireless access is the I E E E 802.11 standard [1] for wireless local area networks ( W L A N ) . Due to their simplicity and ease of use, W L A N s are being deployed at a rapid pace around the world, bringing high speed access to many users. As a result, a diverse range of applications, including real-time multimedia applications, are expected to be used over W L A N s . Examples of such applications are voice and video telephony and conferencing, video surveillance, streaming High Definition T V ( H D T V ) in a home environment or possibly in neighborhoods, as well as real-time online gaming and tele-robotics. A l l these applications have stringent quality of service (QoS) requirements such as low delay and jitter and guaranteed bitrate services. 1 Multimedia applications are also the driving force behind many new developments in other field of communications. For example, new video streaming applications are gradually appearing on cellular networks, forcing service providers to move to newer technologies and solutions. One solution for providing better broadband access to cellular mobile users is internetworking between high speed W L A N s and cellular networks. The idea is to use the existing high speed W L A N access, wherever service is available, and switch some of the traffic from cellular networks to the local W L A N s , while maintaining the main management and signaling functions within the core of the cellular network. Such mechanisms have received considerable attention from the standard bodies; an example of the specifications of such internetworking scenarios is found in [3]. Given the above scenario, it is imperative for W L A N s to be able to provide the same QoS that cellular networks can, at a higher cost, offer to applications such as voice or video telephony. A n example of typical QoS requirements or performance targets in 3 r d Generation cellular networks is shown in Table 1-1. Note that this table presents the end-to-end requirements; i f a wireless network is only one part of the traffic path, stricter QoS requirements are applied. Therefore, in case of W L A N s , we expect similar or more stringent QoS requirements than those described in Table 1-1. In fact, with more bandwidth availability in W L A N s , high bitrate applications such as high quality video (e.g., with rates in the range of 1-24 Mbps) are also considered; whereas for 3G networks a rate of 384Kbps was considered to be the limit. This increased throughput requirements makes the already stringent end-to-end performance targets even stricter. 2 Table 1-1 3GPP End-user Performance Expectations - Conversational / Real-time Services (Modified from source: 3GPP TS 22.105 V8.0.0) Medium Appl icat ion Degree of symmetry Data rate Key per formance parameters and target values End-to-end One-way Delay Information loss Audio Conversational voice Two-way 4-25 kb/s <150 msec preferred < 3% FER Video Videophone Two-way 32-384 kb/s < 150 msec preferred Lip-synch : < 100 msec < 1% FER Data Telemetry - two-way control Two-way <28.8 kb/s < 250 msec Zero Data realtime games Two-way < 60 kb/s < 75 msec preferred < 3% FER preferred, < 5% FER limit Data Telnet Two-way (asymmetric) < 1 KB < 250 msec Zero The original 802.11 standard has not been designed for real-time services and multimedia applications; as a result, it fails to efficiently provide the required services for real time applications. To address this issue, a new standard, I E E E 802.1 le , has been approved for enhancing the medium access control ( M A C ) layer of the original standard with Quality of Service (QoS) features. These features are presented through a Hybrid Coordination Function (HCF) and support two new access mechanisms of Enhanced Distributed Channel Access ( E D C A ) and H C F Controlled Channel Access ( H C C A ) . Such capabilities provide enough features for developers to devise QoS solutions that make real time multimedia applications in W L A N s feasible. The QoS features of the H C C A can be used to provide per-session guaranteed services to real time applications. However the standard does not mandate any scheduling solution to use these features and leaves it to developers to devise such a scheme. Devising such a mechanism is a complicated task due to the fact that W L A N s are by nature distributed multiple access networks, and the physical layer in wireless networks is more error prone and may operate at different speeds at different times (also known as multirate operation). Addressing these issues, we propose a scheduling solution in this thesis that provides per-session guaranteed services for multimedia applications in W L A N s . Our solution, which is called Controlled Access Phase Scheduling (CAPS) , addresses the variable rate operation of wireless networks and is applicable to any multiple access network with features similar to the 802.1 le standard. The proposed design in this dissertation is evaluated through mathematical analysis as well as simulation experiments. Since E D C A is the first choice of most vendors for QoS provisioning in W L A N s , we present an extensive comparison between the performances of our method with that of E D C A . We also present a new analysis of the E D C A throughput under saturation condition in order to provide more insight into the operation of E D C A . This analysis complements and corrects the existing analyses of E D C A . We show through our experiments and analyses that although E D C A may provide adequate services in lightly loaded networks, it fails to provide the required QoS when the network is heavily loaded. Our method, on the other hand, significantly boosts the capacity and the provided QoS. This thesis provides a detailed description of our design. Some prominent contributions of this thesis are described in the next section. In this chapter we also present an overview of the I E E E 802.1 le technology and its specific features that concern QoS provisioning for multimedia applications. We review some related works that address specific aspects of QoS provisioning in wireless networks and identify the unresolved issues that the current solutions do not address. A guide to the organization of this thesis is presented in the last section of this chapter. 4 1.2 Thesis Contributions This thesis proposes a QoS scheduling framework for 802.1 l e W L A N s . The proposed method provides per-session fair services for multimedia sessions that make reservations with the access point, while sharing the remaining capacity of the W L A N using E D C A access method. Our solution takes into account the fact that W L A N stations may use different transmission rates in the physical layer, and proposes measures to maintain the fairness of the scheduling mechanism. The main contributions of this thesis, made through the course of developing the above solution, are the following: 1. Introducing a unified scheduling framework that centralizes the task of uplink/downlink scheduling in the access point of a W L A N . 2. Developing a new queuing/scheduling model that uses traffic shaping and fair scheduling in the above unified scheduling framework, and achieves efficient scheduling of H C C A and E D C A based access. This model provides guaranteed access services for H C C A flows, while sharing the remaining capacity in a contention based manner using E D C A . 3. Presenting an analysis of temporal and throughput fair scheduling based on the concept of Generalized Processor Sharing (GPS). 4. Extending the C A P S solution to maintain throughput or temporal fairness in multirate environments, and deriving the delay bounds provided by this algorithm under dynamic and static multirate scenarios. 5 5. Introducing a generalized saturation throughput analysis of E D C A that allows for an arbitrary number of priority levels to be considered, extending and correcting the existing methods. 6. Implementing the 802.1 le M A C and the proposed scheduling framework in O P N E T simulation environment. 1.3 Background: IEEE 802.11 e Wireless Local Area Networks In 1997 the I E E E adopted the 802.11 wireless local area network ( W L A N ) standard [1]. This standard defines the media access control ( M A C ) and physical ( P H Y ) layers for a local area network ( L A N ) with wireless connectivity. It addresses local area networking where the connected devices communicate over the air with other devices that are within close proximity to each other. The standard identifies several main components for a W L A N architecture. These are Station (STA), Access Point (AP), Basic Service Set (BSS), Independent Basic Service Set (IBSS), Distribution System (DS), and Extended Service Set (ESS). BSS is a set of stations controlled by a single coordination function, i.e. in a single M A C domain. A n IBSS is an A d Hoc wireless network in which stations communicate in a peer to peer fashion. A DS is a system used to interconnect a set of BSSs and integrated local area networks (LANs) to create an extended service set (ESS). These concepts are illustrated in Figure 1-1. W L A N s are usually deployed in an infrastructure mode, in which an access point controls the network and provides a gateway to the outside world. The other mode of operation for W L A N s is the A d Hoc mode in which the network is managed in a distributed manner. Figure 1-1 depicts the typical topology of the network in each mode. A great deal of research has been 6 dedicated to A d Hoc networks, while research on infrastructure based W L A N s have been less extensive. In this thesis we focus on the infrastructure mode, which is preferred by service providers and is the widely used mode; however, some of the work of this thesis, especially the analysis in Chapter 2, is applicable to A d Hoc networks as well . The original standard has been amended with various enhancements; namely 802.11b (DSSS up to 11Mbps), 802.11a ( O F D M , up to 54 Mbps), and 802.1 l g (backward compatible with 802.11b, with speed of up to 54 Mbps) standards were approved. These standards are only different in their physical layer and data rates; the M A C layer operation for all of them is the same, except for some P H Y related parameters. The M A C layer has recently been amended with features to support QoS and increase efficiency as well . These features are approved under the I E E E 802.1 l e standard [2]. Further enhancements to the P H Y and M A C layers are being considered in the upcoming 802.1 l n standard. Distribution System (DS) Ad-Hoc Mode Infrastructure Mode Figure 1-1 Different WLAN topologies: Ad Hoc vs. Infrastructure In addition to 802.11, other Wireless L A N standards have been developed. For example H I P E R L A N (and H I P E R L A N 2 ) standard has been developed by European 7 Telecommunications Standards Institute (ETSI) [4] [5]. Although, the H I P E R L A N standard seems to be more capable than 802.11 in terms of Quality of Service provisioning, it has not gained the widespread acceptance that 802.11 has. Therefore, we do not focus our research on this standard. In this section we present an overview of the M A C layer functionality of the original 802.11 standard. We then review the enhancements that were introduced in the new 802.1 le standard. In particular, we highlight the controlled access features that are used by our proposed QoS solution. 1.3.1 IEEE 802.11 MAC Layer The basis for 802.11 M A C is a C S M A / C A mechanism (Carrier Sense Multiple Access with Coll is ion 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 ( N A V ) signal that determines for how long the channel remains busy. N A V is set in a "duration" field of the M A C messages. Coll is ion avoidance in 802.11 M A C is performed buy a mechanism called Distributed Coordination Function (DCF). D C F is a protocol that describes how stations can access the wireless medium in a distributed manner. D C F uses inter-frame space (IFS) time intervals to coordinate channel access in the contention period (CP). Each frame type is allowed to access the network i f it finds the medium idle for longer than a predetermined IFS time. The IFS time is different for each type of frame, Data frames have to use DIFS time, while A C K (Acknowledgment), C T S (Clear To Send), and Pol l messages use SIFS time which is shorter than DIFS. This gives 8 A C K , Pol l , or C T S messages higher medium access priority than the data frames. Stations that find the medium busy perform a random back-off and repeat the deference and channel sensing procedure again. The details of D C F can be found in [1] . Figure 1-2 shows the timing relationship in D C F . Immediate access when medium is idle >= DIFS DIFS Busy Medum DIFS PIFS Ha H SIFS Defer Access Contention Window • Backoff Window Next Frame Slot Time Select Slot and decrement backoff as long as medium stays idle Figure 1-2 IFS Timing Relationships in D C F The random backoff is performed by selecting a random number from a contention window of (0,CW). C W is the contention window size and is initially set to aCWmin. When a station transmits a data frame or R T S but does not receive an expected A c k or C T S , it assumes that a collision happened and doubles its contention window size, up to aCWmax. This increase continues for a few times, limited by the retry_limit parameter. The packet is dropped if this limit is reached. The backoff counter is reduced in each idle time slot observed by the station. If a transmission occurs before the counter reaches zero, the counter freezes for the duration of the busy period and resumes its count down with the next observed idle slot (after DIFS). This procedure is depicted in Figure 1-3. When the backoff counter reaches zero the station immediately transmits the frame. 9 Station 1 Station 2 Station 3 Station 4 N A V N A V random backoff (7 slots) C T S random backoff (9 slots) R T S D A T A 0 new random backoff (10 slots) D | Station defers I F N A V remaining backoff (2 slots) A C K Station defers, but keeps backoff counter (=2) Station sets N A V upon receiving R T S Station sets N A V upon receiving R T S D A T A Station 6 D A T A Station sets N A V upon receiving C T S , this station is hidden to station 1 time Figure 1-3 D C F Operation. While D C F is a mandatory function in M A C , an optional mechanism, called Point Coordination Function (PCF), has also been defined in the standard. P C F resides in the access point and provides a contention free access method by polling individual stations whenever it wants to send to or receive data from them. Contention free periods, controlled by P C F , are repeated periodically (Figure 1-4). When the W L A N is controlled by an access point (AP), a beacon is also sent on a periodic basis. If P C F is supported, this beacon becomes the signal that indicates the start and end of a contention free period (CFP). The beacon sets the N A V parameter in all stations to the length of the C F period. To give the access point the priority in sending a beacon, the D C F specifies a PIFS (PCF Inter Frame Space) duration which is shorter than DIFS, but longer than SIFS. Using PIFS the access point can interrupt the normal contention, which uses the longer DIFS waiting time, and send a beacon immediately following any data exchange cycle. Beacon cannot interrupts A c k or C T S packets since these packets use the shorter SIFS. 10 A c k 802.11 periodic superframe STAs (upstream) Figure 1-4 Periodic Contention and Contention Free Periods, P C F Operation. 1.3.2 IEEE 802.lie MAC Layer The M A C in the original 802.11 standard (and a, b, and g variations), does not consider QoS and does not provide necessary mechanisms for properly supporting multimedia applications. Mechanisms for prioritizing between different classes of traffic and reserving guaranteed resources for flows were not present in the original 802.11. For this reason I E E E approved an amendment to the M A C layer specification, under the 802.1 l e standard, that provides necessary mechanisms for proper QoS support in the M A C layer [2]. The new standard introduces some concepts such as transmission opportunity (TXOP) and the capability to poll a station even during the contention period. There are also new frame formats with QoS information fields that help in enabling QoS in the M A C layer. The basic building block of M A C in 802.1 l e is again D C F , with some modifications. Accessing the medium is now controlled by a Hybrid Coordination Function (HCF) that works on top of D C F . Channel access in H C F is done using two protocols called E D C A (Enhanced Distributed Channel Access), and H C C A ( H C F Controlled Channel Access). E D C A provides prioritized aggregate QoS through defining four traffic categories and using different contention parameters for each category. H C C A provides per session QoS through polling mechanisms and user defined scheduling and queuing schemes. 11 E D C A is in fact an enhanced version of D C F that allows different classes of traffic to use different contention and timing parameters, providing them with probabilistic differentiated services. The 802 . l i e standard defines 8 different traffic priorities in 4 access categories for E D C A . The D C F is enhanced by introducing an access category specific IFS waiting time, known as Arbitration IFS or AIFS , that replaces DIFS. Each access category or priority level i can use a different AIFS[i ] . Control frames still use the same SIFS and PIFS waiting times that are shorter than A I F S . Figure 1-5 shows the timing relationship in 802 . l i e D C F and E D C A . The back-off windows are also different for different traffic priorities, so that each class i uses its specific aCWmin[i] , and aCWmax[i]. Access categories with shorter AIFS and smaller contention window limits wi l l have higher probabilities of transmission and wi l l receive higher throughput and priority over other categories. This prioritization enables a relative QoS in 802 . l i e M A C . Immediate a c c e s s when medium is idle >= A l F S f T C L Content ion Window AIFS[TC]+SlofTime Pipe : from [1,1+CWmin[TC]l A l F S f T C ^ Slr-S B u s y / / / Backoff / i +SlotTime / 1 Next Frame Medium / / / Window / _ SlotTime Defer A c c e s s Select Slot and decrement backoff as long as medium stays idle Figure 1-5 IFS relationships in 802.11e E D C A (DCF) One of the new efficiency mechanisms that have been introduced by 802.1 le is the possibility of transmitting multiple frames in one burst of frame exchanges, called transmission opportunity or T X O P (Figure 1-6). T X O P specifies the duration of time in which a station can hold the channel uninterrupted. Frame exchange in a T X O P is done with SIFS spacing which prevents interruption by other stations. A T X O P can be obtained by either winning contention 12 or through a C A P generation by the access point. Other than allowing for multiple frame exchange, which reduces collision and increases throughput, a T X O P can also be used to limit the problem of unfair access by slow stations. This problem occurs in a multirate W L A N in which a station with low transmission rate occupies the channel for a much longer time than that of stations with higher rates. Using T X O P , the slow stations can be forced to use fragmentation and limit their use of the channel. We have conducted a study of the T X O P feature and its effect on the efficiency of a W L A N . This study can be found in [31]. Backoff/ A I P > | J F S Backoff/ A I P > Contention ! Data i A C K Contention I Data" i' A C K Backoff/ <A#rS | | F S ^ S I F S ^ I F S Contention ! Data i A C K : Data j! ' A C K DataJ = DATA from STA(i) TXOP Duration Unusable portion Figure 1-6 T X O P operation in 802.1 le M A C One of the most important features of the 802 . l i e is the capability of an A P to start a contention free duration, known as a Controlled Access Phase (CAP) , even during contention periods. The A P is allowed to initiate a C A P after a PIFS following any frame exchange cycle in contention period. The original C F P (of the 802.11 standard) is in fact a C A P in the new standard (Figure 1-7). This feature allows for a more controlled and efficient polling mechanism in which periodic durations of contention and contention free periods are replaced with a contention period with occasional interruptions by controlled access phases. A C A P can be generated for either uplink or downlink directions. A n uplink C A P is generated by sending a poll to a station and assigning a T X O P to it, a downlink C A P is generated by sending data frames to a station. Figure 1-8 elaborates on how C A P s are generated. 13 ap 802.11e periodic superframe |4 _ 3 C F P (Contention Free Period) C P (Contention Period) Beacon s t a Ack CF-Poll D a t a l CP-Poll ]CF-End T X O P T X O P « > E D C A T X O P E D C A T X O P \ Polled T X O P <• > Controlled Access Phases (CAP)' Figure 1-7 HCCA operation with periodic CFP PIFS Data/A AP (downstream) #• STA (upstream) EDCA TXOP Ack Poll SIFS SIFS SIFS PIFS -> 4-Data 7 ^ in Data/Ack 1 B Polled TXOP EDCA TXOP TXOP obtained by AP EDCA TXOP « _ Controller Access Phase ( C A P ) ' Figure 1-8 HCCA operation without CFP The decision of when to generate a C A P lies with the scheduler that is implemented in the access point. The 802.1 le standard does not mandate any scheduling and admission control mechanisms and leaves it to developers to devise their own solutions. However, a simple scheduler is presented in the standard as a reference (informative, not mandatory). This scheduler does not provide fair or guaranteed services, and is very inefficient for variable bitrate traffic [15] [16]. This fact emphasizes the need for devising scheduling algorithms that can provide the required QoS for Multimedia applications, an issue that this thesis addresses. 14 1.4 Previous Work Providing QoS in wireless access networks has been the focus of many research works in recent years. A s a result there are numerous solutions, proposed for different types of wireless networks. Our focus in this thesis is on the per-session QoS provisioning mechanisms, in particular fair scheduling algorithms. We also review some QoS solutions that are based on providing prioritized and aggregate services. In this section we first review these general solutions for wireless networks and then examine the works dedicated to 802.11 W L A N s . Devising fair scheduling algorithms for providing guaranteed access while maintaining service fairness in wired networks has been the center of attention in many recent research works (e.g. [18][19][20] [30]). Most of the notable proposed algorithms, such as Weighted Fair Queuing (WFQ), are packet based approximations of the ideal Generalized Processor Sharing (GPS) scheduler [18]. GPS is the fluid model scheduler that serves each queue a fair (weighted) amount of data in any duration of time. These solutions were mainly developed for wired networks in which packet loss or variation in server speed were not of concern. As a result their application in wireless networks required modifications to most of them. These modifications were needed to maintain the fairness of the algorithms when service disruption happened for one session, usually in the form of packet loss or broken link. In general, wireless networks are more error prone that wired networks and the probable packet losses are not negligible. In some wireless networks such as 802.11 W L A N s , the speed of transmission may change dynamically and may be different for each station, even for each packet. Therefore special measures are needed to maintain the fairness of the scheduling algorithm. 15 To address the issue of packet loss, several algorithms have been developed that try to achieve packet based approximations of GPS in wireless networks. A survey of such methods is found in [3] [7]. Some notable algorithms from this class of schedulers are Wireless Fair Service (WFS) [8], Idealized Wireless Fair Queuing (IWFQ) and its variation Wireless Packet Service (WPS)[9], and CIF-Q (Channel-Condition Independent Fair Queuing) [10]. These algorithms rely on a lead/lag model in which each session keeps a variable indicating whether the service it received is leading or lagging that of an equivalent error free system. When a session experiences a bad channel, its share of service time is lent to other sessions, and it w i l l be labeled as lagging. Later, when the channel condition improves, the lagging session can retrieve the service time borrowed by the leading sessions and compensate its lag. Depending on the pace of compensation for the lagging sessions, and the criteria for selecting the leading session from which service is taken back, different fairness and service guarantee properties are resulted. I W F Q and W P S present coarse short-term fairness and throughput bounds. CIF-Q and W F S achieve short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access. Although these algorithms may provide the necessary solution for wireless environments such as cellular networks, they lack the features that make them practical in a W L A N . In fact, these algorithms are designed for a single direction scheduling (essentially on the downlink from the access point) and are based on the assumption of a single fixed rate server. These assumptions are not applicable to a C S M A / C A network such as I E E E 802.11. A W L A N based on 802.11 shares the medium at all times between uplink and downlink flows and is inherently a distributed environment, it also allows different operational transmission rates for each station. This means that these existing 16 algorithms that were mainly for cellular networks are not directly usable in an 802.1 le (or 802.11) network. The issue of multirate operation has been considered in other notable algorithms, such as the works presented in [24] [25] [26]; However, these solutions lack the same features that are necessary for C S M A / C A networks. Yuan in [24] proposes a temporal fair algorithm, which is a variation of W F S , but the algorithm is suitable only for single direction scheduling in a T D D or F D D system and does not consider the shared medium nature of W L A N s . Tinnirello in [26] studies service time fairness but does not present any scheduling scheme. Considering that the above algorithms are not directly applicable to 802.11 W L A N s , we examine another class of QoS solutions specially designed for 802.11 networks. These solutions can be categorized into two groups of priority services and guaranteed access services. Priority services are provided through contention access mode of the M A C layer, while guaranteed access services use the polling mechanism of the M A C . Algorithms presented in [13] and [14] provide prioritized differentiated services to aggregated flows. These solutions are mainly based on the contention access mechanisms and provide QoS in a probabilistic manner to traffic aggregates. N i in [13] present a survey of several QoS methods based on contention access. The work in [14] presents a distributed deficit round robin algorithm that tries to enforce fairness through adjusting 802.11 contention mode parameters. The QoS provided by this method is probabilistic and applicable to aggregate of flows, therefore no guarantees can be made and unfairness of the algorithm is not bounded. 17 Contrary to contention mode solutions, research on providing per-session guarantees in W L A N s , especially using the new controlled access features of the 802.1 le standard, has been very limited. The 802.1 le standard itself proposes a simple algorithm (referred to as TGe in this dissertation), which does not provide fair services and is only effective for strict constant bit rate (CBR) traffic. The methods in [15] and [16] improve the proposed simple TGe scheduler, but are still not considered fair with guaranteed service provisioning. The method in [15] extends the original algorithm by adjusting the transmission duration based on the collected queue size information from the stations, and an estimation of its future queue size. Although this method is more efficient than the TGe algorithm, it is based on an estimation of the queue sizes and is only fair in the long run. Also , [16] proposes another extension to TGe by addressing the issue of inefficiency for variable bit rate ( V B R ) traffic; however, this method is inherently not fair and similar to [15] uses transmission opportunity assignments instead of packet scheduling, hence it is susceptible to long delays due to simultaneous bursty transmission that may occur on all flows. Flow isolation is also very poor with either algorithm presented in [15] and [16] due to the fact that they use admission control on average rate basis while service assignment is burst size dependent. Physical layer impairments such as packet loss are also not addressed efficiently by these algorithms. Our proposed solution, in this dissertation, uses the controlled access features of the 802.1 l e standard, a multirate fair GPS based scheduling algorithm, and a framework for combining uplink and downlink scheduling and achieves per session QoS in a W L A N . Where required, we revisit the solutions reviewed in this section and compare them with our proposed solution. 18 1.5 Thesis Scope and Organization This dissertation focuses on providing QoS to multimedia applications in W L A N s . This goal is achieved through scheduling solutions that provide fair guaranteed services for multimedia sessions in a W L A N . We target demanding applications such as voice and video telephony that have stringent delay and bitrate guarantee requirements. Such strict QoS requirements cannot be provided by the E D C A mechanism, especially in heavily loaded networks. Since E D C A is the most readily available QoS solution mechanism that comes as part of the standard, most vendors w i l l use it as the first step in migration from 802.11 based W L A N s to the new 802.1 le based QoS enabled networks. However, E D C A is based on probabilistic QoS provisioning and the level of service it provides, especially in heavily loaded networks, is not adequate for demanding application such as voice and video telephony. The delay and delay jitter measurements from experiments with E D C A based networks confirm this fact. Also, we observe, through analysis and simulation experiments, that the performance of E D C A is very sensitive to its parameters; and even with optimized parameters, its contention based nature wi l l result in degraded service. We provide a throughput analysis of the E D C A mechanism in saturation mode in Chapter 2 and examine its performance, through simulation experiment in Chapter 3 and Chapter 4. We have also compared the performance of E D C A with that of an adaptive E D C A algorithm as well as a periodic C F P based scheduling in [23]. Having shown the shortcomings of E D C A , we develop a scheduling framework in Chapter 3 that provides a complete QoS solution for fair, guaranteed service provisioning in 802.1 le based W L A N s . This solution is applicable to any multiple access network similar to 802.1 le W L A N . It can also use any admission control mechanism, such as those described in the 19 standard [2], its extensions [16] [17], or any generic wireless admission control mechanism. Admission control is outside the scope of this dissertation and we focus on the scheduling solution and bandwidth assignment algorithms for achieving real-time multimedia communications. As it was discussed in section 1.4, W L A N s have certain features that prevent us from using the available QoS mechanisms for wired networks or cellular wireless networks. In a W L A N environment, deriving QoS mechanisms that achieve fairness and provide delay and loss guarantees, is much more challenging for the following reasons: The medium access is done in a distributed manner among stations and any scheduling technique has to co-ordinate stations instead of simply serving local queues. - The conventional single server queuing model is not applicable i f a mixture of prioritized and reservation based traffic are to be served in a distributed W L A N . The medium data rate might change during the lifetime of a session; contrary to the fixed server rate of the conventional schedulers. Packet loss and retransmission also affect the fairness of the algorithm. Given the above facts we propose a scheduling framework in Chapter 3 that centralizes the scheduling task in the access point (addressing the first issue). We achieve this goal by introducing the concept of virtual packets, which are representations of stations actual packets in the access point, and combining the scheduling task for virtual and actual packets. Then, we introduce a new queuing model integrated with a generalized processor sharing based scheduler as well as a traffic shaping scheme to achieve fair guaranteed services using the centralized scheduler (addressing the second issue). This solution provides us with the desired QoS performance for a fixed rate W L A N . 20 W e a d d r e s s t h e i s s u e o f m u l t i r a t e o p e r a t i o n o f a Q o S e n a b l e d W L A N i n C h a p t e r 4, w h e r e w e e x t e n d t h e s c h e d u l i n g a l g o r i t h m t o p r o v i d e e i t h e r t h r o u g h p u t o r t e m p o r a l f a i r n e s s . I n t h i s c h a p t e r , w e d e v e l o p t h e h y p o t h e s i s o f G P S b a s e d t e m p o r a l a n d t h r o u g h p u t f a i r s c h e d u l i n g , a n d a n a l y z e t h e c o m p l e x i t y i s s u e s t h a t m a y a r i s e . W e t h e n d e s c r i b e o u r r e c o m m e n d e d C A P S s o l u t i o n w i t h a m o d i f i e d S F Q a t i t s c o r e , a n d p r e s e n t a n e x t e n s i v e d e l a y a n a l y s i s o f t h i s m o d e l , w h i c h i s f o l l o w e d b y i t s p e r f o r m a n c e e v a l u a t i o n . W e c o n c l u d e t h i s t h e s i s i n C h a p t e r 5, w h e r e w e p r e s e n t a s u m m a r y o f t h e m a i n c o n t r i b u t i o n s o f t h i s t h e s i s t o t h e f i e l d o f w i r e l e s s m u l t i m e d i a n e t w o r k i n g . P o t e n t i a l r e s e a r c h s u b j e c t s t h a t c a n i m m e d i a t e l y f o l l o w t h i s r e s e a r c h a r e a l s o p r e s e n t e d i n t h i s c h a p t e r . 21 1.6 References [1] Wireless L A N Medium Access Control ( M A C ) and Physical Layer (PHY) specifications. A N S I / I E E E Std 802.11: 1999 (E) Part 11, ISO/IEC 8802-11, 1999. [2] I E E E Standard 802.1 le / Amendment 8, "Medium Access Control ( M A C ) Quality of Service (QoS) Enhancements," July 2005. [3] 3GPP TS 23.234: "3GPP Systems to Wireless Local Area Network ( W L A N ) Interworking; System Description (Release 6)," TS 23.234. v. 1.10.0, May 2003. [4] Broadband Radio Access Networks ( B R A N ) ; H f P E R L A N Type 2 Functional Specification; Data Link Control (DLC) Layer; Part 1: Basic Data Transport Function, ETSI Report T R 101 761-1, Ver. 1.1.1, Apr i l 2000. [5] Broadband Radio Access Networks ( B R A N ) ; H I P E R L A N Type 2; Data L ink Control ( D L C ) Layer; Part2: Radio Link Control (RLC) Sublayer, E T S I Report T R 101 761-2, Ver. 1.1.1, Apr i l 2000. [6] H . Fattah and C. Leung, " A n Overview O f Scheduling Algorithms In Wireless Multimedia Networks", Wireless Communications, IEEE, vol . 9, Issue 5, pp. 76 - 83, Oct 2002. [7] T. Nandagopal, S. L u and A . V . Bharghavan, " A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms", Wireless Networks, vol. 8 , Issue 2/3, pp. 231 - 247, March-May 2002. [8] S. L u , T. Nandagopal and V . Bharghavan, "Fair scheduling in wireless packet networks", A C M M O B I C O M ' 9 8 , October 1997. 22 [9] S. L u , V . Bharghavan and R. Srikant, "Fair scheduling in wireless packet networks", I E E E / A C M Trans, on Networking, vol . 7 , Issue 4, pp. 473 - 489, August 1999. [10] T.S. Ng, I. Stoica and H . Zhang, "Packet Fair Queueing Algorithms for Wireless Networks with Location-Dependent Errors", Proc. of I E E E I N F O C O M '98, vol. 3, pp. 1103-1111, March 1998. [11] A . Kamerman and L . Montean, " W a v e L A N - 1 1 : A High-Performance Wireless L A N far the Unlicensed Band", Be l l Labs Technical Journal, pp. 118-133, 1997. [12] J. Rosenberg, et. al., "SIP: Session Initiation Protocol", R F C 3261, June 2002. [13] Q. N i , L . Romdhani, and T. Turletti. " A Survey of QoS Enhancements for I E E E 802.11 Wireless L A N " , Wiley Journal of Wireless Communication and Mobi le Computing ( J W C M C ) , John Wiley and Sons Ltd. , vol. 4, Issue 5, pp. 547-566, 2004. [14] W . Pattara-Atikom, P. Krishnamurthy, S. Banerjee," Distributed mechanisms for quality of service in wireless L A N s " , Wireless Communications, IEEE, vol . 10 , Issue: 3 , pp. 26 - 34, June 2003. [15] P. Ansel, Q. N i , and T. Turletti, " A n efficient scheduling scheme for I E E E 802. l ie , " WiOpt'04: Modeling and Optimization in Mobile , AdHoc and Wireless Networks, 2004. [16] A . Gri lo, M . Macedo and M . Nunes, " A Scheduling Algorithm for QoS Support in I E E E 802 . l i e Networks", I E E E Wireless Communications, vol . 10, Issue 3, pp. 36-43, June 2003. 23 [17] A . Banchs, M . Radimirsch, X . Perez, " Assured and expedited forwarding extensions for I E E E 802.11 wireless L A N " Quality of Service, 2002. Tenth I E E E Int. Workshop on, pp. 237 - 246, M a y 2002. [18] A . Parekh and R. Gallager, " A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case," I E E E / A C M Trans, on Networking, vol. 1, no. 3, pp. 344-357, June 93. [19] J .C.R. Bennett, H . Zhang, " W F 2 Q : Worst-Case Fair Weighted Fair Queueing", I N F O C O M '96. Fifteenth Annual Joint Conference of the I E E E Computer Societies. Networking the Next Generation. Proceedings IEEE, vol. 1, pp. 120-128, March 1996. [20] P. Goyal, H . M . V i n , H . Cheng, "Start-Time Fair Queueing: A Scheduling Algorithm For Integrated Services Packet Switching Networks", Networking, I E E E / A C M Transactions on, vol. 5, Issue 5, pp. 690-704, Oct. 1997. [21] Y . Pourmohammadi Fallah, H . Alnuweiri "Hybrid Poll ing and Contention Access Scheduling in I E E E 802.1 l e W L A N s " , accepted for publication in the Journal of Parallel and Distributed Computing, Elsevier, 2006. [22] Y . Pourmohammadi Fallah, H . Alnuweiri " A controlled-access scheduling mechanism for QoS provisioning in I E E E 802.1 le wireless L A N s " A C M international workshop on Quality of service & security in wireless and mobile networks Q2SWinet '05, pp. 1 2 2 - 129, 2005. [23] Y . Pourmohammadi Fallah, H . Alnuweiri , "Enhanced Controlled-Access and Contention-Based Algorithms for I E E E 802.1 l e Wireless L A N " , Wireless Networks, 24 Communications and Mobile Computing, 2005 International Conference on vol. 1, pp 4 0 9 - 4 1 4 , June 2005. [24] Y . Yuan, D . Gu, W . Arbaugh, J. Zhang, " Achieving Fair Scheduling Over Error-Prone Channels in Multirate W L A N s " , Wireless Networks, Communications and Mobile Computing, 2005 International Conference on, vol. 1, pp. 698-703, June 2005. [25] Z . Jiang, N . K . Shankaranarayana , "Channel Quality Dependent Scheduling for Flexible Wireless Resource Management", Global Telecommunications Conference, 2001. G L O B E C O M '01. I E E E , vol. 6, pp. 3633-3638 , Nov. 2001. [26] I. Tinnirello, S. Choi , "Temporal fairness provisioning in multi-rate contention-based 802.1 le W L A N s " , Wor ld of Wireless Mobi le and Multimedia Networks, Sixth I E E E International Symposium on a, pp. 220 - 230, June 2005. [27] Y . Pourmohammadi Fallah , H . Alnuweiri , "Performance Analysis of Controlled Access Phase Scheduling Scheme for Per-Session QoS Provisioning in I E E E 802.1 le Wireless L A N s " , Proc. of 2006 I E E E Wireless Communications and Networking Conf., vol . 3,pp. 1414-1420, Apr i l 2006. [28] J .Y . Le Boudec, "Application of Network Calculus To Guaranteed Service Networks", I E E E Trans on Information theory, vol . 44, Issue 3, M a y 1998. [29] R. Agrawal, R. L . Cruz, C. Okino and R. Rajan, "Performance Bounds for Flow Control Protocols", I E E E Trans, on Networking, vol . 7, No3, pp. 310-323, June 99. [30] H . Alnuweiri , H . Tayyar, "Analysis of virtual-time complexity in weighted fair queuing.", Computer Communications (2005), vol . 28, Issue 7, pp. 802-810, 2005. 25 Y . Pourmohamrnadi Fallah, H . Alnuweiri , "Modeling and Performance Evaluation of Frame Bursting in Wireless L A N s " , Proc. of 2006 Int. Wireless Communications and Mobi le Computing Conf., pp 869-874, July 2006. 26 Chapter 2. Generalized Saturation Throughput Analysis of EDCA 2.1 Introduction The new I E E E 802.1 le standard introduces enhancements to the Medium Access Control ( M A C ) layer of the original 802.11 standard for Wireless Local Area Networks ( W L A N s ) [1]. While the original 802.11 standard supports only best effort services, the new standard offers priority-based access through several mechanisms. The new services are provided through a new access scheme called Enhanced Distributed Channel Access ( E D C A ) . E D C A is built on top of the original distributed coordination function (DCF) of the 802.11 standard, and introduces class-specific contention window sizes and initial deferment (or Inter Frame Spacing, IFS) times. Probabilistic priorities are possible using these prioritized access parameters. There have been several efforts to analyze the behaviour of the E D C A mechanism under saturation conditions, a model that assumes all stations queues remain continuously backlogged. In this regards, we found models developed by Robinson [3] and Xiao [4] noteworthy. However, the model developed in [4] only considers the contention window size for prioritizing frames, ignoring the important effect of different IFS times for different traffic classes (using Arbitration IFS, or AIFS timers). The model developed in [3] considers both A version of this chapter has been submitted for publication. Yaser Pourmohammadi Fallah, Samer El-Housseini, Hussein Alnuweiri , A Generalized Saturation Throughput Analysis for I E E E 802.1 le Contention-Based M A C . 27 contention-window and AIFS parameters, but assumes a post collision behaviour that does not comply with the 802.11 or 802.1 l e standards. When a collision occurs in an 802.11 W L A N , the stations involved in the collision wait for an A c k Timeout period after the end of collision before they can realize that a collision has occurred. Then, they w i l l resume normal contention. Stations not involved in collision only wait until the end of the collided transmission and then resume normal operation. The model in [3] assumes that non-colliding stations wi l l wait for an EIFS period before resuming contention. Apart from the post collision behavior assumption, the study published in [3] presents a correct way of modeling the behavior of contending stations with two different priorities, or Access Categories. In this chapter, we present a correction of the model in [3] and generalize it to an arbitrary number of priorities instead of only two. Our model provides a complete solution for modeling 802.1 l e E D C A operating in saturation mode. 2.2 Model Development E D C A is a contention-based access method whereby stations that need to access the medium after a busy period must wait for a random duration of time before they are allowed to start transmitting on the channel. This random waiting time is different for each priority and consists of two components: AIFS which is a short time-interval, and a back-off time randomly chosen from a class (access category) specific contention window (CW) size. I E E E 802.11 defines four different length AIFS values for each priority class. Similarly, the C W sizes are specified by priority-specific parameters a C W m i n and oCWraax. Each queue must first sense an idle medium (channel) for an AIFS plus a random-backoff period before transmitting a frame. The backoff duration is chosen randomly between 1 and C W slots, and stored in a backoff counter. C W is initially set to a C W m i n then doubled after each collision 2 8 until it reaches aCWmax. A successful transmission resets CW back to aCWmin. Given that each queue in E D C A contends for the channel independently, we can model the backoff process of each queue separately, and apply the DCF model presented in [2] to each queue. An approximation in this modeling, also used by Robinson in [3], is to ignore the effect of internal contention resolution that happens between the queues of one station. In E D C A if two queues of the same station attempt to transmit at the same time, the queue with higher priority wins and the other queue repeats its backoff process without incrementing its retry counter. We verified the accuracy of the model in [2] and use it in the first stage of our analysis. To model a single queue, we begin by mathematically defining the backoff process behavior for stations operating in a saturation mode. In this case, 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 can be done following the same queuing strategy described in [2] and [3], whereby the backoff value was modeled as a two-dimensional Markov Process. One dimension of this chain describes the backoff counter value, while the other tracks the retransmissions stage, in effect modeling the exponential backoff procedure (refer to [2] for a detailed examination of this model). For such a model to be correct there are two fundamental assumptions. First, in each idle slot, each queue may attempt to transmit with an independent and constant priority x. Second, in each transmission attempt and regardless of the number of past collisions, a packet transmission may result in a collision with an independent and constant probability p. However, since in E D C A each slot after a busy period is available to only a subset of access categories due to AIFS-differentiation, the number of contending stations may be different in 2 9 each slot. For this reason, an average conditional collision probability p is used instead of p, and the same analysis as in [2] is applicable. From this model the following equation is derived that describes Tj as a function of pj for each priority level j (refer to Appendix A for more details): i+Wj + pjWj^Qpjy (2.1) In (2.1) Wj is aCWmin for class j and nij is the maximum number of exponential backoff stages ( aCWmax = 2mjWj). To solve for all Tj and pp we need another set of equations describing p ; i n terms Tj for each priority level. For this purpose we need to find the probability of collision for each class of traffic in each slot after a busy period and then find the average collision probability for each class (p ; ) . The next section describes how p . is derived. n1+n2+n3 ^ I ' I I I J I L Slot 1 2 3 ... j , M M+1 . . . W „ 1-P" ptr z=1 z=M Figure 2-1 Modeling slot-occupancy for different contention zones 30 2.3 Slot Occupancy Recall that each priority level has 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, 2, . . . , K) contending stations (or queues). Each priority level has an AIFS value equal to j slots, meaning that priority level j w i l l start contention in the jth idle slot. For example i f only the three priorities classes 1, 4,and 7 are present, then slots 1 to 3 wi l l have ri\ contending stations, while slots 4 to 6 wi l l have ri\+ ri4 stations, slot 7 onwards wi l l see n\+ri4+n7 contending stations. We model the contention slots after a busy period by a separate Markov Chain in order to derive the slot occupancy and probabilities of collision in each slot. Our model, depicted in Figure 2-1, extends the model presented in [3]. In Figure 2-1 W m i n is the minimum of all the aCWmax values. If n, stations from priority / are present, then the equations that govern this model are: ptr = i rZ=z 1 n;=1(i-^y\ \<Z<M M (l-r ( .) \ z>M •0tr Knowing •« z = z , the probability of at least one transmission in zone z, and assuming that system is in equilibrium with stationary distribution bj (i :l..Wmi„) we have: bl=<\-P^-x>bi_v (i:2.. Wmin-1) by/ min ' Pz=M = °W min-1 ' Q ~ P'z=M ) W min Wmin X^= 1 (2-3) 31 Using an approximation similar to [3], we assume W m i n is the smallest C W m a x in the system. Then bj becomes: i + z ^ ' n ' . a - ^ p + ^ - n ^ ' a - ^ ) ) (2.4) Using (2.4) and (2.3), all the stationary probabilities are computed based on the values of Tj (where j is the traffic class). Next, we find the average conditional collision probability P ; for each priority j (defined as the probability that a transmitted packet of class j encounters collision). To do so we need to find the probability that a given slot z experiences a collision for a class-y station. Denoting this probability by Pc[ we can derive it as follows knowing the number of eligible stations for each slot, and the probability of each station transmitting in that s l o t ( r ; ) : Pc£ = 1 - (1 - T, )"'-' , Pcff = 0 , Pc(:l2 = 1 - (1 - T, )"'-' • (1 - T2 P P c z i = 2 2 = l - d - " * - , ) " • • (1-T 2 )" J - 1 Pc{=l-(l-Tj)nr]. fl (l-Tkr far j<z k=\,k*j PcJz=0 for j>z (2.5) From (2.5), we find the average conditional probability of collision for class-y stations by summing the slot specific probabilities weighted according to slot / occupancy bf. W min Pj-^brPcU (2.6) i=j Given that P)Js a function of T ; f o r several fs, (2.6) and (2.1) form a system of nonlinear equations, amenable to solution by numerical methods. Using such methods we find the 32 average collision and transmission probabilities for each priority class (Pj,Tj). Consequently we can derive the achievable throughput for each class. 2.4 Throughput Analysis To find the throughput of the system we introduce the transmission-event period (Tp), defined as the expected time between such events as successful transmissions, collisions, and idle slots. Since the probabilities of success and collision in each slot after a busy period depend on the slot occupancy, we calculate the expected transmission event period by considering each slot and weighting its corresponding expected duration according to the slot occupancy probability bt as follows: W m i n TP = £ • (a - pz% )-s+pz% • r + p ™ • r ° l ) (2.7) Observe that T 5 in (2.7) is the average duration of one successful transmission, including data and control frames such as A c k and the IFS deferment times [2]; this may also include a bursty transmission of multiple frames that is limited by a "transmission opportunity" (TXOP) duration and can be different for each priority level [6]. T°l is the average time spent in each collision (i.e., average frame length plus IPS deferments), and S is the length of an idle slot which is the defined slot time in 802.11. Also Pzlt and Pz°. denote the average probabilities of a given slot i seeing a successful transmission or a collision, respectively. The probability of an idle slot occurring in zone i is simply given by (\-Pz=i). To ca l cu l a t e^ , , we first find pfz=i, the probability of successful transmission by a single station of class j in slot i. PjSz=i is in fact l-P'L the probability that a station of class j transmits ( r y ) , and no other station transmits ( ^ - ) ; thus we have: 33 0 , otherwise Therefore, the probability that the outcome of slot i is a successful transmission by any class is found as (given that the success probabilities are mutually exclusive between any two stations): i pzs=i = £>r p/*=/> (2.9) 7 = 1 and the probability of slot / seeing a collision is: Pg =P»i-PzS=i (2.10) As the final step in computing the W L A N throughput, we derive the expected payload size (EPj) for each class j which is successfully served during a transmission period: w • EPj = '^jty • rijPjz=i • PL (pL r e f e r s t 0 m e average payload size in a frame) (2.11) Dividing (2.11) by (2.7) we can derive the throughput for each class j: EP Throughput^—- (2.12) 2.5 Simulation Evaluation To evaluate our analytical model we have solved the model equations using numerical methods and compared the results with simulation results generated from an accurate E D C A simulator (developed at U B C ) . The comparison depicted in Figure 2-2 shows that the mathematical model results and the simulation results are very close and almost identical. In Figure 2-2, we plotted the collision probability p and the throughput versus the number of stations for four priorities A to D (A being the highest priority). The four priorities correspond 34 to the four access categories (AC[3] to AC[0]) currently defined for I E E E 802.1 le . As shown in Figure 2-2, both AIFS and C W play a significant role in providing throughput service differentiation. One notable fact is that the difference in collision probability is much more in the case of AIFS differentiation. (a) Collision Probability p vs. Number of Stations (b) Throughput in Kbits vs. Number of Stations 8 10 12 Number of Stations (c) Collision Probability p vs. Number of Stations 10 12 Number of Stations B 10 12 Number of Stations (d) Throughput in Kbits vs. Number of Stations 10 12 Number of Stations Figure 2-2: Collision Probability & Saturation Throughput vs. Num. of Stations (per class). Top plots- AIFS is 1 for all classes, CWmin, CWmax are { A(8,16), B(16,32), C(24,48) ,D(32,64)} Bottom plots - CWmin=32 & CWmax=64 for all classes, AIFS is 0,1, 2, and 3 for classes A to D. We also note that the throughput of each class, and the system, degrades considerably when the number of stations increases. We see in later chapters of this thesis that this performance degradation limits the ability of E D C A to provide services to multimedia applications in a W L A N . In particular, without changing the default E D C A parameters (which is allowed by the 35 standard) the system performance degrades to a level that makes the system unusable, especially for high priority traffic. Our model, presented in this chapter, can be used as an analytical tool for devising adaptive algorithms that adjust E D C A parameters in order to achieve better performance in an 802.1 l e W L A N . The presented model complements previous works on analyzing saturation operation of a W L A N . 3 6 2.6 References [1] I E E E 802.1 le Standard - Amendment 8: Medium Access Control ( M A C ) Quality of Service Enhancements, July 2005. [2] G . Bianchi, "Performance Analysis of the I E E E 802.11 Distributed Coordination Function", I E E E J. on Selected Areas in Communications, vol . 18, no. 3, March 2000. [3] J. Robinson, and T. Randhawa, "Saturation Throughput Analysis of I E E E 802.1 le Enhanced Distributed Coordination Function", I E E E J. on Selected Areas in Communications, vol . 22, Issue 5, pp. 917 - 928, June 2004. [4] Y . Xiao, "Performance Analysis of I E E E 802.1 l e E D C F under Saturation Condition", I E E E International Conf. on Communications, vol. 1, pp. 170-174, June 2004. [5] J. Hui , M . Devetsikiotis; " A Unified Model for the Performance Analysis of I E E E 802 . l i e E D C A " , I E E E Transactions on Communications, vol . 53, Issue 9, pp. 1498 -1510, Sept. 2005. [6] Y . Pourmohammadi Fallah, H . Alnuweiri , "Modeling and Performance Evaluation of Frame Bursting in I E E E 802.11 W L A N s " , Proc. of 2006 Int. Wireless Communications and Mobile Computing Conf., pp. 869-874, July 2006. [7] J.W. Tantra, C. H . Foh, A . B . Mnaouer, "Throughput and Delay Analysis of the I E E E 802.1 l e E D C A Saturation", 2005 I E E E International Conference on Communications, vol . 5, pp. 3450 - 3454, 16-20 May 2005. 3 7 Chapter 3. Per Session QoS Provisioning in WLANs 3.1 Introduction Supporting real-time multimedia applications such as voice-over-IP, video telephony and T V over Wireless Local Area Networks ( W L A N ) requires realizing guaranteed services that are not currently provided by existing W L A N technologies such as I E E E 802.11 [1 ]. To address this issue, the I E E E has approved a new standard, I E E E 802 . l i e [2], to enhance the original M A C layer of the 802.11 standard with features that facilitate guaranteed and differentiated service provisioning. However, the standard only specifies the features required for the new service provisioning and leaves the design of specific scheduling disciplines that utilize these features to the developers and equipment vendors. The solution proposed in this chapter fills this gap by showing how to utilize the available features to provide guaranteed services for real-time multimedia applications. We target the infrastructure mode of operation in which a central access point (AP) controls the network. Most commercial and residential W L A N s use this mode. The need for providing Quality of Service (QoS) for real-time applications in wireless networks has been driving research activities and standardization efforts for some time. In A version of this chapter has been accepted for publication. Yaser Pourmohammadi Fallah, Hussein Alnuweiri, Hybrid Polling and Contention Access Scheduling in IEEE 802.1 le WLANs , Journal of Parallel and Distributed Computing, Elsevier, Vol . 67, Issue 2, pp. 242-256, February 2006. 38 particular, there have been considerable efforts in devising fair scheduling algorithms for wireless environments [3]. These efforts were mostly concentrated on scheduling in cellular networks or generic wireless environments. For example, some notable algorithms such as W F S (Wireless Fair Service) [4], I W F Q (Idealized Wireless Fair Queuing) and its variation Wireless Packet Service (WPS)[5], and CIF-Q (Channel-Condition Independent Fair Queuing) [6] address the scheduling issue in a general wireless network. Other algorithms such as the work presented in [8] address the scheduling issue in an access network in which broadcast and peer-to-peer communications are combined. I W F Q and W P S present coarse short-term fairness and throughput bounds. CIF-Q and W F S achieve short-term and long-term fairness, short-term and long-term throughput bounds, and tight delay bounds for channel access. However, these algorithms are designed for a single direction scheduling (essentially on the downlink from the access point) and are based on the assumption of a single fixed rate server. These assumptions are not applicable to a C S M A / C A network such as I E E E 802.11. A W L A N based on 802.11 shares the medium at all times between uplink and downlink flows and is inherently a distributed environment, it also allows different operational transmission rates for each station. This means that these existing algorithms that were mainly for cellular networks are not directly usable in an 802.1 le (or 802.11) network. The multi-rate operation is considered in other notable algorithms, such as A W F S [9] [10]; but these algorithms also lack the same features that are necessary for a distributed C S M A / C A environment and do not consider the shared medium nature of W L A N s . There also exists another set of QoS solutions specially designed for 802.11 networks. Some of these algorithms, such as the ones proposed in [11],[15], and [16] provide prioritized differentiated services to aggregated flows. These solutions are mainly based on the contention 39 access mechanisms and provide QoS in a probabilistic manner to traffic aggregates. In fact, research on providing per-session guarantees in W L A N s , especially using the new controlled access features of the 802.1 le standard, has been very limited. The 802.1 le standard itself proposes a simple algorithm (referred to as TGe in this thesis), which does not provide fair services and is only effective for strict constant bit rate (CBR) traffic. The methods in [13] and [14] improve the proposed simple TGe scheduler, but are still not considered fair with guaranteed service provisioning. The method in [13] extends the original algorithm by adjusting the transmission duration based on the collected queue size information from the stations, and an estimation of its future queue size. Although this method is more efficient than the TGe algorithm, it is based on an estimation of the queue sizes and is only fair in the long run. Also , [14] proposes another extension to TGe by addressing the issue of inefficiency for variable bit rate ( V B R ) traffic; however, this method is inherently not fair and similar to [13] uses transmission opportunity assignments instead of packet scheduling, hence it is susceptible to long delays due to simultaneous bursty transmission that may occur on all flows. Flow isolation is also very poor with either algorithm presented in [13] and [14] due to the fact that admission control is done on average rate basis while service assignment is burst size dependent. Physical layer impairments such as packet loss are also not addressed efficiently by these algorithms. Our solution focuses on using controlled access mechanisms to provide per session fair quality of service for real-time applications. We present a framework that allows for efficient scheduling of controlled and contention access periods while maintaining service guarantee and short term fairness through employing Generalized Processor Sharing (GPS) based scheduling. We demonstrate that it is possible to provide guaranteed per-session QoS without 40 need to depart from the I E E E 802.1 le standard specifications as is the case with most other solutions. We identified three characteristics of an 802.1 le W L A N that need to be taken into account when devising such a QoS solution: • First, the solution must provide a way of efficiently sharing the medium between uplink and downlink flows; meaning that the solution should provide a unified scheduling scheme for the combined traffic flows from both directions. • Second, the 802.1 l e describes access to the medium in a prioritized contention based scheme that is intermittently interrupted by contention free periods. The scheduler must efficiently distribute contention free and contention periods with flexibility of adjusting the duration of each access type on demand. • Third, the scheduler must achieve proportional (weighted) fairness among sessions and be able to handle the effects of wireless channel variation. We have developed a scheduling solution that addresses all these issues. To the best of our knowledge this is the first design that addresses all the above issues in a single framework for I E E E 802 . l i e networks. In this chapter, we first provide a short description of the 802.1 l e standard, highlighting its controlled access mechanism. We then present a new access scheduling framework designed for the 802.1 le M A C , and capable of providing per-session QoS guarantees for such applications as interactive voice and video over W L A N . Essentially, the proposed solution provides guaranteed services to flows that make reservation with the W L A N Access Point (AP) by means of the available M A C signalling methods, while at the same time, allowing the normal contention based access to take place using the remaining capacity of the channel. This approach is different from the existing polling mechanisms in which long alternating 41 contention free and contention periods are generated (e.g., [19]), resulting in uncontrolled delay bounds and inefficient operation. Our design approach is called Controlled Access Phase Scheduling (CAPS) . The C A P S algorithm is based on a number of novel concepts such as Virtual Packet generation and combined scheduling of uplink and downlink flows [17], as well as using the well established Generalized Processor Sharing (GPS) based scheduling discipline in a new unified queuing framework for both contention and controlled access mechanisms. 3.1.1 IEEE 802.11e MAC Specifications The I E E E 802.1 l e standard introduces new features that enhance the M A C layer of the original 802.11 standard in order to provide QoS to real-time multimedia applications [2]. The offered QoS can be categorized into two classes of prioritized contention access and guaranteed contention free access. Both schemes are built on top of an enhanced version of the Distributed Coordination Function (DCF) which is the main function of the 802.11 M A C . In general, access to the medium is done in a prioritized contention manner during each Contention Period (CP). The original M A C allowed the A P to initiate Contention Free Periods (CFP) on a periodic basis. The 802.1 le M A C redefines C F P as a Controlled Access Phase (CAP) and allows initiating mini CFPs or C A P s arbitrarily even during the contention period. The basis for the 802.11 M A C is a C S M A / C A mechanism (Carrier Sense Multiple Access with Coll is ion Avoidance). This mechanism is essentially a contention access method that uses a binary backoff procedure for collision resolution and inter-frame space (IPS) time intervals for prioritizing access to the medium. The rules describing the timing relations in the M A C are described by D C F . Stations that have frames to send are only allowed to transmit i f they find the channel idle for a frame-specific IFS duration (Figure 3-1). For data frames in contention mode, this waiting time is extended by a random backoff interval as well . If priorities are 42 specified, as in 802.1 le , the contention window from which the random backoff number is selected, and the IFS waiting times may be different for each priority level. The IFS gap for data and R T S frames is A I F S (Arbitration IFS), while beacons and initial C A P messages (poll or data) use a shorter gap time, PIFS, that gives them a higher priority in accessing the channel. Acknowledgements (Ack), packet fragments, responses to polls and C T S messages use a SIFS gap which is the shortest IFS, giving them the highest access priority. SIFS is only used when contention has already been won, or during a contention free period; therefore, it provides an uninterrupted control of the channel for as long as frames are sent with SIFS gaps. Pol l and data frames that are sent using PIFS (to start a C A P or CFP) are also able to grab the channel unchallenged i f they follow a completed frame exchange sequence; this is because after a frame exchange cycle finishes, all stations have to use AIFS plus backoff interval before they can access the channel while A P can send after PIFS, in effect giving it absolute priority over others. However, i f the medium was free for a long time after a busy period, the PIFS waiting for A P and the AIFS plus backoff for stations might coincide, resulting in collision, or a data frame might grab the channel sooner. In any case, the A P can recover quickly by grabbing the channel after PIFS waiting following the busy or collision situation. This is because it does not have to do a backoff before starting a C A P or C F P and only needs to wait a PIFS, thus having guaranteed contention free access [2]. I m m e d i a t e a c c e s s w h e n M e d i u m i s f r e e > = D I F S / A I F S [ i ] A l F S m •run A I F S [ I ] D I F S p i F S / A I F S i P I F S C o n t e n t i o n W i n d o w B u s y m e d i i u m B a c k o f f s l o t s 1 N e x t F r a m e S l o t t i m e D e f e r A c c e s s S e l e c t S l o t a n d D e c r e m e n t B a c k o f f a s l o n g a s m e d i u m i s i d l e Figure 3-1 Some IFS relationships in D C F and E D C A 43 The 802 . l i e standard also introduces an important new concept: Transmission Opportunity (TXOP) . A transmission opportunity specifies the duration of time in which a station can hold the medium uninterrupted and perform multiple frame exchange sequences consequently with SIFS spacing. A station can obtain a T X O P either through contention or be granted a T X O P by the A P . After completion of each frame exchange cycle during a T X O P , i f enough time is left in the station's T X O P , it can retain control of the medium and commence a new frame exchange cycle after a SIFS period, otherwise it does not continue transmission using SIFS and enters the normal contention mode using AIFS deferred access and normal backoff. M A C layer rules for controlling and coordinating access to the wireless medium in the 802 . l i e standard are specified under the Hybrid Coordination Function (HCF) protocol. H C F offers two access mechanisms; E D C A (Enhanced Distributed Channel Access) which is an enhanced version of D C F and is used for contention based access, and H C C A ( H C F Controlled Channel Access) that replaces the Point Coordination Function (PCF) of the 802.11 standard and specifies the polling or controlled access schemes. The 802.1 l e standard defines 8 different traffic priorities in 4 access categories and also enables the use of traffic stream IDs (TSIDs), which allow per flow resource reservation. Under E D C A access mechanism, depending on the type of a frame (Data or Control) and its priority, different AIFS values are used (Arbitration IPS or A I F S in Figure 3-1). The backoff windows are also different for each priority. Shorter AIFS times and smaller contention windows give higher access priority. This prioritization enables a relative and per-class (or aggregate) QoS in the M A C . The 802 . l i e standard allows for dynamically adjusting most E D C A parameters, facilitating performance enhancement using adaptive algorithms. 44 Under H C C A , access to the medium is controlled by the Access Point. H C C A is an enhanced version of the Point Coordination Function (PCF) of the original standard that controls the CFPs. The most important enhancement provided by H C C A is the new concept of Controlled Access Phase or C A P . A C A P is a usually short contention free period that is initiated during a contention period (Figure 3-2). A n access point can start a C A P by sending a poll or data frame while it finds the medium idle for PIFS. Since PIFS is shorter than AIFS (used by E D C A ) , the A P is able to interrupt the contention operation and generate a C A P at almost any moment (with at most one packet length delay). A C F P (as described in 802.11) is also considered a C A P (Figure 3-2). However, with capability to generate C A P s at any time, there is no need for periodic CFPs. The C A P generation capability is the main feature that we use for providing per-flow QoS. The 802.1 l e standard does not specify the scheduling discipline that determines when C A P s are generated and leaves it to system developers to devise such a scheme. API ** 7 ? CFP (Contention Free Period) CP (Contention Period 802.11e periodic superframe Beacon 4 CF-Poll CP-Poll Data CF-End STAs < -TXOP * /I Controlled Access Phases (CAP) < > < » Polled EDCA TXOP TXOP PIFS -> f-PIFS s p AP (downstream) S 4 V STAs (upstream) Polled TXOP < -> \ EDCA TXOP TXOP obtained by AP Controller Access Phase (CAP) Figure 3-2 802.lie H C C A : C A P generation with C F P (left), without C F P (right) The guaranteed access with bounded delay gives the A P the power to start a contention free access at any time with at most one packet length delay. This feature can be used to provide services for real-time applications that cannot tolerate unbounded delay or high jitter. At the start of a C A P the access point can send either a data frame (downlink C A P ) or a poll message 45 (uplink C A P ) after sensing the channel idle for PIFS. A C A P may include more than one consecutive frame exchange sequences that are limited by a station or flow specific T X O P . When data frames are sent downlink, the A P decides for how long it w i l l send frames to a particular destination; for uplink data frames, a station is only allowed to send frames for the duration of the T X O P granted by the A P . If this duration is short, the station must fragment its frames and only send the part that fits in the granted T X O P . If T X O P is set to zero the station is only allowed to send one frame (size limited by other M A C regulations). The 802.1 le standard draft provides flow IDs (Traffic Stream ID) in frame formats to enable per-flow QoS handling. It also specifies that it is the responsibility of stations to setup traffic streams (flows) and request resource reservation. This is done through sending an A D D T S request to the A P and asking for a traffic stream to be setup with specific traffic specifications. The information carried in the A D D T S request is used by the admission control and scheduling functions of the A P . The A D D T S response by A P completes the traffic stream setup procedure. The standard draft specifies the format in which the traffic stream specifications are described. In fact, we found this description to be very thorough. In particular fields such as service interval and start time are very useful in setting up scheduled access and poll messages. 3.2 CAPS: Controlled Access Phase Scheduling Given the characteristics of an 802.1 l e W L A N , we present a unified QoS framework that addresses prominent aspects of a W L A N environment. Our scheduling framework has the following features: 1) Use of virtual packets to combine the task of scheduling uplink and downlink flows of a naturally distributed C S M A / C A environment into a central scheduler that resides in an A P ; 2) Application of a GPS-based algorithm and an integrated traffic shaper in a 46 unified H C C A and E D C A queuing framework to provide guaranteed fair channel access to H C C A flows, and sharing the remaining capacity using E D C A (as illustrated in Figure 3-2). The following subsections describe the prominent features of our design, which is depicted in Figure 3-3, in more detail. 3.2.1 Centralizing the Scheduling Task: Combined Downlink/Uplink Scheduling One important feature of C A P S is its ability to centralize the scheduling task in the inherently distributed W L A N environment. In an 802.11 W L A N , the medium is shared between downstream and upstream traffic at all times. Thus, any scheduling discipline must handle packet transmissions from individual stations to the A P (i.e. upstream), and from A P to the stations (i.e. downstream). Downstream packets are available in the A P buffers and can be directly scheduled, while upstream packets reside in the stations generating these packets and cannot be scheduled directly. However, the A P can use upstream traffic specifications, available through signalling or feedback, and schedule poll messages that allow for upstream packet transmission. The key to realizing the above scheduling concept, is to represent packets from remote stations (i.e. the upstream packets) by "virtual packets" in the A P , then use a single unified scheduler to schedule virtual packets along with real packets (downstream packets). When scheduling virtual packets, the A P issues polling in the appropriate sequence to generate transmission opportunities for upstream packets. We call this mechanism hybrid scheduling because it combines upstream and downstream scheduling in one discipline. The performance of the scheduler wi l l of course depend on the specific discipline used. In fact, the framework can use any conventional single server scheduler with some modifications. We propose to use 47 GPS based fair algorithms such as Start-time Fair Queuing (SFQ) [22], Weighted Fair Queuing (WFQ) [18], or Worst case Fair Weighted Fair Queuing ( W F 2 Q ) , [21]. For brevity, we name these C A P S options as C A P S - S F Q , C A P S - W F Q and C A P S - W F 2 Q . Using a GPS based algorithm ensures fairness and bounded delay (thus controlled jitter) and increases the capacity of the system for supporting multimedia sessions. As wi l l be shown later, we wi l l modify these algorithms to suit them for the proposed framework. We wi l l analyze these algorithms performance, and identify the best choice in different situations. U P S T R E A M Requests fronj stations > Virtual Packet Generator (VPG) Virtual Packets D O W N S T R E A M packets classif ier) \ Queues w/ reservation-Actual Packets . E D C A queues Access Point Station m-r> m-» E D C A Contention Access Indicates the next service round : contention access using E D C A or an H C C A CAP generation Virtual Generate Packets C A P |generation| Service Poll [messages! Station sends packet, AP sends Ack Actual ckets A P sends Packet, receives Ack Indicates (lie next service round : contention access using EDCA or responding to Poll (transmitting in a CAP generated by the AP ) Poll Message Indication Upstream packets (classif ier: Queues w/ reservation > •j-"^ Actual Packets i y — • E D C A queues Actual Packets (response to poll) Actual Packets (contention won) Station sends packet, receives Ack Figure 3-3 Architecture and queuing model of C A P S Access Point and Station The task of generating virtual packets is performed by a module called Virtual Packet Generator (VPG) , as depicted in Figure 3-3. V P G uses control plane requests (explicit through 48 A D D T S message or implicit through interpreting SIP, [20], calls in higher layers), or traffic pattern estimation to determine the patterns of virtual packets (or flows) that must be generated. For example, for a voice call, a periodic flow of packets similar to the real traffic is generated by the V P G . The generated virtual packets are classified along with actual downstream packets and are queued and scheduled for service based on the algorithm described in the next section. Packets that are served by the scheduler are treated differently based on whether they are actual or virtual packets. Actual packets are directly transmitted in a downstream C A P , but for virtual packets an upstream C A P is generated by sending a poll message and assigning the appropriate T X O P to the station whose virtual packet is being served. 3.2.2 Scheduling, and Traffic Shaping Using the hybrid scheduling model enabled by virtual packets, we can use a central queuing and scheduling model in the A P , as depicted in Figure 3-3. The integrated scheduler/shaper module combines E D C A and H C C A operation to achieve both fairness and service guarantee. In all stations (including the A P ) , the queuing model comprises all queues for flows with reservation ( H C C A queues) plus the 4 (or 8) basic E D C A queues for each prioritized access category. After each transmission or channel busy period, the scheduler examines the queues with reservation (virtual and actual flow queues) and determines whether a queue must be served. In this step only queues whose traffic is conformant to the declared traffic shape are examined. If a queue is found eligible for H C C A service and is selected by the scheduler, it is given controlled access through a C A P generation. But i f no queue is found, the scheduler selects the 49 contention access mode and allows all actual packet queues in the system, including those with non conforming traffic, to contend for accessing the channel using E D C A rules. When contention is allowed, all queues in the stations wi l l contend for accessing the channel (including the H C C A queues). But in the A P we only allow E D C A queues plus the actual packet H C C A queues to contend; Virtual flows are excluded from contention because their corresponding actual flows in the stations are already involved in contention. The E D C A contention parameters used by contending H C C A queues are chosen locally based on the information collected during session setup. The operation of C A P S can be divided into three tasks. The first task is admission control and generating virtual packets according to the declared session information. The second task includes time-stamping, pre-shaping and queuing the arriving packets. The third and main task is selecting the packet to be served and controlling the switching between H C C A and E D C A . Task 1: Generating Virtual Packets & Admission Control This task processes requests from stations to set up flows for sessions. Admission control rules are applied to determine whether a session can be admitted by the A P . Since admission control is outside the scope of this thesis we do not discuss it here. In fact, any admission control mechanism that works with fair scheduling algorithms can be used. For an admitted uplink session, this process generates virtual packets using the available information. If service interval 5, and average packet size P, are specified, virtual flows of size P, bits are generated every 5, seconds. If 5, is not declared, we can use the declared average rate r,-, and generate virtual packets of size Pj every (r/Pj) seconds. Note that this process provides bandwidth guarantees to flows specified by their average rate requirements. To provide delay guarantees 50 in the system, the maximum burst (b,) size of each flow / must be supplied to the traffic shaper. Limit ing the burst size is an essential requirement for providing delay guarantees in any G P S -based schedulers such as weighted-fair queuing and its variants. One way of increasing the system capacity is to allow bursty transmission through T X O P s and reduce the overhead incurred by poll messages. This is achieved by C A P S by simply using larger virtual packets with proportionally longer service intervals (to keep the average rate constant). For Applications such as Voice-over-IP where periods of silence and activity exist, a consistent stream of polls to silent stations wi l l be wasteful. To address this issue the V P G must stop sending polls after detecting an empty queue (through the queue size field of the received poll response being set to zero or the more_data bit turned off)- The V P G wi l l resume generating VPs as soon as it receives a new frame for the session that arrives through E D C A . If E D C A may cause unacceptable delay the V P G can send polls at a lower rate to inquire about the activity of the voice source. Task 2: Queuing Packets Packets that are received by the C A P S scheduler are classified into three groups 1) virtual packets for uplink flows with reservations; 2) real packets belonging to downlink flows with reservations; 3) packets with no flow-association and no reservation. The first two types are called H C C A packets in this thesis and are assigned to H C C A queues. For scheduling purposes the length attribute of these packets must be adjusted to account for the different overheads incurred by each type. Virtual packets require an extra poll message at the 51 beginning of a C A P , so the transmission period for such packets must be increased accordingly. When a packet without reservation is received, its access category field is examined and the packet is stored in a corresponding E D C A queue. For the H C C A packets, the Traffic Stream ID of the (virtual or real) packet is used to determine its corresponding session queue. Before queuing, the conformance of the arriving H C C A packet to its flow's declared traffic pattern is checked and the packet is properly tagged with an eligibility time indicating when the packet is eligible for H C C A service (section 3.3 elaborates on this issue more). The packets are then time-stamped with start or finish tags according to the algorithm used in the inner scheduler (e.g. SFQ, W F Q or W F 2 Q ) . The packet start and finish times for these inner schedulers (SFQ, W F Q , and W F 2 Q ) are given by: Where Sf and F * are the start and finish timestamps for the k'h packet from the i'h flow, L * is the adjusted packet length, rt is the rate assigned to the flow, and V(t) is the virtual time function. The virtual time is calculated differently for each inner scheduler. For W F Q and W F 2 Q , V(t) represents the progress time of a GPS scheduler that is fed with the packets from these queues and is calculated as : maxCF^-'.VCO) (3.1) F* (3.2) r V(tj-i + T) = V(tj-i) + T T<tj ./ = 2,3,... (3.3) (I/O 52 where C is the server rate, T i s the time between two subsequent events j and j-1 (i.e.. packet arrival or departure) in the GPS system and Bj is the set of backlogged sessions (queues) between these events. For S F Q the virtual time is described in a much simpler way as the start tag of the packet in service at time t. A t the end of a busy period v(t)\s set to zero (or the last packet's finish time). Task 3: Scheduling and Traffic Shaping With packets queued in either H C C A or E D C A queues, the main task of C A P S is to determine which mode of operation should be used and which queue must be served at each service time. A service time occurs after a transmission is completed and the A P senses that medium has been idle for one P U S duration. At this time the algorithm described in Figure 3-4 indicates whether a C A P for a virtual or actual packet must be generated, or control should be given to E D C A . The algorithm requires maintaining a queue budget parameter gt for uplink traffic control. The queue budget parameter keeps track of the lost service time and the available T X O P time for a specific virtual flow at any given service time. Initially, gt is set to zero; it increases with each transmitted poll, and decreases with each response received. The scheduling algorithm is explained in a two-step pseudo code format depicted in Figure 3-4. The algorithm assumes that generated virtual flows are conformant to the reservations made during session setup, but actual downlink or uplink flows may not conform to their previously declared pattern. Therefore, traffic shaping and control is performed differently for actual and virtual flows. For uplink flows we only have an estimate of the flow pattern through virtual flow specifications and must wait for the actual packets to arrive before we can apply traffic 53 shaping. This is achieved through compensation as explained later. For actual downlink flows, we can apply the shaping measures directly to the flows through an eligibility flag that is explained in the next section. The scheduler only serves virtual flows with packets and actual flows with eligible H o L (Head-of-Line) packets. When no such packets are found, control is given to E D C A . Therefore the decision for switching to E D C A is made indirectly through traffic shaping and virtual packet generation processes. Step l : /* Select the queue to serve: */ { /* F ind queue J' with smallest H o L time stamp, from the set of al l virtual flow queues plus all downlink H C C A queues with eligible H o L packets.*/ A l : i = find_queue_to_serve() /* budget update for Vir tual F lows*/ i f ( i Virtual Packet queue) gi = min { bi, g, + vp_size } goto Step2; else i f ( i downlink H C C A queue) goto Step2; /* actual downlink packet to be served*/ goto Step2; /* no packet to be served */ } /*endof Step 1*/ Step2: /* Determine and apply E D C A or H C C A operation*/ { If (no queue selected in Stepl ) /* yield to E D C A * / exit; /*exit the algorithm ti l l next service round */ else /*initiate a C A P , H C C A operation*/ { If (/: Vir tual Packet queue) send a poll to queue i's destination; else i f (/: actual packet queue) send the packet in a C A P ; } W A I T for response or timeout; If ( data of size L received in response to poll from queue i ) gi = gi-L else (timeout or failure) do not update g,; 1 W A I T until next service round; goto S tep l ; Figure 3-4 Pseudo code for the scheduling task 3.2.3 Implementing the Traffic Shaper The integrated traffic shaper in the system is needed for downlink actual packets. Since virtual packets are already conformant to a predefined shape (enforced by the V P G ) , we only need to use the shaper to ensure that actual downlink flows do not exceed their promised H C C A service. This way we make sure that C A P S only assigns the promised service times to H C C A and switches to E D C A for using the remaining capacity. If shapers were not used, mal-behaving downlink flows could take up all the channel capacity and starve the E D C A traffic. 54 To enforce the shaping decisions on downlink H C C A flows, we add a new time stamp called eligibi 1 ity_time to each queued packet. Eligibi l i ty time is derived based on a token bucket shaper with envelope (rjt+bj). Upon arrival, each packet is tagged with the time when it becomes eligible (compared to system time). The inner scheduler only looks at H o L packets whose eligibility time is past the system time. However, for E D C A all H o L packets can contend. There are two options for implementing the shaper for C A P S - W F Q and C A P S - W F 2 Q . We can either implement the shaper in a separate queue, thus the packets in H C C A queues wi l l all be eligible for scheduling. However when E D C A is active, the shaping queues are also used for contention i f their corresponding H C C A queues are empty. The other option is to implement the shaper in the same queue, but use the eligibility_time tag to identify H o L packets eligible for H C C A scheduling. As expected, E D C A contention is applicable to all H o L downlink packets in this case. This method requires that we delay passing the packet arrival event to the GPS emulator for ineligible packets until they reach their eligibility time. Time stamping packets only happens after a packet becomes eligible too. For virtual time calculation the GPS emulator only uses the packet arrival event as an external trigger. For C A P S - S F Q the shaping can be done in a much simpler way because virtual time is calculated using SFQ events. The scheduling tasks, including the time stamping and update of the virtual time, only apply to packets with eligibility time reached. Thus in each service round the scheduler only acts on H o L packets that are eligible. If no such packet is found the scheduler yields to E D C A , and takes over after E D C A operation completes (or PIFS passes). SFQ is in general much easier to implement than W F Q and W F 2 Q ; the fact that the shaping for 55 C A P S - S F Q is also very simple increases the advantage of C A P S - S F Q over other C A P S options. 3.2.4 Lost Service Compensation for Uplink Flows Traffic shaping for uplink flows is mainly done through generating conformant virtual flows. However, in some cases the length of an uplink packet, sent in response to a poll , may be smaller than that of the virtual packet that generated the poll . In this case the budget g, does not go to zero after receiving the poll response and increases (up to the burst size) by the unused amount of budget. The positive and increased budget for virtual flows is an indication of lost service for uplink flows. This lost service can be compensated in two ways: 1) "Immediate Compensation" in which the entire budget is assigned in one pol led-TXOP when the next virtual packet for this queue is served, 2) "Deferred Compensation" for which the T X O P is always assigned based on the length of the virtual packet currently in service and any excess budget is used to generate additional virtual packets for the same virtual flow. Compensation occurs for the flow when these packets are later served. With immediate compensation a small virtual packet may result in a large T X O P being assigned to the station to compensate for the lost service. We call this case Long Response (or L R ) . The L R case may result in a large (but still bounded) difference between C A P S operation and the ideal GPS for a short period of time. We analyze this situation later in this chapter. With deferred compensation, since the T X O P assigned to a station as a result of serving a virtual packet is not derived from the budget parameter but from the virtual packet size, we ensure that the long response case does not happen and the subsequent service disturbance is avoided for other flows, as a result the service guarantees for other flows are still valid. 56 For deferred compensation, a virtual flow that has a positive g-t can exchange the accumulated budget with additional virtual packets that are then stored in its queue and wi l l get service at the guaranteed rate. The compensation virtual packet is generated when an indication of non-zero queue size is received either through H C C A or E D C A packets from the station. Deferred Compensation is, in effect, similar to retransmitting a virtual packet (poll message) and re-assigning the T X O P until it is properly responded to. This mechanism isolates the compensation for a specific flow from the rest of the flows and enhances service guarantees. It, however, introduces implementation overhead. Therefore, we only use this option when we do not have a good estimation of uplink flows and the bounds on service discrepancy become unacceptably large. The analysis in section 3.3 helps us to make a choice more appropriately. Note that the budget grows i f there is not enough data in the station queue, meaning that at the end of the response T X O P the station queue is empty, so the extra budget should not be re-assigned through generating a virtual packet immediately, and the scheduler must wait until it receives a message from the station with non-zero queue size report. It then creates a virtual packet with the same length (up to the available budget) and stores it at the end of the queue. 3.2.5 Adapting to Wireless Channel Physical channel impairments in a W L A N result in packet loss and consequently retransmission of packets by the M A C layer. If the quality is consistently low, the operational transmission rate for a station may be reduced as well . Channel impairment issues can be dealt with in many ways. One method is to use a lead/lag model as described in earlier works on single direction schedulers such as those described in [3], [4] or [6], These models rely on 57 detecting channel quality beforehand and lending one stations transmission time to another to avoid transmitting in a bad channel. A lead/lag counter is maintained and the stations that are leading in their service wi l l gradually give back service to the lagging stations. Such methods are not usually applicable i f good channel estimations are not available. They also cannot be applied when uplink flows are concerned, since A P may not know of stations' conditions. As a result, we rely on the retransmission feature of the M A C and adapt a simpler model of readjustment of scheduling task in order to maintain fairness. If channel monitoring is efficiently possible in W L A N s , the lead/lag method can also be used. To deal with packet loss, the M A C layer can retransmit a packet a few times until it arrives at the receiver or is dropped after n attempts (n must be small enough to avoid causing excessive delay for the entire session). If retransmission happens during a C A P it may disturb the fairness of the scheduler since a station may take longer than expected to transmit the packet. To counter this problem we have several options: the first option is to avoid immediate retransmission and wait until the next service round for this queue. This is automatically achieved for virtual packets by the deferred compensation method discussed above. For downlink packets the H o L packet's time stamps are recalculated as i f it was a new packet. This method prevents problems in this flow from disturbing other flows and ensures that service guarantees are still valid. Also, a good side effect is that immediate retransmission on the bad channel is avoided and situation may improve till the next service round. Since the retransmitted packet wi l l remain eligible for H C C A service, the retransmissions are indeed done at the expense of E D C A traffic, or in other words using the spare capacity of the channel. It is the responsibility of the admission control mechanism to reserve a portion of the channel capacity for dealing with packet retransmission. 58 Another option to maintain fairness in presence of retransmission is to move the packet that incurred problem to a special queue set up for retransmission (or to an E D C A queue) with separate reservations. This method is similar to Server Based Fair Algorithm ( S B F A ) described in [23]. This, in effect, isolates the effect of packet loss and retransmission from all other queues, and from the next packets in the same queue. The re-adjustment of packet time stamps, as described above, must be reflected in virtual time calculation of the inner scheduler as well. Implementing this policy for C A P S - S F Q is very simple as its virtual time is calculated using real events from-the scheduler; however for C A P S - W F Q and C A P S - W F 2 Q , applying the length adjustments to virtual time, though feasible, is computationally expensive because virtual time is calculated from simulating a GPS server. 3.3 Performance Guarantee Analysis Since C A P S is based on GPS and uses fair queuing algorithms, we expect it to be able to guarantee channel resources for each session. We examine this fact by proving that the difference between C A P S and ideal unidirectional GPS is bounded under different conditions and using different inner schedulers. To examine this point, we analyze the algorithm under worst case scenarios where the order of served packets in C A P S is different from the ideal order of its unidirectional inner scheduler, hence from G P S . C A P S deviates from the ideal order of a unidirectional inner scheduler in two cases: when immediate compensation is used and the response to a poll message is longer than the corresponding virtual packet (i.e. Long Repose, L R , case), and when a short response is sent in response to a longer virtual packet (i.e. Short Response, SR, case) in both immediate and 59 deferred compensation modes. If each generated virtual flow exactly matches its corresponding uplink flow (poll response), C A P S behavior is equal to its inner scheduler. In this case all the performance bounds of the inner scheduler are applicable to C A P S as well. But in the case of L R and SR, the order of packets in C A P S and its inner scheduler may be different; as a result new performance bounds may be found for C A P S . In this section we first analyze the L R case for both immediate and deferred compensation options. We show that deferred compensation is indeed the preferred choice when strict performance guarantees are needed. Consequently we analyze the SR case under deferred compensation for several inner scheduler options. 3.3.1 Long Response Case: Immediate and Deferred Compensation Using immediate compensation, a virtual flow queue may gather a large budget if its virtual packets are responded with short or no packets (null packets) for a long time. Since in immediate compensation the entire budget is assigned in one T X O P in each poll, the actual uplink frames corresponding to virtual frames may be of the maximum allowed size and larger in size than the corresponding virtual frames ( L R case); this results in an order of service in C A P S that is different from its ideal inner scheduler and G P S . For such a case, the difference in order and service progress is bounded as w i l l be shown; however, this bound may become very large for the L R case. The SR case is also applicable in the immediate compensation mode. To examine the deviation of C A P S from GPS due to the L R case, we restrict the analysis of the immediate compensation mode to a situation where virtual packets are chosen smaller than the corresponding uplink packets (LR still happens due to null or lost packets). This way the 6 0 SR case does not happen and we can derive the deviation bounds due to L R for the immediate compensation method. Finding this bound is enough for the sake of demonstrating the inefficiency of the immediate compensation method. We argue that since this bound could be very large and increases when the SR case is considered, the deferred compensation method should be used instead of the immediate compensation. To establish this argument we consider the C A P S - W F Q algorithm in this section; a similar analysis is applicable to C A P S - S F Q and C A P S - W F 2 Q , and resulting bound are very similar. The increase of the deviation bound, when the SR case is also considered for immediate compensation, is limited by the contribution of actual packets that are scheduled ahead of a V P larger than its corresponding uplink packet (SR case). The reason is that the L R case only happens for the virtual packet queues. In this case, only the actual packet queues can introduce the SR situation and add to the L R bound that is independently found from virtual packet traffic. Since the SR case results in bounded deviation, as is shown in the next section, the bounds for the immediate compensation increases with at most the bound found in the next section. This fact further confirms the argument that the deferred compensation method is preferred over the immediate compensation method. To find the difference in the service order of C A P S and G P S , consider a packet from queue k that is scheduled after a number of virtual packets j. If the virtual flows utilize their entire assigned T X O P in response to the short virtual packets, we may face a situation in which many frames from uplink flows j may be served ahead of frame k in C A P S , while in GPS k would finish service before all these packets. For example, for C A P S - W F Q , this order of scheduling is created i f several virtual frames from flows j have smaller finish times than frame k. The finish times are calculated using the virtual packet lengths. 61 With immediate compensation, responses to virtual packets may be as long as the burst size (enforced by the budget parameter), and given that the scheduler works with virtual packet lengths, we may have more virtual packets scheduled before k and after the bursty response. There is also one other situation that can add to the difference between C A P S - W F Q and GPS. This situation is the same scenario mentioned in [18] that describes the inherent difference of W F Q and G P S ; one example of this case is when a frame m arrives in an empty system and starts service under W F Q , but a short time later a frame k arrives (in another queue) and its calculated finish time is less than that of m. Since m has already started the service, k must wait until the end of service for m. Note that this situation may only happen for maximum one packet ra. Given the described situation we can combine this case with the case where several small virtual packets from queues j are scheduled ahead of k and after m, but their actual frames are served after k in GPS. Considering the above worst case scenario the following theorem can be proved: Theorem 1: i f tj, and denote the finish time for frame i in C A P S - W F Q and GPS respectively, the following inequality holds for frame k (as described above), i f immediate compensation is used and long response case is incurred: t k ' U k - ^ — Z 1 V _ R (3-4) Lmax is the maximum packet length in the system, R is the channel rate, V is the set of all virtual flow queues, and Vf" is the minimum virtual packet length of flow j. We also assume that the maximum response size to any virtual packet from flows / is bounded by the burst size b[ (according to immediate compensation rules). 62 Proof: denoting the amount of traffic served from queue i as 5„ and from all queues as S, we know that using immediate compensation the maximum amount of traffic that is served in C A P S - W F Q from each virtual queue j between the end of frame m (tm) and beginning of frame A: (i.e., tk -Lj/R) includes: 1) a burst size response to a virtual packet (bj) 2) sum of normal size responses (Wj) to the rest of virtual packets scheduled before k but after the virtual packet that resulted in the bursty response. Thus we have: Sj(tl)-Sj(tk-Lk/R)< Wj+bj (3.5) Also, denoting as X the sum of all traffic from downlink packets served in C A P S - W F Q between m and k (thus served between tm and tk -Lk/R ), and taking a sum over all virtual flows traffic we have the following (V is the set of all V P queues, except queue k): S(tk-Lk/R) -S(tm) < Jj(Wi + bj)+X (3.6) je V A n d since all packets are served at rate R, we have: X+^(W, + bj) tk-WR- tm < ^ - (3.7) A For the flows j virtual packets to have been scheduled before k by C A P S - W F Q , they must have all arrived and departed before uk in the simulated GPS system, this includes virtual packets that resulted in a bursty response as well as those that incurred normal size responses (Wj). To conceive the worst case we can assume the smallest sizes , i.e., V("m, for the virtual packets that resulted in bursty response. Therefore, knowing that frame m arrives (at tm - Lm/R) before other packets that contribute to the sum of traffic in (3.6) and knowing that k finishes after all these packets in GPS we have: 63 ^(V™ +Wj) + X + Lk uk > ^ + (tm - -f) (3.8) Assuming maximum possible length for m, the theorem follows from deducting (3.8) from (3.7). Note that in (3.4) all the values for packet lengths and burst sizes already include the adjustments for M A C operation overhead (i.e. polling and acknowledgement). Q.E.D. Expression (3.4) shows that the difference between service time in C A P S - W F Q and GPS is bounded (similar expressions can easily be found for SFQ and W F 2 Q ) . However, it can become large if the burst sizes of virtual flows are large. We can also show that the backlog of each session under C A P S is more than GPS by a bounded amount. A n d since GPS is an ideal system, we wi l l have bounded backlog for any session with reservation in C A P S . Since backlog is also the difference between arrival and service curves, it is enough for our purpose to show that the difference between served traffic in C A P S and GPS is bounded. Theorem 2: For any given time x the difference between the amount of served traffic in C A P S - W F Q with immediate compensation (denoted S/Oj)) and GPS (denoted S/O.r)) is bounded by the following: SJ(0,T) - SJ(0,T) < Z ( b j ) - £ ( V 7 i n ) + L m a x (3.9) je V je V Proof: Let's assume that a packet of size L that finishes service at time T in G P S , completes service at t+L/R in C A P S . Since Packets are served in the same order in both systems (assuming all flows are conformant) we have: SJ(0,T) = Sj(0, t+L/R) (3.10) 64 If for simplicity we rewrite Theorem 1 as t,-Ui<A, we wi l l have: (t+L/R) - A < r. Also , from (3.10) we have: Sj(0,t+UR -A) < S/0,T) = S/O, t+L/R) = Sj(0, t)+L (3.11) Since we know that the slope of Sj is at most R: Sj(0,t+L/R -A) < Sj(0,t)+L -A.R ; (3.12) deducting (3.11) from (3.12), we have Sj(0,t)-Sj(0, t)<A.R, and the theorem follows. Q . E . D . With Theorems 1 and 2 we show that C A P S with immediate compensation performs different from GPS by a bounded amount, thus confirming that it can indeed provide fair and guaranteed services, as is possible with GPS and W F Q . However, as is seen from (3.4) and (3.9), in certain situations we may encounter a large deviation from GPS operation. This is the case when the difference of the sum of allowed burst sizes and minimum V P sizes amounts to a large value. In this case the algorithm provides fairness in a longer term than is possible by its inner scheduler. For such situations, we must use deferred compensation which has higher implementation complexity but eliminates the L R case altogether and results in shorter term fairness. With deferred compensation the length of the frame that is sent in response to a poll is always equal or less than that of the virtual packet that generated the poll . This means that the L R case is in fact eliminated. In certain cases where we have virtual packet sizes that match the corresponding uplink packet size, we can show that deferred compensation can provide delay bounds equal to that of an ideal unidirectional scheduler, even if some packets are not present and polls are not responded to. For example, for C A P S - W F Q , the worst case situation 65 that has been described earlier reduces to the case where only one long packet may be served ahead of its order in W F Q if it starts service before other smaller packets arrive. This situation which is in fact similar to the worst case in W F Q system results in the following bounds: t k - u k < ± f - (3.13) The above expression directly follows from the proof from Theorem 1 with the knowledge that the service orders in C A P S strictly follows the finish time calculations based on GPS (except for the explained worst case packet m). Consequently we can revisit theorem 2 and derive the following inequality for the deferred compensation case under the same conditions: Sj(0,T)-Sj(0,z)<Lmax (3.14) Expression (3.14) is simply proved by following the proof for (3.9) and replacing A with Lmax. Deferred compensation eliminates the L R case and can considerably improve the bounds on backlog and delay in worst case situations. Therefore we argue that the implementation overhead of deferred compensation is acceptable. Given this argument we assume that deferred compensation is used with C A P S and continue the analysis of C A P S in SR case under this assumption. 3.3.2 Performance Analysis of CAPS with Deferred Compensation In this section we examine the deviation of C A P S operation from its inner scheduler in the SR case and derive the performance bounds for three inner schedulers, W F Q , W F 2 Q , and SFQ. As mentioned before, the L R case is eliminated when deferred compensation is used. It is also important to note that the algorithm corrects the projected start and finish times of the next packets in the queues after detecting a SR case, preventing the propagation of the SR case. 66 t • < S R case in C A P S - W F Q t S R case in C A P S - W F 2 Q u k * ' > j J^max . t S R case in C A P S - S F Q Figure 3-5 SR case for W F Q , W F 2 Q and SFQ S R case for C A P S - W F Q A worst case scenario for C A P S - W F Q with short response situation happens when a long virtual packet with finish time uk is scheduled for a short uplink packet with ideal finish time of uk under GPS. This means that all the packets j with GPS finish times uk<Uj<uk were supposed to finish service after k in G P S , but under C A P S - W F Q they are sent ahead of k since Uj < uk. With these assumptions we can now prove the following theorem: Theorem 3: i f tk, and uk denote the finish time for frame k in C A P S - W F Q and GPS respectively, the following inequality holds for frame k, i f deferred compensation is used: t,-u,< =^ + (Lk Lk) Q: the set of all queues R R ( 3 . 1 5 ) Proof: To picture the worst case situation, we consider a busy period in which all queues in the system are backlogged for the duration of time in which C A P S service order is different from GPS finish times. Also consider packet i to have been the last packet served before k with ur<uk (thus served in correct W F Q order). The maximum difference happens when we consider that for the duration between uk and uk all other queues always have packets for transmission. To find the service deviation we divide the packets, which are sent ahead of k in C A P S but finish after k in GPS , into two sets of W I and W2. W I includes packets j that start service in 67 GPS after i and before k and finish after uk with a maximum GPS finish time of u ; m a x . W 2 includes packets that start and finish between uk and ukv. Without loss of generality, we can divide packets in W 2 into smaller packets and create a set W 2 ' such that its packet have a GPS finish time of w™ x. Denoting the amount of traffic in W 2 as W2, the packets in W 2 ' contain aW^bits, where a<l . If we consider a hypothetical W F Q system including all the packets in W I and W2' , as well as a hypothetical packet k' with uk = w™x + e> M™ x , the behavior of this system is equivalent to C A P S until the last packet in W I and W2' . Knowing that packet k' is served last in the hypothetical system, we can use the property of W F Q and write: . W, +aW2 +Lk ' + £ + K ^ = u + L m ] L ( 3 1 6 ) * ' R 1 R R On the other hand, we can calculate the GPS finish time of k' from: uk = uk+(j3Wl+aW2 + Lk-Lk)/R, where B <1 and B.Wj is the portion of W I traffic (Wi) that is served by GPS after uk. Now, considering that packet k finishes after all W I and W 2 W +w +L packets in C A P S , we have tt=t. H—! , which can be combined with the above R equations to write: tk-uk<((JW,+W2)IR + lmmIR. (3.17) From inequality (3.17) we see that only the part of W I and W 2 traffic that is served in GPS after uk is affecting the deviation of C A P S from G P S . Therefore, as an alternative, we can divide the packets in set W I to smaller packets and create a set SI with packets j that have uk< Uj < uk+ e, and a set S2 including packets that start and finish between uk and uk. Figure 3-5 shows these sets. Notice that (3.17) indicates that only packets in S2 contribute to the 68 deviation of C A P S from G P S . The size of S2 traffic (i.e. S2) is in fact equal to pWx +W2 in (3.17) and is found as: 5 2 < £ { r , . ( ^ ^ ) } . (3.18) MQ ,j*k rk Combining (3.18) and (3.17), and knowing5 2 = pWx +W, we obtain (3.15) and prove the theorem. As an alternative, one can also find (3.15) by considering a hypothetical set S T ' that includes SI and a packet ft" with uk„ = uk + £. Since the set SI includes all packets j that have uk< Uj < uk+ e, serving packets in S I " in W F Q order, is equivalent to C A P S - W F Q serving SI and packet k. Therefore, we can use the property of W F Q , in terms of its difference with G P S , and write the following for packet k" from the set S I " : tk„-uk..<^- => tk.~ uk<^ + £ (3.19) Knowing that packet / was served before packets in set SI and packet k", and given that packet k" is of length Lk, we have tk.. = t( +(5, +Lk)lR . Combining with (3.19) we rewrite this equation as: t < 1 k_ + £ ( 3 2 0 ) R Since packet k in C A P S - W F Q is served after all packets in SI and S2 and packet i, and the service rate is R, using (3.18) we find the finish time of k as: t k = t l + S l + S 2 + L k < r , . + ^ L + i f £ ^ 1 (3.21) k ' R ' R R Deducting (3.21) from (3.20) and choosing 8 close to zero we obtain (3.15). Q . E . D . 69 The above proof shows that we only need to find the amount of traffic in S2 to calculate the deviation of C A P S from GPS. This fact is later used in this section when we consider the W F 2 Q algorithm. From expression (3.15), we see that although the deviation between GPS and C A P S - W F Q is bounded, it may become large i f rk is small or the difference of virtual and actual packet sizes is large. If more precise knowledge of the uplink flows is available and used in virtual packet generation, this bound wi l l become smaller. S R case for C A P S - W F 2 Q W F 2 Q uses the same finish times as in W F Q ; however, when scheduling packets according to their finish time, it only considers those packets that have already started service in the corresponding GPS at the scheduling moment. This mechanism positively affects the service difference bounds for C A P S in some situations. The worst case scenario for C A P S - W F 2 Q is more or less the same as in. C A P S - W F Q , except for the packets that are served during (uk, uk) in G P S . These packets, although have Uj< uk, may or may not have started service at the moment when the virtual packet k is eligible for service (Figure 3-5). If these packets have started service under G P S , the service difference bound for C A P S - W F 2 Q is exactly like C A P S - W F Q , described in (3.15). Lower bounds are possible i f we have further knowledge of the packet sizes for queues j. Similar to the proof in theorem 3, we consider a set SI whose packets j have finish times: uk< Uj < uk+ e. Also, consider a packet / as the last packet that was served in correct W F 2 Q order. After this packet is served, at tj, C A P S can be either ahead of GPS for this packet ( f , < M , ) , or be lagging behind at most Lmax/R according to [21], i.e., u, <ti<ui+ Lma/R. When C A P S is lagging at ti, the GPS start time of the other packets are going to be less than the current C A P S 70 time of tt, thus the packets are eligible. To conceive the worst case, we want to have more packets from queues j eligible for service at time Uj, thus we assume that C A P S was lagging at U and continues to be behind GPS when the last packet j is served from set SI ( C A P S finish time of the last packet of set SI is tj>uj). From theorem 3 we know that the traffic in S1 does not increase the deviation of C A P S and G P S . So we find the traffic served during (w ,^ A t the beginning of this period, when all the packets in SI have been served, the C A P S service progress time (TCAPS, defined as the time when C A P S finishes service for the last packet in SI) is assumed as lagging behind GPS finish time for these packets (i.e., TOPS =«/)» meaning that GPS has progressed further at this point (due to earlier serving an out of the GPS order for another queue) and at least one packet from each queue j is eligible. Notice that TCAPS is tj plus the time it takes to serve packets in set SI (TCAPS = U+ S//R). Similar to the proof of theorem 3, assume a hypothetical set S I ' that includes SI and a packet k' with uk' = uk + £. We know that packets in SI ' being served in W F 2 Q order, is equivalent to C A P S - W F 2 Q serving S1 and packet k. Therefore, we can use the 2 i ' property of W F Q, in terms of its difference with GPS (refer to [21]), and write the following for packet k' from the set ST: Inequality (3.22) means that the C A P S scheduler progress time is behind the GPS progress time, thus a set of packets from all queues may be served ahead of k, adding to the difference between C A P S and G P S . To worsen the. situation we assume that queues j have (infinitesimally) small packets like a fluid system; these packets are served at rate ^ . e G ^ in GPS , and rate R in C A P S , thus C A P S advances faster and may reach and lead ahead of GPS 71 (finish time of a packet in C A P S be equal or less than its GPS finish time), making packets from queues j ineligible, and allowing packet k to be serviced. We also note that just before the moment when C A P S reaches G P S , one more packet can be served. We denote the length of this packet as LL. Considering the amount of traffic that can be served in (TQAPS -TOPS) as Ss, we know that the maximum traffic that can be served between uk and uk is: Sm = m,n{Ss + Il, ( £ j £ e J M r j ) • ( - ^ - L ) } (3.23) and Ss is found as follows using inequality (3.22) and choosing e close to zero: TCAPS+^ = TCPS+-^r- => Ss< M Q ' " ( L m a x - L J (3.24) PQ,j*k jeQ,j*k The maximum value of Ss is found when the equality holds in the above expression. The packet with length L 1 must have a finish time less than u k to be counted in C A P S and GPS difference. Since this packet is sent at rate R, we can calculate its maximum allowable size as 'R multiplied by allowed time': L' = max{0 , R-{uk-uk ^—) = R - ( L K ~ L K ^—)} (3.25) jeQ ,j*k jeQ ,j*k Note that LVK may be larger than the LMAX that is chosen from queues other than the one packet k belongs to. Having found Ss and L L we can conclude that the maximum amount of traffic served ahead of k is given by Si + Sw , where Sw is found as: Sw=min{Ss+L', ^ 0 , ( ^ — ^ ) ) (3.26) jeQ ,j*k rk R R S + S I From (3.26) and (3.22) and knowing that tk -t{ =———+ — we have indeed proved the following theorem: 72 2 Theorem 4: i f t,, and «, denote the finish time for frame i in C A P S - W F Q and GPS respectively, the following inequality holds for frame k i f deferred compensation is used: tk-uk <^ + ^  (3 .27) k k R R The bound in (3 .27) is indeed less than or equal to what is expressed in (3 .15) ; thus, it may well depend on the flow parameters to determine whether using W F 2 Q is helpful to reduce the effects of imprecise virtual packet generation. In the next subsection we study S F Q and find that it may in fact be a better choice for reducing the effect of virtual/actual flow mismatch. S R case for C A P S - S F Q For C A P S - S F Q with deferred compensation, the short response case can be contained and its effects eliminated. In fact, we prove that the following theorem holds for C A P S - S F Q . Theorem 5: i f r„ and «, denote the finish time for frame i in C A P S - S F Q and GPS respectively, the following inequality holds for frame k i f deferred compensation is used: Z r m a x j T T t - u < * Q - * * ( 3 . 2 8 ) * R R rk Proof: We first explain that we can eliminate the effect of SR case on C A P S - S F Q . To see this point, notice that in SFQ packets are time-stamped with start and finish times as follows for the f th packet of flow k that arrives at time A,-*: S f =max{V(A l *),F | .* ,}; " ' >,* = Sf + L,/rk ' (3 .29) where L\ denotes the packet size, and V(.) is the system virtual time, taken to be the start tag of the packet currently being served. As a modification to SFQ, in C A P S - S F Q , i f a short response 73 occurs, the finish time of the current virtual packet should be adjusted to reflect the actual size of the uplink packet. This means that the next virtual packet backlogged in the queue wi l l have the correct start time tag. Since in S F Q packets are served in order of start time, the SR case does not change the order of service in C A P S - S F Q from the inner ideal unidirectional S F Q scheduler. As a result, we know that the difference between C A P S - S F Q and GPS is the same as the difference between S F Q and G P S . Given that in GPS a packet / that arrives at H o L is served after L/rk. A n d knowing that in worst case scenario for S F Q ([22]) such packet may be served after maximum packets from all other queues we can directly derive (3.28). Q . E . D . From the bounds found in this section we see that the delay bound of W F Q and W F 2 Q worsens in W L A N s , compared to their bounds found for an ideal unidirectional scenario. This is not the case for SFQ. As it is shown in [22], the delay bound of ideal W F Q or W F 2 Q is better than S F Q only for high bitrate flows, and in schedulers with a large number of session. For low bitrate flows, SFQ provides a much better delay bound. Given the bounds found above, this advantage of SFQ is strengthened with the increased deviation of W F Q or W F 2 Q from GPS in non-ideal cases of a W L A N . These advantages, along with the ease of implementation and adoption of retransmission policies make C A P S - S F Q the best choice for our framework. 3.4 Performance Evaluation To evaluate the service guarantee features of C A P S and measure its performance under different conditions, we conducted several experiments using an O P N E T simulator that we developed for 802 . l i e W L A N s . The applications that were selected for the experiments were the real-time applications that are most likely to use QoS services of an 802.1 le W L A N , i.e., 74 real-time voice and video conferencing. We assumed an 802.11b physical layer for our experiment. We compared the results from C A P S operation with those that are achieved by the E D C A mechanism. Some of the performance gains such as the total throughput increase of our algorithm wi l l be similar to that of other H C C A algorithms such as the TGe scheduler and the works presented in [13] and [14]. However, the TGe scheduler has already been shown (in [13] and [14]) to be very inefficient for V B R traffic and is unlikely to be deployed in real products, thus we do not re-evaluate it here. Also, a direct comparison with H C C A algorithms presented in [13] and [14] would only be possible i f implementation details of such algorithms and their associated admission control mechanisms were available. However, crucial implementation details are not presented in [13] and [14], making their implementation subject to reader's interpretation. These facts encouraged us to focus on E D C A which is the most likely contender with methods such as C A P S . It is important to note that we considered absolute worst case scenarios in the previous section in order to prove the ability of C A P S to achieve fair and guaranteed services similar to G P S . In practice, these worst case scenarios do not happen very often, and we can achieve much better average delay and bitrate provision performance using C A P S . Through our experiments we demonstrate advantages of C A P S in providing guaranteed throughput, protection from background and from same class traffic, and increase in system capacity for multimedia applications. The results in this section are valid for all three options of C A P S - W F Q , C A P S - S F Q and C A P S - W F 2 Q , unless stated otherwise. In fact, we see that in most cases the worst case scenarios of the previous section do not occur easily, and the average or near worst case behavior of all three options of C A P S are very similar. To get more insight, we conducted an experiment in which the maximum delay for one 500Kbps video flow was measured as the 75 number of H C C A flows (each 500Kbps, with 2000B packets) increased. We simulated the SR case by generating 4000B virtual packets for video packets of average size 700B. The results, depicted in Figure 3-6, show that the near worst case behavior only happens when the load reaches the limits of available capacity; otherwise the behavior is very similar for C A P S -W F Q , C A P S - W F 2 Q , and C A P S - S F Q . Number of 500Kbps uplink flow s Figure 3-6 Max Delay observed for different inner schedulers To examine and compare the delay performance of C A P S and E D C A we considered a home W L A N scenario in which an uplink video session co-existed with a heavy downlink traffic of 5Mbps. We also considered 2 (and 6) stations sending uplink background traffic of 200Kbps. The video was a CIF size H.264 foreman video with a bitrate of around 500Kbps. The cumulative distribution function of the measured delay for the video session is depicted in Figure 3-7. This figure shows that C A P S has a significantly better delay pattern than E D C A . For example i f the deadline is set to 100msec, more than 10 to 20% of the packets in E D C A wi l l miss their deadline, although the average delay of E D C A is far below this deadline. This experiment, which is based on real life scenarios, confirms that E D C A is not suitable for real time multimedia applications (for more details see Appendix B) . In our next experiment we demonstrate the ability of C A P S to guarantee a certain bitrate. For this purpose, we observe the achieved throughput of a C A P S flow with 100Kbps 76 r e s e r v a t i o n a n d o t h e r f l o w s w i t h n o r e s e r v a t i o n a n d E D C A a c c e s s . A l l t h e s t a t i o n s i n t h i s e x p e r i m e n t a r e d a t a s o u r c e s w i t h r a t e 200Kbps (200Bytes p a c k e t s , w i t h e x p o n e n t i a l i n t e r -a r r i v a l , a n d h i g h e s t E D C A p r i o r i t y ) . I n d i f f e r e n t s t e p s o f t h e e x p e r i m e n t w e i n c r e a s e d t h e n u m b e r o f s t a t i o n s t o i n c r e a s e t h e l o a d u n t i l t h e W L A N e n t e r s s a t u r a t i o n . F i g u r e 3-8 d e p i c t s t h e r e s u l t . A s i s s e e n , a t l o w l o a d s a l l s t a t i o n s c a n g e t t h e i r 200Kbps t r a f f i c t h r o u g h . A s t h e l o a d i n c r e a s e s , f l o w s w i t h o u t C A P S s e r v i c e s u f f e r f r o m c o l l i s i o n a n d p r o b l e m s o f c o n t e n t i o n a c c e s s , w h i l e t h e f l o w w i t h r e s e r v a t i o n m a i n t a i n s a t l e a s t i t s g u a r a n t e e d r a t e u n d e r C A P S ( i . e . 100Kbps i n t h i s e x a m p l e ) . 0.15 Delay (sec) 0.25 Figure 3-7 CDF of delay for an uplink Video flow (CAPS vs EDCA) 250 200 150 100 50 Throughput (Kbps) Flow using CAPS access i- - - Flows using EDCA access - i r 1 2 3 4 5 , 6 , 7 8 9 10 11 12 Load (Mbps) Figure 3-8 CAPS ability to guarantee bitrate (for all CAPS options) 77 To examine the ability of C A P S to increase W L A N capacity we evaluated the delay performance of a voice only W L A N and measured the number of G.711 voice flows that could be supported in an 11Mbps W L A N (e.g. in an 802.11b P H Y ) . The voice flows were 64Kbps (80Kbps with R T P and IP overhead) with a rate of 50 packets per second. We increased the default minimum and maximum contention window sizes for E D C A voice access category to let it accommodate more stations. Without this increase E D C A would fail very quickly. We also allowed larger virtual packets, but with longer service intervals to allow for bursty operation ( E D C A by default uses bursty operation for voice category). In this experiment no background or data traffic was present. As is shown in Figure 3-9, when C A P S is used the average and maximum delay for voice sessions remains controlled for a higher number of voice sessions, demonstrating a substantial capacity boost despite the significant overhead of poll messages. For example, if the maximum specified delay for voice sessions is restricted to 100 ms within the W L A N , E D C A can admit no more than 20 flows while C A P S can serve more than 45 voice flows ( C A P S - W F Q and C A P S - W F 2 Q performs identically, but slightly different from C A P S - S F Q ) . 0.3 0.25 o" 0.2 CD IO ~ 0.15 » 0.1 0.05 0 Avg CAPS-WFQ • A — Avg CAPS-SFQ - * Avg EDCA - * MaxCAPS-WFQ H MaxCAPS-SFQ - • Max EDCA 10 15 20 25 30 35 40 45 50 Number of Stations Figure 3-9 A Voice only W L A N , Maximum and Average delay for (CAPS vs. E D C A ) In another set of experiments we considered a 256Kbps H.264 Video traffic and observed the delay its packets incurred as we increased the background traffic of all classes (including 78 voice). Although the video was a variable bitrate media which caused SR case, we still achieved a very controlled delay performance using C A P S (all options) compared to E D C A . The results shown in Figure 3-10 confirm that the flow is protected from the background traffic. 2.5 5 7.5 10 15 Combined Background Load (Mbps) Figure 3-10 Delay of a single video session as background traffic increases In the last set of experiments we examined the per-session services of C A P S versus the aggregate services of E D C A . We considered a W L A N in which the background data traffic was fixed but the number of video flows increased in the channel. We observed the delay incurred by a low bitrate video such as a 64Kbps cell-phone size video, while some higher bitrate video flows were being added to the W L A N . As shown in Figure 3-11, C A P S is able to protect the low bitrate stream against higher bit-rate flows from the same traffic class. Meanwhile, E D C A fails to isolate this flow and unfairly allows the higher bitrate flows to degrade the quality of lower bitrate flows. This deficiency in E D C A is because of its inherent aggregate service differentiation which fails to achieve flow isolation within the same traffic class. 79 max delay (sec) 0.4 - I E D C A — K — C A P S 0.3 - 1 0.2 r4r..-_-_r • • " " x * ) ( """ ) ( * ~ " * 0 1 , , , , , 66 220 580 830 1080 1330 video load (Kbps) Figure 3-11 Protection from same class traffic: per flow vs. aggregate QoS 3.5 Concluding Remarks Providing per-session QoS in WLANs requires special measures that are addressed by our proposed CAPS framework. The proposed design enables centralized scheduling of upstream and downstream flows in the access point. It also facilitates on demand use of controlled access phases under H C C A , while allowing E D C A operation for the remaining capacity. This feature allows very efficient service guarantee for time sensitive flows even under heavy traffic conditions. In particular, applications such as real-time voice and video over W L A N will greatly benefit from this design because of the inherent similarity of their operational environment to the cases that are targeted by this design. The CAPS framework can be used in similar shared medium environments such as IEEE 802.16. Integrating the presented design with the power management features of 802.1 le is also an open issue to be further studied. The flexibility provided by the combined uplink/downlink scheduling of CAPS can also be used to employ cross-layer optimizations in the M A C using information from application and physical layers. Average de lay (sec) 10.06 0.05 0.04 E D C A - C A P S 66 220 580 830 1080 video load (Kbps) 1330 80 3.6 References [1] Wireless L A N Medium Access Control ( M A C ) and Physical Layer (PHY) specifications. A N S I / I E E E Std 802.11: 1999 (E) Part 11, ISO/IEC 8802-11, 1999. [2] I E E E Standard 802.1 le / Amendment 8, "Medium Access Control ( M A C ) Quality of Service (QoS) Enhancements", July 2005. [3] T. Nandagopal , S. L u and A . V . Bharghavan, " A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms", Wireless Networks, vol. 8 , Issue 2/3, pp. 231 - 247, March-May 2002. [4] S. L u , T. Nandagopal and V . Bharghavan, "Fair scheduling in wireless packet networks", A C M M O B I C O M ' 9 8 , October 1997. [5] S. L u , V . Bharghavan and R. Srikant, "Fair scheduling in wireless packet networks", I E E E / A C M Trans, on Networking, vol . 7 , Issue 4, pp. 473 - 489, August 1999. [6] T.S. Ng, I. Stoica and H . Zhang, "Packet Fair Queueing Algorithms For Wireless Networks With Location-Dependent Errors", Proc. of I E E E I N F O C O M '98, vol . 3, pp. 1103-1 111, March 1998. [7] A . Boukerche, and T. Dash "Performance Evaluation of a Generalized Hybrid T D M A / C D M A Protocol for Wireless Multimedia with QoS Adaptation", Computer Communication, vol . 28, pp. 1468-1480, 2005. [8] A . Boukerche, T. Dash, and C. M Pinotti "Performance Analysis of a Novel Hybrid Push-Pull Algorithm with QoS Adaptations in Wireless Networks", Performance Evaluation, vol. 60, pp. 201-221, 2005. 81 [9] Y . Yuan, D . Gu, W . Arbaugh, J. Zhang, "Achieving Fair Scheduling Over Error-Prone Channels in Multirate W L A N s " .Wireless Networks, Communications and Mobi le Computing, 2005 International Conference on, vol. 1, pp. 698-703, June 2005. [10] Z . Jiang, N . K . Shankaranarayana , "Channel Quality Dependent Scheduling for Flexible Wireless Resource Management", Global Telecommunications Conference, 2001, G L O B E C O M '01, I E E E , vol. 6, pp. 3633 - 3638, Nov. 2001. [11] Q. N i , L . Romdhani and T. Turletti , " A Survey of QoS Enhancements for I E E E 802.11 Wireless L A N " , Wiley Journal of Wireless Communication and Mobile Computing ( J W C M C ) , John Wiley and Sons Ltd., vol. 4, Issue 5, pp. 547-566, 2004. [12] Q. N i , "Performance Analysis and Enhancements for I E E E 802.1 le Wireless Networks", I E E E Networks, vol. 19, Issue 4, pp. 21 - 27, July-Aug. 2005. [13] P. Ansel, Q. N i , and T. Turletti, " A n efficient scheduling scheme for I E E E 802.1 le," WiOpt'04: Modeling and Optimization in Mobile , AdHoc and Wireless Networks, 2004. [14] A . Gri lo , M . Macedo and M . Nunes, " A Scheduling Algorithm for QoS Support in I E E E 802 . l i e Networks", I E E E Wireless Communications, vol . 10, Issue 3, pp. 36-43, June 2003. [15] R.S . Ranasinghe, L . L . H . Andrew, D . A . Hayes, D . Everitt, "Scheduling Disciplines for Multimedia W L A N s : Embedded Round Robin and Wireless Dual Queue", Communications, 2001. I C C 2001. I E E E International Conf. on , vol . 4, pp. 1243 -1248, 11-14 June 2001. 82 [16] W . Pattara-Atikom, P. Krishnamurthy, S. Banerjee, "Distributed Mechanisms For Quality O f Service In Wireless Lans", Wireless Communications, I E E E , vol . 10 , Issue: 3, pp:26 - 34, June 2003. [17] Y . Pourmohammadi Fallah and H . Alnuweiri , " A Controlled-Access Scheduling Mechanism For QoS Provisioning In I E E E 802.1 l e Wireless L A N s " , A C M International Workshop on Quality of Service & Security in Wireless and Mobile Networks Q2SWinet '05, pp. 122 - 129 , 2005. [18] A . Parekh and R. Gallager, " A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case", I E E E / A C M Trans, on Networking, vol.1, no. 3, pp. 344-357, June 93. [19] X . J . Dong, M . Ergen, P. Varaiya, A . P u r i , "Improving The Aggregate Throughput O f Access Points In I E E E 802.11 Wireless Lans", Local Computer Networks, Proceedings of 28th Annual I E E E International Conf. on, pp. 682 - 690, Oct. 2003. [20] J. Rosenberg, et.al., "SIP: Session Initiation Protocol", R F C 3261, June 2002. [21] J .C.R. Bennett, H . Zhang, " W F 2 Q : Worst-Case Fair Weighted Fair Queueing", I N F O C O M '96. Fifteenth Annual Joint Conference of the I E E E Computer Societies, Networking the Next Generation, Proceedings I E E E , vol . 1, pp. 120-128, March 1996. [22] P. Goyal, H . M . V i n , H . Cheng, "Start-Time Fair Queueing: A Scheduling Algorithm For Integrated Services Packet Switching Networks", Networking, I E E E / A C M Transactions on, vol. 5, Issue 5, pp. 690-704, Oct.. 1997. [23] P. Ramanathan and P. Agrawal, "Adapting Packet Fair Queueing Algorithms To Wireless Networks", A C M M O B I C O M ' 9 8 , October 1998. Chapter 4. Fair Scheduling in Multi-Rate WLANs 4.1 Introduction The widespread deployment of I E E E 802.11 Wireless Local Area Networks ( W L A N ) has made broadband wireless access a reality for many users [1]. As a result, a large variety of applications, such as real time multimedia applications, are being considered for these networks. Voice and Video telephony and real time T V are some examples. Supporting such applications requires guaranteed services that are not currently provided by existing 802.11 W L A N s . The new I E E E 802.1 le standard enhances the medium access controller ( M A C ) layer of the original 802.11 standard with features that facilitate guaranteed and priority service provisioning [2]. However, the new standard specifies only the features that are required for guaranteed service provisioning, and leaves the design of specific scheduling disciplines to developers. Conventional scheduling techniques developed for wired networks or single direction wireless networks are not applicable to W L A N s due to numerous reasons such as the fact that uplink and downlink traffic in W L A N s share the same channel at all times and stations may operate at different rates at different times. Our proposed solution addresses these issues and efficiently utilizes the available features of the new standard to provide fair guaranteed A version of this chapter has been submitted for publication. Yaser Pourmohammadi Fallah, Hussein Alnuweiri, Analysis of Temporal and Throughput Fair Scheduling in Multi-Rate IEEE 802.1 le WLANs , submitted to Transaction on Mobile Computing, IEEE. 8 4 services for real-time applications. We target the infrastructure mode of operation in which a central access point (AP) controls the network. Most W L A N s operate in this mode. There have been considerable efforts in devising fair scheduling algorithms for wireless environments [3]. Some notable algorithms are Wireless Fair Service (WFS) [4], Idealized Wireless Fair Queuing (IWFQ), and Channel Independent Fair Queuing (CIF-Q) [6], These algorithms are mainly designed for single direction scheduling, usually downlink from a base station, and are based on the assumption of a single fixed rate server; however, none of these assumptions are applicable to a multirate C S M A / C A (Carrier Sense Multiple Access with Coll is ion Avoidance) network like I E E E 802.11. A W L A N based on 802.11 shares the medium at all times between uplink and downlink flows, and allows different operational transmission rates for each station. This means that these existing algorithms that were mainly for cellular networks are not directly usable in an 802.1 le network and need to be modified. There also exist another set of QoS solutions specially designed for 802.11 networks. These algorithms, such as the ones specified in [11],[15], and [16] provide prioritized differentiated services to aggregate flows. These solutions are mainly based on the contention access mechanisms and provide QoS in a probabilistic manner. Other notable algorithms that consider the multirate operation, e.g., works presented in [22][23], also lack the same features that are necessary for C S M A / C A networks. Yuan in [22] proposes a temporal-fair algorithm, which is a variation of W F S , but the algorithm is suitable only for single direction scheduling in a T D D (Time Divis ion Duplex) or F D D (Frequency Division Duplex) system and does not consider the shared medium nature of W L A N s . Tinnirello in [23] studies service time fairness but does not present any scheduling scheme. 85 The works presented in [13] [14] consider the specific controlled access mechanism of the 802 . l i e and propose extensions to the simple scheduler suggested in the standard, but the presented algorithms do not provide fine scale fairness and service guarantees in a multirate environment. In fact, very little work has been dedicated to providing solutions for per-session guarantees in multirate W L A N s . Our solution focuses on using controlled access mechanisms to provide per session QoS for real-time applications while maintaining fairness in short and long term. This is mainly achieved through using the Controlled Access Phase Scheduling (CAPS) mechanism that we first presented in [19] for a single rate W L A N . In this chapter, we extend C A P S to address the fairness issues in multirate and packet loss prone environment of a W L A N . Our extended solution addresses three main characteristics of an 802.1 le W L A N that need to be taken into account when devising a QoS solution. First, the solution efficiently schedules both uplink and downlink flows to access the medium according to a Generalized Processor Sharing (GPS) based algorithm and without need for duplexing methods. Second, the scheduler efficiently distributes scheduled and contention based access periods with flexibility of changing the portion of each access type on demand. Third and most importantly the scheduler is able to provide throughput or service time (temporal) fairness and guarantee in a multirate environment. To the best of our knowledge this is the first design that addresses all these issues in a single framework for I E E E 802.1 le networks. In this chapter, we first briefly review multirate W L A N s , in particular the 802.1 l e standard. Then, we present an overview of the C A P S mechanism that is the basis of the multirate solution presented in this chapter. We examine the effects of channel impairments on the modeling of a scheduler in W L A N s and then extend the C A P S solution to address the issues of 8 6 multirate operation. We provide an analysis of different options of scheduling with C A P S , and present a performance evaluation of the final solution based on this study. 4.1.1 Scheduled Access in IEEE 802.11e MAC The M A C layer of the 802.11 standard is based on a C S M A / C A mechanism. Coll is ion avoidance in the M A C is achieved through Distributed Coordination Function (DCF) that specifies the timing rules of accessing the wireless medium. Stations running D C F have to wait a frame specific Inter Frame Space (IFS) time, before they can access the wireless medium. For data (and RTS) frames, each station has to wait an AIFS (Arbitration IFS) time plus a random backoff time, before it can access the medium. Acknowledgment (Ack) packets can be sent after a SIFS, which is shorter than A I F S . This ensures that an A c k messages can always be sent without interruption by other stations. The Access Point uses a PIFS (Point coordination function IFS), which is shorter than AIFS but longer than SIFS. This way, the access point can interrupt normal contention and take over the channel to create periods of contention free access called Controlled Access Phase (CAP) . Since PIFS is longer than SIFS, the A P can only start a C A P after the current cycle of SIFS spaced frames completes. In the 802.1 le standard, the M A C layer rules for controlling and coordinating access to the wireless medium are specified under the Hybrid Coordination Function (HCF) protocol that works on top of D C F [2]. Using the services of D C F , H C F offers two access mechanisms: E D C A (Enhanced Distributed Channel Access), which is an enhanced version of the D C F of the original standard and is used for contention based access, and H C C A ( H C F Controlled Channel Access) that specifies the polling or controlled access schemes. The 802 . l i e standard defines 8 different traffic priorities in 4 access categories and also enables the use of traffic flow IDs, which allow per flow resource reservation. Access to the medium is normally done 87 through E D C A ; but the A P can interrupt the contention period (CP), at almost any time by waiting a PIFS time, and initiate a C A P to allow H C C A access (Figure 4-1). This feature allows scheduled H C C A access to the channel; however, the standard does not mandate any specific scheduling algorithm for H C C A , and devising the scheduler is left to developers. PIFS A P (downstream) TW-S I F S SIFS Data/, S T A -v. ' (upstream) E D C A T X O P g Ack S3 Poll S IFS I F S ^ —> <— ¥ Data/Ack Polled T X O P E D C A T X O P T X O P obtained by A P E D C A T X O P < -=. > < _ _ - - -> Controller Access Phase (CAP) Figure 4-1 H C C A C A P generation The 802.1 le standard also introduces the concept of Transmission Opportunity (TXOP) . T X O P specifies the duration of time in which a station can hold the medium uninterrupted and perform multiple frame exchange cycles consequently with SIFS spacing. Under the E D C A access mechanism, different AIFS values are used for different classes of traffic. The backoff windows are also different for each priority. Shorter AIFS times and smaller contention windows give higher access priority. This prioritization enables a relative and per-class (or aggregate) QoS in the M A C . The 802.1 le standard allows for dynamically adjusting most E D C A parameters, facilitating performance enhancement using adaptive algorithms [21]. 4.1.2 MultiRate Operation of a WLAN Wireless channels are significantly more error prone than wired channels. As a result, more error recovery and robustness methods are employed in wireless environments. One method of increasing the robustness of communications over a wireless channel is to reduce the number of bits that are modulated into one symbol (e.g., from Q A M - 6 4 to Q A M - 1 6 ) . The other method is through increasing the F E C encoding ratio. These methods increase the probability of a frame being correctly received at the receiver, but consequently reduce the transmission rate. The 802.11 standard utilizes these methods and defines several modes of operation for the P H Y that result in different transmission rates over the 20Mhz available wireless channel. Through employing different modulation and F E C methods, a variety of transmission rates are available in the 802.11 W L A N s . For example, the 802.11b standard allows four rates of 1, 2, 5.5 and 11Mbps, while 802.1 la/g provides a set of eight rates (6, 9, 12, 18... 54 Mbps). The upcoming 802.1 In standard has an even larger set of available rates, ranging from 6 to almost 300 Mbps (600 Mbps for 40 M H z channels). Any of these transmission rates can be applied to individual frames and stations. As a result, an 802.11 network includes stations that may use different transmission rates. Moreover, individual packets belonging to the same station may also be sent at different rates. The decision to use a specific modulation and F E C method is made in the transmitter using the available channel condition information. Such information may be continuously collected through monitoring the SNR, interference level and other measurable parameters. It is therefore possible for a station to change the transmission rate dynamically, or just choose an appropriate rate at the time of associating with the access point. The information that is gathered by the transmitter is used to determine a P H Y mode that results in the highest 89 transmission rate with an acceptable Bit Error Rate (BER) or Packet Error Rate (PER). Usually a BER value of 10"5 is considered acceptable, and if the packet length is known, a PER of 10% is deemed acceptable. The mechanism that is used for selecting the appropriate transmission rate (PHY mode), from the set of available rates, is called "link adaptation". The standard does not mandate any specific link adaptation algorithm, and it is up to developers to devise such methods. Several algorithms have been designed for determining the process of selecting the best P H Y mode. The work in [6] describes an Auto Rate Fall-back (ARF) protocol that uses a heuristic method in which the transmitter selects the next lower rate after two failed transmissions (ACKs not received for two consecutive transmissions), and raises the rate to the next higher rate after ten successful transmissions. The method also maintains a timer to reset the rate if no transmissions happen after a rate reduction. However, such methods may not be very efficient, since they are affected by M A C layer operation and respond very slowly to channel variations. A new mechanism described in [7] provides a more intelligent method that uses channel BER information and results in a more sustainable throughput. Temporal Fairness vs. Throughput Fairness The use of different transmission rates by each station or frame has significant implications on the fairness of the services given to stations in a W L A N . Since lower rates mean longer transmission times, it is clear that a station that is experiencing lower channel quality and is using lower transmission rate takes more time to send the same amount of data. As a result, it may starve the other stations of service. This situation may be deemed unfair, if we define fairness in terms of service time. This type of fairness is also called "temporal fairness" in which the goal is to provide the stations with the same amount of service time, regardless of 90 their transmission rate. In contrast to temporal fairness, we can also define fairness in terms of the throughput that is assigned to stations in a given duration of time (usually long-term); this is called "throughput fairness". In this case, fairness is achieved i f all stations achieve the same throughput in a given duration of time. It must be noted that the issue of unfairness in W L A N s is also linked to the packet loss problem, since multirate operation does not completely eliminate the packet loss probability in W L A N s . The original 802.11 M A C was designed to be throughput fair, resulting in temporal unfairness in multirate scenarios. However, the temporal unfairness that results from lower rate stations taking up long times to transmit may be unacceptable. To tackle this issue, the concept of transmission opportunity has been introduced in 802.1 le to limit the maximum transmission time for each station or class of traffic. Using T X O P , it is possible to achieve temporal fairness in contention mode ( E D C A ) of the M A C layer. Throughput fairness is also possible in E D C A by removing T X O P limitations. For controlled or scheduled access using H C C A , the scheduling process can be designed to provide either temporal or throughput fairness based on the overall performance objective. We address this issue in the current chapter. In the next section, we wi l l briefly describe a framework for centralizing the scheduling task for a W L A N . This centralized design is extended in later sections to deal with service variations specific to multirate 802.11 wireless L A N s . 4.2 Centralized Hybrid Scheduling in WLANs Considering the distributed multiple access environment of the 802.1 le W L A N , with possible packet loss and multirate operation, we propose a detailed QoS solution that addresses 91 the following three prominent aspects of scheduling in such environments: (1) Unified Uplink/Downlink scheduling, our QoS framework uses virtual packets and combines the task of scheduling uplink and downlink flows of a naturally distributed C S M A / C A environment into a central scheduler that resides in an A P ; (2) Service guarantee and scheduling H C C A and E D C A access, our framework uses a GPS based algorithm for the centralized scheduler, as well as an integrated traffic shaper, to provide guaranteed fair channel access to H C C A flows with reservation, and share the remaining capacity using E D C A ; (3) Multirate operation, we extend the single server/scheduler model, to maintain fairness and service guarantees under multi rate operation and channel impairments such as packet loss. Since our solution presented here is an extension of the C A P S framework[19], we wi l l not repeat the details of C A P S and only provide an overview in the next subsections. A complete description of C A P S framework, initially designed for single rate W L A N s , is found in chapter 3 or [19]. 4.2.1 Combining Downlink and Uplink Scheduling In a C S M A / C A W L A N , the medium is shared between downlink and uplink traffic at all times. Therefore, the scheduling discipline must consider both uplink and downlink traffic for scheduling at all times. Moreover, it must enforce the scheduling decision. Downlink packets are available in the A P buffers and can be directly scheduled, while uplink packets reside in the stations generating these packets, and cannot be scheduled directly. However, the A P can use uplink traffic specifications, available through signalling (e.g., M A C A D D T S messages) or feedback, and schedule poll messages that allow for uplink packet transmission. The key to realizing the above scheduling concept is to represent packets from remote stations (i.e. the uplink packets) by "virtual packets" in the A P , then use a single unified scheduler to schedule virtual packets along with real packets (downlink packets). When 9 2 scheduling virtual packets, the A P issues polling in the appropriate sequence to generate transmission opportunities for uplink packets. This hybrid scheduling scheme combines uplink and downlink scheduling in one discipline, and allows the use of centralized single server schedulers. This design is depicted in Figure 4-2. Virtual packets are generated using the specified patterns of uplink traffic flow (e.g., specified in the M A C layer A D D T S message). For example, for a voice call, a periodic flow of virtual packets similar to the real traffic is generated. The virtual packets are classified along with actual downlink packets, and are queued and scheduled for service by the inner scheduler. Packets that are served by the scheduler are treated differently based on whether they are actual or virtual packets. Actual packets are directly transmitted in a downlink C A P , but for virtual packets an uplink C A P is generated by sending a poll message and assigning the appropriate T X O P to the station whose virtual packet is being served. UPSTREAM, ^ Virtu si stations Packet Generator (VPG) Virtual Packets DOWNSTREAM packets classif ier} Actual Packets Queues w/ reservation-„ E D C A queues Dh* E D C A Contention Access Indicates the next service round: contention access using EDCA or an HCCA CAP generation Virtual Packets-C A P |generation| Service 3end Poll (Station sends Data Packet) Actual lackets Send Data Packet Figure 4-2 Architecture and queuing model of a CAPS Access Point 4.2.2 Scheduling and Switching between HCCA and EDCA C A P S generates durations of H C C A access (CAP) to serve downlink and uplink flows that have made reservation with the access point, and leaves the remaining capacity to be used by 9 3 E D C A in a fair contention manner. To achieve this goal, traffic shaping on both virtual and actual downlink flows is needed. Since virtual packets are already generated according to an accepted traffic pattern, we only need to apply the traffic shaping policy to downlink H C C A flows. This is achieved by time stamping all the downlink H C C A packets with a service eligibility time. At each service round, the C A P S scheduler serves only downlink H C C A queues with eligible head of line (HoL) packet, plus any non-empty virtual flow queue (a service time occurs after a transmission is completed and the A P senses that medium has been idle for one PIFS duration). If a queue is not found for H C C A service, control is given to E D C A . To share the channel fairly in E D C A , we allow all downlink H C C A queues (including those with non-conforming traffic) plus the existing 4 (or 8) E D C A queues to contend for the channel. Virtual flow queues are not allowed to contend since their corresponding uplink flows in stations are already involved in contention. When the inner scheduler determines that H C C A service must take place, it selects one of the eligible queues based on the scheduling discipline used. We use a GPS based scheduler in order to provide fairness and service guarantee. In chapter 3, we investigated the use of several GPS based fair algorithms such as Start-time Fair Queuing (SFQ, [18]), Weighted Fair Queuing (WFQ, [16]), or Worst case Fair Weighted Fair Queuing ( W F 2 Q , [17]). These algorithms require tagging each packet with start and finish times and then serving them in the order of either start time (SFQ) or finish time (WFQ, and W F 2 Q ) . They also maintain a virtual time function that keeps track of the system progress in comparison to an ideal GPS . The packet start and finish times for these inner schedulers (SFQ, W F Q , and W F 2 Q ) are given by: S*=max(F ,* - \V(0 ) (4.1) 94 Where S? and Ft are the start and finish timestamps for the k'h packet from the ith flow, ht is the packet length, r, is the rate assigned to the flow, and V(t) is the virtual time function. The 2 virtual time is calculated differently for each inner scheduler. For W F Q and W F ' Q , V(t) represents the progress time of a GPS scheduler that is serving the same set of packets from these queues at rate C, and is calculated as: y(r;_,+r) = y(f,_,)+^ J ( y , / C ) , T<tj-tH,j = 2X.. (4.3) where T is the time between two subsequent events j and j-1 (i.e.. packet arrival or departure) in the GPS system and Bj is the set of backlogged sessions (queues) between these events. For SFQ, the virtual time is described in a much simpler way as the start tag of the packet in service at time t. At the end of a busy period, v(t) is set to the maximum of finish tag of packets served in that busy period (or zero) [18]. The multirate behavior of a W L A N and the choice of temporal or throughput fairness affect how the corresponding GPS scheduler progresses; thus, the above time stamps and virtual time calculations may need to be modified. We wi l l discuss the modifications later in this chapter. In chapter 3 (also in [19]) we investigated the use of several GPS based fair algorithms such as SFQ, W F Q , and W F 2 Q . We identified that i f precise knowledge of uplink flows is not available, the deviation of C A P S from an ideal GPS is different from that of C A P S inner scheduler and the ideal GPS . The deviation bounds are found in [19] and chapter 3, and it is shown that i f precise knowledge of uplink packet sizes is not available, the deviation of C A P S -W F Q and C A P S - W F 2 Q from an ideal GPS may be much larger than the deviation of the inner schedulers from G P S . This weakness of C A P S - W F Q and C A P S - W F 2 Q somewhat decreases 95 their suitability, in comparison to C A P S - S F Q , which is found to always behave identically to SFQ. In this chapter, we analyze the effects of multirate operation and packet loss on the performance of the inner scheduler of C A P S to identify the enhancements needed for providing either temporal or throughput fair services, and to identify the best inner scheduler choice. 4.2.3 Service Compensation for Uplink Flows Traffic shaping for uplink flows is mainly done through generating conformant virtual flows. However, in some cases the length of an uplink packet, sent in response to a poll , may be smaller than that of the virtual packet that generated the poll. To keep track of this lost service for the station, and compensate it later, the algorithm maintains a queue budget parameter g, for each uplink flow /. The budget is always limited to the maximum allowed burst size of each flow. It is incremented by the size of each transmitted poll, and decremented by the size of each response received. When the response packet is shorter than the virtual packet, the budget becomes positive. The positive budget is an indication of lost service. To compensate this lost service we use a "Deferred Compensation" method in which the excess budget is used to generate additional virtual packets for the same virtual flow (for more details and also other compensation options refer to section 3.2.4 or [19]). These additional virtual packets are then stored in the corresponding queue, and wi l l receive service at the flow's guaranteed rate. In effect, this is similar to attempting to retransmit a virtual packet (poll message). This mechanism isolates the compensation for a specific flow from the rest of the flows, and enhances service guarantees and fairness. 96 4.2.4 Adapting to Wireless Channel Quality As it was described in previous sections, we can use the C A P S framework and centralize the scheduling task in the access point of a W L A N . In conventional schedulers, the server is considered to be a fixed rate server (e.g. 100Mbps Ethernet), while for wireless environments this assumption does not hold and many sources of impairments make the server behave differently from a fixed rate server. For example, physical channel impairment in a W L A N results in packet loss or reduction in transmission rate over the wireless medium. Collisions that are inherent in C S M A networks also introduce a random but bounded medium access delay to the M A C layer H C C A operation. These impairments in M A C and P H Y operations mean that the transmission services provided by a W L A N are indeed variable, and the W L A N has to be modeled by a variable rate server with occasional interruptions in service. We examine the effect of each of these service disruptions on the modeling of W L A N as a server for the proposed fair scheduling framework. Effec t o f col l i s ion on CAP generat ion de lay In H C C A mode, a C A P can only be initiated by an access point after sensing the medium idle for a PIFS time. If the medium is busy, the A P has to wait until the current T X O P finishes and then it can take over the channel. Since all non-AP stations have to wait longer than PIFS, there is no possibility of collision in this case. If the medium was not busy when an A P needs to generate a C A P , a collision may happen i f another station's waiting time for E D C A access elapses at the same time, and it attempts to transmit over the channel. In this case the A P has to wait until the end of the collided frame, before it can take over the channel. Since a T X O P is usually longer than a frame length, the A P medium access delay is at most one T X O P length. 97 To handle the effect of H C C A access delay and maintain the fairness of the inner scheduler, certain steps must be taken. If schedulers such as W F Q and W F Q are used, it wi l l be enough to freeze the calculation of virtual time for the duration of the access delay. For algorithms like SFQ, this delay has no effect on the fairness of the algorithm because the algorithm does not change its virtual time during the delayed H C C A access anyways. Assuming this adjustment, we do not need to consider this delay for these scheduling algorithms. Effect of Packet Loss The 802.11 standard allows retransmission in the M A C layer to increase the probability of correct reception for packets that are lost due to physical layer errors. One way to model the retransmission process in H C C A mode is to consider it as a rate reduction. For example, i f a packet is retransmitted n times, we can assume that it has been served at an n times lower rate (counting M A C and P H Y overhead as well). Using this model for retransmitted packets we can simplify the problem to the rate reduction (Multirate) case. If dynamic and precise channel estimation is available, we can also utilize the lead/lag model used in [4] [6]. These models rely on detecting channel quality beforehand and lending one station's transmission time to another; however, this situation in W L A N s is dealt with using the multirate operation. Therefore we do not study these models in this chapter and focus on the abovementioned retransmission policies and multirate operation instead. Effect of Multi-Rate Operation A n 802.11 W L A N that uses multirate operation to combat channel impairments can be simply modeled as a multirate server that serves packets at a given rate for the entire duration of the packet. The multirate operation can be either static or dynamic. In static multirate, each station selects a specific rate at association time and may change the rate occasionally, but not 98 very often. In dynamic multirate scenario, the station may use a different rate for each packet. In the next sections we study the effects of multirate operation on the fairness of different C A P S scheduling options. 4.3 Fairness and Multirate operation of WLANs Multi-rate operation introduces complexities for fair scheduling algorithms that normally assume a fixed service rate for all queues. In particular, GPS based algorithms must ensure that they emulate a GPS server that is operating under the same variable rate conditions in order to correctly provide fair services. Although such a task may be computationally very expensive for some algorithms, it is in general feasible. When the transmission rate for a specific station changes, the transmission durations for its flows become different from what the scheduler may have originally anticipated. Therefore, the scheduler may have to either cut the transmission time for this station, or borrow from the service time of other stations. In effect, the scheduler is faced with two different choices of either maintaining service time fairness amongst stations (temporal fairness) or continuing to provide the promised throughput to all stations (throughput fairness). Admission control or network management entities can decide on which approach to apply, based on application requirements and network capability. The general idea is to borrow from the excess capacity of the server (if there is any) and provide the guaranteed service to a station whose transmission rate has dropped. This can be seen as providing throughput fairness by borrowing from system's excess capacity. When the extra capacity is depleted, the policy of the scheduler should change to maintaining the current service level for other stations and not penalizing them for the rate reduction in one station; effectively providing temporal fairness. 99 Assuming that the decision of providing temporal or throughput fairness is made by the admission control and management entities we examine how temporal and throughput fairness can be achieved in C A P S , using different types of GPS based inner schedulers. As a first step we investigate the centralized scheduler behavior under W L A N multirate conditions and then extend the analysis to include C A P S specific performance. 4.3.1 Fair Generalized Processor Sharing with MultiRate Operation The GPS algorithm is based on a fluid model server that provides fair (weighted) service to all flows, assuming a constant transmission rate [16]. When working in a multirate environment, we need to redefine GPS so that it remains either throughput fair or temporal fair. In a throughput fair GPS server, in each round of service all queues are served an amount of traffic proportional to their weight. This description can be applied to the following throughput fairness formulation for GPS in order to derive the amount of guaranteed throughput for each flow. Throughput fairness for a GPS server is defined as: ' > — (4.4) where W (.(T,0 is the traffic (in bits) served for queue / during time period (r,t), and % is the queue / weight (without loss of generality we assume =1 m t n e r e s t of this chapter). j all queues Given the description of throughput fair GPS , we know that i f the total amount of served traffic in (TJ) is B bits, each queue i w i l l receive a share of cpi • B . Transmitting this amount at a queue transmission rate C , takes (piBICi time, assuming constant rate for the queue in (r,0. Hence, the total time to serve all queues is: t-r= ^(<PjBIC.) j all queues 100 Taking the sum over all queues j in (4.4) and noting that the sum of all W/s is B, we derive the guaranteed rate of service g,. for queue / by dividing Wt (x,t) by {t - x) as follows: i, * ft 5—S" = *' „ = ft C « (4.5) i a// queues >- j j M q u e u e s L- ;. „ (p. where we define C * = l / ( 2^  ~ ) a s t n e average server rate. The above expression shows j all queues ^ j that the guaranteed throughput for one queue is dependent on the transmission rate of other queues. The other option of fairness, as described before, is temporal fairness. We can formulate the temporal fairness of a scheduler as follows: T.(T,t) (p - ^ - ^ - > ^ ~ (4.6) Tj(T,t) q>} in which T (.(r,0is the portion of time interval (t,t) spent serving queue /. Thus a temporally fair GPS scheduler serves each queue, in each round of service, for duration of time proportional to the service weight of the queue. Following this definition and taking a sum over all flows j in (4.6) we know that in a period ( T , 0 , the scheduler spends 7) (r, 0 > <pt -(t-r) for queue r, thus serving W;(z,t) > (pi{t-r).Ci bits for this queue. Dividing this amount by (t — x), we have the following guaranteed throughput for each queue i served by a Temporal Fair GPS scheduler: g^VC, (4.7) 101 In contrast to (4.5), the above equation shows that for a temporal fair G P S , the guaranteed throughput is not dependent on other queues transmission rates, and is directly proportional to the queue's transmission rate. Next, we examine how packet based approximations of GPS such as W F Q or WF^Q can emulate a throughput or temporal fair G P S ; where appropriate, we wi l l distinguish two types of Multirate operation, static and dynamic, in our analysis. 4.3.2 Throughput and Temporal Fair WFQ and WF2Q W F Q and W F 2 Q are packet based approximations of G P S . We achieve temporal or throughput fairness for these algorithms under multirate operation i f we modify them to approximate a throughput or temporal fair GPS . To do so, we consider a realization of these algorithms that use simulation of the corresponding GPS scheduler [16] [17]. This method uses a virtual time that keeps track of the progress of a hypothetical GPS scheduler serving the same queues. Then it tags packets with their finish time from the simulated GPS system and serves them based on the increasing order of finish times (for W F Q ) . For W F 2 Q only packets that have started service under GPS are considered for scheduling. Virtual time and packet finish and start times are described in equations (4.1) to (4.3) for a single rate scheduler. In this section we present throughput and temporal fair W F Q and W F 2 Q and analyze their implementation complications. A n analysis of the deviation of these algorithms from their corresponding GPS schedulers is given in Appendix C as a reference. 4.3.2.1 Throughput F a i r W F Q and W F 2 Q A throughput fair W F Q should use the virtual time that is derived from a throughput fair GPS system, as described in the previous section. To find out how such virtual time can be calculated, we first present the following definition of virtual time: virtual time v(t) represents the number of completed service rounds in a GPS system until the given time t. Service rounds 102 in a throughput fair system are service visits by the scheduler during which a fair proportion of traffic is served from each backlogged queue. For example, for each queue i this amount is q>.a bits, where without loss of generality we set cr to 1 bit (and consider the number of rounds as a real number). A more rigorous definition of o as an infinitesimal amount of data can be used, but is unnecessary for our discussion. Clearly, i f the number of backlogged queues increases, then the time it takes to complete a round increases as well . In fact, for a constant rate server with rate C (bits per second), the number of rounds completed during an interval of length x in which the set of backlogged sessions (5) remains unchanged is: T C • T V (t+ X ) - V(t) = ( the number of completed rounds in x ) = = ——— (4.8) isfl *-This expression is in fact what equation (4.3) describes. The corresponding start and finish times for the k'h packet that arrives at time af are also given as: Sf = max(F.k-1 ,V(af)) and Fk (4.9) <Pi Lk in which — denotes the number of rounds of service needed to serve packet k. This is regardless of the transmission rate. Static Multirate Case To consider the effects of multirate operation, we first consider the static multirate case. Here, each queue i has a fixed but different transmission rate C,. Recalling the definition of throughput fair GPS whereby tpj bits are served in each round for queue i, and knowing that this amount takes q>. IC.seconds to serve, equation (4.8) becomes: 103 V(t+T)-V(t)= T or ^L= 1 (4.10) y i dt y (Pi_ i—t /~t L—i s-t ieB ieB »-/ Note that — denotes the slope of the virtual time function. Finish and Start time tags for dt the multirate case remain as in (4.9), since they are not directly dependent on the transmission rate. Dynamic Multirate Case In a W L A N environment, it is possible that in certain cases each individual packet k belonging to the same station (queue /) be sent at a different transmission rateCf. Since the rate does not change during one packet transmission, we find that the time it takes to serve one flow i's share is tpi IC. . Taking a sum over all flows / belonging to the set of backlogged queues, equation (4.10) changes to: V(t+t)-V(t)= r or J J U 1 (4.11) Y%_ dt y <p, 2—i f->k 2—i rk ieB ieB where klh packet of queue i is being served during (t, t+T). Although the above equation looks similar to (4.10), it can be considerably harder to compute. In (4.10), updating the slope of virtual time function can be done at start and end of each queue's busy periods; while in (4.11) this has to happen at each packet arrival and departure. Computing (4.11) becomes even much harder, i f we consider the fact that in dynamic multirate cases, the rate at which a packet is sent in the future may not be known in advance. Since GPS may run ahead of W F Q and W F 2 Q by at most bits for any given packet, where is the maximum packet length in the system, it is possible that a packet assumes a 104 rate by GPS while it receives a different rate by the actual scheduler. This situation leads to incorrect calculation of time stamps (and potentially wrong scheduling order for at most one packet). In this case, all the virtual time and related tags must be recalculated in order to correctly schedule successor packets. This requires that we back track the GPS simulation until the arrival of the packet in question and recalculate all the time stamps for successor packets in the same queue, as well as the virtual time calculated at that time, and all the finish and start time tags dependent on this virtual time. Such re-adjustments require that we store the arrival time of all packets and re-simulate the behavior of the system from the arrival time of the concerned packet. This is potentially a very costly solution, especially for large systems. Nevertheless, such a task is possible, despite complexity. 4.3.2.2 Temporal F a i r W F Q and W F 2 Q Similar to the throughput fair GPS scheduler, we can model the progress of a temporal fair GPS scheduler using a virtual time function. However, in this case we change the definition of a service round (virtual time represents the number of completed service rounds in a. GPS system until the given time t) as follows: A round is a service visit by the scheduler in which the server spends a fair proportion of time serving each backlogged queue. For example, for each queue i this amount is cpfi seconds, where 8 is a very small unit of time. Assuming a static or dynamic multirate case, the length of a service round is ^(ptS, and the following ieB expresses the virtual time progress during an interval of length T in which the set of backlogged sessions (B) remains unchanged: (without loss of generality we can set 5 to 1/C seconds, where C is the server nominal rate, and obtain an equation similar to (4.8)): 105 V(t+r)-V(t)= — t — ^ ^ L (4.12) ieB ieB The above formulation for the virtual time is applicable to both dynamic and static multirate operations. To compute the corresponding start and finish times for the kth packet that arrives at time a* , we must note that such packet requires y k seconds of service in dynamic Lk / multirate case ( y for static multirate). This time divided by the amount of service (pt5given to this queue in each round wi l l give us the number of service rounds needed to serve this packet, thus: 5* =max(F,<-\V(a*)) and Ff = Sf + ^ =S*+ %j- (4.13) Clearly, the finish time is directly dependent on the transmission rate of the packet. The above equations are valid for both static and dynamic multirate operations (replacing C* with C, for static case). With dynamic rate change, re-adjustment of time stamps is necessary (as in throughput fair case) to correct the situation in which the actual transmission rate is different from what was assumed at scheduling time. 4.3.3 Throughput and Temporal Fair SFQ in a MultiRate Scenario The SFQ algorithm is inherently throughput fair. This fact was established in [22] by proving that the difference of weighted service given to any given pair of queues is bounded. This was shown by proving that the following bound exists: W^TJ) Wj(T,t) <Pt <Pj < _ L _ + - L - ( 4 _ 1 4 ) <Pi (Pj 106 Since there is no assumption on the transmission rate of individual queue's or packet's transmission rates, SFQ maintains its throughput fairness in both static and dynamic multirate scenarios. With a simple modification to the SFQ implementation, the algorithm can work properly without needing the advanced knowledge of individual packet transmission rates. The reason is that packets are served in order of start time tags, and the time stamp of head of line packets can be adjusted after the current packet finishes service, which means its transmission rate is known. This modification had already been included in C A P S - S F Q in order to eliminate the effect of virtual and actual packet length mismatch [19]. To achieve temporal fairness using SFQ, we need to modify the algorithm so that its inherent throughput fairness translates to temporal fairness. This property is achieved by modifying the definition of finish time tag as follows: The start time remains unchanged at5* = maxiF* l,V(af)), and virtual time selected as the start time of the packet in service. For brevity, we call this modified S F Q as STFQ (Start-time Temporal Fair Queuing). To prove that this modification yields a temporal fair service, we first need to define a temporal fairness measure similar to (4.14). We wi l l use the following measure for two queues / and j that are backlogged over the interval ( T , t): where Tj( T , t) is the amount of service time provided to queue /. For the static multirate case we have the following lemma. ( 4 . 1 5 ) T^TJ) Tj(T,t) ( 4 . 1 6 ) 107 Lemma 1: A S T F Q system with weights <p;and transmission rate C, for each queue has the following bound on temporal fairness measure: Htmf — 7].(T,0 T.(T,t) (pi L" + r m a x ( 4 . 1 7 ) Proof: In SFQ the weights are un-interpreted numbers and the algorithm is throughput fair with regards to these weights. For a S F Q system with weights Cj<pi, we have (from (4.14)): . Wi(T,t) Wj(T,t) Ctq>t CM Ci(Pi Cj(Pj (4.18) On the other hand, we see that using the rate Ci<pi in finish time equation (4.15) yields the required S T F Q system. We also know that during an interval (t, t) the amount of server time W(T,t) spent on each queue i is Tt (r, t) = —• . The Lemma follows from this equality. Q.E.D. For the dynamic multirate case we redefine the finish time in (4.15) as follows:. ( 4 . 1 9 ) where C* is the transmission rate for the km packet of queue i. We show next that this definition r.th results in a temporal fair service as well. Lemma 2: A S T F Q system with weight ^.and transmission rate C* for each packet k of queue / has the following bound on temporal fairness measure: Htmf — Tt{r,t) Tj(T,t) <pj < + • j m a x C m i n / i m m ,. (pt Cj <pj (4.20) 108 Proof: Consider a SFQ scheduler with weights q>t assigned to each queue i with packets of length d' - = Ly^k )• This system is clearly equivalent to the dynamic multirate STFQ. Since S F Q is throughput fair the following inequality holds for this system: Wfat) W'j(T,t) (Pj + • (Pj (4.21) where W'(T, t) is the amount of traffic served for queue / in the S F Q server. If we assume that M packets have been served for queue / in interval (? ,t), we have: w;'(r,r) = ^ ^ ] L ' n = ^ ^ . , ( A " W e also know that the amount of time spent serving the same M packets in STFQ, during the same interval (r ,t) is T^TJ) = ^M_^L" /C"), thus W'(T,t) - T ; ( r , 0 and we can rewrite (4.21) as : 7 ) ( r , 0 T,.(r,r) 9i L, L"; 9i Since L , = ( L ; / C, 1 ) , where C™"1 is the minimum transmission rate for a packet in any interval (T ,t). The lemma follows by substitutingL' m a x in (4.21). Q.E.D. 4.4 Delay Bound Analysis of CAPS-SFQ We have shown in chapter 3 (also in [19]) that in a singe rate W L A N , W F Q and W F 2 Q do not have an advantage over other fair algorithms such as S F Q that use start time scheduling. In fact, we have shown that the advantage of W F Q and W F 2 Q over SFQ, in terms of their lower deviation from GPS in some ideal situations, diminishes when we consider the short response case and W L A N operation. Given this fact, and considering the significant complexity of implementing time stamp adjustment for W F Q and W F 2 Q algorithms in a dynamic multirate 109 environment, we select the modified S F Q as our choice for the inner scheduler of C A P S . Choosing SFQ has other advantages as well; for example, the delay bound provided by S F Q for a flow with low bitrate, can be much less than that provided by W F Q and W F 2 Q [18]. Having chosen S F Q as the inner scheduler, we next derive the delay bound of C A P S - S F Q under different fairness assumptions and multirate conditions. It must be noted that the same adjustment of time stamps that corrects the time stamps in S F Q is also effective in eliminating the short response case described in Chapter 3. Therefore, the analysis in this section applies to both a standalone modified SFQ as well as C A P S - S F Q , which is the focus of this chapter. 4.4.1 Delay Bound Analysis of Throughput Fair SFQ in Static Multirate Case The delay bound found for the S F Q algorithm in [18] assumes an average service rate C for all queues. This is clearly not applicable to the multirate environment we are considering. In this section we present a series of lemmas that wi l l lead to finding the delay bound of the static multirate C A P S - S F Q , and proving that it is given by inequality (4.33) of theorem 1. The work in [18] defines the scheduling delay of a packet as the time it takes the packet to depart the system after its Expected Arrival Time (EAT). EAT* is defined as .the time that we expect a packet k from queue i to start service (reach head of line in a corresponding GPS) i f the queue has been continuously served at a reserved rate rt. Thus, the scheduling delay of concern in this section excludes the queuing delay inside a queue, since that delay can be separately found. For brevity we call the scheduling delay bound as "delay" in this section. This definition leads to the following observation: 110 Departure of packet p) - Dep) < EATk + Scheduling Delay jk-\ EAT? = max (af, EAT?-1 + {All) n where a] is the arrival time of packet k. If the queue remains backlogged after rath arrival we also have: EAT," = EAT"1 + Yk~l ^- (4.23) To calculate the delay, we must consider the packets whose service time does not finish before the expected arrival time of packet k of a queue / . To formulate this situation, assume (without loss of generality) that packet k arrives in queue / that has been backlogged with packets ra to k-1 such that packet ra arrived at an empty queue. Wi th these assumptions and assuming that the weight (pi of each flow i in SFQ is set to r„ the start time tags are found as: 6 7 = V « ) , S* = S 7 + Y k~X -L (4.24) Let V, = and V2 - Sk be the system virtual times, corresponding to the start time tags of L" packets ra and k. From (4.24) we derive v - y, = — ; combining with (4.23) we have: EATk = EAT!" +V2-Vl. (4.25) Figure 4-3 shows that the worst case departure time of packet k is after the service time of all the packets shown in the figure, plus the arrival time of packet ra. We divide these packets into the following two sets of E l and E2: E l : {all packets n \ V, < S? < V2 and F" < V2} E2: {all packets n | V, < 5," < V2 and F" > V2 } 111 Therefore, the departure time for packet k is Depkf < EAT}" + T(E\) + T(E2) + (Lkf tc)), where Ckf is the transmission rate for packet k of f low/ . , and T(E) is the time it takes to serve packets of set E. If we deduct EATkf from both sides of this expression, we wi l l have the delay for packet k (Delay = Depk - EAT) ) as: Delay < EAT™ + T'El) - EAT) + T(E2) + Ck (4.26) If we show that EATfm + T(E\) - EAT) < 0 we have proven that Lk Delay <T(E2) + ^k-C f (All) We can rewrite this condition, knowing that EAT) = EAT? + V2 - V , , as following T(E\)<V2 -V, (4.28) Figure 4-3 Delay Analysis of CAPS-SFQ Note that up to this point we have not made any assumptions on the transmission rate of each packet, so condition (4.28) must be met for both dynamic and static multirate cases in order to get the delay bound in (4.27). To prove (4.28), we present the following lemmas under different multirate assumptions. As a first step we introduce the stability condition for a throughput fair SFQ. 112 Lemma 3: Given weights n and transmission rate C, for individual queues in a throughput fair S F Q scheduler, the scheduler is stable and can provide the expected throughput of ri, i f the following condition is met for the flows: I ^ 1 (4.29) all flows i ^ i Proof: A throughput fair system, with rates r, assigned as weights for each queue, must provide r((t-r) of service to each queue in an interval ( T , t). Knowing that each queue has a transmission rate C„ we can calculate the time it takes to serve one queues traffic in ( i , t) as r,{t-1 )/Ci. Summing over all queues i, we know that the system is stable and able to provide the service, only i f this sum of times is less than the original interval (r,t ) : ^ <{t-x). The lemma follows from this inequality. Q.E.D. all flows i C' i Lemma 4: In a Static Multirate SFQ, the time it takes to serve the traffic of set E l is less than V 2 - V, , for V i and V 2 as described in (4.24); i.e., we have T(E1) < V2 - V , . Proof: Packets n (n from 1 to some x for each queue i) that belong to set E l have the start and finish tags as follows: S,1 >V,, F*<V2 (4.30) The maximum amount of traffic in E l is observed when the queues are always backlogged, L" and we have F* = 5,' ~~^2' Combining this equation with (4.30), we get the following: (4-31) 113 Dividing both sides of (4.31) by C, and then taking a sum over all flows / we get: Z ILTH S h v ' - v ' ] ( 4 - 3 2 ) a///tows i i all flows i ^ / The left side of the above inequality is indeed T(E1). Considering the result of Lemma 3 in (4.29) for the stability of a static multirate SFQ, we know that the right side of the above equation is always less than (V2-V1), thus: T { E \ ) = X Z;=1-^< E f - O ^ - V , ) ^ - ^ ) Q . E . D . all flows i ^ i all flows i ^ / Having proven the above lemmas, we now present the main result of this section for the static multirate case. Theorem 1: The delay bound for any packet k belonging to queue / with weight (assigned rate) rf and transmission rate Cf, in a stable throughput fair S F Q scheduler under static multirate assumptions, is as follows: Delay) < £ { 7 ^ + 7^ ( 4-33) jeQ,j*k Cj C f Proof: Following lemmas 3 and 4 we know that inequality (4.27) is valid. Also, since all packets in E2 contribute to the delay incurred by packet k after its E A T , we should consider the maximum length for these packets. Consequently, considering the transmission rate of each flow the theorem follows. Q . E . D . The above theorem implies that the delay bound of one queue may in fact increase with the rate reduction in other queues. This fact is later examined in this chapter through experiments. 114 4.4.2 Delay Bound Analysis of Throughput Fair SFQ in Dynamic Multirate Case To find the delay bound in dynamic multirate scenario we again need to prove that inequality (4.28) is valid, and packets belonging to set E l do not contribute to the delay bound. To do so we first define the stability condition in the following lemma; we then prove, in lemma 6, that the condition in (4.28) is valid for this case. Lemma5: Given weights r, for each queue i and transmission rate C- for each packet k of this queue in a throughput fair S F Q scheduler, the scheduler is stable and can provide the expected throughput of r; for flow i, i f the following condition is met in any interval (T , t): I I f <- 71*? <«4> all flows i neBi i ' neBi Proof: Consider an interval T-t- r, for the server to be fair and able to guarantee the promised rate (be stable), it must be able to serve a set B i of packets from queue i during T, such that the following inequality holds (the left side is the amount of received service): ^L:>rrT (4.35) neBi L" On the other hand we know that packets from set B ; take AT,. = to transmit. Taking neBi Ci L" a sum over all queues i we must have ^ A7j = < T in order to have a stable all flows i all flows i ne Bi C) server. Combining this condition with (4.35) the proof completes. Q.E .D. Lemma 6: In a Dynamic Multirate SFQ, the time it takes to serve the traffic of set E l is less than V 2 - V , for V j and V 2 , as described in (4.24); i.e., we have: T(E1) < V2 - V, . 115 Proof: Packets n (n from 1 to some x for each queue /) that belong to set E l have the start and finish tags as follows: S / > V „ F*ZV2 (4.36) The maximum amount of traffic in E l is observed when the queues are always backlogged and L" we have F* - S- + /^n=l— ^ V2. Combining with (4.36) we get the following: Yjf*V*-V> (4-37) Considering an interval of length T(E1), we know that packets served in this interval for all queues take: T(£V= I /Z3 (4-38) all flows i ^ / If the system is assumed stable, we know that inequality (4.34) from Lemma 5 is valid for the x L" x L" interval T(El); thus we have T(E\) = ^ ZI=i~ - " K n ° w m § t n a t f o r a n Y queue all flows i Cj Kj L" in set E l we have ^ * = ] ~J-<V2-Vl (according to (4.36)), the lemma is proved. Q.E.D. Theorem 2: The delay bound for any packet k belonging to queue / with weight (assigned rate) rf and transmission rate Ckf in a stable throughput fair S F Q scheduler under dynamic multirate assumptions is as follows: Delay) < £ M - } + - f (4.39) jeQ,j*k ^ j *-/ 116 where(L™ x ,C™ n ) are a pair of length and transmission rates for queue j that have the maximum transmission duration. Proof: Following lemmas 5 and 6 we know that inequality (4.27) is valid. Also, since all packets in E2 contribute to the delay incurred by packet k after its E A T , we should consider the maximum length for these packets. Consequently, considering the transmission rate of each flow the theorem follows. Q.E.D. 4.4.3 Delay Bound of Temporal-Fair SFQ in Static and Dynamic Multirate Cases To find the scheduling delay bound for the temporal fair S F Q (STFQ), we can use the same concept of Expected Arr ival Time as in the previous section. The scheduling delay bound is a measure of other flows' effect on the departure time of a given packet in a flow; whereas, E A T represents the time we expect the packet to reach the head of line in its own flow and start service. E A T calculation in (4.22) assumes that each queue is served by a fluid server at a rate which is in fact the weight assigned to the queue in throughput fair SFQ. For Temporal fair SFQ, the relation between the rate of the hypothetical fluid server and the weights assigned to each queue is not straight forward. The reason is that a temporal fair scheduler does not directly guarantee throughput; especially in dynamic multirate scenarios, the fixed weight for a queue of S T F Q does not guarantee a fixed throughput for it. However, for the static multirate scenario, the fixed we igh ty , and transmission rate C, of a queue / do indeed guarantee a throughput of r, = C, • q>, (if £ q>} =1). j all queues We can model the fluid server in the temporal fairness case as a server with rate ri = C, • <pi for the static multirate case, and a variable rate server with per packet rate of r? = C- • <pt for the dynamic multirate scenario. Employing these rates in (4.22) gives us the expected arrival 117 time in the temporal fair system. Since these values for rates are indeed the same weights as described in (4.15) and (4.19), the temporal fair system can be viewed as a throughput fair system with the above rates as the weights. Consequently, the analysis of the previous section is still applicable, which suggests that the traffic in set E l does not contribute to the scheduling delay bound. As a result, the following theorem holds. Theorem 3: In a static (or dynamic) multirate scenario, an S T F Q scheduler with transmission rate C, (or C*) for each queue / (and packet k), can guarantee the following scheduling delay bound for each queue / a n d packet k: L m a x L* Delayf < ]T {—L—} + — for static multirate case (4.40) jeQ,j*k Cj Cf Delay f < ^ { m i n } + —j- for dynamic multirate case (4.41) The stability conditions for the throughput fair SFQ (as described in Lemma 3 ) change to the following condition in temporal fair SFQ, which is already true: ^ <Pj < 1 . j all queues It is imperative to note that although the scheduling delay bounds are the same for throughput and temporal fair SFQ, the guaranteed throughput and consequently the cumulative delay bounds are quite different. This is because the total delay (cumulative delay) a packet may incur is very much dependent on the throughput it receives from the scheduler and is equal to the sum of scheduling and queuing delays. For example, a packet k that arrived in a backlogged queue with n other packets has to wait at most ^ ^ l " ) before it reaches the head of line, i f a rate of r" is guaranteed for the rc'th packet of this queue. The study of 118 queuing delay is a well developed subject and is not repeated here. It is worth to note that to derive the bounds on the queuing delay we need to assume a traffic shape such as token bucket regulated traffic for the incoming flow and consider the throughput provided to the flow by the scheduler. Consequently, well-known mechanisms such as the one described in [25] wi l l provide the queuing delay. 4.5 Performance Evaluation To evaluate the performance of C A P S - S F Q in multirate environments, we conducted several simulation experiments using an O P N E T based 802.1 le simulator that we have developed at U B C . We observed different features of throughput and temporal fair C A P S - S F Q , and examined the difference between the two fairness modes. We assumed an 802.1 l b P H Y in these experiments. In our first experiment, we observed the throughput granted to two stations (STA1 and STA2) in a static multirate case by throughput-fair C A P S - S F Q and by E D C A . We considered the transmission rate for STA1 to be 2Mbps, while other stations including S T A 2 had 11Mbps transmission rate. The number of stations increased from 5 to 55; each station had a load of 200 Kbps (packet size uniformly distributed in [250,1750]). The virtual packets generated for STA1 and S T A 2 in C A P S - S F Q had a rate of 200Kbps with 1000B packets. The results, depicted in Figure 4-4, show that throughput-fair C A P S is able to guarantee the 200Kbps throughput for both STA1 and S T A 2 , despite the lower transmission rate for S T A 1 . This is not the case for E D C A that provides a lower throughput for S T A 1 . 119 Throughput 250 200 * 150 Q. n * 100 50 a •" a • &• - •—STA1-EDCA -a—STA2-EDCA - A — S T A 1-CAPS -9—STA2-CAPS 1 2 3 4 5 6 7 8 9 10 11 Total Offered Load (Mbps) Figure 4-4 The ability of Throughput Fair CAPS-SFQ to guarantee bitrate Providing throughput fairness to a low transmission rate station may degrade the level of service received by other stations. We observe this fact in another experiment in which we measured the throughput received by stations with transmission rate 2Mbps and 11Mbps. In this experiment, C A P S - S F Q was used and the two modes of throughput and temporal fairness were considered. We increased the number of 300Kbps stations in this experiment, to see how the scheduler divides the available capacity. As it is seen from Figure 4-5, when temporal fairness is used, the high bitrate stations do not see service degradation since they are isolated from the effect of service loss for other stations. However, when throughput fairness is considered, both types of stations suffer equally. In effect, service from stations with 11Mbps is taken and given to lower rate stations. 350 _ 300 I 250 5 200 C L "§> 150 j= 100 50 0 I - X — T h . F a i r STA 2Mbps Th.Fair STA 11Mbps -A—Tm.Fa i r STA 2Mbps H I — Tm.Fair STA 11 Mbps 2.4 3.6 4.2 4.8 Load (Mbps) 5.4 6.6 Figure 4-5 Throughput Fairness vs. Temporal Fairness 120 We repeated the above experiment with 12 stations (to keep the network stable) and obtained the distribution of the packet delays for each type of station. The delay measurements were done for both cases of temporal and throughput fair C A P S - S F Q and for E D C A . The results, depicted in Figure 4-6, show that high bitrate stations have the best delay performance under temporal fair C A P S - S F Q , while by compromising service for these stations we can achieve reasonable service levels for both types of stations using throughput fairness (under the conditions of the experiment). The general idea is to allow throughput fairness for as long as it is possible to meet the minimum service requirements of all stations. When the load increases beyond this point, temporal fairness must be used to guarantee that at least stations with higher transmission rate (good channel condition) receive the promised service. Empir ica l C D F t r ,T< Q O 0.2 yd- - - - 1 - -0.1 H U M 0.2 0 0 0.05 0.15 0.3 0.35 Delayfsec) Figure 4-6 Delay distribution for C A P S (Temporal & Throughput Fair) and E D C A 121 4.6 Concluding Remarks This chapter extends the solution proposed in chapter 3, and presents a design for providing per flow service guarantees in the M A C layer of a multirate W L A N . The solution introduced in this chapter employs the CAPS-enabled centralized scheduling of uplink and downlink flows in the access point, and uses a modified S F Q based algorithm along with traffic shaping to provide guaranteed services, while providing either throughput or temporal fairness. Application such as real-time Voice and Video over W L A N wi l l greatly benefit from this design, because of the inherent similarity of their operational environment to the cases that are targeted by the proposed solution. Currently, we are examining the application of our design to other networks such as I E E E 802.16, and the integration of the presented algorithms with the power management features of the 802.1 le standard. 122 4.7 References [1] Wireless L A N Medium Access Control ( M A C ) and Physical Layer (PHY) specifications. A N S I / I E E E Std 802.11: 1999 (E) Part 11, ISO/IEC 8802-11, 1999. [2] I E E E 802 . l i e Standard - Amendment 8: Medium Access Control ( M A C ) Quality of Service Enhancements, July 2005. [3] T. Nandagopal , S. L u and V . Bharghavan, " A Unified Architecture for the Design and Evaluation of Wireless Fair Queueing Algorithms", Wireless Networks, vol . 8 , Issue 2/3, pp. 231 - 247, March-May 2002. [4] S. L u , T. Nandagopal and V . Bharghavan, "Fair scheduling in wireless packet networks", in: A C M M O B I C O M ' 9 8 (October 1997). [5] T.S. Ng, I. Stoica and H . Zhang, "Packet Fair Queueing Algorithms For Wireless Networks With Location-Dependent Errors", Proc. of I E E E I N F O C O M '98, vol. 3, pp. 1103-1111, March 1998. [6] A . Kamerman and L . Montean, "WaveLAN-I I : A High-Performance Wireless L A N far the Unlicensed Band", Be l l Labs Technical Journal, pp. 118-133 , 1997. [7] S. A . Khan, "Adjacent Channel Interference in Overlapping Access Points of O F D M W L A N s " , M . A . S c Thesis, University of British Columbia, February 2006. [8] Y . Pourmohammadi-Fallah, A . Elfeitori, H . Alnuweir i , " A Unified Scheduling Approach for Guaranteed Services over I E E E 802.1 le Wireless L A N s " , Broadband Networks, First Int. Conf. on, pp. 375 - 384, Oct 2004. [9] J. Rosenberg, et.al., "SIP: Session Initiation Protocol", R F C 3261, June 2002. [10] Q. N i , L . Romdhani, and T. Turletti. " A Survey of QoS Enhancements for I E E E 802.11 Wireless L A N " . Wiley Journal of Wireless Communication and Mobile Computing ( J W C M C ) , John Wiley and Sons Ltd. , 2004; vol . 4, Issue 5, pp. 547-566, 2004. [11] R.S. Ranasinghe, L . L . H . Andrew, D . A . Hayes, D . Everitt, "Scheduling disciplines for multimedia W L A N s : embedded round robin and wireless dual queue", Communications, 2001. I C C 2001. I E E E Int. Conf. on , vol. 4 , pp:1243 - 1248, June 2001. [12] W . Pattara-Atikom, P. Krishnamurthy, S. Banerjee, " Distributed mechanisms for quality of service in wireless L A N s " , Wireless Communications, IEEE, vol. 10 , Issue: 3 pp:26 - 34, June 2003. [13] P. Ansel, Q. N i , and T. Turletti, " A n efficient scheduling scheme for I E E E 802.1 le", WiOpt'04: Modeling and Optimization in Mobile , A d H o c and Wireless Networks, 2004. [14] A . Gri lo , M . Macedo, and M . Nunes, " A Scheduling Algorithm for QoS Support in I E E E 802.1 l e Networks", I E E E Wireless Communications, vol . 10, Issue 3, pp. 36-43, June 2003. [15] A . Banchs, M . Radimirsch, X . Perez, " Assured and expedited forwarding extensions for I E E E 802.11 wireless L A N " Quality of Service, 2002. Tenth I E E E Int. Workshop on, pp. 237 - 246, March 2002. [16] A . Parekh and R. Gallager, " A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case," I E E E / A C M Trans, on Networking, vol.1, no. 3, pp. 344-357, June 93. 124 [17] J .C.R. Bennett, H . Zhang, " W F 2 Q : Worst-Case Fair Weighted Fair Queueing", I N F O C O M '96. Fifteenth Annual Joint Conference of the I E E E Computer Societies. Networking the Next Generation. Proceedings I E E E , V o l . 1, pp. 120-128, March 1996. [18] P. Goyal, H . M . V i n , H . Cheng, "Start-Time Fair Queueing: A Scheduling Algorithm For Integrated Services Packet Switching Networks", Networking, I E E E / A C M Transactions on, vol. 5, Issue 5, pp. 690-704, Oct. 1997 [19] Y . Pourmohammadi Fallah and H . Alnuweiri , "Hybrid Poll ing and Contention Access Scheduling in I E E E 802.1 le W L A N s " , Journal of Parallel and Distributed Computing, Elsevier, V o l . 67, Issue 2, pp. 242-256, February 2006. [20] Y . Pourmohammadi Fallah, H . Alnuweiri " A controlled-access scheduling mechanism for QoS provisioning in I E E E 802.1 le wireless L A N s " A C M international workshop on Quality of service & security in wireless and mobile networks Q2SWinet '05, pp. 122 -129 , 2005. [21] Y . Pourmohammadi Fallah, H . Alnuweiri , "Enhanced Controlled-Access and Contention-Based Algorithms for I E E E 802 . l i e Wireless L A N " , Wireless Networks, Communications and Mobile Computing, 2005 International Conference on, vol. 1, pp. 4 0 9 - 4 1 4 , June 2005. [22] Y . Yuan, D . Gu, W . Arbaugh, J. Zhang, " Achieving Fair Scheduling Over Error-Prone Channels in Multirate W L A N s ",Wireless Networks, Communications and Mobile Computing, 2005 International Conference on, vol . 1, pp. 698 - 703, June 2005. 125 [23] I. Tinnirello, S. Choi , "Temporal fairness provisioning in multi-rate contention-based 802.1 l e W L A N s " , World of Wireless Mobi le and Multimedia Networks, 2005. Sixth I E E E International Symposium on a, pp. 220 - 230, June 2005. [24] Y . Pourmohammadi Fallah , H . Alnuweiri , "Performance Analysis of Controlled Access Phase Scheduling Scheme for Per-Session QoS Provisioning in I E E E 802.1 l e Wireless L A N s " , Proc. of 2006 Wireless Communications and Networking Conf., vol . 3,pp. 1414-1420, Apr i l 2006. [25] J .Y . Le Boudec, "Application of Network Calculus To Guaranteed Service Networks", I E E E Trans, on Information Theory, vol. 44, Issue 3, M a y 1998. [26] R. Agrawal, R. L . Cruz, C. Okino and R. Rajan, "Performance Bounds for Flow Control Protocols", I E E E Trans, on Networking, vol . 7, no. 3, pp 310—323, June 99. [27] H . Alnuweiri , H . Tayyar, "Analysis O f Virtual-Time Complexity In Weighted Fair Queuing", Computer Communications, vol . 28, Issue: 7, pp. 802 - 810, 2005. 126 Chapter 5. Summary and Conclusions 5.1 Summary and Concluding Remarks This research was motivated by the need for providing QoS in wireless local area networks. The goal of this thesis is to devise a scheduling framework that provides per-session QoS to multimedia applications in a W L A N such as I E E E 802 . l i e . Multimedia applications are demanding applications with stringent QoS requirement. In particular, application such as voice and video telephony, require low delay and jitter services from a W L A N . We studied several proposals that provide QoS solutions for wireless networks, and identified that these solutions lack the features required for QoS provisioning in multirate C S M A / C A based wireless networks. In particular we identified the following three features that are required from any QoS solution: 1) the ability to schedule both uplink and downlink directions at the same time; 2) efficiently dividing the use of wireless channel between contention and controlled access modes ( E D C A and H C C A ) while providing guaranteed services with low access delay to H C C A sessions 3) the ability to maintain throughput or temporal fairness in multirate environments. We developed a hybrid polling solution that possesses all these features and provides a flexible framework that allows for further extension. To gain detailed knowledge of the operation of the 802 . l i e M A C , we implemented all the features of the standard in software (C language). We imported the implementation into the O P N E T simulation tool and evaluated the features of the M A C layer under different scenarios. 127 We verified the results from our simulator with those of other published works and ensured the accuracy of the implementation. Through our study we identified that the existing throughput analyses of the E D C A under saturation mode were incomplete or flawed. We corrected the existing models and presented a generalized analysis of saturation throughput for E D C A in Chapter 2. Analytical models of E D C A under finite load conditions (non-saturated networks) are presented in other researchers' works. Following our analysis and several simulation experiments we observed that the performance of E D C A mechanism is very sensitive to its parameters and network conditions. As a result, we considered H C C A based solutions and presented C A P S . C A P S , described in Chapter 3, is a hybrid scheduling mechanism that achieves the goal of per-session guaranteed service provisioning through the use of virtual packets, GPS based scheduling, and traffic shaping. C A P S utilizes GPS based scheduling at its core. Methods such as W F Q , W F 2 Q or SFQ were examined for C A P S and it was shown that for situations where exact knowledge of uplink traffic is not available in the access point C A P S may behave differently from its core scheduler (except for C A P S - S F Q ) . Nevertheless, it was proved that C A P S is able to provide per session guaranteed services. Extending the design in Chapter 3, we examined the effects of multirate operation of a W L A N on the fairness of our scheduling algorithm in Chapter 4. We presented a detailed analysis of throughput and temporal fairness and extended the definition of GPS scheduling to introduce temporal or throughput fair G P S . We then presented temporal and throughput fair version of the packet based approximations of GPS (WFQ, W F 2 Q and SFQ). 128 Considering the issues of dynamic multirate operation in W L A N s we demonstrated that although the implementation of throughput or temporal fair C A P S - W F Q and C A P S - W F 2 Q in dynamic multirate W L A N s is possible, it is computationally very costly. Knowing from Chapter 3 that C A P S - W F Q and C A P S - W F 2 Q do not have an advantage over C A P S - S F Q in single rate W L A N s , we recommend fair C A P S - S F Q as our QoS solution in multirate W L A N s . We presented several simulation experiments in Chapter 4 to demonstrate that throughput and temporal fair C A P S - S F Q is in fact able to provide the expected services and outperforms other methods such as E D C A (which can be made throughput or temporal fair). The work presented in Chapter 3 and Chapter 4 provides a complete scheduling solution for per-session QoS provisioning in multirate 802.1 l e W L A N s . 5.2 Summary of Contributions The main contributions of this thesis can be summarized as follows: • A unified scheduling framework has been introduced that uses the concept of virtual packets (representing uplink flows) and combines the scheduling of virtual packets with actual downlink packets to achieve the goal of centralizing the task of uplink/downlink scheduling in the access point. • A new queuing/scheduling model has been developed that uses traffic shaping and GPS based scheduling in the above unified scheduling framework and achieves efficient scheduling of H C C A and E D C A based access. This model provides guaranteed access services for H C C A flows while sharing the remaining capacity in a contention based manner using E D C A . 129 • A n analysis of temporal and throughput fairness based on the concept of GPS based scheduling has been presented. This analysis was used to devise and analyze temporal and throughput fair versions of W F Q , W F 2 Q and SFQ algorithms. • A n analysis of the performance of C A P S - S F Q in multirate environments has been presented, deriving the delay bounds provided by this algorithm under dynamic and static multirate scenarios. • A generalized saturation throughput analysis of E D C A has been presented that allows for an arbitrary number of priority levels to be considered; extending and correcting the existing methods. • A complete implementation of the 802.1 l e M A C and the proposed scheduling framework have been done and tested in O P N E T simulation environment. It is important to note that providing QoS for multimedia applications is crucial to most service providers as it enables efficient deployment of revenue producing applications such as voice and video telephony and T V over W L A N s . Applications such as voice only W L A N s or real time video surveillance are examples of applications that are currently used, but at very low efficiency. We have shown in Chapter 3 that using C A P S we can significantly boost the capacity of the network while still maintaining fairness and per-session service protection required by such applications. Another possible application of C A P S is in W L A N s that inter-network with Wireless Wide Area Networks such as 3 r d generation (3G) or 4 t h generation (4G) cellular networks. It is expected that in future networks, 3G or 4 G mobile users that enter the service area of a W L A N 130 switch to the W L A N and use its higher bitrate services. Such service transfer requires that the W L A N be able to provide the same level of QoS that is provided by 3 G and 4 G networks. With popularity of live multimedia applications in cellular networks, it is imperative that W L A N s support such application too. C A P S design is perfectly suitable for such scenarios. 5.3 Future Research Directions There are a number of related issues that can be investigated as an extension to the presented research. We present some of these subjects in this section. In designing C A P S we assumed the availability of some controlled access mechanisms of the 802.1 l e W L A N s ; however, we can easily apply the design and idea of C A P S to any multiple access network that uses controlled access mechanisms such as polling. For example, wireless metropolitan area networks ( W M A N ) such as I E E E 802.16 can use the proposed solution with some modifications. Power management is one of the important issues for low power W L A N devices. Given the ability of C A P S (and H C C A ) to schedule access for individual stations in a deterministic fashion, one can extend these methods to take into account the power management issues as well. For example, a V o I P station that uses C A P S to send its uplink packets can reduce its O N durations i f it receives periodic services from the access point, while using contention based methods requires more transmission attempts, thus higher power usage. Admission Control is a topic that has received much attention in recent years. We do not consider any specific admission control mechanism in this dissertation. The standard does not mandate such methods either. A n analysis of different admission control mechanisms and their 131 performance in multirate W L A N environments can complement the work presented in this thesis. Mobi l i ty is an important aspect of most wireless networks. Mobi l i ty in W L A N s is supported in the L L C and M A C layers. Studying the effects of mobility on the performance of polling based mechanisms such as C A P S is another issue that can be beneficial in devising a complete QoS solution for mobile W L A N s or similar networks. 132 APPENDICES Appendix A. Modeling 802.11 DCF In this appendix, we present a summary of the model developed by Bianchi to derive the equations governing the backoff process behavior of D C F or a single queue in E D C A . We verified this model to be an accurate representation of the station behavior in saturation mode. Using this model the probability x of a stations attempting transmission in a slot time is found as a function of n (the network size), W (the minimum contention window size), and m, which describes the maximum backoff stage and expresses the maximum contention window size as 2m-W. In each stage of retransmission the contention window size is W,-=2'-W. As previously explained, in saturation mode all stations always have frames available for transmission, which means that for each frame transmission the stations have to run the backoff procedure. Since the backoff value is derived randomly we can model it as a random variable b(t). The value that is derived for the backoff counter at the beginning of each backoff process depends on the previous retransmission history of the system, thus b(t) is non-Markovian. To handle this problem Bianchi uses another process s(t) to model the contention window size and models the backoff procedure using a two dimensional process [s(t), b(t)]. The backoff state represented by this two dimensional stochastic process is Markovian and can be modeled as in Figure A - l with the following state transition probabilities: 1 G. Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function", IEEE Journal on Selected Areas in Communications, vol. 18, no. 3, March 2000. P(i,k\i,k+1} = 1 ke ( W , -2) i e (o,m) P{0,k\i,0J = (l-p)/Wo ke (0,Wo-l) i e (o,m) P{i,k\i-1,0} = p/Wik e (OW -1) ie (l,m) Pfm,k\m,0j = p/W,nk e (0,Wm -1) (1) 133 One important assumption in this model is that the probability p that a transmission attempt in a slot results in collision, is constant in each slot and is independent of the retransmission history of the system. Solving the markov chain model, we find the following equation that expresses the probability of transmission: r = (2) (l-2p)(W + \) + PW(l-(2p)m) In the case of D C F , using the fact that stations whose backoff counters reach zero wi l l attempt a transmission, we can find the probability of collision as a function of x: P = l - ( l - r ) " - ' (3) Note that (3) is not applicable to E D C A since probability of collision is dependent on the transmission probability of other classes as well . For D C F , one can solve (2) and (3) using numeric methods and find x and p based on the known values of CWmin , CWmax, and n. Figure A - l Markov model for the backoff procedure 134 Appendix B. Performance of H.264 Video over 802.11e WLAN The H.264 standard has recently emerged as the most prominent video compression technology. Considering this fact, most of our experiments with video files, reported in this thesis, use the traces from H.264 encoded video sequences. To further analyze the performance of H.264 video transmission over W L A N s and examine the quality of the delivered video, we have devised a simulation framework that allows simulating real-time video communications scenarios using an offline simulator. This framework, depicted in Figure B . l , consists of a core network simulator (in this case, the 802.1 le O P N E T model) and several interfaces that apply the simulation result to a decodable H.264 file containing the video sequence. H.264 Encoder PSNR, Video,... H.264 Decoder H.264 file, 1 0 • • E *TP format Pattern for R T P packets delivered to decoder H.264 file, R T P format Offline Network Simulator Dropped Late Figure B . l Offline Video Communication Simulator 135 Using the above framework we have conducted several experiments to observe the quality of an H.264 video transmitted over an 802.1 l e W L A N . We considered the physical layer errors and the effect of M A C layer operation. The W L A N that was used for this experiment was comprised of one uplink video source (CIF size H.264 encoded foreman video with 500Kbps bitrate and 700 Byte slice sizes) and a number of stations generating background traffic (30 stations, 200Kbps bitrate, with lOOOByte packets with exponential inter-arrival). We considered two cases of very low P H Y error (10"6, denoted as no error in Figure B.2) and high P H Y error of 10"5. We also repeated the case with P H Y errors for 6 background stations in order to verify that the difference between C A P S and E D C A exists even in lightly loaded networks. The cumulative distribution function of the measured delay in each case is depicted in Figure B.2. CAPS With Error and 30 Stations BKGND EDCA With Error and 30 Stations BKGND EDCA No Error and 30 Stations BKGND CAPS No Error and 30 Stations BKGND CAPS With Error and 6 Stations BKGND EDCA With Error and 6 Stations BKGND 0.1 0.15 Delay (sec) 0.2 0.25 Figure B.2 C D F of delay in a W L A N with and without P H Y errors 136 From Figure B.2 we see that introducing errors in the P H Y layer has a significant effect on E D C A operation because it incurs retransmission, effectively increasing the load of the network and the probability of collision. The P H Y error effects are very limited in C A P S . It is also seen that although the average delay for the E D C A case is acceptably low, the jitter levels are very high. This is seen from the C D F of the delay for E D C A case, where it is spread over a wide range. Using the offline network simulator, depicted in Figure B . l , we applied the effects of P H Y errors and M A C delay to the 500Kbps foreman video (from the experiment) and observed the output video quality. Some snapshots of the played back video are depicted in Figure B.3. We considered two different delay deadlines of 100msec and 250msec for the received packets, and the E D C A case with 30 stations. As we expected, C A P S performance was clearly superior to that of E D C A and the video quality is considerably better. The delay deadlines and the simulation scenario are shown on each snapshot window in Figure B.3 . 137 EDCA - 100ms with 1E-5 BER EDCA - 250ms Figure B.3 Snapshots of foreman video, transmitted in four different WLAN scenarios 138 Appendix C. Analysis of Throughput and Temporal Fair WFQ and WF2Q Service discrepancy bounds for Throughput or Temporal W F Q in multirate environments are indeed very similar to the single rate case. The bound on the lag of W F Q compared to GPS, in serving any packet, is found by Parekh 1 to be ( L m a x / C ) . This bound is found considering a scenario in which a packet m (with length Lm = L m a x ) , that has a GPS finish time of um > Uj { i:m+l .. k}, is served ahead of packets m+1 to k in W F Q ; thus packet k has a W F Q service completion time of tk < uk + , behind its GPS finish time uk. This is shown using the following facts: uk > min{a'} + {time it takes to serve m + \to k) and min{a'} > tm L L L ut > y —+t — - = t „ — -k — ^ „ "m p '•k p We can apply the same argument to the multirate case in which each packet is served at a different rate. The above expression changes in this case to: 4^ L. L L »k*TTr + t,n-7r = h - 7 r i=m+l *-m L m Note that the above inequality holds for the multirate case because the time that it takes to serve packets m+1 to k in either the throughput or temporal fair GPS and W F Q is ^ , i=m+l Cj 1 A . P a r e k h a n d R . G a l l a g e r , " A G e n e r a l i z e d P r o c e s s o r S h a r i n g A p p r o a c h to F l o w C o n t r o l i n I n t e g r a t e d S e r v i c e s N e t w o r k s : T h e S i n g l e - N o d e C a s e " , I E E E / A C M T r a n s , o n N e t w o r k i n g , v o l . 1 , n o . 3, p p . 344-357, J u n e 93. 139 and we have already defined k as the last packet served in WFQ order. Therefore, for the multirate scenario we have: L L L tt <ut + —— where we find m so that: —— > max{—} for all packets i. * c c c m in t The same service lag bound of WFQ is applicable to WF Q (proven in the article by Bennet2). The justification is that the bound in WF 2 Q is found by modeling the scheduler as a Regulated or R-WFQ and the GPS server as a Regulated GPS or R-GPS. Since regulated schedulers are only used to delay the patterns of arrivals until the GPS service eligibility time, the order and times of departure remain unchanged2. Such an adjustment is still possible and correct under either temporal or throughput fair multirate cases. The bounds given above are found based on the assumption that the uplink packet lengths are known. Also we assume that advanced knowledge of the transmission rate of each packet is available. For situations where these two assumptions do not hold, these bounds have to be re-evaluated. The reason is that in the above analysis we assumed that the order of service in the inner scheduler and CAPS are the same, which may not be true when dynamic multirate or short response cases are considered. 2 J.C.R. Bennett, H . Zhang, "WF 2 Q: Worst-Case Fair Weighted Fair Queueing", INFOCOM '96. Fifteenth Annual Joint Conference of the IEEE Computer Societies. Networking the Next Generation. Proceedings IEEE, Vol . 1, pp. 120-128, March 1996. 140 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0100418/manifest

Comment

Related Items