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.     

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.     

Perfect sampling for closed queueing networks

In this paper we investigate coupling from the past (CFTP) algorithms for closed queueing networks. The stationary distribution has a product form only in a very limited number of particular cases when queue capacity is finite, and numerical algorithms are intractable due to the cardinality of the state space. Moreover, closed networks do not exhibit any monotonic property enabling efficient CFTP. We derive a bounding chain for the CFTP algorithm for closed queueing networks. This bounding chain is based on a compact representation of sets of states that enables exact sampling from the stationary distribution without considering all initial conditions in the CFTP. The coupling time of the bounding chain is almost surely finite, and numerical experiments show that it is close to the coupling time of the exact chain.     

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.     

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.     

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.     

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.     

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.     

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.     

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 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.     

Performance evaluation of multicast communication in packet-switched networks

In this paper we describe the theoretical background and practical application of QNA-MC (queueing network analyser supporting multicast), a tool for the analytical evaluation of multicast protocols. QNA-MC is based on the QNA method, which (approximately) analyses open networks of GI|G|m queues. In contrast to standard QNA, QNA-MC allows for the specification and evaluation of multicast routes. As in real multicast communication, packets leaving a particular node can be copied and deterministically routed to several other nodes. In order to analyse such queueing networks, QNA-MC converts the multicast routes to a suitable input for standard QNA. From the results delivered by QNA, QNA-MC then derives several performance measures for multicast streams in the network. A validation of QNA-MC, via a comparison to simulation results, shows that QNA-MC yields very good results. Finally, we give a detailed application example by evaluating different multicast routing algorithms for a realistic video conferencing scenario in the European MBONE.     

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.     

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.     

Two classes of performance bounds for closed queueing networks

Two classes of performance bounds for separable queueing networks are presented, one for single-chain networks and one for multichain networks. Unlike most bounds for single-chain networks, our bounds are not based upon the consideration of balanced networks. Instead, they are obtained by assuming mean queue lengths to be proportional to server loads; hence, they are called proportional bounds. Proportional bounds are tighter than balanced bounds because individual server loads are retained as parameters in a bound's formula. For the same reason, they require more computational effort than balanced bounds. We also show how proportional bounds are related to balanced bounds. Next we present generalized bounds that are calculated iteratively over sequences of population sizes; our method extends that of Eager and Sevcik (1983). These generalized bounds are shown to have a nested property. Furthermore, we present optimal population sequences, over all sequences of the same length, for getting the tightest upper and lower bounds. The other emphasis of this paper is on performance bounds for networks with many closed chains and many service centers. Bounding techniques are especially important for multichain networks since the computation time and space requirements are often so large that an exact solution is not feasible. Models of communication networks typically have many routing chains which are characterized by a sparseness property. In the computation of our performance bounds for multichain networks, we improve their accuracy by making use of routing information and exploiting the sparseness property.     

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 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.     

A systematic method for efficient computation of full and subsets Zernike moments

A new method is proposed for fast and accurate computation of Zernike moments. This method presents a novel formula for computing exact Zernike moments by using exact complex moments where the exact values of complex moments are computed by mathematical integration of the monomials over digital image pixels. The proposed method is applicable to compute the full set of Zernike moments as well as the subsets of individual order, repetition and an individual moment. A comparison with other conventional methods is performed. The results show the superiority of the proposed method.