Probability of X or more simultaneous/overlapping events at any point over time period Y given Z agents issuing N events/second of average duration M?

Question

This might be a "please do my homework" question, except I'm a humble developer trying to predict system behavior rather than a student...

I have N devices issuing potentially-expensive http requests - each request takes, say, 2 seconds to complete on average. These devices are making requests at a certain average rate - say every 3 minutes.

My server infrastructure can only handle M simultaneous requests - I need to understand how likely requests are to fail due to "too many concurrent requests".

Initially it's tempting to just simplify to "I have events randomly generated at a certain avg rate, they last a certain avg duration, what is the probability of a certain number of simultaneous events in a certain period", but that doesn't seem to be accurate: At a minimum, it misses the fact that as long as the number of "request issuing agents" is lower than or equal to the "simultaneous request threshold" you're testing for, the probability will clearly be 0...

This seems like something that people must have figured out already, but I can't seem to find anything.

Is the best (only?) way to test this to actually run simulations?

Answer 1

There is something called a "Poisson Birth and Death Process" that might serve you here. A homework problem in a textbook (prob 18 on p.212 of S. Karlin, A first course in stochastic processes) gives a typical result: "A telephone exchange has $m$ channels. Calls arrive in the pattern of a Poisson process with parameter $\lambda$; they are accepted if there is an empty channel, otherwise they are lost. The duration of each call is a r.v. whose distribution is exponential with parameter $\mu$. The lifetimes of separate calls are independent random variables. Find the stationary probabilities of the number of busy channels." The solution: $$p_n =\frac{(\lambda/\mu)^n (1/n!) }{\sum_{k=0}^m (\lambda/\mu)^k (1/k!) }$$ for $n=0,\ldots,n$.

In your problem, $\lambda$ and $\mu$ might be $1/180$ and $1/2$ per second each, so the ratio $\lambda/\mu=1/90$, and $m$ is $M$. If $m=3$, the fraction of time your server is saturated is $p_3 = (90^{-3}/6) / (1+90^{-1}+90^{-2}/2 + 90^{-3}/6)$ , the fraction of time it's idle is $p_0 = 1/(1+90^{-1}+190^{-2}/2 + 90^{-3}/6)$, and so on.

I have no idea if http servers obey the same models that telephone exchanges seem to have obeyed, but this is the kind of model phone companies seem to have used.