Computational algorithms for networks of queues with rejection blocking

Summary Open, closed and mixed queueing networks with reversible routing, multiple job classes and rejection blocking are investigated. In rejection blocking networks blocking event occurs when upon completion of its service of a particular station's server, a job attempts to proceed to its next station. If, at that moment, its destination station is full, the job is rejected. The job goes back to the server of the source station and immediately receives a new service. This is repeated until the next station releases a job and a place becomes available. In the model jobs may change their class membership and general service time distributions depending on the job class are allowed. Two station types are considered: Either the scheduling discipline is symmetric, in which case the service time distributions are allowed to be general and dependent on the job class or the service time distributions at a station are all identical exponential distributions, in which case more general scheduling disciplines are allowed. An exact product form solution for equilibrium state probabilities is presented. Using the exact product form solution of the equilibrium state distribution, algorithms for computation of performance measures, such as mean number of jobs and throughputs, are derived. The complexity of the algorithms is discussed.     

Performance analysis of a virtual circuit protocol with local control

In many current packet switching networks, packets are transmitted sequentially by means of so-called virtual circuits. In this paper, a queueing network model for a virtual circuit with local buffer size constraints and blocking at the intermediate nodes is derived and analysed. The analysis is based on the decomposition of the fixed virtual route into its individual links. Each hop is modelled as a closed BCMP queueing network. The introduction of the steady-state blocking probability p as the characterizing parameter of the interface between two consecutive links permits the recursive computation of important design parameters, such as throughput, utilization, and mean transmission time. A modified rejection probability, introduced to describe the behaviour at the interface more accurately, supports the previous results.     

New performance sensitivity formulae for a class of product-form queueing networks

Perturbation analysis (PA) applies a dynamic point of view to the sample paths of stochastic systems; the realization factor, one of the main concepts of PA, measures the final effect of a perturbation on system performance and provides a novel approach in obtaining performance sensitivities. In this paper, we solve analytically the set of equations for realization factors of a two-server cyclic network. We prove an invariance property of the performance sensitivity for Norton's aggregation. Using the results, we derive closed-form formulae for the derivatives of performance measures in a closed queueing network with load-dependent exponential servers. The performance measures have two general forms: customer average and time average. In contrast with the usual approach based on product-form solutions, our results provide additional insights into the performance sensitivity of closed queueing networks and have immediate applications to problems of optimal control. The general formulae are expressed in terms of Buzen's algorithm with a computational complexity comparable to that of the formulae obtained by directly taking the derivatives of the product-form solutions.     

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.     

A review on queueing network models with finite capacity queues for software architectures performance prediction

A review is carried out on how queueing network models with blocking have been applied so far into the performance evaluation and prediction of Software Architectures (SA). Queueing network models with finite capacity queues and blocking have recently been introduced and applied as more realistic models of systems with finite capacity resources and population constraints. Queueing network models have been often adopted as models for the evaluation of software performance. Starting from our own experience, we observe the need of a more accurate definition of the performance models of SA to capture some features of the communication systems. We consider queueing networks with finite capacity and blocking after service (BAS) to represent some synchronization constraints that cannot be easily modeled with queueing network models with infinite capacity queues. We investigate the use of queueing networks with blocking as performance models of SA with concurrent components and synchronous communication. Queueing theoretic analysis is used to solve the queueing network model and study the synchronous communication and performance of concurrent software components. Our experience is supported by other approaches that also propose the use of queueing networks with blocking. Directions for future research work in the field are included.     

Performance analysis of mesh interconnection networks withdeterministic routing

This paper develops detailed analytical performance models for k-ary n-cube networks with single-hit or infinite buffers, wormhole routing, and the nonadaptive deadlock-free routing scheme proposed by Dally and Seitz (1987). In contrast to previous performance studies of such networks, the system is modeled as a closed queueing network that: includes the effects of blocking and pipelining of messages in the network; allows for arbitrary source-destination probability distributions; and explicitly models the virtual channels used in the deadlock-free routing algorithm. The models are used to examine several performance issues for 2-D networks with shared-memory traffic. These results should prove useful for engineering high-performance systems based on low-dimensional k-ary n-cube networks     

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.     

Performance Analysis of a Client–Server System Using Queueing Networks: A Case Study

Queueing networks have been widely used to evaluation performance of mainframe computer systems. In contrast, few results have been reported for modern open systems, so it was not clear whether queueing networks are useful for modern systems or not. We think this situation has partly been due to lack of handy evaluation tools. This paper presents tow tools that we developed to evaluate open system performance. On is a measuring tool that is capable of accurately obtaining the service times of system resources requested by an application transaction. The other is an estimating tool which calculates various performance measures based on queueing network models. This paper also describes a case study in which the performance of a medium-sized UNIX client–server system (up to 24 clients) is estimated using the tools and these estimates are then compared with experimental results. The estimates closely agree with the measured results and are accurate enough for practical applications. Based on this, we conclude that queueing network models are also useful for modern systems.     

一种用于异步流水线环性能分析的排队网络近似分析算法

异步电路的性能评测一直是异步电路设计技术研究的难点所在。本文提出了异步流水线环的一种排队网络近似分析算法。首先将异步流水线环建模为闭合阻塞排队网络,再使用近似分析算法分析阻塞排队网络的性能,包括吞吐率、响应时间等,进而得到异步流水线的吞吐率、周期时间和延迟等性能参数。通过将本文算法的计算结果和数值计算得到
的精确结果进行比较,证明了该算法的正确性和有效性。     

Approximate analysis of finite fork/join queueing networks

We perform an approximate analysis on the finite-buffered acyclic fork/join queueing networks under the “blocking before service” mechanism. This study, besides being able to handle a network with complex topology and with finite buffers, is more general than the existing ones of its kind in that two performance measures, the system throughput and the average number of customers in each buffer, are taken into account. For a simple two-sibling network, we propose in detail a decomposition algorithm in which each decomposed subsystem carries over the local fork/join/tandem structure. The extension of this algorithm to a more general system is also discussed. Experimental results are provided showing that the proposed algorithm yields accurate results on the two performance measures.     

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.     

Extensions and generalizations of smoothed perturbation analysis ina generalized semi-Markov process framework

Under a very general framework, both in terms of finite-time performance measures and system structure, the authors derive smoothed perturbation analysis (SPA) estimators and prove their unbiasedness. The commuting condition, which has been key in previous work, is not required a priori, and thus the framework includes such systems as the GI/G/1/K queue and multiclass queueing networks, which do not satisfy the commuting condition. The generality achieved is traded off against the fact that the estimator is not always easily implementable on a single sample path. The use of the commuting condition in a local sense is proposed to help simplify the estimators derived: queueing and multiclass queueing networks are used as illustrative examples. For a simple multiclass closed queueing network, some simulation results are provided. When the commuting condition is satisfied globally, the framework allows the recovery of previous results on IPA and SPA estimators as corollaries of the main theorems     

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.     

A decomposition approach to modelling high service time variability

The predictive ability of queueing network models can be greatly enhanced if these models include the effects of system characteristics such as high service time variability and simultaneous resource possession, which violate the assumptions required for their efficient exact solution. In this paper we present a new approximate solution technique for queueing networks that include Coxian servers to represent resources at which customers have high service time variability. Our approach is unique in several respects: it is based directly on the theory of near-complete decomposability, it is non-iterative (performance measures for the queueing network of interest are expressed as linear combinations of the performance measures of a set of separable queueing networks), and it is conceptually and computationally simple.     

Modeling and analysis of message switched computer-communication networks with multilevel flow control

A message-switched network with three-level flow-control, namely End-to-End, Local and Global, is considered. A queueing model of the entire controlled network. including probabilistic routing, is developed. Fixed routing becomes a special case. Analytic expressions for the important system measures such as average network throughout, average delay and blocking probability are obtained. The results can be applied to message-switched networks having any combination of the above three flow-control schemes.     

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.     

Nonstationary analysis of circuit-switched communication networks

Circuit-switched communication networks have been analyzed extensively in the stationary case, i.e. where the arrival and/or service rates are independent of time. In this paper, we study a circuit-switched network where the rates of external arrivals at the network are time-dependent functions. The circuit-switched network is modelled as a nonstationary queueing network with population constraints, which is analyzed approximately in order to obtain the blocking probability functions. Using this method we model two circuit-switched networks, namely, a traffic-groomed tandem optical network and a single-orbit LEO satellite network.     

Integrated Performance Models for Distributed Processing in Computer Communication Networks

This paper deals with the analysis of large-scale closed queueing network (QN) models which are used for the performance analysis of computer communication networks (CCN's). The computer systems are interconnected by a wide-area network. Users accessing local/remote computers are affected by the contention (queueing delays) at the computer systems and the communication subnet. The computational cost of analyzing such models increases exponentially with the number of user classes (chains), even when the QN is tractable (product-form). In fact, the submodels of the integrated model are generally not product-form, e.g., due to blocking at computer systems (multiprogramming level constraints) and in the communication subnet (window flow control constraints). Two approximate solution methods are proposed in this paper to analyze the integrated QN model. Both methods use decomposition and iterative techniques to exploit the structure of the QN model such that computational cost is proportional to the number of chains. The accuracy of the solution methods is validated against each other and simulation. The model is used to study the effect that channel capacity assignments, window sizes for congestion control, and routing have on system performance.     

Optimal buffer allocation in finite closed networks with multiple servers

In this study, we present an optimal buffer allocation procedure for closed queueing networks with finite buffers. The performance measures are evaluated using the expanded mean value analysis, and the solution procedure is incorporated into a nonlinear optimization scheme to arrive at the sub-optimal buffer space vector. The effectiveness of the method is demonstrated through several numerical experiments. Discussions on convergence and computational complexity are also included.     

Queueing network models of packet switching networks part 2: Networks with population size constraints

An overview of the application of product-form queueing networks to the performance analysis of store-and-forward packet communication networks is presented. Queueing network models with closed chains and other forms of population size constraints are considered. The modeling and analysis of networks with window flow controlled virtual channels are described first. Models for the performance analysis of strategies for nodal buffer management and permit-oriented network congestion control are then presented.