Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDiffusion limits of limited processor sharing queues
169
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider a processor sharing queue where the number of jobs served at any time is limited to $K$, with the excess jobs waiting in a buffer. We use random counting measures on the positive axis to model this system. The limit of this measure-valued process is obtained under diffusion scaling and heavy traffic conditions. As a consequence, the limit of the system size process is proved to be a piece-wise reflected Brownian motion.
rate research
Read More
The paper studies approximations and control of a processor sharing (PS) server where the service rate depends on the number of jobs occupying the server. The control of such a system is implemented by imposing a limit on the number of jobs that can share the server concurrently, with the rest of the jobs waiting in a first-in-first-out (FIFO) buffer. A desirable control scheme should strike the right balance between efficiency (operating at a high service rate) and parallelism (preventing small jobs from getting stuck behind large ones). We employ the framework of heavy-traffic diffusion analysis to devise near optimal control heuristics for such a queueing system. However, while the literature on diffusion control of state-dependent queueing systems begins with a sequence of systems and an exogenously defined drift function, we begin with a finite discrete PS server and propose an axiomatic recipe to explicitly construct a sequence of state-dependent PS servers which then yields a drift function. We establish diffusion approximations and use them to obtain insightful and closed-form approximations for the original system under a static concurrency limit control policy. We extend our study to control policies that dynamically adjust the concurrency limit. We provide two novel numerical algorithms to solve the associated diffusion control problem. Our algorithms can be viewed as average cost iteration: The first algorithm uses binary-search on the average cost and can find an $epsilon$-optimal policy in time $Oleft( log^2 frac{1}{epsilon} right)$; the second algorithm uses the Newton-Raphson method for root-finding and requires $Oleft( log frac{1}{epsilon} loglog frac{1}{epsilon}right)$ time. Numerical experiments demonstrate the accuracy of our approximation for choosing optimal or near-optimal static and dynamic concurrency control heuristics.
A many-server queueing system is considered in which customers with independent and identically distributed service times enter service in the order of arrival. The state of the system is represented by a process that describes the total number of customers in the system, as well as a measure-valued process that keeps track of the ages of customers in service, leading to a Markovian description of the dynamics. Under suitable assumptions, a functional central limit theorem is established for the sequence of (centered and scaled) state processes as the number of servers goes to infinity. The limit process describing the total number in system is shown to be an Ito diffusion with a constant diffusion coefficient that is insensitive to the service distribution. The limit of the sequence of (centered and scaled) age processes is shown to be a Hilbert space valued diffusion that can also be characterized as the unique solution of a stochastic partial differential equation that is coupled with the Ito diffusion. Furthermore, the limit processes are shown to be semimartingales and to possess a strong Markov property.
In this paper, we analyse a single server polling model with two queues. Customers arrive at the two queues according to two independent Poisson processes. There is a single server that serves both queues with generally distributed service times. The server spends an exponentially distributed amount of time in each queue. After the completion of this residing time, the server instantaneously switches to the other queue, i.e., there is no switch-over time. For this polling model we derive the steady-state marginal workload distribution, as well as heavy traffic and heavy tail asymptotic results. Furthermore, we also calculate the joint queue length distribution for the special case of exponentially distributed service times using singular perturbation analysis.
This work considers a many-server queueing system in which customers with i.i.d., generally distributed service times enter service in the order of arrival. The dynamics of the system is represented in terms of a process that describes the total number of customers in the system, as well as a measure-valued process that keeps track of the ages of customers in service. Under mild assumptions on the service time distribution, as the number of servers goes to infinity, a law of large numbers (or fluid) limit is established for this pair of processes. The limit is characterised as the unique solution to a coupled pair of integral equations, which admits a fairly explicit representation. As a corollary, the fluid limits of several other functionals of interest, such as the waiting time, are also obtained. Furthermore, in the time-homogeneous setting, the fluid limit is shown to converge to its equilibrium. Along the way, some results of independent interest are obtained, including a continuous mapping result and a maximality property of the fluid limit. A motivation for studying these systems is that they arise as models of computer data systems and call centers.
This work considers a server that processes $J$ classes using the generalized processor sharing discipline with base weight vector $alpha=(alpha _1,...,alpha_J)$ and redistribution weight vector $beta=(beta_1,...,beta_J)$. The invariant manifold $mathcal{M}$ of the so-called fluid limit associated with this model is shown to have the form $mathcal{M}={xinmathbb{R}_+^J:x_j=0 for jinmathcal{S}}$, where $mathcal{S}$ is the set of strictly subcritical classes, which is identified explicitly in terms of the vectors $alpha$ and $beta$ and the long-run average work arrival rates $gamma_j$ of each class $j$. In addition, under general assumptions, it is shown that when the heavy traffic condition $sum_{j=1}^Jgamma_j=sum_{j=1}^Jalpha_j$ holds, the functional central limit of the scaled unfinished work process is a reflected diffusion process that lies in $mathcal{M}$. 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 $gamma_j=alpha_j$ for $j=1,...,J$, in which case $mathcal{M}=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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
