Markov-modulated infinite-server queues driven by a common background process

This paper studies a system with multiple infinite-server queues that are modulated by a common background process. If this background process, being modeled as a finite-state continuous-time Markov chain, is in state j, then the arrival rate into the i-th queue is λ_{i, j}, whereas the service times of customers present in this queue are exponentially distributed with mean μ^{? 1}_{i, j}; at each of the individual queues all customers present are served in parallel (thus reflecting their infinite-server nature).

Three types of results are presented: in the first place (i) we derive differential equations for the probability-generating functions corresponding to the distributions of the transient and stationary numbers of customers (jointly in all queues), then (ii) we set up recursions for the (joint) moments, and finally (iii) we establish a central limit theorem in the asymptotic regime in which the arrival rates as well as the transition rates of the background process are simultaneously growing large.     

COMPUTATION OF STEADY-STATE PROBABILITIES FOR RESOURCE-SHARING CALL-CENTER QUEUEING SYSTEMS

Two routing rules for a queueing system of two stations are considered as alternative models for modeling a call-center network. These routing rules allow customers to switch queues under certain server and other resource availability conditions, either external to the system upon arrival to the network, or internal to the system after arrival to a primary call center. Under the assumption of Poisson arrivals and exponentially distributed service times, these systems are analyzed using matrix-geometric techniques, yielding a non-trivial set of ergodicity conditions and the steady-state joint probability distribution for the number of customers at each station. An extensive numerical analysis is conducted, yielding some physical insight into these systems and related generalizations.     

Matrix Product-Form Solutions for LCFs Preemptive Service Single-Server Queues with Batch Markovian Arrival Streams

ABSTRACT

This paper considers three variants of last-come first-served (LCFS) preemptive service single-server queues, where customers are served under the LCFS preemptive resume (LCFS-PR), preemptive repeat-different (LCFS-PD), and preemptive repeat-identical (LCFS-PI) disciplines, respectively. These LCFS queues are fed by multiple batch Markovian arrival streams. Service times of customers from each arrival stream are generally distributed and their distributions may differ among different streams. For each of LCFS-PR, LCFS-PD, and LCFS-PI queues, we show that the stationary distribution of the queue string representing enough information to keep track of queueing dynamics has a matrix product-form solution. Further, this paper discusses the stability of LCFS-PD and LCFS-PI queues based on the busy cycle. Finally, by numerical experiment, we examine the impact of the variation of the service time distribution on the mean queue lengths for the three variants of LCFS queues.     

Multi-class M/PH/1 queues with deterministic impatience times

This article considers computational procedures for the waiting time and queue length distributions in stationary multi-class first-come, first-served single-server queues with deterministic impatience times. There are several classes of customers, which are distinguished by deterministic impatience times (i.e., maximum allowable waiting times). We assume that customers in each class arrive according to an independent Poisson process and a single server serves customers on a first-come, first-served basis. Service times of customers in each class are independent and identically distributed according to a phase-type distribution that may differ for different classes. We first consider the stationary distribution of the virtual waiting time and then derive numerically feasible formulas for the actual waiting time distribution and loss probability. We also analyze the joint queue length distribution and provide an algorithmic procedure for computing the probability mass function of the stationary joint queue length.     

POLLING SYSTEMS WITH SIMULTANEOUS BATCH ARRIVALS

We study the delay in polling systems with simultaneous batch arrivals. Arrival epochs are generated according to a Poisson process. At any arrival epoch, batches of customers may arrive simultaneously at the different queues, according to a general joint batch-size distribution. The server visits the queues in cyclic order, the service times and the switch-over times are generally distributed, and the service disciplines are general mixtures of gated and exhaustive service. We derive closed-form expressions for the expected delay at each of the queues when the load tends to unity (under proper scalings), in a general parameter setting. The results are strikingly simple and reveal explicitly how the expected delay depends on the system parameters, and in particular, on the batch-size distributions and the simultaneity of the batch arrivals. Moreover, the results suggest simple and fast-to-evaluate approximations for the expected delay in heavily loaded polling systems. Numerical experiments demonstrate that the approximations are highly accurate in medium and heavily loaded systems.     

Asymptotic Throughput in Discrete‐Time Cyclic Networks with Queue‐Length‐Dependent Service Rates

Abstract

For a discrete‐time closed cyclic network of single server queues whose service rates are non‐decreasing in the queue length, we compute the queue‐length distribution at each node in terms of throughputs of related networks. For the asymptotic analysis, we consider sequences of networks where the number of nodes grows to infinity, service rates are taken only from a fixed finite set of non‐decreasing sequences, the ratio of customers to nodes has a limit, and the proportion of nodes for each possible service‐rate sequence has a limit. Under these assumptions, the asymptotic throughput exists and is calculated explicitly. Furthermore, the asymptotic queue‐length distribution at any node can be obtained in terms of the asymptotic throughput. The asymptotic throughput, regarded as a function of the limiting customer‐to‐node ratio, is strictly increasing for ratios up to a threshold value (possibly infinite) and is constant thereafter. For ratios less than the threshold, the asymptotic queue‐length distribution at each node has finite moments of all orders. However, at or above the threshold, bottlenecks (nodes with asymptotically‐infinite mean queue length) do occur, and we completely characterize such nodes.     

An Exact Analysis of the Multi‐class M/M/k Priority Queue with Partial Blocking

Abstract

We consider a multi‐server queuing model with two priority classes that consist of multiple customer types. The customers belonging to one priority class customers are lost if they cannot be served immediately upon arrival. Each customer type has its own Poisson arrival and exponential service rate. We derive an exact method to calculate the steady state probabilities for both preemptive and nonpreemptive priority disciplines. Based on these probabilities, we can derive exact expressions for a wide range of relevant performance characteristics for each customer type, such as the moments of the number of customers in the queue and in the system, the expected postponement time and the blocking probability. We illustrate our method with some numerical examples.     

Simultaneous arrival of customers to two different queues and modeling dependence via copula approach

ABSTRACT

In classical queueing systems, a customer is allowed to wait only in one queue to receive the service. In practice, when there exist a number of queues rendering the same service, some customers may tend to simultaneously take turn in more than one queue with the aim to receive the service sooner and thus reduce their waiting time. In this article, we introduce such a model and put forward a methodology to deal with the situation. In this regard, we consider two queues and assume that if a customer, who has turn in both queues, receives the service from one of the queues, the other turn is automatically withdrawn. This circumstance for the model brings about some abandonment in each queue as some customers receive the service from the other one. We study the customer’s waiting time in the mentioned model, which is defined as the minimum of waiting times in both queues and obtain probability density function of this random variable. Our approach to obtain probability density function of each of the waiting time random variables is to rely on the existing results for the abandonment case. We examine the situation for the cases of independence and dependence of the waiting time random variables. The latter is treated via a copula approach.     

Subexponential asymptotics of the waiting time distribution in a single-server queue with multiple Markovian arrival streams

This paper considers subexponential asymptotics of the tail distributions of waiting times in stationary work-conserving single-server queues with multiple Markovian arrival streams, where all arrival streams are modulated by the underlying Markov chain with finite states and service time distributions may differ for different arrival streams. Under the assumption that the equilibrium distribution of the overall (i.e., customer-average) service time distribution is subexponential, a subexponential asymptotic formula is first shown for the virtual waiting time distribution, using a closed formula recently found by the author. Further when customers are served on a FIFO basis, the actual waiting time and sojourn time distributions of customers from respective arrival streams are shown to have the same asymptotics as the virtual waiting time distribution.     

Approximate queue length distribution of a discriminatory processor sharing queue with impatient customers

We consider a two-class processor sharing queueing system with impatient customers. The system operates under the discriminatory processor sharing (DPS) scheduling. The arrival process of each class customers is the Poisson process and the service requirement of a customer is exponentially distributed. The reneging rate of a customer is a constant. To analyze the performance of the system, we develop a time scale decomposition approach to approximate the joint queue-length distribution of each class customers. Via a numerical experiment, we show that the time scale decomposition approach gives a fairly good approximation of the queue-length distribution and the expected queue length.     

Functionals of Markovian Branching D-BMAPS

Abstract

We consider a stochastic system in which Markovian customer attribute processes are initiated at customer arrivals in a discrete batch Markovian arrival process (D-BMAP). We call the aggregate a Markovian branching D-BMAP. Each customer attribute process is an absorbing discrete time Markov chain whose parameters depend both on the phase transition, of the driving D-BMAP, and the number of arrivals taking place at the customer's arrival instant. We investigate functionals of Markovian branching D-BMAPs that may be interpreted as cumulative rewards collected over time for the various customers that arrive to the system, in the transient and asymptotic cases. This is achieved through the derivation of recurrence relations for expected values and Laplace transforms in the former case, and Little's law in the latter case.     

Filtering recursions for calculating likelihoods for queues based on inter-departure time data

We consider inference for queues based on inter-departure time data. Calculating the likelihood for such models is difficult, as the likelihood involves summing up over the (exponentially-large) space of realisations of the arrival process. We demonstrate how a likelihood recursion can be used to calculate this likelihood efficiently for the specific cases of M/G/1 and Er/G/1 queues. We compare the sampling properties of the mles to the sampling properties of estimators, based on indirect inference, which have previously been suggested for this problem.     

Workload Process,Waiting Times,and Sojourn Times in a Discrete Time MMAP[K]/SM[K]/1/FCFS Queue

Abstract

In this paper, we study the total workload process and waiting times in a queueing system with multiple types of customers and a first-come-first-served service discipline. An M/G/1 type Markov chain, which is closely related to the total workload in the queueing system, is constructed. A method is developed for computing the steady state distribution of that Markov chain. Using that steady state distribution, the distributions of total workload, batch waiting times, and waiting times of individual types of customers are obtained. Compared to the GI/M/1 and QBD approaches for waiting times and sojourn times in discrete time queues, the dimension of the matrix blocks involved in the M/G/1 approach can be significantly smaller.     

A computational algorithm for the loss probability in the M/G/1+PH queue

This article develops a computational algorithm for the loss probability in the stationary M/G/1 queue with impatient customers whose impatience times follow a phase-type distribution (M/G/1+PH). The algorithm outputs the loss probability, along with an upper-bound of its numerical error due to truncation, and it is readily applicable to the M/D/1+PH, M/PH/1+PH, and M/Pareto/1+PH queues.     

A Spectral Method for a Nonpreemptive Priority BMAP/G/1 QUEUE

Abstract

In this paper we consider a nonpreemptive priority queue with two priority classes of customers. Customers arrive according to a batch Markovian arrival process (BMAP). In order to calculate the boundary vectors we propose a spectral method based on zeros of the determinant of a matrix function and the corresponding eigenvectors. It is proved that there are M zeros in a set Ω, where M is the size of the state space of the underlying Markov process. The zeros are calculated by the Durand-Kerner method, and the stationary joint probability of the numbers of customers of classes 1 and 2 at departures is derived by the inversion of the two-dimensional Fourier transform. For a numerical example, the stationary probability is calculated.     

Optimal Routing Among ⋅/M/1 Queues with Partial Information

Abstract

When routing dynamically randomly arriving messages, the controller of a high-speed communication network very often gets the information on the congestion state of down stream nodes only after a considerable delay, making that information irrelevant at decision epochs. We consider the situation where jobs arrive according to a Poisson process and must be routed to one of two (parallel) queues with exponential service time distributions (possibly with different means), without knowing the congestion state in one of the queues. However, the (conditional) probability distribution of the state of the unobservable queue can be computed by the router. We derive the joint probability distribution of the congestion states in both queues as a function of the routing policy. This allows us to identify optimal routing schemes for two types of frameworks: global optimization, in which the weighted sum of average queue lengths is minimized, and individual optimization, in which the goal is to minimize the expected delay of individual jobs.     

Analysis and Computation of the Joint Queue Length Distribution in a FIFO Single-Server Queue with Multiple Batch Markovian Arrival Streams

This paper considers a work-conserving FIFO single-server queue with multiple batch Markovian arrival streams governed by a continuous-time finite-state Markov chain. A particular feature of this queue is that service time distributions of customers may be different for different arrival streams. After briefly discussing the actual waiting time distributions of customers from respective arrival streams, we derive a formula for the vector generating function of the time-average joint queue length distribution in terms of the virtual waiting time distribution. Further assuming the discrete phase-type batch size distributions, we develop a numerically feasible procedure to compute the joint queue length distribution. Some numerical examples are provided also.     

Commuting Matrices in the Queue Length and Sojourn Time Analysis of MAP/MAP/1 Queues

Queues with Markovian arrival and service processes, i.e., MAP/MAP/1 queues, have been useful in the analysis of computer and communication systems and different representations for their stationary sojourn time and queue length distribution have been derived. More specifically, the class of MAP/MAP/1 queues lies at the intersection of the class of QBD queues and the class of semi-Markovian queues. While QBD queues have a matrix exponential representation for their queue length and sojourn time distribution of order N and N², respectively, where N is the size of the background continuous time Markov chain, the reverse is true for a semi-Markovian queue. As the class of MAP/MAP/1 queues lies at the intersection, both the queue length and sojourn time distribution of a MAP/MAP/1 queue has an order N matrix exponential representation. The aim of this article is to understand why the order N² distributions of the sojourn time of a QBD queue and the queue length of a semi-Markovian queue can be reduced to an order N distribution in the specific case of a MAP/MAP/1 queue. We show that the key observation exists in establishing the commutativity of some fundamental matrices involved in the analysis of the MAP/MAP/1 queue.     

Response Time Distribution in a D-MAP/PH/1 Queue with General Customer Impatience

ABSTRACT

This paper presents two methods to calculate the response time distribution of impatient customers in a discrete-time queue with Markovian arrivals and phase-type services, in which the customers’ patience is generally distributed (i.e., the D-MAP/PH/1 queue). The first approach uses a GI/M/1 type Markov chain and may be regarded as a generalization of the procedure presented in Van Houdt ^[14] Van Houdt , B. ; Lenin , R. B. ; Blondia , C. Delay distribution of (im)patient customers in a discrete time D-MAP/PH/1 queue with age dependent service times Queueing Systems and Applications 2003 , 45 1 , 59 – 73 . [CROSSREF]  [Google Scholar] for the D-MAP/PH/1 queue, where every customer has the same amount of patience. The key construction in order to obtain the response time distribution is to set up a Markov chain based on the age of the customer being served, together with the state of the D-MAP process immediately after the arrival of this customer. As a by-product, we can also easily obtain the queue length distribution from the steady state of this Markov chain.

We consider three different situations: (i) customers leave the system due to impatience regardless of whether they are being served or not, possibly wasting some service capacity, (ii) a customer is only allowed to enter the server if he is able to complete his service before reaching his critical age and (iii) customers become patient as soon as they are allowed to enter the server. In the second part of the paper, we reduce the GI/M/1 type Markov chain to a Quasi-Birth-Death (QBD) process. As a result, the time needed, in general, to calculate the response time distribution is reduced significantly, while only a relatively small amount of additional memory is needed in comparison with the GI/M/1 approach. We also include some numerical examples in which we apply the procedures being discussed.