How can I model overlapping service times in queueing model?

Question

Say there are two queues (1 and 2) in series.

The latency will be $t_1 + t_2$ without overlapping of their service times ($t_1$ and $t_2$ respectively).

If there is a overlapping, the latency will be $t_1 + t_2 - T_o$ where $T_o$ is the overlapped time. (Specifically $T_o = \min(t_1,t_2)$ in my case)

To my best understanding, queueing model is not suitable for modeling the overlapped service times. However, there would be some works for extension cause this overlapping is very common behavior, I believe.

How can I model overlapping service times in queueing model?

Answer 1

That's not in series. If their times are overlapping, they're not in series.

You mentioned that in your particular example, the latency is $t_1 + t_2 - \min(t_1,t_2)$. This quantity can be more cleanly expressed as $\max(t_1,t_2)$.

As a result, your queries are certainly not in series -- on the contrary, they are in parallel. And, there are clean and simple ways to model two queues in parallel.

In particular, assuming the queue times are independent and letting $t=\max(t_1,t_2)$, we have

$$\Pr[t \le x] = \Pr[t_1 \le x] \times \Pr[t_2 \le x].$$

Thus, the cumulative distribution function (CDF) for $t$ is the product of the CDF's for $t_1,t_2$. The CDF for a single queue is easy to compute given standard properties of the queue (e.g., it's easy to compute the CDF from the PDF).