Erlang in Erlang

By anders pearson 02 Nov 2013

The FAQ for the Erlang Programming language says:

Erlang is named after the mathematician Agner Erlang. Among other things, he worked on queueing theory. The original implementors also tend to avoid denying that Erlang sounds a little like “ERicsson LANGuage”.

My guess though is that most programmers writing Erlang code don’t really know much about who Agner Erlang was or why his work inspired programmers at Ericsson nearly a century later to name a programming language after him. I wasn’t there, so obviously I can’t speak to exactly what they were thinking when naming the programming language, but I think I can give a bit of background on Agner Erlang’s contributions and the rest should be fairly obvious. In the process of explaining a bit about his work, I simply can’t resist implementing some of his equations in Erlang.

Agner Erlang was a mathematician who worked for a telephone company. At the time, a very practical problem telephone companies faced was deciding how many circuits had to be deployed to support a given number of customers. Don’t build enough and you get busy signals and angry customers. Build too many and you’ve wasted money on hardware that sits idle.

This is a pretty fundamental problem of capacity planning and has clear analogies in nearly every industry. Agner Erlang laid many of the fundamentals for modeling demand in terms of probabilities and developed basic equations for calculating quality of service given a known demand and capacity.

Erlang’s first equation simply defines a unit of “offered traffic” in terms of an arrival rate and average holding time. This unit was named after him.

The equation’s pretty rough. Brace yourself:

$$ E = \lambda h $$

λ is the call arrival rate and h is the call holding time. They need to be expressed in compatible units. So if you have ten calls per minute coming in (λ) and each call lasts an average of 1 minute (h), you have 10 Erlangs of traffic that your system will need to handle. This is pretty fundamental stuff that would later develop into Little’s Law, which I think of as the \(F = ma\) of Queuing Theory.

Implementing this equation in Erlang is trivial:

I call it “Erlang-A” even though I’ve never seen anyone else call it that. His two more well-known, substantial equations are called “Erlang-B” and “Erlang-C” respectively, so you see where I’m coming from.

Let’s look at those two now, starting with Erlang-B.

Erlang-B tells you, given a traffic level (expressed in Erlangs) and a given number of circuits, what the probability of any incoming call has of getting a busy signal because all of the circuits are in use.

This one turns out to be non-trivial. \(E\) is the traffic, \(m\) is the number of circuits:

$$ Pb = B(E,m) = \frac{\frac{E^m}{m!}} { \sum{i=0}^m \frac{E^i}{i!}} $$

I won’t go into any more detail on that equation or how it was derived. If you’ve taken a course or two on Probabilities and Statistics or Stochastic Processes, it probably doesn’t look too strange. Just be thankful that Agner Erlang derived it for us so we don’t have to.

It’s perhaps instructive to plug in a few numbers and get an intuitive sense of it. That will be easier if we code it up.

That equation looks like a beast to program though as it’s written. Luckily, it can be expressed a little differently:

$$ B(E,0) = 1 $$ $$ B(E,m) = \frac{E B(E,m - 1)}{E B(E,m - 1) + m} $$

That actually looks really straightforward to implement in a programming language with recursion and pattern matching. Like Erlang…

I just introduced an intermediate ‘N’ to avoid the double recursion.

Now we can run a few numbers through it and see if it makes sense.

The base case expresses an idea that should be intuitively obvious. If you don’t have any circuits at all, it doesn’t matter how much or how little traffic you are expecting, you’re going to drop any and all calls coming in. \(P_b = 1\).

Similarly, though not quite as obvious from looking at the formula is that if you have no expected traffic, any capacity at all will be able to handle that load. \(B(0, m) = 0\) no matter what your \(m\) is.

The next more complicated case is if you have 1 circuit available. A load of 1 Erlang makes for a 50% chance of dropping any given call. If your load rises to 10 Erlangs, that probability goes up to about 91%.

More circuits means more capacity and smaller chances of dropping calls. 1E of traffic with 10 circuits, \(B(1,10) = .00000001\). Ie, a very, very low probability of dropping calls.

I encourage you to spend some time trying different values and getting a sense of what that landscape looks like. Also think about how that equation applies to systems other than telephone circuits like inventory management, air traffic, or staffing. Clearly this is wide-ranging, important stuff.

Erlang-C builds on this work and extends it with the idea of a wait queue. With Erlang-B, the idea was that if all circuits were in use, an incoming call “failed” in some way and was dropped. Erlang-C instead allows incoming calls to be put on hold until a circuit becomes available and tells you the probability of that happening, again given the expected traffic and number of circuits available:

$$ PW = {{\frac{E^m}{m!} \frac{m}{m - E}} \over \sum{i=0}^{m-1} \frac{E^i}{i!} + \frac{E^m}{m!} \frac{m}{m - E}} $$

Another rough looking one to implement. Once again though, there’s an alternate expression, this time in terms of Erlang-B:

$$ C(E,0) = 1 $$ $$ C(E,m) = \frac{m B(E,m)}{m - E(1 - B(E,m))} $$

Which again, is straightforward to implement in Erlang:

Again, you should try out some values and get a feel for it. An important anomaly that you’ll discover right away is that you can get results greater than 1 when the expected traffic is higher than the number of circuits. This is a little strange and of course in the real world you can never have a probability higher than 1. In this case, it simply represents the fact that essentially, as \({t \to +\infty}\), the wait queue will be growing infinitely long.

I’ll stop here, but it’s important to note that these equations are just the tip of the iceberg. From them you can predict average queue wait times, throughput levels, etc. Given how many different types of systems can be represented in these ways and how applicable they are to real-world problems of capacity planning and optimization, I think it’s now clear why Agner Erlang deserves (and receives) respect in the field.

I guess I should also point out the obvious, that you should do your own research and not trust any of my math or code here. I only dabble in Queuing Theory and Erlang programming so I’ve probably gotten some details wrong. The Erlang code here isn’t meant for production use. In particular, I’m suspicious that it has some issues with Numerical Stability, but a proper implementation would be harder to understand. Ultimately, I just wanted an excuse to write about a topic that I’m fascinated by and make a very long, drawn out “Yo Dawg…” joke.

Tags: programming math erlang queuing theory