Chapter 6.3

GEOM(1)/GI/1 Waiting Time Distribution

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

The arriving customer stream is modeled by a Bernoulli process with Parameter $p=(1-\alpha)$, i.e. at each point on the discrete time line an arrival occurs with probability $p=(1-\alpha)$. Hence, the interarrival time $A$ is GEOM(1) distributed:

$ \displaystyle a(k) = (1-p)^{k-1} \cdot p = \alpha^{k-1} \cdot (1-\alpha) \;, \quad k = 1,2,\ldots, $ with $ \displaystyle E[A] = \frac{1}{p} = \frac{1}{1-\alpha} \;,$

The stability condition must be fulfilled, i.e.

$\rho = E[B]/E[A]<1$.

Z-Transform of Waiting Time

The Z-transform of the waiting time distribution in GEOM(1)/GI/1 system is obtained:

$ \displaystyle W_{ZT} (z) = \frac{(1-\rho) \cdot (1-z)} {1-\alpha z - (1 - \alpha) \; z \; B_{ZT} (z)} \;. $

This can be seen as the discrete-time form of the Pollaczek-Khintchine formula.

Waiting Time Distribution: Power Method

By means of the power method, we iteratively compute the waiting time distribution, until the distribution $W$ reaches the steady state.

$ \displaystyle w_{n+1} (k) = \pi_0 \Big(w_n (k) * b_n (k) * a_n (-k)\Big) = \pi_0 \Big(w_n (k) * c_n (k)\Big) $

The waiting time distribution of the $(n+1)$-st customer can be successively calculated from the waiting time distribution of the $n$-th customer. The interarrival and service time distributions can be chosen in a customer-dependent manner. This leads to an iterative algorithm for calculating the waiting time distribution of the GI/GI/1 system in time domain.

This can be expressed in terms of random variables:

$ \displaystyle W_{n+1} = \max(W_n+C,0) \quad \text{with } \; C = B-A $