Lecture Notes for Simulation

25 April 2005 - Queue Theory

Outline

Queues

• Queues are buffers to smooth out differences in arrival rates and service times.

Queue Theory and Simulation

• Well understood, closed-form queue-theoretic models can be used to speed up simulations.

  • Replace portions of a simulation with queueing calculations.

• Realistic queue models quickly be come intractable.

  • Deriving results from such models requires simulation.

Queue Characteristics

• A queue can be characterized along several dimensions:

  • Customer behavior in the queue, including the distribution of arrival times and balking behavior.

  • Server behavior, including the distribution of service times and queue-dependent behavior (such as triage or shorter service times).

  • Customer selection, including FIFO, LIFO, and priority selection.

  • The system capacity, mainly in the queue, but also in the server.

  • The number of queues and servers, and the relation between them.

Queue Characterization

• A queue can be characterized by a five-tuple A/B/C/D/E where

  • A is the inter-arrival-time distribution and has typical values M for exponential, D for deterministic, E_k for type-k Erlang, and G for general.

  • B is the service-time distribution and uses the same values as does A.

  • C is the number of servers.

  • D is the system capacity in customers.

  • E is the queue discipline, including FIFO, LIFO, SIRO (service in random order), PRI (priority), and GD (general discipline).

• For example the M/M/1/inf/FIFO queue has exponential arrival and service times, a single server, an infinite-capacity queue, and FIFO customer selection.

• The queue characterization is often abbreviated as a three-tuple A/B/C with D assumed to be 1 and E assumed to be irrelevant.

Questions About Queues

• Queueing systems are analyzed to determine

  • Queue length in customers, usually the maximum or average value.

  • Customer time in system.

    • Determining how this is defined can be tricky.

  • Server idle (or busy) time, also known as utilization.

Exponential and Poisson Distributions

• The exponential and Poisson distributions are the basis for many successful queueing models.

• Underlying assumptions:

  • Given an the arrival rate l, the probability that a customer arrives in a small interval t is lt plus higher-order terms.

  • The probability of more than one arrival in t is ignorably small.

  • Arrivals in non-overlapping time intervals are independent.

The Exponential-Poisson Relation

• The exponential and Poisson distributions are essentially the inverse of one another.

  • A Poisson distribution gives the number of customers arriving in a time interval.

  • An exponential distribution gives the amount of time between successive customers.

• Given a Poisson distribution with arrival rate l and the random variable T equalling the time between successive arrivals,
  P(T > t) = P(zero arrivals at t) = e^-lt

  from which

  F(t) = P(T <= t) = 1 - P(T > t) = 1 - e^-lt

Distribution Properties

• The exponential distribution is memoryless.

  • Arrivals in an interval are not effected by the results of earlier intervals.

  • P(X <= X₂ | X >= X₁) = P(0 <= X <= X₂ - X₁)

• The Poisson distribution is closed under aggregation and disaggregation.

  • n independent Poisson processes sum to a Poisson process.

    • The result process has arrival rate l₁ + ... + l_n.

    • l_i is the arrival rate of the ith constituent process.

  • A Poisson process divides into n independent Poisson processes.

    • Each has an arrival rate of lp_i

      • The original process has arrival rate l.

      • p_i is the probability of dividing to process i.

M/M/1/inf/FIFO Queues

• A queue with 1/l arrival parameter and 1/u service parameter.

• The number of customers in the system at time t with j existing customers is

  P0'(t) = -lP0(t) + uP1(t)	for j = 0
  Pj'(t) = lPj - 1(t) - (l + u)Pj(t) + uPj + 1(t)	for j > 0)

  • In the steady state, the equations are:

    P1 = l/uP0	for j = 0
    Pj + 1 = ((l + u)/u)Pj - (l/u)Pj	for j > 0)

  • The steady-state equations can be unrolled into the closed-form solution
    P_j = r_j(1 - r)

    where r = (l/u).

Expected Number of Clients

• Let random variable X equal the number of clients in the system.

  • What is X's expected value?

• E[X] = r/(1 - r) = l/(u - l) = L

Expected Queue Length

• Let random variable Q equal the number of waiting clients.

  • What is Q's expected value?

• E[Q] = L - r = r/(1 - r) - r = r²/(1 - r) = l²/u(u - l) = L_q

Expected Total Time

• The average time in the system can be determined by Little's formula
  L = lW

  where L is the expected number in the system, l is the arrival rate, and W is the expected total time.

  Rearranging gives

  W = L/l

  and substituting for L gives

  W = (l/(l - u))/l = 1/(l - u)

Expected Queue Time

• The average waiting time in the queue is related to the total waiting time by
  W = W_q + 1/u

  which can be rearranged to give

  W_q = W - 1/u

  W is 1/(u - l), giving

  W_q = 1/(u - l) - 1/u = l/(u(u - l))

• Little's formula also relates queue length to queue-wait time:
  L_q = lW_q

Example M/M/1/inf/FIFO Queue

• A system has five sources feeding a single concentrator.

  l1 = 2 msg/min l2 = 0.5 l3 = 1 l4 = 1 l5 = 3.5 Average service time is 4 sec/msg. Infinite buffering.

• By aggregation the overall arrival rate is
  l = l₁ + l₂ + l₃ + l₄ + l₅ = 2 + 0.5 + 1 + 1 + 3.5 = 8 msg/min.

• The service rate is u = (60 sec/min)/(4 sec/msg) = 15 msg/min.

• Utilization is r = l/u = (8 msg/min)/(15 msg/min) = 0.53.

Example Calculations

• In the steady state, the probability of less than five messages in the system is

  P(X < 5)	=	P(X = 0) + P(X = 1) + P(X = 2) + P(X = 3) + P(X = 4)
  	=	P0 + P1 + P2 + P3 + P4
  	=	(1 - r) + (1 - r)r + (1 - r)r2 + (1 - r)r3 + (1 - r)r4
  	=	(1 - r)(1 + r + r2 + r3 +r4
  	=	.47(2.386)
  	=	.9581

• The expected number of customers in the system is
  L = r/(1 - r) = 0.53/(1 - 0.53) = 1.13

• The average number of messages buffered in the system is
  L_q = r²/(1 - r) = 0.53²/(1 - 0.53) = 0.6

• The average time spent by each message in the system is
  W = 1/(u - l) = 1/(15 - 8) = 1/7 = 0.14 min = 8.6 sec.

• The average time spent by each message in the buffer is
  W = l/(u(u - l)) = 8/15(7) = 0.07 min = 4.6 sec.

Finite Queues

• M/M/1/K/FIFO queues are similar to M/M/1/inf/FIFO queues.

  • The k+1th customer is denied entry into the system.

Points to Remember

This page last modified on 25 April 2005.