Search

We analyze the behavior of Generalized Processor Sharing (GPS) queues with heavy-tailed service times. We compute the exact tail asymptotics of the stationary workload of an individual class and give new conditions for reduced-load equivalence and induced burstiness to hold. We also show that both phenomena can occur simultaneously. Our proofs rely on the single big event theorem and new fluid limits obtained for the GPS system that can be of interest by themselves.

We analyze the queueing behavior of long-tailed traffic flows under the Generalized Processor Sharing (GPS) discipline. We show a sharp dichotomy in qualitative behavior, depending on the relative values of the weight parameters. For certain weight combinations, an individual flow with long-tailed traffic characteristics is effectively served at a constant rate. The effective service rate may be interpreted as the maximum average traffic rate for the flow to be stable, which is only influenced by the traffic characteristics of the other flows through their average rates. In particular, the flow is essentially immune from excessive activity of flows with ‘heavier’-tailed traffic characteristics. In many situations, the effective service rate is simply the link rate reduced by the aggregate average rate of the other flows. This confirms that GPS-based scheduling algorithms provide a potential mechanism for extracting significant multiplexing gains, while isolating individual flows. For other weight combinations however, a flow may be strongly affected by the activity of ‘heavier’-tailed flows, and may inherit their traffic characteristics, causing induced burstiness. The stark contrast in qualitative behavior illustrates the crucial importance of the weight parameters.

We study the departure process of a single server queue with Markovian arrival input and Markov renewal service time. We derive the joint transform of departure time and the number of departures and, based on this transform, we establish several expressions for burstiness (variance) and correlation (covariance sequence) of the departure process. These expressions reveal that burstiness and correlation of the arrival process have very little impact on the departure process when a queueing system is heavily loaded. In contrast, both burstiness and correlation of the service-time process greatly affect those of the departure process regardless of the load of the system. Finally, we show that, even when an arrival process is short-range dependent, the departure process could has long-range dependence if a service-time process is long-range dependent.

We focus on window flow control as used in packet-switched communication networks. The approach consists in studying the stability of a system where each node on the path followed by the packets of the controlled connection is modeled by a FIFO (First-In-First-Out) queue of infinite capacity which receives in addition some cross traffic represented by an exogenous flow. Under general stochastic assumptions, namely for stationary and ergodic input processes, we show the existence of a maximum throughput allowed by the flow control. Then we establish bounds on the value of this maximum throughput. These bounds, which do not coincide in general, are reached by time-space scalings of the exogenous flows. Therefore, the performance of the window flow control depends not only on the traffic intensity of the cross flows, but also on fine statistical characteristics such as the burstiness of these flows. These results are illustrated by several examples, including the case of a nonmonotone, nonconvex and fractal stability region.

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.

We use the concept of burstiness to propose new descriptors of arrival processes or, more generally, point or traffic processes. We say that the arrival process is in aburst when its interarrival times are less than or equal to some threshold value; during periods in which interarrival times are greater than the threshold value, the process is in agap. We propose to describe the arrival process in terms of the number of arrivals during a burst (gap) and the duration of a burst (gap). For the case of discrete-time Markovian arrival processes we derive the distribution of the number of arrivals during a burst (gap) and the mean duration of a burst (gap). We present numerical results to illustrate how our descriptors can be used to understand the behavior of an arrival process and the congestion it induces in a queueing system. We also report the results of an experiment which shows a statistical relationship between two of our descriptors and a measure of queueing congestion.

We study a stream of traffic or message as it is transferred over an ATM connection consisting of burst reducing servers. A message is modeled as a deterministic fluid flow, and an ATM node is modeled as a server which allocates bandwidth to messages. A message's burstiness curve b(μ) is the buffer size needed to prevent cell loss if it is served at rateμ. A server is burst reducing if its output message is always less bursty than the input message. Two popular bandwidth allocation schemes — the fixed rate and the leaky bucket server — are shown to be burst reducing. We also present a new class of burst reducing servers, the affine servers. We derive buffer requirements along a multi-hop connection and the final fluid flow reaching the destination as a message goes through a sequence of burst reducing servers. Finally, we suggest an approach to defining service quality.

The paper gives models and analytic techniques for addressing critical issues of the Broadband Integrated Services Digital Network which will use the Asynchronous Transfer Mode. The traffic is expected to be highly bursty and variable at the source and consequently a key issue is admission control. We study a 4-parameter device called a regulator which acts as a policing device as well as a traffic shaper. The device is a generalized leaky bucket with a data buffer, a token buffer supplied by a constant-rate token stream, and a peak rate controller; the outputs of the device are streams of priority and marked cells. The composite system comprising of the source and the regulator is represented in a stochastic fluid model since fluid flow has been found to have properties well matched to the ATM environment, and the Markov Modulated Fluid Source allows bursty characteristics to be accurately modelled. A complete procedure based on spectral expansions for calculating the system's stationary state distribution is given. It is shown that with proper design the regulator effectively controls a three-way trade-off between throughput, delay and burstiness. Numerical results reveal that performance is sensitive to source characteristics such as the squared coefficient of variation of burst and silent periods. The second part of the paper characterizes the output of the regulator. The distributions of the time periods spent in the various states by the output process are calculated exactly. From this an approximate Markovian characterization is obtained. The output streams of priority and marked cells are coupled to capture their correlations. For the simple case of two-state on-off sources, the approximate Markovian characterization of the regulator's output rate processes is explicitly given and it is distinguished by the property that all moments are identical to those of the actual processes. With this characterization an original goal of analyzing a composite system of access regulation and statistical multiplexing is separated, decomposed and thereby made tractable.

The Uniform Arrival and Service (UAS) model is one of several appropriate to modelling traffic offered to a multi-service communication channel. We exhibit, via asymptotics and a range of specific examples, that it is possible to assign a notionaleffective bandwidth to each source, dependent not only on its mean bandwidth but also on its burstiness and on the channel. The effective bandwidth can be calculated quickly and efficiently using the results of Anick, Mitra and Sondhi and reduces the multi-service network to the more familar, and well understood, form of a traditional circuit-switched network.