6 ms·

Where does one start with understanding and applying queueing theory to real world problems? I manage a system that receives a highly variable number of request

Where does one start with understanding and applying queueing theory to real world problems? I manage a system that receives a highly variable number of requests that are queued for processing by a horizontally scalable number of VMs up to a resource cap. Success of this system is based on the 95p of aggregate processing times over a specified time period being below a certain threshold value. It’s my responsibility to manage the system such that this threshold is always met. I also need to pre-allocate additional system capacity to the right bottlenecks based on predicted increases in demand. So it sounds like knowing queuing theory could be a big help. Where do I begin?

kqr 4y ago
The practical answer is to simulate it. Even if you knew a bunch of queueing theory, you would end up simulating something like this. If you want inspiration and some background, though, I can strongly recommend the book mentioned downthread: http://www.performancemodeling.org/ http://www.performancemodeling.org/ You're absolutely right that queueing theory would be helpful. A little part of me is wondering how on Earth you're doing your job without it!
- toolslive 4y ago
  Yes, even the experts quickly go "pfff, this is getting too complicated, let's simulate"
- kfarr 4y ago
  Correct, in real life queued objects (or people) are "agents" that exhibit imperfect behavior that doesn't really adhere to a perfect queuing equation. Classic example is motor vehicle throughput: queuing equations might be helpful in broad strokes for coarse estimates but need agent level simulation to accurately predict outcome.
- setr 4y ago
  I’ve implemented queuing simulators in the past, but two questions I’ve always been bugged by (which I feel like are easily answered if I ever took proper math courses…): 1. I don’t understand how you “know” you’re in the steady state, beyond looking at the graph — I’ve always just made it go like 10k steps to force it, but this seems needlessly wasteful. I imagine you could track the derivative but if it oscillates? 2. I don’t know how to verify if the distributions are poisson/exponential in reality, except by plotting More relevant note, I’ve always been surprised by how little exists online on the subject, and how little code it actually requires; I forget the terms but multiple event classes, multiple agent, infinite buffer sim took maybe 100 LoC C# from stdlib. Maybe 60 LoC in python — probably 25% was just tracking the stats I wanted like wait time. Biggest performance trick is that poison inter-arrival rate is exponential, and so you can generate all arrival times up front; then instead of simulating every second, you can just skip forward in time to when the events actually occur… so your sim scales on number of events occurring, rather than length of time simulated. Pretty sure you can even do arbitrarily length simulations in constant memory but never tried
mjb 4y ago
Simulation, as kqr said. I like to use the classic queue theory results (e.g. results on M/M/1 and M/M/c) as unit tests for the simulators I build. I've found that application of queue theory very helpful in avoiding silly simulation bugs.

kqr 4y ago

The practical answer is to simulate it. Even if you knew a bunch of queueing theory, you would end up simulating something like this. If you want inspiration and some background, though, I can strongly recommend the book mentioned downthread: http://www.performancemodeling.org/ http://www.performancemodeling.org/ You're absolutely right that queueing theory would be helpful. A little part of me is wondering how on Earth you're doing your job without it!

toolslive 4y ago
Yes, even the experts quickly go "pfff, this is getting too complicated, let's simulate"
kfarr 4y ago
Correct, in real life queued objects (or people) are "agents" that exhibit imperfect behavior that doesn't really adhere to a perfect queuing equation. Classic example is motor vehicle throughput: queuing equations might be helpful in broad strokes for coarse estimates but need agent level simulation to accurately predict outcome.
setr 4y ago
I’ve implemented queuing simulators in the past, but two questions I’ve always been bugged by (which I feel like are easily answered if I ever took proper math courses…): 1. I don’t understand how you “know” you’re in the steady state, beyond looking at the graph — I’ve always just made it go like 10k steps to force it, but this seems needlessly wasteful. I imagine you could track the derivative but if it oscillates? 2. I don’t know how to verify if the distributions are poisson/exponential in reality, except by plotting More relevant note, I’ve always been surprised by how little exists online on the subject, and how little code it actually requires; I forget the terms but multiple event classes, multiple agent, infinite buffer sim took maybe 100 LoC C# from stdlib. Maybe 60 LoC in python — probably 25% was just tracking the stats I wanted like wait time. Biggest performance trick is that poison inter-arrival rate is exponential, and so you can generate all arrival times up front; then instead of simulating every second, you can just skip forward in time to when the events actually occur… so your sim scales on number of events occurring, rather than length of time simulated. Pretty sure you can even do arbitrarily length simulations in constant memory but never tried

mjb 4y ago

Simulation, as kqr said. I like to use the classic queue theory results (e.g. results on M/M/1 and M/M/c) as unit tests for the simulators I build. I've found that application of queue theory very helpful in avoiding silly simulation bugs.