Mixed gated/exhaustive service in a polling model with priorities

In this paper we consider a single-server polling system with switch-over times. We introduce a new service discipline, mixed gated/exhaustive service, that can be used for queues with two types of customers: high and low priority customers. At the beginning of a visit of the server to such a queue, a gate is set behind all customers. High priority customers receive priority in the sense that they are always served before any low priority customers. But high priority customers have a second advantage over low priority customers. Low priority customers are served according to the gated service discipline, i.e. only customers standing in front of the gate are served during this visit. In contrast, high priority customers arriving during the visit period of the queue are allowed to pass the gate and all low priority customers before the gate. We study the cycle time distribution, the waiting time distributions for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type. Through numerical examples we illustrate that the mixed gated/exhaustive service discipline can significantly decrease waiting times of high priority jobs. In many cases there is a minimal negative impact on the waiting times of low priority customers but, remarkably, it turns out that in polling systems with larger switch-over times there can be even a positive impact on the waiting times of low priority customers.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

Double-sided matching queues: Priority and impatient customers

We analyze a double-sided queue with priority that serves patient customers and customers with zero patience (i.e., impatient customers). In a two-sided market, high and low priority customers arrive to one side and match with queued customers on the opposite side. Impatient customers match with queued patient customers; when there is no queue, they leave the system unmatched. All arrivals follow independent Poisson processes. We derive exact formulae for the stationary queue length distribution and several steady-state performance measures.     

Waiting time in a multi-server cutoff-priority gueue, and its application to an urban ambulance service

We consider a priority queue in steady state with N servers, two classes of customers, and a cutoff service discipline. Low priority arrivals are "cut off" (refused immediate service) and placed in a queue whenever N1 or more servers are busy, in order to keep N-N1 servers free for high priority arrivals. A Poisson arrival process for each class, and a common exponential service rate, are assumed. Two models are considered: one where high priority customers queue for service and one where they are lost if all servers are busy at an arrival epoch. Results are obtained for the probability of n servers busy, the expected low priority waiting time, and (in the case where high priority customers do not queue) the complete low priority waiting time distribution. The results are applied to determine the number of ambulances required in an urban fleet which serves both emergency calls and low priority patients transfers.     

On a generic class of two-node queueing systems

This paper analyzes a generic class of two-node queueing systems. A first queue is fed by an on–off Markov fluid source; the input of a second queue is a function of the state of the Markov fluid source as well, but now also of the first queue being empty or not. This model covers the classical two-node tandem queue and the two-class priority queue as special cases. Relying predominantly on probabilistic argumentation, the steady-state buffer content of both queues is determined (in terms of its Laplace transform). Interpreting the buffer content of the second queue in terms of busy periods of the first queue, the (exact) tail asymptotics of the distribution of the second queue are found. Two regimes can be distinguished: a first in which the state of the first queue (that is, being empty or not) hardly plays a role, and a second in which it explicitly does. This dichotomy can be understood by using large-deviations heuristics. This work has been carried out partly in the Dutch BSIK/BRICKS project.     

对一类等待空间有限的抢占优先权排队的分析

讨论M/M/1抢占优先权排队模型, 且假设低优先权顾客的等待空间有限. 该模型可以用有限位相拟生灭过程来描述. 由矩阵解析方法, 对该拟生灭过程进行了分析, 并得到排队模型平稳队长的计算公式, 最后还用数值 结果说明了方法的有效性.     

Tail asymptotics for service systems with transfers of customers in an alternating environment

This study examines service systems with transfers of customers in an alternating environment. We model the service system as a two-server two-parallel queue (primary and auxiliary queues), that has various applications especially in manufacturing and healthcare systems. We establish a sufficient stability condition, and based on the censoring technique, we provide sufficient conditions under which the stationary distribution possesses an exactly geometric tail along the direction of the queue length in the primary queue.     

On the value function of a priority queue with an application to a controlled polling model

We give a closed-form expression for the discounted weighted queue length and switching costs of a two-class single-server queueing model under a preemptive priority rule. These expressions are used to do a single step of policy iteration in a polling model with a dynamically controlled switching rule, starting from the preemptive priority rule. Numerical experiments show that this leads to a policy that performs well.     

Queue length in an absolute priority system with hyperexponential input flow

Joint generating functions of queue length are obtained for a single-channel absolute priority system with restarting service of interrupted units and recurrent input flow with hyperexponential distribution of intervals between arrivals.     

Discrete time queues with delayed information

We study the behavior of a single-server discrete-time queue with batch arrivals, where the information on the queue length and possibly on service completions is delayed. Such a model describes situations arising in high speed telecommunication systems, where information arrives in messages, each comprising a variable number of fixed-length packets, and it takes one unit of time (a slot) to transmit a packet. Since it is not desirable to attempt service when the system may be empty, we study a model where we assume that service is attempted only if, given the information available to the server, it is certain that there are messages in the queue. We characterize the probability distribution of the number of messages in the queue under some general stationarity assumptions on the arrival process, when information on the queue size is delayedK slots, and derive explicit expressions of the PGF of the queue length for the case of i.i.d. batch arrivals and general independent service times. We further derive the PGF of the queue size when information onboth the queue length and service completion is delayedK=1 units of time. Finally, we extend the results to priority queues and show that when all messages are of unit length, thec rule remains optimal even in the case of delayed information.     

Stability and Analysis of TCP Connections with RED Control and Exogenous Traffic

In this paper we study the stability and performance of a system involving several TCP connections passing through a tandem of RED controlled queues each of which has an incoming exogenous stream. The exogenous stream, representing the superposition of all incoming UDP connections into a queue, has been modeled as an MMPP stream. We consider both the TCP Tahoe and the TCP Reno versions. We start with the analysis of a single TCP connection sharing a RED controlled queue with an exogenous stream. The effect of the exogenous stream (which is almost always present in large networks) is to cause the system to converge to a stationary distribution from any initial conditions. This stability result holds good for any work conserving discipline. We also obtain the performance indices of the system; specifically the goodputs and the mean sojourn times of the various connections. The complexity involved in computation of performance indices for the system is reduced by approximating the evolution of the average queue length process of the RED queue by a deterministic ODE. Then, by using a decomposition approach of two time scales, we reduce the study of the system to that of a simplified one for which the performance measures can be obtained under stationarity. Finally, we extend the above results to the case when multiple TCP connections share a RED controlled queue with an exogenous stream and to the case when a TCP connection passes through several RED controlled tandem queues each of which has an incoming exogenous stream. We also consider an example of multiple TCPs passing through a tandem of queues. A number of simulation results have been provided which support the analysis.     

N-策略单重休假M/G/1排队系统的队长分布

本文考虑N-策略单重休假M/G/1排队系统,通过引进"服务员忙期"和使用全概率分解技术,从任意初始状态出发,研究了队长的瞬态分布和稳态分布,首次导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式,以及平稳队长的随机分解.特别地,通过本文可直接获得一些特殊排队系统相应的结果.     

MAP 1, MAP2 /M/c retrial queue with guard channels and its application to cellular networks

In this paper, we investigate the impact of retrial phenomenon on loss probabilities and compare loss probabilities of several channel allocation schemes giving higher priority to hand-off calls in the cellular mobile wireless network. In general, two channel allocation schemes giving higher priority to hand-off calls are known; one is the scheme with the guard channels for hand-off calls and the other is the scheme with the priority queue for hand-off calls. For mathematical unified model for both schemes, we consider theMAP ₁,MAP ₂ /M/c/b, ∞ retrial queue with infinite retrial group, geometric loss, guard channels and finite priority queue for hand-off class. We approximate the joint distribution of two queue lengths by Neuts' method and also obtain waiting time distribution for hand-off calls. From these results, we obtain the loss probabilities, the mean waiting time and the mean queue lengths. We give numerical examples to show the impact of the repeated attempt and to compare loss probabilities of channel allocation schemes.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.      

Tail asymptotics for a Lévy-driven tandem queue with an intermediate input

We consider a Lévy-driven tandem queue with an intermediate input assuming that its buffer content process obtained by a reflection mapping has the stationary distribution. For this queue, no closed form formula is known, not only for its distribution but also for the corresponding transform. In this paper, we consider only light-tailed inputs. For the Brownian input case, we derive exact tail asymptotics for the marginal stationary distribution of the second buffer content, while weaker asymptotic results are obtained for the general Lévy input case. The results generalize those of Lieshout and Mandjes from the recent papers (Lieshout and Mandjes in Math. Methods Oper. Res. 66:275–298, 2007 and Queueing Syst. 60:203–226, 2008) for the corresponding tandem queue without an intermediate input.     

A tandem network with MAP inputs

This paper studies a tandem queue with MAP inputs. A novel formulation is proposed to model it into a level-dependent quasi-birth-death process with expanding blocks. This allows us to analyze the joint time-dependent and steady-state queue length distributions efficiently. We also obtain the network sojourn time of an arbitrary customer.     

Large number of queues in tandem: Scaling properties under back-pressure algorithm

We consider a system with N unit-service-rate queues in tandem, with exogenous arrivals of rate λ at queue 1, under a back-pressure (MaxWeight) algorithm: service at queue n is blocked unless its queue length is greater than that of the next queue n+1. The question addressed is how steady-state queues scale as N→∞. We show that the answer depends on whether λ is below or above the critical value 1/4: in the former case the queues remain uniformly stochastically bounded, while otherwise they grow to infinity.     

An explicit solution to a tandem queueing model

We consider two queues in tandem, each with an exponential server, and with deterministic arrivals to the first queue. We obtain an explicit solution for the steady state distribution of the process (N₁(t), N₂(t), Y(t)), where N_j(t) is the queue length in the jth queue and Y(t) measures the time elapsed since the last arrival. Then we obtain the marginal distributions of (N₁(t), N₂(t)) and of N₂(t). We also evaluate the solution in various limiting cases, such as heavy traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

输入率可变、反馈的、且有负顾客的优先排队模型

针对实际应用中存在输入率可变、因服务出差错而导致顾客需要重新排队接受服务以及不同的顾客类需要不同的服务质量等现状,建立了输入率可变、有反馈及负顾客的、服务时间服从一般分布优先排队模型.得出了"强占优先"与"非强占优先"两种服务规则下,系统中每一类顾客的队长、等待时间、逗留时间的平稳分布均存在,并求出了每一类顾客的队长、等待时间、逗留时间及他们的L-S变换,忙期等指标,最后还指出了模型在应用中的注意事项及要进一步解决的问题.