Hacker News new | ask | show | jobs
by domano 881 days ago
Hey, can you recommend something one might read to get up to speed on queuing theory? I certainly am not aware of it, but work with queues.
5 comments

I refer to Fundamentals of Queueing Theory by Gross, Shortle, Thompson & Harris.

Although Wikipedia is enough. As far as insights go the topic is relatively simple, it is just bad practice to be re-deriving the first 100 pages of an intro-to-queueing textbook in an emergency.

80% of the time it is enough to assume the process is an M/M/1 queue or consider how the queue would perform relative to an M/M/1 queue. M/M/1 queues are the analog to fitting a straight line, simple & technically incorrect. It is good to move through that part of the day without thinking.

Whenever I talk to operations research people about "how do I learn X?" or "how do I calculate Y?" I usually get told to write a Monte Carlo simulation despite there being a lot of beautiful math involving stochastic processes, generating functions and stuff like that. (Even if you are calculating results in closed form it is still a slam dunk to have a simulation to check the work except when you are dealing with "exceptional event" distributions... That is, a Monte Carlo simulation of a craps game will give you an accurate idea of the odds in many N=10,000 samples, but simulating Powerball takes more like N=1,000,000,000 samples.)

The single "uncommon sense" result you need to know about queuing is

https://erikbern.com/2018/03/27/waiting-time-load-factor-and...

that is, with random arrivals, a queue that has slightly less than 100% utilization will grow stupendously long. People look at a queue with less than 100% and often have a feeling of moral disgust at the "waste" but if you care about the experience of the customer and the reliability of the system you don't let utilization get above about 80% or so.

I learned about this stuff in grad school. The course wasn't mandatory for everyone but my supervisor made it mandatory for me due to the nature of the research I was doing: "Computer Systems and Performance Evaluation". It was basically focused on queuing theory and state space modelling.

Reading through this whole discussion thread really makes me want to dig up my old notes and whip up a blog post with a Jupyter notebook or something that people can use to really dig into this and start to grok what's happening because a lot of it really isn't that intuitive until you've been steeped in it for a while.

If I were you I'd consider using

https://simpy.readthedocs.io/en/latest/

inside a Jupyter notebook.

Hey that's awesome! Unfortunate that I'm going to get even more confused now about whether I'm talking about SimPy or SymPy but that's life :)
Maybe use one for closed form, use their other for the simulation that confirms it!
There are a billion books on abstract or basic queueing theory (worth reading) but a really good modern paper on distributed software implications is https://pure.psu.edu/en/publications/metastable-failures-in-...
Also, in this context, not a bad idea to revisit the broader topic of scheduling.

https://csc-knu.github.io/sys-prog/books/Andrew%20S.%20Tanen...