The Erlang C Formula

The Erlang C formula has a fairly interesting structure. Take a look:

\[ P_w = \frac{\frac{t^n}{n!}\frac{n}{n-t}}{\left( \sum\limits_{i=0}^{n-1} \frac{t^i}{i!} \right) + \frac{t^n}{n!} \frac{n}{n-t}} \]

\(t\) is the total inbound traffic, in erlangs (an erlang is 100% usage of a single line for one hour). \(n\) is the number of servers you have handling all this traffic. What this formula gives us back is \(P_w\), the probability that any given caller in to the system will have to wait instead of being served immediately.

Knowing this probability then gives us ways to analyze how many traffic servers we should provide, if we know at least a little bit about the amount of traffic the system will have to handle.

Computationally, there are a few interesting pieces to Erlang C. First of all, there’s the part that’s repeated exactly as the numerator and as a summand in the denominator. We can abstract this away so we only have to compute it once.

\[ P_w = \frac{x}{\left( \sum\limits_{i=0}^{n-1} \frac{t^i}{i!} \right) + x } \: \: \mathrm{where} \: x = \frac{t^n}{n!} \frac{n}{n-t} \]

Warning: ad-hoc guesstimation incoming!

Even using the most naive methods, we can calculate \(x\) in time at most linear in either \(n\) or \(t\), so we’re not doing too badly there. We can use either memoization on a table of factorials, or for small enough \(n\) just calculate directly. The summation calculates \(i!\) but does it \(n\) times where \(i\) is bounded by \(n\), so a simple upper bound there assuming linear factorials is $(n^2) $. With memoization for factorials, we reduce to a simple linear bound.

All this is assuming fairly straightforward implementations with naive big \(\mathcal{O}\) approximations attached. For example, factorial could realistically be computed in \(\mathcal{O}(n (\log n)^3 \log \log n)\) time¹. To be faster, we could use Stirling’s approximation since our amount of traffic is an estimate anyways. However, everything actually runs pretty fast for how complicated the formula seems at first glance!

Of course, we’re also making some other pretty strong assumptions (e.g. that multiplication speed is constant for arbitrarily large numbers). As a rough estimate, it seems this computation is somewhere between \(\mathcal{O}(n)\) and \(\mathcal{O}(n^2)\). In practice, \(t\) may grow pretty fast, but you’re not likely to have a huge \(n\) (how many places have a million servers in their data centers)?

As I’ve hinted at, you’d likely be able to memoize much more of the work away if for some reason you needed to calculate Erlang C repeatedly. Finally, just knowing we should interpret the result as a probability might ease our worries. There’s not too much difference between a 10% chance of having to wait versus an 11% chance.