Read an Excerpt

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.

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

Work remaining at t = total work load offered up to t - elapsed time + total time during which server was idle in (0, t).

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

[MATHEMATICAL EXPRESSION OMITTED]

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.

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

[MATHEMATICAL EXPRESSION OMITTED]

If K(x) - x > 0 for x [member of] (0, t), then W(t) = K(t) - t.

Proof. Let us set

z(t) = sup{u:0 < u < t and W(u) = 0}.

Then

[MATHEMATICAL EXPRESSION OMITTED]

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

[MATHEMATICAL EXPRESSION OMITTED]

Lemma 1.1 provides an explicit characterization of the important event {W(t) = 0} purely in terms of K(·) and the supremum functional, as follows.

Lemma 1.2.W(t) = 0 if and only if

K(t) ≤ t, (2)

and

[MATHEMATICAL EXPRESSION OMITTED]. (3)

Proof. Suppose that W(t) = 0. Then Eq. (1) implies

[MATHEMATICAL EXPRESSION OMITTED],

so that K(t) ≤ t. Also, as in Lemma 1.1, for 0 < x < t,

[MATHEMATICAL EXPRESSION OMITTED].

Hence W(t) = 0 implies

[MATHEMATICAL EXPRESSION OMITTED].

Conversely, assume the conditions (2) and (3) of Lemma 1.2.

Case 1. K(x) = x for some x [member of] (0, t). Then by Lemma 1.1,

[MATHEMATICAL EXPRESSION OMITTED].

Since W(·) is nonnegative, we have W(t) = 0.

Case 2. K(x) = x for no x [member of] (0, t). Then by Lemma 1.1,

W(t) = K(t) - t ≤ 0.

We note that Lemma 1.2 takes into account the initial value W(0) = K(0), as it should.

Lemma 1.1 may be interpreted physically in the following manner. The quantity in braces {K(t) - K(x) - t + x} is, if positive, the excess of arriving load in the interval [x, t) over the elapsed time t - x; it is therefore the overload in [x, t). Reich's formula then says, essentially, that

[MATHEMATICAL EXPRESSION OMITTED].

The relationship between the waiting-time W(·) and the offered traffic K(·) can be further elucidated graphically by reference to Fig. 2. The light solid line shows K(t) - t, the traffic offered up to time t minus the traffic that could have been served if the server had been kept busy throughout the interval (0, t).

It is assumed, in Fig. 2, that the server starts busy at t = 0. It is busy until t = a. At this point the server becomes idle, and K(t) - t turns negative; its negative value is the negative of the idle time. At t = b, more traffic is offered, and K(t) - t jumps up.

The heavy dashed line represents the waiting-time at t, W (t); W(t) can also be thought of as the traffic in hand and yet to be served at time t. This line can never be negative. It is equal to K(t) - t before a and is zero from a to b. At b it jumps up, remaining above and parallel to K(t) - t until t = d, when the server becomes idle again. W(t) is above K(t) - t by exactly the amount by which K(t) - t was most negative at b. At d, when W(t) reaches zero, K(t) - t is just reaching its previous local infimum, and K(d) - d = K(b) - b.

During the interval (d, e), W(·) remains at zero, and K(t) - t becomes more negative, establishing new local infima as it goes, and building up more idle time. At t = e, K(t) - t and W(·) both jump up. Again W(·) is parallel to K(t) - t, but is now above it by an amount equal to the negative of the last infimum, K(e) - e.

In Fig. 2,

[MATHEMATICAL EXPRESSION OMITTED]

is shown as a light dashed line. It is a monotone, nonincreasing function of t, and is the negative of the total idle time up to time t. To account for the period t < a, when K(t) - t has not yet become negative, and the server has not yet been idle, we write

[MATHEMATICAL EXPRESSION OMITTED],

and thus obtain another representation for the delay; i.e., a solution of Eq. (1).

In a manner similar to that of Fig. 2, Fig. 3 depicts, simultaneously, the offered load K(·) in a light solid line, the waiting-time W(·) in a heavy solid line, the negative of the accumulated idle time in a heavy dashed line, and the "load-time excess" K(t) - t in a light dashed line, when it does not coincide with the negative of the idle time. The terminology in Fig. 3 has been purposely chosen to suggest an interpretation in terms of inventory or storage theory. W(t) is the real backlog (of orders, say), K(t) is the cumulative amount ordered, and K(t) - t might be termed the load-time excess or the virtual backlog. Then

Real backlog = virtual backlog + accumulated idle time.

3. CHARACTER OF THE RESULTS TO BE PROVEN

Models of waiting lines usually contain explicit assumptions about the statistical nature of the offered load K(·). For instance, the simplest models amount to assuming that the interarrival times (tn - tn-1) are all independent, with the same negative exponential distribution; a similar assumption is made for the service-times. These assumptions give a class of models parametrized by the means of the negative exponential distributions.

A broader class of models is specified by retaining the assumptions that the interarrival times be independent and identically distributed (and similarly for service-times), but allowing any distribution, not just the negative exponential. The interarrival and service-time distributions may still be said to "parametrize" this broader class of models, since their choice determines a model in the class. In the papers of Khinchin, Kendall, Bailey, Takács (5), and Benes, the arrivals form a Poisson process, and the service-times are independent of each other and of the arrival process. In the work of Smith and Lindley, it is assumed that the interarrival-times and the service-times are (independent) renewal processes. The references just cited are merely representative; we make no attempt to give an adequate bibliography of the subject.

Indeed, the literature of applied probability theory contains many investigations of waiting-times (for one server); however, these studies have depended essentially on assumptions of statistical independence or special distributions. Many useful and interesting results have been obtained under these assumptions, which probably include most cases of practical interest. We believe, though, that the assumptions have tended to obscure the stochastic process of interest (the waiting-time) with analytical detail, since it is not always possible to separate the essential features of the stochastic process from those which only reflect the strength and analytic nature of the hypotheses.

As assumptions more general even than those of Lindley are considered, it becomes extremely laborious to specify the model first, and then compute interesting quantities, such as distributions of delay, probabilities of loss, etc. So instead of looking for ways of exactly characterizing the model, we can try to search directly for simple ways of expressing the quantities of interest in terms of the model. Since the probability

Pr {W(t) ≤ w} (4)

is what we actually wish to compute from the model, the question arises whether this calculation can be made without first specifying the entire probabilistic structure of K(·). The following intuitive argument can be adduced for answering "yes." W(·) is denned in terms of the load K(·) by a very special relationship, expressed in the integral equation (1); hence, no matter what are the statistical features of K(·), it is likely that the distribution of W(·) depends only on some very particular, physically interpretable, statistical functions associated with K(·). It is not obvious that such an economy can be made in the generality we desire.

A principal result [formulas (2.4) and (2.5) or (3.16) and (3.17)], described in later sections, states that the probability (4) can, in fact, be given a fairly simple expression which is generally valid for any load process. This expression depends only on two special functions obtainable from the statistical structure of the load K(·). Each function has a definite intuitive or physical significance, given later. These statistical functions achieve the desired economy of description because we can state that the desired probabilities depend only on the features of K(·) expressed in the functions. For the purposes of calculating (4), we do not need the entire probabilistic structure of K(·), but only a relatively small relevant part.

From a theoretical viewpoint, the assumptions made in the literature have been inadmissibly strong. For indeed, Eq. (1) defines a transformation of a stochastic process K(·) of service-times and arrival epochs into another stochastic process W(·) of waiting-times. For each t, there is an operator or formula which gives the distribution of W(t) in terms of suitable fundamental statistical functions associated with K (u) for u ≤ t. The principal problem is to find the form of the operator and the character of the fundamental functions. The answer to this problem should depend only on the integral equation (1) and on the fact that K(·) is a nondecreasing step function. It should depend on no special features of the probability measure for K(·) except those implied by this last property.

Some inkling of the nature of this answer can be given briefly here. The operator we seek is linear and operates only on the distribution of K(t) - t, and, for each u ≤ t, on the conditional distribution of K(t) - K(u) — t + u relative to the knowledge that

[MATHEMATICAL EXPRESSION OMITTED].

Accordingly, the present work involves (at first) no assumptions of independence and no special distributions. We shall assume at first that K(·) is a random, nondecreasing step function; its only statistical peculiarity is that it is a nondecreasing step function.

Another way of putting the problem we have attempted to solve is as follows: For general load processes K(·), what is a small amount of information about the statistical nature of K(·) with which one can nevertheless compute Pr {W(t) ≤ w} for all t and w, and how is this calculation to be made? The required statistical functions are then the information about K(·); the formula for the probability (4)indicates the method of calculation.

One approach to the waiting-times, used really in all the papers cited previously, is to solve the Kolmogorov equations for the distributions of a Markov process. Since our assumptions do not necessarily give rise to a Markov process, this approach is not sufficiently general to solve our problem.

Another possibility is to first solve Eq. (1) and then try to express the distribution of the solution W(t) in terms of the probability measure for K(u), u ≤ t. However, the solution of (1) involves the supremum functional, and so, although it is adequate in some cases, this approach incurs directly the notorious difficulties associated with the distribution of a supremum.

(Continues…)

---

Excerpted from "General Stochastic Processes in the Theory of Queues"
by .
Copyright © 2017 Dover Publications, Inc..
Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---