General Stochastic Processes in the Theory of Queues

CHAPTER 1

VIRTUAL DELAY

1. INTRODUCTION

Congestion theory is the study of mathematical models of service systems, such as telephone central offices, waiting lines, and trunk groups. It has two practical uses: first, to provide engineers with specific mathematical results, curves, and tables, on the basis of which they can design actual systems; and second, to establish a general framework of concepts into which new problems can be fitted, and in which current problems can be solved. Corresponding to these two uses, there are two kinds of results: specific results pertaining to special models, and general theorems, valid for many models.

Most of the present literature of congestion theory consists of specific results resting on particular statistical assumptions about the traffic in the service system under study. Indeed, few results in congestion theory are known which do not depend on special statistical assumptions, such as negative exponential distributions, or independent random variables. In this monograph we describe some mathematical results which are free of such restrictions, and so constitute general theorems. These results concern general stochastic processes in the theory of queues with one server and order-of-arrival service.

In this work we have three aims: (1) to describe a new general approach to certain queueing problems; (2) to show that this approach, although quite general, can nevertheless be presented in a relatively elementary way, which makes it widely available; and (3) to illustrate how the new approach yields specific results, both new and known. What follows is written only partly as a contribution to the mathematical analysis of congestion. It is also, at least initially, a frankly tutorial account aimed at increasing the public understanding of congestion by first steering attention away from special statistical models, and obtaining a general theory. Such a point of view, it is hoped, will yield new methods in problems other than congestion.

When a general theory can be given, it will be useful in several ways. It will (i) increase our understanding of complex systems; (ii) yield new specific results, curves, tables, etc; and (iii) extend theory to cover interesting cases which are known to be inadequately described by existing results. At first acquaintance, the theorems of such a general theory may not resemble results at all; that is, they may not seem to be facts which one could obviously and easily use to solve a real problem. A general theory is really a tool or principle, expressing the essence or structure of a system; properly explained and used, this tool will yield formulas and other specifics with which problems can be treated.

2. THE SYSTEM TO BE STUDIED

There is a queue in front of a single server, and the waiting customers are served in order of arrival, with no defections from the queue. We are interested in the waiting-time of customers.

As a mathematical idealization of the delays to be suffered in the system, we use the virtual waiting-time W(t), which can be defined as the time a customer would have to wait for service if he arrived at time t. W(·) is continuous from the left; at epochs of arrival of customers, W(·) jumps upward discontinuously by an amount equal to the service-time of the arriving customer; otherwise W(·) has slope —1 while it is positive. If it reaches zero, it stays equal to zero until the next jump.

It is usual to define the stochastic process W(·) in terms of the arrival epoch tk and the service-time. Sk of the kth arriving customer, for k = 1, 2, …. However, the following procedure is a little more elegant; we describe the service-times and the arrival epochs simultaneously by a single function K(·), which is defined for t ≥ 0, left-continuous, nondecreasing, and constant between successive jumps. The locations of the jumps are the epochs of arrivals, and the magnitudes are the service-times. It is convenient to define K(·) to be continuous from the left, except at t = 0, where it is continuous from the right. The functions W(·) and K(·) are depicted simultaneously in Fig. 1.

FIG. 1. The load K(·) and the virtual delay W(·). At the epoch tk of arrival of the kth customer, W(·) jumps upward discontinuously by an amount equal to Sk, the service-time of the kth customer; otherwise, W(·) has slope –1 if it is positive; if it reaches zero it stays equal to zero until the next jump of the load function K(·).

If K(t) is interpreted as the work offered to the server in the interval [0, t), then W(t) can be thought of as the amount of work remaining to be done at time t. In terms of this interpretation, it can be seen that

Then formally, W(·) is denned in terms of K(·) by the integral equation

where U(t) is the unit step function, that is, U(x) = 1 for x ≥ 0, and U(x) = 0 otherwise.* For simplicity we have set W(0) = K(0).

It is possible to give an explicit solution of Eq. (1) in terms of K(·) and the supremum functional. This is the content of the following result of E. Reich [1].†

Lemma 1.1. If K(x) — x has a zero in (0, t), then

If K(x) – x > 0 for x ∈ (0, t), then W(t) = K(t) – t.

Proof. Let us set

Then

On the other hand, for 0 < x < t Eq. (1) gives

Lemma 1.1 provides