12.1 Introduction

The Achilles' heel of Markov models is their susceptibility to state space explosion. Even in simple models, where there are a fixed number of customers, where all customers are identical, and where the demands placed by each customer on each device are exponentially distributed, the number of states is given by the expression

where N is the number of customers and K is the number of devices. For small systems, such as the database server example in the previous chapter with N = 2 and K = 3, the number of states is 6. However, in a moderate sized office network with, say, 25 users and 25 workstations, the number of states is more than 63 trillion. With 50 users and 50 workstations, the number of states is over 5 x 10²⁸. Since there is one linear equation (i.e., equating flow into the state to the flow out of the state) for every state, solving such a large number of simultaneous equations is infeasible.

However, the good news is that clever algorithms have been developed for a broad class of useful Markov models that do not require the explicit solution to a large number of simultaneous equations. One such technique is Mean Value Analysis (MVA). Instead of solving a set of simultaneous linear equations to find the steady state probability of being in each system state, from which performance metrics (e.g., system throughput, device utilizations, user response times) can be derived, MVA is a simple recursion. MVA calculates the performance metrics directly for a given number of customers, knowing only the performance metrics when the number of customers is reduced by one. The recursion is intuitive, efficient, and elegant. The majority of commercially viable performance evaluation packages owe their success to MVA. Its impact on the field of analytical performance evaluation has been huge.

In this chapter, MVA is reconstructed from first principles and presented in its simplest form. All of the N customers are assumed to be (statistically) identical, forming a single class of customers. Each of the K devices is assumed to be load independent, meaning that the device neither speeds up nor slows down depending upon the number of customers at the device. Finally, the demand that a customer places on a device (i.e., the service required by a customer at a particular device) is assumed to be exponentially distributed. There are enhancements to MVA that remove each of these restrictions (i.e., allowing multi-class customers, allowing load dependent servers, and allowing non-exponential service), but presenting such extensions is not the purpose of this chapter. Rather, the desire is for an appreciation of and an intuitive, working understanding of MVA.

This chapter is example based. In Section 12.2, the database server example from previous chapters is extended and used to develop and illustrate the basic MVA algorithm. A concise, algorithmic description of MVA is given in Section 12.3. The special case of balanced systems is presented in Section 12.4. Section 12.5 describes extensions and limitations associated with MVA. The chapter concludes with a summary and relevant exercises.