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.     

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.     

An approximation method for a class of queueing systems

We consider a queueing system with an ordered hunt. Specifically, we consider a communication system in which messages arrive at a node that has n output links numbered 1,…,n, and an arriving message is processed by the lowest numbered idle link. Obtaining such steady-state parameters as the expected delay of an arbitrary message and the utilization factor of each link requires knowledge of the complete state space of the system and the solution of 2ⁿ linear equations. In this paper we develop a method of computing the approximate values of these parameters without the need for the knowledge of the complete state space and the solution of 2ⁿ linear equations.     

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.     

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.     

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.     

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.     

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.     

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.     

A generalisation of Norton's theorem for multiclass queueing networks

Consider an arbitrary subset σ of service centres in a locally balanced multiclass queueing network for which a parametric analysis is to be undertaken. It is shown that the complete network only has to be solved once using the convolution algorithm, after which statistical measures for σ can be calculated repeatedly without re-evaluating the rest of the network. It has also been proved that the concept of replacing a subnetwork in a closed multiclass queueng network with a single composite service centre with a state dependent service rate (also called Norton's Theorem for queuing networks) is a very special case of the more general result mentioned above. An example is given in which the theoretical results are applied when σ is a subnetwork of a closed multiclass queueing network satisfying local balance.     

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.     

A new convolution algorithm for loss probability analysis in multiservice networks

Performance analysis in multiservice loss systems generally focuses on accurate and efficient calculation methods for traffic loss probability. Convolution algorithm is one of the existing efficient numerical methods. Exact loss probabilities are obtainable from the convolution algorithm in systems where the bandwidth is fully shared by all traffic classes; but not available for systems with trunk reservation, i.e. part of the bandwidth is reserved for a special class of traffic. A proposal known as asymmetric convolution algorithm (ACA) has been made to overcome the deficiency of the convolution algorithm. It obtains an approximation of the channel occupancy distribution in multiservice systems with trunk reservation. However, the ACA approximation is only accurate with two traffic flows; increased approximation errors are observed for systems with three or more traffic flows.In this paper, we present a new Permutational Convolution Algorithm (PCA) for loss probability approximation in multiservice systems with trunk reservation. This method extends the application of the convolution algorithm and overcomes the problems of approximation accuracy in systems with a large number of traffic flows. It is verified that the loss probabilities obtained by PCA are very close to the exact solutions obtained by Markov chain models, and the accuracy outperforms the ACA approximation.     

Simulation for passage times in closed, multiclass networks of queues with unrestricted priorities

Regenerative simulation for passage times in networks of queues with priorities among job classes (and one or more job types) can be based on observation of a fully augmented job stack process which maintains the position of each of the jobs in a linear ‘job stack’, an enumeration of the jobs by service center and job class. In this paper we develop an estimation procedure for passage times through a subnetwork of queues. Observed passage times for all the jobs enter into the construction of point and interval estimates. The confidence intervals obtained using this estimation procedure are shorter than those obtained from simulation using a marked job.     

SNAPL/1: A language to describe and evaluate queuing network models

Recent theoretical developments in queuing theory have made multiclass queuing network models a viable alternative to established simulation methods for the analysis of dynamic systems. Computer software is required to describe and solve such network models. This paper describes a language which provides the human interface to a particular multiclass queuing network modelling package. The discussion is illustrated with an example from the language and concludes with suggestions for improvements.     

Fluid limits and diffusion approximations for networks of multi-server queues in heavy traffic

A Functional Strong-Law-of-Large-Numbers (known as fluid limit or fluid approximation) and a Functional Central Limit Theorem (known as diffusion approximation) are proved for both open and closed networks of multi-server queues in heavy traffic. The fluid limit is a reflected piecewise linear deterministic process, and the diffusion limit is a reflected Brownian motion; both limiting processes are on the nonnegative orthant for open networks and on the nonnegative unit simplex for closed networks. The results generalize the existing ones for networks of single-server queues.     

Combining Bayesian Networks and Total Cost of Ownership method for supplier selection analysis

In this study, we analyze the supplier selection process by combining Bayesian Networks (BN) and Total Cost of Ownership (TCO) methods. The proposed approach aims to efficiently incorporate and exploit the buyer’s domain-specific information when the buyer has both limited and uncertain information regarding the supplier. This study examines uncertainty from a total cost perspective, with regards to causes of supplier performance and capability on buyer’s organization. The proposed approach is assessed and tested in automotive industry for tier-1 supplier for selecting its own suppliers. To efficiently facilitate expert opinions, we form factors to represent and explain various supplier selection criteria and to reduce complexity. The case study in automotive industry shows several advantages of the proposed method. A BN approach facilitates a more insightful evaluation and selection of alternatives given its semantics for decision making. The buyer can also make an accurate cost estimation that are specifically linked with suppliers’ performance. Both buyer and supplier have clear vision to reduce costs and to improve the relations.     

Fast algorithm for multicast and data gathering in wireless networks

Given a wireless network G=(V,E), we consider a maximum critical energy problem [J. Park, S. Sahni, Maximum lifetime broadcasting in wireless networks, IEEE Transactions on Computers 54 (9) (2005) 1081–1090] that has an objective of increasing the chances of doing a sequence of broadcasts. We present an optimal generalized solution algorithm running in improved optimal O(|V|+|E|) time, where V stands for a set of nodes and E stands for a set of links in the network. Our approach is applicable in an omnidirectional antenna model and can be used to solve the problem of multicasting traffic so as to maximize the lifetime of the network [A. Orda, B.-A. Yassour, Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas, in: Proc. ACM MOBIHOC, 2005] and a data gathering problem [K. Kalpakis, K. Dasgupta, P. Namjoshi, Maximum lifetime data gathering and aggregation in wireless sensor networks, Computer Networks 42 (2003) 697–716; Y. Xue, Y. Cui, K. Nahrstedt, Maximizing lifetime for data aggregation in wireless sensor networks, ACM Moble Networks and Applications 10 (6) (2005) 853–864] with an improved running time.     

Design and analysis of a stable set-up protocol for transcoding multicast trees in active networks

Based on active networking, an advanced streaming service was designed to offer different formats of the same stream using a single multicast tree. To that end, the initial format of the stream that is sent into the tree is transcoded to the other requested formats in the nodes of the tree, based on application level functionality residing in these network nodes. To set up such a multicast tree (including the necessary forwarding state in the nodes) and to install the necessary functionality in the nodes, a number of tree set-up procedures were designed. In this paper, performance aspects of these procedures are investigated: the stability and consistency of the forwarding state during the set-up procedures and the influence of dynamic user behaviour on the multicast tree. This performance assessment is based on a thorough analysis of the different set-up procedures and on simulations of the procedures. Based on the analysis, it is seen that great care must be taken during the set-up procedures in order to avoid interference with the existing streams. Therefore, extensions for the procedures are proposed. Furthermore, the influence of dynamic user behaviour on session state and performance attributes is analysed.