Multiaccess, Reservations & Queues

This book proposes and analyses delay models for communication over a shared channel by means of a reservation procedure. In this introductory chapter, we discuss in general terms the main concepts for multiaccess communication: Contention resolution and reservation procedures. We then turn to cable networks and describe in some detail the current protocols to transmit data. Moreover, we give examples, obtained by complex system simulations, of the specific performance issues that arise in the evaluation of these networks. These examples have strongly motivated our research effort, in which we aim at complementing the simulated results with analytical models and calculations.

This book is about the study of a reservation procedure on a communication channel with a large round-trip time. The study is carried out via the mathematical analysis of a number of key performance models: The contention tree, the repairman model, the bulk service queue, and the tandem queue with shared service capacity. In Chap. 1, we have briefly touched upon the four key models that form the points of departure for this monograph. In this chapter, we give a more extensive introduction to these models and motivate their use within the context of a reservation procedure. Additionally, we give a brief introduction to the vast literature available and highlight some of the original contributions made in this book.

Contention trees constitute a popular class of algorithms to provide access to a shared resource for a random population of contenders. In particular, they can be used to transmit the request messages of a reservation procedure. In this chapter, we explore the basic properties of contention trees. The main original contribution of this chapter concerns our study of the delay experienced in the use of a contention tree. For this we introduce the notion of success instant. We give an approximation to the marginal empirical distribution of a success instant and show that this approximation is asymptotically exact for an increasing number of contenders.

In this chapter we extend the study of stand-alone contention trees to more practical settings. In such a setting, one must take into account that stations alternate between activity periods and idle periods, and the splitting procedure must be complemented with a channel access protocol to accommodate newcomers. We describe the standard algorithms to do this, free access and blocked access, and propose a novel mechanism: Scheduled blocked access.

The repairman model is used in Chap. 4 to approximate the request delay in a reservation procedure. In particular, the sojourn time in the repairman model with the Gated Random Order of Service (GROS) discipline is suggested as an approximation for the request delay, when blocked contention trees are used in a dynamic environment. Section 4.5 gives a heuristic approximation to the variance of the sojourn time under GROS. That approximation would be valid under overload conditions when the number of stations is large.

In Sect. 2.3 we proposed variants of the bulk service queue as models for the data-transmission phase of a reservation procedure. In this chapter we first focus on the classical bulk service queue and, in particular, on deriving characteristics of the stationary queue length distribution. The bulk service queue has a deeply rooted place in queueing theory and appeared throughout the twentieth century in a variety of applications. The work done on the bulk service queue runs to a large extent parallel to the maturing of queueing theory as a branch of mathematics. We therefore give an extensive description of the historical perspective in which the bulk service queue can be placed. Next, we give a detailed account of the methodology that can be applied to solve for the stationary queue length distribution. The methodology can be roughly categorised into three techniques: The generating function technique, random walk theory, and the Wiener-Hopf technique. Depending on the technique used, characteristics of the stationary distribution can be expressed in terms of either the roots of some equation, or infinite series that involve convolutions of some probability distribution. The three techniques cover the existing methodology to a large extent, both from the analytical and computational viewpoint. The historical overview is given in Sect. 6.1. We then present the generating function technique in Sect. 6.2, random walk theory in Sect. 6.3, and the Wiener-Hopf technique in Sect. 6.4.

For modelling data transfer organised via a reservation procedure, we proposed in Sect. 2.3 two models, referred to as fixed boundary model and flexible boundary model. For these models, time is divided into slots, and slots are grouped into frames. The fixed boundary model divides each frame into a fixed number of request and data slots. The flexible boundary model also uses this division, but additionally, the unused data slots (due to lack of data packets) are turned into request slots. For both models, we first consider the queue length at frame boundaries. The stationary queue length distribution in either model can be determined from a rather standard application of the generating function technique (demonstrated in Sect. 6.2 for the discrete bulk service queue). Due to the periodic scheduling, however, it is far less straightforward to analyse the stationary delay. By adopting a technique developed in Bruneel and Kim [28] and Kang and Steyaert [92], we succeed in deriving the probability generating function of the stationary delay.

Reservation procedures are often used on communication channels that are characterised by large round-trip times. As a consequence, a successful reservation must be separated in time from the corresponding data transmission. We propose a queueing model for this situation. Moreover, we investigate scheduling strategies: Strategies to divide the bandwidth between the request process and the data-transmission process. In particular, we consider ‘static’ scheduling and “adaptive’ scheduling.

In this chapter we investigate the two-stage tandem queue with coupled processors, which has been suggested as a model for a reservation mechanism in Sect. 2.4. It is assumed that jobs arrive at the first station according to a Poisson process and require service at both stations before leaving the system. The amounts of work that a job requires at each of the stations are independent, exponentially distributed random variables. When both stations are nonempty, the total service capacity is shared between the stations according to fixed proportions. When one of the stations becomes empty, the total service capacity is given to the nonempty station.

In Chap. 9 we have considered the two-stage tandem queue with coupled processors. We have shown that the pgf of the joint stationary queue length distribution can be found using the theory of boundary value problems.

Reservation procedures consist of two phases: A request phase and a data-transmission phase. In the previous chapters, we have proposed models for the delay in the request phase, see Chap. 4, and for the delay in the data-transmission phase, see Chaps. 7 and 8. Along the way, we have made some suggestions to improve the standard algorithms to schedule the reservation procedure.