Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(11)
Asymptotic Optimality
Heavy Traffic
Limit Theorem
multiclass queueing network
Queueing Network
Queueing System
Satisfiability
State Space Collapse
Stochastic Process
First Order
Process Network
Related Publications
(6)
Maximum Pressure Policies in Stochastic Processing Networks
State space collapse with application to heavy traffic limits for multiclass queueing networks
Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discretereview p
A scheduling policy with maximal stability region for ring networks with spatial reuse
Performance Evaluation and Policy Selection in Multiclass Networks
Subscribe
Academic
Publications
ASYMPTOTIC OPTIMALITY OF MAXIMUM PRESSURE POLICIES IN STOCHASTIC PROCESSING NETWORKS1
ASYMPTOTIC OPTIMALITY OF MAXIMUM PRESSURE POLICIES IN STOCHASTIC PROCESSING NETWORKS1,Informs Journal on Computing,J. G. DAI,WUQIN LIN
Edit
ASYMPTOTIC OPTIMALITY OF MAXIMUM PRESSURE POLICIES IN STOCHASTIC PROCESSING NETWORKS1
(
Citations: 13
)
BibTex

RIS

RefWorks
Download
J. G. DAI
,
WUQIN LIN
We consider a class of stochastic processing networks. Assume that the networks satisfy a complete resource pooling condition. We prove that each maximum pressure policy asymptotically minimizes the workload process in a stochastic processing network in heavy traffic. We also show that, under each quadratic holding cost structure, there is a maximum pressure policy that asymptotically minimizes the holding cost. A key to the optimality proofs is to prove a
state space collapse
result and a
heavy traffic
limit theorem
for the network processes under a maximum pressure policy. We extend a frame work of Bramson (Queueing Systems Theory Appl. 30 (1998) 89148) and Williams (Queueing Systems Theory Appl. 30 (1998b) 525) from the multi class
queueing network
setting to the stochastic processing network setting to prove the
state space collapse
result and the
heavy traffic
limit theorem. The extension can be adapted to other studies of stochastic processing networks. 1. Introduction. This paper is a continuation of Dai and Lin (2005), in which maximum pressure policies are shown to be throughput optimal for a class of sto chastic processing networks. Throughput optimality is an important, firstorder objective for many networks, but it ignores some key secondary performance mea sures like queueing delays experienced by jobs in these networks. In this paper we show that maximum pressure policies enjoy additional optimality properties; they are asymptotically optimal in minimizing a certain workload or holding cost of a stochastic processing network. Stochastic processing networks have been introduced in a series of three papers by Harrison (2000, 2002, 2003). In Dai and Lin (2005) and this paper we consider a special class of Harrison's model. This class of stochastic processing networks is much more general than multiclass queueing networks that have been a subject of intensive study in the last 20 years; see, for example, Harrison (1988), Williams
Journal:
Informs Journal on Computing  INFORMS
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www2.isye.gatech.edu
)
(
www.kellogg.northwestern.edu
)
Citation Context
(9)
...Recent results of Dai and Lin [7,
8
] and Ata and Lin [3] show that with the use of a maximum pressure policy, ( ^ Qn 1 (t);:::; ^ Q n 4 (t)); converges to a 4 dimensional reected Brownian motion which is actually lifted from a 2 dimensional workload process...
...Most surprisingly, as ! 1 the correlation approaches 1, and we are close to complete resource pooling [
8
]...
Yoni Nazarathy
,
et al.
Positive Harris recurrence and diffusion scale analysis of a push pull...
...It has been shown in [
4
] that the maximumpressure policy (similar to the backpressure policy) minimizes the workload process for a stochastic processing network in the heavy traffic regime when processor splitting is allowed...
Gagan Rajesh Gupta
,
et al.
Delay Analysis for MultiHop Wireless Networks
...(3) Maximum Pressure policies for stochastic processing networks as described in Dai and Lin (2005), see also
Dai and Lin (2006)
...
...They were further studied in the more general framework of stochastic processing networks (introduced by Harrison (2000, 2001, 2002)) in
Dai and Lin (2005, 2006)
...
Yoni Nazarathy
,
et al.
Near optimal control of queueing networks over a finite time horizon
...A more general stochastic network is considered for heavy traffic analysis in [
7
], again without considering signaling complexity...
...We refer the readers to [2,
7
, 19, 21, 22] for the similar CRP condition in other types of networks...
Yung Yi
,
et al.
Delay and effective throughput of wireless scheduling in heavy traffic...
...We will consider two policies for the KSRS network: The affine switching curve policy of Henderson, Meyn, and Tadic [20] (see also [5, 25]) and the max pressure policy of Dai and Lin [7,
8
]( see also [29, 30])...
Anat Kopzon
,
et al.
A PushPull Network with Infinite Supply of Work
References
(49)
State space collapse with application to heavy traffic limits for multiclass queueing networks
(
Citations: 110
)
Maury Bramson
Journal:
Queueing Systems  Theory and Applications  QUESTA
, vol. 30, no. 12, pp. 89148, 1998
Two Workload Properties for Brownian Networks
(
Citations: 20
)
Maury Bramson
,
R. J. Williams
Journal:
Queueing Systems  Theory and Applications  QUESTA
, vol. 45, no. 3, pp. 191221, 2003
Diffusion Approximations for Some Multiclass Queueing Networks with FIFO Service Disciplines
(
Citations: 16
)
Hong Chen
,
Hanqin Zhang
Journal:
Mathematics of Operations Research  MOR
, vol. 25, no. 4, pp. 679707, 2000
Matching Output Queueing with a Combined Input Output Queued Switch
(
Citations: 328
)
Shangtse Chuang
,
Ashish Goel
,
Nick Mckeown
,
Balaji Prabhakar
Conference:
IEEE INFOCOM  INFOCOM
, vol. 3, pp. 11691178, 1999
On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach Via Fluid Limit Models
(
Citations: 384
)
J. G. Dai
Journal:
Annals of Applied Probability  ANN APPL PROBAB
, vol. 5, no. 1995, pp. 4977, 1995
Sort by:
Citations
(13)
Positive Harris recurrence and diffusion scale analysis of a push pull queueing network
(
Citations: 4
)
Yoni Nazarathy
,
Gideon Weiss
Journal:
Performance Evaluation  PE
, vol. 67, no. 4, pp. 201217, 2010
Delay Analysis for MultiHop Wireless Networks
(
Citations: 21
)
Gagan Rajesh Gupta
,
Ness B. Shroff
Conference:
IEEE INFOCOM  INFOCOM
, pp. 23562364, 2009
Stability and Asymptotic Optimality of Generalized MaxWeight Policies
(
Citations: 8
)
Sean P. Meyn
Journal:
Siam Journal on Control and Optimization  SIAM
, vol. 47, no. 6, pp. 32593294, 2009
Stable and utilitymaximizing scheduling for stochastic processing networks
(
Citations: 5
)
Libin Jiang
,
Jean Walrand
Conference:
Annual Allerton Conference on Communication, Control, and Computing  Allerton
, 2009
Near optimal control of queueing networks over a finite time horizon
(
Citations: 6
)
Yoni Nazarathy
,
Gideon Weiss
Journal:
Annals of Operations Research  Annals OR
, vol. 170, no. 1, pp. 233249, 2009