Queuing Theory1Queuing TheoryQueuing Theory• Queuing theory is the mathematics of waiting lines.• It is extremely useful in predicting and evaluating system performance.• Queuing theory has been used for operations research. Traditional queuing theory problems refer to customers visiting a store, analogous to requests arriving at a device.Long Term Averages• Queuing theory provides long term average values.• It does not predict when the next event will occur.• Input data should be measured over an extended period of time.• We assume arrival times and service times are random.Assumptions• Independent arrivals• Exponential distributions• Customers do not leave or change queues.• Large queues do not discourage customers.Many assumptions are not always true, but queuing theory gives good results anywayQueuing ModelSTqTwWQλInteresting Values• Arrival rate (λ) — the average rate at which customers arrive. • Service time (s) — the average timerequired to service one customer. • Number waiting (W) — the average number of customers waiting.• Number in the system (Q) — the average total number of customers in the system.Queuing Theory2More Interesting Values• Time in the system (Tq) the average time each customer is in the system, both waiting and being serviced.• Time waiting (Tw) the average time each customer waits in the queue.Tq = Tw + sArrival Rate• The arrival rate, λ, is the average rate new customers arrive measured in arrivals per time period. Common units are access/second• The inter-arrival time, a, is the average time between customer arrivals. It is measured in time per customer. A common unit would be seconds/access.a = 1 / λRandom Values• We assume that most of the events we are interested in occur randomly.– Time of a request to a device– Time to service a request– Time user makes a request• Although events are random, we may know the average value of the times and their distribution.• If you flip a coin, you will get heads 50% of the time.Exponential Distribution• Many of the random values are exponentially distributed.Frequency of Occurrence = e-t• There are many small values and a few large values.• The inter-arrival time of customers is naturally exponentially distributed.Exponential Distribution00.10.20.30.40.50.60.70.80.9100.511.522.533.544.55Poisson Arrival Rate If customers are arriving at the exponentially distributed rate λ, then the probability that there will be k customers after time t is: tkkekttPλλ−=!)()(Queuing Theory3Math Notes0! = 1! = 1X0= 1X1= XPoisson Example• A networked printer usually gets 15 print jobs every hour. The printer has to be turned off for 10 minutes for maintenance. What is the probability that nobody will want to use the printer during that time?Poisson Solution• A networked printer usually gets 15 print jobs every hour. The printer has to be turned off for 10 minutes for maintenance. What is the probability that nobody will want to use the printer during that time?• The arrival rate is 15/60 = 0.25 jobs/min.082.0!0)10*25.0()10(10*25.000==−ePExpected Number of ArrivalsIf customers are arriving at the exponentially distributed rate λ, how many customers should you expect to arrive in time t?Expected = λ * tFor the printer problem with an arrival rate λ = 0.25, in 10 minutes we should expect 2.5 jobs to arriveQueuing ModelsQueuing systems are usually described by three values separated by slashesArrival distribution / service distribution / # of serverswhere:•M = Markovian or exponentially distributed •D = Deterministic or constant.•G = General or binomial distributionCommon Models• The simplest queuing model is M/M/1where both the arrival time and service time are exponentially distributed.•The M/D/1 model has exponentially distributed arrival times but fixed service time.•The M/M/n model has multiple servers.Queuing Theory4Why is there Queuing?• The arrivals come at random times.• Sometimes arrivals are far apart. Sometimes many customers arrive at almost the same time. When more customers arrive in a short period of time than can be serviced, queues form.• If the arrival rate was not random, queues would not be created.Utilization• Utilization (represented by the Greek letter rho, ρ) is the fraction of time the server is busy.• Utilization is always between zero and one0 ≤ρ≤1• If a bank teller spends 6 hours out of an 8 hour day counting money, her utilization is 6/8 = 0.75Calculating Utilization• Utilization can be calculated from the arrival rate and the service time.s*λρ=It is important that the units of both the arrival rate and the service time be identical. It may be necessary to convert these values to common units.Little’s Formula• The number in the system is equal to the arrival rate times the average time a customer spends in the system.Q = λ * Tq• This is also true for just the queue.W = λ * TwM/M/1 FormulasTqs=−1ρρρ−=1QTws=−ρρ1ρρ−=12WApplication of Little’s Formula• Multiplying the formulas on the left by λgives the formula on the right.QsTq =−=−=ρρρλλ11Queuing Theory5024681012141618200 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1UtilizationTqSolution Process1. Determine what quantities you need to know.2. Identify the server3. Identify the queued items 4. Identify the queuing model 5. Determine the service time 6. Determine the arrival rate 7. Calculate ρ8. Calculate the desired values Example• Consider a disk drive that can complete an average request in 10 ms. The time to complete a request is exponentially distributed. Over a period of 30 minutes, 117,000 requests were made to the disk. How long did it take to complete the average request?What is the average number of queued requests?Solution• Determine what quantities you need to know.– The average request time is Tq– The number of queued jobs is W• Identify the server– The disk drive is the server• Identify the queued items – Disk requests• Identify the queuing model – M/M/1Solution (cont.)• Determine the service time S = 10 ms = 0.01 sec / request• Determine the arrival rate λ = 117,000 request / (30 min * 60 sec/min) = 65 requests / sec• Calculate ρρ = λ*s = 0.01 sec/request * 65 req/sec = 0.65Solution (cont.)• Time to complete the average requestmssTQ6.2865.0101.01=−=−=ρThe average length of the queue21.165.0165.0122=−=−=ρρWQueuing Theory6Number in the