Stochastic Networks and Queues

This chapter introduces the basic definitions and results concerning point processes. A point process is the mathematical object used to describe the flow of customers in a queueing system: the arrival instants and the value of services they require. It can be an arrival process as well as a departure process. General definitions and properties of point processes are briefly presented. An important subclass is analyzed in detail: Poisson point processes. The Poisson point process is, with Brownian motion, an ubiquitous object in probability theory. It shows up in numerous limit theorems and the explicit form of the distribution of many of its functionals can be easily derived. Poisson point processes are presented in a quite general framework (a locally compact space or a complete metric space) because their main properties are simple and independent of the particular structure of ℝ ^d where they are generally considered. Moreover, this level of generality is required to study the important marked Poisson point processes. The last part of this chapter is a short summary of the main properties of renewal point processes, including the renewal theorem.

The arrival process of this queue is a renewal point process, services of the customers form an i.i.d. sequence and the service discipline is First In First Out (FIFO). It works as follows: When a customer requiring a service x ≥ 0 arrives at the queue, it joins the queue and as soon as it is at the head of the queue (i.e. all the customers arrived before him have left the queue), it is served for a duration of time x by the server.

The Wiener-Hopf factorization gives a method to get the Laplace transform of the stationary waiting time of a GI/GI/1 FIFO queue. In practice, see Section 2.5 of Chapter 2, this method consists in locating the poles and the roots of a function in the complex plane. In practice, it is not always easy to get the number of poles and zeros of a complex function in general, and a fortiori to locate them. For this reason, getting some simple qualitative results for the GI/GI/1 FIFO queue may turn out to be quite difficult.

This chapter investigates the equilibrium behavior of some queueing networks.

The queue with an infinite number of servers is, with the M/M/1queue, a basic model. It plays a crucial role in most of the stochastic models of communication networks. If the M/M/1 queue is the basic element of a Jackson network (see Section 4.4.1 page 92), the M/M/∞ queue is the basic element of loss networks (see Example 4.2.3 page 88) used to represent communication networks. As it is the case for the M/M/1 queue, the stochastic processes describing this queue are not only important in the analysis of queueing systems but also in various areas such as statistical physics or theoretical computer science.

The general problem of convergence in distribution of Markov chains with a countable state space is investigated in this chapter. For the GI/GI/1 queue in Chapter 2, the convergence in distribution of the Markov chain (W _n ) has been obtained by using an explicit representation of the random variable W _n as a functional of the random walk associated with the interarrival times and the service times. Markov chains describing the behavior of most queueing systems cannot, in general, be represented in such a simple way. In this chapter, simple criteria are given to determine whether a given Markov chain is ergodic or transient. The main results are Theorem 8.6 for ergodicity and Theorem 8.10 for transience. In practice, these results can be used in many applications. These criteria can be seen as an extension, in a probabilistic setting, of a classical stability result of ordinary differential equations due to Lyapunov^[Lia07] in 1892. In a stochastic context, the first results of this type are apparently due to Khasminskii for diffusions (see Khasminskii [26]). The stability criterion by Lyapunov is recalled at the end of the chapter (see Hirsch and Smale [27] for a detailed presentation of these questions). In Chapter 9, an important scaling method is introduced that will give a more precise picture of the relation between the stability of ordinary differential equations and the stability properties of Markov

It is in general quite difficult to have a satisfactory description of an ergodic Markov process describing a stochastic network. When the dimension of the state space d is greater than 1, the geometry complicates a lot any investigation: Analytical tools of Chapter 2 for dimension 1 cannot be easily generalized to higher dimensions. Note that the natural order on the real line plays an important role for Wiener-Hopf methods. The example of queueing networks seen in Chapter 4 for which the stationary distribution has a product form should be seen as an interesting exception, but an exception. In the same way as in Chapter 3, it is possible nevertheless to get some insight on the behavior of these processes through some limit theorems. In this chapter, limit results consist in speeding up time and scaling appropriately the process itself with some parameter. The behavior of such rescaled stochastic processes is analyzed when the scaling parameter goes to infinity. In the limit one gets a sort of caricature of the initial stochastic process which is defined as a fluid limit (see the rigorous definition below). As it will be seen, a fluid limit keeps the main characteristics of the initial stochastic process while some stochastic fluctuations of second order vanish with this procedure. In “good cases”, a fluid limit is a deterministic function, solution of some ordinary differential equation. As it can be expected, the general situation is somewhat more complicated. These ideas of rescaling stochastic processes have emerged recently in the analysis of stochastic networks, to study their ergodicity properties in particular. See Rybko and Stolyar^[RS92] for example. In statistical physics, these methods are quite classical, see Comets^[Com91].

In this chapter definitions and basic results of ergodic theory are presented in a probabilistic setting. It must be stressed that this is a fundamental topic in probability theory. Results proved in this chapter are classical in a Markovian framework (ergodic theorems, representations of the invariant probability,...). It is nevertheless very helpful to realize that the Markov property does not really play a role to get these results: They also hold in a much more general (and natural) setting. As it will be seen in Chapter 11, the study of stationary point processes is quite elementary if a basic construction of ergodic theory is used (the “special flow” defined page 295). Since this subject is not standard in graduate courses on stochastic processes, most of the results are proved. The reference book Cornfeld et al. [13] gives a broader point of view of this domain. In the following (Ω,.ℱ, ℙ) is the probability space of reference.

A queueing system can be seen as an operator on arrival processes. If the sequence of the arrival times of customers is (t _n ) and (S _n ) is the sequence of their respective sojourn times in the queue (the nth customer arrives at time t _n and leaves at t _n + S _n ). The queue transforms a point process {t _n } (the arrival process) in another point process {t _n + S _n } (the departure process). In this setting, it is quite natural to investigate the properties of point processes that are preserved by such a transformation. In fact, very few properties remain unchanged. Most of the independence properties are lost for the departure process (the examples of the M/M/1 queue or some product form networks seen in Chapter 4 are remarkable exceptions to this general rule). For example, if the arrival process is a renewal process, the departure process is not, in general, a renewal process.

The single server queue with First In First Out service discipline is analyzed in a general framework in this chapter.