A matrix geometric representation for the queue length distribution of multitype semi-Markovian queues

In this paper we study a broad class of semi-Markovian queues introduced by Sengupta. This class contains many classical queues such as the GI/M/1 queue, SM/MAP/1 queue and others, as well as queues with correlated inter-arrival and service times. Queues belonging to this class are characterized by a set of matrices of size m and Sengupta showed that its waiting time distribution can be represented as a phase-type distribution of order m . For the special case of the SM/MAP/1 queue without correlated service and inter-arrival times the queue length distribution was also shown to be phase-type of order m , but no derivation for the queue length was provided in the general case. aper introduces an order m 2 phase-type representation ( κ , K ) for the queue length distribution in the general case and proves that the order m 2 of the distribution cannot be further reduced in general. A matrix geometric representation ( κ , K , ν ) is also established for the number of type τ ⊆ { 1 , … , m } customers in the system, where a customer is of type τ if the phase in which it completes service belongs to τ . We derive these results in both discrete and continuous time and also discuss the numerical procedure to compute ( κ , K , ν ) . When the arrivals have a Markovian structure, the numerical procedure is reduced to solving a Quasi–Birth–Death (for the discrete time case) or fluid queue (for the continuous time case). y, by combining a result of Sengupta and Ozawa, we provide a simple formula to compute the order m phase-type representation of the waiting time in a MAP/MAP/1 queue without correlated service and inter-arrival times, using the R matrix of a Quasi–Birth–Death Markov chain.