Quasi-Birth-and-Death Processes

The focus of this chapter is a special class of stochastic processes, the class of so-called quasi-birth-and-death (QBD) processes. From a modeler’s point of view, QBD processes are particularly interesting, as they combine a high degree of modeling expressiveness with efficient methods for the numerical analysis. On the one hand, QBD processes are closely related to conventional queueing systems and allow the specification of complex interarrival and service time distributions. Actually, their structure is general enough to reflect the underlying Markov chain of a stochastic Petri net, as will be shown later in Chapter 5. On the other hand, QBD processes are of Markovian nature, enabling the development of a number of very efficient solution algorithms. The first works on this class of stochastic processes appeared in the late 1960s, with the initial publications of Evans [66] and Wallace [194]. Since then, the interest in this class of stochastic processes has steadily increased, with the extensive treatment of Neuts [152] being one of the milestones which made them a widespread and fruitful research area.