Tandem Queues with Identical Service Times in Heavy Traffic

A queueing network consists of several nodes where at each node there is a server and a queue; jobs pass through the network receiving a random amount of service at each node. In classical Jackson networks, a particular job’s random service requirements at each node are independent of one another. This independence enables the computation of various steady-state performance measures and scaling limits.

The independence assumption may not be very realistic, however. Consider instead a queueing network where, although service times are random, any particular job has identical service times at each server. In this situation much dependence is introduced and many classical results break down. Even for the simplest example of a two-node tandem queue, very little is known. In seminal work on this model, Boxma [4] found the steady state distribution for the workload in the second queue at special time-points, in the case arrivals are Poisson. The workload is the amount of time a newly arriving job would need to wait for service to begin and represents one of the most important measures of congestion in a queueing system. For the basic two-node model, the complicated dependencies exist only in the second queue. To expand on Boxma’s result, we study the entire workload process in the second queue of the two-node tandem system. Unfortunately, this process does not converge under the same scaling as the workload in the first queue. To handle this, we introduce and study a related process M, called the plateau process, which encodes most of the information in the workload process. We show that under appropriate scaling, workload in the first queue converges, and although the workload in the second queue does not converge, the plateau process does converges to a limit M∗ that is a certain function of two independent Levy processes.

Although the aforementioned result gives a characterization of the long term dynamics of workload in the second queue, it is difficult to compute distributional quantities from this characterization explicitly. To this end, we find the one dimensional distribution of the plateau process on a certain subsequence of special time points, similar to Boxma’s approach. For this more detailed analysis we restrict to the case of exponential interarrival times and regularly varying service times with infinite variance.