Chapter 7.3

M/D/1 vs. nD/D/1 GI/GI/1 Waiting Time Distributions

(c) Tobias Hossfeld (Aug 2021)

This script and the figures are part of the following book. The book is to be cited whenever the script is used (copyright CC BY-SA 4.0):
Tran-Gia, P. & Hossfeld, T. (2021). Performance Modeling and Analysis of Communication Networks - A Lecture Note. Würzburg University Press.

On the example of the Internet of Things (IoT), the superposition of periodic traffic from $n$ sensor nodes is investigated yielding an nD/D/1 queueing system. Here, the Palm-Khintchine theorem may be applied to approximate the system with an M/D/1 queue. But the question arises, how large must $n$ be such that the aggregated IoT traffic may be properly (i.e. with negligible bias) approximated by a Poisson process?

In other wors: when $n$ is large enough a Poisson process (M/D/1) can be used instead of the aggregated periodic traffic (nD/D/1). This approximation is used for dimensioning an IoT load balancer which is the first point of the IoT cloud architecture where the individual traffic flows become aggregated. Such a load balancer is required to distribute the workload across the back-end servers. The difference of the waiting time distributions for the nD/D/1 and the approximating M/D/1 system are quantified.

System Description

Consider periodic traffic from $n$ asynchronous IoT sensors sending every time $\Delta t$. The processing times $B$ of the load balancer are constant, e.g. for computing hashes of the incoming packets. The deterministic service times have the following Laplace transform.

$ B \sim D(b)$ with $E[B]=b$ and $ \Phi_B(s) = e^{-s b}$

nD/D/1 Queue

The nD/D/1 waiting time has the following cumulative distribution function:

$ \displaystyle W(t) = 1-\!\!\!\sum_{k=\lceil t/b \rceil}^{n-1} \binom{n-1}{k}\left( \frac{kb-t}{\Delta t}\right)^k \left(1-\frac{kb-t}{\Delta t} \right)^{n-1-k} \frac{\Delta t-(n-1)\cdot b+t}{\Delta t -k \cdot b +t} $

The mean waiting time is based on the Erlang-B formula $B(n,a)$. For its computation, the iterative method is used. $ \displaystyle E[W]= \frac{(n-1)\rho b}{2 n\cdot B(n-2,n/\rho)} \\ B(0,a)=1 \;, \quad {B(n,a)} = \left(1 + \frac{n}{a\cdot B(n-1,a)} \right)^{-1} $

M/D/1 queue

The CDF of the waiting time in an M/D/1 system is

$ \displaystyle W(t) = (1-\lambda b) \sum_{k=0}^{\lfloor t/b\rfloor} \frac{(\lambda (k\cdot b - t))^k}{k!}e^{-(\lambda (k\cdot b - t))} \cdot $

Alternatively, the approach by Iversen is used for fast numerical computation of the CDF of the waiting times for M/D/1.

The mean of the waiting time follows from Takacs recursion with $E[B^2] = b^2$ or the Laplace transform $E[W] = - \frac{d}{ds}\Phi_W(s) |_{s=0}$.

$ \displaystyle E[W] = \frac{\lambda E[B^2]}{2(1-\rho)} = \frac{\rho b}{2(1-\rho)} $

Comparison of M/D/1 and nD/D/1 Waiting Times

Complementary cumulative distribution function of the waiting times for $n=500$, $b=1$, $\rho=\lambda b=0.9, \Delta t=n/\rho$ for an nD/D/1 and the corresponding M/D/1 system.

Comparison of Means

The mean waiting times are depicted for the nD/D/1 system depending on the number of nodes $n$ for different offered loads $\rho$ and $b=1$. The dashed lines indicate the corresponding M/D/1 system. The legend indicates which is the minimal number $n^*$ of nodes resulting in a relative error between the mean waiting times smaller than $\epsilon=2\%$.