Stochastic models of computer communication systems

F. P. Kelly

Journal of the Royal Statistical Society (Series B) 47 (1985) 379-395, with Discussion 415-428.

(Part of a Symposium on Stochastic Networks: other papers were by
I. Mitrani on "Response time problems in communication networks", and by
P. Whittle on "Scheduling and characterization problems for stochastic networks".)
Available from JSTOR, discussion on pages 415-428.

Citations, from Google Scholar.

Summary

This paper describes some examples of the stochastic models found useful in the design and analysis of advanced computer and communication systems. Our major theme might be termed the control of contention. As illustrations of this theme we discuss concurrency control procedures for databases, dynamic channel assignment for cellular radio, and random access schemes for the control of a broadcast channel. We emphasize asymptotic properties of product-form distributions and we present some new results on the stability of acknowledgement based random access schemes.

Keywords: concurrency control; database locking; dynamic channel assignment; cellular radio; random access schemes; product-form distributions.

Introduction

This paper is intended to describe to the Society some examples of the stochastic models found useful in the design and analysis of advanced computer and communication systems. The examples chosen are broadly concerned with what might be termed the control of contention, and an attempt has been made to provide enough of the technical background to motivate the models considered. In Section 2 we describe a probabilistic model, due to Mitra (1985), for conflicts among transactions in a database. Such conflicts can arise in distributed computer systems, where to ensure the consistency of a database it is often necessary to forbid the concurrent execution of transactions involving common items: a transaction must then contend with other transactions for access to the items it requires. Mitra (1985) has shown that his model can be used to answer some important design questions concerning concurrency control procedures which use exclusive and non-exclusive locks. Mitra's results are based upon a product-form solution; we indicate how his asymptotic formulae can be extended beyond the range of light traffic and the assumption of an unstructured database.

In Section 3 we discuss one of the many interesting problems which arise in connection with cellular radio. Cellular radio makes efficient use of a limited number of radio channels by allowing the repeated reuse of each channel in sufficiently separated spatial regions. The topic we consider is contention between different regions for the use of dynamically assigned channels. Everitt and Macfadyen (1983) have described an analytically tractable method of dynamic channel assigment, which they term the maximum packing strategy. Again a product form solution is involved: from this it is easy to obtain asymptotic formulae applicable in light traffic. These formulae establish the advantage of the strategy over a fixed channel assignment for low enough loss probabilities, but the advantage disappears as traffic and the number of channels increase. The real potential of dynamic schemes is their ability to cope automatically with traffic intensities which fluctuate in space and time.

We go to some lengths in Sections 2 and 3 to indicate relationships with work on random fields (Preston, 1976).

In Section 4 we discuss random access schemes for the control of a broadcast channel shared by a large number of users. This is an example of an increasingly important class of problem: high data rates and extensive parallel processing lead to distributed computer systems whose performance is often constrained by fundamental limitations (imposed by the speed of light) on how well the various components can coordinate their activity. We outline the results of Mikhailov (1979) and Hajek (1982a) on random access schemes using channel feedback, and we present some new results on the stability of acknowledgement based random access schemes.

Queueing network models have been used extensively in connection with packet-switching communication networks and time-shared multiprogrammed computer facilities. See Kleinrock (1976) for an introduction to this area, including an account of the role of models in the design of the ARPANET system, and Kelly (1979) and Gelenbe and Mitrani (1980) for further details of the models themselves. A major aim of these models has been to relate performance measures such as queue lengths, throughput and delays to the dimensioning of system components. The models considered in this paper have a rather different emphasis, their main aim being to provide insight into the mechanisms by which contention limits the performance of a system.

No attempt is made here to survey all the important probabilistic questions concerning the systems described: for a fuller perspective the reader is referred to Christodoulakis (1984) on database systems, Davis (1984) on cellular radio and Stuck (1984) on channel access methods. An indication of the enormous scope for probabilistic modelling in the design and analysis of computer communication systems can be found in the volumes edited by Disney and Ott (1982), Baccelli and Fayolle (1984), Iazeolla et al. (1984), Gelenbe (1984) and Gopinath (1985).

Frank Kelly's papers