共查询到20条相似文献,搜索用时 0 毫秒
1.
Towards better multi-class parametric-decomposition approximations for open queueing networks 总被引:1,自引:0,他引:1
Ward Whitt 《Annals of Operations Research》1994,48(3):221-248
Methods are developed for approximately characterizing the departure process of each customer class from a multi-class single-server queue with unlimited waiting space and the first-in-first-out service discipline. The model is (GT
i
/GI
i
)/1 with a non-Poisson renewal arrival process and a non-exponential service-time distribution for each class. The methods provide a basis for improving parametric-decomposition approximations for analyzing non-Markov open queueing networks with multiple classes. For example, parametric-decomposition approximations are used in the Queueing Network Analyzer (QNA). The specific approximations here extend ones developed by Bitran and Tirupati [5]. For example, the effect of class-dependent service times is considered here. With all procedures proposed here, the approximate variability parameter of the departure process of each class is a linear function of the variability parameters of the arrival processes of all the classes served at that queue, thus ensuring that the final arrival variability parameters in a general open network can be calculated by solving a system of linear equations. 相似文献
2.
Given a stochastic ordering between point processes, say that a p.p. N is smooth if it is less than the Poisson process with the same average intensity for this ordering. In this article we investigate
whether initially smooth processes retain their smoothness as they cross a network of FIFO ·/D/1 queues along fixed routes. For the so-called strong variability ordering we show that point processes remain smooth as
they proceed through a tandem of quasi-saturated (i.e., loaded to 1) M+·/D/1 queues. We then introduce the Large Deviations ordering, which involves comparison of the rate functions associated with
Large Deviations Principles satisfied by the point processes. For this ordering, we show that smoothness is retained when
the processes cross a feed-forward network of unsaturated ·/D/1 queues. We also examine the LD characteristics of a deterministic p.p. at the output of an M+·/D/1 queue.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
3.
This paper establishes functional central limit theorems describing the heavy-traffic behavior of open single-class queueing networks with service interruptions. In particular, each station has a single server which is alternatively up and down. There are two treatments of the up and down times. The first treatment corresponds to fixed up and down times and leads to a reflected Brownian motion, just as when there are no service interruptions, but with different parameters. To represent long rare interruptions, the second treatment has growing up and down times with the up and down times being of ordern andn
1/2, respectively, when the traffic intensities are of order 1-n–1/2. In this case we establish convergence in the SkorohodM
1 topology to a multidimensional reflection of multidimensional Brownian motion plus a multidimensional jump process. 相似文献
4.
State space collapse with application to heavy traffic limits for multiclass queueing networks 总被引:3,自引:0,他引:3
Heavy traffic limits for multiclass queueing networks are a topic of continuing interest. Presently, the class of networks
for which these limits have been rigorously derived is restricted. An important ingredient in such work is the demonstration
of state space collapse. Here, we demonstrate state space collapse for two families of networks, first-in first-out (FIFO)
queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply
our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks,
we employ law of large number estimates to show a form of compactness for appropriately scaled solutions. The limits of these
solutions are next shown to satisfy fluid model equations corresponding to the above queueing networks. Results from Bramson
[4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO
networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams
[41]. State space collapse and the ensuing heavy traffic limits also hold for more general queueing networks, provided the
solutions of their fluid model equations converge. Partial results are given for such networks, which include the static priority
disciplines.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
5.
Cheng -Shang Chang 《Queueing Systems》1995,20(1-2):7-36
Using the contraction principle, in this paper we derive a set of closure properties for sample path large deviations. These properties include sum, reduction, composition and reflection mapping. Using these properties, we show that the exponential decay rates of the steady state queue length distributions in an intree network with routing can be derived by a set of recursive equations. The solution of this set of equations is related to the recently developed theory of effective bandwidth for high speed digital networks, especially ATM networks. We also prove a conditional limit theorem that illustrates how a queue builds up in an intree network. 相似文献
6.
Robert Sh. Liptser 《Queueing Systems》1993,14(1-2):1-31
We consider a simple queueing model with one service station. The arrival and service processes have intensitiesa(N–Q
t) andNf(N
–1
Q
t), where Qt is the queue length,N is a large integer,a>0 andf(x) is a positive continuous function. We establish the large deviation principle for the sequence of the normalized queue length processq
N
t
=N
–1Qt,N1 for both light (a<f(0)) and heavy (af(0)) traffic and use this result for an investigation of ergodic properties ofq
N
t
,N 1. 相似文献
7.
In this paper a higher order approximation for single server queues and tandem queueing networks is proposed and studied. Different from the most popular two-moment based approximations in the literature, the higher order approximation uses the higher moments of the interarrival and service distributions in evaluating the performance measures for queueing networks. It is built upon the MacLaurin series analysis, a method that is recently developed to analyze single-node queues, along with the idea of decomposition using higher orders of the moments matched to a distribution. The approximation is computationally flexible in that it can use as many moments of the interarrival and service distributions as desired and produce the corresponding moments for the waiting and interdeparture times. Therefore it can also be used to study several interesting issues that arise in the study of queueing network approximations, such as the effects of higher moments and correlations. Numerical results for single server queues and tandem queueing networks show that this approximation is better than the two-moment based approximations in most cases. 相似文献
8.
A sequence of shortest queueing systems is considered in this paper. We give weak convergence theorems for the queue length and waiting time processes when the sequence of traffic intensities associated with the sequence of shortest queueing systems approaches the critical value (=1) at appropriate rates.Research supported by the National Natural Science Foundation of China. 相似文献
9.
Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse 总被引:3,自引:0,他引:3
Certain diffusion processes known as semimartingale reflecting Brownian motions (SRBMs) have been shown to approximate many
single class and some multiclass open queueing networks under conditions of heavy traffic. While it is known that not all
multiclass networks with feedback can be approximated in heavy traffic by SRBMs, one of the outstanding challenges in contemporary
research on queueing networks is to identify broad categories of networks that can be so approximated and to prove a heavy
traffic limit theorem justifying the approximation. In this paper, general sufficient conditions are given under which a heavy
traffic limit theorem holds for open multiclass queueing networks with head-of-the-line (HL) service disciplines, which, in
particular, require that service within each class is on a first-in-first-out (FIFO) basis. The two main conditions that need
to be verified are that (a) the reflection matrix for the SRBM is well defined and completely- S, and (b) a form of state space collapse holds. A result of Dai and Harrison shows that condition (a) holds for FIFO networks
of Kelly type and their proof is extended here to cover networks with the HLPPS (head-of-the-line proportional processor sharing)
service discipline. In a companion work, Bramson shows that a multiplicative form of state space collapse holds for these
two families of networks. These results, when combined with the main theorem of this paper, yield new heavy traffic limit
theorems for FIFO networks of Kelly type and networks with the HLPPS service discipline.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
10.
We consider a Skorohod map
which takes paths in
to paths which stay in the positive orthant
. We let
be the domain of definition of
. A convex and lower semi-continuous function
and a set
are given. We are concerned with the calculation of the infimum of the value
for t ⩾ 0 and absolutely continuous
subject to the conditions
and
. We show that such minimization problems characterize large deviation asymptotics of tail probabilities of the steady-state
distribution of certain reflected processes. We approximate the infimum by a sequence of finite-dimensional minimization problems.
This approximation allows to formulate an algorithm for the calculation of the infimum and to derive analytical bounds for
its value. Several applications are discussed including large deviations of generalized processor sharing and large deviations
of heavily loaded queueing networks.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
11.
Several exponential bounds are derived by means of the theory of large deviations for the convergence of approximate solutions of stochastic optimization problems. The basic results show that the solutions obtained by replacing the original distribution by an empirical distribution provides an effective tool for solving stochastic programming problems.Supported in part by a grant from the US-Israel Science Foundation. 相似文献
12.
关于大偏差概率的一个界 总被引:1,自引:1,他引:0
研究得到了关于随机和S(t)=∑N(t)i=1Xi,t≥0大偏差的幂的一个界,其中(N(t))t≥0是一族非负整值随机变量,(Xn)n∈N是独立同分布的随机变量,其共同的分布函数是F与(N(t))t≥0独立.本结论是在假设分布函数F的右尾属于ERV族的情况下得到的. 相似文献
13.
In this paper we consider a stochastic server (modeling a multiclass communication switch) fed by a set of parallel buffers.
The dynamics of the system evolve in discrete-time and the generalized processor sharing (GPS) scheduling policy of [25] is
implemented. The arrival process in each buffer is an arbitrary, and possibly autocorrelated, stochastic process. We obtain
a large deviations asymptotic for the buffer overflow probability at each buffer. In the standard large deviations methodology,
we provide a lower and a matching (up to first degree in the exponent) upper bound on the buffer overflow probabilities. We
view the problem of finding a most likely sample path that leads to an overflow as an optimal control problem. Using ideas
from convex optimization we analytically solve the control problem to obtain both the asymptotic exponent of the overflow
probability and a characterization of most likely modes of overflow. These results have important implications for traffic
management of high-speed networks. They extend the deterministic, worst-case analysis of [25] to the case where a detailed
statistical model of the input traffic is available and can be used as a basis for an admission control mechanism.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
14.
The generality and usefulness ofM/G/C/C state dependent queueing models for modelling pedestrian traffic flows is explored in this paper. We demonstrate that the departure process and the reversed process of these generalizedM/G/C/C queues is a Poisson process and that the limiting distribution of the number of customers in the queue depends onG only through its mean. Consequently, the models developed in this paper are useful not only for the analysis of pedestrian traffic flows, but also for the design of the physical systems accommodating these flows. We demonstrate how theM/G/C/C state dependent model is incorporated into the modelling of large scale facilities where the blocking probabilities in the links of the network can be controlled. Finally, extensions of this work to queueing network applications where blocking cannot be controlled are also presented, and we examine an approximation technique based on the expansion method for incorporating theseM/G/C/C queues in series, merge, and splitting topologies of these networks. 相似文献
15.
In this paper we review and extend the effective bandwidth results of Kelly [28], and Kesidis, Walrand and Chang [29, 6]. These results provide a framework for call admission schemes which are sensitive to constraints on the mean delay or the tail distribution of the workload in buffered queues. We present results which are valid for a wide variety of traffic streams and discuss their applicability for traffic management in ATM networks. We discuss the impact of traffic policing schemes, such as thresholding and filtering, on the effective bandwidth of sources. Finally we discuss effective bandwidth results for Brownian traffic models for which explicit results reveal the interaction arising in finite buffers. 相似文献
16.
We establish a sufficient condition for the existence of the (conventional) diffusion approximation for multiclass queueing networks under priority service disciplines. The sufficient condition relates to a sufficient condition for the weak stability of the fluid networks that correspond to the queueing networks under consideration. In addition, we establish a necessary condition for the network to have a continuous diffusion limit; the necessary condition is to require a reflection matrix (of dimension equal to the number of stations) to be completely-S. When applied to some examples, including generalized Jackson networks, single station multiclass queues, first-buffer-first-served re-entrant lines, a two-station Dai–Wang network and a three-station Dumas network, the sufficient condition coincides with the necessary condition. 相似文献
17.
Benjamin Melamed 《Stochastic Processes and their Applications》1982,13(2):227-234
This paper relates the reversibility of certain discrete state Markovian queueing networks — the class of quasi-reversible networks — to the reversibility of the underlying switching process. Quasi-reversible networks are characterized by a product form equilibrium state distribution.When the state can be represented by customer totals at each node, the reversibility of the state process is equivalent to the reversibility of the switching process. More complicated quasi-reversible networks require additional conditions, to ensure the reversibility of the network state process. 相似文献
18.
This paper presents a three-step procedure which allows to approximate the queue-length and the busy-time processes associated
with open queueing networks. These three approximations are based on reflection mappings and are introduced with explicit
estimates of their accuracy. The third one may be treated as approximation by accompanying reflection Brownian motions with
rates of convergence.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
19.
《Operations Research Letters》2021,49(1):76-80
We provide an example of a strictly subcritical multiclass queueing network which is unstable under the least attained service (LAS) service protocol. It is a reentrant line with two servers and six customer classes. The customer interarrival times in our system are bounded below and have finite exponential moments, while the corresponding service times are deterministic. As a special case, we obtain a deterministic, strictly subcritical unstable LAS network. 相似文献
20.
This paper is concerned with Brownian system models that arise as heavy traffic approximations for open queueing networks. The focus is on model formulation, and more specifically, on the formulation of Brownian models for networks with complex routing. We survey the current state of knowledge in this dynamic area of research, including important open problems. Brownian approximations culminate in estimates of complete distributions; we present numerical examples for which complete sojourn time distributions are estimated, and those estimates are compared against simulation. 相似文献