CPE 619 Introduction to Queuing TheoryOverviewQueueing Models: What Will You Learn?Basic Components of a QueueKendall Notation A/S/m/B/K/SDArrival ProcessService Time DistributionService DisciplinesCommon DistributionsExample: M/M/3/20/1500/FCFSGroup Arrivals/ServiceKey VariablesKey Variables (cont’d)Slide 14Rules for All QueuesRules for All Queues (cont’d)Slide 17Little's LawProof of Little's LawApplication of Little's LawExample 30.3Stochastic ProcessesTypes of Stochastic ProcessesDiscrete/Continuous State ProcessesMarkov ProcessesBirth-Death ProcessesPoisson ProcessesPoisson Processes (cont’d)Poisson Process (cont’d)Relationship Among Stochastic ProcessesSummaryAnalysis of A Single QueueSlide 33Slide 34Birth-Death Processes (cont’d)Theorem: State ProbabilityProofProof (cont’d)Slide 39Slide 40Slide 41M/M/1 QueueResults for M/M/1 QueueResults for M/M/1 Queue (cont’d)Slide 45Slide 46Slide 47Slide 48Slide 49Example 31.2Example 31.2 (cont’d)Slide 52Slide 53M/M/m QueueHomework #7CPE 619Introduction to Queuing TheoryAleksandar MilenkovićThe LaCASA LaboratoryElectrical and Computer Engineering DepartmentThe University of Alabama in Huntsvillehttp://www.ece.uah.edu/~milenkahttp://www.ece.uah.edu/~lacasa2OverviewQueueing NotationRules for All QueuesLittle's LawTypes of Stochastic Processes3Queueing Models: What Will You 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?4Basic Components of a Queue1. Arrival process6. Service discipline2. Service time distribution4. Waiting positions3. Number of servers5. Customer PopulationExample: students at a typical computer terminal roomwith a number of terminals. If all terminals are busy,the arriving students wait in a queue.5Kendall Notation A/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 discipline6Arrival ProcessArrival times: Interarrival times: j form a sequence of Independent and Identically Distributed (IID) random variablesThe most common arrival process: Poisson arrivalsInter-arrival times are exponential + IID  Poisson arrivalsNotation:M = Memoryless = PoissonE = ErlangH = Hyper-exponentialG = General Results valid for all distributions7Service 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 positions8Service 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)9Common 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 help10Example: M/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:(Only the first 3 parameters are sufficient to indicate the type)Infinite buffer capacityInfinite population sizeFCFS service discipline G/G/1 = G/G/1/1/1/FCFS11Group Arrivals/ServiceBulk arrivals/serviceM[x]: x represents 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 m servers12Key Variables12mPreviousArrival ArrivalBeginServiceEndService w srnnqns Time13Key Variables (cont’d) 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 queue14Key Variables (cont’d)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 service15Rules for All QueuesRules: The following apply to G/G/m queues1. Stability Condition:  < mFinite-population and the finite-buffer systems are always stable2. Number in System versus Number in Queue:n = nq+ nsNotice that n, nq, and ns are random variables. E[n]=E[nq]+E[ns]If the service rate is independent of the number in the queue, Cov(nq,ns) = 016Rules for All Queues (cont’d)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 Queue r = w + sr, w, and s are random variablesE[r] = E[w] + E[s]17Rules for All Queues (cont’d)6. If the service rate is independent of the number of jobs in the queue, Cov(w,s)=018Little's LawMean number in the system = Arrival rate  Mean response time This relationship applies to