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.     

MRE hierarchical decomposition of general queueing network models

Summary The principle of Minimum Relative Entropy (MRE), given fully decomposable subset and aggregate mean queue length, utilisation and flow-balance constraints, is used in conjunction with asymptotic connections to infinite capacity queues, to derive new analytic approximations for the conditional and marginal state probabilities of single class general closed queueing network models (QNMs) in the context of a multilevel variable aggregation scheme. The concept of subparallelism is applied to preserve the flow conservation and a universal MRE hierarchical decomposition algorithm is proposed for the approximate analysis of arbitrary closed queueing networks with single server queues and general service-times. Heuristic criteria towards an optimal coupling of network's units at each level of aggregation are suggested. As an illustration, the MRE algorithm is implemented iteratively by using the Generalised Exponential (GE) distributional model to approximate the service and asymptotic flow processes in the network. This algorithm captures the exact solution of separable queueing networks, while for general queueing networks it compares favourably against exact solutions and known approximations.This work is sponsored by the Science and Engineering Research Council (SERC), UK, under grant GR/F29271     

A maximum entropy priority approximation for a stableG/G/1 queue

Summary The principle of maximum entropy is used under two different sets of mean value constraints to analyse a stableG/G/1 queue withR priority classes under preemptive-resume (PR) and non-preemptive head-of-line (HOL) scheduling disciplines. New one-step recursions for the maximum entropy state probabilities are established and closed form approximations for the marginal queue length distribution per priority class are derived. To expedite the utility of the maximum entropy solutions exact analysis, based on the generalised exponential (GE) distribution, is used to approximate the marginal mean queue length and idle state probability class constraints for both the PR and HOLG/G/1 priority queues. Moreover, these results are used as building blocks in order to provide new approximate formulae for the mean and coefficient of variation of the effective priority service-time and suggest a maximum entropy algorithm for general open queueing networks with priorities in the context of the reduced occupancy approximation (ROA) method. Numerical examples illustrate the accuracy of the proposed maximum entropy approximations in relation to simulations involving different interarrival-time and service-time distributions per class. Comments on the extension of the work to more complex types of queueing systems are included.This work is sponsored in part by the Science and Engineering Research Council (SERC), UK, under grant GR/D/12422 and in part by the Ministry of Higher Education of the Algerian Government     

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.     

The behaviour of a single queue in a general queueing network

Summary We develop a method based on diffusion approximations in order to compute, under general conditions, the queue length distribution of a single queue in a network of queues. Several applications of this approach to computer network performance analysis and to time-sharing systems are presented. The accuracy of model predictions are evaluated by comparison with known exact results in particular cases, with simulation experiments and with the approximation method of Kobayashi and Reiser.     

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.     

Approximating queue lengths inM(t)/G/1 queue using the maximum entropy principle

Using the discrete time approach a model is developed for obtaining the expected queue length of theM(t)/G/1 queue. This type of queue occurs in different forms in transportation and traffic systems and in communications and manufacturing systems. In order to cut down the very high computational efforts required to evaluate the performance measures in such queues by exact methods, the Maximum Entropy Principle is used to approximate the expected queue length which is one of the most commonly used performance measures. A procedure is then developed for reducing the error encountered when this approximation is adopted. The results from this paper will encourage the practitioners to use the appropriate time-varying queueing models when the need arises instead of resorting to very poor approximations.     

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.     

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.     

Stability of Parallel Queueing Systems with Coupled Service Rates

This paper considers a parallel system of queues fed by independent arrival streams, where the service rate of each queue depends on the number of customers in all of the queues. Necessary and sufficient conditions for the stability of the system are derived, based on stochastic monotonicity and marginal drift properties of multiclass birth and death processes. These conditions yield a sharp characterization of stability for systems where the service rate of each queue is decreasing in the number of customers in other queues, and has uniform limits as the queue lengths tend to infinity. The results are illustrated with applications where the stability region may be nonconvex.     

On tandem blocking queues with a common retrial queue

We consider systems of tandem blocking queues having a common retrial queue. The model represents dynamics of short TCP transfers in the Internet. Analytical results are available only for a specific example with two queues in tandem. We propose approximation procedures involving simple analytic expressions, based on mean value analysis (MVA) and on fixed point approach (FPA). The mean sojourn time of a job in the system and the mean number of visits to the orbit queue are estimated by the MVA which needs as an input the fractions of blocked jobs in the primary queues. The fractions of blocked jobs are estimated by FPA. Using a benchmark example of the system with two primary queues, we conclude that the approximation works well in the light traffic regime. We note that our approach becomes exact if the blocking probabilities are fixed. Finally, we consider two optimization problems regarding minimizing mean total sojourn time of a job in the system: (i) finding the best order of queues and (ii) allocating a given capacity among the primary queues.     

Waiting-time approximations for cyclic-service systems with switchover times

Mean waiting-time approximations are derived for a single-server multi-queue system with nonexhaustive cyclic service. Nonzero switchover times of the server between consecutive queues are assumed. The main tool used in the derivation is a pseudo-conservation law recently found by Watson (1984). The approximation is simpler and, as extensive simulations show, more accurate than existing approximations. Moreover, it gives very good insight into the qualitative behaviour of cyclic-service queueing systems.     

Local area networks supporting speech traffic

This paper presents a new analytical model for estimating the average queue length and the average queueing delay of data packets in a SENET-like integrated voice and data system. The analytical model also computes the mean queue lengths and average queueing delays of data packets for every number of calls allowed in the system. The analysis uses the fluid flow approximation of data queues. The equations used to represent the integrated system provide further insight into the system behavior and can be useful to similar systems. The method presented here is easy to apply, avoids the numerical difficulties of other methods in the literature, and yields estimates in very good agreement with simulation results. Also presented is a new flow control procedure that significantly improves the delay performance and considerably reduces the mean data queue length.     

The influence of service-time variability in a closed network of queues

This paper describes the effect of service-time variability on the standard performance measures of a closed network of single-server queues with the first-come first-served discipline and one job class. Several service-time variability principles are proposed to serve as rough practical guidelines. The most interesting one states that the mean queue length at a bottleneck queue typically decreases when the variability of the service time at that queue is increased. The principles are supported here by numerical examples and theorems in special cases. The principles are also applied to test approximation procedures.     

Throughput 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 first define the average rate as observed by users and by the queue. In an M/M/1 processor-sharing queue, we give closed-form expressions for these average rates, and prove a strict ordering amongst them. We prove that the queue service rate (in bps) is an increasing function of the minimum required average transmission rate, and give a closed-form expression for the marginal cost associated with such a performance requirement. We then consider the effect of using connection access control by modeling an M/M/1/K processor-sharing queue. We give closed-form expressions for average transmission rates, and discuss the relationship between the queue service rate (in bps), the queue limit, the average rate, and the blocking probability     

On a batch arrival Poisson queue with a random setup time and vacation period

The single server queue with vacation has been extended to include several types of extensions and generalisations, to which attention has been paid by several researchers (e.g. see Doshi, B. T., Single server queues with vacations — a servey. Queueing Systems, 1986, 1, 29–66; Takagi, H., Queueing Analysis: A Foundation of Performance evaluation, Vol. 1, Vacation and Priority systems, Part. 1. North Holland, Amsterdam, 1991; Medhi, J., Extensions and generalizations of the classical single server queueing system with Poisson input. J. Ass. Sci. Soc., 1994, 36, 35–41, etc.). The interest in such types of queues have been further enhanced in resent years because of their theoretical structures as well as their application in many real life situations such as computer, telecommunication, airline scheduling as well as production/inventory systems. This paper concerns the model building of such a production/inventory system, where machine undergoes extra operation (such as machine repair, preventive maintenance, gearing up machinery, etc.) before the processing of raw material is to be started. To be realistic, we also assume that raw materials arrive in batch. This production system can be formulated as an M^x/M/1 queues with a setup time. Further, from the utility point of view of idle time this model can also be formulated as a case of multiple vacation model, where vacation begins at the end of each busy period. Besides, the production/inventory systems, such a model is generally fitted to airline scheduling problems also. In this paper an attempt has been made to study the steady state behavior of such an M^x/M/1 queueing system with a view to provide some system performance measures, which lead to remarkable simplification when solving other similar types of queueing models.This paper deals with the steady state behaviour of a single server batch arrival Poisson queue with a random setup time and a vacation period. The service of the first customer in each busy period is preceded by a random setup period, on completion of which service starts. As soon as the system becomes empty the server goes on vacation for a random length of time. On return from vacation, if he finds customer(s) waiting, the server starts servicing the first customer in the queue. Otherwise it takes another vacation and so on. We study the steady state behaviour of the queue size distribution at random (stationary) point of time as well as at departure point of time and try to show that departure point queue size distribution can be decomposed into three independent random variables, one of which is the queue size of the standard M^x/M/1 queue. The interpretation of the other two random variables will also be provided. Further, we derive analytically explicit expressions for the system state (number of customers in the system) probabilities and provide their appropriate interpretations. Also, we derive some system performance measures. Finally, we develop a procedure to find mean waiting time of an arbitrary customer.     

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.     

Approximate analysis of a discrete-time tandem network of cut-through queues with blocking and bursty traffic

A discrete-time tandem network of cut-through queues is presented. The model allows finite capacity queues, blocking, and bursty traffic. A new bursty arrival process, IBK(k), for cut-through traffic is introduced. The tandem network is analyzed using single-node decomposition. Each queue is analyzed numerically in isolation assuming that its arrival and service processes are known. The parameters of the arrival and service processes of the queues are obtained using an iterative scheme. The results obtained are approximate and validation tests have shown that the model has good accuracy. Using this model, the packet loss, throughput, and queue length distributions were obtained for different traffic parameters and queue sizes.     

两类服务对象轮询模型的平均运行周期

系统地研究了两类服务对象轮询服务模型的平均运行周期．首先扩展了现有的每队列只具有单类服务对象的单类服务对象轮询服务模型，提出了每队列内具有两类服务对象的两类服务对象轮询服务模型(这两类对象分别采用门限服务和限定服务)．然后，在该模型稳定条件下，通过构造出队列队长的嵌入式马尔可夫链、概率母函数和Laplace-Stieltje变换，求解出平衡状态下该模型的平均运行周期．并且，通过指出队列稳定性与模型稳定性之间的差异，给出了在部分或者全部的限定式服务队列不稳定时．模型的平均运行周期．最后仿真验证了理论结果的正确性．