Classroom Exercise 14 Answers

Queues and Little's Laws

Fall 2017

A *two-stage pipeline* is a queueing system in which two
independent M/M/1 queues with processing rates
μ_{1} and μ_{2} are connected in series:

The input to the pipeline is a stream of requests
whose inter-arrival rate is λ.

- Recall that a single-queue system is in balance only
if λ/μ<1. Under what conditions is this two-queue
system in balance? Why?
*Answer:*We need both queues to behave, which means that we require both λ/μ_{1}< 1 and λ/μ_{2}< 1. - If a system is in balance, the output rate = the input rate.
But is it possible for a system to be in balance if the middle rate
in the above (between the two queues) does not match the input rate? Why?
*Answer:*Suppose the rates for the second and third edges are λ_{2}and λ_{3}. Since the second queue is in balance, λ_{3}must equal λ_{2}. But we also know that for the whole system to be in balance, λ_{3}must equal λ Thus λ_{2}must equal λ. - Recall that for a single M/M/1 queue, the average jobs in system
is p/(1-p), where p=λ/μ. What is the average waiting time
between request and response for the two-queue system above?
Hint: by Little's law, waiting time * arrival rate = jobs in system.
*Answer:*The wait time is the sum of the individual wait times, which is (for each queue) jobs in system / arrival rate. Thus the time for the composite system is p_{1}/(1-p_{1})/λ + p_{2}/(1-p_{2})/λ where p_{1}=λ/μ_{1}and p_{2}=λ/μ_{2}. - Suppose that we observe that average jobs in system for
μ
_{1}and μ_{2}are 3 and 4, respectively and that the wait time for a request to travel through the pipeline is 2 seconds. What is the average arrival rate λ?*Answer:*By Little's law, 3/λ + 4/λ = 2 seconds, so that λ = 7/2 = 3.5 requests per second. - (Advanced) We have seen that a two-rate source is equivalent to a single-rate source
whose (inter-arrival) rate is the sum. Is a two-queue pipeline with
task completion rates μ
_{1}and μ_{2}equivalent to a single M/M/1 queue with some task completion rate μ? Why or why not?*Answer:*No. We would have to have some μ depending upon μ_{1}and μ_{2}for which the total time in system p_{1}/λ(1-p_{1}) + p_{2}/λ(1-p_{2}) = p/λ(1-p), where p=λ/μ and p_{i}=λ/μ_{i}. A little algebra will convince you that any expression for μ contains λ, which means that it is impossible to choose a μ depending upon only μ_{1}and μ_{2}. - (Advanced) In class I have suggested that no real system satisfies
the queueing assumptions and that all queueing results are approximations.
I did not describe the kind of approximation. In particular, consider the M/M/1
result that the mean jobs in system are p/(1 - p), where p=λ/μ.
Given that inter-arrival times are not exponential, and processing is not memoryless, Is this figure too high or too low? Why?
*Answer:*We know that the way "real life" differs is that- Job processing is not independent, which increases processing time.
- Arrivals are not independent; there are flash crowds.