14 2. SINGLE QUEUES
n D T; (2.1)
where n is the average number of jobs at the queue (waiting and in service), and T is the
average time at the queue.
(b) If we view the waiting space alone as the system, then
L D W ; (2.2)
where L is the average number of jobs waiting for service, and W is the average waiting
time.
(c) If we view the single server alone as the system, then the average number of jobs at the
server is 1 Prob.1 job at the server/ C 0 Prob.no job at the server/ D
1
, so
D
where D Prob.1 job at the server/: (2.3)
A server is busy if and only if it is serving a job, so is a measure of server utilization.
Since T D W C
1
(waiting time plus service time), we have
n D T D
W C
1
D L C : (2.4)
As is a probability, D
requires that < , i.e., arrival rate is slower than service rate.
is is intuitive; if > , then jobs arrive faster than they can be served, the queue will grow
indefinitely, there is no steady state, and averages have no meaning.
What if D ? e answer depends on whether the inter-arrival and service times are
deterministic. Such details are specified by the notation we introduce next.
2.2 QUEUE SPECIFICATION
In the Kendall Notation A=S=K=B=N=d ,
A is the arrival process (e.g., M for memoryless, i.e., Poisson arrivals);
S is the service time distribution (e.g., D for deterministic, G for general);
K is the number of servers (possibly infinite);
B is the buffer capacity (including jobs in service; by default, B is infinity);
N is the job population size (by default, N is infinity);

Get Analytical Performance Modeling for Computer Systems, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.