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

Motivated by the 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 regarding the queue length or the total workload is provided at regular intervals (variations on it, especially the EPRCA algorithm, 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. We also obtain rates of convergence to the stationary distributions and finiteness of moments. For the single bottleneck 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 the 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. Proceedings of the Seminar on Stability Problems for Stochastic Models, Hajdúszoboszló, Hungary, 1997, Part I.     

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.     

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.     

Optimal Feedback Control for Linear Systems with Input Delays Revisited

The design problem of optimal feedback control for linear systems with input delays is very important in many engineering applications. Usually, the linear systems with input delays are firstly converted into linear systems without delays, and then all the design procedures are based on the delay-free linear systems. In this way, the feedback controllers are not designed in terms of the original states. This paper presents some new closed-form formula in terms of the original states for the delayed optimal feedback control of linear systems with input delays. We firstly reveal the essential role of the input delay in the optimal control design of the linear system with a single input delay: the input delay postpones the action of the optimal control only. Based on this fact, we calculate the delayed optimal control and find that the optimal state can be represented by a simple closed-form formula, so that the delayed optimal feedback control can be obtained in a simple way. We show that the delayed feedback gain matrix can be “smaller” than that for the controlled system with zero input delay, which implies that the input delay can be considered as a positive factor. In addition, we give a general formula for the delayed optimal feedback control of time-variant linear systems with multiple input delays. To show the effectiveness and advantages of the main results, we present five illustrative examples with detailed numerical simulation and comparison.     

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.     

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.     

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.     

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.     

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.     

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.     

Lévy-Driven Carma Processes

Properties and examples of continuous-time ARMA (CARMA) processes driven by Lévy processes are examined. By allowing Lévy processes to replace Brownian motion in the definition of a Gaussian CARMA process, we obtain a much richer class of possibly heavy-tailed continuous-time stationary processes with many potential applications in finance, where such heavy tails are frequently observed in practice. If the Lévy process has finite second moments, the correlation structure of the CARMA process is the same as that of a corresponding Gaussian CARMA process. In this paper we make use of the properties of general Lévy processes to investigate CARMA processes driven by Lévy processes {W(t)} without the restriction to finite second moments. We assume only that W (1) has finite r-th absolute moment for some strictly positive r. The processes so obtained include CARMA processes with marginal symmetric stable distributions.     

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.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

Generalized inverses and their application to applied probability problems

The main aim of this paper is to examine the applicability of generalized inverses to a wide variety of problems in applied probability where a Markov chain is present either directly or indirectly through some form of imbedding. By characterizing all generalized inverses of I—P, where P is the transition matrix of a finite irreducible discrete time Markov chain, we are able to obtain general procedures for finding stationary distributions, moments of the first passage time distributions, and asymptotic forms for the moments of the occupation-time random variables. It is shown that all known explicit methods for examining these problems can be expressed in this generalized inverse framework. More generally, in the context of a Markov renewal process setting the aforementioned problems are also examined using generalized inverses of I—P. As a special case, Markov chains in continuous time are considered, and we show that the generalized inverse technique can be applied directly to the infinitesimal generator of the process, instead of to I—P, where P is the transition matrix of the discrete time jump Markov chain.     

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.     

Recursive computation of invariant distributions of Feller processes

This paper provides a general and abstract approach to compute invariant distributions for Feller processes. More precisely, we show that the recursive algorithm presented in Lamberton and Pagès (2002) and based on simulation algorithms of stochastic schemes with decreasing steps can be used to build invariant measures for general Feller processes. We also propose various applications: Approximation of Markov Brownian diffusion stationary regimes with a Milstein or an Euler scheme and approximation of a Markov switching Brownian diffusion stationary regimes using an Euler scheme.     

The lambda selections of parametric interval-valued fuzzy variables and their numerical characteristics

To model the uncertainty in the secondary possibility distributions, this paper develops a new method for handling interval-valued fuzzy variables with variable lower and upper possibility distributions. For a parametric interval-valued fuzzy variable, we define its lower selection variable, upper selection variable and lambda selection variable. The three selection variables are characterized by variable possibility distributions, and their numerical characteristics like expected values and n-th moments are important indices in practical optimization and decision-making problems. Under this consideration, we establish some useful analytical expressions of the expected values and n-th moments for the lambda selections of parametric interval-valued trapezoidal, normal and Erlang fuzzy variables. Furthermore, we focus on the arithmetic about the sums of common parametric interval-valued fuzzy variables. Finally, we apply the proposed optimization indices to a quantitative finance problem, where the second moment is used to measure the risk of a portfolio.     

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     

Distributional Form of Little's Law for FIFO Queues with Multiple Markovian Arrival Streams and Its Application to Queues with Vacations

This paper considers stationary queues with multiple arrival streams governed by an irreducible Markov chain. In a very general setting, we first show an invariance relationship between the time-average joint queue length distribution and the customer-average joint queue length distribution at departures. Based on this invariance relationship, we provide a distributional form of Little's law for FIFO queues with simple arrivals (i.e., the superposed arrival process has the orderliness property). Note that this law relates the time-average joint queue length distribution with the stationary sojourn time distributions of customers from respective arrival streams. As an application of the law, we consider two variants of FIFO queues with vacations, where the service time distribution of customers from each arrival stream is assumed to be general and service time distributions of customers may be different for different arrival streams. For each queue, the stationary waiting time distribution of customers from each arrival stream is first examined, and then applying the Little's law, we obtain an equation which the probability generating function of the joint queue length distribution satisfies. Further, based on this equation, we provide a way to construct a numerically feasible recursion to compute the joint queue length distribution.