The PH/PH/1 queue at epochs of queue size change

The PH/PH/1 queue is considered at embedded epochs which form the union of arrival and departure instants. This provides us with a new, compact representation as a quasi-birth-and-death process, where the order of the blocks is the sum of the number of phases in the arrival and service time distributions. It is quite easy to recover, from this new embedded process, the usual distributions at epochs of arrival, or epochs of departure, or at arbitrary instants. The quasi-birth-and-death structure allows for efficient algorithmic procedures. This revised version was published online in June 2006 with corrections to the Cover Date.