We consider a system of two coupled queues, \$Q_1\$ and~\$Q_2\$. When both queues are backlogged, they are each served at unit rate. However, when one queue empties, the service rate at the other queue increases. Thus, the two queues are coupled through the mechanism for dynamically sharing surplus service capacity. We derive the asymptotic workload behavior at \$Q_1\$ for various scenarios where at least one of the two queues has a heavy-tailed service time distribution. First of all, we consider a situation where the traffic load at \$Q_1\$ is below the nominal unit service rate. We show that if the service time distribution at \$Q_1\$ is heavy-tailed, then the workload behaves exactly as if \$Q_1\$ is served in isolation at a constant rate, which only depends on the service time distribution at \$Q_2\$ through its mean. In addition, we establish that if the service time distribution at \$Q_1\$ is exponential, then the workload distribution is either exponential or semi-exponential, depending on whether the traffic load at \$Q_2\$ exceeds the nominal service rate or not. Next, we focus on a regime where the traffic load at \$Q_1\$ exceeds the nominal service rate, so that \$Q_1\$ relies on the surplus capacity from \$Q_2\$ to maintain stability. In that case, the workload distribution at \$Q_1\$ is determined by the heaviest of the two service time distributions, so that \$Q_1\$ may inherit potentially heavier-tailed characteristics from \$Q_2\$.

, , ,
,
CWI
CWI. Probability, Networks and Algorithms [PNA]
Stochastics

Borst, S.C, Boxma, O.J, & van Uitert, M.J.G. (2002). The asymptotic workload behavior of two coupled queues. CWI. Probability, Networks and Algorithms [PNA]. CWI.