Elastic Threshold-based Admission Control for Qos ...

Elastic Threshold-based Admission Control for Qos ...

Elastic Threshold-based Admission Control for QoS Satisfaction in Wireless Networks with Reward Optimization for Multiple Priority Classes April 6, 2010 M. Conlan A. Moini Content Background Key QoS metrics for wireless cellular networks Call Admission Control (CAC) algorithms Elastic threshold-based CAC algorithm System model Performance model Analysis results

Comparison with other CAC algorithms Conclusions References Background Mobile wireless networks must increasingly carry multiple classes of services with distinct Quality of Service (QoS) requirements real-time multimedia services Standard voice calls Streaming video/audio non-real-time services SMS text messages Picture mail Email Network

providers need a method for optimizing the cumulative value of services they provided This presentation focuses on a threshold-based CAC algorithm which determines optimal threshold levels maximizing system reward while satisfying QoS constraints for multiple priority service classes Key QoS Performance Metrics Cellular Wireless Network Blocking probability of new calls Dropping probability of handoff calls a handoff occurs when a mobile user with an ongoing connection leaves current cell and enters another cell an ongoing connection may be dropped during a handoff due to

unavailability of wireless channels (insufficient bandwidth in new cell) QoS Constraints observed blocking probability should be less than the blocking probability threshold for each service class i Bih Btih Bin Btin You can reduce handoff-call-drop probability by rejecting new connection requests, thus increasing in new-call blocking probability. Call Admission Control (CAC) Mechanism

to regulate traffic volume in (wireless or wired) networks intended to ensure, or maintain, a certain level of quality of service work by regulating total utilized bandwidth, total number of calls, packets or data bits passing a specific point per unit time Extensively studied for single-class network traffic, such as voice (real-time) Threshold-based when a defined limit is reached or exceeded, new calls may be prohibited from entering the network until at least one current call terminates or prevent new calls from entering the network only if the resources of a particular type would be overburdened example: keep the dropping probability of handoff calls and/or the blocking probability of new calls lower than pre-specified thresholds

Partition-based algorithms partition system resources and allocate distinct partitioned resources to serve distinct service classes Priority-based regulation of calls according to priority descriptors Graceful degradation service quality of individual calls can deteriorate to a certain extent Call Admission Control (CAC)

Algorithms Threshold-based Algorithm Ogbonmwan, Li and Kazakos (2005) 3 threshold levels for a system with two service classes used to reserve channels for voice handoff calls, new voice calls, and data handoff calls threshold values are periodically reevaluated based on workload conditions Distributed CAC algorithm Haung and Ho (2002) partitions channel resources in each cell into three partitions: real-time calls partition non-real-time calls partition, and

shared partition used by both classes calls to share applies a threshold value to new calls to satisfy more stringent QoS requirements for handoff calls uses an iterative algorithm to estimate call arrival rates to each cell in the heterogeneous networks CAC Algorithms (cont.) Bandwidth Reservation and Reconfiguration Ye, Hou and Papavassilliou (2002) mechanism to facilitate handoff processes for multiple services Common Characteristics of CAC Algorithms Call admission decisions based on meeting or not exceeding a certain threshold levels

Example: keep dropping probability of handoff calls and/or blocking probability of new calls lower than pre-specified thresholds Handle QoS requirements without considering value issues associated with service classes, i.e., what value priority service classes will bring to a system Threshold-based CAC Algorithm Chen and Chen (2006) Assigns distinct, discrete thresholds to each service type Shares all available channels among all service classes to achieve higher utilization Leverages thresholds to limit traffic from lowpriority calls, hence reserving more bandwidth for high-priority calls Limitations:

suffers from use of discrete thresholds which cuts traffic from service classes abruptly and reject any further traffic How to select appropriate threshold level Elastic Threshold-based CAC Algorithm for Multiple Service Classes with Priorities Extends earlier work by Chen et al. (2006) Utilizes two thresholds for each service class i: low threshold high threshold Rejects

a fraction of class i new service calls when low threshold is reached Rejects all class i new service calls once high threshold is reached CLAIM: Elastic Threshold-based CAC Algorithm produces optimal results! By allowing multiple service call types to share all channels and by limiting call arrivals of low-priority service classes, elastic threshold-based CAC algorithm produces optimal results: maximizes systems reward while meeting QoS requirements reward refers to any kind of value brought to the system due to services

example: revenue generates higher rewards compared to existing CACs Network Reward Function (assuming 2-priority service classes*) reward earned from servicing class i handoff calls per unit time reward earned from servicing class i new calls per unit time *: extensible to multiple service classes without loss of generality Service QoS Requirements

(assuming 2-priority service classes) QoS constraints are expressed in terms of blocking probability thresholds: Observed handoff dropping probability and new call blocking probability of class i generated by a CAC algorithm must not exceed the corresponding threshold probabilities. Blocking probability threshold for handoff calls Blocking probability threshold for new calls

System Model (Wireless Cellular Network) Each cell has C channels where C can vary depending on the available bandwidth in that cell When a call of service class i enters a handoff area from a neighboring cell, a handoff call request is generated Threshold is reached if accepting an incoming call will cause the number of channels used to exceed the threshold value. Each service call has its specific QoS requirement dictated by its service type attribute (e.g., real-time, non real-time) requires certain number of bandwidth

channels imposes system-wide QoS requirements Elastic Threshold-based CAC Algorithm for Multiple Service Classes with Priorities new call class i low threshold System high threshold handoff call class

i low threshold high threshold rejects a fraction of class i new calls when is reached and rejects all class i new calls when is reached starts blocking a fraction of class i handoff calls when is reached and blocks all class i handoff calls when is passed. Elastic Threshold-based CAC

Algorithm for 2-priority Service Classes* *: extensible to multiple service classes without loss of generality Elastic Threshold-based CAC Algorithm for 2-priority Service Classes Low threshold is triggered if a new lowpriority class 2 call arrives when the number of channels used by the system is greater than by . CAC then starts rejecting a fraction of (class 2) call arrivals until a class 2 a new call arrival

causes the number of channels being used exceed the high threshold Once the high threshold of new calls is reached, the system rejects all class 2 new calls. Elastic Threshold-based CAC Call Admission Probabilities n : total number of channels allocated in the system Prob. of accepting a new call of service class i

Prob. of accepting a hand-off call of service class i ki : number of channels required by a service call SPN Model for Elastic Thresholdbased CAC SPN Model for Elastic Thresholdbased CAC Places Transitions *

: * : SPN Model for Elastic Threshold CAC Transitions Enabling Predicates : : SPN Model for Elastic Threshold CAC Arrival Rates if =

if 0 if is disabled. if = if 0 if is disabled. SPN Model Parameters Blocking/dropping probabilities as a function of

arrival rate: Reward earned per unit time, per cell V : assigned reward per reward earned from servicing class i handoff calls per unit time reward earned from servicing class i new calls per unit time i call for service class i (no distinction between new and handoff calls)

Finding Optimal Threshold Combination Challenge: find a set of threshold levels that provide legitimate solution Two-step process Step I : finding a legitimate solution Step II: determining a locally optimal solution by applying a greedy search starting from the legitimate solution found in Step I Finding a legitimate solution Method I : set all thresholds at max capacity (C) and

incrementally reduce low threshold, in reverse priority order, until legitimate solution is found Method II: start with all thresholds set to minimum channel size required to support the QoS constraints and incrementally increase until legitimate solution is found (invoked only if 1st method fails). Next perturb threshold levels using a greedy search algorithm to optimize reward while satisfying QoS requirements Check adjacent threshold levels (current threshold ) for values with higher reward, if any. legitimate solution : maximizes reward per unit time while satisfying QoS Comparison of Elastic Thresholdbased with other CAC Algorithms Model and analyze wireless cellular network performance using simulation Apply competing CAC algorithms to measure system QoS and reward rate performance

threshold-based partition spillover elastic threshold-based Consider two distinct priority service classes real-time (e.g. video) and non real-time (e.g. voice) each service type requires a number of bandwidth channels to satisfy its bandwidth QoS requirement handoff calls have a higher priority than new calls Simulated Wireless Cellular Network with Wrap-around Structure

6 adjacent cells 1024 users Random destination Random speed Random pause time Simulation Parameters new call blocking probability handoff call blocking probability for each service class i (i =1,2) Reward Rate vs. Number of Mobile Units

Elastic threshold-based CAC algorithm produced highest reward. QoS of Call Admission Algorithms Elastic threshold-based CAC algorithm ensures QoS for more users. Conclusions Elastic threshold-based CAC algorithm is superior satisfies QoS requirements even in heavy load conditions generates high rewards despite increased traffic generated by high population leverages low threshold to regulate traffic (rejecting just a fraction of traffic) and the high threshold to

reject traffic generated by service calls outperforms existing CAC algorithms for QoS satisfaction and reward optimization is extensible to multiple priority service classes Threshold-based and spillover CAC algorithms perform reasonably well under moderate load Partitioning CAC algorithms perform poorly among all References 1. S.E. Ogbonmwan, W. Li, D. Kazakos, Multi-threshold bandwidth reservation scheme of an integrated voice/data wireless network, in: 2005 International Conference on Wireless Networks, Communications and Mobile Computing, Maui, Hawaii, June 2005, pp. 226231.

2. Y.-R. Haung, J.-M. Ho, Distributed call admission control for a heterogeneous PCS network, IEEE Transactions on Computers 51 (2002), 14001409. 3. J. Ye, J. Hou, S. Papavassilliou, A comprehensive resource management for next generation wireless networks, IEEE Transactions on Mobile Computing 1 (4) (2002) 249263. 4. I.R. Chen, C.M. Chen, Threshold-based admission control policies for multimedia servers, The Computer Journal 39 (9) (1996) 757 766. 5.

O. Yilmaz and I.R. Chen, "Elastic threshold-based admission control for QoS satisfaction with reward optimization for servicing multiple priority classes in wireless networks, Information Processing Letters, Vol. 109, No. 15, July 2009, pp. 868-875.

Recently Viewed Presentations

  • California State of the 4-H STEM Initiative

    California State of the 4-H STEM Initiative

    The need for scientific literacy. For economic prosperity and national security. For a functioning democracy. As preparation for life and work. Scientific literacy is an important societal issue, impacting our nation's economic prosperity and national security, and necessary for youth...
  • Prime Factorization - S S Sabol

    Prime Factorization - S S Sabol

    Factor. The numbers that are multiplied to get a product. 15 = 3 x 5. 3 and 5 are factors of 15. 2 x 9 = 18. 2 & 9 are factors of 18. 3 x 2 =6. 3 &...
  • Population Evolution - MS. SWISS AP BIOLOGY

    Population Evolution - MS. SWISS AP BIOLOGY

    Hardy Weinberg. Population: group of individuals of the same species, in the same area, that interbreed. Gene Pool: copies of every type of allele at every locus in all members of the population *Different from Punnett Squares- because we assume...
  • MEDIA: What is the role of this institution and how has it ...

    MEDIA: What is the role of this institution and how has it ...

    MEDIA: What is the role of this institution and how has it changed over time? Defining "media" First and second media age. The networked society
  • A possible generalized form of Jarzynski equality

    A possible generalized form of Jarzynski equality

    Fluctuation Theorem & Jarzynski Equality — new developments in nonequilibrium process Zhanchun Tu (涂展春) [email protected] Department of Physics Tamkang University Outline I. Introduction II. Fluctuation theorem (FT) & Jarzynski equality (JE) III. Generalized JE IV.
  • Selling xRM & SharePoint - download.microsoft.com

    Selling xRM & SharePoint - download.microsoft.com

    SharePoint - Informal Rules - Document Centric. Informal Rules. Formalized Processes. CRM - Formal Rules - Process Centric. Informal Rules. Formalized Processes. SharePoint - Enterprise Search. ... A rich client for SharePoint that allows you to take lists and libraries...
  • What can you remember about Emotivism? So what

    What can you remember about Emotivism? So what

    moral. imperatives. Secondly, and more importantly, Hare allows prescriptions that emerge from a fanatic culture that we would want to condemn. Prescriptivism appears to say that so long as people are consistent in putting forward horrific judgements then their consistency...
  • L'Atomo e le Molecole - fisicainweb.altervista.org

    L'Atomo e le Molecole - fisicainweb.altervista.org

    ELEMENTI E COMPOSTI da C22 a C33 Libro di testo "Osservare e capire la vita" N2 + O2 N2O N2 + O2 N2O3 N2 + O2 N2O5 28g 16g 44gV 28g 48g 76g 28g 80g 108g Fine I simboli degli...