On extreme values in open queueing networks

This paper presents heavy traffic limit theorems for the extreme virtual waiting time of a customer in an open queueing network. In this paper, functional limit theorems are proved for extreme values of important probability characteristics of the open queueing network investigated as the maximum and minimum of the total virtual waiting time of a customer, and the maximum and minimum of the virtual waiting time of a customer. Also, the paper presents the previous related works for extreme values in queues and the virtual waiting time in heavy traffic.     

On the Full Idle Time in Multiphase Queueing Systems

The modern queueing theory is a powerful tool for a quantitative and qualitative analysis of communication systems, computer networks, transportation systems, and many other technical systems. The paper is designated to the analysis of queueing systems arising in the network theory and communications theory (such as the so-called multiphase queueing systems, tandem queues, or series of queueing systems). We present heavy traffic limit theorems for the full idle time in multiphase queueing systems. We prove functional limit theorems for values of the full idle time of a queueing system, which is its important probability characteristic. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 367–386, July–September, 2005.     

The Law of the Iterated Logarithm for Extreme Waiting Time in Multiphase Queueing Systems

The objective of this research in the queueing theory is the law of the iterated logarithm (LIL) under the conditions of heavy traffic in multiphase queueing systems (MQS). In this paper, the LIL is proved for the extreme values of some important probabilistic characteristics of the MQS, namely, maxima and minima of the summary waiting time of a customer, and maxima and minima of the waiting time of a customer.     

A Law of the Iterated Logarithm for Extreme Queue Length in Multiphase Queues

The object of this research in queueing theory is the Law of the Iterated Logarithm (LIL) under the conditions of heavy traffic in Multiphase Queueing Systems (MQS). In this paper, the LIL is proved for extreme values of important probabilistic characteristics of the MQS investigated as well as maxima and minima of the summary queue length of customers and maxima and minima of the queue length of customers. Also, the paper presents a survey on the works for extreme values in queues and the queues in heavy traffic.      

A Law of the Iterated Logarithm for the Sojourn Time Process in Queues in Series

The object of this research in the sphere of queueing theory is the law of the iterated logarithm under the conditions of heavy traffic in queues in series. In this paper, the laws of the iterated logarithm are proved for the values of important probabilistic characteristics of the queueing system, like the sojourn time of a customer, and maximum of the sojourn time of a customer. Also, we prove that the sojourn time of a customer can be approximated by some recurrent functional. We also provide the results of statistical simulations for various system parameters and distributions.     

A network of priority queues in heavy traffic: One bottleneck station

In this paper we consider an open queueing network having multiple classes, priorities, and general service time distributions. In the case where there is a single bottleneck station we conjecture that normalized queue length and sojourn time processes converge, in the heavy traffic limit, to one-dimensional reflected Brownian motion, and present expressions for its drift and variance. The conjecture is motivated by known heavy traffic limit theorems for some special cases of the general model, and some conjectured “Heavy Traffic Principles” derived from them. Using the known stationary distribution of one-dimensional reflected Brownian motion, we present expressions for the heavy traffic limit of stationary queue length and sojourn time distributions and moments. For systems with Markov routing we are able to explicitly calculate the limits.     

Heavy-traffic analysis of the sojourn time in a three node Jackson network with overtaking

We consider a Jackson network consisting of three first-in-first-out (FIFO)M/M/1 queues. When customers leave the first queue they can be routed to either the second or third queue. Thus, a customer that traverses the network by going from the first to the second to the third queue, can be overtaken by another customer that is routed from the first queue directly to the third. We study the distribution of the sojourn time of a customer through the three node network, in the heavy traffic limit. A three term heavy traffic asymptotic approximation to the sojourn time density is derived. The leading term shows that the nodes decouple in the heavy traffic limit. The next two terms, however, do show the dependence of the sojourn times at the individual nodes and give quantitative measures of the effects of overtaking.     

A survey of retrial queues

We present a survey of the main results and methods of the theory of retrial queues, concentrating on Markovian single and multi-channel systems. For the single channel case we consider the main model as well as models with batch arrivals, multiclasses, customer impatience, double connection, control devices, two-way communication and buffer. The stochastic processes arising from these models are considered in the stationary as well as the nonstationary regime. For multi-channel queues we survey numerical investigations of stationary distributions, limit theorems for high and low retrial intensities and heavy and light traffic behaviour.     

On the Analysis of the Virtual Waiting Time in Open Queueing Networks

The model of an open queueing network in heavy traffic has been developed. These models are mathematical models of computer networks in heavy traffic. A limit theorem has been presented for the virtual waiting time of a customer in heavy traffic in open queueing networks. Finally, we present an application of the theorem—a reliability model from computer network practice.     

饱和情形开排队网络的强逼近

本文用强逼近理论和斜反射定理，研究了饱和情形下的开排队网络，得到了队长、虚等待时间和顾客在网络中逗留时间的强逼近定理．     

Sojourn time problems in feedback queues

A brief survey of the literature on sojourn time problems in single node feedback queueing systems is presented. The derivation of the distribution and moments of the sojourn time of a typical customer in a Markov renewal queue with state dependent feedback is considered in depth. The techniques used relate to the derivation of a first passage time distribution in a particular Markov renewal process. These results are applied to birth-death queues with state dependent feedback. For such models an alternative approach using the theory of Markov chains in continuous time is also examined.     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

Steady state approximations of limited processor sharing queues in heavy traffic

We investigate steady state properties of limited processor sharing queues in heavy traffic. Our analysis builds on previously obtained process limit theorems, and requires the interchange of steady state and heavy traffic limits, which are established by a coupling argument. The limit theorems yield explicit approximations of the steady state queue length and response time distribution in heavy traffic, of which the quality is supported by simulation experiments.     

Compound Transient Phenomena in Multiphase Queuing Systems. III

The author continues the work on functional limit theorems in multiphase queuing systems (QS) under heavy traffic. In this paper there are proved theorems for the waiting time of a job when at phases of a system various conditions of heavy traffic are satisfied (compound transient phenomena).     

On the M_t/M_t/K_t+M_t queue in heavy traffic

The focus of this paper is on the asymptotics of large-time numbers of customers in time-periodic Markovian many-server queues with customer abandonment in heavy traffic. Limit theorems are obtained for the periodic number-of-customers processes under the fluid and diffusion scalings. Other results concern limits for general time-dependent queues and for time-homogeneous queues in steady state.     

Sojourn time distributions in the queue defined by a general QBD process

We consider a general QBD process as defining a FIFO queue and obtain the stationary distribution of the sojourn time of a customer in that queue as a matrix exponential distribution, which is identical to a phase-type distribution under a certain condition. Since QBD processes include many queueing models where the arrival and service process are dependent, these results form a substantial generalization of analogous results reported in the literature for queues such as the PH/PH/c queue. We also discuss asymptotic properties of the sojourn time distribution through its matrix exponential form.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.     

Convergence of a queueing system in heavy traffic with general patience-time distributions

We analyze a sequence of single-server queueing systems with impatient customers in heavy traffic. Our state process is the offered waiting time, and the customer arrival process has a state dependent intensity. Service times and customer patient-times are independent; i.i.d. with general distributions subject to mild constraints. We establish the heavy traffic approximation for the scaled offered waiting time process and obtain a diffusion process as the heavy traffic limit. The drift coefficient of this limiting diffusion is influenced by the sequence of patience-time distributions in a non-linear fashion. We also establish an asymptotic relationship between the scaled version of offered waiting time and queue-length. As a consequence, we obtain the heavy traffic limit of the scaled queue-length. We introduce an infinite-horizon discounted cost functional whose running cost depends on the offered waiting time and server idle time processes. Under mild assumptions, we show that the expected value of this cost functional for the n-th system converges to that of the limiting diffusion process as n tends to infinity.     

The MM CPP/GE/c G-Queue: Sojourn Time Distribution

We obtain the sojourn time probability distribution function at equilibrium for a Markov modulated, multi-server, single queue with generalised exponential (GE) service time distribution and compound Poisson arrivals of both positive and negative customers. Such arrival processes can model both burstiness and correlated traffic and are well suited to models of ATM and other telecommunication networks. Negative customers remove (ordinary) customers in the queue and are similarly correlated and bursty. We consider both the cases where negative customers remove positive customers from the front and the end of the queue and, in the latter case, where a customer currently being served can and cannot be killed by a negative customer. These cases can model an unreliable server or load balancing respectively. The results are obtained as Laplace transforms and can be inverted numerically. The MM CPP/GE/c G-Queue therefore holds the promise of being a viable building block for the analysis of queues and queueing networks with bursty, correlated traffic, incorporating load balancing and node-failures, since the equilibrium behaviour of both queue lengths and response times can be determined in a tractable way.