Performance Modeling and Design of Computer Systems Quotes

“There is an easy way to remember the formula for Pblock by relating it to the Poisson distribution. Can you see what it is?”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“The applicability of the Erlang-B formula stems from the fact that it is independent of the service time distribution.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“The key question in these types of systems is, “What is the fraction of jobs that are lost?” This fraction is known as the blocking probability, Pblock. We determine the blocking probability by modeling the M/M/k/k queueing system as a CTMC.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“A CTMC is a stochastic process with the property that every time it enters state i, the following hold: 1.   The amount of time the process spends in state i before making a transition is Exponentially distributed with some rate (call it νi). 2.   When the process leaves state i, it will next enter state j with some probability (call it pij) independent of the time spent at state i.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“By the Markovian and stationary properties of the CTMC, the probability that the CTMC leaves state i in the next t seconds is independent of how long the CTMC has already been in state i. That is, P{τi > t + s | τi > s} = P{τi > t} . Question: What does this say about τi? Answer: This says that τi is memoryless. But this means τi is Exponentially distributed!”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“Given a Poisson process with rate λ, suppose that each event is classified “type A” with probability p and “type B” with probability 1 – p. Then type A events form a Poisson process with rate pλ, type B events form a Poisson process with rate (1 – p)λ, and these two processes are independent.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“Given two independent Poisson processes, where process 1 has rate λ1 and process 2 has rate λ2, the merge of process 1 and process 2 is a single Poisson process with rate (λ1 + λ2).”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“(9.17) Yet this says that the stationary equations are simply relating the total rate of transitions out of state i with the total rate of transitions into state i: Total rate leaving state i = Total rate entering state”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“πi Pij = “rate” of transitions from state i to state j. To see this, observe that the DTMC is in state i for πi fraction of all time steps. Furthermore, Pij fraction of those time steps will result in the chain next moving to j. Hence, for πiPij fraction of all time steps, the DTMC is in state i, and its next step is to go to state j. Thus, if we look over t time steps (let t be large), then πiPijt transitions will have their start point in i and their end point in j. Dividing by t, we see that the rate of transitions (number of transitions per time step) that have their start point in i and their end point in j is πiPij. Question: What does Σj πiPij represent? Answer: This is the total rate of transitions out of state i, including possibly returning right back to state i (if there are self-loops in the chain).”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“for periodic chains, when the solution to the stationary equations exists, it does not represent the limiting distribution, but rather it represents the long-run time-average fraction of time spent in each state.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“we never have to actually determine whether our DTMC is positive recurrent. It suffices to simply check for irreducibility and aperiodicity and then solve the stationary equations. If these stationary equations yield a distribution, then that distribution is also the limiting probability distribution.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“As defined, πj is a limit. Yet it is not at all obvious that the limit πj exists! It is also not obvious that represents a distribution (i.e., Σi πi = 1),”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“πj represents the limiting probability that the chain is in state j (independent of the starting state i). For an M-state DTMC, with states 0, 1, . . . , M – 1, represents the limiting distribution of being in each state.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“The Markovian Property states that the conditional distribution of any future state Xn+1, given past states X0, X1, . . . , Xn–1, and given the present state Xn, is independent of past states and depends only on the present state Xn.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“Given any system where Time Avg, Time Avg, λ, and X exist and where λ = X, then Time Avg = λ · Time Avg. Observe that Little’s Law is stated as an equality between time averages, not ensemble averages. Little’s Law says that the time-average number in system for sample path ω is equal to λ times the time-average time in system for that sample path. However, we know that if we assume that the system is also ergodic, then the time average converges to the ensemble average with probability 1; namely, on almost every sample path, the time average on that sample path will be equal to the ensemble average over all paths (see Section 5.3). Thus, assuming ergodicity, we can apply Little’s Law in an ensemble-average sense,”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“Aperiodicity refers to the fact that the system state (number of jobs in the system) should not be tied in some particular way to the time step; for example, it should not be the case that the system is always in state 0 for even time steps and state 1 for odd time steps; otherwise, the particular t that Enzo picked for stopping the system might sway his result.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“Every time that the system empties (0 jobs), the process starts anew in state 0. We call this a “restart.” In a positive recurrent system, the system empties infinitely often.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“Given an irreducible system, in which we can get to any state, the system is positive recurrent if for any state i, the state is revisited infinitely often, and the mean time between visits to state i (renewals) is finite.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“Irreducibility says that a process should be able to get from any state to any other state”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action

“An ergodic system is one that is positive recurrent, aperiodic, and irreducible.”
― Mor Harchol-Balter, Performance Modeling and Design of Computer Systems: Queueing Theory in Action