A class of renewal Interrupted Poisson Processes and applications to queueing systems

Switched Poisson Processes and Interrupted Poisson Processes are often employed to characterize traffic streams in distributed computer and communications systems, especially in investigations of overflow processes in telecommunication networks. With these processes, input streams having inter-segment correlations and high variance as well as state-dependent traffic can properly be modelled. In this paper we first derive an approximation method to describe the Generalized Switched Poisson processes in conjunction with a renewal assumption. As a special case of this class of processes, the class of Interrupted Poisson processes is also included in the investigation. As a result, a generalization of the well-known class of Interrupted Poisson processes is obtained. It is shown that the renewal property is also given for this general class of Interrupted Poisson processes having generally distributed off-phase. To illustrate the accuracy of the presented renewal approximation of Generalized Switched Poisson processes and to show the major properties of the General Interrupted Poisson processes, applications to some basic queueing systems are discussed by means of numerical results.This work was done while the author was with Institute of Communications Switching and Data Technics, University of Stuttgart, Seidenstrasse 36, D-7000 Stuttgart 1, FRG.     

Transient flows in queueing systems via closure approximations

We present a method for obtaining approximations to the distribution of flow times of customers in arbitrary queueing systems. We first propose approximations for uni-variate and multi-variate distributions of non-negative random variables. Then using a closure approximation, we show that the distribution of flow time can be calculated recursively. Computational results for the single server, multi-server and tandem queues are encouraging, with less than 5%average error in the mean flow time in most cases. The average error in the variance of flow times is found to be less than 10% for the more regular distributions.     

Reduced systems in Markov chains and their applications in queueing theory

A reduced system is a smaller system derived in the process of analyzing a larger system. While solving for steady-state probabilities of a Markov chain, generally the solution can be found by first solving a reduced system of equations which is obtained by appropriately partitioning the transition probability matrix. In this paper, we catagorize reduced systems as standard and nonstandard and explore the existence of reduced systems and their properties relative to the original system. We also discuss first passage probabilities and means for the standard reduced system relative to the original system. These properties are illustrated while determining the steady-state probabilities and first passage time characteristics of a queueing system.     

Travel times in queueing networks and network sojourns

We first describe expected values of sojourn times for semi-stationary (or synchronous) networks. This includes sojourn times for units and sojourn times for the entire network. A typical sojourn time of a unit is the time it spends in a sector (set of nodes) while it travels through the network, and a typical network sojourn time is the busy period of a sector. Our results apply to a wide class of networks including Jackson networks with general service times, general Markov or regenerative networks, and networks with batch processing and concurrent movement of units. The results also shed more light on when Little's law for general systems, holds for expectations as well as for limiting averages. Next, we describe the expectation of a unit's travel time on a general route in a basic Markov network process (such as a Jackson process). Examples of travel times are the time it takes for a unit to travel from one sector to another, and the time between two successive entrances to a node by a unit. Finally, we characterize the distributions of the sojourn times at nodes on certain overtake-free routes and the travel times on such routes for Markov network processes.This research was supported in part by the Air Force Office of Scientific Research under contract 89-0407 and NSF grant DDM-9007532.     

Characteristics of queueing systems observed at events and the connection between stochastic intensity and palm probability

This article explores the link between the concepts of stochastic intensity and Palm probability and gives a new proof and useful extensions to the so-called PASTA property of queueing theory.     

Almost sure comparison of birth and death processes with application to M/M/s queueing systems

Given conditions, which concern the infinitesimal parameters of two birth and death processes, the processes are constructed on the same probability space such that one process is almost surely larger than the other. Application is made to M/M/s queueing systems. Stochastic comparisons of queue length and virtual waiting time in two M/M/s systems are obtained.     

Optimal server scheduling in nonpreemptive finite-population queueing systems

We consider a finite-population queueing system with heterogeneous classes of customers and a single server. For the case of nonpreemptive service, we fully characterize the structure of the server's optimal service policy that minimizes the total average customer waiting costs. We show that the optimal service policy may never serve some classes of customers. For those classes that are served, we show that the optimal service policy is a simple static priority policy. We also derive sufficient conditions that determine the optimal priority sequence.     

A class of hierarchical queueing networks and their analysis

Queueing networks are an adequate model type for the analysis of complex system behavior. Most of the more realistic models are rather complex and do not fall into the easy solvable class of product form networks. Those models have to be analyzed by numerical solution of the underlying Markov chain and/or approximation techniques including simulation. In this paper a class of hierarchically structured queueing networks is considered and it is shown that the hierarchical model structure is directly reflected in the state space and the generator matrix of the underlying Markov chain. Iterative solution techniques for stationary and transient analysis can be modified to make use of the model structure and allow an efficient numerical analysis of large, up to now not solvable queueing networks.     

Insensitivity of multiclass systems with general dynamic preemptive resume queueing disciplines

We are concerned with the insensitivity of the stationary distributions of the system states inM/G/s/m queues with multiclass customers and with LIFO preemptive resume service disciplines. We introduce general entrance and exit rules into and from waiting positions, respectively, for the behaviour of waiting customers whose service is interrupted. These rules may, roughly speaking, depend on the number of customers in the system. It is shown that the stationary distribution of the system state is insensitive not only with respect to the service time distributions but also with respect to the general entrance and exit rules. As well as the insensitivity of the service scheme, our results are obtained for a special form of state and customer type dependent arrival and service rates. Some further results are concluded related to insensitivity like the formula for the conditional mean sojourn time and the property of transformation of a Poisson input into a Poisson output by the systems.     

Statistical analysis of queueing systems

This paper provides an overview of the literature on statistical analysis of queueing systems. Topics discussed include: model identification, estimation, hypothesis testing and other related aspects. Not all of these statistical problems are covered in books on queueing theory or stochastic processes. The bibliography is not exhaustive, but comprehensive enough to provide sources from the literature.     

Rate conservation laws: A survey

We survey the rate conservation law, RCL for short, arising in queues and related stochastic models. RCL was recognized as one of the fundamental principles to get relationships between time and embedded averages such as the extended Little's formulaH=G, but we show that it has other applications. For example, RCL is one of the important techniques for deriving equilibrium equations for stochastic processes. It is shown that the various techniques, including Mecke's formula for a stationary random measure, can be formulated as RCL. For this purpose, we start with a new definition of the rate with respect to a random measure, and generalize RCL by using it. We further introduce the notion of quasi-expectation, which is a certain extension of the ordinary expectation, and derive RCL applicable to the sample average results. It means that the sample average formulas such asH=G can be obtained as the stationary RCL in the quasi-expectation framework. We also survey several extensions of RCL and discuss examples. Throughout the paper, we would like to emphasize how results can be easily obtained by using a simple principle, RCL.     

Discrete time controllable processes with bounded drift and their application in queueing systems

Recursive algorithms are considered for construction of optimal policies for some special classes of controllable stochastic processes, which are called discrete-time controllable semi-regenerative processes. By means of these processes many controllable queueing systems can be modelled. Numerical examples are given for the investigation of optimal policies in such systems.     

Stochastic petri net analysis of finite-population vacation queueing systems

We consider queueing systems in which the server occasionally takes a vacation of random duration. The vacation can be used to do additional work; it can also be a rest period. Several models of this problem have been analyzed in the past assuming that the population of the system is infinite. Similarly, it is generally assumed that the capacity of the system is infinite. In this paper we show how the finite-population system can be modeled by the stochastic Petri net. We also extend the model to the finite-capacity system. This research was sponsored by the SDIO Innovative Science and Technology Office and was managed by the Office of Naval Research under grant N3014-88-K-0623.     

Financial systems: a few theoretical and algebraic considerations for their modeling

In this paper I suggest that observable entities, usually named ‘financial systems’, may be related to the general conceptual framework of systems theory. Starting from the requisite properties of a (general) system, I derive a strong and operational concept for specific financial systems (Section 1). Then a general modeling procedure is proposed, mainly based upon graph theory (with an additional and complementary use of linear systems analysis), through which it is possible to establish the general static and almost dynamic properties of these specific systems and their implications for financial analysis itself (Section 2). A numerical example (Section 3) illustrates most of the concepts and ideas introduced throughout the paper.     

Decomposition results for general polling systems and their applications

In this paper we derive decomposition results for the number of customers in polling systems under arbitrary (dynamic) polling order and service policies. Furthermore, we obtain sharper decomposition results for both the number of customers in the system and the waiting times under static polling policies. Our analysis, which is based on distributional laws, relaxes the Poisson assumption that characterizes the polling systems literature. In particular, we obtain exact decomposition results for systems with either Mixed Generalized Erlang (MGE) arrival processes, or asymptotically exact decomposition results for systems with general renewal arrival processes under heavy traffic conditions. The derived decomposition results can be used to obtain the performance analysis of specific systems. As an example, we evaluate the performance of gated Markovian polling systems operating under heavy traffic conditions. We also provide numerical evidence that our heavy traffic analysis is very accurate even for moderate traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

Robustness of perturbation analysis estimators for queueing systems with unknown distributions

Sample-path-based stochastic gradient estimators for performance measures of queueing systems rely on the assumption that a probability distribution of the random vector of interest (e.g., a service or interarrival time sequence) is given. In this paper, we address the issue of dealing with unknown probability distributions and investigate the robustness of such estimators with respect to possibly erroneous distribution choices. We show that infinitesimal perturbation analysis (IPA) can be robust in this sense and, in some cases, provides distribution-independent estimates. Comparisons with other gradient estimators are provided, including experimental results. We also show that finite perturbation analysis (FPA), though only providing gradient approximations, possesses some attractive robustness properties with respect to unknown distribution parameters. An application of FPA estimation is included for a queueing system performance optimization problem involving customers with real-time constraints.This work was supported in part by the National Science Foundation Grant ECS-88-01912 and by the Office of Naval Research Contract N00014-87-K-0304.The authors wish to thank Dr. Jack Holtzman for several useful comments and suggestions.     

On queueing with customer impatience until the beginning of service

We study queueing systems where customers have strict deadlines until the beginning of their service. An analytic method is given for the analysis of a class of such queues, namely, models. These are queues with state-dependent Poisson arrival process, exponential service times, multiple servers, FCFS service discipline, and general customer impatience. The state of the system is viewed to be the number of customers in the system. The principal measure of performance is the probability measure induced by the offered waiting time. Other measures of interest are the probability of missing deadline and the probability of blocking. Closed-form solutions are derived for the steady-state probabilities of the state process and some important modeling variables and parameters. The efficacy of our method is illustrated through a numerical example. This revised version was published online in June 2006 with corrections to the Cover Date.     

A heuristic technique for the transient behavior of Markovian queueing systems

Through an examination of numerical solutions to Markovian queueing systems, it has been shown that the expected queue length eventually approaches its equilibrium value in an approximately exponential manner. Based on this observation a heuristic is proposed for approximating the transient expected queue length for Markovian systems by scaling the numerical solution of an M/M/1 system.     

Asymptotic estimates of multi-dimensional stable densities and their applications

The relation between the upper and lower asymptotic estimates of the density and the fractal dimensions on the sphere of the spectral measure for a multivariate stable distribution is discussed. In particular, the problem and the conjecture on the asymptotic estimates of multivariate stable densities in the work of Pruitt and Taylor in 1969 are solved. The proper asymptotic orders of the stable densities in the case where the spectral measure is absolutely continuous on the sphere, or discrete with the support being a finite set, or a mixture of such cases are obtained. Those results are applied to the moment of the last exit time from a ball and the Spitzer type limit theorem involving capacity for a multi-dimensional transient stable process.