A queueing network with a single cyclically roving server

A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation B_i, B _i ^* (s) service time of a customer at queue i and its LST - b_i, b_i ⁽²⁾ mean and second moment of B_i - R_i, R _i ^* (s) duration of switch-over period from queue i and its LST - r_i, r_i mean and second moment of R_i - r, r⁽²⁾ mean and second moment of _i ^N =₁R_i - _i external arrival rate of type-i customers - _i total arrival rate into queue i - _i utilization of queue i; _i=_i - system utilization _i ^N =_1i - c=E[C] the expected cycle length - X _i ^j number of customers in queue j when queue i is polled - X_i=X _i ⁱ number of customers residing in queue i when it is polled - f_i(j) - X _i ^* number of customers residing in queue i at an arbitrary moment - Y_i the duration of a service period of queue i - W_i,T_i the waiting time and sojourn time of an arbitary customer at queue i - F^*(z₁, z₂,..., z_N) GF of number of customers present at the queues at arbitrary moments - F_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at polling instants of queue i - ¯F_i(z₁, z₂,...,z_N) GF of number of customers present at the queues at switching instants of queue i - V_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at service initiation instants at queue i - ¯V_i(z₁,z₂,...,z_N) GF of number of customers present at the queues at service completion instants at queue i The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories.     

Waiting-Time Distributions in Polling Systems with Simultaneous Batch Arrivals

We study the delay in asymmetric cyclic polling models with general mixtures of gated and exhaustive service, with generally distributed service times and switch-over times, and in which batches of customers may arrive simultaneously at the different queues. We show that (1–)X _i converges to a gamma distribution with known parameters as the offered load tends to unity, where X _i is the steady-state length of queue i at an arbitrary polling instant at that queue. The result is shown to lead to closed-form expressions for the Laplace–Stieltjes transform (LST) of the waiting-time distributions at each of the queues (under proper scalings), in a general parameter setting. The results show explicitly how the distribution of the delay depends on the system parameters, and in particular, on the simultaneity of the arrivals. The results also suggest simple and fast approximations for the tail probabilities and the moments of the delay in stable polling systems, explicitly capturing the impact of the correlation structure in the arrival processes. Numerical experiments indicate that the approximations are accurate for medium and heavily loaded systems.     

Class dependent departure process from multiclass phase queues: Exact and approximate analyses

In this paper we study class dependent departure processes from phase type queues. When the arrival process for a subset of the classes is a Poisson process, we determine the Laplace-Stieltjes transform of the stationary inter-departure times of the combined output of all the other classes. We also propose and test approximations for the squared coefficient of variation of the stationary inter-departure times of each customer class. The approximations are based on the detailed structure of the second order measures of the aggregate departure process. Finally, we propose renewal approximations for the class dependent departure process that take into account the utilization of the queue that customers next visit.     

A single-server queue with batch arrivals and semi-Markov services

We investigate the transient and stationary queue length distributions of a class of service systems with correlated service times. The classical \(M^X/G/1\) queue with semi-Markov service times is the most prominent example in this class and serves as a vehicle to display our results. The sequence of service times is governed by a modulating process J(t). The state of \(J(\cdot )\) at a service initiation time determines the joint distribution of the subsequent service duration and the state of \(J(\cdot )\) at the next service initiation. Several earlier works have imposed technical conditions, on the zeros of a matrix determinant arising in the analysis, that are required in the computation of the stationary queue length probabilities. The imposed conditions in several of these articles are difficult or impossible to verify. Without such assumptions, we determine both the transient and the steady-state joint distribution of the number of customers immediately after a departure and the state of the process J(t) at the start of the next service. We numerically investigate how the mean queue length is affected by variability in the number of customers that arrive during a single service time. Our main observations here are that increasing variability may reduce the mean queue length, and that the Markovian dependence of service times can lead to large queue lengths, even if the system is not in heavy traffic.     

Stability of Earliest-Due-Date,First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, first-out queueing networks, where a customer's priority is given by its arrival time in the network, are a special case. Using fluid models, we show that EDDFS queueing networks, without preemption, are stable whenever the traffic intensity satisfies _j <1 for each station j.     

Exact Asymptotics for k i -limited Exponential Polling Models

In this paper we find exact asymptotic expressions for the event that the total queue length is large for a k _i -limited exponential polling model with equal service rates and two classes of customer. It is found that this behaviour divides into two very different regimes, depending on the arrival rates to the system. Using these exact asymptotic expressions, we provide heuristics for choosing the k _i values to provide a given level of quality of service to one class while giving best effort to the other class.     

The last departure time from an M t /G/∞ queue with a terminating arrival process

This paper studies the last departure time from a queue with a terminating arrival process. This problem is motivated by a model of two-stage inspection in which finitely many items come to a first stage for screening. Items failing first-stage inspection go to a second stage to be examined further. Assuming that arrivals at the second stage can be regarded as an independent thinning of the departures from the first stage, the arrival process at the second stage is approximately a terminating Poisson process. If the failure probabilities are not constant, then this Poisson process will be nonhomogeneous. The last departure time from an M _t /G/∞ queue with a terminating arrival process serves as a remarkably tractable approximation, which is appropriate when there are ample inspection resources at the second stage. For this model, the last departure time is a Poisson random maximum, so that it is possible to give exact expressions and develop useful approximations based on extreme-value theory.      

Control of arrivals in a finite buffered queue with setup costs

We consider finite buffered queues where the arrival process is controlled by shutting down and restarting the arrival stream. In the absence of holding costs for items in the queue, the optimal (s,?S) policy can be characterised by relating the arrival control problem to a corresponding service control problem. With the inclusion of holding costs however, this characterisation is not valid and efficient numerical computation of the queue length probability distribution is necessary. We perform this computation by using a duality property which relates queue lengths in the controlled arrival system to a controlled service system. Numerical results which analyse the effect of setup and holding costs and the variability of the arrival process on the performance of the system are included.     

Mean queue size in a queue with discrete autoregressive arrivals of order <Emphasis Type="Italic">p</Emphasis>

We consider a discrete time single server queueing system where the arrival process is governed by a discrete autoregressive process of order p (DAR(p)), and the service time of a customer is one slot. For this queueing system, we give an expression for the mean queue size, which yields upper and lower bounds for the mean queue size. Further we propose two approximation methods for the mean queue size. One is based on the matrix analytic method and the other is based on simulation. We show, by illustrations, that the proposed approximations are very accurate and computationally efficient.     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.     

Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

Transient analysis of queues with heterogeneous arrivals

In this paper we consider a discrete time queueing model where the time axis is divided into time slots of unit length. The model satisfies the following assumptions: (i) an event is either an arrival of typei of batch sizeb _i, i=1,...,r with probability _i or is a depature of a single customer with probability or zero depending on whether the queue is busy or empty; (ii) no more than one event can occur in a slot, therefore the probability that neither an arrival nor a departure occurs in a slot is 1––_{i i} or 1–_{i i} according as the queue is busy or empty; (iii) events in different slots are independent. Using a lattice path representation in higher dimensional space we will derive the time dependent joint distribution of the number of arrivals of various types and the number of completed services. The distribution for the corresponding continuous time model is found by using weak convergence.     

Heavy traffic limit for a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue is M/G/1 and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. We investigate the amount of work in the second queue at certain embedded arrival time points, namely when the upstream queue has just emptied. We focus on the case of infinite-variance service times and obtain a heavy traffic process limit for the embedded Markov chain.     

Cyclic Bernoulli polling

We introduce, analyse and optimize the class of Bernoulli random polling systems. The server movescyclically among N channels (queues), butChange-over times between stations are composed ofwalking times required to move from one channel to another andswitch-in times that are incurredonly when the server actually enters a station to render service. The server uses aBernoulli random mechanism to decide whether to serve a queue or not: upon arrival to channeli, it switches in with probabilityp _i , or moves on to the next queue (w.p. 1 —p _i ) without serving any customer (e.g. packet or job). The Cyclic Bernoulli Polling (CBP) scheme is independent of the service regime in any particular station, and may be applied to any service discipline. In this paper we analyse three different service disciplines under the CBP scheme: Gated, Partially Exhaustive and Fully Exhaustive. For each regime we derive expressions for (i) the generating functions and moments of the number of customers (jobs) at the various queues at polling instants, (ii) the expected number of jobs that an arbitrary departing job leaves behind it, and (iii) the LST and expectation of the waiting time of a cutomer at any given queue. The fact that these measures of performance can be explicitly obtained under the CBP is an advantage over all parameterized cyclic polling schemes (such as the k-limited discipline) that have been studied in the literature, and for which explicit measures of performance are hard to obtain. The choice of thep _i 's in the CBP allows for fine tuning and optimization of performance measures, as well as prioritization between stations (this being achieved at a low computational cost). For this purpose, we develop a Pseudo-conservation law for amixed system comprised of channels from all three service disciplines, and define a Mathematical Program to find the optimal values of the probabilities {p _i } _i ^N =1 so as to minimize the expected amount of unfinished work in the system. Any CBP scheme for which the optimalp _i 's are not all equal to one, yields asmaller amount of the expected unfinished work in the system than that in the standard cyclic polling procedure with equivalent parameters. We conclude by showing that even in the case of a single queue, it is not always true thatp ₁=1 is the best strategy, and derive conditions under which it is optimal to havep ₁ < 1.Supported by a Grant from the France-Israel Scientific Cooperation (in Computer Science and Engineering) between the French Ministry of Research and Technology and the Israeli Ministry of Science and Technology, Grant Number 3321190.     

Light traffic for workload in queues

General exact light traffic limit theorems are given for the distribution of steadystate workloadV, in open queueing networks having as input a general stationary ergodic marked point process {(t _n ,K _n )n0 (where t_n denotes the arrival time and K_n the routing and service times of the nth customer). No independence assumptions of any kind are required of the input. As the light traffic regime, it is only required that the Palm distribution for the exogenous interarrival time converges weakly to infinity (while the service mechanism is not allowed to change much). As is already known in the context of a single-server queue, work is much easier to deal with mathematically in light traffic than is customer delayD, and consequently, our results are far more general than existing results forD. We obtain analogous results for multi-channel and infinite-channel queues. In the context of open queueing networks, we handle both the total workload in the network as well as the workload at isolated nodes.Research supported in part by the Japan Society for the Promotion of Science during the author's fellowship in Tokyo, and by NSF Grant DDM 895 7825.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

On the multi-phase M/G/1 queueing system with random feedback

In this paper we consider an M/G/1 queue with k phases of heterogeneous services and random feedback, where the arrival is Poisson and service times has general distribution. After the completion of the i-th phase, with probability θ _i the (i + 1)-th phase starts, with probability p _i the customer feedback to the tail of the queue and with probability 1 − θ _i − p _i  = q _i departs the system if service be successful, for i = 1, 2 , . . . , k. Finally in kth phase with probability p _k feedback to the tail of the queue and with probability 1 − p _k departs the system. We derive the steady-state equations, and PGF’s of the system is obtained. By using them the mean queue size at departure epoch is obtained.     

Dynamic power control in a fading downlink channel subject to an energy constraint

A central controller chooses a state-dependent transmission rate for each user in a fading, downlink channel by varying transmission power over time. For each user, the state of the channel evolves over time according to an exogenous continuous-time Markov chain (CTMC), which affects the quality of transmission. The traffic for each user, arriving at the central controller, is modeled as a finite-buffer Markovian queue with adjustable service rates. That is, for each user data packets arrive to the central controller according to a Poisson process and packet size is exponentially distributed; an arriving packet is dropped if the associated buffer is full, which results in degradation of quality of service. The controller forwards (downlink) the arriving packets to the corresponding user according to an optimally chosen transmission rate from a fixed set A _i of available values for each user i, depending on the backlog in the system and the channel state of all users. The objective is to maximize quality of service subject to an upper bound on the long-run average power consumption. We show that the optimal transmission rate for each user is solely a function of his own packet queue length and channel state; the dependence among users is captured through a penalty rate. Further, we explicitly characterize the optimal transmission rate for each user. This project is partially supported by Motorola grant # 0970-350-AF24. The authors thank Phil Fleming,Randy Berry and Achal Bassamboo for helpful comments.     

The advantage of indices of dispersion in queueing approximations

A recent robust queueing approximation for open queueing networks exploits partial characterizations of each arrival process by its rate and index of dispersion for counts (IDC), which is a scaled version of the variance–time curve. Even though only means and variances (as functions of time) are involved, we show that the IDC provides a basis for more accurate approximations than traditional two-moment partial characterizations. For the $GI∕GI∕1$ queue, this approach applied to the arrival and service processes fully characterizes the model.