Modelling congestion in closed queueing networks

We will consider the problem of identifying regions of congestion in closed queueing networks with state-dependent service rates. A particular queue will be called a bottleneck if the number of customers in that queue grows without bound as the total number of customers in the network becomes large. We will review methods for identifying potential bottlenecks, with a view to controlling congestion. We will see that the problem of identifying bottlenecks can be reduced to one of finding them in an isolated subnetwork with suitably modified routing intensities. Several special cases will be studied, illustrating a range of behaviour. For example, it is possible for a subnetwork to be congested, yet each queue in that subnetwork is not strictly a bottleneck.     

Throughput bounds for closed queueing networks

Analytical lower and upper bounds for the throughput of closed queueing networks with single and delay (infinite) servers are studied in this paper. The numerical evaluation of these bounds requires a small number of significant operations which is independent of the population N. This is in contrast to the exact computation of the throughput which requires at least O(N) operations as N tends to infinity. The bounds are given by simple closed-form analytical expressions and may be more suitable for various performance studies than the algorithmical form of the exact solution.In this paper, the previously known balanced-job bounds are generalized to networks containing delay servers (terminals) and a hierarchy of bounds is obtained for single and multiple class networks. For the single class network, further new bounds are derived: lower and upper bounds that require the evaluation of one square root and an upper bound that requires a constant number of exponentiations. This upper bound does not employ the balancing of server loadings and is especially useful for asymptotic analysis in the case of a large number of customers N.     

Mean-value analysis and convolution method for queue-dependent servers in closed queueing networks

In this paper, we formulate a recursive relation for the marginal probabilities of a closed network with K customers in terms of the same network with K ? 1 customers. Mean-value analysis (MVA) is an application of this relation, together with Little's formula. It is shown that the convolution method, too, can be based on the same recursive result. This leads to a new convolution algorithm called normalized convolution algorithm (NCA), which like MVA works entirely with probabilities and throughputs rather than with quantities such as normalization contacts. NCA avoids a difficult problem, the occurrence of floating-point over-flows in the original convolution algorithm.We shall also solve a numerical stability problem found in MVA. Finally, we show how MVA and the convolution algorithm can be combined in the same problem to yield a hybrid method retaining the best properties of both methods.     

A generalized method of moments for closed queueing networks

We introduce a new solution technique for closed product-form queueing networks that generalizes the Method of Moments (MoM), a recently proposed exact algorithm that is several orders of magnitude faster and memory efficient than the established Mean Value Analysis (MVA) algorithm. Compared to MVA, MoM recursively computes higher-order moments of queue lengths instead of mean values, an approach that remarkably reduces the computational costs of exact solutions, especially on models with large numbers of jobs.In this paper, we show that the MoM recursion can be generalized to include multiple recursive branches that evaluate models with different numbers of queues, a solution approach inspired by the Convolution algorithm. Combining the approaches of MoM and Convolution simplifies the evaluation of normalizing constants and leads to large computational savings with respect to the recursive structure originally proposed for MoM.     

Approximations for large scale closed queueing networks

Evaluation of closed queueing networks with product form solutions is very time-consuming if the population sizes or the network size is large. This paper provides an analysis of an approximation technique, based upon mean value analysis which requires considerably less computation time, and yet achieves a high degree of accuracy. The approximates are unique in some feasible regions. Error analysis and illustrative examples are provided.     

Equivalencies between open and closed queueing networks with finite buffers

Equivalencies between open and closed models of queueing networks with finite buffers are investigated. Interarrival times in open networks and service times are assumed to be exponentially distributed. Using these equivalencies, bounds on the throughput of open networks are established.     

On the nonconcavity of throughput in certain closed queueing networks

Analytic queueing network models are being used to analyze various optimization problems such as server allocation, design and capacity issues, optimal routing, and workload allocation. The mathematical properties of the relevant performance measures, such as throughput, are important for optimization purposes and for insight into system performance.We show that for closed queueing networks of m arbitrarily connected single server queues with n customers, throughput, as a function of a scaled, constrained workload, is not concave. In fact, the function appears to be strictly quasiconcave. There is a constraint on the total workload that must be allocated among the servers in the network. However, for closed networks of two single server queues, we prove that our scaled throughput is concave when there are two customers in the network and strictly quasi-concave when there are more than two customers. The mathematical properties of both the scaled throughput and reciprocal throughput are demonstrated graphically for closed networks of two and three single server queues.     

Characteristics of optimal workload allocation for closed queueing networks

We consider the problem of allocating a given workload among the stations in a multi-server product-form closed queueing network to maximize the throughput. We first investigate properties of the throughput function and prove that it is pseudoconcave for some special cases. Some other characteristics of the optimal workload and its physical interpretation are also provided. We then develop two computational procedures to find the optimum workload allocation under the assumption that the throughput function is pseudoconcave in general. The primary advantage of assuming pseudoconcavity is that, under this assumption, satisfaction of first order necessary conditions is sufficient for optimality. Computational experience with these algorithms provides additional support for the validity of this assumption. Finally, we generalize the solution procedure to accommodate bounds on the workloads at each station.     

Higher-order distributional properties in closed queueing networks

In many real-life computer and networking applications, the distributions of service times, or times between arrivals of requests, or both, can deviate significantly from the memoryless negative exponential distribution that underpins the product-form solution for queueing networks. Frequently, the coefficient of variation of the distributions encountered is well in excess of one, which would be its value for the exponential. For closed queueing networks with non-exponential servers there is no known general exact solution, and most, if not all, approximation methods attempt to account for the general service time distributions through their first two moments.We consider two simple closed queueing networks which we solve exactly using semi-numerical methods. These networks depart from the structure leading to a product-form solution only to the extent that the service time at a single node is non-exponential. We show that not only the coefficients of variation but also higher-order distributional properties can have an important effect on such customary steady-state performance measures as the mean number of customers at a resource or the resource utilization level in a closed network.Additionally, we examine the state that a request finds upon its arrival at a server, which is directly tied to the resulting quality of service. Although the well-known Arrival Theorem holds exactly only for product-form networks of queues, some approximation methods assume that it can be applied to a reasonable degree also in other closed queueing networks. We investigate the validity of this assumption in the two closed queueing models considered. Our results show that, even in the case when there is a single non-exponential server in the network, the state found upon arrival may be highly sensitive to higher-order properties of the service time distribution, beyond its mean and coefficient of variation.This dependence of mean numbers of customers at a server on higher-order distributional properties is in stark contrast with the situation in the familiar open M/G/1 queue. Thus, our results put into question virtually all traditional approximate solutions, which concentrate on the first two moments of service time distributions.     

Implementation of Monte Carlo integration for the analysis of product-form queueing networks

MonteQueue is a new public-domain software package which rapidly solves large and small multiclass product-form queueing networks with multiple- and single-server stations over a wide range of traffic conditions. MonteQueue obtains estimates of performance measures by applying importance sampling to sum and integral representations of the network's normalization constants. This paper discusses the implementation issues and surveys of the theoretical properties of the four importance sampling techniques included in MonteQueue. It also presents new numerical data which compare the performance of the four techniques.     

Feedback invariant discipline and insensitivity in closed queueing networks

Motivated by control theory concepts, we investigate a closed queueing network by adding a feedback path to each node. A feedback invariant service discipline is introduced. This approach differs from the conventional queueing theory approach and provides a new criteria and an intuitive explanation for the insensitivity property in a closed queueing network.     

Regularizability of complex switched server queueing networks modelled as hybrid dynamical systems

The paper considers the problem of the qualitative analysis of complex switched server queueing networks. Such networks can be used to model various flexible manufacturing, communications, and computer systems. We introduce the concept of regularizability for such systems and obtain a necessary and sufficient condition for a switched server queueing network to be regularizable.     

An analysis of an approximation algorithm for queueing networks

Queueing network models have proved to be useful aids in computer system performance prediction. Numerous approximation algorithms have been devised to allow queueing networks to be analyzed with a reduced computational expense. In particular, for separable queueing networks several popular iterative approximation algorithms are available.

One disadvantage of these algorithms has been the lack of results concerning their behavior, such as whether or not iteration convergence is guaranteed. This paper presents an analysis of an approximate MVA algorithm proposed by Schweitzer (1979). It is proved that the equations defining the algorithm have a unique solution when there is only a single customer class, and iteration initializations that yield monotonic convergence to this solution are exhibited. It is also proved that the solution is pessimistic relative to the exact queueing network solution.     

A unified view of product-form approximation techniques for general closed queueing networks

Two major approximate techniques have been proposed for the analysis of general closed queueing networks, namely the aggregation method and Marie's method. The idea of the aggregation technique is to replace a subsystem (a subnetwork) by a flow equivalent single-server with load-dependent service rates. The parameters of the equivalent server are obtained by analyzing the subsystem in isolation as a closed system with different populations. The idea of Marie's method is also to replace a subsystem by an equivalent exponential service station with load-dependent service rates. However, in this case, the parameters of the equivalent server are obtained by analyzing the subsystem in isolation under a load-dependent Poisson arrival process. Moreover, in Marie's case, the procedure is iterative.

In this paper we provide a general and unified view of these two methods. The contributions of this paper are the following. We first show that their common principle is to partition the network into a set of subsystems and then to define an equivalent product-form network. To each subsystem is associated a load-dependent exponential station in the equivalent network. We define a set of rules in order to partition any general closed network with various features such as general service time distributions, pupulation constraints, finite buffers, state-dependent routing. We then show that the aggregation method and Marie's method are two ways of obtaining the parameters of the equivalent network associated with a given partition. Finally, we provide a discussion pertaining to the comparison of the two methods with respect to their accuracy and computational complexity.     

An iterative method for computing closed queueing networks

An iterative method is proposed for calculating closed queueing networks. The method successively calculates the state probabilities of each server treated as a closed queueing system.Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 181–183, March–April, 1992.     

Sensitivity results in open, closed and mixed product form queueing networks

General formulas are proposed to quantify the effects of changing the model parameters in the so-called BCMP network [F. Baskett et al., J. ACM 22 (2) (April 1975) 248–260]. These formulas relate the derivative of the expectation of any function of both the state and the paramaters of the network with respect to any model parameter (i.e., arrival rate, mean service demand, service rate, visit ratio, traffic intensity) to known functions of the state variables. Applications of our results to sensitivity analysis and optimization problems are given.     

Approximation models of feed-forward G/G/1/N queueing networks with correlated arrivals

In this paper we develop approximation models for feed-forward networks of G/G/1/N queues. We use Linear Algebra Queueing Theory (LAQT) techniques to create reduced state space representations for the queue departure processes. Reduced state space departure processes are presented where the first three moments and the correlation decay are mapped to a two state process. A three state process is also presented matching the first five moments and the first three lag autocorrelations. Numerical examples of end-to-end performance for high-speed communications networks with correlated arrival traffic are presented. The results are compared with simulation models and other approximation methods.     

Computational aspects of aggregation in multiple class queueing networks

We extend the convolution and mean value analysis algorithms to incorporate composite servers that result from the aggregation of stations in a multiple class queueing network model. The method defines a new composite server device factor that is used in the product form solution of the aggregated network. The approximate analysis of multiclass networks can then be handled in a computationally efficient manner provided that a sufficient condition is satisfied.     

Accuracy of approximating queueing network departure processes with independent renewal processes

A distributed and fully symmetric solution is presented for the distributed termination problem. In contrast to the existing solutions, the above solution does not require a predesignated process to detect termination. The case of asynchronous communications is also discussed.     

A customer threshold property for closed finite queueing networks

We present a new class of finite queues in cyclic networks with production blocking. We show that with a threshold property related to the number of customers in the network, these queues are insensitive to the allocation of buffers and the order of the stations. In addition, some simple and practical, yet effective approximations are presented. Numerical examples have been carried out to demonstrate the efficacy of the approaches.