Some Equivalence Results for Load-Independent Exponential Queueing Networks

In this paper we derive a number of results concerning the behavior of closed load-independent exponential queueing networks. It is shown that if the service rate of any station is increased (decreased), then the throughput of the network itself also increases (decreases). This is not true for product form networks in general. In addition, if the service rate at server i is increased then both the mean queue length and mean waiting time at server i decrease while both these quantities increase at all stations j ? i. The opposite effect is observed if the senrvice rate at station i is decreased. The main result of the paper is a proof of the conjective that corresponding to any general closed queueing network consisting of M stations and in which N customers circulate according to the elements of an irreducible stochastic routing matrix Q, there exists a closed load-independent exponential queueing network with the same M, N, and Q such that the mean number of customers at each station in the exponential network is equal to that in the general network. If the network throughput is specified, it is shown that this exponential network iS unique.     

非乘积解随机Petri网的乘积形式近似求解

讨论了非乘积解随机Petri网的近似求解问题。将Marie方法引入到随机Petri网的近似分析中,利用随机Petri网中已有的结论将该方法中的分解原则推广到更一般的情形,使其应用范围更广,利用运算分析法对这些分解原则作了形式化描述,在此基础上,给出了有关结论的数学证明。最后,对这种近似方法作了误差分析,找出了产生误差的原因。实验数据表明本文所给的近似方法应用广且有效。     

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.     

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.     

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.     

MRE hierarchical decomposition of general queueing network models

Summary The principle of Minimum Relative Entropy (MRE), given fully decomposable subset and aggregate mean queue length, utilisation and flow-balance constraints, is used in conjunction with asymptotic connections to infinite capacity queues, to derive new analytic approximations for the conditional and marginal state probabilities of single class general closed queueing network models (QNMs) in the context of a multilevel variable aggregation scheme. The concept of subparallelism is applied to preserve the flow conservation and a universal MRE hierarchical decomposition algorithm is proposed for the approximate analysis of arbitrary closed queueing networks with single server queues and general service-times. Heuristic criteria towards an optimal coupling of network's units at each level of aggregation are suggested. As an illustration, the MRE algorithm is implemented iteratively by using the Generalised Exponential (GE) distributional model to approximate the service and asymptotic flow processes in the network. This algorithm captures the exact solution of separable queueing networks, while for general queueing networks it compares favourably against exact solutions and known approximations.This work is sponsored by the Science and Engineering Research Council (SERC), UK, under grant GR/F29271     

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

Machine allocation algorithms for job shop manufacturing

In this paper we present algorithms for the solution of two server (machine) allocation problems that occur in manufacturing networks. The manufacturing network is modelled as an open network of queues with general interarrival time and service time distributions. The queueing network is analyzed by using the parametric decomposition method: a two-moment approximation scheme. The server allocation problems are solved by means of a marginal analysis scheme. Numerical results on two manufacturing networks are presented.     

Distributed-information neural control: the case of dynamic routingin traffic networks

Large-scale traffic networks can be modeled as graphs in which a set of nodes are connected through a set of links that cannot be loaded above their traffic capacities. Traffic flows may vary over time. Then the nodes may be requested to modify the traffic flows to be sent to their neighboring nodes. In this case, a dynamic routing problem arises. The decision makers are realistically assumed 1) to generate their routing decisions on the basis of local information and possibly of some data received from other nodes, typically, the neighboring ones and 2) to cooperate on the accomplishment of a common goal, that is, the minimization of the total traffic cost. Therefore, they can be regarded as the cooperating members of informationally distributed organizations, which, in control engineering and economics, are called team organizations. Team optimal control problems cannot be solved analytically unless special assumptions on the team model are verified. In general, this is not the case with traffic networks. An approximate resolutive method is then proposed, in which each decision maker is assigned a fixed-structure routing function where some parameters have to be optimized. Among the various possible fixed-structure functions, feedforward neural networks have been chosen for their powerful approximation capabilities. The routing functions can also be computed (or adapted) locally at each node. Concerning traffic networks, we focus attention on store-and-forward packet switching networks, which exhibit the essential peculiarities and difficulties of other traffic networks. Simulations performed on complex communication networks point out the effectiveness of the proposed method.     

Modeling parallel and distributed systems with finite workloads

In studying or designing parallel and distributed systems one should have available a robust analytical model that includes the major parameters that determine the system performance. Jackson networks have been very successful in modeling computer systems. However, the ability of Jackson networks to predict performance with system changes remains an open question, since they do not apply to systems where there are population size constraints. Also, the product-form solution of Jackson networks assumes steady-state and exponential service centers or certain specialized queueing discipline. In this paper, we present a transient model for Jackson networks that is applicable to any population size and any finite workload (no new arrivals). Using several non-exponential distributions we show to what extent the exponential distribution can be used to approximate other distributions and transient systems with finite workloads. When the number of tasks to be executed is large enough, the model approaches the product-form solution (steady-state solution). We also, study the case where the non-exponential servers have queueing (Jackson networks cannot be applied). Finally, we show how to use the model to analyze the performance of parallel and distributed systems.     

Dual and selfdual networks of queues with rejection blocking

Open and closed queueing networks with rejection blocking are investigated. Using the concept of holes, a duality is derived for pairs of networks. This duality equates equilibrium state probabilities and throughputs of the given network and its dual. As an application an exact product form solution for certain closed queueing networks with rejection blocking are derived. In this case, duality provides a simple method to compute performance measures. In some cases, a network and its dual have the same structure. Duality provides relations among performance measures of different stations in this case.     

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.     

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.     

Probability distribution in varying-structure queueing networks

The paper is devoted to the computation of stationary distributions of queueing systems in random media. Results obtained for considered models follow from a theorem proved in the paper. As an application of the theorem, we consider Jackson networks whose structure (the set of working nodes, service and input flow intensities, routing matrix, state set) and type (open/closed network) varies as the state of another network or of the environment changes. Product-form formulas for the computation of stationary distributions of the considered networks are obtained, and algorithms for the solution of auxiliary problems are developed.     

The multiple phase service network with generalized processor sharing

Summary An analysis is given of multiple phase service facilities of which queueing networks are special models, for the case of a service discipline to be denoted as generalized processor sharing. Under this discipline requests are served simultaneously with a rate depending on the phase and the number of requests present here. The model is of a very general type, its analysis is given for arbitrary routing matrices and absolutely continuous required service time distributions. The mathematical technique used is that of the supplementary variable. Generalisations of known results for closed and open networks are obtained and new results about the average sojourn time of a request in the system are derived, in particular for requests with given route and given processing times at the nodes of the route. Some basic results about reversed processes and departure processes are discussed. For a special but important model the workload is discussed.     

一种计算性能指标对路径概率灵敏性的新方法

本文提出了应用全状态摄动分析直接计算对路径概率的灵敏性,推导了路径变化时摄动的产生规则,给出了两个数值例子,实验结果验证了这一方法的有效性和准确性。     

A diffusion approximate solution to the g/g/k queueing system

In the opening sections of this paper we present a diffusion approximate solution to a G/G/k queueing station under steady state condtions. The approximation technique is computationally simple and practical in that it requires knowledge of the means and variances of the interarrival and service time distributions, but not their distributional forms. Several numeric examples attesting to the good quality of the approximation are also included. We then discuss extending the basic approximation technique to account first for a feed back option and then to networks of multiserver queueing stations.     

Experiments with improved approximate mean value analysis algorithms

Approximate mean value analysis (MVA) is a popular technique for analyzing queueing networks because of the efficiency and accuracy that it affords. In this paper, we present a new software package, called the improved approximate mean value analysis library (IAMVAL), which can be easily integrated into existing commercial and research queueing network analysis packages. The IAMVAL packages include two new approximate MVA algorithms, the queue line (QL) algorithm and the fraction line (FL) algorithm, for analyzing multiple class separable queueing networks. The QL algorithm is always more accurate than, and yet has approximately the same computational efficiency as, the Bard–Schweitzer proportional estimation (PE) algorithm, which is currently the most widely used approximate MVA algorithm. The FL algorithm has the same computational cost and, in noncongested separable queueing networks where queue lengths are quite small, yields more accurate solutions than both the QL and PE algorithms.