#### Transcript ppt - Dr. Wissam Fawaz

Welcome to COE 755: Queuing Theory Instructor: Dr. Wissam F. Fawaz Office 103, Bassil Bldg. Email: [email protected] Required text book: Chee Hock Ng, Queuing Modelling Fundamentals, second edition, John Wiley & Sons, 2008. Course website: http://www.wissamfawaz.com/queueing_theory.htm 1 Course Description Queuing Analysis is a vital tool used in evaluating system performances its application covers A wide spectrum from Bank automated teller machines to transportation and communications data networks This queuing course focuses on queuing modeling techniques and its application in data networks 2 Course synopsis The course covers Discrete/continuous random variables Birth and death process Machine Interference Problem Hypo/Hyper exponential distributions Markovian/semi-Markovian Queueing Systems Discrete and Continuous Markov Processes Queueing Networks 3 Course learning objectives Students are expected to be able: gain a mastery of Markovian queuing systems construct queuing models for engineering problems and solve queuing problems become familiar with the derivation techniques used to measure system performance work with an emerging class of arrival processes Markov-modulated arrival process use QNAP (Queuing Network Analysis Package) software To solve real world network related problems 4 Assessment & grading Topic presentation/Homeworks 15% Simulation projects 15% Exam I 20% Exam II 20% Final 30% 5 Queuing definitions Kleinrock Bose “We study the phenomena of standing, waiting, and serving, and we call this study Queueing Theory.” “The basic phenomenon of queuing arises whenever a shared facility needs to be accessed for service by a large number of jobs or customers.” Takagi “A queue is formed when service requests arrive at a service facility and are forced to wait while the server is busy working on other requests” 6 Wrap up The study of queuing is the study of waiting Customers may wait on a line Planes may wait in a holding pattern Jobs may wait for the attention of the CPU in an computer Packets may wait in the buffer of a node in a computer network Telephone calls may wait to get through an exchange 7 Real life queuing examples Call center service level Service statement (Regie (public service) du Quebec) If you call the Regie The waiting time to speak with an information clerk is 30 seconds in 75% of cases and you will never wait more than 3 minutes This is one of the commitments that the Regie respect 95% of the time 8 History lesson History goes back to primitive man 9 History of queuing theory Markov Analysis Andrey A. Markov (born 1856). Created the Markov models and produced first results for these processes in 1906 10 History of queuing theory Erlang Analysis Agner Erlang (in 1909): A Danish engineer in the Copenhagen Telephone Exchange, published his first paper on queuing theory 11 Course prerequisite I assume That you are familiar with the pre-requisite knowledge Probability theory Transform theory And matrices Still, I will review some essential background knowledge of certain related disciplines 12 Introduction to probability theory Example 1 Suppose that we toss 2 coins What is the probability that the first coin falls heads? What is the probability that the second coin falls heads? What is the probability that either the first or the second coin falls heads? 13 Solution Sample space (Ω) collection of all possible outcomes Ω = {(H, H), (H,T), (T, H), (T, T)} Possible Events The first coin falls heads E = {(H, H), (H, T)} => Pr (E) = 1/2 The second coin falls heads F = {(H, H), (T, H)} => Pr (F) = 1/2 E F : the event that either the first or second coin falls heads 14 Probability: definition Probability function Pr ( ) Define a mapping between Ω and set of real numbers Assigning a number to each event E in Ω Furthermore, Pr must satisfy, for all A, B in Ω Pr(A) ≥ 0 - probability is a positive measure Pr(A) = (cardinality of A)/(cardinality of Ω) Pr(Ω) = 1 – probability is a finite measure A, B disjoint events => Pr( A B ) Pr( A) Pr( B ) 15 Properties Set of properties Property 1 Property 2 If A B => Pr(A) <= Pr(B) Property 3 Pr (impossible event) = 0 Pr(Ac) = 1 – Pr(A) Property 4: Pr( A B) Pr( A) Pr( B) Pr( A B) 16 Combinatorics Permutations K-permutation of a set of n elements Combinations K-combination of a set of n elements => k-permutation / k! (where k! is the number of possible ways to permute that combination) 17 Combinatorics (cont’d) Binomial coefficients Binomial expansion 18 Conditional probability It enables us to determine whether 2 events A, and B are related in the sense That knowledge about the occurrence of one alters the likelihood of occurrence of the other Probability of A given B has occurred Pr( A | B ) Pr( A B ) => Pr( A B ) Pr( A | B ). Pr( B ) Pr( B ) 19 Conditional probability: Example Example 2 A family has two children What is the conditional probability that both are boys Given that at least one of them is a boy Assumptions: Sample space S = {(b,b), (b,g), (g,b), (g,g)} All outcomes are equally likely For instance, (b,g) means the older child is a boy and the younger child is a girl 20 Solution Let B denote Let A denote the event that both children are boys the event that at least one of them is a boy => 1 Pr( B A) Pr({( b, b)}) 1 Pr( B | A) 4 3 Pr( A) Pr({( b, b), (b, g ), ( g , b)}) 3 4 21 Independent events Two events A and B are independent if Pr(A|B) = Pr(A) Pr( AB) Pr( A). Pr( B ) Example 3 Suppose we roll two fair dice. Let E1 denote the event that the sum of the dice is six and F denote the event that the first die equals four. 22 Analysis of the example 3 P(E1∩F) = Pr({(4,2)}) = 1/36 P(E1)P(F) = 5/36 x 1/6 = 5/216 => E1 and F are not independent Reason Our chance of getting a total of six Depends on the outcome of the first die 23 Example of independent events Let E2 be the event that the sum of dice = 7 Is E2 independent of F? The answer is YES since: P(E2∩F) = Pr({(4,3)}) = 1/36 Equivalent P(E2)P(F) = 1/6 x 1/6 = 1/36 24 Conditional probabilities and Independence 25 Total probability Let B1, B2, …, and Bn be mutually exclusive events Disjoint events whose union equals Ω (partition of sample space) Then, probability of any given event A in Ω Pr( A) Pr( A | B1 ). Pr( B1 ) Pr( A | B2 ). Pr( B2 ) ... Pr( A | Bn ). Pr( Bn ) 26 Baye’s formula Let {B1, B2, …, Bn } be a partition of a sample space The problem is to calculate P(Bi) given A has occurred it enables us to calculate a conditional probability When we know the reverse conditional probabilities 27 Baye’s formula: example Example 4 Three cards with different colours on different sides The upper side of a randomly drawn card is red What is the probability that the other side is blue? Solution (using Baye’s formula) 28