C - Markov Chains and Queues

Summary

At various points in the book, we use stochastic traffic and queueing models to represent the behavior of a network under conditions of random demand. These are based on Markov processes as well as some more general queueing models, which are summarized in this appendix. A readable and comprehensive treatment of these models may be found in [Kleinrock75].

Random Processes

Random processes, such as connection requests, contents of packet queues, and so forth, can be described as sequences of random variables, often called the states of the process, with state transitions occurring at successive (isolated) time points. (Between state transitions, the state remains constant.) In discrete state processes, the states take on discrete (typically integer) values, whereas in continuous state processes the states take on a continuum of values. For example, a discrete state process might be the length of a packet queue, whereas a continuous state process might be the random noise generated in an electrical circuit. In discrete time processes, the transitions are spaced regularly in time so that a complete description of the process is given by the state sequence alone. In continuous time processes, the transitions may occur randomly, at any point in time.

A realization of a random process is a specific sequence. In the case of discrete time processes, a realization is completely specified as a sequence of states. In continuous time processes, the transition times must also be specified.