Understanding Queueing Theory in Computer Networks
Queueing theory is a powerful analytic tool used to analyze performance in queueing processes, applicable in various industries including retail, manufacturing, and computer networks. It involves studying characteristics such as arrival patterns, service patterns, and queue disciplines to make performance statements. Queueing systems are described by their arrival patterns, service patterns, and queue disciplines, which influence customer behavior and service efficiency. Through understanding these aspects, network administrators can optimize network performance and efficiency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Queueing Theory 14-740: Fundamentals of Computer Networks Credit: Bill Nace Material from Computer Networking: A Top Down Approach, 6thedition. J.F. Kurose and K.W. Ross
traceroute QT Overview Performance Evaluation Little s Law Rate Transition Diagrams M/M/1 Systems M/M/c Systems Examples 14-740: Fall 2017 2
Queueing Theory An analytic tool to make performance statements about queueing processes Very applicable: retail, manufacturing, ... Network uses: routers, transport, ... 14-740: Fall 2017 3
Queueing System Describe via six characteristics Arrival pattern Service pattern Queue discipline System capacity # of service channels # of service stages 14-740: Fall 2017 4
#1: Arrival Pattern Often, arrivals are stochastic Need to know the PDF of interarrival times Sometimes, arrive in batches or in bulk Need the PDF of batch size A stationary arrival pattern doesn t change with time 14-740: Fall 2017 5
Impatient Customers Customer reaction is sometimes impatient Balk is when a customer refuses to enter Renege is when customer leaves Customer may jockey for position by switching input queues Network packets rarely do any of these 14-740: Fall 2017 6
#2: Service Pattern Similar to arrival patterns, service patterns are often stochastic Described by a PDF of customer service times A state-dependent server changes based on the number of customers waiting Server may get flustered or work faster Service can be stationary or nonstationary 14-740: Fall 2017 7
#3: Queue Discipline The manner in which customers are chosen from the queue for service First Come First Served (FCFS) Last Come First Served Useful for stack based or inventory systems Random Service Selection (RSS) Priority Schemes 14-740: Fall 2017 8
#4: System Capacity Is there a physical limitation to the number of customers in the queue? Common in real life Buffer memory in a router # of chairs for waiting at barber shop Often ignored to simplify the analysis 14-740: Fall 2017 9
#5: Multiple Service Channels Adding servers increases capacity How do customers wait? Single queue can feed many servers Each server may have its own queue 14-740: Fall 2017 10
#6: Stages of Service In a multistage queueing system, customers exit one service only to start waiting for another service Doctor s Office: check-in, history, exam, tests, re-exam, payment Some systems allow feedback (recycling parts is common in manufacturing) 14-740: Fall 2017 11
Greek Lambda Arrival rate ? Mu Service rate Rarer: Scale (1/rate) Rho Utilization (probability of being busy) 14-740: Fall 2017
Kendall53s A/B/X/Y/Z Notation Characteristic Symbol Explanation M Exponential Interarrival-time distribution (A) D Deterministic Ek Erlang type k Hk k exponentials Service-time distribution (B) PH Phase Type G General # parallel servers (X) 1, 2, 3... , Max capacity (Y) 1, 2, 3... , FCFS First come, first served LCFS Last come, first served Queue Discipline (Z) RSS Random Selection for Service PR Priority GD General Discipline 14-740: Fall 2017 13
Kendall53s A/B/X/Y/Z Notation Characteristic Symbol Explanation M Exponential Interarrival-time distribution (A) D Deterministic Ek Erlang type k Hk k exponentials Service-time distribution (B) PH Phase Type G General # parallel servers (X) 1, 2, 3... , Max capacity (Y) 1, 2, 3... , FCFS First come, first served LCFS Last come, first served Queue Discipline (Z) RSS Random Selection for Service PR Priority GD General Discipline 14-740: Fall 2017 14
Exponential the exponential distribution is the probability distribution that describes the time between events in a Poisson point process, i.e., a process in which events occur continuously and independently at a constant average rate. (Wikipedia) 14-740: Fall 2017
Deterministic In mathematics, a degenerate [Deterministic] distribution is a probability distribution in a space (discrete or continuous) with support only on a space of lower dimension. If the degenerate distribution is univariate (involving only a single random variable) it is a deterministic distribution and takes only a single value. Examples include a two-headed coin and rolling a dice whose sides all show the same number. (Wikipedia) 14-740: Fall 2017
Erlang The Erlang distribution is a two parameter family of continuous probability distributions The two parameters are: a positive integer k, the "shape", and a positive real number , the "rate". The "scale , ?, the reciprocal of the rate, is sometimes used instead. The Erlang distribution was developed by A. K. Erlang to examine the number of telephone calls which might be made at the same time to the operators of the switching stations. This work on telephone traffic engineering has been expanded to consider waiting times in queueing systems in general. The distribution is now used in the fields of stochastic processes and of biomathematics. Events that occur independently with some average rate are modeled with a Poisson process. The waiting times between k occurrences of the event are Erlang distributed. (Wikipedia) 14-740: Fall 2017
General Known mean and variance, but nothing else. 14-740: Fall 2017
Markovian A Markov chain is "a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event." In probability theory and related fields, a Markov process, named after the Russian mathematician Andrey Markov, is a stochastic process that satisfies the Markov property (Wikipedia) 14-740: Fall 2017
Common Queueing Systems G/G/1 General, single server system G/G/c General, multi-server system G/G/ General, self-serve system M/M/1 Markovian, single server M/M/c Markovian, multi-server M/M/c/k Multi-server, with limited size Infinite system size and FCFS discipline are always assumed as the defaults 14-740: Fall 2017 20
traceroute QT Overview Performance Evaluation Little s Law Rate Transition Diagrams M/M/1 Systems M/M/c Systems Examples 14-740: Fall 2017 21
Parameters is the average arrival rate # customers or packets per second is the average service rate # packets served per second c is number of servers 14-740: Fall 2017 22
Traffic intensity / c A measure of traffic congestion in the servers When > 1, average # of arrivals exceeds service capability bad When = 1, randomness prevents queues from emptying (unless perfectly scheduled deterministic arrivals) bad Steady state only when < 1 14-740: Fall 2017 23
# of customers N(t) is number of customers in the system Sum of Nq(t) and Ns(t), for queues and service Expected number in system Expected number in queue Where pn is Pr{N=n}, probability of a particular number n customers in the system 14-740: Fall 2017 24
# of customers N(t) is number of customers in the system Sum of Nq(t) and Ns(t), for queues and service Expected number in system Expected number in queue Where pn is Pr{N=n}, probability of a particular number n customers in the system 14-740: Fall 2017 25
Time TI is interarrival time (time between successive arrivals) Tq is time spent in queue S is service time T is total time T = Tq + S 14-740: Fall 2017 26
Littles Law the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate multiplied by the average time W that a customer spends in the system. (Wikipedia) 14-740: Fall 2017
Littles Law Relationship between # customers and the waiting time W is the mean waiting time in the system W = E[ T ] and Wq = E[ Tq ] Little s Law: L = W ( and Lq = Wq ) Especially powerful when combined with E[ T ] = E[ Tq ] + E[ S ] to get W = Wq + 1/ Given , and any 1 of {W, Wq, L, Lq} can get rest 14-740: Fall 2017 28
Further Results What is E[ Ns ]? L - Lq = (W - Wq) = (1/ ) = / r / For c=1, r = and 14-740: Fall 2017 30
Busy Probability For a G/G/c system, Pb is the probability of a given server being busy At steady state, E[ Ns ] = r Servers are identical, so E[Na server] = r/c = Pb Recall that = / c and r = / Therefore, Pb = 14-740: Fall 2017 31
traceroute QT Overview Performance Evaluation Little s Law Rate Transition Diagrams M/M/1 Systems M/M/c Systems Examples 14-740: Fall 2017 33
Birth-death process A type of continuous-time Markov chain System modeled as a set of states Transitions occur between adjacent states When in state n, an arrival moves the system to state n+1 When in state n > 0, a departure moves the system to state n-1 14-740: Fall 2017 34
Rate Transition Diagram Describes the number of customers in the system Customers arrival time is an exponential random variable with rate n Likewise, departure is random with rate n 14-740: Fall 2017 35
Flow-balance Equations pn is the probability of being in state n The system is in steady-state, therefore: ( n+ n)pn = n-1pn-1 + n+1pn+1 for n 1 0p0 = 1p1 14-740: Fall 2017 36
My apologies for the derivation! Rewriting the flow-balance equations: Do some inductive reasoning: Which leads to: Similarly: 14-740: Fall 2017 38
traceroute QT Overview Performance Evaluation Little s Law Rate Transition Diagrams M/M/1 Systems M/M/c Systems Examples 14-740: Fall 2017 39
M/M/1 Systems Exponentially distributed because Independent of state of the system 14-740: Fall 2017 40
M/M/1 Flow Balance Eqns Rewrite the G/G/c eqns with and n = and n = for all n Now what? We need to know what p0 is! 14-740: Fall 2017 41
M/M/1 Flow Balance Eqns Rewrite the G/G/c eqns with and n = and n = for all n Now what? We need to know what p0 is! 14-740: Fall 2017 42
Probabilities must add to 1 (Remember = /c and c=1 server) 14-740: Fall 2017 43
Probabilities must add to 1 (Remember = /c and c=1 server) 14-740: Fall 2017 44
Plug p0 into Flow-Balance This final equation is incredibly useful, as it allows us to determine probabilities of system state, given only and Also allows us to generate measures of effectiveness 14-740: Fall 2017 45
Plug p0 into Flow-Balance This final equation is incredibly useful, as it allows us to determine probabilities of system state, given only and Also allows us to generate measures of effectiveness 14-740: Fall 2017 46
Measures of Effectiveness Manipulating the summation (via the derivative of the version without n inside) 14-740: Fall 2017 48
More Measures of Effectiveness Avg size of nonempty queue 14-740: Fall 2017 49
More Measures of Effectiveness Avg size of nonempty queue 14-740: Fall 2017 50
traceroute QT Overview Performance Evaluation Little s Law Rate Transition Diagrams M/M/1 Systems M/M/c Systems Examples 14-740: Fall 2017 51
M/M/c Systems How are things different with multiple servers? Arrival rate is still constant Service rate is not System has service capability of c Assuming c customers to service 14-740: Fall 2017 52
Rate Transition Diagram Discontinuity caused by limited # servers Service rate determined by number of servers in use... ... capped by number of available servers 14-740: Fall 2017 53
Similar derivation to M/M/1 14-740: Fall 2017 54
