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.This paper introduces an order $m^2$ phase-type representation $(\kappa ,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 $(\kappa ,K,\nu )$ is also established for the number of type $\tau ?\{1,\dots ,m\}$ customers in the system, where a customer is of type $\tau$ if the phase in which it completes service belongs to $\tau$. We derive these results in both discrete and continuous time and also discuss the numerical procedure to compute $(\kappa ,K,\nu )$. 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).Finally, 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.