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.     

A Retrial Queue with a Constant Retrial Rate,Server Downs and Impatient Customers

ABSTRACT

In this paper, we consider a retrial queueing system consisting of a waiting line of infinite capacity in front of a single server subject to breakdowns. A customer upon arrival may join the queue (waiting line) or go to the retrial orbit (another queue) to retry for service after a random time. Only the customer at the head of the retrial orbit is allowed to retry for service. Upon retrial, the customer enters the service if the server is idle; otherwise, it may go back to the retrial orbit or leave the system (become impatient). All the interarrival times, service times, server up times, server down times and retrial times are exponential, and all the necessary independence conditions in these variables are assumed. For this system, we provide sufficient conditions under which, for any given number of customers in the orbit, the stationary probability of the number of customers in the waiting line decays geometrically. We also provide explicitly an expression for the decay parameter.     

ON THE INFINITE SERVER SHORTEST QUEUE PROBLEM: SYMMETRIC CASE

Abstract

We consider two identical parallel M/M/∞ queues. A new arrival is routed to the queue with the smaller number of customers. If both systems have equal occupancy, the arrival joins either with probability 1/2. These types of models have been used to describe CDMA (Code Division Multiple Access) cellular systems. We analyze this model both numerically and asymptotically. For the latter, we consider the limit ρ = λ/μ → ∞, where λ (resp., μ) is the arrival (resp., service) rate. An efficient numerical method is developed for computing the joint steady-state distribution of the number of customers in the two queues. We give several asymptotic formulas, valid for different ranges of the state variables, which show the qualitative structure of the joint distribution. The numerical accuracy of the asymptotic results is tested.     

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.     

Routing in a queueing system with two heterogeneous servers in speed and in quality of resolution

Heterogeneous servers, in manufacturing and service systems, may have different speeds and different quality levels for the provided service or good For a two-server queueing model, we formulate the job routing problem for minimizing the stationary weighted sum of the expected time spent in the system and the number of unsatisfied customers per time unit. Using a Markov decision process approach, we prove that the optimal routing policy of jobs to service is a threshold policy that depends on the queue length. When the number of waiting jobs in the queue is below a certain threshold, only one server should work and the other one remains idle. At or above this threshold, both servers should serve jobs. This is an extension of the known result where only the heterogeneity in speed is considered.     

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.     

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.     

Large deviations of multiclass M/G/1 queues

Consider a multiclass M/G/1 queue where queued customers are served in their order of arrival at a rate which depends on the customer class. We model this system using a chain with states represented by a tree. Since the service time distribution depends on the customer class, the stationary distribution is not of product form so there is no simple expression for the stationary distribution. Nevertheless, we can find a harmonic function on this chain which provides information about the asymptotics of this stationary distribution. The associated h‐transformation produces a change of measure that increases the arrival rate of customers and decreases the departure rate thus making large deviations common. The Canadian Journal of Statistics 37: 327–346; 2009 © 2009 Statistical Society of Canada     

A Bitcoin-inspired infinite-server model with a random fluid limit

The synchronization process inherent to the Bitcoin network gives rise to an infinite-server model with the unusual feature that customers interact. Among the closed-form characteristics that we derive for this model is the busy period distribution which, counterintuitively, does not depend on the arrival rate. We explain this by exploiting the equivalence between two specific service disciplines, which is also used to derive the model’s stationary distribution. Next to these closed-form results, the second major contribution concerns an asymptotic result: a fluid limit in the presence of service delays. Since fluid limits arise under scalings of the law-of-large-numbers type, they are usually deterministic, but in the setting of the model discussed in this paper the fluid limit is random (more specifically, of growth-collapse type).     

Analysis of a discrete-time queue with load dependent service under discrete-time Markovian arrival process

In the study of normal queueing systems, the server’s average service times are generally assumed to be constant. However, in numerous applications this assumption may not be valid. To prevent congestion in overload control telecommunication networks, the transmission rates vary depending on the number of packets waiting in the queue. As traffics in telecommunication networks are of bursty nature and correlated, we assume that arrivals follow the discrete-time Markovian arrival process. This paper analyzes a queueing model in which the server changes its service times (rates) only at the beginning of service depending on the number of customers waiting in the queue. We obtain the steady-state probabilities at various epochs and some performance measures. In addition, varieties of numerical results are discussed to display the effect of the system parameters on the performance measures.     

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.     

Discrete-time GIX/Geo/1/N queue with negative customers and multiple working vacations

Using the supplementary variable and the embedded Markov chain method, we consider a discrete-time batch arrival finite capacity queue with negative customers and working vacations, where the RCH killing policy and partial batch rejection policy are adopted. We obtain steady-state system length distributions at pre-arrival, arbitrary and outside observer’s observation epochs. Furthermore, we consider the influence of system parameters on several performance measures to demonstrate the correctness of the theoretical analysis.     

On a general mixed priority queue with server discretion

We consider a single-server queueing system which attends to N priority classes that are classified into two distinct types: (i) urgent: classes which have preemptive resume priority over at least one lower priority class, and (ii) non-urgent: classes which only have non-preemptive priority among lower priority classes. While urgent customers have preemptive priority, the ultimate decision on whether to interrupt a current service is based on certain discretionary rules. An accumulating prioritization is also incorporated. The marginal waiting time distributions are obtained and numerical examples comparing the new model to other similar priority queueing systems are provided.     

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.     

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.     

Equilibrium strategies in a constant retrial queue with setup time and the N-policy

Abstract

In this article, customers’ strategic behavior and social optimation in a constant retrial queue with setup time and the N-policy are investigated. Customers who find the server isn’t idle either leave forever or enter an orbit. After a service, the server will seek a customer from the orbit at a constant rate. The server is closed whenever the system becomes empty, and is activated when the number of waitlisted customers reaches a threshold. We obtain the equilibrium arrival rates in different states. There exist both Follow-the-Crowd (FTC) and Avoid-the-Crowd (ATC) behaviors. Through the Particle Swarm Optimization (PSO) algorithm, we numerically obtain the optimal solution of the social welfare maximization problem. Finally, numerical examples are presented to illustrate the sensitivity of system performance measures.     

Modelling the travel time of transit vehicles in real‐time through a GTFS‐based road network using GPS vehicle locations

Predicting the arrival time of a transit vehicle involves not only knowledge of its current position and schedule adherence, but also traffic conditions along the remainder of the route. Road networks are dynamic and can quickly change from free‐flowing to highly congested, which impacts the arrival time of transit vehicles, particularly buses which often share the road with other vehicles, so reliable predictions need to account for real‐time and future traffic conditions. The first step in this process is to construct a framework with which road state (traffic conditions) can be estimated using real‐time transit vehicle position data. Our proposed framework implements a vehicle model using a particle filter to estimate road travel times, which are used in a second model to estimate real‐time traffic conditions. Although development and testing took place in Auckland, New Zealand, we generalised each component to make the framework compatible with other public transport systems around the world. We demonstrate the real‐time feasibility and performance of our approach in real‐time, where a combination of R and C++ was used to obtain the necessary performance results. Future work will use these estimated traffic conditions in combination with historical data to obtain reliable arrival time predictions of transit vehicles.     

Spare Reliability for Capacitated Computer Networks Under Tolerable Error Rate and Latency Considerations

Error rate and transmission time are both critical factors in a computer system. In addition to guarantee the robustness of the computer system under both tolerable error rate and latency, enhancing the system reliability by a routing scheme, named spare reliability, is also a critical task. Virtually, each branch possesses multiple possible capacities. Such a network is termed a capacitated computer network (CCN). Hence, this article develops an efficient algorithm to derive the spare reliability of a CCN, where the spare reliability is the probability that data can be sent through multiple minimal paths considering routing scheme.     

The existence of waiting time moments for single server queues with mixed renewal and poisson inputs

The following queuing system is considered: Two independent recurrent input streams (streams 1 and 2) arrive at a server. It is assumed that stream 1 is of Poisson type. Three priority disciplines are studied in case that customers of type 1 have priority: head-of-the-line, preemptive-resume, and preemptive-repeat discipline. For all three cases, the limiting distribution function of actual waiting times of low-priority customers is considered, and conditions are given for the existence of moments related to these limiting distributions.