The heavy traffic limit of an unbalanced generalized processor sharing model

DOI10.1214/07-AAP438MaRDI QIDQ2476397zbMATHOpenAlexWikidataFDO

Authors Kavita Ramanan, Martin I. Reiman

Publication date 19 March 2008

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

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

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)

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.

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

Cites work

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

Cited in

(21)

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

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)