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?


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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.