UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Multimedia services in DS/CDMA cellular networks : Erlang capacity and scheduling schemes Fattah, Hossam 2003

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

Item Metadata

Download

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

Full Text

Multimedia Services in DS/CDMA Cellular Networks: Erlang Capacity and Scheduling Schemes by Hossam Fattah B.Sc, University of Al-Azhar, 1995 M.A.Sc, University of Victoria, 2000 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Department of Electrical and Computer Engineering) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA November 14, 2003 © Hossam Fattah, 2003 a Supervisor: Dr. Cyril Leung ABSTRACT Broadband wireless networks are being envisioned to provide ubiquitous multimedia ser-vices to mobile users. Supporting multimedia services along with the legacy wireless ap-plications such as voice in an integrated networking framework requires a new network in-frastructure and the provision of Quality of Service (QoS) guarantees. This thesis addresses QoS issues in CDMA networks, specifically, Erlang capacity and blocking probability of a CDMA system with multimedia traffic and the design of several radio link-layer scheduling schemes employing service differentiation, and providing QoS guarantees. A new method is proposed for calculating the Erlang capacity of a DS/CDMA system that can accommodate different traffic sources with variable transmission bit rates. In this approach, each source is modelled'using a continuous-time Markov process. The evaluation is illustrated for networks with both homogeneous (one class) and heterogeneous (multiple classes) traffic sources. Imperfection in power control due to channel impairments is also considered. Such a model can capture traffic burstiness and yield more realistic results. A transmission rate scheduling scheme is proposed that can provide either absolute or relative QoS guarantees for different service classes. The proportional differentiated services model is introduced which enables the network operator to tune QoS ratios among these classes independent of the class loads. An optimization problem is also proposed that maximizes the transmission rate allocations among Mobile Stations (MSs) while ensuring the stability of packet queues and meeting the transmit power level constraint. Analysis and simulation results are used to illustrate the viability of the scheduling scheme which could be applied in the emerging Differentiated Services (DS) Internet. A load-based transmission rate (LTR) assignment scheme is introduced for non-real time data services in an integrated voice/data network. The LTR scheme takes into account session arrival processes and optimally determines the required transmission rate for each I l l session so as to minimize the overall average packet transfer delay. It is shown that the average packet transfer delay of LTR is significantly lower than that of the conventional traffic-based grouping transmission (TGT) scheme. A reservation policy combined with a number of centralized dynamic priority based packet-level schedulers is proposed for providing soft QoS guarantees for multimedia traffic while achieving a high channel utilization. In the reservation scheme, the number of packets selected for transmission from a session is changed dynamically depending on the traffic type, traffic load, Time of Expiry (TOE)/Time of Arrival (TOA) values of packets and/or packet queue length. The proposed scheme is shown to provide high channel utilization while achieving per-class QoS guarantees in a multimedia traffic environment. The scheme can be used in the DS networks. A fair queueing architecture is proposed which allows many of the proposed wireline fair queueing algorithms to be used in wireless CDMA systems. The architecture addresses the issue of time scheduling using a new Generalized Processor Sharing (GPS) approach that utilizes the available power resource efficiently by assigning variable power indices to the mobile stations. This approach supports multirate transmission techniques such as variable spreading gain or multicode. Finally, a new scheduling algorithm "Wireless Deficit Round Robin (WDRR)" is pro-posed. WDRR is a round robin scheduler that has low implementation complexity and provides a low delay bound, tight fairness index, and almost perfect isolation property. The algorithm provides short-term fairness among sessions that perceive a clean channel, long-term fairness among all sessions, ability to meet specified throughput objectives for all sessions, and graceful service degradation among sessions that received excess service. Both analysis and simulation are used to verify the WDRR properties. Table of Contents iv Table of Contents Abstract ii Table of Contents iv List of Tables ix List of Figures xi List of Abbreviations xvi Acknowledgement xx Dedication xxi 1 Introduction 1 1.1 Broadband Wireless Communications Technology 1 1.2 Motivation and Thesis Contributions 3 1.3 Thesis Outline 7 2 Scheduling Multimedia Traffic 9 2.1 Introduction 9 2.2 Wireless Network Scheduler Challenges 11 2.3 Scheduler Components and Properties 12 2.4 Scheduler Classification 14 2.5 Generalized Processor Sharing (GPS) Based Scheduling 15 2.6 Scheduling Algorithms for Wireless TDMA Networks 16 Table of Contents v 2.6.1 Network Model 16 2.6.2 Channel State Dependent Packet Scheduling (CSDPS) 17 2.6.3 Idealized Wireless Fair Queueing (IWFQ) 17 2.6.4 Channel-Condition Independent Fair Queuing (CIF-Q) 18 2.6.5 Server Based Fairness Approach (SBFA) 18 2.6.6 Wireless Fair Service (WFS) 19 2.6.7 Summary 19 2.7 Scheduling in CDMA Networks 20 2.7.1 Packet-by-packet GPS 21 2.7.2 Scheduled CDMA . 22 2.7.3 Dynamic Resource Scheduling (DRS) 22 2.7.4 Wireless Multimedia Access Control Protocol with BER Schedul-ing (WISPER) 23 2.8 Summary 25 3 Erlang Capacity with Multirate Traffic Sources 26 3.1 Introduction 26 3.2 System Model and Admission Criterion 27 3.3 Power Index Model 30 3.4 Imperfect Power Control 36 3.5 Numerical Results and Discussion 37 3.6 Summary 40 4 A Transmission Rate Scheduling Scheme 49 4.1 Introduction 49 4.2 System Model . 51 4.3 Transmission Rate Scheduling Scheme 52 4.3.1 Power Control 52 4.3.2 -M/D/l Queueing Model 54 Table of Contents vi 4.3.3 QoS Performance Measures 55 4.4 Session Admission Control Rule 55 4.4.1 Absolute QoS Admission Control Rule 55 4.4.2 Relative QoS Admission Control Rule 56 4.5 Maximizing Transmission Rates 56 4.6 Rate Guarantee and Credits 57 4.7 Simulation Results 59 4.8 Summary 64 5 A Load-based Transmission Rate Assignment Scheme 68 5.1 Introduction 68 5.2 System Model 69 5.3 Transmission Rate Optimization 69 5.4 Numerical Results 71 5.5 Summary 72 6 A Power Reservation Scheduling Scheme 76 6.1 Introduction 76 6.1.1 Desirable Scheduling Properties 77 6.2 The Proposed MAC Protocol 78 6.2.1 Proposed Algorithm 80 6.2.1.1 Call Admission Control (CAC) 81 6.2.1.2 Packet Scheduling 81 6.2.1.3 Parameters and Notation 83 6.3 Analysis of the Scheduling Scheme 88 6.4 Simulation Environment 91 6.5 Simulation Results and Discussion 92 6.5.1 Error-free Channels 92 6.5.2 Error-prone Channels . , 96 Table of Contents vii 6.5.3 Summary of Results 99 6.6 Summary 101 7 A Distributed Fair Queueing Architecture 107 7.1 Introduction 1° 7 7.2 Network Model 108 7.2.1 The Mobile Station 108 7.2.2 The Base Station 109 7.2.3 Power Control 110 7.3 The GPS Model HI 7.3.1 GPS Model for Good Channels Ill 7.3.2 GPS Model for Poor Channels . . . 113 7.4 Multirate Support . 115 7.5 The Architecture 116 7.6 Simulation Results 117 7.7 Summary 120 8 An Improved Round Robin Packet Scheduler 121 8.1 Introduction 121 8.2 Network Model 122 8.3 The WDRR Algorithm 123 8.3.1 The Error-free Service Model 123 8.3.2 WDRR in Error-prone Channels - Lead, Lag, and Compensation . 127 8.3.3 Support for Both Delay-sensitive and Error-sensitive Channels . .129 8.4 Analysis 129 8.5 Simulation Results 134 8.6 Summary 142 Table of Contents viii 9 Conclusions 145 9.1 Future Work 148 Bibliography 150 Appendix A Calculation of the Moments of the Power Index Random Variable 158 Appendix B WDRR Algorithm Pseudo Code 160 List of Tables be List of Tables Table 2.1 QoS requirements for different applications 10 Table 2.2 Comparison of scheduler properties 17 Table 2.3 Comparison of wireless scheduler components 20 Table 2.4 Comparison of wireless scheduler properties 20 Table 3.1 The state space of the superimposed MMPIP for three traffic sources, each with a three-state MMPIP. 32 Table 3.2 The state space of the A-MMPIP and the corresponding states in the U-MMPIP. 34 Table 3.3 Parameter values for an integrated voice/video/data cellular DS/CDMA network [1,2] 39 Table 4.1 Characteristics of the three service classes 60 Table 4.2 (a) target QoS values, (b) required transmission bit rates, and (c) simulation QoS results for the three service classes in Table 4.1 60 Table 6.1 Simulation parameter values for the reservation scheme 93 Table 7.1 Simulation parameter values 118 Table 7.2 Performance measure values for (a) good channels (b) poor channels. 119 Table 8.1 WDRR performance measure values for example 8.1 (fixed-size pack-ets) 136 Table 8.2 WDRR performance measure values for example 8.1 (variable-size packets) 136 List of Tables x Table 8.3 WDRR performance measure values for example 8.5: Error-sensitive sessions 141 Table 8.4 WDRR performance measure values for example 8.5: Delay-sensitive sessions 141 List of Figures xi List of Figures Figure 2.1 Typical wireless scheduler 10 Figure 2.2 Scheduled CDMA scheduler 23 Figure 2.3 Dynamic resource scheduler 24 Figure 2.4 WISPER uplink/downlink frame format 24 Figure 3.1 Markov modulated power index process (MMPIP) representation of traffic source i 31 Figure 3.2 Blocking probability versus offered voice traffic under perfect power control when / = 0 41 Figure 3.3 Blocking probability versus offered voice traffic under perfect power control when / = 0.55 41 Figure 3.4 Blocking probability versus offered video traffic under perfect power control when / — 0 42 Figure 3.5 Blocking probability versus offered video traffic under perfect power control when / = 0.55 42 Figure 3.6 Blocking probability versus offered data traffic under perfect power control when / = 0 43 Figure 3.7 Blocking probability versus offered data traffic under perfect power control when / = 0.55 43 Figure 3.8 Blocking probability versus offered traffic under perfect power con-trol when / = 0 44 Figure 3.9 Blocking probability versus offered traffic under perfect power con-trol when / = 0.55. . 44 List of Figures xii Figure 3.10 Blocking probability versus offered voice traffic under imperfect power control when / = 0 45 Figure 3.11 Blocking probability versus offered voice traffic under imperfect power control when / = 0.55 45 Figure 3.12 Blocking probability versus offered video traffic under imperfect power control when / = 0 46 Figure 3.13 Blocking probability versus offered video traffic under imperfect power control when / = 0.55 46 Figure 3.14 Blocking probability versus offered data traffic under imperfect power control when / = 0 47 Figure 3.15 Blocking probability versus offered data traffic under imperfect power control when / — 0.55 47 Figure 3.16 Blocking probability versus offered traffic under imperfect power control when / = 0 48 Figure 3.17 Blocking Probability versus offered traffic under imperfect power control when / = 0.55 48 Figure 4.1 The proposed transmission rate scheduling scheme 52 Figure 4.2 Average packet delay, average packet delay ratio, and channel uti-lization for three service classes 61 Figure 4.3 Pseudo code algorithm for solving problem (PI ) with the additional relative QoS measure constraint 62 Figure 4.4 Packet loss rates due to excessive waiting time for the three service classes versus the fraction of class-1 traffic 63 Figure 4.5 Packet loss rate ratio due to excessive waiting time and channel utilization for the three service classes versus the fraction of class-1 traffic. . 64 Figure 4.6 Average packet delay for the three service classes versus the fraction of class-1 traffic 65 List of Figures xiii Figure 4.7 Power index ratio and channel utilization for the three service classes versus the fraction of class-1 traffic 66 Figure 4.8 Graceful power index degradation when v = 1 67 Figure 4.9 Graceful power index degradation when v = 0.5 67 Figure 5.1 System model with each data session represented by an M/D/l queue 70 Figure 5.2 Overall average packet transfer delay versus arrival rate ratio for the TGT and LTR schemes with = OAR^RGT^ 72 Figure 5.3 Overall average packet transfer delay versus arrival rate ratio for the RGT and LTR schemes with \ A = 0.1 Rd RGT.2 73 Figure 5.4 Overall average packet transfer delay versus arrival rate ratio for the TGT and LTR schemes with XA = Q-1Rd,RGT,2 74 Figure 5.5 Overall average packet transfer delay versus arrival rate ratio for the RGT and LTR schemes with A^  = 0.7Rd,RGT,2 75 Figure 6.1 Uplink/downlink frame format 79 Figure 6.2 Pseudo code for the call admission control algorithm 82 Figure 6.3 Variation of PLR, PTD, and U in a single traffic (CBR sessions) environment 94 Figure 6.4 Variation of PLR, PTD, and U in a single traffic (VBR sessions) environment. . 95 Figure 6.5 Variation of PLR, PTD, and U in a single traffic (ABR sessions) environment 96 Figure 6.6 EDF: Variation of PLR, PTD, and U in a multitraffic environment (CBR and VBR sessions) for NVBR = 2 when gcBR = 0.3, gvBR = 0.6 and gCBR = 0.4, g V B R = 0.5 97 List of Figures xiv Figure 6.7 FCFS: Variation of PLR, PTD, and U in a multitraffic environment (CBR and VBR sessions) for NVBR = 2 when gcBR = 0.3, gvBR = 0.6 and gcBR = 0.4, g V B R = 0.5 98 Figure 6.8 RR: Variation of PLR, PTD, and U in a multitraffic environment (CBR and VBR sessions) for NVBR — 2 when gcBR = 0-3,gvBR = 0.6 and gCBR = 0.4, g V B R = 0.5 99 Figure 6.9 EDF: Variation of PLR, PTD, and U in a multitraffic environment (CBR, VBR, and ABR) for N V B R = 1 and N A B R = 1 when g C B R = 0.35, gvBR = 0.3, and g A B R = 0.25 100 Figure 6.10 FCFS: Variation of PLR, PTD, and U in a multitraffic environment (CBR, VBR, and ABR) for N V B R = 1 and N A B R = 1 when g C B R = 0.35, gvBR = 0.3, andgABR = 0.25 101 Figure 6.11 RR: Variation of PLR, PTD, and U in a multitraffic environment (CBR, VBR, and ABR) for NVBR = 1 and N A B R = 1 when g C B R = 0.35, gVBR = 0.3, andgABR = 0.25 102 Figure 6.12 Variation of P L R , PTD, and U in a multitraffic (CBR and ABR sessions) environment for N A B R = 10 when gcBR = gABR = 0 103 Figure 6.13 Variation of PLR, PTD, and U in a multitraffic (CBR and VBR sessions) environment for NVBR = 2 when gcBR = gvBR = 0 104 Figure 6.14 Variation of average burst error length with PB and v (mobile velocity). 105 Figure 6.15 EDF: Effect of channel error correlations on PLR, PTD, and U for CBR sessions (PE = 0.01) 105 Figure 6.16 EDF: Effect of channel error correlations on PLR, PTD, and U for multitraffic environment (CBR (solid lines) and VBR sessions (dashed lines)) for NVBR = 2 when gcBR — 0.3, gvBR = 0.6 and PB = 0.01 106 Figure 7.1 Fair queueing architecture for uplink of a CDMA network 109 Figure 7.2 Graceful service degradation when (a) a = 0.5 and (b) a = 1.0. . . . 120 List of Figures xv Figure 8.1 Quantum allocation 125 Figure 8.2 Deficits shown as slots of length Lmax each 126 Figure 8.3 Session transmission order for (a) DRR (Fig. 8.1) and (b) WDRR (Fig. 8.2). : 126 Figure 8.4 Quantum allocation flow chart 130 Figure 8.5 Transmission flow chart 131 Figure 8.6 Average delay versus the system quantum with fixed-size packets. . 137 Figure 8.7 Average delay versus the system quantum with variable-size packets. 137 Figure 8.8 Average delay versus system quantum with fixed-size packets for (a) session 2 and (b) session 3. 138 Figure 8.9 Average delay versus system quantum with variable-size packets for (a) session 2 and (b) session 3 139 Figure 8.10 Fairness index versus time for different system quanta in WDRR. . . 140 Figure 8.11 Fairness index versus time for different system quanta in DRR. . . . 140 Figure 8.12 Graceful service degradation when a = 0.5 143 Figure 8.13 Graceful service degradation when a = 0.8 143 List of Abbreviations xvi List of Abbreviations IG First Generation 2G Second Generation 3G Third Generation ABR Available Bit Rate ACK ACKnowledgment A-MMPIP Aggregated Markov Modulated Power Index Process AMPS Advanced Mobile Phone System APD Average Packet Delay AWGN Additive White Gaussian Noise BER Bit Error Rate BS Base Station CBR Constant Bit Rate CDMA Code Division Multiple Access CIF-Q Channel-Condition Independent Fair Queuing CTR Capsule Transmission Request CSDPS Channel State Dependent Packet Scheduling DFS Dynamic Frequency Selection DiffServ Differentiated Services DRR Deficit Round Robin DRS Dynamic Resource Schedulig DS Differentiated Services EDF Earliest-Deadline-First ETF Earliest Time-stamp First List of Abbreviations xvii FCFS First-Come First-Serve FDMA Frequency Division Multiple Access FFQ Frame-based Fair Queueing FSG Fixed Spreading Gain GPRS General Packet Radio Service GPS Generalized Processor Sharing GSM Global System for Mobile communications HIPERLAN High PERformance LAN HOL Head of Line HRR Hierarchical-Round-Robin IETF Internet Engineering Task Force i.i.d Independent and Identically Distributed IMT-2000 International Mobile Telecommunications in the year 2000 IntServ Integrated Services IP Internet Protocol IS-95 Interim Standard for the CDMA technology (known as cdmaOne) ITU-T International Telecommunication Union - Telecommunication IWFQ Idealized Wireless Fair Queueing LHS Left Hand Side LQF Longest Queue First LTFS Long Term Fairness Server LTR Load-based Transmission Rate MAC Medium Access Control MBS Mobile Broadband Systems MC MultiCode MMPIP Markov Modulated Power Index Process MS Mobile Station MT Mobile Terminal List of Abbreviations xviii NMT Nordic Mobile Telephone nrt-VBR non real time-Variable Bit Rate OVSF Orthogonal Variable Spreading Factor PDV Packet Delay Variation PGPS Packet by packet Generalized Processor Sharing PLR Packet Loss Rate PPR Packet Permission Reply PSD Power Spectral Density PTD Packet Transfer Delay PTR Packet Transmission Request QoS Quality of Service RGT Rate-based Grouping Transmission RLC Radio Link Control RR Round Robin RTT Radio Transmission Technology rt-VBR real time-Variable Bit Rate r.v. Random Variable SBFA Server Based Fairness Approach SCDMA Scheduled CDMA SCFQ Self Clocked Fair Queueing SIP Session Initiation Protocol SIR Signal to Interference Ratio STFQ Start Time Fair Queueing SGQ Stop-and-Go queueing TCP Transmission Control Protocol TDMA Time Division Multiple Access TGT Traffic-based Grouping Transmission TOA Time of Arrival List of Abbreviations xix TOE Time of Expiry UBR Unspecified Bit Rate U-MMPIP Unaggregated Markov Modulated Power Index Process UMTS Universal Mobile Telecommunications Services VBR Variable Bit Rate VC VirtualClock VSG Variable Spreading Gain W-CDMA Wideband Code Division Multiple Access WDRR Wireless Deficit Round Robin WFQ Weighted Fair Queueing W F 2 Q Worst-case Fair Weighted Fair Queueing WFS Wireless Fair Service WISPER Wireless Multimedia Access Control Protocol with BER Scheduling WLAN Wireless Local Area Networks WRR Weighted Round Robin WPS Wireless Packet Scheduling A c k n o w l e d g e m e n t xx Acknowledgement Thanks God, "Who teacheth by the pen, teacheth man that which he knew not" Quran 96:4,5. This is the right time to take the opportunity to express my feelings and to thank ev-eryone who helped me a lot and showed me the right path to complete my thesis. First and foremost, I would like to thank my supervisor, Dr. Cyril Leung for seeing potential in me and giving me an opportunity to work with him. Despite his busy schedule he al-ways managed to get time to guide me in my studies and research work. He created an atmosphere that was well suited to innovation and the pursuit of excellence. My time at the University of British Columbia was a great success because of his overwhelming personal and technical support. I would like to mention some very close friends who became an important part of my student life at University of British Columbia. These friends include Mohamed Ahmed, Wesam Darwish, Mohamed Mansour, Ayman Malek, Tamer Khattab, and Maged Elkashlan and many others that I am sure I will regret not having them included in this section. Finally, I would thank my parents who listened to my fears and worries, encouraged me and gave me the most. I would also like to thank my sister Heba and my brother Ahmed who supported me by taking care of my parents back in Egypt. Dedication xxi Dedication To my beloved parents. 1. Introduction 1 C h a p t e r 1 I n t r o d u c t i o n 1.1 Broadband Wireless Communications Technology Today, broadband communications and networking are among the fastest growing segments of the telecommunications industry. Traditional wireless communications and networking systems, which include cordless and cellular phones, paging systems, mobile data networks and mobile satellite systems, have evolved rapidly as a result of research and development efforts in both academia and industry. First generation (IG) cellular systems such as Nordic Mobile Telephone (NMT) and Advanced Mobile Phone System (AMPS) are analog systems based on frequency divi-sion multiple access (FDMA). Second generation (2G) cellular systems such as IS-95 and Global System for Mobile communications (GSM) are digital systems. General Packet Ra-dio Service (GPRS), which is the packet-switched extension to GSM, provides data rates up to 170 Kbps. IS-95, the Code Division Multiple Access (CDMA) digital cellular stan-dard, provides a maximum data rate of 14.4 Kbps. IS-95B can provide a peak data rate up to 76.8 Kbps. Both IG and 2G are originally tailored for voice communications and may not meet the diverse QoS requirements of multimedia applications. Third generation (3G) cellular systems are envisioned to support multidimensional [3, 4] (multi-information, multi-transmission media, and multi-layered networks) high-speed wireless communications. Studies and standardization efforts on 3G systems are being carried out under International Mobile Telecommunications in the year 2000 (IMT-2000), 1. Introduction 2 Universal Mobile Telecommunications Services (UMTS), and Mobile Broadband Systems (MBS). A majority of candidate Radio Transmission Technology (RTT) proposals for IMT-2000 (e.g., cdma2000, W-CDMA, CDMA I, and CDMA II) use Direct Sequence Code Division Multiple Access (DS/CDMA) as the leading multiple access technique due to its many desirable features such as higher (soft) system capacity, soft handoff, simple fre-quency planning, and inherent frequency diversity against multipath fading. Activities on the harmonization of the technical specifications for different RTT candidates are being carried out with the aim to achieve an efficient 3G standard capable of supporting broad-band services. 3G systems aim at providing high-speed data services with data rates up to 144 Kbps in a vehicular environment and up to 2 Mbps in indoor and picocellular environ-ments. The peak data rate achievable in cdma2000, the North American 3G standard, is 307.2 Kbps in a 1.25 MHz bandwidth or 614.4 Kbps in a 5 MHz bandwidth. On the other hand, recent Wireless LAN (WLAN) standards such as IEEE 802.1 lg and High PERfor-mance LAN (HIPERLAN/2) have peak data rates of 54 Mbps in the 2.4 GHz and 5 GHz bandwidth respectively. Although wireless cellular networks have been very successful in providing mobile voice service, the growth of wireless multimedia services has been much slower due to low-speed wireless access links, poor link performance, lack of efficient Quality of Service (QoS) support, and expensive user devices and battery technology. In this difficult en-vironment, made even more complex by unpredictable radio propagation, providing QoS guarantees is a real challenge. QoS approaches, as inherited from wireline multimedia networks, need to be revised to take into account the new challenges. The increasing demand for accessing the Internet anytime, anywhere and the develop-ment of a large number of innovative Internet-based applications and devices highlight the need for efficient and seamless QoS control mechanisms that are able to support different levels of service as opposed to a single best-effort level of service. Most services and ap-plications currently available in wireline Internet such as web browsing, E-mail, and file transfer will be adapted and extended to the wireless domain. Traffic generated by different 1. Introduction 3 multimedia applications exhibit a large variety of characteristics and requirements, such as transmission bit rate, maximum tolerable bit error rate, and timeout specifications. Be-cause of this variability, it is expected that traditional voice-optimized wireless networks will perform poorly. What is required is a high-speed access technology combined with highly flexible QoS-aware Medium Access Control (MAC) protocols and scheduling that can easily and efficiently multiplex multimedia traffic over the air interface of the wireless network. 1.2 Motivation and Thesis Contributions The motivation behind this research flows from one main fact: the potential of a large market that stems from the rapidly increasing demand for wireless Internet services. The emergence of cellular wireless networks is envisioned to provide a variety of broadband mobile services and necessitate the provision of QoS guarantees. This includes high-speed Internet access and audio/video delivery. Supporting multimedia applications along with the legacy wireless applications within an integrated networking framework requires new network infrastructure and different protocol design issues. The proposed research encompasses several design issues in the area of wireless packet networking technology supporting multimedia communication. The research is focused at the Radio Link Control (RLC)/(MAC) layers with the aim of contributing to the devel-opment of wireless multimedia packet networks which can be efficiently integrated with the Internet. This thesis proposes different QoS scheduling (or assignment) schemes for supporting multimedia traffic. These schemes are based on three basic QoS approaches, namely guaranteed (or deterministic), soft, and relative QoS. Guaranteed QoS is achieved by analyzing the target QoS parameters (e.g., packet delay, loss rate, delay jitter) and re-serving fixed resources for the duration of the connection to meet the target QoS. When a session traffic load is light, a guaranteed QoS approach may result in low resource uti-lization. Soft QoS may allow a tolerable degradation in the QoS targets but provides more 1. Introduction 4 efficient resource utilization than guaranteed QoS since it allows dynamic resource reser-vation. Soft QoS is different from best-effort QoS in that the latter does not consider the QoS requirements of the sessions. Relative QoS, on the other hand, only guarantees that a certain session will receive a better service relative to another session. QoS can be expressed in terms of different parameters such as packet transfer delay, packet delay jitter, packet loss rate, or transmission bit rate. The scheduling scheme in Chapter 4 can provide either deterministic or relative QoS for different service classes. The scheme in Chapter 5 focuses only on a single class (i.e., data). Both deterministic and soft QoS for different service classes are provided through the mechanism in Chapter 6. The fair queueing architecture and scheduler in Chapters 7 and 8 focus on meeting the target transmission bit rates for different classes and achieving tight delay bound and fairness index. The resource management schemes proposed in this thesis differ in their goals, objec-tives, and/or the required information needed for their operations. In practice, a network operator wil l choose which scheme to implement. For example, if a network operator needs to provide guaranteed QoS for different classes, such as voice, video, and data, the schemes in Chapter 4 and 6 may be used. The scheme in Chapter 5 is appropriate for a network with data users where the objective is to minimize the overall average packet transfer delay. The fair queueing algorithms in Chapters 7 and 8 can be adapted for wireless routers where hundreds or thousands of sessions share the same output link. In the thesis, a novel method for calculating the capacity in a C D M A network with multimedia traffic is proposed. This method is able to capture the different and wide vari-ations in traffic characteristics and hence can be used for calculating the network capacity in broadband systems. In the analysis, each traffic source is represented by a continuous time Markov-Modulated process in which each state represents a different transmission bit rate. The method allows performance measures such as the Erlang capacity and outage or blocking probability to be obtained. Providing some kind of service differentiation among different service classes has been 1. Introduction 5 a problem of enormous commercial and research importance. The differentiated services (DiffServ) and integrated services (IntServ) models were proposed as possible solutions to this problem [5-14]. A fundamentally different approach in the DiffServ model is the pro-portional differentiated services model where the network traffic is grouped into iV service classes which are ordered, such that class i is better (or at least no worse) than class (i — 1) in terms of local performance metrics. The proportional DiffServ model is introduced in the wireless domain by proposing a scheduling scheme that is able to meet either the target absolute QoS parameter values such as throughput, packet loss rate, average packet delay, and delay jitter or relative QoS ratios. The conditions in which absolute or relative QoS targets can be met are stated and followed by an optimization problem that maximizes the rate allocations among Mobile Stations (MSs) while ensuring the stability of packet queues and meeting the transmit power level constraint. In a wireless environment, it is necessary to use the limited wireless resources in an efficient manner while supporting a reasonable level of QoS (e.g., packet transfer delay) requirements. A Load-based Transmission Rate (LTR) scheduling scheme is considered which assigns a transmission rate to each session according to its load so as to minimize the overall packet transfer delay while supporting integrated voice/data services. While the transmission schemes in [15,16] focus on enhancing throughput and do not consider possible traffic load differences among data sessions, the LTR scheme takes into account the arrival processes of data sessions and aims at minimizing the overall packet transfer delay. It is shown that the packet transfer delay of the LTR scheme is significantly improved over that of the conventional scheme employed in IS-95. The design of MAC protocols that allow sharing of the radio spectrum among multi-media traffic while providing end-to-end soft QoS guarantee and maintaining high channel utilization is a useful scenario in the wireless environment. For this purpose, a reserva-tion scheme combined with a number of centralized dynamic priority based packet-level schedulers is proposed for the transmission of multimedia traffic over CDMA channels with power control. In this scheme, the number of packets selected for transmission from a 1. Introduction 6 session is changed dynamically depending on the traffic type, traffic load, Time of Expiry (TOE)/Time of Arrival (TOA) values of packets, and packet queue length. The performance of the proposed scheme is evaluated through analysis and simulation for voice, video, and data traffic models. Simulation results show that the proposed scheme can provide high channel utilization with QoS guarantees in a multimedia traffic environment. Fair queueing algorithms are important components for QoS provision and have been extensively studied in wireline networks. While, many of these algorithms have been adapted to the wireless domain [17], the proposed algorithms generally assume downlink operation so that information about session queue statuses is available to the scheduler. For uplink transmissions, the scheduler (which is located at the base station) does not have immediate access to the statuses of the queues which are remotely distributed at the MSs. In addition, these algorithms are designed for systems in which no multiple simultaneous transmissions are allowed. An architecture for employing these algorithms on both down-link and uplink in CDMA networks is proposed which allow multiple simultaneous trans-missions. This architecture is able to employ any of the wireless fair queueing algorithms and thus allows different algorithms to be used with their attendant pros and cons. The architecture also addresses the issue of time scheduling using a new Generalized Processor Sharing (GPS) approach that utilizes the available power resource efficiently by assigning variable power indices to the mobile stations. Operation in error-prone channels is enabled by a mechanism that compensates mobile stations which experience poor channels. This approach supports multirate transmission techniques such as variable spreading gain and multicode. Bursty channel errors and location-dependent channel capacity and errors are unique factors in wireless networks that need to be taken into consideration when applying wireline scheduling algorithms to the wireless domain. An improved round robin scheduling algo-rithm for CDMA packet cellular networks called Wireless Deficit Round Robin (WDRR), is proposed. WDRR has low implementation complexity, low delay bound, tight fairness index, and good isolation property. In error-prone channels, the algorithm provides short-1. Introduction 7 term fairness among sessions that perceive a clean channel, long-term fairness among all sessions, ability to meet specified throughput objectives for all sessions, and graceful ser-vice degradation among sessions that received excess service. Both analysis and simulation are used to verify the WDRR properties. 1.3 Thesis Outline Subsequent chapters of this dissertation are organized as follows: • In Chapter 2, an overview of multimedia scheduling techniques in wireless networks is provided [18]. Some of the challenges in designing such schedulers are first dis-cussed. Desirable features and classifications of schedulers are then reviewed. This is followed by a discussion of several scheduling algorithms which have been proposed for TDMA and CDMA packet networks. • In Chapter 3, the capacity of a DS/CDMA network with multirate sources is calcu-lated using a continuous-time Markov process for each traffic source [19,20]. An analytical approach is used to obtain the network capacity or outage probability. • In Chapter 4, a guaranteed QoS scheduling scheme for multimedia traffic is proposed, analyzed, and evaluated through simulation [21]. The basic premise here is that the access scheme is able to employ the proportional differentiated service model among different service classes. • In Chapter 5, an LTR scheduling scheme for non-real time data services in the inte-grated voice/data systems is introduced [22]. The LTR scheme optimally determines multiple different transmission rates according to the load of each user so as to min-imize the overall packet transfer delay. • In Chapter 6, a power reservation scheduling policy that the BS can use for servic-ing multimedia traffic in a power controlled CDMA system is presented [23]. This scheme is based on soft resource isolation for different types of traffic and at the same 1. Introduction 8 type dynamic allocations based on the instantaneous needs of the sessions carrying the same type of traffic. • In Chapter 7, a fair queueing architecture for both uplink and downlink is proposed that is able to employ any of the wireless/wireline fair queueing algorithms [24]. Along with the architecture, a novel GPS approach is reviewed that addresses the issue of time scheduling. • In Chapter 8, a WDRR algorithm is presented for use in a packet cellular network [25]. The algorithm is shown to possess the desirable properties of a wireless scheduling algorithm. The algorithm is analyzed and its properties is verified through computer simulations. • In Chapter 9, the contributions of the thesis are summarized and directions for future research are provided. 2. Scheduling Multimedia Traffic 9 C h a p t e r 2 S c h e d u l i n g M u l t i m e d i a Traf f i c i n Wire less N e t w o r k s 2.1 Introduction For many applications, it is important that certain Quality of Service (QoS) targets be met. At the same time, the demand for enabling such applications in a mobile environment is growing rapidly. As an example, the Internet is a continuously evolving entity which is being used by a growing number of mobile applications with diverse QoS requirements. Many new applications are driving calls for substantial changes in the current network in-frastructure. Specifically, the emergence of applications with very different throughput, loss rate, delay or delay jitter requirements underscores the need for a network capable of supporting different levels of service, as opposed to a single, best-effort level of service. Ta-ble 2.1 shows typical QoS requirements for several service classes: non real time-Variable Bit Rate (nrt-VBR), Available Bit Rate (ABR), Unspecified Bit Rate (UBR), Constant Bit Rate (CBR) and real t ime-VBR (rt-VBR). Some example applications are also listed. To meet the wide-ranging QoS requirements of these applications, traffic scheduling algorithms can be employed. Schedulers operate across different sessions (connections or flows) in order to ensure that reserved throughputs and bounds on delays and loss rates are met. As illustrated in Fig. 2.1, the function of a scheduling algorithm is to select the session whose head-of-line (HOL) packet is to be transmitted next. This selection process is based 2. Scheduling Multimedia Traffic 10 Table 2.1. QoS requirements for different applications. Class Appl ica t ion Bandwidth (bps) Delay bound (ms) Loss rate C B R Voice 3 2 K - 2 M 30-60 IO" 2 n r t - V B R Dig i t a l video 1 M - 1 0 M large i o - 6 r t - V B R Video conference 1 2 8 K - 6 M 40-90 IO" 3 U B R F i l e transfer 1 M - 1 0 M large IO" 8 A B R Web browsing • 1 M - 1 0 M large i o - 8 on the QoS requirements of each session. Each Mobile Station (MS) can support one or more sessions at any given time. A large number of traffic scheduling algorithms for wireline networks have been pro-posed in the literature [26-60]. However, these algorithms cannot be directly applied to wireless networks because of fundamental differences between these two types of net-works. In this Chapter, we provide an overview of scheduling techniques which have been proposed for wireless networks to support the provision of guaranteed QoS. Session 1 Session 2 Session /V Figure 2.1. Typical wireless scheduler. 2. Scheduling Multimedia Traffic 11 2.2 Wireless Network Scheduler Challenges Wireless links generally possess characteristics which are quite different from those of wireline links. They are subject to time and location dependent signal attenuation, fading, interference, and noise which result in bursty errors and time-varying channel capacities. A wireless channel model that is frequently used in the study of scheduling algorithms is a discrete-time Markov chain with two states: error-free ("good") or error-prone ("bad") [61]. The channel moves between the two states according to a certain transition probability matrix. A packet is successfully received if and only if the link stays in the good state throughout the packet transmission time. In order to make scheduling decisions, certain information such as the number of ses-sions, their reserved rates and link states, and the statuses of session queues is needed by the scheduler. This information may be easily available for the downlink if the scheduler is located at the Base Station (BS). For the uplink, some means must be provided to collect queue status information and to inform MSs of their transmission times. Another challenge arises from the need to maximize MS battery life. In order to con-serve energy, it is preferable for an MS to transmit/receive in contiguous time slots and then go into a sleep (very low energy consumption) mode for an extended period rather than to rapidly switch among transmit, receive and sleep modes. However, this preference has to be balanced against the need to maintain QoS levels. Handoffs are required in cellular networks when an MS, S, moves from its current cell Ci to a neighboring cell C 2 . Following a handoff, any packets for S which are queued at Ci's BS will be forwarded to C2's BS. One problem that arises in time-stamp based scheduling is how the time-stamp values for these packets ought to be changed. Another problem is that a handoff may result in the time-stamps of packets of a new session being artificially low. This may cause the new session to receive extra service and hence introduce a fairness gap among sessions [62]. In a Code Division Multiple Access (CDMA) network, the total interference at an MS 2. Scheduling Multimedia Traffic 12 must be small enough to ensure an adequate Signal-to-Interference Ratio (SIR) for each session, thereby enabling its target bit error rate (BER) to be met. The scheduler should ensure that the number of simultaneous transmissions in the network is not so high as to result in excessive interference. 2.3 Scheduler Components and Properties The following components are generally included in a scheduler in order to provide efficient operation in a wireless environment [61,63]. • An error-free service model which describes how the algorithm provides service to sessions with error-free channels. • A lead/lag counter for each session which indicates whether the session is leading, in-sync with, or lagging its error-free service model and by how much. • A compensation model which is used to improve fairness among sessions. A lagging session is compensated at the expense of leading sessions when its link becomes error-free again. • Separate slot and packet queues for each session can be used to support both delay-sensitive and error-sensitive sessions. When a packet arrives, it is time-stamped and placed in the packet queue; a slot with the same time-stamp value is added to the slot queue. If the HOL packet for a session is dropped due either to excessive delay or an excessive number of retransmissions, the precedence of the session for accessing the channel is maintained by the slot queue. • A means for monitoring and predicting the channel state for every backlogged ses-sion, i.e., a session with packets available for transmission. It is desirable for a scheduling algorithm to possess the following features [34,42]: 1. Efficient link utilization: The algorithm must utilize the channel efficiently. This implies that the scheduler should not assign a transmission slot to a session with a 2. Scheduling Multimedia Traffic 13 currently bad link as the transmission wil l simply be wasted. 2. Delay bound: The algorithm must be able to provide delay bound guarantees for individual sessions in order to support delay-sensitive applications. 3. Fairness: The algorithm should redistribute available resources fairly across ses-sions. It should provide fairness among error-free sessions (short-term fairness) and among error-prone sessions (long-term fairness). 4. Throughput: The algorithm should provide guaranteed short-term throughputs for error-free sessions and guaranteed long-term throughputs for all sessions. 5. Implementation complexity: A low-complexity algorithm is a necessity in high-speed networks in which scheduling decisions have to be made very rapidly. 6. Graceful service degradation: A session which has received excess service at the expense of sessions whose links were bad should experience a smooth service degra-dation when relinquishing the excess service to lagging sessions whose links are now good. 7. Isolation: The algorithm should isolate a session from the ill-effects of misbehaving sessions. The QoS guarantees for a session should be maintained even in the presence of sessions whose demands are in excess of their reserved values. 8. Energy consumption: The algorithm should take into account the need to prolong the M S battery life. 9. Delay/bandwidth decoupling: For most schedulers, the delay is tightly coupled with the reserved rate, i.e., a higher reserved rate provides a lower delay. However, some high-bandwidth applications, e.g. web-browsing, can tolerate relatively large delays. 10. Scalability: The algorithm should operate efficiently as the number of sessions shar-ing the channel increases. 2. Scheduling Multimedia Traffic 14 2.4 Scheduler Classification Schedulers can be classified as work-conserving or non-work-conserving [34]. A work-conserving scheduler is never idle if there is a packet awaiting transmission. Examples in-clude Generalized Processor Sharing (GPS), Packet-by-packet GPS also known as Weighted Fair Queueing (WFQ), VirtualClock (VC), Weighted Round Robin (WRR), Self-Clocked Fair Queueing (SCFQ), and Deficit Round Robin (DRR). In contrast, a non-work-conserving scheduler may be idle even if there is a backlogged packet in the system because it may be expecting another higher priority packet to arrive. Examples are Hierarchical-Round-Robin (HRR), Stop-and-Go queueing (SGQ), and Jitter-Earliest-Due-Date (Jitter-EDD). Non-work-conserving schedulers generally have higher average packet delays than their work-conserving counterparts but may be used in applications where time jitter is more important than delay. A time-stamped scheduler is one which serves packets according to their time-stamp values. Incoming packets are time-stamped before being placed in their respective session queues. The H O L packets are then sorted in increasing order of their time-stamps and the packet with the lowest time-stamp value is selected for transmission. Round robin schedulers do not use time-stamps and can be more easily implemented. However, time-stamped schedulers can provide better QoS guarantees. In a sorted-priority scheduler, each session has a different priority level and packets are chosen for transmission according to their session priority. Examples include V C , W F Q and Jitter-EDD. By contrast, in ^frame-based scheduler, time is divided into frames of fixed or variable size. Each session reserves a portion of the frame for transmitting its packets. H R R and SGQ use fixed-size frames whereas WRR, DRR, and Frame-based Fair Queue-ing (FFQ) use variable-size frames. Fixed-frame size schedulers are non-work-conserving because the scheduler may remain idle if a session runs out of packets to transmit during its reserved portion. 2. Scheduling Multimedia Traffic 15 2.5 Generalized Processor Sharing (GPS) Based Schedul-ing GPS [26] is an efficient, flexible, and fair scheduler originally proposed for use in an error-free environment. It is an idealized fluid-flow model which services all sessions simultane-ously. Many of the proposed time-stamp based algorithms simulate GPS in the background in order to inherit some of its properties. GPS is a work-conserving scheduler which operates at a fixed channel rate C. It is characterized by positive real numbers R\, R 2 , . . . , RN which represent the reserved trans-mission rates of the ./V sessions. The sum of these rates should not exceed C. Each session is guaranteed its reserved rate and the traffic, Wi(ti, t2), served from session i in a time in-terval (ti,t2] is directly proportional to its reserved rate. The expression Wi(£<t2) represents the time allocated to serve session i and is referred to as the normalized service received by a session i. GPS possesses two desirable properties: 1) it provides an end-to-end delay bound if the incoming traffic is well-behaved, i.e. does not exceed its reserved rate, and 2) it provides an equal normalized service to all sessions. The fairness index is commonly defined as the maximum difference between the normalized service received by any two backlogged sessions. GPS is optimal in that it has a fairness index of 0. In order to implement GPS in a Time Division Multiple Access (TDMA) packet net-work, in which one session is served at a time and packets are not infinitely divisible, the GPS algorithm is simulated in the background. This is done through the virtual time func-tion, v(t), which keeps track of the total work performed in GPS. The virtual time function is computed using D ^ = C(J2Rl)-\ v(0) = 0, (2.1) where B(t) is the set of backlogged sessions at time t. Each incoming packet is assigned a 2. Scheduling Multimedia Traffic 16 time-stamp value, Ff, computed according to 0 (2.2) where Sf, L* \ and a1* are the virtual start time, virtual finish time, packet length and arrival time of the kth packet of session i respectively. Packet-by-packet GPS (PGPS) tries to emulate GPS by serving packets in increasing order of their time-stamps. However, it is shown in [44] that the service under PGPS can be quite different from that under GPS. The difference increases with the number of sessions. To overcome this problem, the authors proposed Worst-case Fair Weighted Fair Queueing (WF2Q) which selects a packet for transmission at time t if it has the lowest virtual finish time according to (2.2) from among those that have started (and possibly finished) service under GPS. The packet selection process in WF2Q provides a closer emulation of GPS than that afforded by PGPS. Table 2.2 shows a comparison of three properties of some schedulers originally pro-posed for wireline networks. These algorithms can be used as the error-free service model in the design of wireless schedulers. For effective operation in a wireless environment, the appropriate components mentioned in Section 2.3 also need to be incorporated. 2.6 Scheduling Algorithms for Wireless T D M A Networks In a TDMA network, only one session can transmit at any given time. In this section, we review some of the proposed scheduling algorithms for wireless TDMA networks [63]. 2.6.1 Network Model We consider a packet cellular system consisting of one BS and a number of MSs. Schedul-ing is implemented at the BS which can communicate with all MSs; direct MS-to-MS 2. Scheduling Multimedia Traffic 17 Table 2.2. Comparison of scheduler properties. Delay bound Fairness Complexity PGPS (WFQ) small good O(iV) SCFQ large moderate O(logJV) VC small none O(logiV) DRR large poor 0(1) FFQ small moderate 0(1) WF2Q small very good O(N) communication is not possible. Packets exchanged between the BS and an MS may ex-perience channel errors. Knowledge of the channel state and packet queue status for all sessions is available at the BS. 2.6.2 Channel State Dependent Packet Scheduling (CSDPS) CSDPS is a wireless scheduling framework which allows the use of different service dis-ciplines such as Round Robin (RR), Longest Queue First (LQF), or Earliest Time-stamp First (ETF). The main idea behind CSDPS is to avoid bursty errors at the link layer instead of relying on the transport or application layer for error recovery. The channel state for each session is monitored and if the channel for a session which is due to transmit is in a bad state, the transmission of its packet is deferred. CSDPS does not include the concept of lead and lag and does not provide any compensation for lagging sessions. 2.6.3 Idealized Wireless Fair Queueing (IWFQ) rWFQ is a realization of PGPS with a compensation mechanism for error-prone sessions [61] WF2Q can also be used as the error-free service model. Each session has a service tag that is set equal to the virtual finish time of its HOL packet. If the session is not backlogged, the service tag is set to o o . Each incoming packet is stamped as in (2.2) and queued. The 2. Scheduling Multimedia Traffic 18 algorithm services sessions with good channels in increasing order of their service tags. Lagging sessions will have the lowest service tag values and thus whenever their links become error-free again, they will get access to the channel in preference to leading or in-sync sessions. During this time, non-lagging sessions are unable to transmit. To control this "black-out" period, IWFQ sets bounds on the lead and lag of each session. One drawback of IWFQ is that it does not provide graceful service degradation for leading sessions as a lagging session will capture the channel until it has been compensated for all its lag. 2.6.4 Channel-Condition Independent Fair Queuing (CIF-Q) CIF-Q uses Start Time Fair Queueing (STFQ) as its error-free service model because the authors [64] state that with location-dependent channel errors, it is easier to base scheduling on the start time rather than the finish time. Each session has a lead and lag counter which indicates the number of packets by which the session is leading or lagging its error-free service model. CIF-Q uses a parameter a £ [0,1] to control the rate at which a leading session gives up its lead to a lagging session: a leading session i retains a fraction a of its service and relinquishes the balance of its service to a lagging session. A lead/lag counter bound is not needed since the parameter a can be chosen so as to provide a graceful service degradation for leading sessions. 2.6.5 Server Based Fairness Approach (SBFA) SBFA is a framework that can accommodate any wireline scheduler as its error-free service model [65]. In SBFA, a portion of the outgoing bandwidth is reserved for a hypothetical session called Long-Term Fairness Server (LTFS). The LTFS is used to compensate lag-ging sessions. When a session is selected for transmission, it is allowed to transmit if it experiences a good channel; otherwise a slot for this session is created and queued into the LTFS session and a session with a good channel is selected instead for transmission. When the HOL slot from the LTFS session is selected for transmission, the slot's original 2. Scheduling Multimedia Traffic 19 session is allowed to transmit if it has a good channel; otherwise the next slot is selected. No lead/lag counters are required since the compensation rates provided to lagging sessions are determined by the LTFS reserved bandwidth. 2.6.6 Wireless Fair Service (WFS) WFS has an error-free service model that provide decoupling of delay and bandwidth [66]. The incoming packets are time-stamped according to Ff = £ + maxKo*), + (2-3) fa Hi where fa is the decoupling weight. The service tag of each session is set equal to the virtual finish time of its HOL packet. Sessions are selected for transmission in increasing order of their service tag values provided that the virtual start time of the HOL packet is less than v(t) + Q where g is a look-ahead parameter which determines the schedulable interval. For example, if g = oo and Ri = fa, the error-free service is WFQ. If g — 0 and Ri = fa, the error-free service is WF2Q. Lead and lag counters are used to achieve fairness and graceful service degradation for leading sessions. 2.6.7 Summary The schedulers described previously have O(N) complexity for selecting a session with a good channel for transmission. This is in addition to the complexity associated with emulating their error-free service models. The error-free service complexity of IWFQ, CIF-Q and WFS is O(N). These schedulers can provide good throughput guarantees and delay bounds. The properties of CSDPS and SBFA depend on the specific scheduling algorithm used. None of the schedulers address the issue of MS power'savings. Tables 2.3 and 2.4 provide a summary of the scheduler components and properties. 2. Scheduling Multimedia Traffic 20 Table 2.3. Comparison of wireless scheduler components. CSDPS IWFQ CIF-Q SBFA WFS Error-free model any W F Q STFQ any WFS Lead/lag model no yes yes no yes Compensation model no yes yes yes yes Slot/packet queue no yes no yes yes Graceful degradation no no yes yes yes Table 2.4. Comparison of wireless scheduler properties. long-term throughput guarantee Delay bound Short-term fairness Delay/bandwidth decoupling CSDPS no no no no IWFQ yes yes no no CIF-Q yes yes yes no SBFA yes no no no WFS yes yes yes yes 2.7 Scheduling in C D M A Networks We now describe some schedulers which have been proposed for use in C D M A networks. C D M A can provide several advantages over T D M A and Frequency Division Multiple A c -cess (FDMA) , such as higher (soft) system capacity, soft handoff, simple frequency plan-ning and inherent frequency diversity against multipath fading. Voice activity factor and antenna sectorization are readily exploited using C D M A . One drawback is that an accu-rate power control mechanism is required. The soft capacity feature of C D M A allows a new session to be established provided that the SIR's for all transmitting sessions can be maintained above their target levels a certain percentage of the time [1]. 2. Scheduling Multimedia Traffic 21 In CDMA systems, the packets sent from a number of MSs can be successfully received simultaneously at the BS, provided an adequate power control scheme is used. Such a scheme may attempt to minimize the total transmitted power subject to meeting rate and SIR targets for each session [1]. It has been shown [67] that to satisfy the required BER or equivalently ji for session i, the following inequality should hold i=l h ~ w i where Gi is the Fixed Spreading Gain (FSG) of session i and jt is its SIR. For convenient, 9i = T+G- 1S c a U e ( l m e P o w e r index of session i. Each session is assigned a transmit power level, Pi, according to N0W9i where N0/2 is the power spectral density of the Gaussian noise and W is the channel bandwidth. A new session is admitted as long as inequality (2.4) can be satisfied. 2.7.1 Packet-by-packet GPS A PGPS model for CDMA has been proposed in which multiple sessions are serviced simultaneously [68]. The PGPS server in CDMA is work-conserving and operates between different sessions to guarantee their transmission rates and power indices (or SIRs). The virtual time function in this PGPS model differs slightly from that in (2.1): C is replaced by S i € A ( t ) -fti> where A(t) is the set of all admitted sessions at time t. Each packet is time-stamped according to (2.2) and packets are selected for transmission in increasing order of their virtual finish times. In contrast to a TDMA system in which only one packet can be transmitted at a time, a number of packets can be selected for simultaneous transmission as long as their power indices satisfy (2.4). PGPS has a residual power index problem because each session is assumed to have a fixed power index value. When a number of packets from different sessions are selected for 2. Scheduling Multimedia Traffic 22 transmission, the sum of their power indices may not be close to 1 (see (2.4)) thus resulting in a residual power index that is not utilized. To alleviate this problem, PGPS tries to find one or more additional (non-HOL packets) packets which can be transmitted and which will not result in (2.4) being violated. However, this does not solve the residual power index problem completely. 2.7.2 Scheduled CDMA Scheduled CDMA (SCDMA) [69] is a hybrid CDMA/TDMA scheduler in which the BS schedules transmissions of the MSs as shown in Fig. 2.2. Data are exchanged between the BS and MSs in a fixed-size unit called capsule which can accommodate one or more packets. All MSs in a cell have the same capsule size. SCDMA assumes time-slotted operation in which MSs are allowed to transmit simultaneously in each time slot. For uplink scheduling, a capsule transmission request (CTR) is sent to the BS by an MS whenever the MS has new packets to transmit. The BS sorts the CTRs according to their priority level or delay tolerance and places them in a global queue. For each time slot, the scheduler selects CTRs, whose capsules can be transmitted in that time slot, starting from the head of the queue until (2.4) is satisfied. The BS then sends transmission permis-sion capsules to the selected MSs to inform them of their capsule transmission times and power levels. 2.7.3 Dynamic Resource Scheduling (DRS) DRS is a centralized and adaptive framework for providing resource scheduling through optimal power assignment and code hopping in Wideband-CDMA (W-CDMA) [70]. DRS is a modified version of SCDMA without the TDMA aspect. In DRS, MSs send their requests to the BS. The BS classifies them according to the traffic characteristics of the requested service, and places them into two separate queues: guaranteed and best-effort queues as shown in Fig. 2.3. The guaranteed queue contains requests from sources which 2. Scheduling Multimedia Traffic 23 Capsule transmission request Reply Scheduler Global queue Power allocation Base Station Figure 2.2. Scheduled CDMA scheduler. need to be serviced at a predefined rate such as VBR, CBR, and minimum-rate ABR. The best-effort queue contains UBR and excess ABR requests. The scheduler fulfills requests in the guaranteed queue ahead of those in the best-effort queue as long as (2.4) is satisfied. DRS guarantees the predefined rate of each session. However, neither DRS nor SCDMA provide guaranteed delay bounds. 2.7.4 Wireless Multimedia Access Control Protocol with BER Schedul-ing (WISPER) In WISPER [71], packets are transmitted within frames of length T in both uplink and downlink as shown in Fig. 2.4. The uplink request slot is used by an MS to place transmis-sion requests. The downlink control slot is used by the BS to grant transmission permis-sions. 2. Scheduling Multimedia Traffic 24 Requests Power assignment Classifier arSriteed Best effort queue / queue Power scheduler Base Station Figure 2.3. Dynamic resource scheduler. UPLINK Frame k — T Request Slot Slot Slot 1 I 2 1 Slot I N DOWNLINK Frame k+l T Slot _ J _ L Frame k+l T Slot Slot \N-l\ N Control Slot Figure 2.4. WISPER uplink/downlink frame format. 2. Scheduling Multimedia Traffic 25 There are a number of traffic classes, each with a different BER requirement. Packets are assumed to arrive in batches and all packets in a given batch have the same expiry time. For each batch, WISPER first assigns a priority value which is directly proportional to the remaining number of packets in the batch and inversely proportional to the remaining time before the packets expire and the maximum MS transmission rate. The algorithm selects packets for transmission in order of priority and tries to maximize the number of packets that can be transmitted in a frame. The selected packets are grouped into the TV slots according to the following order: (a) empty slots or slots that contain only packets with the same BER requirements, (b) slots that contain packets with stricter BER requirements and (c) slots that contain packets with looser BER requirements. One drawback is that the maximum number of packets accommodated in a slot is determined by the packet with the strictest BER requirement in the slot. This results in an inefficient slot usage if packets with widely different BER requirements are placed in the same slot. 2.8 Summary The emergence of new multimedia and Internet applications for the wireless domain has spurred the study of scheduling algorithms for providing QoS guarantees. These guaran-tees are usually in the form of bounded delay and jitter, guaranteed rate and fairness among sessions. In this Chapter, a survey of schedulers for wireless networks was provided. Desir-able features and design challenges of such schedulers were outlined. The advantages and drawbacks of some proposed schedulers were discussed. Much work remains to be done in the design and performance evaluation of wireless schedulers, especially for CDMA. 3. Erlang Capacity with Multirate Traffic Sources 26 C h a p t e r 3 E r l a n g C a p a c i t y of a D S / C D M A Sys tem wi th M u l t i r a t e Traf f i c Sources 3.1 Introduction Traffic sources in a Code Division Multiple Access (CDMA) network share a common frequency band during the course of their connections. The soft capacity feature of CDMA allows a source to establish a new connection provided that the total interference at the BS (Base Station) due to all source activities does not exceed the background thermal noise by about 10 dB [1,72]. A power control mechanism may be employed in CDMA networks in order to meet the target Quality of Service (QoS) objectives. Many power control mechanisms have been proposed in the literature to minimize the total transmit power or maximize the total transmit bit rate [67,73]. Due to Mobile Station (MS) power and battery constraints, a power control mechanism that minimizes the transmit power of each MS is highly desirable [16,69,74]. In order to design a system which has different QoS requirements such as blocking probability, bit error rate (BER), or transmission bit rate, the Erlang capacity of the net-work needs to be determined given the variable transmission rate of each traffic source. The Erlang capacity is defined as the average offered traffic load that can be supported at a given value of the blocking probability, i.e. the probability that the admission criterion is not satisfied [1]. The Erlang capacity has been calculated in [1] for voice sources only 3. Erlang Capacity with Multirate Traffic Sources 27 based on an ON/OFF Markov model for each source. The capacity for a voice/data" system is studied in [16] and extended in [75] to include video sources assuming a single transmis-sion rate for each source (e.g., average transmission rate [15]). While these studies provide insight into the capacity, they assume either an ON/OFF model or a single transmission rate for each traffic source. For many applications, this assumption is not realistic. In prac-tice, different multimedia applications may have multiple transmission bit rates or possess different characteristics such as burstiness or correlation. For example, voice sources with fast speech activity detection is represented by a three-state Markov model corresponding to talking, pausing, and listening [76]. Voice codecs have variable transmission bit rates [2]. Video sources can have different number of states corresponding to different transmission bit rate requirements [77]. It is therefore desirable to develop a flexible and efficient ap-proach to calculate the system capacity accurately while being able to accommodate the wide variations in transmission bit rate requirements. In this Chapter, we present a novel method for calculating the Erlang capacity of a CDMA system in which different classes of traffic sources (i.e., voice, video, and data) have variable transmission bit rates. The method is able to capture the wide variations in traffic characteristics such as burstiness or correlation as would be encountered in broadband wireless networks with multimedia traffic. • , • - • 3.2 System Model and Admission Criterion We consider the uplink of a cellular Direct-Sequence (DS) CDMA network. Interference from adjacent cells experienced by a BS is represented by the relative other-cell interference factor [1,78], / , given by f = j r cc where Poc and Pcc represent the other-cell interference power and the power from all sources in the current cell respectively. In [78], it is shown that / « 0.55 when the prop-3. Erlang Capacity with Multirate Traffic Sources 28 agation attenuation is proportional to the fourth power of the distance times a lognormally distributed component with 8 dB differential standard deviation. We assume a total num-ber, N, of traffic sources in the cell. Each traffic source i is modelled by a continuous-time Markov process in which each state represents a different power index value that corre-sponds to a target BER and transmission bit rate as described later. Let the instantaneous received power of source i be denoted by Pi, its maximum trans-mit power be Pi and its spreading gain Si = W/ Ri where W is the spread bandwidth and Ri is the transmission bit rate. The BER requirement for source % is expressed in terms of its signal-to-interference ratio ji required to be received. The background noise is assumed to be additive white Gaussian noise (AWGN) with power spectral density N0/2. The bit energy-to-interference ratio E^/IQ for source i is given by (—)i = -, , M : , i = l,2,...,N. (3.2) • Eb\ _ SjPj ~h ~ (1 + /) Ef=i Pi -Pi + N0W The BER and transmission bit rate QoS requirements are satisfied at any given time if ——ar-^ > 7 t , i = l,2,...,iV. (3.3) {l + fiUjLiPj-Pi + NoW ~ Given a maximum transmit power level and a minimum transmission bit rate for each source, an optimal solution that minimizes the maximum transmit power or minimizes the sum of transmit powers exists when all constrains in (3.3) are met with equality [67] i.e., SiPj :i + f)EUp!-p? + N ° w From (3.4), it can be shown that the optimum power for source i is 7 i = - r — J T - ^ , Vi = l,2,...,W. (3.4) P: = [^(1 + f)Ep; + N0w\, (3.5) i= i where gi is the power index [68] of source i and is defined as # = — , i = l,2,...,N. (3.6) 7i + 3. Erlang Capacity with Multirate Traffic Sources 29 Summing (3.5) over all sources yields N AT. TJ/ i=l 1 (3.7) Notice that in (3.2), the received power of a source is not considered a part of its total interference which is true if there is no multipath fading or the energy of a signal in all multipath components can be 100% resolved. If self-interference is included, it is easy to show that the power index will be given by & = | , * = l,2,...,iV, (3.8) Oi which has a higher value than in (3.6). Substituting (3.7) to (3.5) yields p; = , , r u v : ^ N . , * = i ,2 , . . . , ;v . (3.9) N0Wg, i - ( i + / ) E f = i a Since P* > 0, we can conclude from (3.9) that N lZ9i<T i=l 1 (3.10) + / is a necessary and sufficient condition for the optimum power level to exist. Admitting sources according to (3.10) guarantees that their QoS requirements can be met. The power level of a source which is admitted is determined from (3.9). Imposing the maximum allowable transmit power level constraint, P* < Pi, in (3.9) yields another stricter condition N 1 f ^ 9 i < T i _ _ N ° W • Pi m m - L 9i (3.11) In [1], a source can be admitted as long as the total interference including all source activities in the current and adjacent cells does not exceed the background noise by I/77, i.e. (l + /)£/T + i W < - 5 — . (3.12) i=i ^ 3. Erlang Capacity with Multirate Traffic Sources 30 Substituting (3.7) in (3.12) yields N 1 £<*< 1 + / (3.13) For n > > 0 (3.14) 9i the condition in (3.13) is stricter than (3.10) or (3.11) and (3.13) ensures that the user QoS requirements are met. For convenience, the admission control test is written as f><A*A, (3.15) where A is the power budget available and represents the minimum value of the RHS of (3.10), (3.11), or (3.13) and p e [0,1] is a utilization factor that depends on the amount interference to other cells. Equation (3.15) represents the condition necessary for the fea-sibility of the power control. The Erlang capacity is defined as the average traffic load that can be supported so that the probability of violating (3.15) does not exceed 0.01. 3.3 Power Index Model A model which has been extensively adopted for bursty traffic is the Markov-Modulated Poisson Process (MMPP) [79-81]. A MMPP for source i is a stochastic process charac-terized by a non-negative-value X[Ji(t)], where Ji(t), t > 0 is the state of the underlying instate irreducible Markov process [82]. The arrival rates can take on only Kt values from the set {Ai A 2 . . . A^J. A MMPP has the following properties: a) it becomes a Poisson process if Xj = Xk Vj , k such that 1 < j, k < Kt and b) the superposition of N independent MMPP yields another MMPP with n j l i Ki states. To model different traffic sources with variable bit rate requirements, we use a Markov process for each source i. Each state represents a target power index value according 3. Erlang Capacity with Multirate Traffic Sources 31 Ll,2 2,1 112,3 v3,4 "3,2 Figure 3.1. Markov modulated power index process (MMPIP) representation of traffic source i. to (3.6) or (3.8). This results in a i^ -state continuous-time Markov process as shown in Fig. 3.1. We refers to this as a Markov Modulated Power Index Process (MMPIP). The A"i-state MMPIP for source i is characterized by a Ki x Ki infinitesimal generator Q i and a Ki x Ki diagonal power index matrix A i . For example, for Ki = 2 (i.e., source i has a two-state MMPIP), Q i and A i will have the form (3.16) Qi = , A i = 9i,i 0 T2,i —T2,i 0 92,i and the corresponding 1 x K steady state probability vector 7Ti is 1 K i Tl,i] 1 = 1,2,..:,N. (3.17) For clarity, we will use a transpose to denote column vectors. The superposition of N independent sources yields an MMPIP with m = YlfLi Ki states. By representing each state as Af-tuple (si, S2>•••, SN) a n d using a lexicographic ordering of states, the state space of this MMPIP can be conveniently described using the Kronecker product and sum of matrices [83]. For example, Table 3.1 shows the state space of the superimposed MMPIP for three traffic sources, each has a three-state MMPIP. In the table, each state is represented by the three-tuple (si, s2,s3) where Si, i = 1,2,3, represents the state of traffic source i. Each state has a power index value giy i = 1, 2 , . . . , m, which is equal to gsi,i+gs2,2 + 9s3,3-The Kronecker product, A ® B, of an (L x x Mi) matrix A and an (L2 x M 2 ) matrix B is an (LiL2 x M\M2) matrix with elements AjB. The Kronecker sum, A © B, of 3. Erlang Capacity with Multirate Traffic Sources 32 Table 3.1. The state space of the superimposed MMPIP for three traffic sources, each with a three-state MMPIP State Tuple State Tuple State Tuple 1 (1,1,1) 10 (2,1,1) 19 (3,1,1) 2 (1,1,2) 11 (2,1,2) 20 (3,1,2) 3 (1,1,3) 12 (2,1,3) 21 (3,1,3) 4 (1,2,1) 13 (2,2,1) 22 (3,2,1) 5 (1,2,2) 14 (2,2,2) 23 (3,2,2) 6 (1,2,3) 15 (2,2,3) 24 (3,2,3) 7 (1,3,1) 16 (2,3,1) 25 (3,3,1) 8 (1,3,2) 17 (2,3,2) 26 (3,3,2) 9 (1,3,2) 18 (2,3,2) 27 (3,3,2) an (L x L) matrix A and an (M x M) matrix B is an (LM x LM) matrix given by A © B = A ® I M + I Z , ® B where Ij is an (i x i) identity matrix. The superposition of N independent MMPIP's, each with K states and parameterized by (Qi, Ai), i = 1, 2,..., N, yields another MMPIP parameterized by its (Q, A) where Q = Qi©Q 2 ©.--eQiv, (3.18) A = Ai © A 2 ©... © Ajv = Diag(g1,g2,... ,gm). (3.19) The steady state probability vector 7r of the superimposed (Q, A) MMPIP can be ob-tained by solving TTQ = 0 7reT = 1 where e and 0 are the vectors of all ones and zeros respectively (3.20) The average power index, 3. Erlang Capacity with Multirate Traffic Sources 33 E[G], of the (Q, A) MMPIP is E[G] = 7rAeT = 7rgr, (3.21) where g = [gi g2 • • • gm]- The average power index, E[Gi], of source i is given by E[Gi] = 7riAieT. (3.22) Let J(t), t > 0 be the state of the superimposed m-state MMPIP at time t. Let 7rj(N)=]miP{J(t)=j}, j = l,2,...,m, (3.23) t—>oo be the steady state probability of state j when there are N traffic sources in the system. The outage probability with N sources is then given by Pout(A0 = £ ^ W (3.24) where F denotes the set of all states for which gt > i = 1, 2, . . . , m, (i.e., those states in the superimposed MMPIP corresponding to an outage). Assuming that the number of sources in the system changes slowly relative to the state residence times, the blocking probability, Pg, can be expressed as oo PB=J2 Pout(N)PN (3.25) N=0 where Pjv represents the probability of N sources in the system. The computation of Pout(N) can be time consuming when the number of states in the superimposed MMPIP is large. If the sources can be grouped into different service classes with all sources in the same class having the same transition rate and power index matrices, the computation time can be significantly reduced. We first consider a specific service class I consisting of A^; sources. We use an aggregation method to reduce the state space of the superimposed MMPIP. The original Unaggregated superimposed MMPIP (U-MMPIP) has kf' states where ki is the number of states of a source in class I. All states in the 3. Erlang Capacity with Multirate Traffic Sources 34 Table 3.2. The state space of the A-MMPIP and the corresponding states in the U-MMPIP. State A-MMPIP U-MMPIP 1 (1,1,1) (1,1,1) 2 (1,1,2) (1,1,2),(1,2,1),(2,1,1) 3 (1,1,3) (1,1,3),(1,3,1),(3,1,1) 4 (1,2,2) (1,2,2),(2,1,2),(2,2,1) 5 (1,2,3) (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) 6 (1,3,3) (1,3,3),(3,1,3),(3,3,1) 7 (2,2,2) (2,2,2) 8 (2,2,3) (2,2,3),(2,3,2),(3,2,2) 9 (2,3,3) (2,3,3),(3,2,3),(3,3,2) 10 (3,3,3) (3,3,3) superimposed U-MMPIP with the same aggregate power index value are represented by only one state in an Aggregated MMPIP (A-MMPIP). Consider the example in Table 3.1 for a service class I with three traffic sources, each modelled as a three-state MMPIP (i.e., Ni = 3, ki = 3). Table 3.2 shows the state space of the A-MMPIP and the corresponding states in the U-MMPIP. The set of six states {(1,2, 3), (1,3,2), (2,1,3) ,(2,3,1), (3,1, 2), (3, 2,1)} in the superimposed U-MMPIP have the same aggregate power index value because each one of them represents one source in state 1, one source in state 2, and one source in state 3 and is represented by only one state (1,2,3) in the A-MMPIP. Note that, each state in the A-MMPIP is a permutation of a group of corresponding states in the U-MMPIP and will be represented by the /c/-tuple (niti,n2ti, • • •, nkui) where rijj is the number of class I sources in state j and E^Li n^i = Ni. The steady state proba-bility of state (nij, n2>i,..., n-kiti) in the A-MMPIP is given by 3. Erlang Capacity with Multirate Traffic Sources 35 PNltl,N2tl,...,Nkhl(ni,i,n2:i,... ,nkl,i) -^ L I "1.1 "2,1 n T O ^1,1,1^2,1,1 •••7rk,,l,J> <-3-26) ni}i,n2>i,. . . ,nklii J where is the steady state probability of state j of source % from class / and the com-binatorial coefficient represents the number of states in the U-MMPIP corresponding to a state in the A-MMPIP. The total number of states in the A-MMPIP is given by Ni + k - 1 , (3.27) Ni For a system with w service classes, the total number of states in the A-MMPIP is n ( Nt -h ki - 1 (3.28) V and the steady state probabilities of states [(n^i, 72.2,1, • • •, n fci , i ) , ( n i ,2, ^2,2) • • • > nfc2,2)> • • • ,.("1 )] i s w II pNXMN2tl,...,Nkhl(nu, n 2 i i , n k a ) . (3.29) 2=1 The number of states in the U-MMPIP is reduced by a factor of ^ ( Ni + h - l 1=1 { Nt 1 ^—jj — (3.30) i=l where J2T=i N i = N -3. Erlang Capacity with Multirate Traffic Sources 36 3.4 Imperfect Power Control The analysis in previous section assumes a fixed received SIR for each source. In reality, it has been shown that the received SIR is a lognormally distributed random variable (r.v.) [1, 72]. This variation in the received SIR may be due to reasons such as shadow fading. The effect of this variation is to simply cause the power index value in each state of the MMPIP in Fig. 3.1 to be a r.v. while the transition rates are unchanged. The distribution function of the power indices in (3.6) and (3.8) needs to be computed in order to evaluate (3.23). Assuming that the received SIR, T, for a traffic source is log-normally distributed where Y is a Gaussian distributed r.v. (i.e., Y ~ Af(my,Oy) = Af\Bmx, f32o-2x) and (3 = ln(10)/10. For notational simplicity, the source index is not explicitly shown. The power index in (3.6) can be approximated as a lognormal r.v.. Using Wilkinson approxi-mation [84], the mean and variance of the power index in (3.6) are r = i o x / 1 0 = eY (3.31) a2g = e2mv+av(e°v - 1) (3.32) where \ l n ( l + £2 e-2/3m x+2/324 + 2iSe-/3mx+/32<4/2) 21n(l + 5 e - ^ + ^ / 2 ) l n ( l + S2e-2f3mx+2(}2ax + 2Se-<3mx+l}2axl2) 21n( l + Se-/3m*+'32'4/2). (3.33) The mean and variance of (3.8) are 3. Erlang Capacity with Multirate Traffic Sources 37 a? = l_eWmx+^<y\^l _ xy (3.34) 9 Cj2 For a source from class £ with /c/-state MMPIP, the sum of the i.i.d power index r.v. in the superimposed MMPIP for a number, n^ j, of sources in state j; 1 < j < h can be approximated using a Gaussian distributed r.v. (i.e., central limit theorem), that is Zjyi = njtigj ~ Af(njtimg,njtiol) I < j < h. (3.35) From (3.24) AT; iVi-fe Nt-(b+c) pUNi)^ E E - E 6=0 c=0 d=N(-(6+c) ^ V i . i , i v 2 i l jv f c £,,(wi,z, n2,i,nka)P(Zi > /iA) Ni Ni-b Nt-(b+c) = E E ••• E 6=0 c=0 d=JV,-(6+c) PNli,,N2,i,...,Nklti{ni,i,n2,i, • • • ,nkl,i)W\ / ,„s) ^JVariZi) where Zt = Zu + Z2,i + ... + Zka. (3.36) 3.5 Numerical Results and Discussion In this section, we present numerical results for a CDMA system with three different types of services, namely voice, video, and data users. The other-cell interference / factor can be 0 (for single cell) or 0.55 (for multiple cell). Table 3.3 summarizes the system param-eter values used including the transmission bit rate and the mean residence times for each service class. 3. Erlang Capacity with Multirate Traffic Sources 38 We used the admission criterion of (3.15). We consider both no self-interference (i.e., (3.6)) and self-interference (i.e., (3.8)). The results obtained using the proposed method is compared to those from the conventional method in which only one transmission bit rate (the average source bit rate) is used for each traffic source [15,16,75]. We consider both homogeneous system with a single service class and heterogeneous system that have multiple service classes. PB is calculated from (3.25) for both perfect and imperfect power control assuming P^ is a Poisson (i.e., assuming M/M/oo queueing model [72]). Figs. 3.2, 3.4, and 3.6 show the blocking probability for voice, video, and data sources respectively in a homogeneous system when / = 0. The outage probability (i.e., Pout{N)) in the conventional method for a given number of sources is either zero or one since there is a fixed power index value for each source. However, the outage probability, Pout{N), calculated from the MMPIP will typically take a value in (0,1). For low traffic values, the conventional method yields overly optimistic results since the number of sources tends to be small and hence Pout(N) for the conventional method is zero. The threshold value, Nth, of n that causes Pout{N) to change its value from 0 to 1 increases as the power budget increases or the power index (equivalently the transmission bit rate) decreases. The higher the value of Nth, the bigger is the difference in the blocking probability values calculated using the conventional and MMPIP methods. For video sources, the difference in blocking probability values obtained from the two methods is smaller since Nth is smaller. Figs. 3.3, 3.5, and 3.7 show the blocking probability for voice, video, and data sources respectively when / = 0.55 where the other-cell interference effect decreases the power budget and hence increases the blocking probability than in case when / = 0 for the same number of sources. The effect of self-interference always results in higher blocking probability since it demands higher power index value. Figs. 3.8 and 3.9 show PB when the system has heterogeneous traffic sources for / = 0 and / = 0.55 respectively. In this Figures, Pout(N) is the average outage probability for all possible combinations of the number of sources in each type of service (i.e., for N = 3, -Pout (3) is the average value of that when there is 1 voice, 1 video, 1 data source or 3 voice 3. Erlang Capacity with Multirate Traffic Sources 39 Table 3.3. Parameter values for an integrated voice/video/data cellular DS/CDMA net-work [1,2]. Chip rate (W) Noise power spectral density (N0/2) Other-cell interference ratio (/) MS maximum transmit Power (P) Utilization factor (/J,) Background-to-total-interference ratio (rj) 1.2288 Mbps 10-8W/Hz 0 (single cell) or 0.55 (multiple cell) 2W 1 0.1 Voice service parameters BER requirement (^) Standard deviation (a) Transmission bit rate in states 1, 2, and 3 (Ri, R2, R3) Mean residence time in states 1, 2, and 3 (TI, T2, T3) Video service parameters BERreqmrementA Standard deviation (cr) Transmission bit rate in states 1, 2, and 3 (Ri,R2, R3) Mean residence time in states 1, 2, and 3 (TI, T2, T3) Data service parameters BER requirement (^) Standard deviation (a) Transmission bit rate in states 1 and 2 (Ri, R2) Mean residence time in states 1 and 2 (TI, T2) 7dB 2.5 dB 0 Kbps, 32 Kbps, 8 Kbps 1.35 s, 1 s, 0.1 s 8dB 2.5 dB 8 Kbps, 88 Kbps, 16 Kbps 0.25 s, 0.5 s, 0.25 s 9dB 2.5 dB 0 Kbps, 38.4 Kbps 1 s, 0.1 s sources or 3 video sources, etc.). It can be seen that for heterogeneous sources, Pb is higher than that for voice and data sources only since it experiences the existence of video sources. Figs. 3.10, 3.12, 3.14 show Pb for voice, video, and data sources respectively with / = 0 and imperfect power control. Due to imperfection in power control, Pg is higher than that of the perfect power control case. 3. Erlang Capacity with Multirate Traffic Sources 40 3.6 Summary The growing demand for multimedia applications with different QoS requirements, such as target BER or transmission bit rate, in current and next generation wireless networks requires a unified analytical framework that is able to capture the wide variations in trans-mission bit rate requirements and provides accurate calculation of the system capacity. In this Chapter, an analytical approach was presented for evaluating the Erlang capacity of a CDMA system with heterogeneous traffic sources. In this method, each traffic source is represented by a MMPIP that characterizes its variable transmission bit rates and target BER. A comparison of the results obtained using the conventional and MMPIP methods showed that the conventional method yields overly optimistic results since it assumes a single transmission bit rate for each source . The model proposed in this paper for Erlang capacity is useful in other directions. For example, video traffic sources have highly variable transmission bit rates which depend on the coding algorithm or the scene content [77,85]. The effect of such variability can be readily studied using the proposed approach. 3. Erlang Capacity with Multirate Traffic Sources 41 Figure 3.2. Blocking probability versus offered voice traffic under perfect power control when / = 0. Figure 3.3. Blocking probability versus offered voice traffic under perfect power control when f = 0.55. 3. Erlang Capacity with Multirate Traffic Sources 42 XT ' . J I . •»• No self-interference -O- Self-interference 1 1.5 2 2.5 3 3.5 Video traffic in Erlangs 4,5 5 Figure 3.4. Blocking probability versus offered video traffic under perfect power control when f = 0. • *• No self-interference -O- Self-interference 2.5 3 3.: Video traffic in Erlangs Figure 3.5. Blocking probability versus offered video traffic under perfect power control when f = 0.55. 3. Erlang Capacity with Multirate Traffic Sources 43 8 10 1 1 1 1 1 1 1 1 1 > 3 - - : r ; -\ ,-\ . . , - r . S MMPIP A-K \ : Conv. : : : / y * •-» - No self-interference - O - Self-interference 10 12 14 16 18 20 22 Data traffic in Erlangs 24 26 28 30 Figure 3.6. Blocking probability versus offered data traffic under perfect power control when f = 0. - * - No self-interference - O - Self-interference Data traffic in Erlangs Figure 3.7. Blocking probability versus offered data traffic under perfect power control when f = 0.55. 3. Erlang Capacity with Multirate Traffic Sources 44 10"' I : : : : : MMPIP : iiiiiiiiiiiiiiiiiiiifcHHrt !::::::::;^&:T:::::::X:: . . . . . . .1. . . . . . . . . . . . 1 ; . - . . - f i r . , T - < ilS:::::':-''::;:::::::::::: Conv. r -1 1 ! No self-interference - O - Self-interference 1 1.5 2 2.5 3 3.5 4 4.5 5 Traffic in Erlangs Figure 3.8. Blocking probability versus offered traffic under perfect power control when / = o. 10" 1 I I I 1 1 1 : : — ' r:. f..' , . .• jjf. : : MMPIP / \ V>;;;:;;ja .^:::^ :;;\;;;;;:::;: ; ; > ' ' : * ' : Conv. . - / . . • . • • / . • ' • i i i i i • +• No self-interference - O - Self-interference * I I I I I ' I I ] l 1 1,5 2 2.5 3 3.5 4 4.5 5 Traffic in Erlangs Figure 3.9. Blocking probability versus offered traffic under perfect power control when f = 0.55. 3. Erlang Capacity with Multirate Traffic Sources 45 10° feTTT":;;;i':77^;;;;;;;;;;; \;;;;;;:;;- 'T;~TT';i;;:ill!• • i•;P. c i- • '•' • • ;:::::::::::;::::::::::::;::::::::::::;:::::::::::;::::::::::: 10"«-• " \ ; *• No self-interference '. ! - O - Self-interference 1 0 -H • 1 1 1 . ' • ' ! 2 3 4 5 6 7 8 9 10 Voice traffic in Erlangs Figure 3.10. Blocking probability versus offered voice traffic under imperfect power con-trol when f = 0. 10° y.: -.j •••• i. i : : : : ! : : ; • : ; ; : : : : h ;::::::::: ; ': - #- No self-interference : : : : : - O - Self-interference 'I i I I I I 1 i I . . : 2 3 4 5 6 7 8 9 10 Voice traffic in Erlangs Figure 3.11. Blocking probability versus offered voice traffic under imperfect power con-trol when f = 0.55. 3. Erlang Capacity with Multirate Traffic Sources 46 10° --"1 r t •• i i i I \ ^ r" J • ••"A : MMPIP Conv. • -* -c • No self-interference >- Self-interference 1 1.5 2 2.5 ' 3 3.5 4 4.5 5 Video traffic in Erlangs Figure 3.12. Blocking probability versus offered video traffic under imperfect power con-trol when f = 0. Figure 3.13. Blocking probability versus offered video traffic under imperfect power con-trol when / = 0.55. . . . 3. Erlang Capacity with Multirate Traffic Sources 47 8 10" .1*:::?:: • •*• No self-interference -O- Serf-interference •+• data 1 -O- data 2 10 12 14 16 18 20 22 Data traffic in Erlangs 24 26 28 30 Figure 3.14. Blocking probability versus offered data traffic under imperfect power con-trol when f — 0. 10° mrnmmwm m ^ M s . ii*? - -Q- — : : i: :::::::::::::::::::::: :: .^••.-['•'•'•'•* MMPIP :::::: yyyyyy^:iyy c o n vyy" :::::::::::::::: i : . r : : ;;;; / " . ' ' r = m milhl!!!!!!!!! ; ' . ' . ' . ' . ' . ' . y . y . . . I -; \t. \ \ i ;; a 111 • ;: /. ;*::::::::::::::::::::;::::::::: •/•;-' :•; ::i::::;:;::::::!i;:::i:::n ••*• No self-interference -O- Self-interference 1 0 ^i 1 1 ' I 5 10 15 20 25 Data traffic in Erlangs Figure 3.15. Blocking probability versus offered data traffic under imperfect power con-trol when f = 0.55. 3. Erlang Capacity with Multirate Traffic Sources 48 . -o- * . .-or.: - 0 • -*• No self-interference -O- Self-interference 1 1.5 2 2.5 Traffic in Erlangs Figure 3.16. Blocking probability versus offered traffic under imperfect power control when f = 0. • +• No self-inl erf ere nee -O- Self-interference 1 1.5 Traffic in Erlangs Figure 3.17. Blocking Probability versus offered traffic under imperfect power control when f = 0.55. 4. A Transmission Rate Scheduling Scheme 49 C h a p t e r 4 A T r a n s m i s s i o n Rate S c h e d u l i n g Scheme for M u l t i m e d i a Services i n Di f ferent iated Services N e t w o r k s 4.1 Introduction Recent work in wireless communications has focused on the support of multimedia ap-plications such as voice, video, and image and data file transfer. It is expected that in next-generation wireless systems, many applications wil l require that different Quality of Service (QoS) requirements be met. Current second-generation systems, such as IS-95 and Global System for Mobile communications (GSM), are tailored for voice communication and may not meet the different QoS requirements for multimedia applications. The design of a scheduling scheme that enables sharing the air interface among multimedia applica-tions with diverse QoS requirements is a challenging task because it typically involves a number of conflicting factors which must be analyzed and weighted. What is needed is an efficient and flexible scheduling scheme that can easily adapt to the changing conditions and QoS requirements of the projected multimedia traffic in wireless networks. Common QoS parameters are Packet Transfer Delay (PTD), Packet Delay Variation (i.e., jitter) (PDV), or Packet Loss Rate (PLR). For non real time-Variable Bit Rate (nrt-VBR) , Available Bit Rate (ABR), and Unspecified Bit Rate (UBR) traffic, P L R is the most 4. A Transmission Rate Scheduling Scheme 50 important QoS parameter. PLR, PDV, and PTD are relevant parameters for both Con-stant Bit Rate (CBR) and real t ime-VBR (rt-VBR) traffic. A different approach for QoS assurance is based on the relative differentiated services model [8,14]. In this model, ap-plications do not get an absolute service level assurance but the network assures that higher classes wil l be offered better service than lower classes. One approach to achieve relative differentiated services is the proportional differentiated services model [7,13]. Accord-ing to this model, the network traffic is grouped into N service classes which are ordered, such that class i enjoys a better (or at least no worse) service level than Class (i — 1) for 1 < i < N. A controllable QoS differentiation parameter is selected by the network op-erator so that the service levels for the different service classes bear fixed ratios to each other. Such a differentiation parameter allows the network operator to tune the QoS ratios between classes independent of the class load. Several service disciplines have been proposed in the literature for Code Division M u l -tiple Access (CDMA) networks (e.g., [70,71,86]). In these disciplines, different criteria such as minimization of packet loss rate or maximization of throughput are used in order to design an efficient service discipline. These criteria are applied to provide an overall target performance measure but individual QoS parameter guarantees for service classes are not considered. In this Chapter, we propose a transmission rate scheduling scheme that the Base Station (BS)/Access Point (AP) can use for multiplexing different traffic classes over the air interface of a power controlled C D M A network. This scheme provides absolute QoS guarantees for each service class in terms of average packet queueing delay, packet transfer delay, packet delay variation (jitter), and packet loss rate. The scheme can also provide proportional differentiated service based on average delay, packet loss rate, and power index. The admission policy for the scheme is given. Since channel bandwidth is the most scarce and precious resource in a wireless environment, we propose an optimal rate allocation scheme that maximizes the sum of the transmission bit rates of all Mobile Station (MSs) while ensuring the stability of packet queues and meeting the power budget. 4. A Transmission Rate Scheduling Scheme 51 4.2 System Model We consider a Direct-Sequence DS/CDMA cellular network with a total number, N, of service classes. Each class represents a number of sessions that are either from the same M S or distributed among different MSs. Sessions that belong to the same service class are assumed to have the same QoS requirements. The scheduling scheme is depicted in Fig. 4.1. As shown in Fig. 4.1, each service class is represented by a separate M/D/l queue that accommodates packets from a number, rm, of sessions belonging to class i. Let Aj j denote the arrival rate (in packets per second) for session j of class i. The class i queue is serviced at a rate of Ri packets per second. The arrival rate and packet size for each session, j, belonging to the same class, i, are assumed to be identical (i.e., Xij — Xi/m). It is assumed that all queues are stable, i.e., the utilization pt — Xi/Ri of queue i server is less than 1. Different representations of the classes at the MSs are possible: • Scenario 1: (Fig. 4.1 (a)): This is the simplest scenario in which each M S has only one session. Each session belongs to a different service class and hence each service class queue is located at a different M S . • Scenario 2: (Fig. 4.1 (b)): Each class i has a number, rm, of sessions. Each M S can have one or more sessions from the same or different classes. Each session has its own channel (e.g., different spreading code). • Scenario 3: (Fig. 4.1 (c))\ A l l sessions in the same class share the same channel (e.g., same spreading code). It is assumed that there is an entity that coordinates the packet transmissions from each session. As an example, the entity could assign packet transmission to each session in a round robin fashion. 4. A Transmission Rate Scheduling Scheme 52 m, sessions of class i K Session 1 queue CDMA Channel C D M A Channel Session 2 queue Class 1 queue Class 2 queue Class N queue Session m. queue (b) m, sessions of class i (a) (c) Figure 4.1. 77ie proposed transmission rate scheduling scheme. 4.3 Transmission Rate Scheduling Scheme 4.3.1 Power Control In this section, we provide the condition that guarantees the bit error rate (BER) (or SIR) and transmission bit rate QoS requirements for each session (or class) while minimizing the total transmit power. Each session j in class i has instantaneous received power of Pij, spreading gain dj = WjRij where W is the spread bandwidth and Rij is the transmission bit rate, and a BER requirement specified by the minimum tolerable SIR Tij. The additive background noise is assumed to have a power spectral density (PSD) N0/2. It is suggested 4. A Transmission Rate Scheduling Scheme 53 in [1] that a session can be admitted as long as the total interference PSD introduced by all sessions in the current cell and in adjacent cells does not exceed the background noise by a factor of I/77 = 10. As a result, the BER and transmission bit rate QoS constraint stated in terms of Rij and T^- is satisfied at any given time if (i.e., (3.15)) JV mi E E f c < ( i ^ ) , (4.D i=i i=i where gitj is the power index [69] of session j belonging to class i and is defined as 9ij = 1 . 1 w ~ i = 1,2,...,JV; ^ = 1,2,...,^. (4.2) For Scenarios 1 and 3, the power index, gi, of class i is 1 1+" 9i = , , Vz = l,2,...,iV. (4.3) However, for Scenario 2, the class z power index, gt, is # = mi, . lw ~ = 1 / w . V i = !. 2.'- •:• >'W- (4.4) The optimum power level for each session j that belong to class i is given by • Pij= ^ " f f i • » = l,2,...,iV; 7 = 1,2,...,^. (4.5) For convenience, the admission control test is written as JV J29i<Kl~v), (4-6) 1=1 where g^ is the power index of class i and p G [0,1] is a utilization factor that depends on the interference to other cells. 4. A Transmission Rate Scheduling Scheme 54 4.3.2 M / D / l Queueing Model The average packet delay, A, for an M/D/l queue i with service rate Ri and utilization Pi is given by [87] In some applications, a packet is dropped from its queue if its waiting time exceeds its timeout specification. To calculate the packet drop (or loss) rate, Piti, due to excessive waiting time in a queue i, we use an M/D/l model with impatient customers [88]. In this model, an arriving packet joins its queue i and waits for a maximum amount of time T; for service. If the waiting time exceeds ri5 the packet is dropped. Ptii is approximately given by [88] where eSi/Ri = 1 + 5i/\u & = (1 - pi){5i/Ri - (1 - #)} \ oa = pi - and A = a{ {\i/(2R2i(l - p^) - ii/di}"1. The average packet queueing delay, A.itji), for transmitted packets is given by [88] (1 - pi)(aj exp(-/3jTi) + ^exp(-<5iri)) 1 - pi(cti exp(-PiTi) + & exp(-5iri)) (4.8) where is the average packet queueing delay for both transmitted and dropped packets and is given by Di(Ti) = [cti/f3i - ai{l/Pi + piTi} exp(-PiTi) + ~ ii{\/b% + PiTi}exp(-5iTi)] x [1 - pi(cti exp(-PiTi) + & exp(-<5;T;))]_ - l (4.10) It is shown in [88] that for large values of Tj, 4. A Transmission Rate Scheduling Scheme 55 P^in) ~ (l-p i)^exp(-r I<5 I). . . (4.11) 4.3.3 QoS Performance Measures The performance measures used here for each service class are: Average Packet queueing Delay (APD), PLR, PDV, and PTD. The PDV1, Vu for a class i is defined as the smallest value of Wi such that P(waiting time in queue i > wi) < ti. (4.12) where ti is typically << 1. For an M/D/l queue with infinitely patient customers, Vi can be calculated as [89] IViiVI > 4 i - l , (4-13) where A{ = - log^)^ + log(l - pi)hi - log(pie7i - l)/ji and e7i = 1 + ii/Pi- The PTD, Ti, of a queue i is defined as Ti = Vi + 1/Ri. (4.14) 4.4 Session Admission Control Rule In this section, we provide a session admission control rule to meet absolute QoS guarantees (i.e., APD, PLR, PDV, or PTD) or relative QoS guarantees (i.e., proportional DS). 4.4.1 Absolute QoS Admission Control Rule When an MS requests a new class i session, the current arrival rate, Aj, of class i is increased by the arrival rate of the new session. Depending on the specific QoS target for class i, the XPDV is the difference between the maximum and minimum packet delays. 4. A Transmission Rate Scheduling Scheme 56 service rate required to satisfy it can be calculated using (4.7), (4.8), (4.13), or (4.14). For service classes that require multiple QoS targets (i.e., a combination of APD, PLR, PDV, and PTD), the service rate is chosen such that the most stringent requirement is satisfied. If the inclusion of this new service rate results in a class i power index value, g,, which still satisfies (4.6), the new session is admitted. Otherwise, it is rejected and the class i arrival rate is restored to its original value. 4.4.2 Relative QoS Admission Control Rule When an MS requests a new class i session, the current arrival rate, A,, of class i is increased by the arrival rate of the new session. The service rate, Ri, of this class i is chosen such that Ri > Aj. The service rates of all other classes are calculated so that the target relative QoS measure is met. If the inclusion of these new service rates still satisfies (4.6), the new session is admitted. Otherwise, it is rejected and the class i arrival rate is restored to its original value. 4.5 Maximizing Transmission Rates One of the main objectives in wireless network design is to maximize transmission rates. This can be stated as the following optimization problem: N max Y,1^ (4-15) P i - j i=i subject to the constraint in (4.6). Due to the constraint in (4.6), the optimal solution will allocate a nonzero rate to only one user (with the lowest SIR ratio). In order to ensure the stability of the N queues (corresponding to the N service classes), the constraint - ? -< i V i e { i , 2 , . . . , i V } , (4.16) 4. A Transmission Rate Scheduling Scheme 57 is added to the above optimization problem. For convenience, we will refer to this new optimization problem as problem (PI). Different QoS targets can be included in problem (PI) by adding additional corresponding constraints. 4.6 Rate Guarantee and Credits Errors occur quite frequently in the wireless environment. A compensation mechanism is needed in order to have a per-session rate guarantee for non real time delay-insensitive sessions (e.g., data). This compensation may not be needed for real-time sessions such as CBR (e.g., voice) and rt-VBR (e.g., video) since the packets of these applications will be dropped once their waiting times exceed a certain threshold. However, for non real time applications that can tolerate large delay bounds and require a guaranteed throughput, it is necessary to have a compensation to achieve long-term throughput fairness among those sessions that experience error-prone channels, i.e., gd = lim VsGA, (4.17) n k=i where A is the set of all sessions in a class, gP(k) and gds are the power indices of session s at the fcth time slot in the bad (i.e., error-prone) and good (i.e., error-free) channel respectively (s represents session j of class i). It is assumed that time is divided into slots of fixed duration. Channel state monitoring and prediction for all sessions is done at the beginning of each time slot and sessions that perceive good channels are allowed to transmit. At the beginning of each time slot, a session s is allocated a power index value according to gP(k) = I Y.jZB*9j i € A (4.18) 0 otherwise, where Bd is the set of backlogged sessions with good channels. In order to provide fairness, there is a credit/debit mechanism. That is, associated with each session s is a credit counter, 4. A Transmission Rate Scheduling Scheme 58 Ca(k), that indicates by how much the sum of the allocated power indices in all previous slots of a session is lagging relative to that assuming a good channel model at the fcth time slot, that is > 0 if session s is lagging Cs{k) I = 0 if session s is in-sync < 0 if session s is leading. At any time, the following holds, (4.19) £C(*) = o. (4.20) To allow for a graceful power index degradation (i.e., to prevent a session that have been in a bad state for a long time from hogging the channel once it becomes error-free again), a lagging session s receives a power index compensation of 5a from leading sessions, 5s = vmm(J29Ps(k),ECs(k))> ( 4 - 2 1 ) seD s€C where C, D are the set of error-free backlogged sessions with credit and debit respectively and v (0 < v < 1) is a graceful power index degradation parameter. The power index ga(k) of each session s is updated according to 9Ps(k) + 9Ps(k) 6sgds Sj G c 9j ' HjeD 9j ' Vs G C Vs € D. (4.22) The credit/debit counter of a session s is updated according to Cs(k) = Cs(k) + (gds - tf'k)), Vs E B, (4.23) where B is the set of backlogged sessions. When a session j with Cj(k) > 0 at the fcth time slot becomes unbacklogged, its Cj(k) value is redistributed back among the leading sessions, that is 4. A Transmission Rate Scheduling Scheme 59 ca(k) = c8(k) + cj{k)^ V / , . v V s e ^ ( 4 - 2 4 ) Ca(fc) Hie/Ci(fc) where Z is the set of sessions with debit. 4.7 Simulation Results Simulation results were obtained in this section to show both absolute and relative QoS guarantees in the proposed scheduling scheme. For all simulation points plotted, the 95% confidence intervals are within ±3% of the values shown. We consider three different ser-vice classes, each generating traffic according to a Poisson process (i.e., packet interarrival times are assumed to be independent, exponentially distributed random variables). We as-sume a chip rate W = 4.096 Mcps, a power budget (1 — if) = 0.9, and utilization factor p = 1. Channel utilization (U) is defined as the ratio of the aggregate power indices value to the available power budget. For simplicity, we assume Scenario 1. Example 4.1 (Absolute QoS) Table 4.1 shows the characteristics of the three service classes in terms of arrival rates (packets per second), minimum acceptable SIRs, and packet expiry times. Table 4.2 (a) shows the target QoS measures of the three classes in terms of APD, PLR, PDV, and PTD. The transmission bit rates (packets per second) required for meeting each of the QoS tar-gets for the three service classes are shown in Table 4.2 (b). These transmission rates are calculated from (4.7), (4.8), (4.13), and (4.14) respectively where e< = I O - 9 . Table 4.2 (c) shows the simulation QoS results when the corresponding transmission rates in Table 4.2 Ob) are used. We can see that simulation QoS values are close to the target values. 4. A Transmission Rate Scheduling Scheme 60 Table 4.1. Characteristics of the three service classes. i A* I\ (dB) n (s) 1 48 7 .06 2 240 8 .3 3 192 9 6 Table 4.2. (a) target QoS values, (b) required transmission bit rates, and (c) simulation QoS results for the three service classes in Table 4.1. ••_ i A,i(rO (s) K(s) Ti(s) 1 0.04 i o - 3 0.05 0.06 2 0.2 ' 10~6 0.25 , 0.3 3 5 IO"12 5.5 6 (a) 1 58.29 87.31 179.45 171.54 2 242.47 258.09 282.8 276.46 3 192.1 193.91 194.08 193.91 (b) 1 0.041 10~3 0.048 0.057 2 0.21 0 0.23 0.28 3 5.14 0 5.3 5.8 (c) Example 4.2 (Relative average delay QoS) We consider the same three service classes in Table 4.1 but with no packet expiry timeout. The proportional DS target is to achieve average delay ratios of D\ : _D2 : D3 — 1 : 2 : 3 4. A Transmission Rate Scheduling Scheme 61 i i * i i 0.2 0.4 0.6 0.8 Fraction of Class-1 Traffic (o) Figure 4.2. Average packet delay, average packet delay ratio, and channel utilization for three service classes. among the three classes while maximizing channel utilization. In the simulation, we solved the optimization problem (PI) with the additional constraint D\ : D2 : D3 = 1 : 2 : 3. Fig. 4.2 shows the average packet delay, average packet delay ratio, and channel utilization for the three classes as a function of the fraction of class-1 traffic (i.e., A i / ( A i + \ 2 + A 3 ) ) which is varied by changing A i while keeping \ 2 and A 3 fixed. Fig. 4.2 (a) shows that the average delays for all classes increase with the class-1 load. This increase in average delays of all classes is a result of maintaining the target average delay ratios within the power budget constraint given by (4.6). The analysis and simulation results agree closely. Fig. 4.2 (b) shows that the target average delay ratios are met regardless of class-1 load variation. Fig. 4.2 (c) shows that a channel utilization of 100% is achieved. Fig. 4.3 shows the pseudo code algorithm used for solving problem (PI) with the additional average delay ratio constraint for two sessions i and j. Example 4.3 (Relative PLR QoS) Fraction of Ciass-1 Traffic Fraction of Class-1 Traffic (a) (b) 4. A T r a n s m i s s i o n R a t e S c h e d u l i n g S c h e m e 62 /*Calculate two transmission rates Ri and Rj for two classes i and j such that their relative average delay ratio . D , : Dj = ai : aj is met */ S o l v e _ P l ( ) { error_factor = 0 . 0 1 ; sum = 0 ; A = — 77); select Ri such that Ri > Ajj w h i l e (| A — sum I > error .factor) { calculate Rj from A : Dj = ai : otj\ sum = gi + gy, Ri = Ri* (A/sum); } /*while*/ } F i g u r e 4.3. Pseudo code algorithm for solving problem (PI) with the additional relative QoS measure constraint. In order to achieve proportional DS in terms of packet loss rates due to excessive waiting time, we consider three service classes with arrival rates of 720, and 820 (packets per second) for class 2 and 3 respectively, corresponding packet expiry timeout values of 0.01 s, 0.04 s, and 0.04 s for the three classes, minimum acceptable SIRs of 7 dB, 8 dB, and 9 dB respectively, and infinite buffer size. The target is to maintain PLR ratios of P ; i : Pz>2 : P/3 = 1:2:3 while maximizing channel utilization. In the simulation, we solved the optimization problem ( P I ) with the additional constraint P^i : P/,2 : P/,3 = 1:2:3 where Piti is calculated from the two approximations in (4.8) (Approxl) and (4.11) (Approx2). Packet loss rates, P / ^ T j ) , i = 1, 2,3, as a function of the fraction of class-1 traffic is shown in Fig. 4.4. Fig. 4.4 shows that the analysis and simulation results agree closely. Fig. 4.5 (a) 4. A Transmission Rate Scheduling Scheme 63 1 0-'°l 1 1 1 1 1 L__ _J 1 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 Fraction of Class-1 Traffic Figure 4.4. Packet loss rates due to excessive waiting time for the three service classes versus the fraction of class-1 traffic. shows that the target PLR ratios are met regardless of class-1 load variation. In addition, Fig. 4.5 (b) shows that a channel utilization of 100% is achieved. Example 4.4 (Relative power index QoS) Another possible proportional DS target is in terms of power indices. We consider the same three service classes in Table 4.1 but with no packet expiry timeout. The target here is to maintain power index ratios of g\ : g2 : gs = 1 : 2 : 3 among the three classes while maximizing channel utilization. Fig. 4.6 shows the average packet delays of the three classes when class-1 load varies. The results are compared to the average delay obtained from (4.7). Fig. 4.6 (a) shows that the average delay of class-1 increases while the average delays for both class-1 and class-2 are almost constant (Fig. 4.6 (b) and (c)). Thus, service differentiation based on the power index provides isolation. In this case, problem (PI) is solved with the additional constraint gi : g2 : gs = 1 : 2 : 3. Fig. 4.7 (a) and (b) show that the target power index ratios are met and at the same time a maximum channel utilization of 100% is achieved. 4. A Transmission Rate Scheduling Scheme 64 1 1 1 Class-2/Class-1 - Class-3/Class-1 : 1 i < 0.2 0.3 0.4 Fraction of Class-1 Traffic (a) 0.2 0.3 0.4 Fraction of Class-1 Traffic (b) Figure 4.5. Packet loss rate ratio due to excessive waiting time and channel utilization for the three service classes versus the fraction of class-1 traffic. Example 4.5 (Compensation mechanism) To illustrate how the compensation mechanism operates in an error-prone environment, we assume three classes with the same reserved power index value of 0.3. Class-1 and Class-2 enjoy error-free channels at all times while Class-3 experiences an error-prone channel in a time window [0,15]. Figures 4.8 and 4.9 show the power index value allocated to each class at different time slots when v — 1 and v = 0.5 respectively. It can be seen that due to the compensation mechanism, class-3 receives power index compensation when it becomes error-free and is able to catch up with the other two classes. 4.8 Summary Multimedia applications (e.g., CBR, rt-VBR, nrt-VBR, ABR, and UBR) with diverse QoS requirements will be common factor in next-generation broadband wireless networks. One 4. A Transmission Rate Scheduling Scheme 65 ,i 1 i 1 0 0.2 0.4 0.6 Fraction of Class-1 Traffic (c) Figure 4.6. Average packet delay for the three service classes versus the fraction of class-1 traffic. of the major technical challenges in the provision of QoS in wireless CDMA network is the design of a scheduling scheme that enables sharing of the limited radio spectrum among the different applications while meeting their QoS targets and maintaining high resource efficiency. In this Chapter, we proposed a scheduling scheme for multiplexing multimedia traffic over the air interface of a power controlled CDMA system. The scheduling scheme is able to achieve absolute QoS guarantees in terms of APD, PLR, PDV, and PTD. We also applied the general model of relative differentiated services in the context of average packet delay, packet loss rate, and power index. This allows the network operator to vary the QoS guarantees for different classes based on pricing or policy objectives. An optimal rate allocation scheme was described that aims to maximize the sum of transmission rates of all MSs subject to the power budget and packet queue stability constraints. A compensation mechanism is used for non real time applications that provides rate guarantees for different 4. A Transmission Rate Scheduling Scheme 66 2.5 — Class-2/Class-1 •-• Class-3/Class-1 0.2 0.3 0.4 0.5 0.6 Fraction of Class-1 Traffic (a) o 0.8 0.2 0.3 0.4 0.5 0.6 Fraction of Class-1 Traffic (b) Figure 4.7. Power index ratio and channel utilization for the three service classes versus the fraction of class-1 traffic. sessions in error-prone environments. Although we assumed a class-based configuration (i.e., Fig. 4.1 (a)), a session-based configuration is also possible in situations with unequal arrival/service rates for sessions in the same class. The proposed scheduling scheme can be readily adapted to the emerging DS Inter-net by combining with some traffic conditioning scheme at the MSs. In fact, the concept here is in line with the proposed Assured Forwarding (AF) Per-Hop Behavior for DS Inter-net [10]. The BS/AP functioning as an ingress node to the wireline network, and integrating the admission policy with the scheduling scheme, can use the ECN (Explicit Congestion Notification) [90] information from downstream routers for controlling different session transmissions. The proposed scheme can also be adapted as the scheduling scheme for the third-generation W-CDMA that enables variable transmission bit rates through code hopping or Orthogonal Variable Spreading Factor (OVSF) [91]. 4. A Transmission Rate Scheduling Scheme 67 s • Class-1 o C l a s s - 2 x C l a s s - 3 o e s 9 ( 3 0 s © © < 5 0 0 0 O C 5 i b ® ® ® ® G 9 ® ® ® ® d ® ® ® ® 0 QI n i J, H H u I, ^ / i O O O O O O 0 1 1 1 0 5 10 15 20 25 30 35 40 Time slot no. Figure 4.8. Graceful power index degradation when v = 1. 0.1 • C la O C la x C la »s-1 , s -2 , s -3 < X X X -X 0 0 O 0 C 5 O 0 O O C 3 O 0 0 0 C 3 X X >® ® ® ® C 0 5 O O O 0 O O O O 0 C 3 O 0 0 0 QI H M K X A X K X K A X K X K A I I I I 1 1 0 5 10 15 20 25 30 35 40 45 Time slot no. Figure 4.9. Graceful power index degradation when v — 0 .5. 5. A Load-based Transmission Rate Assignment Scheme 68 C h a p t e r 5 A L o a d - b a s e d T r a n s m i s s i o n R a t e A s s i g n m e n t S c h e m e f o r a n I n t e g r a t e d V o i c e / D a t a S e r v i c e s 5.1 Introduction It is necessary to use wireless resources in an efficient manner while supporting a reason-able Quality of Service (QoS) level for the packets of data services (e.g., Web browsing, ftp, Email) in a Code Division Multiple Access (CDMA) system. Various rate assignment1 schemes have been proposed for the transmission of voice and data services on the uplink of Direct Sequence CDMA (DS/CDMA) cellular communication systems. The scheme proposed in [16] attempts to maximize the throughput for data services by using time-multiplexing and allowing only one data user to access the channel at a time. In [15], a rate-based grouping transmission (RGT) scheme is proposed which divides all data users into two groups according to their transmission bit rates. It is shown that the RGT scheme pro-vides a throughput gain over the conventional traffic-based grouping transmission (TGT) scheme as used in an IS-95 cellular system. The schemes in [16] and [15] focus on enhanc-ing throughput and do not consider possible traffic load differences among data sessions. Packet transfer delay, defined as the time between the arrival of a packet and its com-1The words "Assignment" and "Scheduling" are used interchangeably. 5. A Load-based Transmission Rate Assignment Scheme 69 plete reception at the receiver, is a commonly used measure of performance for data ses-sions. In this Chapter, a load-based transmission rate scheduling (LTR) scheme is proposed which assigns a transmission rate to each data session according to its load so as to mini-mize the overall average packet delay, while satisfying QoS and queue stability constraints. The LTR scheme is shown to provide significantly lower average delays than the TGT or RGT schemes when the data session loads are different. 5.2 System Model We consider the uplink in a DS/CDMA system with a spread bandwidth of W that supports voice and data services. Each voice session has a reserved talkspurt transmission rate of Ru packets per second. Each data session is represented as an M/D/l queue as illustrated in Figure 5.1. Data packets are of fixed length and arrive at the session i queue according to a Poisson process with rate A; packets per second. Packets from the session i queue are transmitted at a rate of Rd,% packets per second. Let Nv and denote the number of voice and data sessions in the system. Voice and data session QoS targets are specified in terms of minimum acceptable signal-to-interference ratio values, denoted by jv and jd respectively. Following (3.15) and assuming that data sessions transmit all the time, the QoS constraints can be translated into Nd -, £ w <A-AV, (5.1) where A < 1 is a parameter which depends on individual data session power constraints, out-of-cell interference, etc. In (5.1), A „ = N v w where av is the voice activity factor. 5.3 Transmission Rate Optimization The TGT scheme treats all data sessions as belonging to one group sharing the same traffic characteristics and each session i is allocated the same transmission rate Rd given by [15, 5. A Load-based Transmission Rate Assignment Scheme 70 A, A. Session 1 queue Session 2 q ueue Session N, queue CDMA Channel Figure 5.1. System model with each data session represented by an M/D/l queue. 16] Rd = W 1 (5.2) In the RGT scheme [15], the Nd data sessions are divided into two groups of size Mx and Nd — Mi respectively. All sessions in a given group j,j = 1,2 are assigned the same transmission rate Rd,RGT,j with Rd,RGT,i > Rd,RGT,2- For a given value of Rd,RGT,2, the values of Mi and Rd,RGT,i are obtained by solving the following optimization problem max[Mii?^GT,i + (Nd - M1)RdiRGT,2] (5-3) subject to 1 -| ™ 1 + Rd,RGT,lld Rd,RGT,2ld Transmission rate assignment in the LTR scheme is made as follows: Referring to 5. A Load-based Transmission Rate Assignment Scheme 71 Figure 5.2, the average packet transfer delay for session i is given by [92] A = ^ -[1 + 2 ( 1 ^ p . ) ] » where pi = \i/Rd,i- In LTR, the rates Rd>i, i = 1, 2,..., Nd are chosen so as to minimize the overall average packet delay, i.e. subject to 1 N d (P) min D= - j — 5 > A (5.5) A s < i , i = i , 2 > : . . > ^ . ( 5 - 6 ) 5.4 Numerical Results In the comparison of the LTR, TGT and RGT schemes presented below, the following system parameter values are assumed: W = 5 MHz, av — 3/8, Ru = 9.6 packets/s, jv = 7 dB, 7 d = 10 dB, Nv = 30 and A = 1. For the RGT scheme, Rd,RGT,2 = 19.2 packets/s. For the results presented, exactly Nd/2 of the data sessions have a packet arrival rate of XA each whereas each of the remaining Nd/2 data sessions has an arrival rate of As. In RGT, each session with an assigned transmission rate of Rd,RGT,i has an arrival rate of XB- Figs. 5.2 and Figs. 5.4 show the overall average packet delay curves for TGT and LTR with A^  = 0.lRdtRGT,2 and A^  = 0.7Rd,RGT,2 respectively. Overall average packet delay curves for RGT and LTR are shown in Figs. 5.3 and Figs. 5.5 for A^  = 0.lRd,RGT,2 and A^  = 0.7Rd,RGT,2 respectively. The x-axis represents the arrival rate ratio defined as XB/XA-Figs. 5.2 and 5.4 show that the TGT and LTR schemes have the same average packet transfer delay if all sessions have the same arrival rates, i.e. XB/XA = 1. This is because the assigned transmission rates for all sessions are the same in both schemes. When the number of sessions is large (Nd = 24), the assigned session transmission rates in RGT are 5. A Load-based Transmission Rate Assignment Scheme 72 Figure 5.2. Overall average packet transfer delay versus a r r i v a l rate r a t i o for the TGT and LTR schemes with \ A = 0.\R^RGT,2-close to those in TGT resulting in almost the same average delay. For a lower number of sessions (JVd=10), it is interesting to note that R G T has a higher average delay than TGT. The reason for this is that although RGT yields a higher sum for the transmission rates assigned to the Nd sessions than TGT, RGT typically assigns a minimum transmission rate of Rd,RGT,2 to all but one session. As the ratio \B/^A deviates from 1, LTR yields an increasingly larger reduction in overall packet transfer delay over TGT and RGT. 5.5 Summary A new load-based transmission rate (LTR) assignment scheme was proposed for integrated voice/data C D M A networks. The LTR scheme allocates a transmission rate to each session 5. A Load-based Transmission Rate Assignment Scheme 73 10' - * - RGT -fc- LTR 10 10 10 20 30 40 50 60 Figure 5.3. Overall average packet transfer delay versus arrival rate ratio for the RGT and LTR schemes with XA = 0.\RdtRGT,2-in such a way as to minimize the overall average packet transfer delay. The LTR scheme is shown to provide significantly lower average delays than the TGT and RGT schemes when the session arrival rates are different. Although an M/D/l queueing model and average packet transfer delay were used in this Chapter, the approach can be extended to more general queueing models and other performance metrics. 5. A Load-based Transmission Rate Assignment Scheme 74 Figure 5.4. Overall average packet transfer delay versus arrival rate ratio for the TGT and LTR schemes with \ A — 0.7Rd,RGT,2-5. A Load-based Transmission Rate Assignment Scheme 75 Figure 5.5. Overall average packet transfer delay versus arrival rate ratio for the RGT and LTR schemes with XA = 0.7R,I,RGT,2-6. A Power Reservation Scheduling Scheme 76 Chapter 6 A Power Reservation Scheduling Scheme for Multimedia Traffic 6.1 Introduction Different multimedia classes require a wide range of Quality of Service (QoS) guarantees such as bit error rate (BER), Packet Transfer Delay (PTD), or Packet Loss Rate (PLR). A major challenge in providing QoS in Code Division Multiple Access (CDMA) networks is the design of Medium Access Control (MAC) protocols that allow sharing of the ra-dio spectrum among multimedia traffic while satisfying their QoS requirements and at the same time maintaining a high channel utilization. Several scheduling schemes have been proposed in the literature for wireless CDMA networks (e.g., [71,86]). In these schemes, several criteria such as minimization of packet loss rate or maximization of throughput are used to design an efficient packet scheduler. These criteria are applied to provide an overall target performance measure but no minimum level of QoS guarantees for each service class is provided. In this Chapter, a control mechanism is proposed that can provide both hard QoS guar-antees for certain service classes and soft QoS for other service classes. This mechanism can be used by the Base Station (BS) for multiplexing multimedia traffic in a power con-trolled CDMA system. The soft QoS mechanism is a means to overcome the difficulty in providing hard (deterministic) QoS guarantee in a wireless environment with multimedia 6. A Power Reservation Scheduling Scheme 77 traffic. This difficulty is due to the complexity in matching the wireless communication sys-tem behaviors and the unreliable nature of its wireless segment. Providing an end-to-end soft QoS has the advantage of being able to cope with the variability of the wireless/mobile channel during a communication session by dynamically adapting both system resource allocation and offered traffic profiles to "soft" requirements of communicating users. The scheme proposed in this Chapter is shown to provide a considerably high channel utilization along with the QoS guarantee for the multimedia traffic classes. It is based on soft resource isolation for different types of traffic and at the same type dynamic alloca-tions based on the instantaneous needs of the sessions carrying the same type of traffic. The priority of a session is determined based on the traffic type, traffic load, Time of Ex-piry (TOE)/Time of Arrival (TOA) value, and packet queue length. By integrating with appropriate traffic conditioning schemes at the ingress nodes (e.g., Mobile Stations (MSs)), the scheduling framework can be adopted as the MAC policy for wireless IP networks and for the emerging Differentiated Services (DS) Internet [8,12]. 6.1.1 Desirable Scheduling Properties A scheduling algorithm should possess different properties in order to work efficiently in wireless networks [18,34,42,93]. However, the following features should also be taken into account when designing wireless schedulers: 1. Energy consumption: The MSs are constrained in battery and processing power. This implies that the power control algorithm should guarantee the Signal-to-Interference Ratio (SIR) target while minimizing the transmit power level. A centralized imple-mentation of the scheduling algorithm at the BS will also help achieve this goal. 2. Channel utilization: Channel bandwidth is the most scarce and precious resource in a wireless environment. A main objective of a packet scheduler is to maximize the channel utilization while maintaining the target QoS parameters of admitted sessions. 3. Multiplexing gain: Many of the proposed schedulers assume a time-slotted operation 6. A Power Reservation Scheduling Scheme 78 for packet transmission. That is, time is divided into frames which are divided into packets slots. In order to get more multiplexing gain, accommodating packets in slots may not be the choice. 4. Contiguous bandwidth allocation: M S takes about 6 — 20 ps to turn-around between transmit/receive modes. It is better to let the M S receives the announcement once and turn on the transceiver for all packets. This wil l result in a low energy consumption and also reduce the number of turn-arounds [93]. 5. Different traffic classes support: Throughput requirements of multimedia applica-tions change drastically over time. A l l fair queueing algorithms use weights to com-pute bandwidth allocations for different sessions from a priori knowledge. This may be difficult for diverse type of multimedia traffic, and/or difficulty in changing the bandwidth shares dynamically. 6. Simplicity and low complexity: Implementing GPS-based scheduling algorithms may introduce computational burden due to the need to maintain internal system parame-ters and timestamping the incoming packets that rise also complexity in exchanging these information between the MSs and the BS. Simple and efficient algorithms that achieve the same QoS guarantees are desirable. 6.2 The Proposed MAC Protocol We consider a wireless network that can support several service classes (e.g., Constant Bit Rate (CBR), Variable Bit Rate (VBR), and Available Bit Rate (ABR)). Each of these classes seeks target requirements such as SIR or transmission rate. Each packet generated by an M S is assumed to have a TOA and TOE value. In the proposed M A C protocol, the total available bandwidth is divided into two bands: one for the uplink and the other for the downlink. For both bands, time is divided into frames of length Tf. The frame length is chosen so as to coincide with the packet arrival rate of the most abundant traffic classes (usually voice). A typical frame length is in the order of 20 ms [86]. The frame in the 6. A Power Reservation Scheduling Scheme 79 Frame k Frame k+l UPLINK T. .._ . J T. 1 J / / / M / / / / / / / / / / / / / / / / / Req / / Data Slot f ' / / / / Slot / / / / / / / / / / / / / / ' / / / Frame k / DOWNLINK ^ / / ', Ack ^ / Slot / Data Slot Processing gap Figure 6.1. Uplink/downlink frame format. uplink and downlink are synchronized with each other. The frame structure is shown in Fig. 6.1. Each frame is composed of the following Modem preamble: At the start of each frame, the M S or BS transmits a modem pream-ble message for framing and synchronization purposes. Also, it helps to reduce interference from previous frames due to propagation delay. The modem preamble duration is assumed to be equal to a maximum one-trip propagation time 0.033 ms (a cell has a radius of 10 Km). Request slot: This slot is composed of the uplink transmission requests from the MSs. This slot has two purposes: 1) to place admission requests by new MSs that ask for ad-mission to the network and 2) to place transmission requests by MSs currently registered in the network. Each M S can support multiple sessions simultaneously. Whenever an M S receives a new packet, it sends a transmission request to the BS containing its session ID and the packet TOA/TOE values. Each M S can use its dedicated control channel for send-ing these information or piggypacking them on uplink packets. Once the BS receives this request, a data structure is used by the BS to keep track of the packet associated with the request. The data structure contains information such as the M S that owns the packet, ses-6. A Power Reservation Scheduling Scheme 80 sion ID, and packet's TOA/TOE values. This information is kept until the packet has been received successfully or the packet expires and is discarded. The BS needs about 50 chips to detect request from MSs and thus this slot is set equal to 0.041 ms (assuming a chip rate of 1.2288 Mcps). BS processing slot: This slot follows the request slot used by the MSs since the BS needs time to process the requests and compute the transmission permissions before the next A C K slot begins. The duration of this slot may vary and hence it is assumed to be equal to a maximum one-trip propagation time of 0.033 ms. Acknowledgement slot: The A C K slot is used by the BS to provide acceptance notifi-cations to MSs that have requested admission to the network, and to provide transmission permissions to MSs that previously requested permissions to transmit a packet. A BS can send these messages through a dedicated control channel of each M S or by piggypacking them on downlink packets. This slot is expected to be relatively small and thus roughly equals to a maximum round-trip propagation time of 0.066 ms. MS processing slot: This slot follows the A C K slot used by the BS since the MSs need time to process and interpret the transmission permissions sent by the BS . The duration of this slot is assumed to be equal to 0.033 ms. Data slot: Includes the uplink/downlink packet transmissions from the M S and BS respectively. This slot occupies the remaining of the frame time which is 19.794 ms and hence yields an overhead of 1.03%. 6.2.1 Proposed Algorithm In this section, we propose a call admission control for guaranteeing the QoS parameters for a newly admitted session. 6. A Power Reservation Scheduling Scheme 81 6.2.1.1 Call Admission Control (CAC) After an MS registers to a cell either locally or through handoff, it may request a target transmission rate and BER for its sessions as they are created. A Call Admission Con-trol (CAC) algorithm is performed in order to determine whether the target requirements for each session can be met by the network or not. The network capacity is given by (i.e., (3.15)) f></xA, (6.1) i = l where gi is the power index, gt = 1/(1 + (W/jiRi)), and W, 7», and Ri are the chip rate, minimum required signal-to-interference ratio (SIR), and transmission bit rate of session i respectively. N is the total number of sessions, p G [0,1] is a utilization factor that affects interference to adjacent cells and power consumption, and A is the available power budget. The CAC algorithm is shown in Fig. 6.2. The algorithm accepts or rejects a session based on the available resource. Each session asks for a target power index value in each frame. The counter, g, keeps track of the sum of the power index values of the admitted sessions. A session is accepted as long as the counter value is less than the available power budget A. Otherwise, it is rejected. The power index value requested by a session is based on the target transmission bit rate and BER. 6.2.1.2 Packet Scheduling In the proposed MAC protocol, a set of packet-scheduling schemes is presented for the transmission of multimedia traffic over CDMA channels with power control. The work is based on the fact that packet scheduling at the link-level for dynamic bandwidth allocation to different admitted sessions and at the same time reserving power resources may be ideal for meeting their QoS requirements while achieving high channel utilization. In addition, an efficient MAC protocol with the above-mentioned desirable scheduler properties is real-ized. The idea here is provide 'soft' resource isolation for the different service classes. That 6. A Power Reservation Scheduling Scheme 82 C A C (g^ /*session admission control*/ { /* gi. Requested power index value of session i; A : Available power budget; \i : A utilization factor (fi 6 [0,1]) g: Counter which records the sum of the power index values of admitted sessions; (g is set to 0 initially) if (g + gi) >= pA session i is rejected; else { 9 = 9 + 9x1 session i is admitted; } } Figure 6.2. Pseudo code for the call admission control algorithm. is, to reserve some power index values which can be changed dynamically in each frame for each service class according to the class instantaneous traffic load, and at the same time make dynamic allocations based on the instantaneous needs of the sessions from the same service class. The packet-level scheduling schemes that are being proposed to transmit multime-dia traffic are: First-Come First-Serve (FCFS), Earliest-Deadline-First (EDF), FCFS+, EDF+, and Round Robin (RR). A l l of these algorithms are traffic priority-based centralized schemes with resource reservation (i.e., power index reservation) for each of the different 6. A Power Reservation Scheduling Scheme 83 service classes coupled with dynamic allocation. The number of packets to be transmitted from each session is determined by its traffic type, TOA/TOE values of its Head-Of-Line (HOL) packet and/or the length of its packet queue. FCFS and EDF are based on the TOA and TOE values of the packet respectively while FCFS+, EDF+ take the packet queue lengths into consideration while performing scheduling calculations. RR is a simple sched-uler that serves sessions in a round-robin fashion and ignores the delay-bound requirements of different sessions. RR ensures fairness among sessions by guaranteeing a successful packet transmission from each session in a round. RR has low implementation complexity compared to other scheduling schemes because it avoids exchanging the TOA/TOE values for each incoming packet and the necessity of sorting these values. In the first four schemes, the priority of a packet is determined based on TOA/TOE val-ues. For FCFS, sessions are prioritized in ascending order of the TOA value of their HOL packets. Ordering between sessions with same TOA values are assumed to be random. FCFS+ is similar to FCFS except that packets with the same TOA values are prioritized in descending order of their packet queue length. In EDF, sessions are prioritized in as-cending order of the TOE value of their HOL packets. Ordering between sessions with the same TOE values are assumed to be random. EDF+ is similar to EDF except that packets with the same TOE values are prioritized in descending order of their packet queue length. RR does not take into consideration TOA/TOE values or queue length, instead it serves sessions in a round-robin manner. 6.2.1.3 Parameters and Notation The BS keeps the following information for all admitted sessions in the network: MS ID, session ID, service class (i.e., CBR/rt-VBR/nrt-VBR/ABR/UBR), queue-length , and TOA/TOE values. We consider only three service classes: CBR, VBR, and ABR although the model can be extended easily to higher number of service classes. Information about sessions is stored in data structure (i.e., linked list) and ordered according to the scheduling schemes employed (i.e., FCFS, FCFS+, EDF, EDF+, and RR). After each frame, the BS 6. A Power Reservation Scheduling Scheme 84 updates the TOA/TOE information for each of the 'active' sessions (i.e., sessions for which requests have been successfully received and these sessions waiting for transmission in the next frame). We used the following parameters: N, NCBR, NVBR, and NABR denote the total num-ber of sessions, the number of CBR sessions, the number of VBR sessions, and the number of ABR sessions. gcBR, QVBR-I 9ABR denote the reserved power index value for CBR ses-sions, VBR sessions, and ABR sessions respectively and gcBR{t), 9vBR(t), gABR{t) are their instantaneous values at the Uh frame. At any time, gcBR + gvBR + gABR < A*A. ScBRif), SvBRif), and SABB(t) denote the set of active CBR sessions, VBR sessions, and ABR sessions at the ith frame respectively and S(t) = ScBR(t) U SvBR(t) U SABR^) and sessions in S(t), ScBR(t), SvBR(t), and SABR^) are ordered according to the scheduling algorithm being employed. For RR scheme, S(t) contains the CBR sessions first, then VBR, then ABR ones (i.e., CBR sessions have priority over VBR sessions due to their more stringent delay requirements and VBR sessions have also priority over ABR ones). A power index value is reserved during each frame for CBR, VBR, and ABR sessions by setting a value for gcBR, gvBR, and gABR respectively. The values of the parameters gcBR, gvBR, and gABR can be changed at any frame. The maximum values of these param-eters depends on the power budget of the network (e.g., (6.1)). Algorithm 1 shows the pseudo code for the five proposed scheduling schemes. Algo-rithm 1 has four phases. In the first phase: for each service class j, a HOL packet is chosen from each session i in the list Sj(t) such that the resulting power index of that session gt does not exceed the reserved power index value gj(t) of that class at the tth frame. It may happen that the power index of a session exceed the reserved power index value, in such a case , this session is skipped (i.e., will not be chosen for transmission) and the next ses-sions in the class are examined. After the end of the first phase, there may remain a residual power index value that can accommodate more packets from previously chosen sessions. During the second phase, sessions in Sj(t) for each service class are examined if more packets other than the HOL packet can be chosen to be transmitted while its new power 6. A Power Reservation Scheduling Scheme 85 index value is still within the reserved power index value gj(t) for that class. At the third phase, any residual power index value from all service classes are distributed among the HOL packets of sessions in the list S(t) that are not serviced before. That is, the algorithm gives priority to serve those sessions that have not receive any service over those that have already got some service. In the last phase, any residual power index value are allocated to sessions in S(t). The algorithm gives priority for servicing the HOL packet over another non-HOL packet from the same sessions since HOL packets are likely to expire before another non-HOL packets. However, a session is selected only if it is error-free, otherwise it is not selected until its channel becomes error-free again. However, packets are not removed from the session queues until they are successfully acknowledged or expired. Sessions are not compensated for their error-prone periods since there are deadlines for each packet and a late packet will be either transmitted successfully or dropped and such a reimbursement may not deem to be necessary. Algor i thm 1 Pseudo code for the five proposed packet schedulers. Scheduler() { i = 0; gcBR,{t) = gcBR> /*First phase */ /*Select HOLpacket(s) from each session in each service class*/ 1- while (i < \SCBR{t)\ andgCBR(t) > 0) { select the HOL packet of session i such that gi < gcBR(t); 9CBR{t) = 9CBR{t) ~ 9i; i++; } i = 0; gvBRif) = 9VBRI 2- while (i < \SVBR{t)\ andgvBR(t) > 0) 6. A Power Reservation Scheduling Scheme 86 { select the HOL packet of session i such that gi < gvBR.{t)>' gvBR,(t) = gvBR,(f) - gu i++; } i = 0; gABR.(t) = gABR; 3- while (i < \SABR{t)\ and gABR(t) > 0) { select the HOL packet of session i such that gi < gABR(t)> gABR(t) = gABR{t) - gi', } /* Second phase*/ /^Distribute the remaining reserved power index value for each service class among its sessions*/ i = 0; 4- while (i < \SCBR(t)\ and gCBR(t) > 0) { 9CBR(t) = gcBR(t) + gu select packets from session i such that gi < gcBR(t); 9CBRif) = 9CBRif) - 9ii } i = 0; 5- while (i < and gvBRif) > OJ { gVBRif) = gVBRif) + g^ 6. A Power Reservation Scheduling Scheme 87 select packets from session i such that < gvBB,(t); gvBRif) = gvBRif) - gv, } i = 0; 6- while (i < \SABR(t)\ and gABR(t) > 0) { gABR(t) = gABR(t) + gu select packets from session i such that gi < gABR(f)> gABR{t) = gABR{t) - gu } /*Third phase*/ /*Distribute remaining power index values from all service classes among HOL packets of sessions in S(t) */ i = 0; g(t) = gCBR(t) + gvBR(t) + gABR(f)i 7- while (i < \S(t)\ and g(t) > 0) { if(session i selected before in steps 1-6) continue; else select the HOL packet of session i such that gi < g(t); g(t) = g(t) - g^ } i = 0; /*Fourth phase */ 6. A Power Reservation Scheduling Scheme 88 /^Distribute remaining power index values from third phase among sessions in S(t) */ 8- while (i < \S(t)\ andg(t) > 0) In this section, we focus on analysis of the proposed power reservation scheduling scheme. Theorem 6.1 Non-work-Conserving: The proposed scheduling schemes are non-work-conserving disciplines. When there is no channel error, the maximum server idle time is (£5 — £1) , where £5 and £1 are time stamps defined in Fig. 6.1. Proof: A work-conserving service discipline is never idle when there is a packet ready to transmit. Non-work-conserving disciplines, allow the server to be idle if no packet is eligible to be transmitted. Initially, there is no packet in MSs' queues, and therefore, the server in BS is idle. If a packet arrives at a queue during the modem preamble period, it will be transmitted in the next uplink data slot in the same frame if there is no channel error. If there is no packets during the modem preamble period, all packets that arrive after the end of the preamble period will be scheduled to be transmitted in the uplink data slot in the next frame. That is, if packets in MSs are ready to be transmitted in [£i,£4), they will be scheduled to be transmitted in [£5, £6). The server will start to serve packets in the beginning of £5. Therefore, the maximum server idle time is (£5 — £ 1 ) . • Theorem 6.2 CBR delay bound: The maximum packet delay of CBR sessions is min{(T3 — } 6.3 Analysis of the Scheduling Scheme 6. A Power Reservation Scheduling Scheme 89 ti) + TiT/jT^}, where n 6 {1, 2,3,...}. T£ut is the packet timeout value of a CBR session and n depends on the duration of errors. Proof: A CBR session is the session that committed not to generate more than a fixed number of packets per frame time Tf. Let a and d be the arrival and departure time of a packet in CBR sessions respectively. If a G [tiff), the departure time will be d e [t5, T6). Therefore the maximum delay equals T 6 — ti = (T3 — h) + Tf. If error occurs, the packets still gets chance to be transmitted in the following uplink data slot. Therefore, between (T3 — ii) and the frame in which the packet is transmitted successfully, there might be several frames in which this packet can not be transmitted. Thus the maximum delay equals (T3—ti)-\-nTf, where n € {1, 2,3,...} and depends on the interval of errors. Since apacket will be dropped if it is not transmitted successfully before its deadline then all packets have a maximum delay T 0 c u t . The delay bound, therefore, is min{(T3 — h) + nTf,T£ut}. • Theorem 6.3 CBR jitter bound: The maximum variation in packet delays of CBR sessions is min{(T3 - tf) + nTf,Tcout} - (t2 - tf), where n E {1, 2,3,...}. Proof: Jitter is the difference between the maximum and minimum packet delays. From Theorem 6.2, the maximum packet delay of a CBR session is min{(T3 — tf) + nTf,T^ut}. A packet arrives in [To, h) can be transmitted immediately in [t2, t3) if there is no channel error. Therefore, the minimum packet delay is (t2 — tf). Thus the jitter bound is min{(T3 — ti + nTf),TZut}-(t2-ti). M Theorem 6.4 VBR delay bound: The maximum packet delay of VBR sessions is mm{(T3-ti) + nTF,T:UT} if c>J2Ri min j(T3 - ti) + UTf + Tf ^2iee PH — C C ),T:u\ ifc<Y,R (6.2) wheren € {1,2,3,...}, C is the maximum number of packets (fromVBR sessions) that can be accommodated in a frame, Ri is the maximum number of generated packets per frame 6. A Power Reservation Scheduling Scheme 90 for a VBR session i, £ is the set of VBR sessions in error-free states, and T^ut is the packet timeout value of a VBR session Proof: In V B R sessions, the number of packets generated per frame varies. If the channel capacity C is enough for J2i<=e Ri, the total number of backlogged V B R packets wil l be scheduled. When each V B R session generates maximum number of packets, all V B R packets generated before the request period can be transmitted in the following uplink data slot. Therefore the maximum delay is m i n { ( T 3 - t i ) + r / , T ^ J . However, if C < J2iSe Ri, a packet may need to wait for some more frames, each with 7 7 of unit times, to be transmitted. The maximum number of frames a packet may need to wait is (T c !)• Therefore, the maximum delay is (T3 - ti) + 7/(1 + \(J2ite R% — C)/C]). A V B R session may have a timeout value T^llt for each packet. The packet wil l be dropped if it is not transmitted successfully before its deadline. Hence the maximum packet delay is min{(T 3 — t\) + 7/(1 + \{T,i£eRi ~ C)/C]),T^ut}. When the channel of a V B R session is in error-prone state, the packet still gets chance to be transmitted in the following uplink data period but it may need to wait for some more frames (i.e., some extra Tf units of time while the channel in error state). Therefore, the theorem follows. • Theorem 6.5 VBR jitter bound: The maximum variation in packet delays of VBR sessions is mmKTs-t^ + T f ^ j - i h - U ) mm {(T3 - t l ) + UTf + Tf ( p £ * g ~ C ifC>Y,Ri ice ) , 2 ^ } - ( t 2 - * i ) ifC<Y,Ri ' } ice (6.3) Proof: From Theorem 6.3, the minimum packet delay is (t2 —The maximum packet delay for a V B R session is obtained in Theorem (6.4). The jitter bound is the difference between the maximum and minimum packet delays. Hence the theorem follows. • Theorem 6.6 Time Complexity: If sessions are admitted according to the CAC in Fig. 6.2, then any service discipline will have 0(1) time complexity for scheduling. Otherwise, EDF, 6. A Power Reservation Scheduling Scheme 91 FCFS, EDF+ , and FCFS+ have O(N) time complexity. On the other hand, RR has 0(1) complexity. Proof: Assuming that sessions are admitted according to the algorithm in Fig. 6.2. The proposed scheduling schemes knows which session it should choose to schedule by just looking at the data structure used for storing the sessions IDs. This data structure is created at the beginning and updated in the request period. The update only takes some computations which take constant time. It is independent with the number of sessions. Therefore, the scheduling decision has a time complexity of 0(1) . There is no need for sorting or exchanging TOA/TOE values, etc. However, if sessions are admitted without the C A C , the proposed EDF, FCFS, EDF+, and FCFS+ schemes need to sort the data structure according to TOA/TOE values and/or queue length. If the total number of sessions in all MSs is N, the sorting algorithm needs an O(N) time complexity for sorting. R R scheme avoids the sorting process since it serves sessions in a round-robin fashion thus yielding an 0(1) time complexity. • 6.4 Simulation Environment The performance of the proposed scheduling schemes are evaluated using computer simu-lation. The 95% confidence intervals are within ± 3 % of the results obtained. We consider three types of traffic sources (i.e., CBR, V B R , and ABR) . Voice, video, and data are exam-ples of CBR, V B R , and A B R sessions respectively. Each session is assumed to generate traffic according to a continuous-time Markov process with each state represents a different transmission bit rate. The simulation parameters are shown in Table 6.1. Voice is assumed to generate a bit-stream during one state only (i.e., O N state) and is classified as a C B R source due to its stringent delay requirement [94]. Video has different transmission rates modelled by multiple states (in our simulation, it is assumed to have three states) and thus become an example of V B R . Since data has large packet timeout value (i.e. 5 s), it is classified as A B R [95]. Each incoming packet has its own TOA/TOE values and packets 6. A Power Reservation Scheduling Scheme 92 interarrival times are assumed to be exponentially-distributed random variables. We assumed a single cell only and seamless (always successful) handoffs and registra-tion. Packet scheduling is performed according to Algorithm 1. All MSs are assumed to have infinite buffer and traffic in both directions (uplink/downlink) are symmetric. All the requests sent by the MSs to the BS or the ACKs sent by the BS to the MSs are assumed to be contention-free and successfully transmitted. For the performance measure, we are interested in a) Packet Loss Rate (PLR): defined as the ratio of the number of packets dropped to the total number of packets generated, b) Packet Transfer Delay (PTD): which is the average time between a packet generation and its successful reception at the receiver, and c) Channel Utilization (U): defined as the ratio of the total used power index value to the available power budget. 6.5 Simulation Results and Discussion In this section, we show the simulation results of the proposed schemes in both error-free and error prone channels. 6.5.1 Error-free Channels We first consider homogenous traffic sources (i.e., CBR, VBR, or ABR only). Figs. 6.3,6.4, and 6.5 show the performance measures for CBR, VBR, and ABR sessions. EDF, FCFS schemes have identical results since all the packets have the same TOE values. For such an environment, where all packets have the same timeout value, serving packets according to their TOE or TOA results in the same performance measures. However, EDF+ and FCFS+ have almost identical results compared to EDF and FCFS schemes respectively. The max-imum number of users that can be accommodated while achieving almost zero PLR are 25, 4, and 38 concurrent sessions for CBR, VBR, and ABR traffic sources respectively. However, RR ignores the TOE/TOA values and achieves fairness in allocating the channel to different sessions thus resulting in higher PLR than the other schemes. 6. A Power Reservation Scheduling Scheme 93 Table 6.1. Simulation parameter values for the reservation scheme. Chip rate (W) 1.2288 Mbps Utilization factor (n) 1 Power budget (A) 0.9 Voice service parameters BER requirement (—) 7 dB Jo Transmission bit rate in states 1 and 2 (Ru R2, R3) 0 Kbps, 9.6 Kbps Mean residence time in states 1 and 2 (ri, r2) 1.35 s, 1 s Packet expiry time 40 ms Video service parameters BER requirement (-p) 8 dB Transmission bit rate in states 1, 2, and 3 (Ri, R2, R3) 32 Kbps, 48 Kbps, 64 Kbps Mean residence time in states 1, 2, and 3 0i, r2, r3) 0.25 s, 0.5 s, 0.25 s Packet expiry time 200 ms Data service parameters BER requirement (-p) 9 dB Jo Transmission bit rate in states 1 and 2(Ri,R2) 0 Kbps, 38.4 Kbps Mean residence time in states 1 and 2 (ri, r2) 1 s, 0.1 s Packet expiry time 5 s Figs. 6.6, 6.7, and 6.8 shows the results for multitraffic environments (CBR and VBR sessions only) for EDF, FCFS, and RR schemes. In these figures, a portion of the available power index is reserved for each type of traffic (i.e., gcBR = 0.3, gvBR = 0.6 and gcBR — 0.4, gvBR — 0.5). VBR sessions in EDF scheme (Fig. 6.6) have zero PLRVBR and their PTDVBR is almost constant due to their reserved resource which prevents the influence of the CBR sessions. However, while decreasing gvBR still results in zero PLRVBR, it results in a slight increase in PTDVBR due to less reservation. FCFS scheme (Fig. 6.7) has close results compared to the EDF scheme in Fig. 6.6. This is due to the resource reservation which provides almost constant performance to different service classes irrespective of the scheduling scheme being employed. However, for RR scheme (Fig. 6.8), PLRVBR is 6. A Power Reservation Scheduling Scheme 94 N C B H Figure 6.3. Variation of PLR, PTD, and U in a single traffic (CBR sessions) environment. still zero due to isolation of classes while PTDVBR increases slightly more than that in E D F and FCFS schemes since R R scheme gives priority to C B R sessions over V B R ones when there is excess power index. A channel utilization U?»0.77 can be achieved when NCBR = 20 and NVBR — 2 with reservation parameters of gcBR = 0.3, gvBR = 0.6. Figs. 6.9, 6.10, and 6.11 shows the results for multitraffic environments (CBR, V B R , and A B R sessions) for EDF, FCFS, and R R schemes respectively. Each service class has a reserved power index value of 0.35, 0.3, 0.25 respectively. In the three schemes, PLRVBR/PLRABR = 0 due to the power resource reservation. U « 0.74 when NCBR = 2to,NVBR = l,andiNABR = l. Fig. 6.12 shows the results for multitraffic environment without any resource reserva-tion (i.e., gcBR = gABR = 0) for both C B R and A B R sessions when there are 10 concurrent A B R sessions. For both types of sources, EDF+ and FCFS+ are almost identical to E D F and FCFS respectively. For E D F and FCFS schemes, PLRABR is almost zero. However, for C B R sessions and for NCBR = 40, PLRCBR » 1 x IO" 2 , ! x 10~ 2 , and 5 x IO" 2 for EDF, RR, and FCFS schemes respectively. E D F and EDF+ schemes perform the best in 6. A Power Reservation Scheduling Scheme 95 N V B R Figure 6.4. Variation of PLR, PTD, and U in a single traffic (VBR sessions) environment. terms of PLRCBR among all other schemes. However, since the packets of CBR sessions have lower timeout value than that of the ABR packets, EDF and EDF+ schemes yield a lower PTDCBR than FCFS and FCFS+ schemes, while the latter yields better PTDABR for ABR sessions since the packets of ABR sessions are serviced as soon as they arrive. The RR scheme results in the lowest PTDCBR for CBR sessions since it gives priority to CBR sessions over ABR ones. On overall and in term of overall PLR, EDF and EDF+ schemes yield the lowest PLR. All schemes have almost the same channel utilization of 0.87 with NCBR = 40. Fig. 6.13 shows a multitraffic scenario without any resource reservation (i.e., gcBR = gVBR = 0) for both CBR and VBR sessions when there are 2 concurrent VBR sessions. For both types of classes, EDF+ and FCFS+ are almost identical to EDF and FCFS respectively. For VBR sessions, EDF scheme has the lowest PLRVBR while the RR one has the highest. In contrary to CBR sessions, RR scheme has the lowest PLRCBR due to the priority of servicing CBR sessions over the VBR ones. FCFS scheme results in the highest PLRCBR for CBR sessions since more service is provided to VBR sessions. FCFS scheme provides 6. A Power Reservation Scheduling Scheme 96 39 40 N.„„ Figure 6.5. Variation of PLR, PTD, and U in a single traffic (ABR sessions) environment. the lowest PTDVBR for VBR sessions since they are given precedence over the CBR ones in this scheme due to the higher packet arrival rate of the VBR sessions. On overall and in term of overall PLR, EDF and EDF+ schemes yield the lowest PLR. Finally, all schemes have very close channel utilization of about 0.92 when NCBR — 30. 6.5.2 Error-prone Channels Since wireless networks is characterized by its bursty and location-dependent channel er-rors, we assumed fading channels to study the performance of the proposed scheduling techniques in error-prone channels. An adequate approximation for a Rayleigh fading chan-nel is the first-order Markov model with two states "good" and "bad" and transition prob-abilities 1—p and 1 — q from good to bad and vice-versa respectively [96,97]. Given p and q, the Markov process is characterized. The steady-state probability of packet error is given by PE = 2]_~P_ and the average length of an error burst is (1 — q)'1. Also, for a Rayleigh 6. A Power Reservation Scheduling Scheme 97 Figure 6.6. EDF: Variation of PLR, PTD, and U in a multitraffic environment (CBR and VBR sessions) for NVBR = 2 when gcBR = 0.3, gVBR = 0.6 andgCBR = 0.4, gVBR = 0.5. fading channel with a fading margin1 F, Pg = 1 — e~llF and q = 1 — ^e'^ )/~<^B<9) where 9 = <Jj^?- Here, Q(.,.) is Marcum's Q function, p = J(2irfdTf) is the Gaussian correlation coefficient (where J 0 is the zero order Bessel function of the first kind) of two successive samples of the complex amplitude of a fading channel with maximum Doppler shift fd (where fd = v/\ = mobile speed/carrier wavelength) taken T / seconds apart. From PE and q, p can be obtained. The parameter fdTf is the normalized Doppler bandwidth and is directly related to the correlation in the fading process. When fdTf is small, the fading process is very correlated (i.e., there will be long bursts of packet errors); on the other hand, for large value of fdTf, the channel error events are almost independent (i.e, there will be short bursts of packet errors). For a certain value of average packet error PE = (particularly for a value in the range of 10-2 to 10~3), the error burst-length increases (i.e., the fading process becomes more correlated) as the user mobility (and hence fdTf) decreases. Other 1It is the maximum fading attenuation which still allows correct reception of a packet. 6. A Power Reservation Scheduling Scheme 98 N C B R Figure 6.7. FCFS: Variation of PLR, PTD, and U in a multitraffic environment (CBR and VBR sessions) for N V B R = 2 when gCBR = 0.3, gvBR = 0.6 andgcBR = 0.4, gVBR = 0.5. parameters remaining the same, as PE increases, error burst length increases rapidly for low-mobility users (Fig. 6.14). In our simulation, when a packet is transmitted, it is kept in the buffer until it is suc-cessfully ACKed or it expires. E D F scheme is simulated using the two-state channel model where the channel state is determined by the two parameters p and q. These two parameters are determined by the normalized Doppler frequency fdTf and the average packet loss rate PE-The performance measures for C B R sessions are shown in Fig. 6.15 for PE = 0.01 (i.e., fading margin 19.978 dB), a user velocity of 1, 5, and 60 km/hr, and a carrier frequency of 900 M H z . The P L R increases with decreasing user mobility since the channel fading events are more correlated with low user-mobility. For example when NQBR = 50, the P L R is about 36 x 1 0 - 3 , 3 2 x 10~ 3 ,31 x I O - 3 for v = 1,5,60 km/hr respectively and U « 0.82. 6. A Power Reservation Scheduling Scheme 99 N C B H Figure 6.8. RR: Variation of PLR, PTD, and U in a multitraffic environment (CBR and VBR sessions) for NVBR = 2 when gcBR = 0.3, gvBR = 0.6 and gcBR = 0.4, gvBR = 0.5. Figure 6.16 shows the results of channel errors in a multitraffic environment. As ex-pected, the PLR decreases with increasing user mobility. However, due to resource isola-tion, PLRVBR and PTDVBR are almost constant. 6.5.3 Summary of Results We have proposed a power index reservation scheme combined with a set of centralized schedulers for CDMA networks in both a single traffic and multitraffic environment. For homogenous traffic, the results obtained are • EDF, EDF+, FCFS, and FCFS+ schemes have identical performance since all packets have the same TOE value. • Although the RR scheme results in higher PLR than the others, it has the lowest implementation complexity and provides fairness guarantee. 6. A Power Reservation Scheduling Scheme 100 N C B H Figure 6.9. EDF: Variation of PLR, PTD, and Uina multitraffic environment (CBR, VBR, and ABR) for NVBR = 1 and NABR = 1 when gCBR = 0.35, gVBR = 0.3, and g A B R = 0.25. For multitraffic environment and without any resource reservation, the following results are obtained • RR scheme has the highest PLR for sessions with the highest packet timeout value and has the lowest PTD for sessions with the lowest packet timeout value due to the prioritization of sessions in descending order of their timeout values. • EDF and EDF+ schemes provide the best overall PLR while achieving a high channel utilization. For error-prone channels, we notice the following • The PLR increases with decreasing the user mobility due to the fact that the fading process becomes more correlated when the user velocity decreases. • The channel utilization, U, decreases as a result of increasing the PLR. 6. A Power Reservation Scheduling Scheme 101 10 20 N „ „ „ Figure 6.10. FCFS: Variation of PLR, PTD, and U in a multitraffic environment (CBR, VBR, and ABR) for NVBR = 1 and NABR = 1 when gcBR — 0.35, gvBR = 0.3, and 9ABR = 0.25. 6.6 Summary For servicing multimedia traffic over the air interface of a power controlled CDMA system, a soft QoS control mechanism can achieve high channel utilization and at the same time provides QoS assurance to different service classes. The set of packet scheduling schemes described in this Chapter is suitable for providing QoS requirements in a multitraffic en-vironment where service to different traffic streams is changed dynamically, depending on traffic type, traffic load, TOA/TOE value of a packet and/or queue length. The reservation parameters, namely gcBR, 9VBR, and gABR are the 'tuning' knob's that can be dynamically adjusted for varying the QoS required for the different service classes. Simulation results show that a reasonably good QoS guarantee (in terms of long term packet loss rate and packet transfer delay) can be obtained for voice, video, and data traffic. 6. A Power Reservation Scheduling Scheme 102 Figure 6.11. RR: Variation of PLR, PTD, and U in a multitraffic environment (CBR, VBR, and ABR) for N V B R = 1 and NABR = 1 when gcBR = 0.35, gVBR = 0.3, and g A B R = 0.25. 6. A Power Reservation Scheduling Scheme 103 Figure 6.12. Variation of PLR, PTD, and U in a multitraffic (CBR and ABR sessions) environment for NABR = 10 when gcBR = 9ABR = 0. 6. A Power Reservation Scheduling Scheme 104 Figure 6.13. Variation of PLR, PTD, and U in a multitraffic (CBR and VBR sessions) environment for NVBR = 2 when QCBR — 9VBR = 0. 6. A Power Reservation Scheduling Scheme 105 Figure 6.14. Variation of average burst error length with PE and v (mobile velocity). Figure 6.15. EDF: Effect of channel error correlations on PLR, PTD, and U for CBR sessions (PE = 0.01). 6. A Power Reservation Scheduling Scheme 106 Figure 6.16. EDF: Effect of channel error correlations on PLR, PTD, and U for multitraf-fic environment (CBR (solid lines) and VBR sessions (dashed lines)) for NVBR = 2 when 9CBR = 0.3, gvBR = 0.6 and PE = 0.01. 7. A Distributed Fair Queueing Architecture 107 Chapter 7 A Distributed Fair Queueing Architecture 7.1 Introduction Many wireline fair queueing algorithms have been adapted to wireless networks [17]. How-ever, the proposed algorithms generally assume downlink operation so that information about session queue statuses is available to the scheduler which is located at the Base Sta-tion (BS). For uplink transmissions, the scheduler does not have immediate access to the statuses of the queues which are remotely distributed at the Mobile Stations (MSs). These algorithms are also designed for systems in which no multiple simultaneous transmissions occur. In Code Division Multiple Access (CDMA) networks, which support multiple simul-taneous transmissions, each MS transmits at a power level which allows the bit error rate (BER) target to be met while minimizing the total transmit power [67]. Scheduled CDMA (SCDMA) [69] and Dynamic Resource Scheduling (DRS) [70] were proposed as frameworks for providing uplink/downlink packet scheduling in CDMA networks. Both SCDMA and DRS do not address the issue of time scheduling for providing guaranteed delay bounds. The issue of time scheduling in CDMA networks has been addressed in [68] using a Generalized Processor Sharing (GPS) approach that guarantees the transmission rate as well as the transmit power level of an MS. The approach assumes fixed spread-7. A Distributed Fair Queueing Architecture 108 ing gain and hence can not be used in multirate transmission schemes such as Variable Spreading Gain (VSG) or MultiCode (MC). Moreover, good channels are assumed and no mechanism is provided for compensating those MSs with error-prone channels. In this Chapter, we propose a C D M A fair queueing architecture for both uplink and downlink that is able to employ any of the wireless fair queueing algorithms and thus allows different algorithms to be used with their attendant pros and cons. We also propose a different GPS approach that allows the MSs to change their power indices to achieve full utilization of the available power resource and enable the support of multirate transmission schemes. A compensation mechanism is introduced to achieve long-term fairness among sessions that perceive bad channels. The compensation mechanism provides long-term power index fairness and graceful power index degradation. 7.2 Network Model We consider a packet cellular network consisting of a BS and a number of MSs. The packets are transmitted using Direct Sequence Spread Spectrum C D M A (DS/CDMA) technology. Time is divided into slots of duration Ts that can accommodate at least one packet. Errors in wireless networks are bursty in nature and may be highly correlated in successive packet transmissions. The channel between the BS and an M S is modelled as a two-state Markov chain which moves between a good and a bad state; the transition probabilities from good to bad state and vice-versa are denoted by pe and pg respectively. 7.2.1 The Mobile Station As shown in Fig. 7.1, each M S has one or more session queues in which packets are queued for transmission. The M S operates as follows: • When a new packet arrives, the M S sends a Packet Transmission Request (PTR) to the BS. The PTR contains the M S ID, session ID, packet length, Time of Arrival 7. A Distributed Fair Queueing Architecture 109 M S 1 Packet Transmission Requests (PTR) Session 1 queue Session 2 queue M S 2 Session 1 queue Session 2 queue Packet Permission Replies (PPR) Session classifier Slot queues Power fair queueing algorithm Power & Code assignment Base Station Figure 7.1. Fair queueing architecture for uplink of a CDMA network. (TOA), and Time of Expiry (TOE). These requests are sent through a separate control channel or by piggybacking on uplink packets. • If a packet expires, the M S drops it from its session queue. The M S does not normally need to notify the BS as the latter has the TOE. If necessary, the M S can transmit a Packet Drop Request (PDR) when it drops a packet. • After the M S receives a Packet Permission Reply (PPR), it can transmit the appropri-ate packets from the session queue. 7.2.2 The Base Station As indicated in Fig. 7.1, the BS contains the slot queues, each corresponding to a session and operates as follows: • When a PTR arrives, a new slot is created with the same length as the packet length 7. A Distributed Fair Queueing Architecture 110 and inserted into the corresponding session slot queue. If the fair queueing algorithm employs timestamping, the slot is timestamped before insertion. • When a packet expires, its slot is deleted and the timestamps of slots in its slot queue are recalculated. • When a number of packets are chosen for transmission, a PPR is sent to the MSs through a separate control channel or by piggybacking on downlink packets. The slot queues at the BS are similar to those introduced in [17] to maintain session access precedence. 7.2.3 Power Control Due to M S battery lifetime limitation, we adopt the approach that minimize the total trans-mit power given certain traffic and channel conditions and QoS (SIR) targets [67,69]. Each session i, has a link gain hi to the BS, and a required B E R represented by its minimum tol-erable signal-to-interference ratio (SIR) 7 * . The QoS constraint at any given time is given by It is shown in Chapter 3 that a solution exists that minimizes the total transmit power and the optimum power level is p. = n 2) gjN0W fc(l-E£iS;) This solution is feasible as long as (assuming other-cell interference factor, / = 0) J 2 g j < l - A - N g c , (7.3) where 7. A Distributed Fai r Queueing Architecture 111 A = N°W , (7.4) mm^h-iPi/gi) where Pi is the maximum transmit power and the power index, gi , of session i is defined as 9i = ^ Zr- C7-5) In (7.3), 5C is the sum of the power indices of the channels used for control purposes. Inequality (7.3) represents a sufficient condition for admitting a new session i and for the existence of an optimal solution. If (7.3) holds for a set of sessions, these sessions can transmit simultaneously and their QoS requirements (i.e., ji and Gi) can be met. The optimal power levels can be obtained from (7.2). 7.3 The GPS Model The GPS approach in [68] assumes a fixed power index for each session during the course of connection. It also assumes that sessions always enjoy good channels and does not provide a compensation mechanism to ensure fairness among sessions with poor channels (i.e. channels which fluctuate between good and bad states). Here, we provide another approach with variable power indices. First, we define the GPS model in which all sessions experience good channels and then we define it for the case of poor channels. We donate both models by d and p respectively. 7.3.1 GPS Model for Good Channels A GPS server in CDMA is a work-conserving and operates between different sessions with guaranteed work rates W\,..., W^- The work rate of session i is defined as Wi = Rcgu (7.6) 7. A Distributed Fair Queueing Architecture 112 where Rc is the chip rate. The server has a total work rate, C, given by C = RC{1 - A). (7.7) At the kth time slot, session i will receive a work rate, uii(kTs), that is Wi(kTs) = „ W i C, (7.8) where B is the set of backlogged sessions. At any time, the following must hold £ W i < C , (7.9) where A is the set of admitted sessions. Since (7.9) and (7.3) are equivalent, the call admis-sion test can be viewed as a constraint on the sum of the power indices or the guaranteed work rates. A session QoS is guaranteed by its power index. The power index at time t of session i is defined as 9t(kTs) = It follows that 9 i -(1-A) Vie B ^jeB9j (7.10) 0 otherwise. X>?(fcTs) = 1 - A. (7.11) From (7.10), we can view the GPS server as a server with a power budget that is dis-tributed among all backlogged sessions in proportional to their power indices. In packet-by-packet GPS (PGPS) [26], each incoming packet k of session i is times-tamped with its virtual start time, , and virtual finish time, Ff, defined as S? = m^(Ff-\v(a*)) F* = ^ + Sl (7.12) JXr 7. A Distributed Fair Queueing Architecture 113 where Ff = 0, a* is the arrival time of the packet, and v(.) is the virtual time function defined as dv = = C = (1 - A) Each session i has a guaranteed power index <?; which varies as in (7.10) depending on the set of backlogged sessions B. This results in a guaranteed work and transmission rate. Serving sessions in an increasing order of virtual finish time provides fairness among sessions. 7.3.2 GPS Model for Poor Channels Wireless scheduling algorithms such as IWFQ, CIF-Q, WFS, and WPS [17] employ a com-pensation mechanism to achieve long-term fairness for operation over poor channels. Each session has an associated lag counter that measures the number of packets by which the session is lagging relative to its good channel service model. Employing the packet compensation mechanism in CDMA networks with a dual-class of service (SIR and transmission bit rate) will not guarantee that a session has been allo-cated its nominal power resource (i.e., power index). It is thus desirable to adopt another approach for achieving long-term fairness that fully utilizes the available power budget. Since the power index is a good representative of a session in terms of its SIR and bit rate, we employ a power index compensation mechanism that achieve long-term fairness in terms of the power index, that is gf= lim -f>f(fcTs) Vi G A. (7.14) where g?(kTs) is the power index value of session i at the kth time slot. In our architecture, an uplink channel state monitoring and prediction for all sessions is done at the beginning of each time slot Ts and sessions that perceive good channels are allowed to transmit. At the beginning of each time slot, a session i is allocated a power index according to 7. A Distributed Fai r Queueing Architecture 114 - ( 1 - A ) VieB d gp(kTs) = l ^J€B^9J (7.15) I 0 otherwise, where Bd is the set of backlogged sessions with good channels. Associated with each session i is a lag counter, lagi(kT3), that indicates by how much the power index value of a session is lagging relative to its good channel model at the kth time slot, that is > 0 if session i is lagging lagi(kTs) \ = 0 if session i is in-sync (7.16) < 0 if session i is leading. At any time, the following holds, "£la9i(kTs) = 0. (7.17) ieA To allow for a graceful service degradation, a lagging session i receives <5; power index compensation from leading sessions, that is mm((l - A) -J29UkTs),J29UkTs),J2la9i(kTs)), ieL ieD teL where L, D are the set of backlogged lagging and leading sessions with good channels respectively and a (0 < a < 1) is a graceful service degradation parameter similar to that in [64]. The power index g\(t) of each session i is updated according to gf (kTs) + 5i ViEL 9P{kTs) = { _9i_yrx ( 7 , 1 9 ) 9i(kTs) - — }^6i V z 6 D-^jeD 9j i(zL The lag counter of session i is updated according to la9i(kTs) = la9i(kTs) + (g?(kTs) - g?(kTa)) V i € B. (7.20) 7. A Distributed Fair Queueing Architecture 115 When a lagging session j becomes unbacklogged, its lag is redistributed back among the leading sessions, that is lagi(kTa) = lagi(kTs) + l a g j ( k T a ) ^ ^ ^ Vz E D. (7.21) The power index of each session is calculated according to (7.10) or (7.19) and each session is allowed to transmit within its power index. Note that because of the work-conserving property of the server, the following holds £s? ( fcT s ) = l - A y i e B . (7.22) i€B The variation in the power index of a session implies a variable transmission bit rate (as-suming constant SIR) and hence the need for multirate support. The next section describes how the MS can support multirate transmission. 7.4 Multirate Support Assuming a maximum packet length L and a maximum processing gain G among all ses-sions, the time slot duration Ts is set equal fo LG/RC. A session may need to transmit up to m packets within a time slot. This multirate requirement can be achieved using VSG or MC transmission. In VSG [98], the chip rate is maintained constant while the processing gain is varied so that m packets are transmitted during a slot. If a session i is to transmit m packets during a slot, then its processing gain has to be reduced to Gi/m. In order to keep the actual SIR (as given by the LHS of (7.1)) constant, its transmit power has to be increased to mPi and its new power index will be 9 ^ = /* =-^~77- .(7-23) Note that 7. A Distributed Fair Queueing Architecture 116 m9i > gYSG > g i . (7.24) The power level of this session , P^SG, is determined using (7.2) and (7.23). In MC [99], all packets are transmitted at a "basic" rate. To increase the transmission rate over the basic rate, a session may transmit up to m packets simultaneously using m different spreading codes. The power index with MC will be gfc = ^ t r - (7-25) The power level of this session , P^c, is determined using (7.2) and (7.25). P r c represents the aggregate power level of all codes used. The power level of each code is pMC/m. 7.5 The Architecture As the wireline fair queueing algorithms work within the transmission bit rate capacity of the outgoing link, the power fair queueing algorithms works within the power budget capacity of the wireless link. When new packets arrive at the MS, PTRs are sent to the BS as mentioned in Section 7.2. If a timestamped power fair queueing algorithm is employed, it operates between these slot queues and chooses the slots with minimum timestamps for transmission in the next time slot until inequality (7.3) is no longer satisfied. If timestamps are not used, a number of packets are chosen for transmission from each session i such that gri < g\{kTs) Vi E B, r E {VSG, MC}, I E {d, p}, (7.26) where g\ is the power index value of the chosen packets as determined from (7.23) or (7.25). The computation of the virtual time function in (7.13) is complex because of the need to keep track of the set of backlogged sessions B. For example, algorithms such as SCFQ [38] 7. A Distributed Fair Queueing Architecture 117 or STFQ [40] use more relaxed definitions for the virtual time function in order to reduce complexity. At any time, the virtual time function is defined in SCFQ and STFQ as the vir-tual finish time and the virtual start time of the packet currently in service respectively. The definitions may be extended to C D M A networks with simultaneous packet transmissions according to the following two corollaries Corollary 7.1 In SCFQ, the virtual time function is set to the maximum virtual finish time of all packets currently in service. Corollary 7.2 In STFQ, the virtual time function is set to the maximum virtual start time of all packets currently in service. Proof: This can be viewed as transmitting these simultaneous packets in serial and since the virtual time function is a non-decreasing function, the virtual time function is set to the virtual time value of the last transmitted packet which has the maximum virtual time value. • 7.6 Simulation Results In this section we present simulation results for both good and poor channels. We assume a system with 5 MSs (sessions) and a single BS. The simulation parameters values are given in Table 7.1. Packets arrive according to independent Poisson processes. Packet lengths are assumed to be fixed-size. We assume that the channels carrying the PTRs and PPRs are good at all times and have negligible propagation delays. For each session, we are interested in evaluating the following three performance measures: (1) W, the ratio of the power index of the session to the sum of the power indices of all sessions, (2) P, the ratio of the number of packets transmitted by a session to the total number of packets transmitted by all sessions, and (3) Dave, the average delay of successfully transmitted packets. The 95% confidence intervals for the performance results presented are at most ± 3 % of the values shown in the tables. 7. A Distributed Fair Queueing Architecture 118 Table 7.1. Simulation parameter values. Parameter Symbol Value Chip rate (Mbps) Rc 1.2288 Reserved transmission bit rate (Kbps) Ri, R2, R3, R4, Rs 4.8,9.6,19.2,38.4,76.8 Link gain hi 1 Maximum transmit power (W) Pi 2 Control channel parameter 1.2 Kbps, 7 dB, 0.005 Noise power spectral density {W/Hz) N0/2 10~6 SIR (dB) 7i>72,73,74,7s 7, 7,9,9, 7.8 Power budget 1 - A 0.64 Session normalized power index 5 9il Yl 9j j=i 0.03,0.06,0.17,0.31,0.43 Time slot duration (s) T 0.20833 Example 7.1 (Good and poor channels): Table 7.2 (A) and (B) show the results in both good and poor channels respectively. Ta-ble 7.2 (A) shows that a session transmits at a normalized power index value close to its target value. The number of packets transmitted is proportional to the reserved transmis-sion bit rate (e.g., session 2 transmits twice as many packets as session 1) while the average delay decreases with the reserved transmission bit rate. For poor channels , we assume all sessions experience good channels all the time except for session 3 which experiences a poor channel modelled by a two-state Markov chain with a good to bad state transition probability pe — 0.06 and a bad to good state transition probability pg = 0.04. The graceful service degradation parameter, a, is set to 1. In Table 7.2 (B), it can be seen that due to the compensation mechanism, each session transmits at a normalized power index value close to its target value. The number of packets transmitted by a session is proportional to its reserved transmission bit rate. The average delay of session 3 is higher compared to the good channels case. The average delays of all other sessions are also higher than in Table 7.2 (A) because of the compensation mechanism that tries to guarantee the power indices and transmission bit rates for all sessions in poor channels. 7. A Distributed Fair Queueing Architecture 119 Table 7.2. Performance measure values for (a) good channels (b) poor channels. (A) Good channels (B) Poor channels session W P •&avg (^) W P Davg(s) 1 0.030 0.033 7.1 0.030 0.034 9.8 2 0.059 0.068 4.6 0.059 0.067 6.7 3 0.172 0.133 1.4 0.172 0.133 4.5 4 0.311 0.262 0.7 0.311 0.262 1.9 5 0.428 0.504 0.4 0.428 0.504 1.5 Example 7.2 (Service degradation for leading sessions): We assume three sessions with equal reserved transmission bit rates, target SIRs, and nor-malized power indices of 9.6 Kbps, 7 dB, and 0.06 respectively with all other parameter values as in Table 7.1. The channel for session 1 is in bad state in the time interval [0,10] and in a good state after that. Sessions 2 and 3 enjoy good channels all the time. The service degradation for leading sessions is illustrated in Fig. 7.2 (a) for a = 0.5. Up to time 10, session 1 has a zero power index as it has a bad channel. Sessions 2 and 3 receive excess service with the power budget distributed equally among them so that each session gets a power index of 0.32. At time 10, the channel for session 1 becomes good, and the session begins to reduce its lag. The leading sessions (2 and 3) start to give up some of their leads to the lagging session (session 1). Even though sessions 2 and 3 accumulated a substantial lead, they are not prevented from transmitting but rather they experience a graceful degradation of service. The effect of increasing a can be seen in Fig. 7.2 (b). This higher a value causes the leading sessions to give up their leads more rapidly. At time 10, the leading sessions 2 and 3 have zero power indices until the lagging session catches up. 7. A Distributed Fair Queueing Architecture 120 0.45 S 0.4 S o °- 0.3 tj>t>00&fj> i — - i 1 rvTyTVTVTYTV rtVTVTVTVTV^ LUAIAJAIAIJ >»C>M>I >00M>t axixDaxDct) (a) 0 5 10 15 20 25 Time (b) Figure 7.2. Graceful service degradation when (a) a = 0.5 and (b) a = 1.0. 7.7 Summary A general framework for deploying fair queueing algorithms in wireless CDMA networks was proposed. The architecture supports both uplink and downlink transmissions and takes into account power budget constraints. The transmission bit rates and BER's targets of sessions are met through guaranteed power index values. Power is allocated among all sessions in proportional to their weights. For use with poor channels, a power index com-pensation mechanism is employed in order to achieve long-term fairness among sessions. The framework supports multirate services using VSG and MC. 8. An Improved Round Robin Packet Scheduler 121 Chapter 8 An Improved Round Robin Packet Scheduling Algorithm 8.1 Introduction Many traffic scheduling algorithms, that are used for Quality of Service (QoS) provision, have been proposed for the wireline domain [34,42]. Adapting these algorithms to the wireless domain is not an easy task due to the unique features of wireless networks [17, 66] which include (a) location-dependent channel capacity and channel errors, (b) channel access contention, (c) scheduling on both uplink and downlink, and (d) processing and battery power constraints for the Mobile Station (MS). In order for a scheduling algorithm to work well in this environment, it should possess the following properties [17,65] (a) short-term fairness among sessions that perceive a clean channel, (b) long-term fairness among all sessions, (c) ability to meet prescribed throughput objectives, (d) bounded delay for session packets, and (e) graceful service degradation for all sessions. One important aspect of scheduling algorithms is implementation complexity. Most of the proposed wireless scheduling algorithms can be classified as either: i) round-robin schedulers or ii) Generalized Processor Sharing (GPS) based schedulers. GPS-based sched-ulers [26] are generally more complex as they involve the use of virtual time function. Channel State Dependent Packet Scheduling (CSDPS) [100] and Wireless Packet Schedul-ing (WPS) [61] are examples of the first class whereas Idealized Wireless Fair Queueing 8. An Improved Round Robin Packet Scheduler 122 (IWFQ), Channel-condition Independent Fair Queueing (CIF-Q) [64], Server Based Fair-ness Approach (SBFA) [65], and Wireless Fair Service (WFS) [66] are examples of the second class. The proposed wireless deficit round robin (WDRR) algorithm, which makes use of the deficit round robin idea in [101], is a round-robin scheduler which can be easily imple-mented. We analyze this algorithm, verify its properties through computer simulations and show that it possesses the above-mentioned desirable properties of a wireless scheduling algorithm. It is shown that the error-free service characteristics of WDRR are superior to those of the algorithm in [101] for both fairness index and isolation property. This algo-rithm can be applied in any CDMA or non-CDMA system which incorporates time-division multiplexing. 8.2 Network Model We consider a packet cellular network consisting of a Base Station (BS) and a number of MSs. Scheduling is implemented centrally at the BS which communicates with the MSs; direct MS-to-MS communication is not possible. Packets exchanged between the BS and an MS may experience channel errors. Knowledge of the channel state and packet queue status for all sessions is available at the BS. Errors in wireless networks are bursty in nature and may be highly correlated in suc-cessive packet transmissions. The channel is modelled as a two-state Markov chain which moves between the error-free ("good") and error-prone ("bad") states; the transition prob-abilities from good to bad state and vice-versa are denoted by pe and pg respectively. In this Chapter, we focus on the algorithmic operation of WDRR and do not address issues such as a more accurate error model or the MAC protocol. 8. A n I m p r o v e d R o u n d R o b i n P a c k e t S c h e d u l e r 123 8.3 The WDRR Algorithm The basic scheduling mechanism for WDRR is now described. WDRR consists of the following key components: • An error-free service model, that provides wireless service to sessions with error-free channels. • A lead and lag model, that determines which sessions are leading, lagging, or in-sync with their error-free service model and by how much. • A compensation model, which requires leading sessions to compensate lagging ses-sions for service received while the lagging sessions' channels were in the bad state. 8.3.1 The Error-free Service Model In WDRR, a set A of sessions share the outgoing channel and each session i G A has a normalized rate weight (or reserved rate) r». The sum of the reserved rates assigned to sessions does not exceed the outgoing channel capacity C, i.e., 2 > < 1 . (8.1) The algorithm operates in rounds: in each round, at most a total of Q bits are nominally transmitted from all the clean backlogged sessions; Q is referred to as the system quantum parameter. The session i quantum Qi is given by Qi = ^ x Q, (8.2) and represents the number of bits that are nominally allocated to session i in each round. Let Lmax be the maximum packet size among all sessions in A. The system quantum Q is chosen so as to satisfy Qi Lmax, i G A. (8.3) 8. An Improved Round Robin Packet Scheduler 124 Each session i e A maintains a deficit state variable A> initially set equal to zero, that is incremented by Qi at the beginning of each round. Session i is allowed to transmit up to Di bits, i.e., the maximum number, K, of packets in the current round satisfies the inequality where L\ is the size of packet k of session i. Di is decremented after each packet trans-mission by an amount equal to the packet size. If the session is still backlogged after transmitting the K packets, its Di is left unchanged; otherwise it is reset to zero. In order to provide short-term fairness, WDRR provides service to sessions in small increments by interleaving the packet transmissions of different sessions. This is done by dividing each round into a number of frames. Each frame consists of a variable number of slots of maximum size Lmax. The nominal number of slots allocated to session i € A in a given frame is If a session is unbacklogged for one of its assigned slots, the slot is de-assigned, i.e. deemed not to have been assigned. In this case, A is decremented by an amount equal to min (A, Lmax) so that it might still transmit should it become backlogged later in the same round. At the end of a round, the deficit Di of any unbacklogged session i is reset to zero. Due to the variable packet size, each slot may not be fully utilized by packets and hence at the end of a frame, a session i may still have packets that satisfy (8.4). In this case, a new frame is generated. Within a frame, slots for different sessions are interleaved in a round robin fashion. To clarify how WDRR works, consider an example consisting of four sessions with reserved rates 0.5, 0.25, 0.125, 0.125 respectively and assume, for simplicity, that the pack-ets are of fixed-size of unit length (Lmax = 1) and the system quantum is 16 Lmax. Due K E 4 f c < A (8.4) (8.5) 8. An Improved Round Robin Packet Scheduler 125 #1 r, =0.5 #2 r2=0.25 #3 r3=0.125 #4 r4 =0.125 Figure 8.1. Quantum allocation. to the fixed-size packets, each round wil l consist of only one frame. Initially the deficit counters of all sessions are zero and sessions are allocated quanta as in Fig. 8.1. Fig. 8.2 represents the session deficits when they are divided into slots of equal size Lmax. Fig. 8.3 (a) and (b) show the order of packet transmissions from each session for D R R and W D R R respectively. The interleaving used in W D R R can be seen in Fig. 8.3 (b). If each session is allowed to transmit using its whole deficit value at once as in [101], then session 1 will send a burst of 8 packets, followed by bursts from each of the other sessions. Session 4 will have to wait 8 + 4 + 2 = 14 packets before it can start transmitting its H O L packet. One way to reduce the H O L packet delay is to service sessions in smaller bursts (slots) as shown in Fig. 8.3 (b). Session 4 is now able to transmit its H O L packet after 3 packet transmissions, independent of the deficit values of the other sessions. The interleaving of packet transmissions minimizes the worst-case session delay of H O L packets and yields a better fairness index as shown by the analysis. Transmitting packets as in Fig. 8.3 (a) causes each session to send a burst of packets and then go silent until all other sessions have finished sending their bursts of packets. This oscillation between long bursts and long silence periods is undesirable for a congestion control algorithm. The task of controlling congestion is made easier by smoothing out the packet transmissions from each session over time [44]. System quantum 16 Deficit counter | 2 | 8. An Improved Round Robin Packet Scheduler 126 Deficit counter #1 =0.5 #2 r2 =0.25 #3 r3 =0.125 #4 r4 =0.125 Figure 8.2. Deficits shown as slots of length Lmax each. (a) Round time (b) Figure 8.3. Session transmission order for (a) DRR (Fig. 8.1) and (b) WDRR (Fig. 8.2). 8. An Improved Round Robin Packet Scheduler 127 8.3.2 WDRR in Error-prone Channels - Lead, Lag, and Compensa-tion We now consider WDRR in error-prone channels with location-dependent and bursty chan-nel errors; it is assumed that the channel changes state after each round. A session i can be leading, lagging, or in-sync. A session is leading if it has received more service than it would have received in an error-free system, lagging if it has received less, and in-sync if it has received the same amount. Associated with each session i is a parameter lagi that represents the difference between the service that session i would have received in an error-free system and the service that it has actually received in the error-prone system. A session i is lagging if lagi is positive, leading if lagi is negative, and in-sync if lagi is zero. At all times, the following equation holds: X># = 0. (8.6) The parameter lagi is measured in bits and not in slots as in [61,64-66]. This provides finer granularity to the compensation models which allows for greater fairness in compen-sating the lagging sessions. To achieve a graceful service degradation for leading sessions, we use a system param-eter a (0 < a < 1) to control the fraction of session quantum Qi retained by a leading session i. A leading session i has to give up a maximum of (1 — a) of its quantum Qi in a round to lagging sessions. Since the number (1 — a)Qi of bits could be higher than session i's lead \lagi\, to prevent the leading session i from becoming a lagging session, session i relinquishes min((l — a)Qi: \lagi\) bits. A lagging session j receives bit alloca-tions from two sources : (a) its normal quantum allocation Qj, and (b) bits relinquished by leading sessions; these are shared by clean lagging sessions in a weighted round robin (WRR) manner where the weight of each lagging session is its lag value. To achieve long-term fairness, in addition to compensating lagging sessions, when a 8. A n Improved Round Robin Packet Scheduler 128 session with a positive lagi value becomes unbacklogged, we need to adjust the lags of the other sessions in order to ensure that (8.6) holds. We do this by distributing the positive lag of the lagging session among all the remaining leading sessions j lagj = lagj + lagi x 1 ;J , (8.7) l^feLla9f where L is the set of leading sessions. By distributing lagi among the leading sessions, we avoid disturbing the in-sync sessions. A session is said to be clean if its channel is in the good state during the current round and dirty otherwise. When a new round begins, all sessions are allocated quanta according to the following four cases: Case 1- Session i is backlogged and clean: (a) if i is lagging or in-sync, then it is allocated a quantum Qi, (b) otherwise, if session i is leading and there exists a clean back-logged lagging session j, session i relinquishes min( ( l — a)Qi, \lagi\) to session j; lagi is incremented by min(( l — a)Qi, \lagA) and lagj is decremented by the same amount. Session j is chosen from among all the clean backlogged lagging sessions in a weighted round robin fashion according to their lags, (c) otherwise, if session i is leading and there is no clean backlogged lagging session j, session i is allocated a quantum Qi. Case 2-Session i is backlogged and dirty: (a) if there exists a clean backlogged lagging session j, then session j is allocated a quantum Qi, lagi is incremented by Qi, and lagj is decremented by Qi, (b) otherwise, if there exists a clean backlogged leading session j, then j is allocated a quantum Qt, lagi is incremented by Qi, and lagj is decremented by Qi, (c) otherwise, if there exists a clean backlogged in-sync session j, then j is allocated a quantum Qi, lagi is incremented by Qi, and lagj is decremented by Qi, (d) otherwise, the quantum Qi is wasted. Case 3-Session i is unbacklogged and clean: Session i is allocated a quantum Qi. Case 4-Session i is unbacklogged and dirty: Session i is not allocated any quantum. The flow charts of the W D R R algorithm are shown in Fig. 8.4 and Fig. 8.5. Fig. 8.4 explains how each session is allocated its quantum in error-free and error-prone channels. 8. An Improved Round Robin Packet Scheduler 129 Once the deficit counter of each session is updated, W D R R schedules packet transmissions according to Fig. 8.5. Essentially, W D R R tries to avoid wasting quanta, tries to decrease lag before increasing lead, and tries to avoid disturbing in-sync sessions. 8.3.3 Support for Both Delay-sensitive and Error-sensitive Channels For an error-sensitive session, the head-of-line (HOL) packet may be dropped after a certain number of transmissions whereas for a delay-sensitive session, the H O L packet is dropped after a delay bound is exceeded. W D R R supports both types of session requirements by leaving the deficit variable unchanged on packet deletion. When a lagging session i deletes its H O L packet and becomes unbacklogged, its lag value, lagi, is reset to zero and in order to ensure that (8.6) holds, the leads of the leading sessions are adjusted according to (8.7). 8.4 Analysis Definition 8.1 A session can send if it perceives a good channel during the current round; otherwise it cannot send. Lemma 8.1 At the end of any round, 0 < Di < Lmaxfor every session i. Proof: Initially A = 0. During subsequent rounds, we have two possibilities: 1. If session i can send, it can be either: (a) backlogged and Di wi l l be decremented when a packet is transmitted and continue to be decremented until the size of the H O L packet is greater than A- Since the maximum packet size is Lmax, it follows that Di < Lmax, or (b) unbacklogged, in which case Di is reset to 0 at the end of the round. 2. If the session cannot send, it wil l not be allocated a quantum Qi and its A remains unchanged; hence 0 < A < Lmax. Figure 8.4. Quantum allocation flow chart. 8. An Improved Round Robin Packet Scheduler 131 Start new round Allocate quanta to sessions Get session S for current slot p so E • Transmit HOL packets of S Decrement D c move to next slot Figure 8.5. Transmission flow chart. 8. An Improved Round Robin Packet Scheduler 132 Lemma 8.2 The size (number of bits transmitted), R, of a round is bounded by R <Y2,Qi + NLmax. (8.8) i€A Proof: From lemma 8.1, A < Lmax. When a new round starts, there are two possibili-ties: 1. If all sessions can send, then the total quantum allocation is Yi^A Qi (a lagging o r in-sync session receives its normal quantum while a leading session shares its quantum with lagging ones). 2. If some session cannot send and is backlogged, its quantum Q{ will be relinquished to another session and if it is unbacklogged, it will not be allocated a quantum; hence the total allocation does not exceed YiaA Qi-The algorithm accumulates the different allocations in the deficit variables and hence + £ A- (8.9) i€A i £ A before updating of the deficit variables. From lemma 8.1: £ A < i V £ m a z , (8.10) ieA and (8.8) follows. Remark 8.1 If no interleaving is performed, Lemma 8.2 provides the following upper-bound on the delay of the HOL packet (defined as the time interval between the packet becoming HOL and the packet starting transmission) of any session i di < E ^ a Q j + N L m a x . (8.11) With interleaving, this delay is bounded by 8. An Improved Round Robin Packet Scheduler 133 NL < ilA^l. (8.12) Corollary 8.1 At the end of any round, the difference in the total number of bits sent by any two continuously (in all rounds) clean backlogged in-sync sessions with the same reserved rate r, is less than Lmax. Remark 8.2 Since from lemma 8.1, the maximum value of the deficit variable at the end of a round is Lmax, the corollary follows. With interleaving, it is easy to show that the maximum difference in the total number of bits sent by any two continuously clean backlogged in-sync sessions with the same reserved rate r is bounded by 2 L m a x at any time (even during the middle of a round). Without interleaving, the upper-bound is 2 L m a x + r * Q. Theorem 8.1 The total number of bits, Wi(k), transmitted from any continuously clean backlogged in-sync session i after k rounds is bounded by kQi - Lmax < Wi(k) < kQi. (8.13) Proof: In each round, session i is allocated a quantum Qi, thus yielding a total allocation of kQi bits. At the end of round k, the total number of bits transmitted is kQi — Di. Since 0 < Di < Lmax (from lemma 8.1), (8.13) follows. • Theorem 8.2 The difference between the normalized service received by any two contin-uously clean backlogged in-sync sessions i and j after k rounds is bounded as follows. wz(k) w ^ k ) ^ ^ ^ ^ ( 8 1 4 ) Ti rj u rj Proof: From theorem 8.1 and dividing by r* we get kQ — LmaxJTi < Wi(k)/ri < kQ. 8. An Improved Round Robin Packet Scheduler 134 Remark 8.3 The bound (8.14) on the fairness index between session i and j is valid at the end of a round. At any time, with interleaving the fairness index between any two continuously clean backlogged in-sync sessions with the same reserved rate r is bounded by 2Lmax/r. If there is no interleaving, the bound is (2Lmax + rQ)/r. Theorem 8.3 The long-term throughput of a continuously clean backlogged in-sync ses-sion i is close to the session i quantum, i.e., lim ^ 1 = Q i . (8.15) Proof: This follows directly from (8.13). • Theorem 8.4 Consider a leading backlogged session i during the time interval from round di to round d2. Let lagi(d) be the session i lag at the beginning of a round d. Suppose that there is always a clean lagging session which can take the compensation allocation whenever session i gives up a fraction (1 — a) of its quantum Qi during [d\, d2\. Then, the maximum number, Rg, of rounds in the graceful degradation period is given by -lagi(di). (l-a)Qi Proof: As long as \lagi(d)\ > (1 - a)Qit where d E [dx,d2], session i will give up (1 - a)Qi bits per round. In the final round of the graceful degradation period, it gives up its remaining lead which is < (1 — a)Qi. • 8.5 Simulation Results In this section some properties of WDRR are illustrated and the analysis in Section 8.4 is verified using computer simulation. In particular it is shown that on error-free channels, WDRR provides a tighter delay bound, a better fairness index and isolation property than DRR. On error-prone channels, WDRR is able to provide long-term fairness and graceful service degradation. 8. An Improved Round Robin Packet Scheduler 135 In the scenarios which we simulated, independent Poisson-distributed traffic streams are generated with the arrival rate for session i given by r;. Packet lengths are assumed to be either of fixed-size of 1 unit or the size is uniformly distributed in [0.1,1] and the channel capacity is 1 unit length/unit time. For each session, we are interested in the following four performance measures: (1) W, the fraction of packets transmitted by a session out of the total number of packets transmitted by all sessions, (2) Pt, the loss probability defined as the ratio of the number of packets dropped by an error- or delay-sensitive session to its total number of transmitted packets, (3) Dave, the average delay for successfully transmitted packets. The 95% confidence intervals for the performance values presented are at most ± 3 % of the values shown in the tables. Example 8.1 (WDRR and IWFQ): W D R R is compared with IWFQ in this example. We consider a scenario with three error-free sessions having reserved rates of 0.5, 0.25, and 0.125 and a system quantum Q = 8. The results are shown in Table 8.1 for fixed-size packets and in Table 8.2 for variable-size packets. In both cases, it can be seen that the actual rates are very close to the reserved rates. The average delays decrease with the reserved rate. This is due to the fact that the number of slots nominally allocated in each round to a session is directly proportional to its reserved rate as in (8.2). Thus, a session with a higher reserved rate has a larger number of nominally allocated slots. IWFQ is a timestamped algorithm that transmits packets in an increasing order of their timestamp values. Due to interleaving in W D R R , session 1 experiences a lower delay with IWFQ than with W D R R whereas sessions 2 and 3 have lower delays with W D R R . Generally, the session with highest delay with IWFQ wil l experience a lower delay with W D R R ; conversely, the session with the lowest delay with IWFQ wil l experience a higher delay with WD R R . This is due to the conservation law [102] which states that the overall average packet delay is identical for any scheduler which is work-conserving and selects packets for transmission in a way that is not dependent on the packet length. Example 8.2 (WDRR and DRR): 8. An Improved Round Robin Packet Scheduler 136 Table 8.1. WDRR performance measure values for example 8.1 (fixed-size packets). session W Pi Davg 1 0.5 0.51 0 4.29 W D R R 2 0.25 0.253 0 5.25 3 0.125 0.125 0 6.54 1 0.5 0.51 0 3.33 IWFQ 2 0.25 0.253 0 5.64 3 0.125 0.125 0 7.19 Table 8.2. WDRR performance measure values for example 8.1 (variable-size packets). session W Pi Davg 1 0.5 0.51 0 0.84 W D R R 2 0.25 0.253 0 0.86 3 0.125 0.125 0 0.88 1 0.5 0.51 0 0.82 IWFQ 2 0.25 0.253 0 0.89 3 0.125 0.125 0 0.96 In this example, we investigate the performance differences between W D R R and D R R and verify that W D R R provides a lower delay bound as predicted by the analysis in section 8.4. As in Example 8.1, We consider three error-free sessions having reserved rates of 0.5, 0.25, and 0.125. We compare both algorithms with different values of the system quantum. We are interested in getting the average delays for all sessions. The average delay of each session with both fixed-size and variable-size packets are plotted in Fig. 8.6 and Fig. 8.7. The interleaving of packet transmissions in W D R R has the same effect as that described in Example 8.1. Example 8.3 (Isolation property): 8. An Improved Round Robin Packet Scheduler 137 i r i i i i - ; u v i * - , ^ , G~ : _ . € > - . ' - o o_ _ s " - - 0 - . "TO O - o - - - i e Session 1 (WDRR) • * • Session 2 (WDRR) • * • Session 3 (WDRR) -e- Session 1 (DRR) Session 2 (DRR) - » - Session 3 (DRR) ^o^-—r^^^-—.p & ^ • i i i [ I ' I I I I I I I I 0 10 20 30 40 50 60 70 80 System quantum Figure 8.6. Average delay versus the system quantum with fixed-size packets. I I I ! * • ' • * < \ * - C s *— - •*-. * — • • - * 4--* T A • - • _Q f. t •- Q . : • • • • O • -T- -Or •' -«• Session 1 (WDRR) ••* Session 2 (WDRR) * Session 3 (WDRR) - 0 - Session 1 (DRR) - * - Session 2 (DRR) - » - Session 3 (DRR) 0 10 20 30 40 50 60 70 80 System quantum Figure 8.7. Average delay versus the system quantum with variable-size packets. 8. An Improved Round Robin Packet Scheduler 138 ! 1 - WDRR DRR session :1 is / misbehaving / session: 1 is behaving A — • WDRR DRR session 1 is misbeha ving s /s s session 1 is behaving h • i 0 20 40 60 System quantum 0 20 40 60 System quantum Figure 8.8. Average delay versus system quantum with fixed-size packets for (a) session 2 and (b) session 3. In this example, we investigate the isolation properties of WDRR and DRR. Sessions 1, 2, and 3 are error-free and have reserved rates of 0.5, 0.25, and 0.125 respectively. We assume that session 1 can misbehave. When it misbehaves, the packet arrival rate for session 1 is four times higher than normal. The average delays for both sessions 2 and 3 with session 1 behaving normally and misbehaving are plotted in Fig. 8.8 for fixed-size packets and in Fig. 8.9 for variable-size packets. It can be seen that the average delay for WDRR increases less rapidly than for DRR. This is due to the interleaving in WDRR which provides better isolation from the misbehaving session. Example 8.4 (Fairness property) We show in this example the better fairness property provided by WDRR over DRR. We assume three error-free sessions with equal reserved rates of 0.3 and each session is back-logged at any time. We notice the maximum difference between the normalized service received by any two backlogged sessions over a time window [0,40] (Theorem 8.2). We plot this normalized service versus a unit time step in a time interval of [0,40] as in Fig. 8.10 8. An Improved Round Robin Packet Scheduler 139 1 1 1 1 — W D R R D R R / / : \ session 1 is. s : j misbehaving / / .. session:.! .is behaving A . ; A - W D R R DRR \ • • r" - V sessio misbe n 1 is w i n g session behav ! / 1 is ng \ \ i i i 20 40 60 80 System quantum (a) 20 40 60 System quantum (b) Figure 8.9. Average delay versus system quantum with variable-size packets for (a) ses-sion 2 and (b) session 3 . and Fig. 8.11 for both WDRR and DRR respectively. We vary also the system quantum in each run. As we can see in Fig. 8.10 for WDRR, the maximum fairness index is one. This is due to interleaving which provides service to sessions in equal and small bursts. We note also the independence of the fairness index on the system quantum. Both curves for the two system quanta are totally identical indicating the independence of the WDRR perfor-mance on the system quantum- On the other hand and as in Fig. 8.11 for DRR, the fairness index increases with the system quantum. DRR services sessions in a bigger bursts than in WDRR leading to a higher fairness index. Example 8.5 (Error-prone channels): In this example, the three sessions have equal rates of 0.3. Session 3 is error-free all the time whereas sessions 1 and 2 experience error-prone channels according to a two-state Markov model withpe = 0.03 andp5 = 0.07. For error-sensitive sessions, a packet is dropped if it is not successfully transmitted in 8. An Improved Round Robin Packet Scheduler 140 H 1- ~T T~ O 0=10 x Q=20 10 15 20 Time 25 30 35 Figure 8.10. Fairness index versus time for different system quanta in WDRR. ~~i r~ T r O 0=10 x Q=20 10 15 20 25 30 35 Time Figure 8.11. Fairness index versus time for different system quanta in DRR. 8. An Improved Round Robin Packet Scheduler 141 Table 8.3. WDRR performance measure values for example 8.5: Error-sensitive sessions. session ri W Pi 1 0.3 0.332 0 63.13 WDRR 2 0.3 0.332 0 64.39 3 0.3 0.336 0 8.15 error 1 0.3 0.336 0 6.24 free 2 0.3 0.329 0 6.26 channels 3 0.3 0.335 0 6.32 Table 8.4. WDRR performance measure values for example 8.5: Delay-sensitive sessions. session W Pi 1 0.3 0.328 0.003 50.13 WDRR 2 0.3 0.327 0.005 51.33 3 0.3 0.345 0 7.81 8 attempts. Table 8.3 shows the simulation results of WDRR. For comparison, the results when all the three channels are error-free are also presented in Table 8.3. It can be seen that sessions 1 and 2 (with error-prone channels) receive the same actual rates as session 3 (with error-free channel) but have larger delays due to errors. The compensation mechanism in WDRR provides actual rate guarantees even in error-prone channels. For delay-sensitive sessions, a packet is dropped when its delay bound is exceeded. In the simulation, a packet is dropped if it is not transmitted within 200 time units. This might happen even before it becomes the HOL packet. Table 8.4 shows the simulation results. As with the case of error-sensitive sessions, sessions 1 and 2 (with error-prone channels) receive the same actual rate as session 3 (with an error-free channel) but incur larger delays. Example 8.6 (Graceful service degradation): This example illustrates how WDRR provides graceful service degradation for leading ses-8. An Improved Round Robin Packet Scheduler 142 sions. The three sessions have equal reserved rates of 0.3. Session 1 experiences a bad channel in the time interval [0,200] and a good channel after that. Sessions 2 and 3 enjoy error-free channels all the time. The graceful service degradation of WDRR for the leading session is illustrated in Fig. 8.12 and Fig. 8.13 for two different values of a. It can be seen that WDRR provides a linear service degradation which is different from that in IWFQ, WPS [61], and WFS [66]. Up to time 200, session 1 is unable to transmit as it has a bad channel. Session 2 receives the excess service. Because the algorithm avoids disturbing in-sync sessions as much as possible, we can see that session 3 does not receive any excess service. At time 200, the channel for session 1 becomes error-free, and the session begins to reduce its lag. The leading session (session 2) starts to give up some of its lead to the lagging session (session 1). Even though session 2 had accumulated a substantial lead, it is not prevented from transmitting but experiences a graceful degradation of service, while the in-sync session (session 3) is not disturbed at all. The effect of the parameter a can also be observed in Fig. 8.12 and Fig. 8.13. The higher the value of a, the slower the leading session gives up its lead. For a = 0, the curve for the leading session would be completely flat until the lagging session caught up with the leading and in-sync sessions. 8.6 Summary The emergence of new applications for the wireless domain such as multimedia and Internet applications has spurred the use of wireless traffic scheduling algorithms for providing QoS guarantees. These guarantees are usually in the form of bounded-delay, guaranteed-rate, and fairness among sessions. In this Chapter, WDRR is proposed as a new scheduling algorithm for wireless net-works. To the best of our knowledge, this is the first wireless scheduling algorithm that provides low delay bound, tight fairness index, and good isolation property with low im-plementation complexity. The error-free service model of WDRR is shown through analysis and simulation to 8. An Improved Round Robin Packet Scheduler 143 Time Figure 8.12. Graceful service degradation when a = 0.5. 0 500 1000 1500 Time Figure 8.13. Graceful service degradation when a = 0.8. 8. An Improved Round Robin Packet Scheduler 144 be superior of that of DRR. This error-free model is extended to work efficiently in error-prone channels which characterize any wireless link so that it can provide short-term and long-term fairness among sessions, meets throughput objectives, and supports both delay-sensitive and error-sensitive sessions. It was shown that the compensation rate can be tuned to suit specific needs. 9. Conclusions 145 C h a p t e r 9 C o n c l u s i o n s Several Radio Link Control (RLC)/Medium Access Control (MAC) layer protocol design problems in multimedia wireless networking have been addressed in this dissertation. This includes calculating the Erlang capacity of a power controlled Code Division Multiple Ac-cess (CDMA) system with multirate sources, proposing an access scheme that guarantees different Quality of Service (QoS) parameters such as bit error rate (BER), packet loss rate, delay and delay jitter, introducing a load-based transmission rate assignment scheme for data sessions in an integrated voice/data system, integrating multimedia services with QoS provision over the air interface, presenting a new fair queueing architecture combined with a Generalized Processor Sharing (GPS) model for CDMA networks, and finally, proposing a new round robin packet scheduling scheme. The work presented in this dissertation are summarized below. • Erlang Capacity of a CDMA System with Multirate Traffic Sources We have presented a new analytical approach for evaluating the Erlang capacity of a CDMA system with different types of traffic sources. First, we derive an admis-sion criterion that takes into account the other-cell interference and self-interference effect. Following the admission criterion, we introduce a method for modelling mul-timedia services in a CDMA system with power control. In this method, each traf-fic source is represented by a Markov process that characterize its transmission bit rates and target BER. Through the use of Kronecker algebra, the superposition of the Markov processes of all sources yields the system Markov process which captures 9. Conclusions 146 the total transmitted power level for all sessions and hence can be used to obtain the blocking probability or effective power level. The analysis is extended to include an-other dominant effect in wireless network which is the imperfection in power control due to fading or shadowing effect. • A Guaranteed Quality of Service Wireless Scheduling Scheme Current wireless multimedia applications may require different QoS measures such as throughput, packet loss rate, delay, and delay jitter. A transmission rate schedul-ing scheme for CDMA networks is proposed that can provide absolute or relative QoS guarantees. The scheduling scheme uses several queues, each representing a different service class, and allocates a transmission rate to each queue so as to meet the different QoS targets. The scheduling scheme provides relative differentiated ser-vices among the different service classes so that the network operator is able to tune QoS ratios between these classes independent of the class loads. An optimization problem is proposed that maximizes the transmission rate allocations among Mobile Stations (MSs). Operation in error-prone channels is enabled by a mechanism that compensates sessions which experience poor channels. Analysis and simulation re-sults are used to illustrate the viability of the scheduling scheme. Such a scheme can be applied in the emerging Differentiated Services (DS) Internet. • Load-based Transmission Rate Assignment Scheme As data applications vary in their offered load (e.g., web browsing, ftp, Email, rlogin, telnet, etc. ), a load-based transmission rate (LTR) assignment scheme is investigated for integrated voice/data systems. The LTR scheme assigns transmission rates to all data sessions according to their loads so as to minimize the overall average packet transfer delay. LTR scheme is different from the conventional scheme that assigns equal rates to all data sessions irrespective of the incoming traffic load. The proposed LTR scheme is shown to provide significant lower average packet transfer delay than the conventional one. • Soft QoS Provisioning in the Wireless CDMA Air-Interface 9. Conclusions 147 A power reservation policy combined with dynamic priority based packet-level schedul-ing schemes have been investigated for servicing multimedia traffic over CDMA air interface with power control. In the proposed scheduling policy, the number of pack-ets selected for transmission from a session is changed dynamically depending on the traffic type, traffic load, Time of Expiry (TOE)/Time of Arrival (TOA) values of packets, and/or packet queue length. The resource allocation is based on 'soft' re-source isolation for different service classes. That is, the reserved power resource for each service class can be changed dynamically from frame to frame and at the same time make dynamic allocations based on the instantaneous needs of the sessions from the same service class. The reservation parameters, gcBR, 9VBR, and gABR, are the 'tuning' knob's that can be dynamically adjusted for varying the QoS required for the different service classes. The values of gcBR-, gvBR, and gABR can be adjusted by the network operator according to the instantaneous traffic load and/or pricing policy. • Distributed Fair Queueing Architecture Fair queueing algorithms can play an important role in an integrated-services net-work that provides a broad range of QoS guarantees. Most of the proposed wireless fair queueing algorithms assume downlink operation and/or a single packet trans-mission only. For uplink transmissions, the scheduler (which is located at the BS) does not have immediate access to the statuses of the queues which are remotely distributed at the MSs. These algorithms are designed for systems in which no mul-tiple simultaneous transmissions are allowed. A CDMA fair queueing architecture for both uplink and downlink is proposed that is able to employ any of the wireless fair queueing algorithms with their attendant pros and cons and thus allows different algorithms to be used with their attendant pros and cons. We also propose a dif-ferent GPS approach that achieve fairness among competing MSs in term of power resource. A new compensation mechanism is described that works among sessions that perceive error-prone channels to achieve long-term fairness. The compensation mechanism provides long-term power index fairness and graceful power index degra-9. Conclusions 148 dation. The architecture supports multirate transmission schemes such as Variable Spreading Gain and MultiCode. • An Efficient Round Robin Algorithm For Packet Cellular Networks A new round robin scheduling algorithm (WDRR) for packet cellular networks is proposed. W D R R is a round robin scheduler that has low implementation complex-ity and offers a low delay bound, tight fairness index, and good isolation property. In error-prone channels, the algorithm provides short-term fairness among sessions that perceive a clean channel, long-term fairness among all sessions, ability to meet spec-ified throughput objectives for all sessions, and graceful service degradation among sessions that received excess service. Both analysis and simulation are used to verify that W D R R have the desirable feature of a wireless packet scheduler. 9.1 Future Work • Transmission Control Protocol (TCP) Performance in Wireless CDMA Net-works TCP/IP is the standard network protocol used in the Internet. Its use in next genera-tion multimedia networks is a certainty. The transport protocol performance depends on the service provided by the underlying network and R L C / M A C layer. The in-fluence of the proposed access control schemes on TCP/IP performance needs to be investigated. • Wireless LAN (HIPERLAN Type 2) A HIPERLAN/2 network looks like any other W L A N from a network topology point of view. Users connect their Mobile Terminals (MT) to an Access Point (AP) and can move around in the coverage area provided by the APs. Traffic scheduling schemes are crucial components in HIPERLAN/2, which are used to optimize the allocation of resources, especially as demand for the resources increases. Centralized schedul-ing is also important for the efficient support of QoS. HIPERLAN/2 possesses sev-9. Conclusions 149 eral advantages compared to IEEE 802.1 lx such as a) QoS for real-time multimedia communication; at least for operators, it will be vital to find new ways of increasing the revenue streams besides offering plain best-effort Internet services, b) Efficient power save mechanism for integration into portable devices, c) a MAC layer devel-oped and optimized for radio communication at 5 GHz to deliver highest possible throughput over the air interface, d) Dynamic Frequency Selection (DFS) which re-alizes automatic frequency planning thereby simplifying radio network installation and expansion, e) Convergence Layer offering backbone network independence by allowing for interoperability with: Ethernet, IEEE1394 (Firewire), ATM, and 3G (third generation) mobile systems, and finally f) Strong security features with sup-port for individual authentication and per session encryption keys. The performance of HIPERLAN/2 with the new QoS-aware schemes proposed in this thesis would be of great interest. Bibliography 150 Bibliography [1] A. M. Viterbi and A. J. Viterbi, "Erlang capacity of a power controlled CDMA sys-tem," IEEE Journal on Selected Areas in Communications, vol. 11, no. 6, pp. 892-900, August 1993. [2] T. S. Rappaport, Wireless Communications, Principles, and Practice. Prentice-Hall, 1996. [3] M. Zeng, A. Annamalai, and V. K. Bhargava, "Recent advances in cellular wireless communications," IEEE Personal Communications Magazine, vol. 37, pp. 128-138, September 1999. [4] T. S. Rappaport, A. Annamalai, R. Buehrer, and W. Tranter, "Wireless communi-cations: past events and a future perspective," IEEE Communications Magazine, vol. 40, pp. 148-161, May 2002. [5] S. Blake, D. Blake, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An architecture for differentiated services," IETF RFC 2475, December 1998. [6] P. P. White, "RSVP and integrated services in the Internet: A tutorial," IEEE Com-munications Magazine, vol. 35, pp. 100-106, May 1997. [7] C. Dovrolis and P. Ramanathan, "A case for relative differentiated services and the proportional differentiation model," IEEE Network, vol. 13, pp. 26-34, Septem-ber/October 1999. [8] D. Grossman, "New terminology and clarifications for diffserv," IETF RFC 3260, April 2002. [9] C. Dovrolis and P. Ramanathan, "Dynamic class selection: From relative differenti-ation to absolute QoS," International Conference on Network protocols, November 2001. [10] J. Heinanen, F. Baker, W. Weiss, and J. Wroclawski, "Assured forwarding PHB group," IETF RFC 2597, June 1999. [11] A. Odlyzko, "Paris metro pricing: the minimalist differentiated services solution," IEEE Seventh International Workshop on Quality of Service (IWQoS), pp. 159-161, May/June 1999. [12] I. Mahadevan and K. Sivalingham, "Quality of service in wireless networks based Bibliography 151 on differentiated services architecture," IEEE Eighth International Conference on Computer Communications and Networks, pp. 548 - 553, October 1999. [13] C. Dovrolis, D. Stiliadis, and P. Ramanathan, "Proportional differentiated services: delay differentiation and packet scheduling," IEEE/ACM Transactions on Network-ing, vol. 10, pp. 12-26, February 2002. [14] K. Nichols, S. Blake, F. Baker, and D. Black, "Definition of the differentiated ser-vices field (DS field) in the IPv4 and IPv6 headers," IETF RFC 2474, December 1998. [15] H. Kang and K. Kim, "Throughput enhancement scheme for integrated voice/data DS-CDMA system: rate-based grouping transmission," Electronics Letters, vol. 35, no. 17, pp. 1437-1438, August 1999. [16] S. Ramakrishna and J. Holtzman, "A scheme for throughput maximization in a dual-class CDMA system," IEEE Journal on Selected Areas in Communications, vol. 16, no. 6, pp. 830-844, August 1998. [17] S. Lu, V. Bharghavan, and T. Nandagopal, "Fair queueing in wireless networks: Issues and approaches," IEEE Personal Communications Magazine, vol. 6, pp. 44-53, February 1999. [18] H. Fattah and C. Leung, "An overview of scheduling algorithms in wireless mul-timedia netowrks," IEEE Wireless Communications Magazine, vol. 9, pp. 76-83, October 2002. [19] , "Capacity of a DS/CDMA system with heterogeneous traffic sources," To ap-pear in IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), August 2003. [20] , "Erlang capacity of a CDMA cellular system with multirate sources," To ap-pear in IEEE Vehicular Technology Conference (VTC), October 2003. [21] , "A transmission rate scheduling scheme for multimedia services in wire-less CDMA networks," To appear in IEEE Global Telecommunications Conference (GLOBECOM), December 2003. [22] , "A load-based transmission rate assignment scheme for an integrated voice/data DS-CDMA system," To appear in IEE Electronics Letters, 2003. [23] , "A guaranteed quality of service wireless access scheme for CDMA net-works," To appear in IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM), August 2003. [24] , "A distributed fair queueing architecture for CDMA networks," IEEE Vehicu-lar Technology Conference (VTC), vol. 1, pp. 166-170, September 2002. Bibliography 152 [25] , "An efficient scheduling algorithm for packet cellular networks," IEEE Vehic-ular Technology Conference (VTC), vol. 4, pp. 2419- 2423, September 2002. [26] A. K. Parekh and R. G. Gallager, "A generalized processor sharing approach to flow control - the single node case," IEEE Computer and Communications Societies Con-ference (INFOCOM), vol. 2, pp. 915-924, May 1992. [27] A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," Internetworking: Research and Experience, vol. 1, no. 1, pp. 3-26,1990. [28] L. Zhang, "VirtualClock: A new traffic control algorithm for packet switching net-works," ACM Transactions on Computer Systems, vol. 9, pp. 101-124, May 1991. [29] D. Ferrari and D. Verma, "A scheme for real-time channel establishment in wide-area networks," IEEE Journal on Selected Areas in Communications, vol. 8, pp. 368-379, April 1990. [30] M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, "Weighted round-robin cell multiplexing in a general-purpose ATM switch chip," IEEE Journal on Selected Ar-eas in Communications, vol. 9, pp. 1265-1279, October 1991. [31] M. Shreedhar and G. Varghese, "Efficient fair queueing using deficit round robin," ACM SIGCOMM, vol. 9, pp. 231-242, September 1995. [32] C. Kalmanek, H. Kanakia, and S. Keshav, "Rate-controlled servers for very high-speed networks," IEEE Global Telecommunications Conference (GLOBECOM), pp. 300.3.1-300.3.9, December 1990. [33] S. Golestani, "A framing strategy for congestion management," IEEE Journal on Selected Areas in Communications, vol. 9, pp. 1064-1077, September 1991. [34] H. Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Proc. IEEE, vol. 83, pp. 1374-1396, October 1995. [35] D. Stiliadis and A. Varma, "Latency-rate servers: A general model for analysis of traffic scheduling algorithms," IEEE Computer and Communications Societies Con-ference (INFOCOM), pp. 111-119, March 1996. [36] , "Rate-proportional servers: A design methodology for fair queueing algo-rithms," IEEE/ACM Transactions on Networking, vol. 9, no. 2, pp. 164-174, April 1998. [37] , "Efficient fair queueing algorithms for packet-switched networks," IEEE/ACM Transactions on Networking, vol. 9, no. 2, pp. 175-185, April 1998. [38] S. Golestani, "A self-clocked fair queueing scheme for broadband applications," In-ternational Teletraffic Conference, pp. 636-646, April 1994. Bibliography 153 [39] , "Network delay analysis of a class of fair queueing algorithms," IEEE Journal on Selected Areas in Communications, vol. 13, pp. 1057-1070, Aug. 1995. [40] P. Goyal, H. Vin, and H. Chen, "Start-time fair queueing: A scheduling algorithm for integrated services packet switching networks," ACM SIGCOMM, pp. 157-169, September 1996. [41] D. Stiliadis and A. Varma, "A general methodology for designing efficient traffic scheduling and shaping algorithms," IEEE Computer and Communications Societies Conference (INFOCOM), pp. 326-335, April 1997. [42] R. Guerin and V. Peris, "Quality-of-service in packet networks: basic mechanisms and directions," Computer Networks, vol. 31, pp. 169-189, 1999. [43] J. Bennett and H. Zhang, "Hierarichal packet fair queueing algorithms," ACM SIG-COMM, pp. 143-156, Aug. 1996. [44] , "WF2Q: worst-case fair weighted fair queueing," IEEE Computer and Com-munications Societies Conference (INFOCOM), pp. 120-128, March 1996. [45] J. Crowcroft and J. Oechslin, "Differentiated end-to-end Internet services using a weighted proportional fair sharing TCP," ACM SIGCOMM, vol. 28, no. 3, pp. 53-67, July 1998. [46] I. Stoica, S. Shenker, and H. Zhang, "Core-stateless fair queueing: Achieving ap-proximately fair bandwidth allocations in high speed networks," ACM SIGCOMM, vol. 28, pp. 118-130, October 1998. [47] S. Suri, G. Varghese, and G. Chandranmenon, "Leap forward fair queueing," IEEE Computer and Communications Societies Conference (INFOCOM), pp. 557-565, 1997. [48] J. Rexford, A. Greenberg, and F. Bonomi, "A fair leaky-bucket shaper for ATM networks," AT&T laboratory, Tech. Rep. AT&T Rep., July 1995. [49] H. Elguibaly, A. Sabaa, J. Muzio, F. Elguibaly, and D. Shpak, "Performance evalu-ation of a window-based approach for ATM cell scheduling," Canadian Conference on Electrical and Computer Engineering, pp. 36^ -0, 1995. [50] A. Parekh and R. Gallager, "A generalized processor sharing approach to flow con-trol - the multiple node case," Laboratory for information and decision systems, MIT, 77 Massachusetts Avenue Cambridge, MA 02139-4307, USA, Tech. Rep. 2076, July 1991. [51] F. Elguibaly, "Design and analysis of arbitration protocols," IEEE Transactions on Computers, vol. 38, no. 2, 1989. [52] S. Floyd and V. Jacobson, "Link-sharing and resource managment models for packet Bibliography 154 networks," IEEE/ACM Transactions on Networking, vol. 1, no. 4, pp. 397^ 113, Aug. 1993. [53] S. Floyd and A. Romanow, "Dynamics of TCP traffic over ATM networks," IEEE Journal on Selected Areas in Communications, vol. 13, no. 4, pp. 633-641, May 1995. [54] J. Turner, "Maintaining high throughput during overload in ATM switches," IEEE Computer and Communications Societies Conference (INFOCOM), pp. 287-295, April 1996. [55] D. Verma, D. Ferrari, and H. Zhang, "Guaranteeing delay jitter bounds in packet switching networks," Tricomm 91, April 1991. [56] H. Zhang and S. Keshav, "Comparison of rate based service disciplines," ACM SIG-COMM, pp. 113-122, 1991. [57] R. Gibbens and P. Hunt, "Effective bandwidths for the multi-type UAS channel," Queueing Systems, pp. 17-28, September 1991. [58] F. Kelly, "Effective bandwidth at multi-class queues," Queueing Systems, pp. 5-16, September 1991. [59] R. Guerin, H. Ahmadi, and M. Naghshineh, "Equivalent capacity and its application to bandwidth allocation in high-speed networks," IEEE Journal on Selected Areas in Communications, vol. 9, no. 7, pp. 968-981, September 1991. [60] A. Greenberg and N. Madras, "How fair is fair queueing," The Journal of ACM, vol. 39, no. 3, pp. 568-598, July 1992. [61] S. Lu, V. Bharghavan, and R. Sirkant, "Fair scheduling in wireless packet networks," IEEE/ACM Transactions on Networking, vol. 7, no. 4, pp. 473^ 89, August 1999. [62] M. Kang and S. Wilbur, "A fair guaranteed down-link sharing scheme for cellular packet switched networks," IEEE Global Telecommunications Conference (GLOBE-COM), vol. 2, pp. 1006-1010, November 1997. [63] T. Nandagopal, S. Lu, and V. Bharghavan, "A unified architecture for the design and evaluation of wireless fair queueing algorithms," ACM MOBICOM, pp. 132-142, August 1999. [64] T. S. Ng, I. Stoica, and H. Zhang, "Packet fair queuing algorithms for wireless net-works with location-dependent errors," IEEE Computer and Communications Soci-eties Conference (INFOCOM), vol. 3, pp. 1103-1 111, March 1998. [65] P. Ramanathan and P. Agrawal, "Adapting packet fair queuing algorithms to wireless networks," ACM MOBICOM, pp. 1-9, October 1998. [66] S. Lu, V. Bharghavan, and T. Nandagopal, "Design and analysis of an algorithm Bibliography 155 for fair service in error-prone wireless channels," ACM/Baltzer Wireless Networks Journal, vol. 6, pp. 323-343, August 2000. [67] A. Sampath, P. S. Kumar, and J. M. Holtzman, "Power control and resource manage-ment for a multimedia CDMA wireless system," IEEE Personal, Indoor and Mobile Radio Communications Conference (PIMRC), pp. 21-25, September 1995. [68] M. Arad and A. Leon-Garcia, "A generalized processor sharing approach to time scheduling in hybrid CDMA/TDMA," IEEE Computer and Communications Soci-eties Conference (INFOCOM), vol. 3, pp. 1164-1171, March 1998. [69] M. A. Arad and A. Leon-Garcia, "Scheduled CDMA: a hybrid multiple access for wireless ATM networks," IEEE Personal, Indoor and Mobile Radio Communica-tions Conference (PIMRC), vol. 3, pp. 913-917, October 1996. [70] O. Gurbuz and H. Owen, "Dynamic resource scheduling strategies for QoS in W-CDMA," IEEE Global Telecommunications Conference (GLOBECOM), vol. la, pp. 183-187, December 1999. [71] I. Akyildiz, D. Levine, and I. Joe, "A slotted CDMA protocol with BER scheduling for wireless multimedia networks," IEEE/ACM Transactions on Networking, vol. 7, no. 2, pp. 146-158, April 1999. [72] A. J. Viterbi, CDMA: Principles of spread spectrum communication. John Wiley. & Sons, Inc., 1995. [73] C. Yun and D. G. Messerschmitt, "Power control for variable QoS on a CDMA chan-nel," IEEE Military Communications Conference (MILCOM), pp. 178-182, 1994. [74] A. Sampath and J. Holtzman, "Access control of data in integrated voice/data CDMA systems: benefits and tradeoffs," IEEE Journal on Selected Areas in Communica-tions, vol. 15, no. 8, pp. 1511-1526, October 1997. [75] S. S. Choi and D. H. Cho, "Performance evaluation of an adaptive access control scheme in an integrated voice/video/data CDMA system," IEEE Global Telecommu-nications Conference (GLOBECOM), vol. 4, pp. 2081-2085, 1999. [76] D. Goodman and S. Wei, "Efficiency of packet reservation multiple access," IEEE Transactions on Vehicular Technology, vol. 40, pp. 170-176, February 1991. [77] M. R. Izquierdo and D. Reeves, "A survey of statistical source models for variable-bit-rate compressed video," Multimedia Systems, vol. 7, no. 3, pp. 199-213, 1999. [78] A. J. Viterbi, A. M. Viterbi, and E. Zehavi, "Other-cell interference in cellular power-controlled CDMA," IEEE Transactions on Communications, vol. 42, pp. 1501— 1504, February/March/April 1994. [79] H. Heffes and D. M. Lucantoni, "A Markov modulated characterization of packe-Bibliography 156 tized voice and data traffic and related statistical multiplexer performance," IEEE Journal on Selected Areas in Communications, pp. 856-868, September 1986. [80] H. Heffes, "A class of data traffic processes-covariance function characterization and related queueing results," Bell Systems Technical Journal, vol. 59, pp. 897-929, July-August 1980. [81] B. Maglaris, D. Anastassiou, P. Sen, G. Karlsson, and J. Robbins, "Performance models of statistical multiplexing in packet video communications," IEEE Transac-tions on Communications, vol. 36, no. 7, pp. 834—844, July 1988. [82] M. F. Neuts, Structured stochastic matrices of M/G/l type and their applications. New York: Dekker, 1989. [83] V. Amoia, G. D. Micheli, and M. Santomauro, "Computer-oriented formation of transition-rate matrices via Kronecker algebra," IEEE Transactions on Reliability, vol. R-30, no. 2, pp. 123-132, June 1981. [84] S. Schwartz and Y. S. Yeh, "On the distribution function and moments of power sums with log-normal components," Bell Systems Technical Journal, vol. 61, pp. 1441-1462, September 1982. [85] P. Pancha and M. El Zarki, "Bandwidth-allocation schemes for variable-bit-rate MPEG sources in ATM networks," IEEE Transactions on Circuits and Systems for Video Technology, vol. 3, no. 3, June 1993. [86] T. Lee and J. Wang, "Admission control for variable spreading gain CDMA wireless packet network," IEEE Transactions on Vehicular Technology, vol. 49, no. 2, pp. 565-575, March 2000. [87] D. Gross and C. Harris, Fundamentals of Queueing Theory. John Wiley & Sons, Inc., 1974. ' ' ' [88] A. G. De Koko and H. C. Tijms, "A queueing system with impatient customers," Journal of Applied Probability, vol. 22, pp. 688-696, 1985. [89] A. Huang and D. McDonald, "Connection admission control for constant bit rate traffic at a multi-buffer multiplexer using the oldest-cell-first discipline," Journal of Queueing Systems, vol. 29, pp. 1-16, January 1998. [90] K. Ramakrishnan, S. Floyd, and D. Black, "The addition of explicit congestion no-tification (ECN) to IP," IETF RFC 3168, September 2001. [91] F. Adachi, M. Sawahashi, and H. Suda, "Wideband DS-CDMA for next-generation mobile communications systems," IEEE Communications Magazine, vol. 36, pp. 56-69, September 1998. [92] L. Kleinrock, Queueing Systems. John Wiley & Sons, Inc., 1975, vol. 1. Bibliography 157 [93] J. Chen, K. Sivalingam, P. Agrawal, and R. Acharya, "Scheduling multimedia ser-vices in a low-power MAC for wireless and mobile ATM networks," IEEE Transac-tions on Multimedia, vol. 1, no. 2, pp. 187-201, June 1999. [94] S. Nanda, D. Goodman, and U. Timor, "Performance of PRMA: a packet voice protocol for cellular systems," IEEE Transactions on Vehicular Technology, vol. 40, no. 3, pp. 584-599, August 1991. [95] A. Mohammad, "Radio link control and transport protocol design issues in wireless IP networks," Ph.D. dissertation, Department of Electrical and Comuter Engineer-ing, University of Victoria, British Columbia, Canada, 2000. [96] A. Chockalingam, M. Zorzi, L. Milstein, and P. Venkataram, "Performance of a wireless access protocol on correlated Rayleigh-fading channels with capture," IEEE Transactions on Communications, vol. 46, no. 5, pp. 644 - 655, May 1998. [97] M. Zorzi, R. Rao, and L. Milstein, "On the accuracy of a first-order Markov model for data transmission on fading channels," Fourth IEEE International Conference on Universal Personal Communications, pp. 211-215, November 1995. [98] C.-L. I. and K. K. Sabnani, "Variable spreading gain CDMA with adaptive con-trol for true packet switching wireless network," IEEE International Conference on Communications (ICC), vol. 2, pp. 725-730, June 1995. [99] C.-L. I. and R. D. Gitlin, "Multi-code CDMA wireless personal communications networks," IEEE International Conference on Communications (ICC), vol. 2, pp. 1060-1064, June 1995. [100] D. Duchamp and N. Reynolds, "Measured performance of a wireless LAN," IEEE 17th Conference On Local Computer Networks, pp. 494-499, September 1992. [101] M. Shreedhar and G. Varghese, "Efficient fair queueing using deficit round robin," IEEE/ACM Transactions on Networking, vol. 4, pp. 375 -385, June 1996. [102] L. Kleinrock, Queueing Systems. John Wiley & Sons, Inc., 1976, vol. 2. Appendix A 158 Appendix A Calculation of the Moments of the Power Index Random Variable Assuming that L is a lognormal r.v., i.e., L = 10x'w = eY (A.l) where Y is a Gaussian distributed r.v. (i.e., Y ~ jV(my,<7y) = M(f5mx,01cr2x) and (3 = ln(10)/10. The moments of L is E\eY\ = mL = e^+4/2 = ePmx+p*x/2 (A.2) E[e2Y] = e 2 m Y + 2 a Y - eWmx+2p2ax^ The power index of a traffic source is given by where eY, ez, ew, and ev are lognormal r.v. and G is the processing gain. Using Wilkinson approach [84] and by equating the moments of the these r.v., the statistics (i.e., mean and variance) of the power index are (A.4) e2mw+2cr%v = ]_ _|_ £ 2 e 2 m Z + 2 o Z + 2GemZ+<7^2. Re-writing (A.4) yields Appendix A 159 mw + a2w/2 = ln ( l + Gemz+^/2) 2mw + 2a2w = ln ( l + G2e2mz+2^ + 2Gemz+°z/2). Solving (A.5) for mw and aw yields (A.5) mw = 2 ln ( l + Gem z + a^ 2) - - ln ( l + G2e2mz+2^ + 2Gemz+az'2) o2w = ln ( l + G 2e 2 m z + 2 f f^ + 2Gemz+^'2) - 21n(l + Gemz+^'2). Since (A.6) mz = —Amy Ji _ fl2 2 ° Z = P aY my = —(3mw Jl FftJl av = p a (A.7) From (A.6) and (A.7), the mean and variance of the power index in (A.3) is given by mv = \ ln(l + G2e-2l3mY+2l32ar + 2 G e - / 3 m y + / 3 V 2 ' / 2 ) - 21n(l + G e - / W + / 3 2 4 / 2 ) a\ = ln(l + G2e~2l3mY+2^y + 2Ge-^+^yl2) - 21n(l + Ge^mY+^y'2). (A.S) Appendix B 160 Appendix B WDRR Algorithm Pseudo Code The Pseudo code of the WDRR algorithm is shown below. process_round() /*the main program to process round*/ 1 predict_alLsession_states_in_current_round(); 2 if (all sessions need new round) 3 for (all session that was unbacklogged in previous round) 4 Di = 0; 5 allocate_quanta(); 6 interleave(); 7 continue; /*a new frame is generated within the same round*/ 8 else if (next slot s is beyond current frame) 9 interleave(); 10 continue; 11 else /*next slot s is a valid slot in current frame*/ 12 i=get_sessionJd_to_transmit_in_current_slot(); 13 if (i is backlogged) 14 {slot_size=min(A,^ moa:) 15 while (hol_size(i)< slot_size) 16 {transmit hoi packet; Appendix B 161 17 slot_size=slot_size-hol_size(i);} 18 Di = Di - (min(A, Lmax)-slot_size);} 19 else /*session i is unbacklogged*/ 20 Di = Di - min (A, Lmax);} allocate_quanta() /*the basic quantum allocation mechanism*/ 21 if (session i is backlogged) 22 {if (session i can send) /*Case 1*/ 23 {if (session i is lagging or in-sync) 24 Df+ = Qi 25 else /*session i is leading*/ 26 {j=pick_lagging_session_from_WRR(); 27 if (j exists) 28 {Di + + = Qi - min(( l - a)Qi}\lagi\)\ 29 Dj + + = min(( l - a)Qu \lagA); 30 lagt+ = min(( l - a)Qu \lagi\); 31 ia97~ = min(( l - a)Qu \lagi\);} 32 else 33 Df+ - Qi}} 34 else /*session i cannot send (Case 2)*/ 35 {j=pickJagging_session_from_WRR(); 36 if (j doesn't exist) 37 {j=pick_leading_session(); 38 if (j doesn't exist) 39 {j=pick_in_sync-session ();}} 40 if (j doesn't exist) /*no session found*/ 41 wasted_quantum+ + = Qu Appendix B 162 42 else 43 {Dj + + = Qi, 45 44 lagf+ = Qi, lag]" = Qi;} 46 else /^ session i is unbacklogged (Case 3 and 4)*/ 47 {if(session i can send) 48 Di + + = Q^} interleaveO /*interleave the session transmissions in each frame*/ 49 for (all clean sessions) 50 num_slotSi = \Di/Lmax\, 51 for (all clean sessions) 52 {if (num_sloti ^ 0) 53 assign slot s to session i; 54 . num_slots^  ; 55 s + +;} 

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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065548/manifest

Comment

Related Items