Table of Contents
Question of the Day
Assigned Reading
Chapter 3.3 - 3.6.
Summary of Notation
| Notation | Meaning |
|---|---|
| N(t) | number of customers in the network at time t |
| Ni | number of customers in the network after the ith customer departs from the network |
| N | average number of customers in the network |
| D(t) | number of departures during the interval [0, t] |
| A(t) | number of arrivals during the interval [0, t] |
| Ai | number of arrivals during the service interval for the ith customer |
| U(X) | indicator function for random variable X |
| λ | average arrival rate into the network |
| 1/λ | average interarrival time between customers |
| τ | average interarrival time between customers |
| τi | interarrival time between customer i-1 and customer i |
| T | average time a customer spends in the network |
| μ | average service rate |
| 1/μ | average service time per customer |
| ρ | utilization; average fraction of time the server is busy; the probability that the server is busy at some randomly selected time |
| Nq | average number of customers waiting in the queue |
| W | average time a customer spends in the queue |
M/G/1 Queueing Systems
A queueing system that is M/G/1 states that the arrival process (i.e. distribution of interarrival times) is Poisson, denoted by M, the service distribution (i.e. the expected service time) is general, denoted by G, and there is a single server, denoted by 1. A Poisson arrival process implies that the interarrival times τi are independent and identically distributed with an exponential distribution and expected value 1/λ. A general service process implies that the service times Y(i) are independent and identically distributed with an unspecified distribution function and average service time 1/μ and variance of this service time σY2.
The results that follow apply to any single server queueing system with Poisson arrivals, independent and identically distributed service times, and a FCFS queueing discipline. The queueing system is in steady state if the utilization, ρ is less than 1.
Derivation of the P-K Formulas
For Poisson arrivals and steady state operation, the distribution function for the number of customers in a system is the same at any arbitrary point in time. As such, ρ = E[U(N(t))] = E[U(Ni)] = E[Ai+1], where Ai has the same distribution function for all i. This means we can drop the subscript and state that ρ = E[A].
Recall that Ni+1 = Ni - U(Ni) + Ai+1. If we square both sides of this equation, and take the expected values, we obtain:
Taking a closer look at each side of this expression, we can observe the following with respect to each term in the equation:
LHS and RHS Term 1
Steady state operation implies a distribution function of Ni that is the same for all i, thus:
RHS Term 2
which implies:
RHS Term 4
so:
RHS Term 5
The number of arrivals during the service interval depends only on the length of the service interval, not on Ni assuming that steady state RVs are independent of the arrival process. So Ai+1 is independent of Ni and U(Ni). So:
RHS Term 6
Similarly:
Putting it all Together
Furthermore, because the system has Poisson arrivals (i.e. memoryless) and is operating in steady state, the number of customers in the system does not depend on t. Thus:
This means we can write the original, complex expression more simply as:
where solving for N yields:
What about RHS Term 3?
We haven't solved for E[A2] though, which is the second moment of A. We know that the mean and variance of a random service time are known as 1/μ and σY2, respectively. So:
and:
So:
Since Y is itself a RV, we'll write the above expression more generally as:
But:
So:
We can the above into N, which we solved for earlier as:
which results in:
From Little's Law, we can relate N to λT as:
Let the coefficient of variation of the service time random variable be defined as:
Given this, we can rewrite:
as:
The P-K Formulas
The Pollaczek-Khinchine (P-K) mean-value formulas give the mean number (N) and mean time (T) as functions of utilization (ρ), arrival rate, and the first (1/μ) and second (σY2) moments of the service time.
M/G/1
For an M/G/1 queueing system, the P-K formulas are:
It can be observed that for a fixed λ and μ (and thus a fixed ρ), N and T increase linearly with σY2, the variance of the service time. Furthermore, N and T can be minimized if the service time is constant (i.e. deterministic), which implies σY2 = 0. Thus, there are two special cases of the M/G/1 queueing system:
- M/M/1
- M/D/1
M/M/1
For M/M/1, the arrival rate is Poisson with exponentially distributed interarrival times. The service times are exponentially distributed with mean 1/μ and σY2 = (1/μ)2.
Thus, from the M/G/1 P-K formulas, we can derive and simplify the formulas for an M/M/1 queueing system:
and:
So, the P-K formulas for an M/M/1 system are:
M/D/1
For M/D/1, the arrival rate is Poisson with exponentially distributed interarrival times. The service times are deterministic/fixed at 1/μ and σY2 = 0.
Thus, from the M/G/1 P-K formulas, we can derive and simplify the formulas for an M/D/1 queueing system:
Comparison of M/G/1 Queueing Systems
Average time in the system as a function of utilization
Average number in the system as a function of utilization
Contrast to D/D/1
For D/D/1 queueing systems, the P-K formulas do not apply.
