Approximate Computation of Sojourn Time Distribution in Open Queueing Networks

Varsha Mainkar, Kishor S. Trivedi and Andrew J. Rindos
Additional contact information
Varsha Mainkar: Duke University, Computer Science Department
Kishor S. Trivedi: Duke University, Electrical Engineering Department
Andrew J. Rindos: IBM, RTP

Chapter 37 in Computations with Markov Chains, 1995, pp 599-600 from Springer

Abstract: Extended Abstract The method of decomposition of queues has been widely used in solution of large and complex queueing networks for which exact solutions do not exist. We apply the basic paradigm of decomposition in computing approximations to the sojourn-time distribution in open queueing networks in which the service times and arrival processes are non-Markovian. For doing so we have made use of existing results on sojourn time distribution at a single queue. Using these, a queueing network is translated into a semi-Markov chain, whose absorption time distribution approximates the sojourn time distribution of the queueing network. However, the semi-Markov model does not represent the state of the queueing network (i.e., number of jobs at each queue). The state-space size of the semi-Markov models is thus linear in the number of queues in the network. This is achieved by having one state in the semi-Markov model corresponding to each queue in the queueing network, and one absorbing state to denote exit out of the network. The states are then connected together according to the topology of the network. The holding time distribution of a state is the sojourn time distribution at the corresponding queue. This sojourn time distribution must be computed by considering each queue in isolation. We approximate the arrival process to each queue to a phase-type arrival process, and then compute the sojourn time distribution assuming it is a PH/G/1 queue. Once we have the holding time distributions and the routing probability matrix, the absorption time distribution of the semi-Markov chain can be computed. The absorption time distribution approximates the sojourn time distribution of the queueing network.

Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4615-2241-6_37

Ordering information: This item can be ordered from
http://www.springer.com/9781461522416

DOI: 10.1007/978-1-4615-2241-6_37

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().