Seven Insights into Queueing Theory [pdf] | Hacker News Reader

Seven Insights into Queueing Theory [pdf]

treewhimsy.com

133 pointsbshanks17 comments

To anyone who finds these models interesting and wants to learn a lot more - I’d highly recommend Mor Harchol-Balter’s textbook: https://www.amazon.com/Performance-Modeling-Design-Computer-.... (She is currently a professor at Carnegie Mellon).

(Self-repost from an earlier queuing theory thread).

I think you might have a dead link.

Performance Modeling and Design of Computer Systems: Queueing Theory in Action https://www.amazon.com/dp/1107027500

I'm sorry to say that this is not a good book on Performance... The organisation is horrid, the examples are terrible - I hope I don't get downvoted for my opinion.

Negative opinions go over much better when your argument can convince others with more than saying something sucks. Detailed reasoning and experience etc. It also helps to not mention votes.

Yes, however, the interest on this subject is minimal, so I won't bother anybody with my analysis. I bought this book and I sent it back right away, unfortunately.

Eh, I see few enough negative book reviews that ceteris paribus just this much would be enough. It takes time to read a book.

My favorite book on the subject is Telecommunication Networks: Protocols, Modeling and Analysis by Mischa Schwartz. It's one of the rare books that go very deep into the math, but explains it almost step by step, so it is very accessible.

Yes, absolutely, seconded! I was fortunate enough to take her class (which she taught using this book) and I left the class feeling like I really understood things, having proved everything starting from basic probability. The rigor is admirable.

Adding these insights to this intro to queueing theory for developers: https://github.com/joelparkerhenderson/queueing_theory

Despite having a math background, I got stuck on page 1, which is supposed to be definitions, where "Utilization" is used without being defined. With some googling, it turns out this is the ratio of a Poisson parameter to an exponential parameter, under the assumption that arrivals are Poisson distributed and service times are exponentially distributed. Basically, utilization = (average rate of arrivals)*(average service time).

As it's used on the first page, "utilization" is just the fraction of time that the "service center" is in use. So if it's not doing any work at all, it would be 0, fully utilized would be 1. I don't think you need to connect it to Poisson distributions or go into much more depth to use it to understand the gist of the rest of the paper. I assume that since this is an excerpt from a book, it would've been defined elsewhere.

This throws me though. Because if a service center can process one unit per minute, and the average arrival rate is also one unit per minute, I'd assume the utilization was 1 (or 100%). In that scenario I wouldn't expect the queue to be infinitely long. What insight am I missing?

One way to look at is that the utilization is capped at 1, while arrival rate is not.

Assume the processing center can process one unit per minute.

Let's start with a simple case--constant arrival rate at 1 per minute and constant processing rate at 1 per minute.

If the arrival is constant (ie no variation), then indeed the queue size would be 0, because the arrival coincides with completion of processing of previous arrival by the service center. The expected queue wait time is 0.

Now let's look at what happens if arrival rate is variable but average to 1 per minute.

We know the steady state utilization is 1. Because if the utilization is less than 1, the processing center is processing at less than 1 per minute, which means new arrivals would start to fill the queue until the utilization approaches and reaches 1. In other words, the processing center is always busy processing at steady state.

Now, how do we estimate the queue size? Intuitively, we can think about the inter-arrival time. If the next unit arrives at less than 1 minute after the previous, this means the queue grows (since the processing center needs 1 minute to process each unit). Conversely, if the unit arrives more than 1 minute after the previous, the queue shrinks. The number of units in the system (queue + processing center) = queue size + 1. The processing center is always busy, i.e. = 1, and the queue size is lower-bounded at 0 but not upper-bounded. Let p(i) be the probability that the system has i units, at steady state we can express it as,

if i == 0, p(i) = 0

if i > 0, p(i) = p(i-1) * p(inter-arrival time < 0.5) + p(i+1) * p(inter-arrival time > 0.5)

Basically, this says the system will always have at least 1 unit (processing center is always busy), and probability of having i in the system is dependent on probability of previous states i-1 and i+1, and the inter-arrival probability. If the queue size is not bounded, it turns out the p(i) is close to uniform (transition probability from i to i+1 or i-1 is the same at each i, each i feeds into adjacent states, and only boundary condition on i=0), especially for larger i because the boundary condition at i=0 has less effect. And the expected value of a (roughly) uniform distribution that spans (0, inf) is, well, infinite!

Feel free to correct me if I am wrong. I haven't touched probability and queueing theory in a long time.

I was surprised to see no mention of Little's law[1]. It's a simple and powerful little theorem with practical implications.

[1] https://en.wikipedia.org/wiki/Little%27s_law

I've seen a few interesting things pop up on HN recently about queueing theory--this post was also neat: https://kottke.org/19/01/its-time-for-some-queueing-theory

Is this not basically https://en.wikipedia.org/wiki/Amdahl%27s_law

Reply on news.ycombinator.com