Regenerative Simulation of Response Times in Networks of Queues

Abstract

A technique ~s presented for the estmaatton by simulation of response time characteristics of queuemg network models of multlprogrammed computer systems The techmque is based on the regenerative method for the simulation of stochastic systems and the ~dea of trackmg a marked job m the network Illustrative numencal results m part obtained from a simulation of a queuemg model of a database management system are reported KEY WORDS AND PHRASES, queuemg networks, regenerative method, stmulatton, statistical analysts of simulations CR CATEGORIES 5 5, 8 1, 8 3 1. Introduction Networks of queues have been widely used in computer system performance evaluation as models of the interaction between the processing and input-output resources of (multiprogrammed) systems and subsystems; see, e.g. Gaver [8], Lewis and Shedler [171, Buzen [3], Moore [18], and Lavenberg and Shedler [15]. Under the usual queueing-theoretic independent and identically (often exponentially) distributed service time assumptions, analyses based on a "numbers-in-queue" state space can be carried out (cf. Jackson [14], Baskett, Chandy, Muntz, and Palacios [1], and Relser and Kobayashl [191), yielding for stationary queue length distributions expressions that can be evaluated numerically. Obtainable from such analyses are measures of computer system performance derivable from the stationary queue length distributions such as device "utilizations" and job "throughput." Other measures of system performance (calculated as sums of queueing times) are the times, which we shall call passage times, for a job to traverse a portion of the network. In dosed networks certain passage times, complete circuits or loops, are often anterpretable in computer system models as job response times. Analyses based on the numbers-in-queue state space yield expected values for passage times, but do not yaeld other characteristics of interest such as percentiles or quantiles. Moreover alternative analyses to provide these characteristics are m general not available, and it as necessary to resort to samulation.