Introduction To Queueing Theory

2y ago
14 Views
5 Downloads
393.42 KB
41 Pages
Last View : 20d ago
Last Download : 2m ago
Upload by : Warren Adams
Transcription

Introduction toQueueing TheoryRaj JainWashington University in Saint LouisJain@eecs.berkeley.edu or Jain@wustl.eduA Mini-Course offered at UC Berkeley, Sept-Oct 2012These slides and audio/video recordings are available on-line at:http://amplab.cs.berkeley.edu/courses/queueand http://www.cse.wustl.edu/ jain/queueUC Berkeley, Fall 2012 2012 Raj Jain30-1

OverviewQueueing Notation Rules for All Queues Little's Law Types of Stochastic Processes UC Berkeley, Fall 2012 2012 Raj Jain30-2

Basic Components of a Queue1. Arrivalprocess5. Population Size6. Servicediscipline4. WaitingpositionsUC Berkeley, Fall 20122. Service timedistribution3. Number ofservers 2012 Raj Jain30-3

Kendall Notation A/S/m/B/K/SD A: Arrival processS: Service time distributionm: Number of serversB: Number of buffers (system capacity)K: Population size, andSD: Service disciplineUC Berkeley, Fall 2012 2012 Raj Jain30-4

Arrival Process Arrival times:Interarrival times: j form a sequence of Independent and Identically Distributed(IID) random variablesNotation: M Memoryless Exponential E Erlang H Hyper-exponential D Deterministic constant G General Results valid for all distributionsUC Berkeley, Fall 2012 2012 Raj Jain30-5

Service Time Distribution Time each student spends at the terminal.Service times are IID.Distribution: M, E, H, D, or GDevice Service center QueueBuffer Waiting positionsUC Berkeley, Fall 2012 2012 Raj Jain30-6

Service Disciplines First-Come-First-Served (FCFS)Last-Come-First-Served (LCFS) Stack (used in 9-1-1 calls)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 delayShortest 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)UC Berkeley, Fall 2012 2012 Raj Jain30-7

Example M/M/3/20/1500/FCFS Time between successive arrivals is exponentially distributed.Service times are exponentially distributed.Three servers20 Buffers 3 service 17 waitingAfter 20, all arriving jobs are lostTotal 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/ / /FCFSUC Berkeley, Fall 2012 2012 Raj Jain30-8

Quiz 30AKey: A/S/m/B/K/SDTF The number of servers in a M/M/1/3 queue is 3 G/G/1/30/300/LCFS queue is like a stack M/D/3/30 queue has 30 buffers G/G/1 queue has population size D/D/1 queue has FCFS discipline UC Berkeley, Fall 2012 2012 Raj Jain30-9

Exponential Distribution 1Probability Density Function (pdf):a1 x/af(x)f (x) eaCumulative DistributionZ xFunction (cdf):1F (x) P (X x) f (x)dx 1 e x/aF(x)0Mean: axxVariance: a2Coefficient of Variation (Std Deviation)/mean 1Memoryless: Expected time to the next arrival is always a regardless ofthe time since the last arrival Remembering the past history does not help.UC Berkeley, Fall 2012 2012 Raj Jain30-11

Erlang Distribution 1 Sum of k exponential random variablesSeries of k servers with exponential service timeskXX xi where xi exponentialki 1 Probability Density Function (pdf):xk 1 e x/af (x) (k 1)!ak Expected Value: akVariance: a2kCoV: 1/ k UC Berkeley, Fall 2012 2012 Raj Jain30-12

Hyper-Exponential Distribution The variable takes ith value with probability pix1x x2 xmxi is exponentially distributed with mean aiHigher variance than exponentialCoefficient of variation 1UC Berkeley, Fall 2012 2012 Raj Jain30-13

Group Arrivals/Service Bulk arrivals/serviceM[x]: x represents the group sizeG[x]: a bulk arrival or service process with general inter-grouptimes.Examples: M[x]/M/1 : Single server queue with bulk Poisson arrivalsand exponential service times M/G[x]/m: Poisson arrival process, bulk service withgeneral service time distribution, and m servers.UC Berkeley, Fall 2012 2012 Raj Jain30-14

Quiz 30BExponential distribution is denoted as distribution represents a set of parallelexponential servers Erlang distribution Ek with k 1 is same asdistribution UC Berkeley, Fall 2012 2012 Raj Jain30-15

Key Variables12 mnqPreviousArrivalTimensBeginEndService ServiceArrival n wsrUC Berkeley, Fall 2012 2012 Raj Jain30-17

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 serviceas well as those waiting in the queue.UC Berkeley, Fall 2012 2012 Raj Jain30-18

Key Variables (cont) nq Number of jobs waitingns Number of jobs receiving servicer Response time or the time in the system time waiting time receiving servicew Waiting time Time between arrival and beginning of serviceUC Berkeley, Fall 2012 2012 Raj Jain30-19

Rules for All QueuesRules: The following apply to G/G/m queues1.Stability Condition: Arrival rate must be less than service rate m Finite-population or finite-buffer systems are always stable.Instability infinite queueSufficient but not necessary. D/D/1 queue is stable at λ μ2. 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) 0UC Berkeley, Fall 2012 2012 Raj Jain30-20

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]UC Berkeley, Fall 2012 2012 Raj Jain30-21

Rules for All Queues(cont)6. If the service rate is independent of the number of jobs in thequeue,Cov(w,s) 0UC Berkeley, Fall 2012 2012 Raj Jain30-22

Quiz 30CIf a queue has 2 persons waiting for service, thenumber is system is If the arrival rate is 2 jobs/second, the mean interarrival time is second. In a 3 server queue, the jobs arrive at the rate of 1jobs/second, the service time should be less thansecond/job for the queue to be stable. UC Berkeley, Fall 2012 2012 Raj Jain30-23

Little's Law Mean number in the system Arrival rate Mean response timeThis relationship applies to all systems or parts of systems inwhich the number of jobs entering the system is equal to thosecompleting service.Named after Little (1961)Based on a black-box view of the system:Arrivals BlackBoxDeparturesIn systems in which some jobs are lost due to finite buffers, thelaw can be applied to the part of the system consisting of thewaiting and serving positionsUC Berkeley, Fall 2012 2012 Raj Jain30-25

Proof of Little's Law4 ArrivalJob 3number21Departure4Number 3in2System112345678Time 12345678TimeIf T is large, arrivals departures NArrival rate Total arrivals/Total time N/THatched areas total time spent inside thesystem by all jobs JMean time in the system J/NMean Number in the system J/T Arrival rate Mean time in the systemUC Berkeley, Fall 201230-264Time 3in2System11 2 3Job number 2012 Raj Jain

Application of Little's LawArrivals DeparturesApplying to just the waiting facility of a service centerMean number in the queue Arrival rate Mean waiting timeSimilarly, for those currently receiving the service, we have:Mean number in service Arrival rate Mean service timeUC Berkeley, Fall 2012 2012 Raj Jain30-27

Example 30.3 A monitor on a disk server showed that the average time tosatisfy an I/O request was 100 milliseconds. The I/O rate wasabout 100 requests per second. What was the mean number ofrequests at the disk server? Using Little's law:Mean number in the disk server Arrival rate Response time 100 (requests/second) (0.1 seconds) 10 requestsUC Berkeley, Fall 2012 2012 Raj Jain30-28

Quiz 30DKey: n λ R During a 1 minute observation, a server received 120requests. The mean response time was 1 second. Themean number of queries in the server is UC Berkeley, Fall 2012 2012 Raj Jain30-29

Stochastic Processes Process: Function of timeStochastic Process: Random variables, which are functions oftimeExample 1: n(t) number of jobs at the CPU of a computer system Take several identical systems and observe n(t) The number n(t) is a random variable. Can find the probability distribution functions for n(t) ateach possible value of t.Example 2: w(t) waiting time in a queueUC Berkeley, Fall 2012 2012 Raj Jain30-31

Types of Stochastic Processes Discrete or Continuous State ProcessesMarkov ProcessesBirth-death ProcessesPoisson ProcessesUC Berkeley, Fall 2012 2012 Raj Jain30-32

Discrete/Continuous State Processes Discrete Finite or CountableNumber of jobs in a system n(t) 0, 1, 2, .n(t) is a discrete state processThe waiting time w(t) is a continuous state process.Stochastic Chain: discrete state stochastic processNote: Time can also be discrete or continuous Discrete/continuous time processesHere we will consider only continuous time processesStateUC Berkeley, Fall 2012Time30-33 2012 Raj Jain

Markov Processes Future states are independent of the past and depend only onthe present.Named after A. A. Markov who defined and analyzed them in1907.Markov Chain: discrete state Markov processMarkov It is not necessary to history of the previous statesof the process Future depends upon the current state onlyM/M/m queues can be modeled using Markov processes.The time spent by a job in such a queue is a Markov processand the number of jobs in the queue is a Markov chain.UC Berkeley, Fall 2012 2012 Raj Jain30-34

Birth-Death Processes 0 1 2 j j-1 jj j j j 1 j j The discrete space Markov processes in which the transitionsare restricted to neighboring statesProcess in state n can change only to state n 1 or n-1.Example: the number of jobs in a queue with a single serverand individual arrivals (not bulk arrivals)UC Berkeley, Fall 2012 2012 Raj Jain30-35

Poisson Distribution If the inter-arrival times are exponentially distributed,number of arrivals in any given interval are Poisson distributedτ Exponentialtimen Poissonf (τ ) λe λτn e λtP (n arrivals in t) (λt) n! E[τ ] λ1E[n] λtM Memoryless arrival Poisson arrivalsExample: λ 4 4 jobs/sec or 0.25 sec between jobs on averageUC Berkeley, Fall 2012 2012 Raj Jain30-36

Poisson Processes Interarrival time s IID and exponential number of arrivals n over a given interval (t, t x) has aPoisson distribution arrival Poisson process or Poisson streamProperties: 1.Merging: 2.Splitting: If the probability of a job going to ithsubstream is pi, each substream is also Poisson with amean rate of pi UC Berkeley, Fall 2012 2012 Raj Jain30-37

Poisson Processes (Cont) 3.If the arrivals to a single server with exponentialservice time are Poisson with mean rate , thedepartures are also Poisson with the same rate provided .UC Berkeley, Fall 2012 2012 Raj Jain30-38

Poisson Process(cont) 4. If the arrivals to a service facility with m service centersare Poisson with a mean rate , the departures alsoconstitute a Poisson stream with the same rate , provided i i. Here, the servers are assumed to haveexponentially distributed service times.UC Berkeley, Fall 2012 2012 Raj Jain30-39

PASTA PropertyPoisson Arrivals See Time Averages Poisson arrivals Random arrivals from a large number ofindependent sources If an external observer samples a system at a random instant:P(System state x) P(State as seen by a Poisson arrival is x)Example: D/D/1 Queue: Arrivals 1 job/sec, Service 2 jobs/sec 012345All customers see an empty system.M/D/1 Queue: Arrivals 1 job/sec (avg), Service 2 jobs/secRandomly sample the system. System is busy half of the time.UC Berkeley, Fall 20120123430-405 2012 Raj Jain

Relationship Among Stochastic ProcessesUC Berkeley, Fall 2012 2012 Raj Jain30-41

Quiz 30ET F Birth-death process can have bulk service Merger of Poisson processes results in aProcess The number of jobs in a M/M/1 queue is Markov T F A discrete time process is also called a chain UC Berkeley, Fall 2012 2012 Raj Jain30-42

Summary Kendall Notation: A/S/m/B/k/SD, M/M/1Number in system, queue, waiting, serviceService rate, arrival rate, response time, waiting time, servicetimeLittle’s Law:Mean number in system Arrival rate Mean time in systemProcesses: Markov Only one state required,Birth-death Adjacent statesPoisson IID and exponential inter-arrivalUC Berkeley, Fall 2012 2012 Raj Jain30-44

Homework 30Form a team of 2 students. Select any system. Monitor the times ofarrivals and departures of requests starting from an idle state andending at the end of the next idle state with at least one idle state inthe middle. (You can have more than one cycle) Examples: System you are designing, network using a networkmonitor, traffic light, restaurant, grocery store, bank, 1. Compute: Mean arrival rate Mean service rateIdleBusy Server utilization Mean response time Mean number in system2. What distribution (M, D, or G) according to you these arrivals andservice should have and why? There is no need to analytically verify.Due: Via email to jain@eecs by noon next Monday. UC Berkeley, Fall 2012 2012 Raj Jain30-45

Reading ListIf you need to refresh your probability concepts, readchapter 12 Read Chapter 30 Refer to Chapter 29 for various distributions UC Berkeley, Fall 2012 2012 Raj Jain30-46

Queueing Theory Raj Jain Washington University in Saint Louis Jain@eecs.berkeley.edu or Jain@wustl.edu A Mini-Course offered at UC Berkeley, Sept-Oct 2012 These slides and audio/video recordings are available on-line at: . Can find the

Related Documents:

Purpose Simulation is often used in the analysis of queueing models. A simple but typical queueing model Waiting line Server Calling population Queueing models provide the analyst with a powerful tool for designing and evaluating the performance of queueing systems. Typical measures of system performance Server util

802.16 networks was conducted in [7], [8] by combining link-layer queueing with physical-layer transmission. A vacation queueing model was adopted in [9] to analyze the link-layer queueing performance of OFDM-TDMA systems with round-robin scheduling. A queueing model for OFDMA systems was used in [10] to design a scheduling scheme that balances

theory to construct the dynamic system of screening system in this paper. Queueing theory is the mathematical study of waiting lines [23]. In queueing theory, a model is constructed so that queue length

the understanding of teletra c, queueing theory fundamentals and related queueing behavior of telecommunications networks and systems. These concepts and ideas form a strong base for the more mathematically inclined students who can follow up with the extensive literature on

of Queueing Theory Applied to Emergency Care. Here is a picture of the participants at our meeting on October 25, 2012. Figure 1. Emergency Care/Queueing Seminar: (Left to Right) Jed Keesling, Trent Register, Joshua Hurwitz, Jean Larson, James Maissen, Hayriye Gulbu-dak, Evan Milliken,

probability, operational research, telecommunication, i ndustrial engineering, com-puter science, management science publish articles on queu eing extensively. The ow of new theories and methodologies in queueing has become very hard to keep . Queueing Theory and its Applications, A Personal View 13 distrib

have faded. But our lack of completeness is also explained by the time constraints of this survey. Queueing applications are abundant in Canada. The diverse areas where queueing analysis has been applied include: ship-ping and canals, grocery store checkout line count estimation, vehic

Components of a Queueing Model The calling population Finite or infinite (often approx. “very large”) Infinite pool: arrival rate not affected by the number of customers who have left the calling population and joined the queueing system. Finite pool: can affect arrival proce