QoS技術(shù)基礎(chǔ)-chpt2.ppt

1、1,Elements of Queuing Theory,The queuing model Core components; Notation; Parameters and performance measures Characteristics; Markov Process Discrete-time Markov chain; Continuous-time Markov chain; Birth-death process; Some typical and often-used distributions Exponential Distribution; Poisson Dis

2、tribution; M/M/1 Littles Law Brief review of M/M/s, M/G/1, M/D/1 Some additional discussions.,2,Queuing Systems,Core components of the model Arrival process Buffer (the so-called queue) Infinite or finite; Service process single or parallel servers Service discipline (FIFO, random),3,Kendall Notatio

3、n for Queuing Systems (1951),a/b/s/e/p/d a, specifies the arrival process b, specifies the service process s, is the number of parallel servers in the system e, (usually ) is buffer size (i.e. maximum number of customers allowed in system) p, (usually ) is size of customer population d, is the servi

4、ce discipline (FIFO, LIFO, etc.),4,Queuing model parameters, = average rate of customer arrivals (no. of customers/unit time) = average rate of customer serviced by a server (no. of customers/unit time) (1/ = average service time) s = number of servers (channels) in the system If s , then . . . If s

5、 , then . . . The queuing systems is in steady state when the rate of departures from the system equals the rate of arrivals.,5,Performance Evaluation,6,Queuing Performance Measures,Lq = average number of customers in queue Wq = average waiting time in queue (until service starts) L = average number

6、 of customers in system = Lq + (average number being served) W = average time a customer spends in system = Wq + 1/ = utilization factor = /(s ) = fraction of time a server is busy (on average) Pn = the probability that exactly n customers are in the system Pzn = the probability that at least n cust

7、omers are in the system PW = Pzs = the probability that a customer must wait for service (or the fraction of customers who must wait at least some time in the queue),7,Markov Process,The probabilistic future of the process depends only on the current state and not upon the history of the process. In

8、 other words, the entire history of the process is summarized in the current state. Markov chain: A Markov process with discrete state space discrete-time Markov chain and continuous-time Markov chain: focus of our further discussions.,8,Discrete-Time Markov chain,9,Discrete-Time Markov chain (contd

9、),A matrix that satisfies the above properties is called a stochastic matrix.,10,Discrete-Time Markov chain (contd),The Chapman-Kolomogorov Equation:,11,Discrete-Time Markov chain (contd),Apparently,The matrix form:,12,Discrete-Time Markov chain (contd),Therefore, by solving the system of linear equ

10、ations defined by:,Where:,We get the system invariant measure or stable d.f.,It is not discussed in this course the conditions under which the above results hold. For ones who are interested, pls. refer to corresponding papers or books where detailed discussions or analysis are made.,13,Discrete-Tim

11、e Markov chain (contd),The example: one-step transition matrix:,The transition diagram:,The equilibrium equation in matrix notation:,The invariant measure:,14,Continuous-time Markov chain,The Chapman-Kolmgorov Equation for C-M.C.:,15,Continuous-time Markov chain(contd),Where:,16,Continuous-time Mark

12、ov chain(contd),By solving the following system of equations, we can get the invariant measure:,17,Continuous-time Markov chain(contd),It is not discussed in this course the conditions under which the above results hold. For ones who are interested, pls. refer to corresponding papers or books where

13、detailed discussions or analysis are made.,18,Continuous-time Markov chain (contd),The example: the Q matrix:,The transition diagram:,The equilibrium equation in matrix notation:,The invariant measure:,19,Birth-Death Process,20,Birth-Death Process (contd),Then we get the differential equation:,21,Bi

14、rth-Death Process (contd),Then we get:,Or equivalently:,The equilibrium equations or the balance equations of a birth and death process,22,Birth-Death Process (contd),The computation of p0 relies on the fact:,Cinfinite,23,Exponential Distribution,(Continuous random variable),24,Exponential Distribut

15、ion,(Continuous random variable),Memoryless Property,25,Exponential Distribution,26,Poisson distribution,(Discrete random variable),X 0, 1, 2, 3, .,X = 0, 1, 2, ., parameter,e = 2.718,Expected value of X = , Variance of X = ,27,Poisson Process,28,Poisson Process (contd),The counting process,Proof:,2

16、9,Poisson Process (contd),Proof (contd):,For n0, we have:,30,Poisson Process (contd),Proof (contd):,By noting the initial condition Pk(0) = 0, k0, solving the differential equation recursively yields the desired results.,This says, in particular, the mean number of events per time unit, or equivalen

17、tly, the rate at which events occur, is given by EN(t)/ t = . This is why is called the rate of the Poisson process.,31,Poisson Process (contd),Proof:,32,Poisson Process (contd),Additional properties of Poisson Process:,The inverse is also valid.,33,Catalogue of Queues,Single server, Poisson arrival

18、s M/G/1 M/M/1 M/D/1 Multiple servers, Poisson arrivals M/G/s M/M/s etc, etc,34,M/M/1,In summary: Arrival process is Poisson Process; Departure process is Poisson Process; Service discipline is FCFS; Work-conserving;,35,M/M/1 (contd),36,M/M/1 (contd),This parameter is often called the utilization lev

19、el of the system because it tells the average load status of the system.,The transition diagram:,37,M/M/1 (contd),Ls = Lq + Ws = Wq + 1/,38,Littles Law,Relationship between the performance measures for any queue.,39,Littles Law,40,MultiServer Systems with Exponential Service Times (M/M/s Systems), =

20、 /(s) Pn = Lq = (/ )sP0/s!(1- )2 Ls = Lq + / Wq = Lq / Ws = Wq + 1/,41,Queuing Example,Purchase two facsimile transmission (fax) machine for use of two departments. For each dept:,42,Example: Two separate queues,Modelled as two separate M/M/1 queues, we get the following performance measures:,43,36/

21、day from Design + 36/day from sales = 72items/day = M/M/2 system with = 72 items per day and =48 items per day.,Example: Common pool,44,Benefits of Pooling Servers,The result for example 2 holds in general: If customers are homogeneous, then there will be less customer waiting on average if servers

22、are pooled into one queuing system. Notice that in both systems the utilization rates are the same, so the servers do not work any harder or longer in one configuration versus the other. Instead, they work more effectively in a pooled system by coordinating their idle time so that a server is never

23、idle while other servers have queues. As long as customers can choose which queue to enter and can switch among queues, system with s queues should behave no differently than a system with one queue.,45,M/G/1 Systems,the variance of the service time = 2,46,M/D/1 Systems,When the service times are a constant, so that 2=0, we say that the service distribution is deterministic. Everything else being equal, the more variation in ser