WUSTL CSE 567M - Analysis of A Single Queue (23 pages)

Previewing pages 1, 2, 22, 23 of 23 page document View the full content.
View Full Document

Analysis of A Single Queue



Previewing pages 1, 2, 22, 23 of actual document.

View the full content.
View Full Document
View Full Document

Analysis of A Single Queue

115 views


Pages:
23
School:
Washington University in St. Louis
Course:
Cse 567m - Computer Systems Analysis
Computer Systems Analysis Documents
Unformatted text preview:

Analysis of A Single Queue Raj Jain Washington University in Saint Louis Saint Louis MO 63130 Jain cse wustl edu These slides are available on line at http www cse wustl edu jain cse567 06 Washington University in St Louis CSE567M 31 1 2006 Raj Jain Overview Birth Death Processes M M 1 Queue M M m Queue M M m B Queue with Finite Buffers Results for other Queueing systems Washington University in St Louis CSE567M 31 2 2006 Raj Jain Birth Death 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 0 1 1 1 2 2 2 Washington University in St Louis 1 J 1 3 J CSE567M 31 3 1 J 1 1 2 2006 Raj Jain Birth 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 Washington University in St Louis CSE567M 31 4 2006 Raj Jain Theorem State Probability The steady state probability pn of a birth death process being in state n is given by Here p0 is the probability of being in the zero state Washington University in St Louis CSE567M 31 5 2006 Raj Jain 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 Washington University in St Louis CSE567M 31 6 2006 Raj Jain 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 t Washington University in St Louis CSE567M 31 7 2006 Raj Jain Proof Cont The jth equation above can be written as follows Under steady state pj t approaches a fixed value pj that is Washington University in St Louis CSE567M 31 8 2006 Raj Jain Proof Cont Substituting these in the jth equation we get The solution to this set of equations is Washington University in St Louis CSE567M 31 9 2006 Raj Jain Proof Cont The sum of all probabilities must be equal to one Washington University in St Louis CSE567M 31 10 2006 Raj Jain M 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 Washington University in St Louis J 1 J CSE567M 31 11 J 1 2006 Raj Jain Results for M M 1 Queue Birth death processes with Probability of n jobs in the system Washington University in St Louis CSE567M 31 12 2006 Raj Jain 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 Washington University in St Louis CSE567M 31 13 2006 Raj Jain Results for M M 1 Queue Cont Mean number of jobs in the system Variance of the number of jobs in the system Washington University in St Louis CSE567M 31 14 2006 Raj Jain 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 Washington University in St Louis CSE567M 31 15 2006 Raj Jain 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 time Washington University in St Louis CSE567M 31 16 2006 Raj Jain 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 Washington University in St Louis CSE567M 31 17 2006 Raj Jain 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 Washington University in St Louis CSE567M 31 18 2006 Raj Jain Example 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 Washington University in St Louis CSE567M 31 19 2006 Raj Jain 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 Washington University in St Louis CSE567M 31 20 2006 Raj Jain 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 far above the mean queue length the results obtained are a close approximation Washington University in St Louis CSE567M 31 21 2006 Raj Jain Summary Birth death processes Compute probability of having n jobs in the system M M 1 Queue Load independent Arrivals and service do not depend upon the number in the system n n Traffic Intensity Mean Number of Jobs in the system 1 Mean Response Time 1 1 Washington University in St Louis CSE567M 31 22 2006 Raj Jain Homework Submit answers to modified Exercise 31 3 The average response time on a database system is five seconds During a one minute observation interval the idle time …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Analysis of A Single Queue and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Analysis of A Single Queue and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?