Stability and performance analysis of rate-based feedback flow controlled ATM networks

Motivated by ABR class of service in ATM networks, we study a continuous time queueing system with a feedback control of the arrival rate of some of the sources. The feedback about the queue length or the total workload is provided at regular intervals (variations on it, especially the traffic management specification TM 4.0, are also considered). The propagation delays can be nonnegligible. For a general class of feedback algorithms, we obtain the stability of the system in the presence of one or more bottleneck nodes in the virtual circuit. Our system is general enough that it can be useful to study feedback control in other network protocols. We also obtain rates of convergence to the stationary distributions and finiteness of moments. For the single botterneck case, we provide algorithms to compute the stationary distributions and the moments of the sojourn times in different sets of states. We also show analytically (by showing continuity of stationary distributions and moments) that for small propagation delays, we can provide feedback algorithms which have higher mean throughput, lower probability of overflow and lower delay jitter than any open loop policy. Finally these results are supplemented by some computational results. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some limit theorems for regenerative queues

We consider a single server queue with the interarrival times and the service times forming a regenerative sequence. This traffic class includes the standard models: iid, periodic, Markov modulated (e.g., BMAP model of Lucantoni [18]) and their superpositions. This class also includes the recently proposed traffic models in high speed networks, exhibiting long range dependence. Under minimal conditions we obtain the rates of convergence to stationary distributions, finiteness of stationary moments, various functional limit theorems and the continuity of stationary distributions and moments. We use the continuity results to obtain approximations for stationary distributions and moments of an MMPP/GI/1 queue where the modulating chain has a countable state space. We extend all our results to feed-forward networks where the external arrivals to each queue can be regenerative. In the end we show that the output process of a leaky bucket is regenerative if the input process is and hence our results extend to a queue with arrivals controlled by a leaky bucket. This revised version was published online in June 2006 with corrections to the Cover Date.     

A network of priority queues in heavy traffic: One bottleneck station

In this paper we consider an open queueing network having multiple classes, priorities, and general service time distributions. In the case where there is a single bottleneck station we conjecture that normalized queue length and sojourn time processes converge, in the heavy traffic limit, to one-dimensional reflected Brownian motion, and present expressions for its drift and variance. The conjecture is motivated by known heavy traffic limit theorems for some special cases of the general model, and some conjectured “Heavy Traffic Principles” derived from them. Using the known stationary distribution of one-dimensional reflected Brownian motion, we present expressions for the heavy traffic limit of stationary queue length and sojourn time distributions and moments. For systems with Markov routing we are able to explicitly calculate the limits.     

Gated polling with stationary ergodic walking times, Markovian routing and random feedback

We investigate a gated polling system with semi-linear feedback and Markovian routing. We thereby relax the classical independence assumption on the walking times; the walking times constitute a sequence of stationary ergodic random variables. It is shown that the dynamics of this polling system can be described by semi-linear stochastic recursive equations in a Markovian environment. We obtain expressions for the first and second order moments of the workload and queue content at polling instants and for the mean queue content and workload at random instants.     

Moments of the generalized hyperbolic distribution

In this paper we demonstrate a recursive method for obtaining the moments of the generalized hyperbolic distribution. The method is readily programmable for numerical evaluation of moments. For low order moments we also give an alternative derivation of the moments of the generalized hyperbolic distribution. The expressions given for these moments may be used to obtain moments for special cases such as the hyperbolic and normal inverse Gaussian distributions. Moments for limiting cases such as the skew hyperbolic t and variance gamma distributions can be found using the same approach.     

Structural interpretation and derivation of necessary and sufficient conditions for delay moments in FIFO multiserver queues

Scheller-Wolf [12] established necessary and sufficient conditions for finite stationary delay moments in stable FIFO GI/GI/s queues that incorporate the interaction between service time distribution, traffic intensity (ρ) and the number of servers in the queue. These conditions can be used to show that when the service time has finite first but infinite αth moment, s slow servers can give lower delays than one fast server. In this paper, we derive an alternative derivation of these moment results: Both upper bounds, that serve as sufficient conditions, and lower bounds, that serve as necessary conditions are presented. In addition, we extend the class of service time distributions for which the necessary conditions are valid. Our new derivations provide a structural interpretation of the moment bounds, giving intuition into their origin: We show that FIFO GI/GI/s delay can be represented as the minimum of (s − k) i.i.d. GI/GI/1 delays, when ρ satisfies k < ρ < k+1. AMS Subject Classification 60K25     

Analysis of a discrete-time preemptive resume priority buffer

In this paper, we analyze a discrete-time preemptive resume priority queue. We consider two classes of customers which have to be served, where customers of one class have preemptive resume priority over customers of the other. Both classes contain customers with generally distributed service times. We show that the use of probability generating functions is beneficial for analyzing the system contents and customer delays of both classes. It is shown (theoretically as well as by some practical procedures) how moments and approximate tail probabilities of system contents and customer delays are calculated. The influence of the priority scheduling discipline and the service time distributions on the performance measures is shown by some numerical examples.     

Performance analysis of a slotted-ALOHA protocol on a capture channel with fading

We consider the slotted ALOHA protocol on a channel with a capture effect. There are M < users each with an infinite buffer. If in a slot, i packets are transmitted, then the probability of a successful reception of a packet is q _i. This model contains the CDMA protocols as special cases. We obtain sufficient rate conditions, which are close to necessary for stability of the system, when the arrival streams are stationary ergodic. Under the same rate conditions, for general regenerative arrival streams, we obtain the rates of convergence to stationarity, finiteness of stationary moments and various functional limit theorems. Our arrival streams contain all the traffic models suggested in the recent literature, including the ones which display long range dependence. We also obtain bounds on the stationary moments of waiting times which can be tight under realistic conditions. Finally, we obtain several results on the transient performance of the system, e.g., first time to overflow and the limits of the overflow process. We also extend the above results to the case of a capture channel exhibiting Markov modulated fading. Most of our results and proofs will be shown to hold also for the slotted ALOHA protocol without capture.     

Necessary and sufficient conditions in a spectrum control problem

For a linear stationary control system closed by a linear output feedback and for a bilinear stationary control system, we obtain new necessary and sufficient conditions for the solvability of the eigenvalue spectrum control problem in the case of a special form of the coefficients.     

Approximation of inverse moments of discrete distributions

For a wide class of discrete distributions, we derive a representation of the inverse (negative) moments through the Stirling numbers of the first kind and inverse factorial moments. We specialize the results for the Poisson, binomial, hypergeometric and negative binomial distributions.     

On a multivariate renewal-reward process involving time delays and discounting: applications to IBNR processes and infinite server queues

This paper considers a particular renewal-reward process with multivariate discounted rewards (inputs) where the arrival epochs are adjusted by adding some random delays. Then, this accumulated reward can be regarded as multivariate discounted Incurred But Not Reported claims in actuarial science and some important quantities studied in queueing theory such as the number of customers in \(G/G/\infty \) queues with correlated batch arrivals. We study the long-term behaviour of this process as well as its moments. Asymptotic expressions and bounds for quantities of interest, and also convergence for the distribution of this process after renormalization, are studied, when interarrival times and time delays are light tailed. Next, assuming exponentially distributed delays, we derive some explicit and numerically feasible expressions for the limiting joint moments. In such a case, for an infinite server queue with a renewal arrival process, we obtain limiting results on the expectation of the workload, and the covariance of queue size and workload. Finally, some queueing theoretic applications are provided.     

Light tail asymptotics in multidimensional reflecting processes for queueing networks

We are concerned with the stationary distributions of reflecting processes on multidimensional nonnegative orthants and other related processes, provided they exist. Such stationary distributions arise in performance evaluation for various queueing systems and their networks. However, it is very hard to obtain them analytically, so our interest is directed to analytically tractable characteristics. For this, we consider tail asymptotics of the stationary distributions.     

A general class of scale-shape mixtures of skew-normal distributions: properties and estimation

This paper introduces the scale-shape mixtures of skew-normal (SSMSN) distributions which provide alternative candidates for modeling asymmetric data in a wide variety of settings. We obtain the moments and study some characterizations of the SSMSN distributions. Instead of resorting to numerical optimization procedures, two variants of EM algorithms are developed for carrying out maximum likelihood estimation. Our algorithms are analytically simple because closed-form expressions of conditional expectations in the E-step as well as the updating estimators in the M-step can be explicitly obtained. The observed information matrix is derived for approximating the asymptotic covariance matrix of parameter estimates. A simulation study is conducted to examine the finite sample properties of ML estimators. The utility of the proposed methodology is illustrated by analyzing a real example.     

Delay performance in random-access networks

We explore the achievable delay performance in wireless random-access networks. While relatively simple and inherently distributed in nature, suitably designed queue-based random-access schemes provide the striking capability to match the optimal throughput performance of centralized scheduling mechanisms in a wide range of scenarios. The specific type of activation rules for which throughput optimality has been established, may however yield excessive queues and delays. Motivated by that issue, we examine whether the poor delay performance is inherent to the basic operation of these schemes, or caused by the specific kind of activation rules. We derive delay lower bounds for queue-based activation rules, which offer fundamental insight in the cause of the excessive delays. For fixed activation rates, we obtain lower bounds indicating that delays can grow dramatically with the load in certain topologies as well.     

Spectrum control in linear systems with incomplete feedback

For a linear stationary control system closed by a linear incomplete feedback, we obtain necessary and sufficient conditions for the solvability of the spectrum control problem in the case of coefficients of special form.     

A Markovian queueing model for ambulance offload delays

Ambulance offload delays are a growing concern for health care providers in many countries. Offload delays occur when ambulance paramedics arriving at a hospital Emergency Department (ED) cannot transfer patient care to staff in the ED immediately. This is typically caused by overcrowding in the ED. Using queueing theory, we model the interface between a regional Emergency Medical Services (EMS) provider and multiple EDs that serve both ambulance and walk-in patients. We introduce Markov chain models for the system and solve for the steady state probability distributions of queue lengths and waiting times using matrix-analytic methods. We develop several algorithms for computing performance measures for the system, particularly the offload delays for ambulance patients. Using these algorithms, we analyze several three-hospital systems and assess the impact of system resources on offload delays. In addition, simulation is used to validate model assumptions.     

Pseudo almost periodic solutions for a model of hematopoiesis with a feedback control

In this paper, a generalized model of hematopoiesis is considered with the introduction of a feedback control and continuously distributed delays. By using Lyapunov functional method and differential inequality techniques, we obtain some sufficient conditions for the existence and global exponential stability of positive pseudo almost periodic solutions of this model. We also provide numerical simulations to support the theoretical results.     

Jump diffusion processes and their applications in insurance and finance

For insurance risks, jump processes such as homogeneous/non-homogeneous compound Poisson processes and compound Cox processes have been used to model aggregate losses. If we consider the economic assumption of a positive interest to aggregate losses, Lévy processes have proven to be useful. Also in financial modelling, it has been observed that diffusion models are not robust enough to capture the appearance of jumps in underlying asset prices and interest rates. As a result, jump diffusion processes, which are, simply speaking, combinations of compound Poisson processes with Brownian motion, have gained popularity for modelling in insurance and finance. In this paper, considering a jump diffusion process, we obtain the explicit expression of the joint Laplace transform of the distribution of a jump diffusion process and its integrated process, assuming that jump size follows the mixture of two exponential distributions, which is a special case of phase-type distributions. Based on this Laplace transform, we derive the moments of the aggregate accumulated claim amounts of insurance risk. For a financial application, we concern non-defaultable zero-coupon bond pricing. We also provide several numerical examples for the moments of aggregate accumulated claims and default-free zero-coupon bond prices.     

Limit theorems,scaling of moments and intermittency for integrated finite variance supOU processes

Superpositions of Ornstein–Uhlenbeck type (supOU) processes provide a rich class of stationary stochastic processes for which the marginal distribution and the dependence structure may be modeled independently. We show that they can also display intermittency, a phenomenon affecting the rate of growth of moments. To do so, we investigate the limiting behavior of integrated supOU processes with finite variance. After suitable normalization four different limiting processes may arise depending on the decay of the correlation function and on the characteristic triplet of the marginal distribution. To show that supOU processes may exhibit intermittency, we establish the rate of growth of moments for each of the four limiting scenarios. The rate change indicates that there is intermittency, which is expressed here as a change-point in the asymptotic behavior of the absolute moments.     

Traffic Flows and Product Form Solutions in Stochastic Transfer Networks

This paper focuses on product form and related tractable stationary distributions in a general class of stochastic networks with finite numbers of nodes such that their network states are changed through signal transfers as well as internal transitions. Signals may be customers in traditional queueing applications, but we do not make any restriction on their effects at departing as well as arriving nodes. They may also instantaneously move around among different nodes. Furthermore, signal routing may depend on the whole network state. For analytical simplicity, we assume that the state space is countable. For such a network, we propose an abstract model, called a stochastic transfer network, and consider the stationary distribution of the network state. We introduce conditional traffic rates for arrivals and departures. Using them, we consider when the network has product form or some other tractable stationary distributions.