30-1©2011 Raj JainCSE567MWashington University in St. LouisIntroduction to Introduction to Queueing TheoryQueueing TheoryRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected]/Video recordings of this lecture are available at:http://www.cse.wustl.edu/~jain/cse567-11/30-2©2011 Raj JainCSE567MWashington University in St. LouisOverviewOverview Queueing Notation Rules for All Queues Little's Law Types of Stochastic Processes30-3©2011 Raj JainCSE567MWashington University in St. LouisQueueing Models: What You will learn?Queueing Models: What You will learn? What are various types of queues. What is meant by an M/M/m/B/K queue? How to obtain response time, queue lengths, and server utilizations? How to represent a system using a network of several queues? How to analyze simple queueing networks? How to obtain bounds on the system performance using queueing models? How to obtain variance and other statistics on system performance? How to subdivide a large queueing network model and solve it?30-4©2011 Raj JainCSE567MWashington University in St. LouisBasic Components of a QueueBasic Components of a Queue1. Arrivalprocess6. Servicediscipline2. Service timedistribution4. Waiting positions3. Number of servers30-5©2011 Raj JainCSE567MWashington University in St. LouisKendall Notation Kendall Notation A/S/m/B/K/SDA/S/m/B/K/SD A: Arrival process S: Service time distribution m: Number of servers B: Number of buffers (system capacity) K: Population size, and SD: Service discipline30-6©2011 Raj JainCSE567MWashington University in St. LouisArrival ProcessArrival Process Arrival times: Interarrival times: jform a sequence of Independent and Identically Distributed (IID) random variables Exponential + IID Poisson Notation: M = Memoryless = Poisson E = Erlang H = Hyper-exponential G = General Results valid for all distributions30-7©2011 Raj JainCSE567MWashington University in St. LouisService Time DistributionService Time Distribution Time each student spends at the terminal. Service times are IID. Distribution: M, E, H, or G Device = Service center = Queue Buffer = Waiting positions30-8©2011 Raj JainCSE567MWashington University in St. LouisService DisciplinesService Disciplines First-Come-First-Served (FCFS) Last-Come-First-Served (LCFS) Last-Come-First-Served with Preempt and Resume (LCFS-PR) Round-Robin (RR) with a fixed quantum. Small Quantum Processor Sharing (PS) Infinite Server: (IS) = fixed delay Shortest Processing Time first (SPT) Shortest Remaining Processing Time first (SRPT) Shortest Expected Processing Time first (SEPT) Shortest Expected Remaining Processing Time first (SERPT). Biggest-In-First-Served (BIFS) Loudest-Voice-First-Served (LVFS)30-9©2011 Raj JainCSE567MWashington University in St. LouisCommon DistributionsCommon Distributions M: Exponential Ek: Erlang with parameter k Hk: Hyper-exponential with parameter k D: Deterministic constant G: General All Memoryless: Expected time to the next arrival is always 1/regardless of the time since the last arrival Remembering the past history does not help.30-10©2011 Raj JainCSE567MWashington University in St. LouisExample Example M/M/3/20/1500/FCFSM/M/3/20/1500/FCFS Time between successive arrivals is exponentially distributed. Service times are exponentially distributed. Three servers 20 Buffers = 3 service + 17 waiting After 20, all arriving jobs are lost Total of 1500 jobs that can be serviced. Service discipline is first-come-first-served. Defaults: Infinite buffer capacity Infinite population size FCFS service discipline. G/G/1 = G/G/1/∞/∞/FCFS30-11©2011 Raj JainCSE567MWashington University in St. LouisGroup Arrivals/ServiceGroup Arrivals/Service Bulk arrivals/service M[x]:xrepresents the group size G[x]: a bulk arrival or service process with general inter-group times. Examples: M[x]/M/1 : Single server queue with bulk Poisson arrivals and exponential service times M/G[x]/m: Poisson arrival process, bulk service with general service time distribution, and mservers.30-12©2011 Raj JainCSE567MWashington University in St. LouisKey VariablesKey Variables12mPreviousArrival ArrivalBeginServiceEndServicew srnnqnsTime30-13©2011 Raj JainCSE567MWashington University in St. LouisKey Variables (cont)Key Variables (cont) Inter-arrival time = time between two successive arrivals. Mean arrival rate = 1/E[]May be a function of the state of the system, e.g., number of jobs already in the system. s = Service time per job. = Mean service rate per server = 1/E[s] Total service rate for m servers is m n = Number of jobs in the system. This is also called queue length. Note: Queue length includes jobs currently receiving service as well as those waiting in the queue.30-14©2011 Raj JainCSE567MWashington University in St. LouisKey Variables (cont)Key Variables (cont) nq= Number of jobs waiting ns= Number of jobs receiving service r = Response time or the time in the system = time waiting + time receiving service w = Waiting time = Time between arrival and beginning of service30-15©2011 Raj JainCSE567MWashington University in St. LouisRules for All QueuesRules for All QueuesRules: The following apply to G/G/m queues1. Stability Condition: < mFinite-population and the finite-buffer systems are always stable.2. Number in System versus Number in Queue:n = nq+ nsNotice that n, nq, and nsare random variables. E[n]=E[nq]+E[ns]If the service rate is independent of the number in the queue, Cov(nq,ns) = 030-16©2011 Raj JainCSE567MWashington University in St. LouisRules for All Queues (cont)Rules for All Queues (cont)3. Number versus Time: If jobs are not lost due to insufficient buffers, Mean number of jobs in the system = Arrival rate Mean response time4. Similarly, Mean number of jobs in the queue = Arrival rate Mean waiting timeThis is known as Little's law.5. Time in System versus Time in Queuer = w + sr, w, and s are random variables. E[r] = E[w] + E[s]30-17©2011 Raj JainCSE567MWashington University in St. LouisRules for All Queues(cont)Rules for All Queues(cont)6. If the service rate is independent of the number of jobs in the queue, Cov(w,s)=030-18©2011 Raj
View Full Document
Unlocking...