This paper considers the subexponential asymptotics of the tail
distributions of virtual waiting times, actual waiting times and
sojourn times in stationary work-conserving single-server queues. To
this end, a single-server queue with a Markovian arrival stream (MAS)
is first examined, where arrivals are modulated by the underlying
Markov chain with finite states and service time distributions may
depend on the states of the underlying Markov chain immediately before
and after arrivals. Under the assumption that the equilibrium
distribution of the overall (i.e., customer-average) service time
distribution is subexponential, a subexponential asymptotic formula is
shown for the virtual waiting time distribution. Further when
customers are served on a FIFO basis, the actual waiting time and the
sojourn time distributions are shown to have the same asymptotics as
the virtual waiting time distribution. As you will see, a common
asymptotic constant of these three distributions is given only in
terms of the utilization factor. Therefore the same asymptotic
formulas hold in the FIFO G/G/1 queue as well, because MAS is dense in
stationary marked point processes.