The heavy traffic limit of an unbalanced generalized processor sharing model

DOI10.1214/07-AAP438zbMATH Open1144.60056arXiv0801.3174OpenAlexW2092305220WikidataQ101947577 ScholiaQ101947577MaRDI QIDQ2476397FDOQ2476397

Authors: Kavita Ramanan, Martin I. Reiman 

Publication date: 19 March 2008

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: This work considers a server that processes $J$ classes using the generalized processor sharing discipline with base weight vector $alpha=(alph{a}_1,\mathrm{...},alph{a}_J)$ and redistribution weight vector $$. The invariant manifold $mathcalM$ of the so-called fluid limit associated with this model is shown to have the form $mathcalM=xinmathbb{R}_{+}^J:x_j=0forjinmathcalS$, where $mathcalS$ is the set of strictly subcritical classes, which is identified explicitly in terms of the vectors $alpha$ and $$ and the long-run average work arrival rates $gamm{a}_j$ of each class $j$. In addition, under general assumptions, it is shown that when the heavy traffic condition $su{m}_{j=1}^{J}gamm{a}_j=su{m}_{j=1}^{J}alph{a}_j$ holds, the functional central limit of the scaled unfinished work process is a reflected diffusion process that lies in $mathcalM$. The reflected diffusion limit is characterized by the so-called extended Skorokhod map and may fail to be a semimartingale. This generalizes earlier results obtained for the simpler, balanced case where $gamm{a}_j=alph{a}_j$ for $j=1,\mathrm{...},J$, in which case $mathcalM=mathbb{R}_{+}^J$ and there is no state-space collapse. Standard techniques for obtaining diffusion approximations cannot be applied in the unbalanced case due to the particular structure of the GPS model. Along the way, this work also establishes a comparison principle for solutions to the extended Skorokhod map associated with this model, which may be of independent interest.

Full work available at URL: https://arxiv.org/abs/0801.3174

Recommendations

• Fluid and heavy traffic diffusion limits for a generalized processor sharing model
• Generalized processor sharing queues with heterogeneous traffic classes
• Generalized processor sharing: Characterization of the admissible region and selection of optimal weights
• A reduced-load equivalence for generalised processor sharing networks with long-tailed input flows
• Asymptotic behavior of generalized processor sharing queues under subexponential assumptions

zbMATH Keywords

diffusion approximationinvariant manifoldqueueing networksgeneralized processor sharingfluid limitsHeavy traffic

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Functional limit theorems; invariance principles (60F17)

Cites Work

• Stochastic-Process Limits
• Title not available (Why is that?)
• Title not available (Why is that?)
• On lipschitz continuity of the solution mapping to the skorokhod problem, with applications
• Reflected Brownian motion on an orthant
• Stochastic discrete flow networks: Diffusion approximations and bottlenecks
• Title not available (Why is that?)
• Open Queueing Networks in Heavy Traffic
• Convex duality and the Skorokhod problem. II
• Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse
• State space collapse with application to heavy traffic limits for multiclass queueing networks
• Fluid and heavy traffic diffusion limits for a generalized processor sharing model
• Fluid model for a network operating under a fair bandwidth-sharing policy.
• An explicit formula for the Skorokhod map on \([0,a]\)
• Simple Necessary and Sufficient Conditions for the Stability of Constrained Processes
• A subsidy-surplus model and the Skorokhod problem in an orthant.
• On the strong solutions of one-dimensional stochastic differential equations with reflecting boundary
• Reflected diffusions defined via the extended Skorokhod map
• A Skorokhod problem formulation and large deviation analysis of a processor sharing model
• Generalized processor sharing queues with heterogeneous traffic classes
• A multiclass feedback queueing network with a regular Skorokhod problem
• A Heavy Traffic Limit Theorem for Networks of Queues with Multiple Customer Types

Cited In (21)

• Fluid and heavy traffic diffusion limits for a generalized processor sharing model
• Pathwise differentiability of reflected diffusions in convex polyhedral domains
• Two coupled queues with vastly different arrival rates: critical loading case
• Positive recurrence for reflecting Brownian motion in higher dimensions
• Characterization of stationary distributions of reflected diffusions
• Generalized processor sharing queues with heterogeneous traffic classes
• The Skorohod oblique reflection problem in time-dependent domains
• The Skorokhod problem in a time-dependent interval
• An explicit formula for the Skorokhod map on \([0,a]\)
• A reduced-load equivalence for generalised processor sharing networks with long-tailed input flows
• On directional derivatives of Skorokhod maps in convex polyhedral domains
• Stochastic variational inequalities with oblique subgradients
• Reflecting Brownian motion in generalized parabolic domains: explosion and superdiffusivity
• Explicit solutions of the extended Skorokhod problems in affine transformations of time-dependent strata
• Interacting queues in heavy traffic
• A Dirichlet process characterization of a class of reflected diffusions
• Sensitivity analysis for the stationary distribution of reflected Brownian motion in a convex polyhedral cone
• An ergodic control problem for many-server multiclass queueing systems with cross-trained servers
• On viscosity solution of HJB equations with state constraints and reflection control
• A heuristic flow-decomposition approach for generalized processor sharing under self-similar traffic
• A Monte Carlo Method for Estimating Sensitivities of Reflected Diffusions in Convex Polyhedral Domains

This page was built for publication: The heavy traffic limit of an unbalanced generalized processor sharing model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476397)