A survey of queueing theory

This paper is intended to give a survey of the main results of queueing theory in China. It consists of five parts: (1) the transient behaviour of typical queueing systems; (2) classical problems; (3) approximation theory; (4) model structure; (5) applications.     

A discrete-time retrial queueing model with one server

This paper presents a one-server queueing model with retrials in discrete-time. The number of primary jobs arriving in a time slot follows a general probability distribution and the different numbers of primary arrivals in consecutive time slots are mutually independent. Each job requires from the server a generally distributed number of slots for its service, and the service times of the different jobs are independent. Jobs arriving in a slot can start their service only at the beginning of the next slot. When upon arrival jobs find the server busy all incoming jobs are sent into orbit. When upon arrival in a slot jobs find the server idle, then one of the incoming jobs (randomly chosen) in that slot starts its service at the beginning of the next slot, whereas the other incoming jobs in that slot, if any, are sent into orbit. During each slot jobs in the orbit try to re-enter the system individually, independent of each other, with a given retrial probability.     

Asymptotic relations in queueing theory

For the GI?G?1 queueing system a number of asymptotic results are reviewed. Discussed are asymptotics related to the time parameter for t → ∞ relaxation times, heavy traffic theory, restricted accessibility with large bounds, approximation by diffusion processes, exponential and regular variation of the tail of the waiting time distribution, limit theorems and extreme value theorems.     

A topological view of Gromov-Witten theory

We study relative Gromov-Witten theory via universal relations provided by the degeneration and localization formulas. We find relative Gromov-Witten theory is completely determined by absolute Gromov-Witten theory. The relationship between the relative and absolute theories is guided by a strong analogy to classical topology.As an outcome, we present a mathematical determination of the Gromov-Witten invariants (in all genera) of the Calabi-Yau quintic 3-fold in terms of known theories.     

A lot sizing model with queueing delays: The issue of safety time

The objective of this paper is to introduce the concept of safety time in a make-to-order production environment. The production facility is represented as a queueing model, explicitly including a non-zero setup time. A methodology is presented to quantify the safety time and to compute the associated service level based on the queueing delay. The main result is a convex relationship of the expected waiting time, the variance of the waiting time and the quoted lead time as a function of the lot size and a concave relationship of the service level as a function of the lot size. Most models in the literature assume batch arrivals. We relax that assumption so that an individual customer arrival process is allowed. We therefore have to derive a new closed form analytical expression for the expected waiting time. Both the deterministic and a stochastic case are studied.     

Boundary value problems in queueing theory

Recently complex function techniques have been developed for the analysis of queueing systems which need for their modelling a two dimensional state space. A variety of computer- and communication networks gives rise to such two-dimensional queueing systems and their analysis is needed for the performance evaluation of these aggregates. The present study reviews these developments     

The problem of stability in queueing theory

The stability problem in queueing theory is concerned with the continuity of the mappingF from the setU of the input flows into the setV of the output flows. First, using the theory of probability metrics we estimate the modulus ofF-continuity providing thatU andV have structures of metric spaces. Then we evaluate the error terms in the approximation of the input flows by simpler ones assuming that we have observed some functionals of the empirical input flows distributions.Research initiated under support by Army Office of Scientific Research through Mathematical Sciences Institute during the author's visit to MSI in December 1988. References     

Valuation theory: A constructive view

The theory of valuations on fields is developed in the constructive spirit of Errett Bishop. As a consequence of the general theory we are able to construct all nonarchimedean valuations on algebraic number fields and compute their ramification indices and residue class degrees. The notion of a field with a valuation for which the infimum of the values of any polynomial function can be computed plays an important role. Numerous limiting counterexamples are provided.     

Open problems in Gaussian fluid queueing theory

We present three challenging open problems that originate from the analysis of the asymptotic behavior of Gaussian fluid queueing models. In particular, we address the problem of characterizing the correlation structure of the stationary buffer content process, the speed of convergence to stationarity, and analysis of an asymptotic constant associated with the stationary buffer content distribution (the so-called Pickands constant).     

Inverse problems in queueing theory and Internet probing

Queueing theory is typically concerned with the solution of direct problems, where the trajectory of the queueing system, and laws thereof, are derived based on a complete specification of the system, its inputs and initial conditions. In this paper we point out the importance of inverse problems in queueing theory, which aim to deduce unknown parameters of the system based on partially observed trajectories. We focus on the class of problems stemming from probing based methods for packet switched telecommunications networks, which have become a central tool in the measurement of the structure and performance of the Internet. We provide a general definition of the inverse problems in this class and map out the key variants: the analytical methods, the statistical methods and the design of experiments. We also contribute to the theory in each of these subdomains. Accordingly, a particular inverse problem based on product-form queueing network theory is tackled in detail, and a number of other examples are given. We also show how this inverse problem viewpoint translates to the design of concrete Internet probing applications.     

Real-time queueing theory: A tutorial presentation with an admission control application

Real-time scheduling, or scheduling with respect to a deadline, is critical in many application areas such as telecommunications, control systems, and manufacturing. This paper presents a novel approach to real-time scheduling based on a queueing theory model. Using real-time queueing theory (RTQT), one can analytically determine the distribution of the lead-time profile (i.e., the time until the deadline is reached) of customers waiting for service. Emphasis is placed on the development of the equations used to determine the lead-time profile distribution. The development of the GI/G/1 case is presented and confirmed using simulation. Simulation results confirm prior research for the M/M/1 and GI/M/1 case. As a practical application, RTQT is used to implement a packet admission control algorithm for a telecommunications network. Using this algorithm, packet lateness was reduced by up to 31%. This revised version was published online in June 2006 with corrections to the Cover Date.     

A queueing model of a production system with two machines,one operator and priorities

This paper studies a priority queueing model of a production system in which one operator serves two types of units with overlapping service times. The two types of units arrive in independent Poisson processes. There are two machines in the system. Units of type 1 receive two consecutive types of services at machine #1: the handwork performed by the operator and the automatic machining without the operator. Units of type 2 receive only the handwork performed by the operator at machine #2. The operator attends the two machines according to a strict-priority discipline which always gives units of type 2 higher priority than units of type 1. At each machine the handwork times have a general distribution, and at machine #1 the machining times have an exponential distribution. The Laplace-Stieltjes transform of the queue-size distributions and the waiting time distributions for a stationary process are obtained.     

Open problems in queueing theory inspired by datacenter computing

Queueing Systems - Datacenter operations today provide a plethora of new queueing and scheduling problems. The notion of a “job” has become more general and multi-dimensional. The ways...