Queuing TheoryTheoryApplicabilityValidationOperational PrinciplesStochastic HypothesisSupplementary HypothesesOperational Variables, Laws, and TheoremsOperational Analysis ComponentsObservation PeriodOperational VariablesBasic QuantitiesDerived QuantitiesSingle Server Queuing SystemOperational LawJob Flow BalanceOperational TheoremK-Device Queuing NetworkK-Device SystemK-Device System - QueuesTwo-Device System – open vs closedSlide 22Central Server NetworkTerminal Driven SystemMixed SystemBasic Operational QuantitiesOutside WorldPossible CombinationsArrivals and DeparturesEquilibriumOperational Quantity DefinitionsRouting FrequenciesSystem Output RateOutput Flow LawUtilization LawQueuesni (t) ExampleMean Queue LengthResponse TimeLittle’s LawExample 1Example 1(Cont)Slide 43Job Flow Balance EquationsVisit RatiosForced Flow LawExample 2Visit Ratio EquationsExample 3 Central ServerEx 3 – Job Flow EquationsEx 3 – Visit Ratio EquationsEx 3 – Visit Ratio Equations (Cont)Ex 3 – Visit RatiosSlide 54General Response Time LawInteractive Response Time FormulaOperational EquationsExample 4 - ConditionsExample 4 - SolutionExample 5 – ConditionsEx 5 – Interactive ThroughputEx 5 – Disk ThroughputEx 5 – Batch ThroughputEx 5 – Triple Batch ThroughputEx 5 – Maximum Disk ThroughputEx 5 – New Interactive ThroughputEx 5 – New Interactive Response TimeBottleneck AnalysisRatiosSaturationBottleneck DeviceMaximum ThroughputMinimum ThroughputJob InterferenceSystem ThroughputSlide 76Terminals in SaturationSlide 78Interactive SystemSlide 80Example 6Example 6 – Vi Si ProductsExample 6 – SaturationResponse Time CurveExample 7 – ConditionsExample 7 – SolutionExample 8Example 8 – Response Time AsymptoteExample 8 – Faster CPU?Example 8 – Faster CPUResponse Time AsymptotesExample 9Example 9 – Current CPUExample 9 – Infinitely Fast CPUExample 9 – 50 TerminalsQueuing Theory•The system is modeled by a stationary stochastic process•Jobs are stochastically independent•Job steps from device to device follow a Markov chain•The system is in stochastic equilibrium•The service time requirements at each device conform to an exponential distribution•The system is ergodic – i.e., long term time averages converge to the values computed for stochastic equilibriumTheory•The theory of queuing networks based on these assumptions is usually called “Markovian queuing network theory•Italicized words in the pervious slide illustrate concepts that the analyst must understand to be able to deploy the models•Some concepts are difficult•Some, such as “equilibrium” or “stationary,” cannot be proved to hold by observing the system in a finite time period•Most can be disproved empirically – For example, parameters change over time, jobs are dependent, device-to-device transitions do not follow Markov chains, systems are observable only for short periods, and service distributions are seldom exponentialApplicability•It is a surprise that these models apply so well to systems which violate so many assumptions of the analysisValidation•When applying or validating the results of Markovian queuing network theory, analysts substitute operational (i.e., directly measured) values for stochastic parameters in the equations•The repeated successes of validations led us to investigate whether the traditional equations of Markovian queuing network theory might also be relations among operational variables, and, if so, whether they can be derived using different assumptions that can be directly verified and that are likely to hold in actual systemsOperational Principles•All quantities should be defined so as to be precisely measurable, and all assumptions stated so as to be directly testable. The validity of results should depend only on assumptions which can be tested by observing a real system for a finite period of time•The system must be flow balanced – i.e., the number of arrivals at a given device must be (almost) the same as the number of departures•The devices must be homogeneous – i.e., the routing of jobs must be independent of local queue lengths, and the mean time between service completions at a given device must not depend on the queue lengths of other devicesStochastic HypothesisThe behavior of the real system during a given period of time is characterized by the probability distributions of a stochastic processSupplementary Hypotheses•Supplementary hypotheses are usually also made•They typically introduce concepts such as state, ergodicity, independence, and the distributions of specific random variables•These hypotheses constitute a stochastic modelOperational Variables, Laws, and Theorems•Hypotheses whose veracity can be established beyond doubt by measurement will be called operationally testable•Operational analysis provides a rigorous mathematical discipline for studying computer system performance based solely on operationally testable hypothesesOperational Analysis Components•A system that can be real or hypothetical•A time period, which may be past, present, or future•The objective of an analysis is equations relating quantities measurable in the system during the given time periodObservation Period•A finite time period in which a system is observed•An operational variable is a formal symbol that stands for the value of some quantity which is measurable during the observation period•It has a single, specific value for each observation periodOperational Variables•Operational variables are either:–Basic quantities, which are directly measured during the observation period–Derived quantities which are computed from the basic quantitiesBasic QuantitiesT – the length of the observation periodA – the number of arrivals occurring during the observation periodB – the total amount of time during which the system is busy during the observation period (B <= T)C – the number of completions occurring during the observation periodBasic quantities (A, B, C) are typical of “raw data” collected during an observationDerived Quantities= A/T the arrival rate (jobs/second)X = C/T, the output rate (jobs/second) U = B/T, the utilization (fraction of time system is busy) S = B/C, the mean service time per completed jobsDerived quantities (, X, U, S) are typical of “performance measures” – they are variables that may change from one observation period to anotherqueue  X Server A