The heavy traffic limit of an unbalanced generalized processor sharing model

DOI10.1214/07-AAP438MaRDI QIDQ2476397zbMATH OpenOpenAlexWikidataFDO

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

diffusion approximation fluid limits generalized processor sharing Heavy traffic invariant manifold queueing networks

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

Abstract: This work considers a server that processes

J

classes using the generalized processor sharing discipline with base weight vector

a l p h a = (a l p h a_{1}, ..., a l p h a_{J})

and redistribution weight vector

. The invariant manifold

m a t h c a l M

of the so-called fluid limit associated with this model is shown to have the form

m a t h c a l M = x i n m a t h b b R_{+}^{J} : x_{j} = 0 f o r j i n m a t h c a l S

, where

m a t h c a l S

is the set of strictly subcritical classes, which is identified explicitly in terms of the vectors

a l p h a

and

and the long-run average work arrival rates

g a m m a_{j}

of each class

j

. In addition, under general assumptions, it is shown that when the heavy traffic condition

s u m_{j = 1}^{J} g a m m a_{j} = s u m_{j = 1}^{J} a l p h a_{j}

holds, the functional central limit of the scaled unfinished work process is a reflected diffusion process that lies in

m a t h c a l 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

g a m m a_{j} = a l p h a_{j}

for

j = 1, ..., J

, in which case

m a t h c a l M = m a t h b b 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.

Review text

Generalized Processor Sharing (GPS) is a scheduling discipline that is used to share a single processing among traffic from several sources. Given a single server that can process one unit of work per unit of time, and that is being shared by \(J\) \(\left( {1 < J < \infty } \right)\) sources, the information needed to implement the GPS policy is contained in the weight vector \(\alpha = (\alpha _1,\dots,\alpha _J )\). When all sources have a backlog of work, source \(j\) is allotted a fraction \(\alpha _j \) of the total capacity of the server. When some classes achieve no backlog by using less than their allotted capacity, the remaining service capacity of the server is split among the other sources in proportion to their \(\alpha _j \)'s. This redistribution is given by redistribution vector \(\beta = (\beta _1,\dots,\beta _J )\). The invariant manifold \(M\) of the so-called fluid limit associated with this model is identified explicitly in terms of the vectors \(\alpha \) and \(\beta \) and the long-range average work arrival rates \(\gamma _j \) of each source \(j\). In addition, under general assumption, it is shown that when the heavy traffic condition \(\sum\nolimits_{j = 1}^J {\gamma _j } = 1 = \sum\nolimits_{j = 1}^J {\alpha _j } \) holds, the functional central limit of the scaled unfinished work process is a reflected diffusion process that lies in \(M\).

Recommendations

Cites work

Cited in

(22)

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)