Module 7: Introduction To Queueing Theory (Notation .
Module 7: Introduction to Queueing Theory(Notation, Single Queues, Little’s Result)(Slides based on Daniel A. Reed, ECE/CS 441 Notes, Fall 1995, used with permission)ECE/CS 441: Computer System AnalysisModule 6, Slide 1
Outline of Section on Queueing Theory1. Notation2. Little’s Result3. Single Queues4. Solutions for networks of queues - Product Form Results (on blackboard, notslides)5. Mean value analysis (if time permits)ECE/CS 441: Computer System AnalysisModule 6, Slide 2
Queueing Theory Notation Queuing characteristics– Arrival process– Service time distribution– Number of servers– System capacity– Population size– Service disciplineEach of these is described mathematically– Descriptions determine tractability of (efficient) analytic solution– Only a small set of possibilities are solvable using standard queueing theoryECE/CS 441: Computer System AnalysisModule 6, Slide 3
Arrival Processes Suppose jobs arrive at times t1 , t2 , . ,tj– Random variables τj tj - tj-1 are inter-arrival times– There are many possible assumptions for the distribution of the τj– Typical assumptions for the τj: Independent Identically distributed– Many other possible assumptions: Bulk arrivals Balking Correlated arrivalsFor Poisson arrival, the inter-arrival times are:– IID (independent and identically distributed)– exponentially distributed (i.e., CDF F(x) 1 - e -x/a)Other common arrival time distributions include– Erlang, Hyper-exponential, Deterministic, General (with a specified mean andvariance)ECE/CS 441: Computer System AnalysisModule 6, Slide 4
Other Queue Features Service time– Interval spent actually receiving service (exclusive of waiting time)– As with arrival processes, there are many possible assumptions– Most common assumptions are IID random variables exponential service time distributionNumber of servers– Servers may or may not be identical– Service discipline determines allocation of customers to serversSystem capacity– Maximum number of customers in the system (including those in service)– May be finite or infinitePopulation size– Total number of potential customers– May be finite or infiniteECE/CS 441: Computer System AnalysisModule 6, Slide 5
Other Queue Features (Continued) Service discipline– The order waiting customers are serviced– Many possibilities, including First-come-first-serve (FCFS), the most common Last-come-first-serve (LCFS) Last-come-first-serve preempt resume (LCFS-PR) Round robin (RR) with finite quantum size Processor sharing (PS) --- RR with infinitesimal quantum size Infinite server (IS)– Almost anything might be used, depending on the the total state of the queue– As expected, service discipline affects the nature of the stochastic processthat represents the behavior of the queueing systemECE/CS 441: Computer System AnalysisModule 6, Slide 6
Queueing Discipline Specification Queueing discipline is typically specified using Kendall’s notation (A/S/m/B/K/SD), where– Interarrival and service time specifiers––––– M exponentialEk Erlang with parameter kHk hyperexponential with parameter kD deterministicG general (any distribution, mean and variance used in the solution)Bulk arrivals or service are denoted by a superscript–– Letters correspond to six queue attributes A: interarrival time distribution S: service time distribution m: number of servers B: number of buffers (system capacity) K: population size SD: service disciplineM[x] denotes exponential arrivals with group size xx is generally a random variable with separately specified distributionOmitted specifiers assume certain defaults–––infinite buffer capacityinfinite population sizeFCFS service disciplineECE/CS 441: Computer System AnalysisModule 6, Slide 7
Example Queueing Discipline Specifications M/D/5/40/200/FCFS– Exponentially distributed interarrival times– Deterministic service times– Five servers– Forty buffers (35 for waiting)– Total population of 200 customers– First-come-first-serve service disciplineM/M/1– Exponentially distributed interarrival times– Exponentially distributed service times– One server– Infinite number of buffers– Infinite population size– First-come-first-serve service disciplineECE/CS 441: Computer System AnalysisModule 6, Slide 8
An Introductory Example Given these descriptions, what are examples of their application?Consider a typical bank– 5 tellers– Customers form a single line and are serviced FCFS– Excluding a run on the bank, the waiting room is effectively infinite– For a large bank, the population is effectively infinite– Bulk arrivals are possible if friends arrive together for serviceWhat about service time and inter-arrival time distributions?– We can go measure them with a watch at the bank– Or, we can make mathematically simplifying assumptions– Latter is most common and exponential distribution is typicalCombining these facts and assumptions– M/M/1 queue– As we shall see, the mean queue length (including one in service) for an M/M/1 queue is!µ "!– Where λ is the mean inter-arrival time µ is the mean service timeECE/CS 441: Computer System AnalysisModule 6, Slide 9
Notation and Basic “Facts” Standard variable names– τ is job interarrival time– λ 1/E[τ] mean job arrival rate– s is service time per customer (job)– m is number of servers– µ 1/E[s] is mean service rate per server– n nq ns is number of jobs in the system– nq is number of jobs waiting to receive service– ns is number of jobs in service– r is response time (service time plus queueing delay)– w is waiting time (queueing delay only)System must be “stable” to have an interesting steady state solution– Number of jobs in the system is finite– Requires the relation λ mµ hold unless the population is finite (queue length is bounded) the buffer capacity is finite (arrivals are lost when queue is full) (in these cases, system is always stable)ECE/CS 441: Computer System AnalysisModule 6, Slide 10
Notation and Basic “Facts” Number of jobs in the system– n nq ns (jobs are either waiting or in service)–E[n] E[n q ] E[n s ] (or n n q n s )– and, if the service rates are independent of queue length Cov(nq,ns) 0 Var[n] Var[nq] Var[ns]Number and time– r w s (response time is the sum of queueing delay and service)– but, r , w, and s are random variables, so r w s– and, if the service rates are independent of queue length Cov(w,s) 0 Var[r] Var[w] Var[s]ECE/CS 441: Computer System AnalysisModule 6, Slide 11
Little’s Law Very important result -- Part of the queueing folk literature for the past centuryFormal proof due to J. D. C. Little (1961)Relates mean queue length to arrival rate and mean response timeMathematically (in seady state),n !r Applies to any “black box” queue under the following assumptions– System is work conserving– Number of jobs entering is same as number leaving (system is stable)Also applies to any transient interval, without requirement that system be stable.Note that these are very general conditions, and can apply for any system(“black box”) in which customers leave and enter subject to the aboveconstraints.An intuitive proof. ECE/CS 441: Computer System AnalysisModule 6, Slide 12
Little’s Law (Continued) Sketch of proof (of steady-state case):– During a long interval, arrivals departures (else no stability)– Area under the curve is total job time units (jobs x time)arrival– Mean queue length n is average curve height (area/time)rate– Mean time in system r is area/arrivalsjobs x timejobs x timejobsx jobstimetime– Mean arrival rate is arrivals/timeAvg time in systemAvg number in systemA very general result:– No assumptions about arrival or service processes– Holds for any queueing discipline (simply charge the area differently)ECE/CS 441: Computer System AnalysisModule 6, Slide 13
Analysis of Single Queues Plan:– Start with one of the simplest queues, an M/M/1– Model as a “birth-death” process– Generalize result to other types of queues A birth-death process is a Markov process in which states are numbered a integers, andtransitions are only permitted between “neighboring” states.Steady state solution of a birth death process (Kleinrock, Queueing Systems, vol. 1):– (Theorem) steady state probability pn of being in state n is! 0 !1 . ! n"1pn p0n 1, 2, ., #µ 1 µ 2 . µ n– where p0 is the probability of being in state 0Now for a proof . ECE/CS 441: Computer System AnalysisModule 6, Slide 14
Birth-Death (Steady-State) State Occupancy Proof If stable, in the steady state (by Markov process solution described earlier)0 * j #1 p j #1 # ( µ j * j ) p j µ j 1 p j 1Flow balance at state jor) µj *j &* j #1' p j 1 p #p' µ j 1 j µ j 1 j #1(%and*0p0µ1 And the solution is.* * .*pn 0 1 n #1 p0µ1µ 2 .µ nn #1 * j p0 "j 0 µ j 1j 1,2,3,.p1 ECE/CS 441: Computer System Analysisn 1,2,., !Module 6, Slide 15
Birth-Death (Steady-State) State Occupancy Proof, cont. Finally, because#! pj 1j 0we havep0 1n 11 !#n 1 " j 0ECE/CS 441: Computer System Analysis%jµ j 1Module 6, Slide 16
M/M/1 Queue Analysis M / M / 1 is a special case of a birth - death process- !i ! j for all i and j- µ i µ j for all i and j By simplificationn(*%p n && ## p 0n 1,2 ,., !'µ By tradition, the ratio*) µis called the " traffic intensity" andpn ) n p0andp0 11 ) ) 2 . ) ! By substitutionp n (1 " ) )) nECE/CS 441: Computer System Analysis 1" )n 0 ,1,2 ,.!Module 6, Slide 17
M/M/1 Queue Analysis (Continued) Utilization U is simply 1 # p 0 * Mean queue length E [ n ] (or n )"n ! np nn 1" ! n( 1 # * )* n“almost” mean of a geometric random variable---factor out a rho firstn 1*1# * Variance of number of jobs in the system [ ]Var [ n ] E n 2 # (E [ n ] )2) " 2&2 '' ! n (1 # * )* n # (E [n])( n 1%* (1 # * )2 Probability of n or more jobs in the system"!pj n"j ! (1 # * )* j * nj nECE/CS 441: Computer System AnalysisModule 6, Slide 18
M/M/1 Queue Analysis (Continued) Mean response time r (or R) via Little's Lawn "ryieldsn!1r " (1 # ! )" µ # "where the response time approaches & as " % µ CDF of response time is (show as homework .)F (r ) 1 # e # rµ (1# ! ) Mean number of jobs in the queue E nq (or nq )[ ]!2nq (n # 1) pn 1# !n 1&ECE/CS 441: Computer System AnalysisModule 6, Slide 19
M/M/1 Queue Example Consider the following queue- " 0.3- µ 0.5 We can calculate the following statistics- utilization U" 0.3U # 0.6µ 0.5- mean number of jobs in the system n#0.6n 1.51 ! # 0.4- mean response time r11r 5.0µ ! " 0.2ECE/CS 441: Computer System AnalysisModule 6, Slide 20
M/M/1 Queue Example (Continued) Consider changing λ– hold µ fixed at 0.5– examine changes in performance metricsECE/CS 441: Computer System AnalysisModule 6, Slide 21
M/M/m Queues M/M/m queues– m servers rather than one server– Reasonable model of a bank queue with multiple tellers a shared memory multiprocessorAssumptions– m servers– All servers have the same service rate µ– Single queue for access to the servers– Arrival rate λ– Formally!n !n 0,1,., "n 0,1,. m ! 1# nµµn n m, m 1,. "% mµWhat are the state occupancy probabilities?ECE/CS 441: Computer System AnalysisModule 6, Slide 22
M/M/m Queues (Continued) State occupancy probabilities- Just another birth - death process- Recall general form of the probability occupancies earlier' ' .'pn 0 1 n &1 p0n 1,2,., %µ1µ 2 .µ n By simple substitution of the ' j and µ j , we have 'np!n 0! n!µpn #n'!p!" m!m n & m µ n 0ECE/CS 441: Computer System Analysisn 1,2,., m ! 1n m, m 1,., !Module 6, Slide 23
M/M/m Queues (Continued)or equivalently (with ! " /(mµ))# ( m! ) nn 1,2,., m ! 1%%p0pn nn! m%! m pn m, m 1,., !%& m! 0 And, because'(pn 1n 0we have)1m)1*(m! ) m(m! ) n p0 ,1 (/m!(1)!)n! . n 1ECE/CS 441: Computer System AnalysisModule 6, Slide 24
M/M/m Queues (Continued) In a similar manner to that for the M/M/1 queue,- We can derive the "standard" measures(queue length, utilization, response time, etc.)- You should do these derivations yourself Mean number of jobs in the system n nq ns!"n m! 1# !ECE/CS 441: Computer System AnalysisModule 6, Slide 25
M/M/m Queues (Continued)where! #mµ" P(& m(m! )mjobs ) pn p0m!(1 % ! )n m'observe that " is- the probability an arriving job must queue- also known as Erlang's C formula Expected number of jobs in service nsm %1'n 1n mns npn mpn m!ECE/CS 441: Computer System AnalysisModule 6, Slide 26
M/M/m Queues (Continued) Utilization of each server- m servers- m) mean jobs in service- individual server utilization must be ) Mean response time r w s (just apply Little' s law)nr *#1&(!! 1 µ % m( 1 ' ) ) " Mean waiting time w (Little' s law again)nqw *n ' ns *) mµ ( 1 ' ) ) rq (q percentile of waiting time)& w100( #!!rq max 0 , ln% ( 100 ' q "ECE/CS 441: Computer System AnalysisModule 6, Slide 27
M/M/m Queue Example Consider changing m– hold λ and µ fixed– examine changes in performance metricsObservations!– M/M/m queue has asymptote at mµ– substantial performance gains with even two serversECE/CS 441: Computer System AnalysisModule 6, Slide 28
M/M/1 and M/M/m Queue Comparison Which is better?- m queues each with an arrival rate !/m- one queue with m servers and an arrival rate of ! Suppose we use mean response time as our metric.- m M / M /1 queues1r µ " ! /m- one M / M /m queue(1%#r '1 *µ & m(1" ) )where# (! / µ)mm!(1" ! /( mµ))p0andmn /"1,m"1( ! / µ) ( ! / µ) 1p0 .1 . m!(1" ! /( mµ)) n 1 n! 10ECE/CS 441: Computer System AnalysisModule 6, Slide 29
Queueing Comparison Consider the following– service rate µ fixed at 4, divided evenly among m servers– fix λ 2– m M/M/1 queues (arrival rate to each is λ/m)– One M/M/m queue (total arrival rate is λ)– Increase mWhat happens to response time in both queues? Why?ECE/CS 441: Computer System AnalysisModule 6, Slide 30
Mean Response Time as function of mECE/CS 441: Computer System AnalysisModule 6, Slide 31
Queueing Comparison Consider the following– service rate µ fixed at 2.1, divided evenly among m servers– varying λ (subject to stability constraint)– m M/M/1 queues (arrival rate to each is λ/m)– One M/M/m queue (total arrival rate is λ)What happens as λ approaches 2.1? Why?ECE/CS 441: Computer System AnalysisModule 6, Slide 32
Mean Response Time as a Function of Arrival RateECE/CS 441: Computer System AnalysisModule 6, Slide 33
Extrapolation Scenarios Given queueing formulae, standard questions include– Performance measures for different parameters– Parameters values needed to satisfy a particular performance constraintExamples:– What is the mean response time if arrival rate doubles?– What is the mean queue length if service rate decreases by one third?– What is the number of servers for mean response time less than fiveminutes?Approach:– Plug and crank– Repeated solution with different parameter valuesECE/CS 441: Computer System AnalysisModule 6, Slide 34
Extrapolation Scenarios (Continued) Concrete example- multiprocessor system (two processors)- mean job service time is 15 seconds- mean job interarrival time is 12 seconds By inspection- mean service rate is 4.0 jobs/minute (per processor)- mean arrival rate is 5.0 jobs/minuteand by plug and crank, we have mean response time rr #1&)1 0.41 minutes (24.6 seconds) !µ % m(1 ' ( )" How many processors do we need to have r 0.3 minutes?- solve for m 3,4 ,.- find smallest value of m such that r 0.3- here, m 3 satisfies this constraintECE/CS 441: Computer System AnalysisModule 6, Slide 35
M/M/m/B Queues Finite buffers– no more than B jobs in total can be queued and in service(i.e., total number of jobs in the system must be less than B)– jobs arriving when B jobs are present are discardedMore formally, this implies!n !n 1,2,., B " 1and! nµµn "# mµ n 1, 2,., m ! 1n m, m 1,., BObservations– B ! m or servers are wasted– birth-death process– finite number of statesECE/CS 441: Computer System AnalysisModule 6, Slide 36
M/M/m/B Queues (Continued) Applying the state occupancy formula .np0(n( n! µpn *.n(p() m! m n ' m µ n 0. And, because - mµn 1, 2,., m ! 1n m, m 1,., B ( m- ) nn 1, 2,., m ! 1p0((p n * nn! m( - m p0n m, m 1,., B() m! Finally, the probability of zero jobs in the system is()'1mnm '1&(1 ' - B ' m 1 (m- )m- ) #p 0 , p n 1 ,!m!(1')n! "n 0n 1% Now, we can use the state occupancy probabilities to compute- mean response time- mean queue lengths- effective arrival ratesBECE/CS 441: Computer System AnalysisModule 6, Slide 37
M/M/m/B Queues (Continued) Mean queue length n (queue plus service)Bn " np nn 1and mean number in the queuenq B"( n ! m )pn m 1n Arrivals are constrained by waiting space - effective arrival rate is less than - jobs enter the system only when buffers are available B !1 " p n (1 ! p B )n 0 and the difference - is the loss rate- Because jobs are not lost after entry, the mean response time isnnr ( 1 ! p B )by Little' s law- Finally, the utilization U of each server is U #(1 ! p B )mµECE/CS 441: Computer System AnalysisModule 6, Slide 38
Other Queues Other queues can be solved to varying degrees.Exact solutions are possible for– M/Er /1 (Erlangian service)– M/D/1 (special case of M/G/1)– M/M/1 with bulk arrivals (restricted cases)Analysis is more difficulty for:– G/M/1– M/G/1– G/G/1ECE/CS 441: Computer System AnalysisModule 6, Slide 39
M/G/1 QueuesM/G/1– General service time distribution– Otherwise, similar to M/M/1 queues– The most complex, readily solvable single queueSolution approach– First, some additional mathematical machinery– Then, comparisons with M/M/1 queuesService time distribution is general– Service history matters– Denote service time already received by X0(t)Arrival distribution is negative exponential– Arrival history does not matter– But we do need to know the number of customers N(t) present– N(t) is non-Markovian because it depends on service timeState-space description– States are [N(t), X0(t)]– Mixed discrete/continuous, two-dimensional description– Analysis via this method (supplementary variables) is ugly– Use the method of embedded Markov chains.ECE/CS 441: Computer System AnalysisModule 6, Slide 40
M/G/1 Queues (Continued) What has changed from M/M/1?– Two-dimensional state space– State space is now continuous (due to X0(t))Ideally– Convert [N(t), X0(t)] to one-dimensional N(t)– Implicitly specify remaining service duration X0(t)How do we do this?– Look only at selected points in time– Compute new metrics only at those points– Choose those points to implicitly carry X0(t)– departures instants make great choices Remaining (residual) service X0(t) is zero! At that instant, we can treat the behavior like a Markov chain N(t) is the number of customers left behind This is an embedded Markov chain; for details (see Kleinrock, vol. 1) but wehaven’t specified the distribution of departure instantsECE/CS 441: Computer System AnalysisModule 6, Slide 41
M/G/1 Queues (Continued) A informal derivation follows (see Kleinrock vol. 1 for details).Notation– Arrival rate λ (Poisson process)– General service time distribution mean x varianceWhat is the expected time until a customer that arrives completes service?– Mean time needed to service customers already waiting Mean time is n q x Note that this is independent of the distribution of x– plus the residual time for customer in service .Residual life requires yet another aside.ECE/CS 441: Computer System AnalysisModule 6, Slide 42
Residual Life What is a “renewal”?– Informally, a point where random variables which describe a model arememoryless given current state, with respect to past state.Renewal example– Consider a queue with general service distribution, and Poisson arrivalprocess– Most time points are not renewal points, since remaining service timedepends on service time completed.– However, times at which service completes are renewal points, sincearrival process is Poisson.Need to determine the residual lifetime of a customer in service:– Denote this random variable as R– Distribution of R depends on Distribution of original variable A (the service time distribution) atits renewal point and some time expended after the renewal pointECE/CS 441: Computer System AnalysisModule 6, Slide 43
Residual Life (Continued) Suppose- a( t ) is the pdf of A (original variable)- the original lifetime has expended time t ethen r( t ), the pdf of R (the residual lifetime) isr (# ! t e t e ) a (# # t e ) a( # )P( A # e )a( # )te1 ! " a( s )ds0 Intuition- in general, knowing about the expended time helps- in short, knowledge changes the pdf- we saw that this was not true for the exponential distribution- the geometric distribution is the only case in the discrete domain Average residual lifetime r (claim without proof)- depends only on the first two moments of the original pdf f ( x )- mean f- second moment f 2 (not the variance!)- mean residual lifetime isf2r 2fECE/CS 441: Computer System AnalysisModule 6, Slide 44
Residual Life (Continued) Example (computer part)- suppose the pdf b( t ) of the failure time is uniform- and suppose the mean value is 10 201 0 ( % 20b( t ) #" 0 otherwise- if the part has been in use for 5 time units, then 201b( t t e ) #"0t e t t e % 20otherwiseand51 & ' b( s )ds 1 &01! 5 0.7520and finally 1r( ( & t e 5 ) # 15"0- notice that0 ( t e % 15otherwisef 2 133.33r 6.672 ! 102fECE/CS 441: Computer System AnalysisObserve– pdf of residual time is not the same as theoriginal pdf– Knowledge of past behavior changes the pdf– There are only two exceptions negative exponential distribution(continuous) geometric distribution (discrete)Module 6, Slide 45
M/G/1 Queues (Continued) How long does a new arrival have to wait for service?- mean time needed to service customers already waiting let x denote the mean service time mean time is n q x note that this is independent of the distribution of x- plus the residual time for customer in service recall that this isx2t 2xassuming a customer is in service the probability of a customer in service is ! Combining items, the waiting time for a new arrival isx2rq n q x !Little’s Law again!2x Expected number of arrivals during this interval is "r , sox2rq rq "x !2xand by rearranging terms"x 2rq 2( 1 # ! )ECE/CS 441: Computer System AnalysisModule 6, Slide 46
M/G/1 Queues (Continued) As we just saw, the mean time to receive service is is#x 2rq 2( 1 " ) Adding the mean service time yields the mean response time#x 2r x 2( 1 " ) Normally, both r and rq are expressed as (verify the math)#( 1 C s2 )1r µ 2µ 2 ( 1 " )and#( 1 C s2 )rq 2µ 2 ( 1 " )where C s2 is the coefficient of variation!2C 2x2sand- ! 2 is the variance of the mean service time1- is the mean service timeµ!2x2 x2 x2- and by simplification (yields original formulation) : 1 C 1 2 1 2 µ2x22xxx2sECE/CS 441: Computer System AnalysisModule 6, Slide 47
M/G/1 Queues (Continued) Via Little' s law, the mean number in the system isn )r()())2 1 C s2) µ 2µ 2 ( 1 ' ( )( 2 1 C s2 ( 2( 1 ' ( ) Observations- this is the famous Pollaczek - Khinchin (PK) formula- learn it, remember it, treasure it!- C s is one for the negative exponential distribution, so( 2 (1 1 )(2(n ( ( 2( 1 ' ( )1' ( 1' (as we knew before- C s is zero for the deterministic distribution ( M / D / 1 queue)( 2 (1 0 )( &2'(#n ( !2( 1 ' ( ) ( 1 ' ( ) % 2 " The value of C s has profound implications- larger C s increases mean queue length and response time- values grow linearly with C sECE/CS 441: Computer System AnalysisModule 6, Slide 48
Queueing Comparison Consider the following– M/D/1 queue (Cs 0)– M/M/1 queue (Cs 1)– M/G/1 queue (Cs 1)ECE/CS 441: Computer System AnalysisModule 6, Slide 49
Queueing Example Consider the following– arrival rate λ 0.6– service rate µ 1.0– M/D/1, M/M/1, and M/G/1 queuesand compare mean response timesM/M/111r 2.5µ ! " 1.0 ! 0.6 M/D/1 M/G/1 (Cs 2.0)()21 ! 1 Cs10.6(1 0)r 1.75µ 2 µ 2 (1" # ) 1.0 2(1.0)(1" 0.6 / 1.0)()21 ! 1 Cs10.6(1 1)r 3.252µ 2 µ (1 " # ) 1.0 2(1.0)(1 " 0.6 / 1.0)ECE/CS 441: Computer System AnalysisModule 6, Slide 50
Queueing Example (Continued) Consider M/M/1 and M/G/1 queues– assume same arrival rates for both– desire same mean response times– must solve for ratio of service ratesM/M/1r 1µm ! "M/G/1(()! 1 C s21r µ g 2 µ g2 1" ! / µ g Equating, we have(())" 1 C s211 µ m ! " µ g 2 µ g2 1! " / µ g )Let’s look at some numerical solutions.ECE/CS 441: Computer System AnalysisModule 6, Slide 51
M/G/1 via Embedded DTMCECE/CS 441: Computer System AnalysisModule 6, Slide 52
M/G/1 via Embedded DTMCECE/CS 441: Computer System AnalysisModule 6, Slide 53
M/G/1 via Embedded DTMCECE/CS 441: Computer System AnalysisModule 6, Slide 54
M/G/1 via Embedded DTMCECE/CS 441: Computer System AnalysisModule 6, Slide 55
Queueing Example (Continued) Comparison Example (Continued)– arrival rate λ 0.6– M/M/1 queue (service rate µm 1.0)– M/G/1 queue (service rate µg)ECE/CS 441: Computer System AnalysisModule 6, Slide 56
Queueing Theory Notation Queuing characteristics –Arrival process –Service time distribution –Number of servers –System capacity –Population size –Service discipline Each of these is described mathematically .
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
Teacher’s Book B LEVEL - English in school 6 Contents Prologue 8 Test paper answers 10 Practice Test 1 11 Module 1 11 Module 2 12 Module 3 15 Practice Test 2 16 Module 1 16 Module 2 17 Module 3 20 Practice Test 3 21 Module 1 21 Module 2 22 Module 3 25 Practice Test 4 26 Module 1 26 Module 2 27 Module 3 30 Practice Test 5 31 Module 1 31 Module .
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,
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
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
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
