Approximate analysis of product-form type queueing networks with blocking and deadlock

A numerical procedure for analyzing exactly closed exponential queueing networks with finite queues is presented first. Due to the finiteness of these queues, blocking and deadlock may occur. Deadlocks are assumed to be detected and resolved instantaneously. The numerical procedure is then incorporated in an approximation algorithm for analyzing closed exponential queueing networks of the product-form type, in which some of the queues are finite. These finite queues are assumed to be linked together to form a single subnetwork. The approximation algorithm is based on a variant of Norton's theorem. Comparisons between the approximate results and exact numerical results were carried out and the relative error was observed to be 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.     

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     

A hybrid method for performance analysis of G/G/m queueing networks

Open queueing networks are useful for the performance analysis of numerous real systems. Since exact results exist only for a limited class of networks, decomposition methods have been extensively used for approximate analysis of general networks. This procedure is based on several approximation steps. Successive approximations made in this approach can lead to a considerable error in the output. In particular, there are no general accurate formulas for computing the mean waiting time and the inter-departure variance in general multiple-server queues. This causes the results from decomposition methods when applied to G/G/m queueing networks to be very approximative and to significantly deviate from actual performance values. We suggest substituting some approximate formulae by low-cost simulation estimates in order to obtain more accurate results when benefiting from the speed of an analytical method. Numerical experiments are presented to show that the proposed approach provides improved performance.     

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.     

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.     

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.     

Analysis of a two-layered network by means of the power-series algorithm

We consider an extension of the classical machine-repair model, also known as the computer-terminal model or time-sharing model. As opposed to the classical model, we assume that the machines, apart from receiving service from the repairman, supply service themselves to queues of products. The extended model can be viewed as a two-layered queueing network, of which the first layer consists of two separate queues of products. Each of these queues is served by its own machine. The marginal and joint queue length distributions of the first-layer queues are hard to analyse in an exact fashion. Therefore, we apply the power-series algorithm to this model to obtain the light-traffic behaviour of the queue lengths symbolically. This leads to two accurate approximations for the marginal mean queue length. The first approximation, based on the light-traffic behaviour, is in closed form. The second approximation is based on an interpolation between the light-traffic behaviour and heavy-traffic results for the mean queue length. The obtained approximations are shown to work well for arbitrary loaded systems. The proposed numerical algorithm and approximations may prove to be very useful for system design and optimisation purposes in application areas such as manufacturing, computer systems and telecommunications.     

An Extension of Norton's Theorem for Queueing Networks

Given a closed BCMP queueing network, the problem is considered of studying the behavior of any subsystem a without solving for the entire system. This paper proves that this is possible for a consisting of any number of queues, arbitrarily interfacing the rest of the system, thus generalizing the classic CHW theorem, also known as Norton's theorem. A general flow-equivalent solution procedure is given and its computational complexity is compared with that of the product-form and the exact aggregation procedure. The relative merits of these procedures are also expressed in terms of a's cardinality.     

An Approximate Analytical Method for General Queueing Networks

In this paper, we present an approximate solution for the asymptotic behavior of relatively general queueing networks. In the particular case of networks with general service time distributions (i.e., fixed routing matrix, one or many servers per station, FIFO discipline), the application of the method gives relatively accurate results in a very short time. The approximate stationary state probabilities are identified with the solution of a nonlinear system. The proposed method is applicable to a larger class of queueing networks (dependent routing matrix, stations with fimite capacity, etc.). In this case, the structure of the network studied must satisfy certain decomposability conditions.     

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

Asymptotic analysis of memory interference in multiprocessors with private cache memories

A closed Markovian queueing network model of a multiprocessor system with a two-level memory hierarchy is considered. Performance measures are introduced and obtained from the partition function. With a special structure of branching probabilities the network model is reduced to a nonlinear machine interference model. Asymptotic representation of the stationary distribution for heavy traffic conditions in the latter model is used for deriving approximate formulas for the performance measures when the number of processors and memory modules is large. For normal usage the approximations are obtained from asymptotic expansions of the partition function.     

Continuous and Discrete Trajectory Models for Dynamic Traffic Assignment

A continuous trajectory model is presented in which transportation networks are represented as topological constructs. The general formulation enhances existing analytic dynamic traffic assignment models by incorporating continuous single-link traffic flow models in a general, coherent, and relatively intuitive manner. Specific exact formulation based on a simplified kinematic wave traffic flow model with physical queues is presented as well.A discrete trajectory model is proposed as an approximation of the continuous model. The discrete model provides wide flexibility in choosing the level of aggregation with respect to time intervals, ranging from several hours, as typical in current practice of long-term travel forecasting models, to one second or less, as in microscopic simulations. An algorithm to find discrete approximate solutions is presented as well as accuracy measures to evaluate them. The effect of time resolution on model performance is examined by a numerical example.     

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.     

Markov-chain model and algorithmic procedure for the performance analysis of closed cyclic queues

This paper presents a model and an algorithmic procedure to analyze closed cyclic queues that are subject to blocking. We consider the first two moments of the processing time and present the fitting of phase-type distributions such that the number of phases and transitions is minimal. Using phase-type distributions, we enable the analysis of queueing systems with processing times with any coefficient of variation. We model the closed cyclic queues subject to blocking as continuous-time Markov chains. The implementation procedure covers the state-space generation and the determination of the infinitesimal generator matrix. Apart from rounding errors, we obtain exact results for the queueing model this way. The results are useful as reference values for the output of approximate approaches. Further, the algorithmic procedure enables a repeated analysis of different configuration alternatives as needed in optimization procedures. Though the method is very fast for small cyclic queues, it takes a long computation time for larger systems. Furthermore, the size of the queueing model to be analyzed is restricted due to the limited working memory with its present-day capacity. In a numerical study, the computation times for different configurations are investigated, limits in the size of the applicable queueing model are given, and numerical results of the performance measures are provided.     

The AMVA priority approximation

Most computer systems contain one or more system resources whose usage is controlled on the basis of workload priorities. Unfortunately, the exact analysis of queueing network models incorporating priority scheduling disciplines is usually infeasible. The MVA Priority Approximation has been proposed as a comparatively inexpensive, and yet reasonably accurate, approximation technique for queueing networks with priority scheduled service centers. Even this algorithm, however, is too expensive to apply to large networks with many classes of customers.In this paper, we show how the MVA Priority Approximation can be modified so that it utilizes approximate rather than exact Mean Value Analysis (MVA), without significant loss of accuracy. Extensive numerical experiments are performed to further assess the accuracy of the modified algorithm, termed here the AMVA Priority Approximation. These experiments utilize the parameter space mapping technique for studying ‘local’ queueing network approximations.     

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.     

An approximate compositional approach to the analysis of fluid queue networks

Fluid models have for some time been used to approximate stochastic networks with discrete state. These range from traditional ‘heavy traffic’ approximations to the recent advances in bio-chemical system models. Here we present a simple approximate compositional method for analysing a network of fluid queues with Markov-modulated input processes at equilibrium. The idea is to approximate the on/off process at the output of a queue by an n-state Markov chain that modulates its rate. This chain is parameterised by matching the moments of the resulting process with those of the busy period distribution of the queue. This process is then used, in turn, as a separate Markov-modulated on/off process that feeds downstream queue(s). The moments of the busy period are derived from an exact analytical model. Approximation using two- and three-state intermediate Markov processes are validated with respect to an exact model of a tandem pair of fluid queues — a generalisation of the single queue model. The analytical models used are rather simpler and more accessible, albeit less general, than previously published models, and are also included. The approximation method is applied to various fluid queue networks and the results are validated with respect to simulation. The results show the three-state model to yield excellent approximations for mean fluid levels, even under high load.     

A recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks

This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are block-structured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures can be calculated.Scope and purposeThe exact analysis of queueing networks with multiple servers at each workstation and finite capacities of the intermediate queues is extremely difficult as for even the case of exponential operation (service or processing) times the Markovian chain that models the system consists of a huge number of states which grows exponentially with the number of stations, the number of servers at each station and the queue capacity of each intermediate queue of the resulting system. The scope and purpose of the present paper is to analyze and provide a recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks. By applying the proposed algorithm one may create the transition matrix of a K-station queueing network for any K. This process allows one to obtain the exact solution of the resulting large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures of the system can be obtained.