8 - Discrete-Time Markov Chains

Summary

Let's review what we already know how to do at this point.

Closed Systems

For closed systems, we can approximate and bound the values of throughput, X, and the expected response time, E[R]. The approximations we have developed are independent of the distribution of service times of the jobs, but require that the system is closed. When the multiprogramming level, N, is much higher than N*, we have a tight bound on X and E[R]. Also, when N = 1, we have a tight bound. However, for intermediate values of N, we can only approximate X and E[R].

Open Systems

For open systems, we cannot do very much at all yet. Consider even a single queue. If we knew E[N], then we could calculate E[T], but we do not yet know how to compute E[N].

Markov chain analysis is a tool for deriving the above performance metrics and in fact deriving a lot more. It will enable us to determine not only the mean number of jobs, E[Ni], at server i of a queueing network, but also the full distribution of the number of jobs at the server.

All the chapters in Parts IV and V will exploit the power of Markov chain analysis. It is important, however, to keep in mind that not all systems can readily be modeled using Markov chains. We will see that, in queueing networks where the service times at a server are Exponentially distributed and the interarrival times of jobs are also Exponentially distributed, the system can often be exactly modeled by a Markov chain.