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.     

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.     

Quasi-reversible multiclass queues with order independent departure rates

This paper introduces a new class of queues which are quasi-reversible and therefore preserve product form distribution when connected in multinode networks. The essential feature leading to the quasi-reversibility of these queues is the fact that the total departure rate in any queue state is independent of the order of the customers in the queue. We call such queues order independent (OI) queues. The OI class includes a significant part of Kelly's class of symmetric queues, although it does not cover the whole class. A distinguishing feature of the OI class is that, among others, it includes the MSCCC and MSHCC queues but not the LCFS queue. This demonstrates a certain generality of the class of OI queues and shows that the quasi-reversibility of the OI queues derives from causes other than symmetry principles. Finally, we examine OI queues where arrivals to the queue are lost when the number of customers in the queue equals an upper bound. We obtain the stationary distribution for the OI loss queue by normalizing the stationary probabilities of the corresponding OI queue without losses. A teletraffic application for the OI loss queue is presented.     

Queues with Service Rate Controlled by a Delayed Feedback

We consider a single queue with a Markov modulated Poisson arrival process. Its service rate is controlled by a scheduler. The scheduler receives the workload information from the queue after a delay. This queue models the buffer in an earth station in a satellite network where the scheduler resides in the satellite. We obtain the conditions for stability, rates of convergence to the stationary distribution and the finiteness of the stationary moments. Next we extend these results to the system where the scheduler schedules the service rate among several competing queues based on delayed information about the workloads in the different queues.     

A stochastic network with mobile users in heavy traffic

We consider a stochastic network with mobile users in a heavy traffic regime. We derive the scaling limit of the multidimensional queue length process and prove a form of spatial state space collapse. The proof exploits a recent result by Lambert and Simatos (preprint, 2012), which provides a general principle to establish scaling limits of regenerative processes based on the convergence of their excursions. We also prove weak convergence of the sequences of stationary joint queue length distributions and stationary sojourn times.     

The MM CPP/GE/c G-Queue: Sojourn Time Distribution

We obtain the sojourn time probability distribution function at equilibrium for a Markov modulated, multi-server, single queue with generalised exponential (GE) service time distribution and compound Poisson arrivals of both positive and negative customers. Such arrival processes can model both burstiness and correlated traffic and are well suited to models of ATM and other telecommunication networks. Negative customers remove (ordinary) customers in the queue and are similarly correlated and bursty. We consider both the cases where negative customers remove positive customers from the front and the end of the queue and, in the latter case, where a customer currently being served can and cannot be killed by a negative customer. These cases can model an unreliable server or load balancing respectively. The results are obtained as Laplace transforms and can be inverted numerically. The MM CPP/GE/c G-Queue therefore holds the promise of being a viable building block for the analysis of queues and queueing networks with bursty, correlated traffic, incorporating load balancing and node-failures, since the equilibrium behaviour of both queue lengths and response times can be determined in a tractable way.     

Markov network processes with product form stationary distributions

This study concerns the equilibrium behavior of a general class of Markov network processes that includes a variety of queueing networks and networks with interacting components or populations. The focus is on determining when these processes have product form stationary distributions. The approach is to relate the marginal distributions of the process to the stationary distributions of “node transition functions” that represent the nodes in isolation operating under certain fictitious environments. The main result gives necessary and sufficient conditions on the node transition functions for the network process to have a product form stationary distribution. This result yields a procedure for checking for a product form distribution and obtaining such a distribution when it exits. An important subclass of networks are those in which the node transition rates have Poisson arrival components. In this setting, we show that the network process has a product form distribution and is “biased locally balanced” if and only if the network is “quasi-reversible” and certain traffic equations are satisfied. Another subclass of networks are those with reversible routing. We weaken the known sufficient condition for such networks to be product form. We also discuss modeling issues related to queueing networks including time reversals and reversals of the roles of arrivals and departures. The study ends by describing how the results extend to networks with multi-class transitions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of the M/G/1 processor-sharing queue with bulk arrivals

We analyze the single server processor-sharing queue for the case of bulk arrivals. We obtain an expression for the expected response time of a job as a function of its size, when the service times of jobs have a generalized hyperexponential distribution and more generally for distributions with rational Laplace transforms. Our analysis significantly extends the class of distributions for which processor-sharing queues with bulk arrivals were previously analyzed.     

Large Deviation Bounds for Single Class Queueing Networks and Their Calculation

We investigate large deviations for the behavior of single class queueing networks. The starting point is a sample large deviation principle on the path-space of network primitives describing the cumulative external arrivals, service time requirements and routing decisions. The behavior of the network, capturing the cumulative total arrivals, idle times and queue lengths, is characterized by a path-space fixed point equation containing the network primitives. The mapping from the network primitives to the set of fixed points is partially upper semicontinuous. This set-valued continuity allows us to derive large deviation bounds for the network behavior in the form of variational problems. The analysis is carried out on the doubly-infinite time axis R and can directly capture stationary and non-Markovian situations. By relaxing the fixed point equation the upper bounds and minimizing paths can be approximated with piecewise linear paths. For a class of typical rate functions we specify sequences of finite dimensional minimization problems which permit the calculation of large deviation rates and minimizing paths for the tail probabilities of queue lengths. We illustrate the approach with an example.     

Single server retrial queues with two way communication

The main aim of this paper is to study the steady state behavior of an M/G/1-type retrial queue in which there are two flows of arrivals namely ingoing calls made by regular customers and outgoing calls made by the server when it is idle. We carry out an extensive stationary analysis of the system, including stability condition, embedded Markov chain, steady state joint distribution of the server state and the number of customers in the orbit (i.e., the retrial group) and calculation of the first moments. We also obtain light-tailed asymptotic results for the number of customers in the orbit. We further formulate a more complicate but realistic model where the arrivals and the service time distributions are modeled in terms of the Markovian arrival process (MAP) and the phase (PH) type distribution.     

Improved bounds for queues with delayed arrivals

Improved bounds are developed for a queue where arrivals are delayed by a fixed time. For moderate to heavy traffic, a simple improved upper bound is obtained which only uses the first two moments of the service time distribution. We show that our approach can be extended to obtain bounds for other types of delayed arrival queues. For very light traffic, asymptotically tight bounds can be obtained using more information about the service time distribution. While an improved upper bound can be obtained for light to moderate traffic it is not particularly easy to apply. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bounds for the tail distribution in a queue with a superposition of general periodic Markov sources: theory and application

An efficient yet accurate estimation of the tail distribution of the queue length has been considered as one of the most important issues in call admission and congestion controls in ATM networks. The arrival process in ATM networks is essentially a superposition of sources which are typically bursty and periodic either due to their origin or their periodic slot occupation after traffic shaping. In this paper, we consider a discrete-time queue where the arrival process is a superposition of general periodic Markov sources. The general periodic Markov source is rather general since it is assumed only to be irreducible, stationary and periodic. Note also that the source model can represent multiple time-scale correlations in arrivals. For this queue, we obtain upper and lower bounds for the asymptotic tail distribution of the queue length by bounding the asymptotic decay constant. The formulas can be applied to a queue having a huge number of states describing the arrival process. To show this, we consider an MPEG-like source which is a special case of general periodic Markov sources. The MPEG-like source has three time-scale correlations: peak rate, frame length and a group of pictures. We then apply our bound formulas to a queue with a superposition of MPEG-like sources, and provide some numerical examples to show the numerical feasibility of our bounds. Note that the number of states in a Markov chain describing the superposed arrival process is more than 1.4 × 10⁸⁸. Even for such a queue, the numerical examples show that the order of the magnitude of the tail distribution can be readily obtained.     

The infinite-buffer single server queue with a variant of multiple vacation policy and batch Markovian arrival process

We consider an infinite-buffer single server queue where arrivals occur according to a batch Markovian arrival process (BMAP). The server serves until system emptied and after that server takes a vacation. The server will take a maximum number H of vacations until either he finds at least one customer in the queue or the server has exhaustively taken all the vacations. We obtain queue length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue lengths and mean waiting times, etc. have been obtained. Several other vacation queueing models like, single and multiple vacation model, queues with exceptional first vacation time, etc. can be considered as special cases of our model.     

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.     

Queues with Dropping Functions and Autocorrelated Arrivals

We present an analysis of the queueing system in which arriving jobs are dropped with probability depending on the queue size. The arrivals are assumed to be autocorrelated and they are modeled by the Markov-modulated Poisson process. Both transient and stationary distributions of the queue size, as well as the system loss ratio and throughput are obtained. The analytical results are accompanied with numerical examples based on the autocorrelated traffic recorded in an IP computer network.     

A Queue with Semi-Markovian Batch Plus Poisson Arrivals with Application to the MPEG Frame Sequence

We consider a queueing system with a single server having a mixture of a semi-Markov process (SMP) and a Poisson process as the arrival process, where each SMP arrival contains a batch of customers. The service times are exponentially distributed. We derive the distributions of the queue length of both SMP and Poisson customers when the sojourn time distributions of the SMP have rational Laplace–Stieltjes transforms. We prove that the number of unknown constants contained in the generating function for the queue length distribution equals the number of zeros of the denominator of this generating function in the case where the sojourn times of the SMP follow exponential distributions. The linear independence of the equations generated by those zeros is discussed for the same case with additional assumption. The necessary and sufficient condition for the stability of the system is also analyzed. The distributions of the waiting times of both SMP and Poisson customers are derived. The results are applied to the case in which the SMP arrivals correspond to the exact sequence of Motion Picture Experts Group (MPEG) frames. Poisson arrivals are regarded as interfering traffic. In the numerical examples, the mean and variance of the waiting time of the ATM cells generated from the MPEG frames of real video data are evaluated.     

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.     

Analysis of a buffer queueing problem in discrete time

We consider a queueing system with bulk arrivals entering a finite waiting room. Service is provided by a single server according to the limited service discipline with server vacation times. We determine the distributions of the time-dependent and stationary queue length in terms of generating functions by a symbolic operator method.     

Mean and variance of waiting time and their optimization for alternating traffic control systems

We analyze alternating traffic crossing a narrow one-lane bridge on a two-lane road. Once a car begins to cross the bridge in one direction, arriving cars from the other direction must wait, forming a queue, until all the arrivals in the first direction finish crossing the bridge. Such a situation can often be observed when road-maintenance work is being carried out. Cars are assumed to arrive at the queues according to independent Poisson processes and to cross the bridge in a constant time. In addition, once cars join the queue, each car needs a constant starting delay, before starting to cross the bridge. We model the situation where a signal controls the traffic so that the signal gives a priority to one direction as long as a new car from the same direction arrives in a fixed time. For this model, we get a closed form for the first two moments of the waiting time of cars arriving at the bridge, and then numerically obtain Pareto optimal solutions of holding times to minimize the mean waiting time and its standard deviation. To the memory of our best friend, Yo Ishizuka     

On effects of arrival rate and burstiness in the queueing system: Analysis ofLb/D/1

This paper studies a single-server queueing system with deterministic service time in which arrivals are regulated by the leaky-bucket mechanism. This paper intends to improve quantitative understanding of the effects of arrival rate and burstiness on the average delay of queueing systems. The study is directed toward identifying the worst traffic of arrivals allowed by the leaky-bucket regulation and clarifying the effects of the leaky bucket parameters (which represent the arrival rate and burstiness) on the average queueing delay. The arrival traffic that maximizes the average queueing delay is characterized as the repetition of the following three phases: bulky arrival, greedy arrival for a specified length of interval, and then no arrival till the token bucket is full. The average queueing delay for the worst traffic is expressed as a function the leaky bucket parameters.Research was partially supported by the NSF under grant ECS-8552419. Research was conducted at the Laboratory for Information and Decision Systems of the Massachusetts Institute of Technology and the U.S. Naval Research Laboratory.