Performance analysis

The design, development, tuning, and operation of computer and communication systems heavily rely on mathematical techniques which are usually indicated as performance analysis methods. The complexity of present-day data-handling facilities is such that brute-force simulation and hardware measurements are no longer effective for evaluating and predicting system performance. Accordingly, more sophisticated techniques for performance analysis have been developed, mostly starting from the formalism of a queueing network (stochastic process algebras and stochastic Petri nets are other formalisms that are being used for performance analysis).

A data-handling network can be seen as a collection of interconnected hardware and software resources that provide services to a community of users. The contention for resources leads to queues. The object of study can now be formulated as a network of service units with customers (jobs or messages) requiring services at those units. The nature of the arrival processes and of the service requests is usually such that they have to be represented as stochastic processes. Hence the main performance measures, like waiting times, workloads and queue lengths, are stochastic variables. Accordingly, the main techniques of performance analysis stem from probability theory. The performance analysis of the daily operation and capacity planning of computer- and communication systems also requires techniques from such areas as combinatorial optimization (scheduling) and stochastic control.

Until the 1960s, queueing theory had been almost exclusively concerned with single service facilities. But nowadays (1990s) the advent of packet- and message-switched communication networks, and of multi-programmed computer systems, require the study of networks of queues. Spurred by these applications, the theory of product-form networks was developed (cf. [a1]). For a small, but practically important, class of queueing networks, the joint steady-state distribution of the queue lengths $ X _ {1} \dots X _ {K} $ at the queues $ Q _ {1} \dots Q _ {K} $ was shown to have a product form:

$$ \tag{a1 } { \mathop{\rm Pr} } \{ X _ {1} = n _ {1} \dots X _ {K} = n _ {K} \} = \prod _ {i = 1 } ^ { K } f _ {i} ( n _ {i} ) , $$

$$ n _ {1} \dots n _ {K} = 0,1, \dots . $$

In the case of an open network (in which customers arrive and eventually disappear again), $ f _ {i} ( n _ {i} ) $ is the marginal queue length probability at $ Q _ {i} $: the queue lengths are independent. In the case of a closed network with $ N $ customers ( $ n _ {1} + \dots + n _ {K} = N $ in (a1)), the queue lengths are dependent. See [a3] for a discussion of these results and of efficient algorithms for evaluating performance measures in the case of a closed network; a key problem here is that the right-hand side of (a1) involves a normalizing constant which is determined by the condition that the sum of all $ \left ( \begin{array}{c} {N + K - 1 } \\ N \end{array} \right ) $ probabilities at the left-hand side should equal one.

The deep understanding that has been acquired for product-form networks and for other basic queueing models like the M/G/1-queue and Erlang's loss model (cf. Queue; Queue with refusals), has made queueing theory into a very effective tool for analyzing and predicting the performance of new services and systems. Successful examples are provided by virtual memory systems, local area networks, wireless communication systems, and, in recent years, by distributed systems, ISDN (Integrated Services Digital Networks), and mobile communications. For details concerning mathematical performance models and techniques, see the surveys [a2], [a4], [a5].

References

[a1]	F.P. Kelly, "Reversibility and stochastic networks" , Wiley (1979)
[a2]	L. Kleinrock, "Performance evaluation of distributed computer-communication systems" O.J. Boxma (ed.) R. Syski (ed.) , Queueing Theory and its Applications , North-Holland (1988) pp. 1–57
[a3]	"Computer performance modeling handbook" S.S. Lavenberg (ed.) , Acad. Press (1983)
[a4]	S.S. Lavenberg, "A perspective on queueing models of computer performance" O.J. Boxma (ed.) R. Syski (ed.) , Queueing Theory and its Applications , North-Holland (1988) pp. 59–94
[a5]	"Stochastic analysis of computer and communication systems" H. Takagi (ed.) , North-Holland (1990)