共查询到20条相似文献,搜索用时 15 毫秒
1.
We consider a model of a multipath routing system where arriving customers are routed to a set of identical, parallel, single
server queues according to balancing policies operating without state information. After completion of service, customers
are required to leave the system in their order of arrival, thus incurring an additional resequencing delay. We are interested
in minimizing the end-to-end delay (including time at the resequencing buffer) experienced by arriving customers. To that
end we establish the optimality of the Round–Robin routing assignment in two asymptotic regimes, namely heavy and light traffic:
In heavy traffic, the Round–Robin customer assignment is shown to achieve the smallest (in the increasing convex stochastic
ordering) end-to-end delay amongst all routing policies operating without queue state information. In light traffic, and for
the special case of Poisson arrivals, we show that Round–Robin is again an optimal (in the strong stochastic ordering) routing
policy. We illustrate the stochastic comparison results by several simulation examples.
The work of the first author was supported through an ARCHIMEDES grant by the Greek Ministry of Education.
The work of the second author was prepared through collaborative participation in the Communications and Networks Consortium
sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement
DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding
any copyright notation thereon. The views and conclusions contained in this document are those of the authors and should not
be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the
U.S. Government. 相似文献
2.
We consider the finite capacity M/M/1−K queue with a time dependent arrival rate λ(t). Assuming that the capacity K is large and that the arrival rate varies slowly with time (as t/K), we construct asymptotic approximations to the probability of finding n customers in the system at time t, as well as the mean number. We consider various time ranges, where the system is nearly empty, nearly full, or is filled to a fraction of its capacity. Extensive numerical studies are used to back up the asymptotic analysis. 相似文献
3.
JIN Yang & AN Hongzhi School of Statistics Renmin University of China Beijing China Academy of Mathematics Systems Science Chinese Academy of Sciences Beijing China 《中国科学A辑(英文版)》2005,48(3):333-340
In this paper, we discuss the relationship between the stationary marginal tail probability and the innovation's tail probability of nonlinear autoregressive models. We show that under certain conditions that ensure the stationarity and ergodicity, one dimension stationary marginal distribution has the heavy-tailed probability property with the same index as that of the innovation's tail probability. 相似文献
4.
5.
《Indagationes Mathematicae》2023,34(5):990-1013
We investigate Markovian queues that are examined by a controller at random times determined by a Poisson process. Upon examination, the controller sets the service speed to be equal to the minimum of the current number of customers in the queue and a certain maximum service speed; this service speed prevails until the next examination time. We study the resulting two-dimensional Markov process of queue length and server speed, in particular two regimes with time scale separation, specifically for infinitely frequent and infinitely long examination times. In the intermediate regime the analysis proves to be extremely challenging. To gain further insight into the model dynamics we then analyse two variants of the model in which the controller is just an observer and does not change the speed of the server. 相似文献
6.
7.
We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting
a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this
class, we first show that if the tail of the service time distribution of one server, say server i
0 ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until
the completion of service at server j ⩾ i
0 asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i
0. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically
tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d.
driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics
are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the
excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and
the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat
more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class
of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that
the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension
of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
8.
9.
The impact of a heavy-tailed service-time distribution upon the M/GI/s waiting-time distribution 总被引:1,自引:0,他引:1
By exploiting an infinite-server-model lower bound, we show that the tails of the steady-state and transient waiting-time
distributions in the M/GI/s queue with unlimited waiting room and the first-come first-served discipline are bounded below
by tails of Poisson distributions. As a consequence, the tail of the steady-state waiting-time distribution is bounded below
by a constant times the sth power of the tail of the service-time stationary-excess distribution. We apply that bound to show
that the steady-state waiting-time distribution has a heavy tail (with appropriate definition) whenever the service-time distribution
does. We also establish additional results that enable us to nearly capture the full asymptotics in both light and heavy traffic.
The difference between the asymptotic behavior in these two regions shows that the actual asymptotic form must be quite complicated.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
10.
We consider Kelly networks with shuffling of customers within each queue. Specifically, each arrival, departure or movement
of a customer from one queue to another triggers a shuffle of the other customers at each queue. The shuffle distribution
may depend on the network state and on the customer that triggers the shuffle. We prove that the stationary distribution of
the network state remains the same as without shuffling. In particular, Kelly networks with shuffling have the product form.
Moreover, the insensitivity property is preserved for symmetric queues.
相似文献
11.
J. A. Morrison 《Queueing Systems》1993,14(1-2):215-237
In this paper the steady-state behavior of many symmetric queues, under the head of the line processor-sharing discipline, is investigated. The arrival process to each of n queues is Poisson, with rateA, and each queue hasr waiting spaces. A job arriving at a full queue is lost. The queues are served by a single exponential server, which has a mean raten, and splits its capacity equally amongst the jobs at the head of each nonempty queue. The normal traffic casep=/< 1 is considered, and it is assumed thatn1 andr= 0(1). A 2-term asymptotic approximation to the loss probabilityL is derived, and it is found thatL = 0(n
–r
), for fixedp. If6=(1–p)/p 1, then the approximation is valid if n2 1 and (r+ 1)2n, and in this caseL r!/(n)r. Numerical values ofL are obtained forr = 1,2,3,4 and 5,n = 1000,500 and 200, and various values ofp< 1. Very small loss probabilities may be obtained with appropriate values of these parameters. 相似文献
12.
Jiyeon Lee 《Operations Research Letters》2004,32(3):265-272
We consider the probability that the total population of a Jackson network exceeds a given large value. By using the relation to the stationary distribution, we derive upper and lower bounds on this probability. These bounds imply a stronger logarithmic limit when multiple nodes have the same maximal load. 相似文献
13.
The ruin probability of the renewal model with constant interest force and negatively dependent heavy-tailed claims 总被引:2,自引:0,他引:2
Recently, Tang [Tang, Q., 2005a. Asymptotic ruin probabilities of the renewal model with constant interest force and regular variation. Scand. Actuar. J. (1), 1–5] obtained a simple asymptotic formula for the ruin probability of the renewal risk model with constant interest force and regularly varying tailed claims. In this paper, we use a completely different approach to extend Tang’s result to the case in which the claims are pairwise negatively dependent and extended regularly varying tailed. 相似文献
14.
In this paper we study queueing networks which allow multiple changes at a given time. The model has a natural application
to discrete-time queueing networks but describes also queueing networks in continuous time.
It is shown that product-form results which are known to hold when there are single changes at a given instant remain valid
when multiple changes are allowed. 相似文献
15.
In this article, the dependent steps of a negative drift random walk are modelled as a two-sided linear process Xn =-μ ∞∑j=-∞ψn-jεj, where {ε, εn; -∞< n < ∞}is a sequence of independent, identically distributed random variables with zero mean, μ>0 is a constant and the coefficients {ψi;-∞< i <∞} satisfy 0 <∞∑j=-∞|jψj| <∞. Under the conditions that the distribution function of |ε| has dominated variation and ε satisfies certain tail balance conditions, the asymptotic behavior of P{supn≥0(-nμ ∞∑j=-∞εjβnj) > x}is discussed. Then the result is applied to ultimate ruin probability. 相似文献
16.
We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy. 相似文献
17.
Bivariate regenerative Markov modulated queueing processes {I
n
,L
n
} are described. {I
n
} is the phase process, and {L
n
} is the level process. Increments in the level process have subexponential distributions. A general boundary behavior at
the level 0 is allowed. The asymptotic tail of the cycle maximum,
, during a regenerative cycle,
, and the asymptotic tail of the stationary random variable L
∞, respectively, of the level process are given and shown to be subexponential with L
∞ having the heavier tail.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
18.
PAN Jiazhu & WU Guangxu LMAM School of Mathematical Sciences Peking University Beijing China 《中国科学A辑(英文版)》2005,48(9):1169-1181
We study the tail probability of the stationary distribution of nonparametric non- linear autoregressive functional conditional heteroscedastic (NARFCH) model with heavy- tailed innovations.Our result shows that the tail of the stationary marginal distribution of an NARFCH series is heavily dependent on its conditional variance.When the innovations are heavy-tailed,the tail of the stationary marginal distribution of the series will become heavier or thinner than that of its innovations.We give some specific formulas to show how the increment or decrement of tail heaviness depends on the assumption on the con- ditional variance function.Some examples are given. 相似文献
19.
20.
A general throughput property of tandem queueing networks with blocking that relates existing decomposition methods to throughput bounds is discussed using the sample path approach. 相似文献