Report Number: CSL-TR-77-135
Institution: Stanford University, Computer Systems Laboratory
Title: Passage time distributions for a class of queueing networks: closed, open, or mixed,
Author: Yu, Philip S.
Date: March 1977
Abstract: Networks of queues are important models of multiprogrammed
time-shared computer systems and computer communication
networks. Although equilibrium state probabilities of a broad
class of network models have been derived in the past,
analytic or approximate solutions for response time
distributions or more general passage time distributions are
still open problems. In this paper we formulate the passage
time problem as a "hitting time" or "first passage time"
problem in a Markov system and derive the analytic solution
to passage time distributions of closed queueing networks.
Efficient numerical approximation is also proposed. The
result for closed queueing networks is further extended to
obtain approximate passage time distributions for open
queueing networks. Finally, we employ the techniques derived
in this paper to study the interfault time and response time
distribution and density functions of multiprogramming, size
of main memory, service time of paging devices and rate of
file I/O requests on the shape of distribution functions and
density functions have been examined.