31-1©2006 Raj JainCSE567MWashington University in St. LouisAnalysis of Analysis of A Single QueueA Single QueueRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse567-06/31-2©2006 Raj JainCSE567MWashington University in St. LouisOverviewOverview! Birth Death Processes! M/M/1 Queue! M/M/m Queue! M/M/m/B Queue with Finite Buffers! Results for other Queueing systems31-3©2006 Raj JainCSE567MWashington University in St. LouisBirthBirth--Death ProcessesDeath Processes! Jobs arrive one at a time (and not as a batch). ! State = Number of jobs n in the system. ! Arrival of a new job changes the state to n+1 ⇒ birth! Departure of a job changes the system state to n-1 ⇒ Death ! State-transition diagram:0 1 2 J-1 J J+1…λ0λ1λ2Λϕ−1λϕΛϕ+1μ1μ2μ3μϕμϕ+1μϕ+231-4©2006 Raj JainCSE567MWashington University in St. LouisBirthBirth--Death Processes(Cont)Death Processes(Cont)! When the system is in state n, it has n jobs in it." The new arrivals take place at a rate λn. " The service rate is μn. ! We assume that both the inter-arrival times and service times are exponentially distributed.31-5©2006 Raj JainCSE567MWashington University in St. LouisTheorem: State Probability Theorem: State Probability ! The steady-state probability pnof a birth-death process being in state n is given by:! Here, p0is the probability of being in the zero state.31-6©2006 Raj JainCSE567MWashington University in St. LouisProof Proof ! Suppose the system is in state j at time t. There are j jobs in the system. In the next time interval of a very small duration Δt, the system can move to state j-1 or j+1 with the following probabilities:31-7©2006 Raj JainCSE567MWashington University in St. LouisProof(Cont)Proof(Cont)! If there are no arrivals or departures, the system will stay in state j and, thus:!Δt = small ⇒ zero probability of two events (two arrivals, two departure, or a arrival and a departure) occurring during this interval pj(t) = probability of being in state j at time t31-8©2006 Raj JainCSE567MWashington University in St. LouisProof(Cont)Proof(Cont)! The jthequation above can be written as follows:! Under steady state, pj(t) approaches a fixed value pj, that is:31-9©2006 Raj JainCSE567MWashington University in St. LouisProof(Cont)Proof(Cont)! Substituting these in the jthequation, we get:! The solution to this set of equations is:31-10©2006 Raj JainCSE567MWashington University in St. LouisProof(Cont)Proof(Cont)! The sum of all probabilities must be equal to one:31-11©2006 Raj JainCSE567MWashington University in St. LouisM/M/1 QueueM/M/1 Queue! M/M/1 queue is the most commonly used type of queue ! Used to model single processor systems or to model individual devices in a computer system ! Assumes that the interarrival times and the service times are exponentially distributed and there is only one server. ! No buffer or population size limitations and the service discipline is FCFS ! Need to know only the mean arrival rate λ and the mean service rate μ. ! State = number of jobs in the system 0 1 2 J-1 J J+1…λλλ λ λλμμ μ μ μ μ31-12©2006 Raj JainCSE567MWashington University in St. LouisResults for M/M/1 QueueResults for M/M/1 Queue! Birth-death processes with ! Probability of n jobs in the system:31-13©2006 Raj JainCSE567MWashington University in St. LouisResults for M/M/1 Queue(Cont)Results for M/M/1 Queue(Cont)! The quantity λ/μis called traffic intensity and is usually denoted by symbol ρ. Thus: ! n is geometrically distributed. Utilization of the server = Probability of having one or more jobs in the system:31-14©2006 Raj JainCSE567MWashington University in St. LouisResults for M/M/1 Queue(Cont)Results for M/M/1 Queue(Cont)! Mean number of jobs in the system:! Variance of the number of jobs in the system:31-15©2006 Raj JainCSE567MWashington University in St. LouisResults for M/M/1 Queue(Cont)Results for M/M/1 Queue(Cont)! Probability of n or more jobs in the system:! Mean response time (using the Little's law):! Mean number in the system = Arrival rate × Mean response time}! That is:31-16©2006 Raj JainCSE567MWashington University in St. LouisResults for M/M/1 Queue(Cont)Results for M/M/1 Queue(Cont)! Cumulative distribution function of the response time:! The response time is exponentially distributed. ⇒ q-percentile of the response time31-17©2006 Raj JainCSE567MWashington University in St. LouisResults for M/M/1 Queue(Cont)Results for M/M/1 Queue(Cont)! Cumulative distribution function of the waiting time:! This is a truncated exponential distribution. Its q-percentile is given by:! The above formula applies only if q is greater than 100(1-ρ).All lower percentiles are zero.31-18©2006 Raj JainCSE567MWashington University in St. LouisResults for M/M/1 Queue(Cont)Results for M/M/1 Queue(Cont)! Mean number of jobs in the queue:! Idle ⇒ there are no jobs in the system ! The time interval between two successive idle intervals ! All results for M/M/1 queues including some for the busy period are summarized in Box 31.1 in the book.31-19©2006 Raj JainCSE567MWashington University in St. LouisExample 31.2Example 31.2! On a network gateway, measurements show that the packets arrive at a mean rate of 125 packets per second (pps) and the gateway takes about two milliseconds to forward them. Using an M/M/1 model, analyze the gateway. What is the probability of buffer overflow if the gateway had only 13 buffers? How many buffers do we need to keep packet loss below one packet per million? ! Arrival rate λ = 125 pps! Service rate μ = 1/.002 = 500 pps! Gateway Utilization ρ = λ/μ= 0.25! Probability of n packets in the gateway = (1-ρ)ρn= 0.75(0.25)n)31-20©2006 Raj JainCSE567MWashington University in St. LouisExample 31.2(Cont)Example 31.2(Cont)! Mean Number of packets in the gateway = (ρ/(1-ρ) = 0.25/0.75 = 0.33)! Mean time spent in the gateway = ((1/μ)/(1-ρ)= (1/500)/(1-0.25) = 2.66 milliseconds! Probability of buffer overflow ! To limit the probability of loss to less than 10-6:We need about ten buffers.31-21©2006 Raj JainCSE567MWashington University in St. LouisExample 31.2(Cont)Example 31.2(Cont)! The last two results about buffer overflow are approximate. Strictly speaking, the gateway should actually be modeled as a finite buffer M/M/1/B queue. However, since the utilization is low and the number of buffers is
View Full Document
Unlocking...