Proof of stability conditions for token passing rings by Lyapunovfunctions

A token passing ring can be described as a system of M queues with one server that rotates around the queues sequentially. Georgiadis-Szpankowski (1992) considered rings where the token (server) performs x ∇ l_j services on queue j, where x is the size of queue j upon arrival of the token, and l_j is a fixed limit of service for queue j. The token then spends some random time switching to the next queue. For j=1, ..., M, arrivals to queue j are Poisson with rate λ_j, and service times have mean s _j and are independent of the arrival and switchover processes. The purpose of this paper is to give an alternate and simpler proof of the stability conditions given by Georgiadis-Szpankowski using Lyapunov functions. An additional assumption is made about the second moments of the service and switchover times being finite     

Optimal scheduling of two competing queues with blocking

Consideration is given to the problem of optimal scheduling for two queues for service at a single station, where the queues have finite capacities and the service rate is class-dependent. The cost structure is linear in the number of holding customers in the queues, combined with blocking costs incurred whenever arrivals encounter a full queue. The authors derive the optimal policy minimizing this criterion when the blocking cost is larger than the holding cost for each queue. Then they show that the optimal policy is of the switching type. Numerical results are included to support the analytical findings     

Optimal control of parallel queues with impatient customers

We consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process with an arrival rate which is a non-increasing function of the number of customers in the system. Upon arrival, a customer must join a server’s queue according to a stationary state-dependent policy, where the state is taken to be the number of customers in servers’ queues. No jockeying among queues is allowed. Each arriving customer is limited to a generally distributed patience time after which it must depart the system and is considered lost. Two models of customer behavior are considered: deadlines until the beginning of service and deadlines until the end of service. We seek an optimal policy to assign an arriving customer to a server’s queue. We show that, when the distribution of customer impatience satisfies certain property, the policy of joining shortest queue (SQ) stochastically minimizes the number of lost customers during any finite interval in the long run. This property is shown to always hold for the case of deterministic customer impatience.     

Parallel exponential queues with dependent service rates

A system of two parallel single-server exponential queues is considered. These queues operate independently except that the service rate in each queue changes whenever the other queue is empty. By treating one of the queues as bounded, this model can be shown to have a matrix-geometric steady state vector which can be computed efficiently. Algorithms are also developed to compute the characteristics of the departure stream of customers from each queue. Some numerical results are presented, and based on these results an efficient approximation scheme for the system is developed which may possibly be extended to systems with more than two parallel queues.     

Decomposing the queue length distribution of processor-sharing models into queue lengths of permanent customer queues

We obtain a decomposition result for the steady state queue length distribution in egalitarian processor-sharing (PS) models. In particular, for multi-class egalitarian PS queues, we show that the marginal queue length distribution for each class equals the queue length distribution of an equivalent single class PS model with a random number of permanent customers. Similarly, the mean sojourn time (conditioned on the initial service requirement) for each class can be obtained by conditioning on the number of permanent customers. The decomposition result implies linear relations between the marginal queue length probabilities, which also hold for other PS models such as the egalitarian PS models with state-dependent system capacity that only depends on the total number of customers in the system. Based on the exact decomposition result for egalitarian PS queues, we propose a similar decomposition for discriminatory processor-sharing (DPS) models, and numerically show that the approximation is accurate for moderate differences in service weights.     

Dynamic routing of real-time jobs among parallel EDF queues: A performance study

This paper introduces an analytical method for approximating the performance of a firm real-time system consisting of a number of parallel infinite-capacity single-server queues. The service discipline for the individual queues is earliest-deadline-first (EDF). Real-time jobs with exponentially distributed relative deadlines arrive according to a Poisson process. Jobs either all have deadlines until the beginning of service or deadlines until the end of service. Upon arrival, a job joins a queue according to a state-dependent stationary policy, where the state of the system is the number of jobs in each queue. Migration among the queues is not allowed. An important performance measure to consider is the overall loss probability of the system. The system is approximated by a Markovian model in the long run. The resulting model can then be solved analytically using standard Markovian solution techniques. Comparing numerical and simulation results for at least three different stationary policies, we find that the existing errors are relatively small.     

An approximate MVA algorithm for exponential, class-dependent multiple servers

Mean value analysis (MVA) is an efficient algorithm for determining the mean sojourn time, the mean queue length, and the throughput in a closed multiclass queueing network. It provides exact results for the class of product-form networks. Often different classes have different service requirements in FCFS queues, but such networks are not of product form. There are several possibilities to compute performance measure for such nodes and networks. In this paper we present an approximation formula for multiple-server FCFS queues with class-dependent service times as a Norton flow equivalent product node, where the departure rate of any class depends on the number of customers of all classes in the queue. We will use this approximation in the sojourn time formula of some exact and approximate MVA algorithms.     

Modelling manufacturing systems: A birth-death approach

An approximation method for modelling a manufacturing system is introduced. The system is considered as a queueing network, where each queue is limited in size, and interarrival and processing times are exponentially distributed. The birth-death approach is considered and an approximation method to reduce the dimension of the model is developed. The results are the marginal probability distribution of the number of units in each queue; other performance indices, such as mean queue lengths, utilizations of the working stations, and throughput can be easily obtained. The general procedure is applied to model, for example, queues in tandem, a split node, and a more complex network of queues. Simulation and, when possible, comparison with the exact solution show an acceptable error level of the proposed method.     

Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems

We consider a class of queueing networks referred to as "generalized constrained queueing networks" which form the basis of several different communication networks and information systems. These networks consist of a collection of queues such that only certain sets of queues can be concurrently served. Whenever a queue is served, the system receives a certain reward. Different rewards are obtained for serving different queues, and furthermore, the reward obtained for serving a queue depends on the set of concurrently served queues. We demonstrate that the dependence of the rewards on the schedules alter fundamental relations between performance metrics like throughput and stability. Specifically, maximizing the throughput is no longer equivalent to maximizing the stability region; we therefore need to maximize one subject to certain constraints on the other. Since stability is critical for bounding packet delays and buffer overflow, we focus on maximizing the throughput subject to stabilizing the system. We design provably optimal scheduling strategies that attain this goal by scheduling the queues for service based on the queue lengths and the rewards provided by different selections. The proposed scheduling strategies are however computationally complex. We subsequently develop techniques to reduce the complexity and yet attain the same throughput and stability region. We demonstrate that our framework is general enough to accommodate random rewards and random scheduling constraints.     

Queueing systems with random service rate

We consider a queue with the arrival process, the service time process and the service rate process as regenerative processes. We provide conditions for its stability, rates of convergence, finiteness of moments and functional limit theorems. This queue can model a queue serving ABR and UBR traffic in an ATM switch; a multiple access channel with TDMA or CDMA protocol and fading; a queue holding best effort or controlled and guaranteed traffic in a router in the integrated service architecture (ISA) of IP-based Internet and a scheduler in the router of a differentiated service architecture. In the process we also provide results for a queue with a leaky bucket controlled bandwidth scheduler. This result is of independent interest. We extend these results to feed-forward networks of queues. We also obtain the results when the arrival rate to the queue can be feedback controlled based on the congestion information in the queue (as in ABR service in the ATM networks or in the real time applications controlled by RTCP protocol in the Internet).     

Analysis of a multi-server queue with two priority classes and (M, N)-threshold service schedule I: non-preemptive priority

In this paper, we propose an ( M , N )-threshold non-preemptive priority service schedule for a queueing system consisting of two-parallel queues and a multi-server. The arrival process for each queue is Poisson, and the service times are exponentially distributed with different means. We derive the generating functions of the stationary joint queue-length distribution, and then obtain the mean queue length and the mean waiting time for each queue.     

A Two-Queue Polling Model with Two Priority Levels in the First Queue

In this paper we consider a single-server cyclic polling system consisting of two queues. Between visits to successive queues, the server is delayed by a random switch-over time. Two types of customers arrive at the first queue: high and low priority customers. For this situation the following service disciplines are considered: gated, globally gated, and exhaustive. We study the cycle time distribution, the waiting times for each customer type, the joint queue length distribution at polling epochs, and the steady-state marginal queue length distributions for each customer type.     

Joining the right queue: a state-dependent decision rule

The problem of assigning customers to one of several parallel queues so as to minimize the average time spent in the system (sojourn time) is studied as a Markov decision process. It is shown how the approach developed by K.R. Krishman and T.J. Ott (Proc. 25th IEEE Conf. Decision Contr. Dec. 1986, p.2124-8) to investigate state-dependent routing of voice traffic for blocking minimization can also be used for sojourn minimization for data traffic. For queues in parallel, this approach produces a rule, called the `separable' rule, which is a generalization of the `join the shortest queue' rule to the case of dissimilar queues, reducing to the shortest queue rule when the queues are all alike. Numerical results show that in cases where the queues are dissimilar in both the service rates and numbers of their servers, the separable rule is strikingly superior to the shortest queue rule; if the dissimilarities are limited to differences in the service rates, the separable rule practically always is better than the shortest queue rule; if the dissimilarities consist only of the numbers of servers being different, then the shortest queue rule does better than the separable rule in most instances     

Violation Probability in Processor-Sharing Queues

Processor-sharing queues are often used to model file transmission in networks. While sojourn time is a common performance metric in the queueing literature, average transmission rate is the more commonly discussed metric in the networking literature. Whereas much is known about sojourn times, there is little known about the average service rate experienced by jobs in processor-sharing queues. We focus here upon performance requirements in the form of an upper bound on the probability of failing to achieve a specified minimum transmission rate or a specified minimum average rate. For an M/G/l processor-sharing queue, we give a closed-form expression for this violation probability. We derive closed-form expressions for the marginal service rate with respect to the violation probability and to the minimum transmission rate, and characterize when each is binding. We then consider the effect of using connection access control by modeling an M/G/l/K processor-sharing queue, and discuss the relationship between queue service rate, queue limit, violation probability, and blocking probability. Finally, we consider a two-class discriminatory processor-sharing queue, and discuss what combinations of class weighting and service rate can be used to achieve specified minimum rate violation probabilities for both classes.     

Asymptotic bounds of throughput in series-parallel queueing networks

We propose a piece-wise linear upper bound on the throughput rate from a network of series-parallel queues where arrivals occur through a single infinite queue. This bound is tight and is observed to be extremely accurate in forecasting the actual throughput rate. We also describe the monotonicity of throughput as a function of the arrival rate and specify a condition under which the upper bound may be computed. We approximate analytically the throughput measured as a function of the arrival rate for two tandem exponential queues, where the first queue has an infinite buffer while the second queue has a finite buffer. We extend this analysis to elementary split and merge queueing networks. We demonstrate the generality and robustness of this asymptotic property, for larger series-parallel networks with general service times and specify the set up of a single simulation experiment which can be used to retrieve the throughput for any arrival rate, as well as other networks performance measures.     

Stationary deterministic flows: II. The single-server queue

The goal of this paper is to establish fundamental properties of queueing systems. A single-server queue is considered in which the usual probabilistic assumptions are not assumed to hold. Only the existence of long-term averages of inter-arrival times and service times is assumed. Based on these minimal assumptions, stability conditions are established. The asymptotic behavior of the unstable queue is determined. In addition, an investigation of the stable queue is undertaken. Topics include queues with failures and asymptotic birth-and-death equations.     

基于混合服务策略轮询系统的性能分析

周期轮询系统已被广泛运用于各个领域,如计算机网络、工业制造系统等。在周期轮询系统中,最基本的队列调度策略有门限服务、限定服务以及完全服务。这些调度策略各有其优缺点,文章提出了一种基于混合服务的调度策略,对一些队列采用门限服务,对另一些队列采用限定服务,这样既可以避免在单一的完全服务中低优先级队列有可能出现的队列饥饿现象,又可以对不同的队列提供不同的服务质量。该文通过嵌入马尔可夫链和概率母函数的方法对基于混合服务的轮询系统进行分析,推导出队列的平均队长,并与采用门限服务的轮询系统进行比较,从而说明混合服务系统的优点。     

A Symmetrical Exponential Open Queue Network with Blocking and Feedback

The exponential open queue network model studied here consists of n symmetrical queues in parallel served by independent first-level servers in tandem with a second-level server. Blocking of the flow of units through a first-level server occurs each time the server completes a service. The server remains blocked until its blocking unit completes its service at the second-level server. An approximate expression of the probability distribution of the number of blocked first-level servers conditioned upon a service completion of a first-level server is obtained. This expression compares well with simulation data. Based on this distribution, an approximate expression of the queue-length probability distribution is derived assuming a processor-sharing type of service. The exact condition for stability of the queue network is also derived. Some potential applications are discussed, and a quantitative evaluation of the model is given through a case study.     

On infinite queueing tandems

We study the flow of jobs on an infinite series of first-come-first-served queues. Jobs are placed in the buffer of the first queue and allowed to flow through the infinite tandem of queues. The service times of each job on consecutive queues form a stationary and ergodic sequence. We are interested in characterizing the flow of jobs asymptotically, after they have passed through a large number of queues.It is shown that the job flow reaches asymptotically a stationary state, which can be characterized in terms of the average service times of the jobs. They eventually form clusters, such that every two consecutive jobs belonging to the same cluster collide infinitely often, while jobs belonging to different clusters eventually cease to interact.     

Weighted fair share scheduling for loosely controlled concurrent event systems

In asynchronous event systems, the production of an event is decoupled from its consumption via an event queue. The loose coupling of such systems allows great flexibility as to where and when within the system the event handler of a given event is actually executed, allowing them to scale with increasing number of processors on a given node or across multiple nodes in a distributed system. Although this flexibility is useful in heterogeneous distributed systems, such as SOA, it may appear not to be well suited for real-time systems, which require an upper bound on how long an event can remain unhandled in a queue. However, we show how the weighted fair scheduling algorithms developed for QoS (quality of service) routing can be adapted to event queues to bound the delay between production and consumption. We achieve this, despite the fact that the underlying execution environment is only weakly controlled, through the use of predictive techniques on a calibrated model of the event system. Our choice of algorithms and data structures is driven in part by the highly concurrent nature of the system. We show how a weighted fair scheduler can be built on a lock-free concurrent priority queue. We analyze the performance of various such queues proposed in the literature and show that a very simple linear quantizing queue yields the best performance.