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.     

On extreme values in open queueing networks

This paper presents heavy traffic limit theorems for the extreme virtual waiting time of a customer in an open queueing network. In this paper, functional limit theorems are proved for extreme values of important probability characteristics of the open queueing network investigated as the maximum and minimum of the total virtual waiting time of a customer, and the maximum and minimum of the virtual waiting time of a customer. Also, the paper presents the previous related works for extreme values in queues and the virtual waiting time in heavy traffic.     

Exact asymptotic formulae of the stationary distribution of a discrete-time two-dimensional QBD process

We propose an analytically tractable approach for studying the transient behavior of multi-server queueing systems and feed-forward networks. We model the queueing primitives via polyhedral uncertainty sets inspired by the limit laws of probability. These uncertainty sets are characterized by variability parameters that control the degree of conservatism of the model. Assuming the inter-arrival and service times belong to such uncertainty sets, we obtain closed-form expressions for the worst case transient system time in multi-server queues and feed-forward networks with deterministic routing. These analytic formulas offer rich qualitative insights on the dependence of the system times as a function of the variability parameters and the fundamental quantities in the queueing system. To approximate the average behavior, we treat the variability parameters as random variables and infer their density by using ideas from queues in heavy traffic under reflected Brownian motion. We then average the worst case values obtained with respect to the variability parameters. Our averaging approach yields approximations that match the diffusion approximations for a single queue with light-tailed primitives and allows us to extend the framework to heavy-tailed feed-forward networks. Our methodology achieves significant computational tractability and provides accurate approximations for the expected system time relative to simulated values.     

A two-server queueing system with periodic and credit-based server availabilities

A discrete-time, two-server queueing system is studied in this paper. The service time of a customer (cell) is fixed and equal to one time unit. Server 1 provides for periodic service of the queue (periodT). Server 2 provides for service only when server 1 is unavailable and provided that the associated service credit is nonzero. The resulting system is shown to model the queueing behavior of a network user which is subject to traffic regulation for congestion avoidance in high speed ATM networks. A general methodology is developed for the study of this queueing system, based on renewal theory. The dimensionality of the developed model is independent ofT;T increases with the network speed. The cell loss probabilities are computed in the case of finite capacity queue.Research supported by the National Science Foundation under grant NCR-9011962.     

About the Sojourn Time Process in Multiphase Queueing Systems

Multiphase queueing systems (MQS) (tandem queues, queues in series) are of special interest both in theory and in practical applications (packet switch structures, cellular mobile networks, message switching systems, retransmission of video images, asembly lines, etc.). In this paper, we deal with approximations of MQS and present a heavy traffic limit theorems for the sojourn time of a customer in MQS. Functional limit theorems are proved for the customer sojourn time – an important probability characteristic of the queueing system under conditions of heavy traffic.      

The Law of the Iterated Logarithm for Extreme Waiting Time in Multiphase Queueing Systems

The objective of this research in the queueing theory is the law of the iterated logarithm (LIL) under the conditions of heavy traffic in multiphase queueing systems (MQS). In this paper, the LIL is proved for the extreme values of some important probabilistic characteristics of the MQS, namely, maxima and minima of the summary waiting time of a customer, and maxima and minima of the waiting time of a customer.     

An interpolation approximation for the GI/G/1 queue based on multipoint Padé approximation

The performance evaluation of many complex manufacturing, communication and computer systems has been made possible by modeling them as queueing systems. Many approximations used in queueing theory have been drawn from the behavior of queues in light and heavy traffic conditions. In this paper, we propose a new approximation technique, which combines the light and heavy traffic characteristics. This interpolation approximation is based on the theory of multipoint Padé approximation which is applied at two points: light and heavy traffic. We show how this can be applied for estimating the waiting time moments of the ^GI/G/1 queue. The light traffic derivatives of any order can be evaluated using the MacLaurin series analysis procedure. The heavy traffic limits of the ^GI/G/1 queue are well known in the literature. Our technique generalizes the previously developed interpolation approximations and can be used to approximate any order of the waiting time moments. Through numerical examples, we show that the moments of the steady state waiting time can be estimated with extremely high accuracy under all ranges of traffic intensities using low orders of the approximant. We also present a framework for the development of simple analytical approximation formulas. This revised version was published online in June 2006 with corrections to the Cover Date.     

Vehicle routing with dynamic travel times: A queueing approach

Transportation is an important component of supply chain competitiveness since it plays a major role in the inbound, inter-facility, and outbound logistics. In this context, assigning and scheduling vehicle routes is a crucial management problem. In this paper, a vehicle routing problem with dynamic travel times due to potential traffic congestion is considered. The approach developed introduces mainly the traffic congestion component based on queueing theory. This is an innovative modeling scheme to capture travel times. The queueing approach is compared with other approaches and its potential benefits are described and quantified. Moreover, the optimization of the starting times of a route at the distribution center is evaluated. Finally, the trade-off between solution quality and calculation time is discussed. Numerous test instances are used, both to illustrate the appropriateness of the approach as well as to show that time-independent solutions are often unrealistic within a congested traffic environment, which is usually the case on European road networks.     

On the Full Idle Time in Multiphase Queueing Systems

The modern queueing theory is a powerful tool for a quantitative and qualitative analysis of communication systems, computer networks, transportation systems, and many other technical systems. The paper is designated to the analysis of queueing systems arising in the network theory and communications theory (such as the so-called multiphase queueing systems, tandem queues, or series of queueing systems). We present heavy traffic limit theorems for the full idle time in multiphase queueing systems. We prove functional limit theorems for values of the full idle time of a queueing system, which is its important probability characteristic. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 45, No. 3, pp. 367–386, July–September, 2005.     

The Buffer-Bandwidth Trade-off Curve is Convex

To achieve a constant overflow probability, the two queueing resources, viz. buffer and bandwidth, can be traded off. In this paper we prove that, under general circumstances, the corresponding trade-off curve is convex in the 'many-sources scaling'. This convexity enables optimal resource partitioning in a queueing system supporting heterogeneous traffic, with heterogeneous quality-of-service requirements.     

A Law of the Iterated Logarithm for the Sojourn Time Process in Queues in Series

The object of this research in the sphere of queueing theory is the law of the iterated logarithm under the conditions of heavy traffic in queues in series. In this paper, the laws of the iterated logarithm are proved for the values of important probabilistic characteristics of the queueing system, like the sojourn time of a customer, and maximum of the sojourn time of a customer. Also, we prove that the sojourn time of a customer can be approximated by some recurrent functional. We also provide the results of statistical simulations for various system parameters and distributions.     

Empirical validation of a queueing approach to uninterrupted traffic flows

In this paper, the use of queueing theory for modeling uninterrupted traffic flows is evaluated. Empirical data on speeds and flows are used to evaluate speeds generated by the different queueing models. Using the Theil inequality coefficient as evaluation criterion, the speeds generated by the queueing models are compared to the empirical speeds. Queueing models that best fit the observed speeds are obtained. It appears that traffic flow on a highway during non-congested hours is best described using a M/G/1 queueing model. During the congested hours however, the state dependent queueing GI/G/z models are more realistic. Because the queueing models describe the empirical data well, they can also be used to evaluate potential improvements in existing traffic conditions. Received: April 2005 / Revised version: June 2005 AMS classification: 60K30, 68M20     

An invariance principle for semimartingale reflecting Brownian motions in an orthant

Semimartingale reflecting Brownian motions in an orthant (SRBMs) are of interest in applied probability because of their role as heavy traffic approximations for open queueing networks. It is shown in this paper that a process which satisfies the definition of an SRBM, except that small random perturbations in the defining conditions are allowed, is close in distribution to an SRBM. This perturbation result is called an invariance principle by analogy with the invariance principle of Stroock and Varadhan for diffusions with boundary conditions. A crucial ingredient in the proof of this result is an oscillation inequality for solutions of a perturbed Skorokhod problem. In a subsequent paper, the invariance principle is used to give general conditions under which a heavy traffic limit theorem holds for open multiclass queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Analysis of the Virtual Waiting Time in Open Queueing Networks

The model of an open queueing network in heavy traffic has been developed. These models are mathematical models of computer networks in heavy traffic. A limit theorem has been presented for the virtual waiting time of a customer in heavy traffic in open queueing networks. Finally, we present an application of the theorem—a reliability model from computer network practice.     

On the law of the iterated logarithm in open queueing networks

An open queueing network model in heavy traffic is developed. Such models are mathematical models of computer networks in heavy traffic. Laws of the iterated logarithm for the virtual waiting time of the customer in open queueing networks and homogeneous computer networks are proved.     

饱和情形开排队网络的强逼近

本文用强逼近理论和斜反射定理，研究了饱和情形下的开排队网络，得到了队长、虚等待时间和顾客在网络中逗留时间的强逼近定理．     

Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing

We consider characterizations of departure functions in Markovian queueing networks with batch movements and state-dependent routing in discrete-time and in continuous-time. For this purpose, the notion of structure-reversibility is introduced, which means that the time-reversed dynamics of a queueing network corresponds with the same type of queueing network. The notion is useful to derive a traffic equation. We also introduce a multi-source model, which means that there are different types of outside sources, to capture a wider range of applications. Characterizations of the departure functions are obtained for any routing mechanism of customers satisfying a recurrent condition. These results give a unified view to queueing network models with linear traffic equations. Furthermore, they enable us to consider new examples as well as show limited usages of this kind of queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of a single-server queue interacting with a fluid reservoir

We consider a single-server queueing system with Poisson arrivals in which the speed of the server depends on whether an associated fluid reservoir is empty or not. Conversely, the rate of change of the content of the reservoir is determined by the state of the queueing system, since the reservoir fills during idle periods and depletes during busy periods of the server. Our interest focuses on the stationary joint distribution of the number of customers in the system and the content of the fluid reservoir, from which various performance measures such as the steady-state sojourn time distribution of a customer may be obtained. We study two variants of the system. For the first, in which the fluid reservoir is infinitely large, we present an exact analysis. The variant in which the fluid reservoir is finite is analysed approximatively through a discretization technique. The system may serve as a mathematical model for a traffic regulation mechanism - a two-level traffic shaper - at the edge of an ATM network, regulating a very bursty source. We present some numerical results showing the effect of the mechanism. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analyzing a Two-Stage Queueing System with Many Point Process Arrivals at Upstream Queue

We consider a two-stage queueing system where the first (upstream) queue serves many flows, of which a fixed set of flows arrive to the second (downstream) queue. We show that as the capacity and the number of flows aggregated at the upstream queue increases, the overflow probability at the downstream queue converges to that of a simplified single queue obtained by removing the upstream queue from the original two-stage queueing system. Earlier work shows such convergence for fluid traffic, by exploiting the large deviation result that the workload goes to zero almost surely, as the number of flows and capacity is scaled. However, the analysis is quite different and more difficult for the point process traffic considered in this paper. The reason is that for point process traffic the large deviation rate function need not be strictly positive (i.e., I(0)=0), hence the workload at the upstream queue may not go to zero even though the number of flows and capacity go to infinity. The results in this paper thus make it possible to decompose the original two-stage queueing system into a simple single-stage queueing system.     

State space collapse with application to heavy traffic limits for multiclass queueing networks

Heavy traffic limits for multiclass queueing networks are a topic of continuing interest. Presently, the class of networks for which these limits have been rigorously derived is restricted. An important ingredient in such work is the demonstration of state space collapse. Here, we demonstrate state space collapse for two families of networks, first-in first-out (FIFO) queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks, we employ law of large number estimates to show a form of compactness for appropriately scaled solutions. The limits of these solutions are next shown to satisfy fluid model equations corresponding to the above queueing networks. Results from Bramson [4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams [41]. State space collapse and the ensuing heavy traffic limits also hold for more general queueing networks, provided the solutions of their fluid model equations converge. Partial results are given for such networks, which include the static priority disciplines. This revised version was published online in June 2006 with corrections to the Cover Date.