Chapter 6

Discrete-time Analysis: Approximation of Continuous 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.

With the time-discrete analysis of GI/GI/1 delay systems, the distribution function of the waiting time can be determined numerically. Any continuous distributions can be approximated by discrete distributions. Using the example of the M/GI/1 waiting system, the exact waiting time (using Laplace transformation) is compared with the results of the time-discrete analysis. The finer the discretization $ \Delta t $, the more precise the time-discrete analysis. This parameter $ \Delta t $ should be played around in the notebook to see how this affects the accuracy of the numerical results.

The arrival process is a Poisson process with rate $ \lambda = 1 / E[A] $. The service time follows an Erlang-k distribution, $ B \sim E_k(\mu_i) $ with $ E[B] = 1 / \mu $. Each of the $ k $ phases of the Erlang-k distribution follows an exponential distribution with rate $ \mu_i = k \mu = k / E[B] $.

1. Continuous M/GI/1 Delay System

1.1 Definition of Parameters for Continuous M/GI/1 Delay System

The interarrival time $ A $ and the service time $ B $ are specified. In addition to the parameters of the distributions, the Laplace transform of the service time is also given and implemented as LT_B (s).

1.2 Laplace Transform of Waiting Time of Continuous M/GI/1

For an M/GI/1 system, the Laplace transform of the waiting time is as follows. The Laplace transform of the service time is required for the calculation:

$ LT \{b (t) \} = \Phi_B (s) $.

$ \displaystyle LT\{w(t)\} = \Phi_W(s) = \frac{(1-\rho)\cdot s}{s-\lambda+\lambda \Phi_B(s)}$

1.3 Numerical waiting time distribution: Inverse numerical Laplace transformation

The inverse numerical Laplace transform delivers the probability density function (PDF) of the waiting time

$LT\{w(t)\} = \Phi_W(s)$.

$w(t) = LT^{-1}\{\Phi_W(s)\}$

To calculate the cumulative distribution function (CDF), the inverse Laplace transform of $ \Phi_W (s) / s $ is calculated.

$ \displaystyle W(t) = LT^{-1}\{\frac{\Phi_W(s)}{s}\} $

The mpmath package can be used in Python for the inverse Laplace transform purpose. The function is called invertlaplace.

2. Discrete-time GI/GI/1 System

2.1 Discretization of the Continuous Distributions A and B

The probability $ P (A \leq t) = A (t) $ is calculated at the discrete places $ i \Delta t $ for $ i = 0,1, ..., a_\max $. Then the discrete distribution $ A_d $ is specified by the probabilities

$ a_d (i) = P (A_d = i) = A (i \cdot \Delta t) -A ((i-1) \cdot \Delta t) \quad $ for $\; 0 <i <a_\max $.

It is:

$a_d(0)=0 \\ a_d(a_\max) = 1-A\left((a_\max-1)\cdot \Delta t\right).$

Comparison of continuous and discrete interarrival time

The CDFs are plotted for the continuous interarrial time $A$ and the discretized interarrival time $A_d$.

Discrete Distribution of interarrival and service time

Note that the discreted exponential distribution yields a Geometric distribution with parameter $p=1-e^{-\lambda \Delta t}$.

$ \displaystyle A_d \sim \mathrm{GEOM}_1(1-e^{-\lambda \Delta t})$.

It is $ a_d(i+1) = A\big( (i+1) \Delta t\big) - A\big(i \Delta t\big) = e^{-\lambda i \Delta t} - e^{-\lambda (i+1) \Delta t} = e^{-\lambda i \Delta t}(1-e^{-\lambda \Delta t}) = (1-p)^i \cdot p $.

Remark: We could also arbitrarily define $a_d(i) = A\big( (i+1) \Delta t\big) - A\big(i \Delta t\big)$ yielding a GEOM$_0$ distribution with parameter $p$.

Discrete-time system function

The discrete-time system function is the difference of the random variables: $ C = B-A $. The distribution is calculated by convolution.

$ \displaystyle c (k) = b (k) * a (-k) $

2.2 Discrete-time Analysis of the M/GI/1 System

The waiting times of the (discretized) M/GI/1 are derived with the power method, until the difference of the waiting time distributions is below a threshold. For this purpose, the difference in the expected value of the waiting time in the iteration steps is computed and compared with a threshold value $ \epsilon $.

The expected value of the waiting time $ E [W_ {disc}] $ with the discrete-time analysis is compared with the exact value $ E [W] $ (for M / G / 1 waiting systems). In addition, Kingman's approximations for the expected value or an upper bound for the expected value are given.

Comparison of CDFs

The cumulative distribution function of the waiting time (through the time-discrete analysis and discretization of the distributions) is now compared with the exact solution (M/GI/1 and Laplace transformation). For lower values of $ \Delta t $, the results become more precise at the expense of more computational effort.

Additionally, the exact CDF of the M/M/1 system is plotted. You may play with the parameter $k$; for $k=1$, the script computes M/M/1, for $k>1$, we have the M/E$_k$/1 queue.