Summary of "Lec 40: M/G/1 Queues: Waiting Times and Busy Period"

Summary of "Lec 40: M/G/1 Queues: Waiting Times and Busy period"

This lecture focuses on the M/G/1 queueing system, extending previous discussions on semi-Markovian queues and the M/G/1 model. The main topics covered include the relationship between the number of customers in the system and waiting times, the distribution of waiting times, and the analysis of busy periods in the M/G/1 queue.

Main Ideas and Concepts

Recap of M/G/1 queue Basics:
- Previously derived the mean number in the system (mean value formula) without explicitly finding the stationary distribution.
- Established that system size distribution at departure epochs equals that at arbitrary time points.
- Results are given in transform form (probability generating functions (PGF) or Laplace transforms), which require specifying the service time distribution to get explicit distributions.
- For exponential service times, the M/G/1 reduces to M/M/1 with known results.
Relationship Between Number in System and Waiting Times:
- Little’s Law: \( L = \lambda W \), where \( L \) is the mean number in system and \( W \) is the mean waiting (sojourn) time.
- Question raised: Is there a relationship between higher-order moments (not just means) of the number in system and waiting times?
- Answer: Yes, there is a relationship expressed in terms of transforms, linking the distribution of system size and the distribution of waiting times.
Key Transform Relationship:
The PGF of the number in the system \( P(z) \) is related to the Laplace transform of the system waiting time \( F_T^*(s) \) by:

\( P(z) = F_T^*(\lambda (1 - z)) \)

This fundamental equation connects the distribution of the number of customers in the system with the distribution of waiting times.
Moments Relationship (Generalization of Little’s Law):
Differentiating the above relationship yields factorial moments of the number in the system in terms of raw moments of the waiting time:

\( L^{(k)} = \lambda^k \mathbb{E}[T^k] \)

where \( L^{(k)} \) is the \( k \)-th factorial moment of the number in the system and \( \mathbb{E}[T^k] \) is the \( k \)-th raw moment of the waiting time.
- For \( k=1 \), this reduces to Little’s Law.
- For \( k=2 \), it relates the second factorial moment of system size to the second moment of waiting time, providing a higher-order moment generalization.
Waiting Time Distribution in M/M/1 and M/G/1:
- In M/M/1, the waiting time distribution can be expressed as a mixture of convolutions of the exponential service time distribution, weighted by the probability of finding \( n \) customers upon arrival.
- The memoryless property of the exponential distribution simplifies analysis.
- In M/G/1, the lack of memoryless property requires a more general transform-based approach.
- The Laplace transform of the waiting time distribution \( F_T^*(s) \) can be expressed in terms of the Laplace transform of the service time distribution \( B^*(s) \):
\( F_T^*(s) = B^*(s) \frac{1 - \rho}{1 - \rho \frac{B^*(s)}{B^*(\lambda (1 - z))}} \)

This formula allows computation of waiting time distributions for general service time distributions.
Residual Service Time and Renewal theory:
- The residual (remaining) service time distribution plays a role in the waiting time distribution.
- Its Laplace transform \( R^*(s) \) can be expressed in terms of \( B^*(s) \), connecting Renewal theory results to queueing analysis.
Busy period Analysis:
- The Busy period is the continuous time interval during which the server is continuously busy, starting from an empty system.
- The Busy period distribution \( G(x) \) satisfies an integral equation involving the service time distribution and the arrival process.
- Its Laplace transform \( G^*(s) \) satisfies:
\( G^*(s) = B^*(s + \lambda - \lambda G^*(s)) \)
- This implicit equation relates the Busy period to the service time distribution.
- The mean Busy period length is:
\( \mathbb{E}[X] = \frac{1}{\mu - \lambda} \)

where \( 1/\mu \) is the mean service time.