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.     

Block-structured supermarket models

Supermarket models are a class of parallel queueing networks with an adaptive control scheme that play a key role in the study of resource management of, such as, computer networks, manufacturing systems and transportation networks. When the arrival processes are non-Poisson and the service times are non-exponential, analysis of such a supermarket model is always limited, interesting, and challenging.This paper describes a supermarket model with non-Poisson inputs: Markovian Arrival Processes (MAPs) and with non-exponential service times: Phase-type (PH) distributions, and provides a generalized matrix-analytic method which is first combined with the operator semigroup and the mean-field limit. When discussing such a more general supermarket model, this paper makes some new results and advances as follows: (1) Providing a detailed probability analysis for setting up an infinite-dimensional system of differential vector equations satisfied by the expected fraction vector, where the invariance of environment factors is given as an important result. (2) Introducing the phase-type structure to the operator semigroup and to the mean-field limit, and a Lipschitz condition can be established by means of a unified matrix-differential algorithm. (3) The matrix-analytic method is used to compute the fixed point which leads to performance computation of this system. Finally, we use some numerical examples to illustrate how the performance measures of this supermarket model depend on the non-Poisson inputs and on the non-exponential service times. Thus the results of this paper give new highlight on understanding influence of non-Poisson inputs and of non-exponential service times on performance measures of more general supermarket models.     

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.     

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.     

Analytical and simulation modeling of a multi-server queue with Markovian arrivals and priority services

We consider a multi-server queueing system in which two types of customers arrive according to a Markovian arrival process. Type 1 customers have preemptive priority over Type 2 customers. A Type 2 arrival finding all servers busy will be lost. However, a Type 1 customer finding all servers busy with at least one Type 2 in service will get into service by pre-empting one of the Type 2 customers in service. Pre-empted Type 2 customers enter into a buffer of finite capacity. These (preempted) customers eventually leave the system after completing a service. In the case of exponential services, this model is studied analytically in steady-state by exploiting the special nature of the queueing model. A number of useful performance measures along with some illustrative examples are reported. In the case of non-exponential services, we simulate the model and discuss the effect of the variatio the services on some selected performance measures.     

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.     

Performance evaluation of fork and join synchronization primitives

Summary The paper presents a performance model of fork and join synchronization primitives. The primitives are used in parallel programs executed on distributed systems. Three variants of the execution of parallel programs with fork and join primitives are considered and queueing models are proposed to evaluate their performance on a finite number of processors. Synchronization delays incurred by the programs are represented by a state-dependent server with service rate depending on a particular synchronization scheme. Closed form results are presented for the two processor case and a numerical method is proposed for many processors. Fork-join queueing networks having more complex structure i.e., processors arranged in series and in parallel, are also analyzed in the same manner. The networks can model the execution of jobs with a general task precedence graph corresponding to a nested structure of the fork-join primitives. Some performance indices of the parallel execution of programs are studied. The results show that the speedup which can be obtained theoretically in a parallel system may be decreased significantly by synchronization constraints.This research we carried out while the author was visiting ISEM, Université de Paris-Sud, France     

Simulation of Generalised Semi-Markov Processes based on Graph Transformation Systems

Stochastic Graph Transformation combines graphical modelling of various software artefacts with stochastic analysis techniques. Existing approaches are restricted to processes with exponential time distribution. Such processes are sufficient for modelling a significant class of stochastic systems, however there are interesting systems which cannot be specified appropriately in such a framework. In several cases one needs to consider non-exponential time distributions. This paper proposes a stochastic model based on graph transformation with general probability distributions. This model is well suited to represent concurrency and performance aspects of architecture reconfiguration. It is also possible to apply Monte Carlo simulation techniques in order to analyse behaviour of complex stochastic systems. The new model is implemented and used to simulate simple networks.     

Fitting mixtures of exponentials to long-tail distributions to analyze network performance models

Traffic measurements from communication networks have shown that many quantities charecterizing network performance have long-tail probability distributions, i.e., with tails that decay more slowly than exponentially. File lengths, call holding times, scene lengths in MPEG video streams, and intervals between connection requests in Internet traffic all have been found to have long-tail distributions, being well described by distributions such as the Pareto and Weibull. It is known that long-tail distributions can have a dramatic effect upon performance, e.g., long-tail service-time distributions cause long-tail waiting-time distributions in queues, but it is often difficult to describe this effect in detail, because performance models with component long-tail distributions tend to be difficult to analyze. We address this problem by developing an algorithm for approximating a long-tail distribution by a hyperexponential distribution (a finite mixture of exponentials). We first prove that, in prinicple, it is possible to approximate distributions from a large class, including the Pareto and Weibull distributions, arbitrarily closely by hyperexponential distributions. Then we develop a specific fitting alogrithm. Our fitting algorithm is recursive over time scales, starting with the largest time scale. At each stage, an exponential component is fit in the largest remaining time scale and then the fitted exponential component is subtracted from the distribution. Even though a mixture of exponentials has an exponential tail, it can match a long-tail distribution in the regions of primary interest when there are enough exponential components. When a good fit is achieved, the approximating hyperexponential distribution inherits many of the difficulties of the original long-tail distribution; e.g., it is still difficult to obtain reliable estimates from simulation experiments. However, some difficulties are avoided; e.g., it is possible to solve some queueing models that could not be solved before. We give examples showing that the fitting procedure is effective, both for directly matching a long-tail distribution and for predicting the performance in a queueing model with a long-tail service-time distribution.     

Response time analysis of parallel computer and storage systems

Fork-join structures have gained increased importance in recent years as a means of modeling parallelism in computer and storage systems. The basic fork-join model is one in which a job arriving at a parallel system splits into K independent tasks that are assigned to K unique, homogeneous servers. In the paper, a simple response time approximation is derived for parallel systems with exponential service time distributions. The approximation holds for networks modeling several devices, both parallel and nonparallel. (In the case of closed networks containing a stand-alone parallel system, a mean response time bound is derived.) In addition, the response time approximation is extended to cover the more realistic case wherein a job splits into an arbitrary number of tasks upon arrival at a parallel system. Simulation results for closed networks with stand-alone parallel subsystems and exponential service time distributions indicate that the response time approximation is, on average, within 3 percent of the seeded response times. Similarly, simulation results with nonexponential distributions also indicate that the response time approximation is close to the seeded values. Potential applications of our results include the modeling of data placement in disk arrays and the execution of parallel programs in multiprocessor and distributed systems     

Monotonicity properties of cost functions in queueing networks

We establish monotonicity properties of cost functions in queueing networks with blocking, using sample path analysis. For any configuration of queueing stations with general interarrival times and exponentially distributed service times, we show that increasing the initial population and/or the arrival rates increases the expected cost (including blocking penalties for jobs that are rejected) incurred over a finite or an infinite horizon. Routing can be either probabilistic or state dependent. Furthermore, we show that this result also applies to networks with communication-type blocking where no jobs are ever lost. The criticality of the constraint imposed on the service times in demonstrated by a simple counterexample.This work is supported in part by the Office of Naval Research under Contract N00014-87-K-0304 and by the National Science Foundation under Grant ECS-8801912.     

QBD approximations of a call center queueing model with general patience distribution

This paper investigates a computationally practical way for analyzing a call center queueing model, i.e., a finite-capacity, multi-server queueing model, where each server goes on a single vacation. Poisson arrival process and exponential service and vacation times are assumed. We also assume that each customer may leave the queue due to impatience. Customers’ patience times are i.i.d. random variables with a general distribution. Level-dependent finite QBD (quasi-birth–death) processes are employed to approximate such a queueing model. Two approaches are considered. The first one uses the phase-type (PH) distribution to approximate the general patience distribution, whereas the second one is based on the idea of replacing the eventual reneging of customers with balking. We find that the first approach is almost impossible to compute numerically due to the exponential growth of the size of the block matrices in a level-dependent finite QBD. We examine the validity and applicability of the approximation based on the second approach and show that it gives us a practical way to obtain performance measures of call center systems in practical scale with sufficiently reasonable accuracy.     

Task Scheduling on the PASM Parallel Processing System

PASM is a proposed large-scale distributed/parallel processing system which can be partitioned into independent SIMD/MIMD machines of various sizes. One design problem for systems such as PASM is task scheduling. The use of multiple FIFO queues for nonpreemptive task scheduling is described. Four multiple-queue scheduling algorithms with different placement policies are presented and applied to the PASM parallel processing system. Simulation of a queueing network model is used to compare the performance of the algorithms. Their performance is also considered in the case where there are faulty control units and processors. The multiple-queue scheduling algorithms can be adapted for inclusion in other multiple-SIMD and partitionable SIMD/MIMD systems that use similar types of interconnection networks to those being considered for PASM.     

Cycle time distribution of cyclic networks with blocking

An algorithm is provided to compute the cycle time distribution for cyclic closed exponential queueing networks with N finite capacity nodes and blocking. The blocking phenomenon is due to the nodes with finite capacity queues which can be used to represent systems with limited resources. Moreover, a recursive algorithm is provided to evaluate the cycle time moments, and a closed form solution, both in terms of distribution and moments of the cycle time, is provided for the model under special constraints.     

Performance evaluation of an importance sampling technique in a Jackson network

Importance sampling is a technique that is commonly used to speed up Monte Carlo simulation of rare events. However, little is known regarding the design of efficient importance sampling algorithms in the context of queueing networks. The standard approach, which simulates the system using an a priori fixed change of measure suggested by large deviation analysis, has been shown to fail in even the simplest network settings. Estimating probabilities associated with rare events has been a topic of great importance in queueing theory, and in applied probability at large. In this article, we analyse the performance of an importance sampling estimator for a rare event probability in a Jackson network. This article carries out strict deadlines to a two-node Jackson network with feedback whose arrival and service rates are modulated by an exogenous finite state Markov process. We have estimated the probability of network blocking for various sets of parameters, and also the probability of missing the deadline of customers for different loads and deadlines. We have finally shown that the probability of total population overflow may be affected by various deadline values, service rates and arrival rates.     

On the proof of correctness of “Yet another asynchronousdistributed discrete event simulation algorithm (YADDES)”

The discipline of discrete event simulation may be utilized to model many physical systems such as digital hardware, queueing networks, telephone networks, simulated warfare, and banking transactions. Where the entities of a physical system execute independently and interact asynchronously, an asynchronous distributed event-driven simulation algorithm may enable the simulation of the system to execute on a parallel processor. This has the potential to significantly reduce the total simulation time. YADDES is the first algorithm that is characterized by: (1) acceptable performance, (2) freedom from deadlock, and (3) probably correct, for circuits where the interactions between the entities constitute a cyclic dependence. Given their complex, asynchronous nature, an important issue associated with all asynchronous distributed algorithms is their correctness, i.e., the generation of accurate output for given input stimulus, under all possible conditions. This paper presents a mathematical proof of correctness and reports the performance of YADDES on the Armstrong parallel processor at Brown University     

网络RAID存储系统边界性能研究

目前针对网络存储系统性能的研究大都集中在定性研究方面,缺乏有效的定量分析方法和模型．在有限容量闭合排队网络理论的基础上,提出了网络RAID存储系统性能的定量分析模型．并提出了一种新的计算有限容量闭合排队网络系统边界性能的分析方法-APBA法,和其他近似分析方法相比,APBA法的计算时间复杂度更低．测试结果表明,通过利用APBA方法,由网络RAID存储系统的性能定量分析模型获得的系统性能值,可以有效反映网络RAID存储系统在轻载区、重载区和过载区的性能边界,以及系统的最大负载量．     

Stability and convergence of moments for multiclass queueingnetworks via fluid limit models

The subject of this paper is open multiclass queueing networks, which are common models of communication networks, and complex manufacturing systems such as wafer fabrication facilities. We provide sufficient conditions for the existence of bounds on long-run average moments of the queue lengths at the various stations, and we bound the rate of convergence of the mean queue length to its steady-state value. Our work provides a solid foundation for performance analysis either by analytical methods or by simulation. These results are applied to several examples including re-entrant lines, generalized Jackson networks, and a general polling model as found in computer networks applications     

Lead time control in multi-class multi-stage assembly systems with finite capacity

In this paper, we model multi-class multi-stage assembly systems with finite capacity as queueing networks. It is assumed that different classes (types) of products are produced by the production system and products’ orders for different classes are received according to independent Poisson processes. Each service station of the queueing network specifies a manufacturing or assembly operation, in that processing times for different types of products are independent and exponentially distributed random variables with service rates, which are controllable, and the queueing discipline is First Come First Served (FCFS). Different types of products may be different in their routing sequences of manufacturing and assembly operations. For modeling multi-class multi-stage assembly systems, we first consider every class separately and convert the queueing network of each class into an appropriate stochastic network. Then, by using the concept of continuous-time Markov processes, a system of differential equations is created to obtain the distribution function of manufacturing lead time for any type of product, which is actually the time between receiving the order and the delivery of finished product. Furthermore, we develop a multi-objective model with three conflicting objectives to optimally control the service rates, and use goal attainment method to solve a discrete-time approximation of the original multi-objective continuous-time problem.