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).     

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     

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.     

Open problems in pluripotential theory

We propose a list of open problems in pluripotential theory partially motivated by their applications to complex differential geometry. The list includes both local questions as well as issues related to the compact complex manifold setting.     

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.     

Game theoretical optimization inspired by information theory

Inspired by previous work on information theoretical optimization problems, the basics of an axiomatic theory of certain special two-person zero-sum games is developed. One of the players, “Observer”, is imagined to have a “mind”, the other, “Nature”, not. These ideas lead to un-symmetric modeling as the two players are treated quite differently. Basic concavity- and convexity results as well as a general minimax theorem are derived from the axioms.     

Open problems in renewal, coupling and Palm theory

This note presents four sets of problems. The first suggests the possibility of a limit theory for null-recurrent renewal processes similar to the theory in the positive recurrent case. The second concerns exact coupling of random walks on the line with step-lengths that are neither discrete nor spread out. The third concerns the coupling characterization of setwise convergence of distributions of stochastic processes to a stationary limit. The fourth concerns characterizations of mass-stationarity, a concept formalizing the intuitive idea that the origin is a typical location in the mass of a random measure. Mass-stationarity is an intrinsic characterization of Palm versions with respect to stationary random measures.     

Open queueing networks in discrete time-some limit theorems

A finite number of nodes, each with a single server and infinite buffers, is considered in discrete time. The service may be FIFO and the service times are constant. The external arrivals and the routing decision variables form a general stationary sequence. Stability of the system is proved under these assumptions. Extension to multiple servers at a node and general stationary distributions holds. If the external input is i.i.d. and the routing is Markovian then stochastic ordering, continuity of stationary distributions, rates of convergence, a functional CLT and a functional LIL and various other limit theorems for the queue length process are also proved. Generalizations to multiple servers at nodes, customers with priority, multiple customer classes, general service length and Markov modulated external arrival cases are discussed.     

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.     

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     

Solving matrix polynomial equations arising in queueing problems

The matrix equation ∑_i=0ⁿA_iXⁱ=0, where the A_i's are m×m matrices, is encountered in the numerical solution of Markov chains which model queueing problems. We provide here a unifying framework in terms of Möbius' mapping to relate different resolution algorithms having a quadratic convergence. This allows us to compare algorithms like logarithmic reduction (LR) and cyclic reduction (CR), which extend Graeffe's iteration to matrix polynomials, and the invariant subspace (IS) approach, which extends Cardinal's algorithm. We devise new iterative techniques having quadratic convergence and present numerical experiments.     

Improved cyclic reduction for solving queueing problems

The cyclic reduction technique (Buzbee et al., 1970), rephrased in functional form (Bini and Meini, 1996), provides a numerically stable, quadratically convergent method for solving the matrix equation X = ∑^{+ ∞} _i=0 X_i A_i, where the A_i's are nonnegative k × k matrices such that ∑^{+ ∞} _i=0 A_i is column stochastic. In this paper we propose a further improvement of the above method, based on a point-wise evaluation/interpolation at a suitable set of Fourier points, of the functional relations defining each step of cyclic reduction (Bini and Meini,1996). This new technique allows us to devise an algorithm based on FFT having a lower computational cost and a higher numerical stability. Numerical results and comparisons are provided. This revised version was published online in August 2006 with corrections to the Cover Date.     

Open problems

One of the most fruitful activities that takes place at a conference is the interchange of problems. Often, in later years the success of a conference may be judged by the number of problems raised there which are eventually solved. The papers in the remainder of this volume contain several problems, but here are some more that did not fit naturally into any of those papers. I hope to see solutions of at least some of these problems in the pages of Positivity in years to come.     

Scheduling inspired models for two-dimensional packing problems

We propose two exact algorithms for two-dimensional orthogonal packing problems whose main components are simple mixed-integer linear programming models. Based on the different forms of time representation in scheduling formulations, we extend the concept of multiple time grids into a second dimension and propose a hybrid discrete/continuous-space formulation. By relying on events to continuously locate the rectangles along the strip height, we aim to reduce the size of the resulting mathematical problem when compared to a pure discrete-space model, with hopes of achieving a better computational performance. Through the solution of a set of 29 test instances from the literature, we show that this was mostly accomplished, primarily because the associated search strategy can quickly find good feasible solutions prior to the optimum, which may be very important in real industrial environments. We also provide a comprehensive comparison to seven other conceptually different approaches that have solved the same strip packing problems.     

An approximation for computing the throughput of closed assembly-type queueing networks

In this paper, we examine throughput (mean number of completed assemblies per unit time) of closed assembly type queueing networks where machine processing times are drawn from general distributions. The system dynamics are characterized via a set of stochastic difference equations; it is shown that the system state can be modeled by a discrete index Markov chain on a continuous state space. Standard Markovian analysis is employed to derive an approximate expression for system throughput, following discretisation of state space. Four examples of CONWIP (CONstant Work IN Process) systems are given that illustrate the results.     

Order statistics applications to queueing and scheduling problems

We prove several basic combinatorial identities and use them in two applications: the queue inference engine (QIE) and earliest due date rule (EDD) scheduling. Larson (1990) introduced the QIE. His objective was to deduce the behavior of a multiserver queueing system without observing the queue. With only a Poisson arrival assumption, he analyzed the performance during a busy period. Such a period starts once all servers are busy with the queue empty, and it ends as soon as a server becomes idle. We generalize the standard order statistics result for Poisson processes, and show how to sample a busy period in the M/M/c system. We derive simple expressions for the variance of the total waiting time in the M/M/c and M/D/1 queues given that n Poisson arrivals and departures occur during a busy period. We also perform a probabilistic analysis of the EDD for a one-machine scheduling problem with earliness and tardiness penalties. The schedule is without preemption and with no inserted idle time. The jobs are independent and each may have a different due date. For large n, we show that the variance of the total penalty costs of the EDD is linear in n. The mean of the total penalty costs of the EDD is known to be proportional to the square root of n (see Harel (1993)). This revised version was published online in June 2006 with corrections to the Cover Date.