Sunday, October 28, 2007

Erlang's Collected Papers

In 1948, the collected papers of Agner Erlang (AKA the father of queueing theory) were translated from the original Danish and published in the Transactions of the Danish Academy of Technical Sciences. They were reissued as a book by Acta Polytechnica Scandinavica in 1960, but due its underwhelming popularity, that book is now out of print. However, I just discovered that the chapters of the book are now available on the web. Kudos to the Academy!

I have an abiding interest in this material, not just because it's seminal and carries a lot of history (albeit less than 100 years), but I don't like the way the Erlang equations are usually derived. Before all his papers were posted on the web (which seems to have been around 2004), I only had photocopies of his 1909 and 1917 papers. I wanted to see if the originator, struggling to develop the early theory, offered more intuition than is presented in the standard derivations found in queueing theory textbooks today. I was quickly disappointed to find that, in some sense, he is more obscure than modern texts. Markov chains (1907) had yet to be applied to queues, so Erlang resorts to direct probability-theoretic arguments which are even less intuitive.

I want to construct a derivation that is more intuitive and in keeping with the approach I took in The Practical Performance Analyst. My best shot, so far, appears in Sections 2.6 and 2.7 of my Perl::PDQ book. There, I demonstrate that the Erlang M/M/m queue acts like a set of m parallel μ-speed queues under light traffic load, but "morphs" into a fast M/M/1 queue with service rate mμ under heavy traffic. Unfortunately, the residence time formula (equation 2.63 in my Perl::PDQ book) that results from generalizing this morphing intuition, is not the exact Erlang formula but a good approximation only. Mathematically, this approximation turns out to be related to the difference between a finite geometric series and the required finite exponential series. More recently, however, I have come a lot closer to the exact formula and I hope to have something more to say about that shortly.

"All things come to those who wait."
(but hopefully, not too late)

In the meantime, here are some of my observations on Erlang's 1917 paper which you might care to ponder as you read it:

  • He never uses the term queue. Instead, Erlang refers to "waiting arrangements" for delayed calls.
  • He doesn't indicate how such waiting arrangements might be implemented, e.g., buffer.
  • He introduces terms like traffic intensity (the letter y in his notation), which is still used today and expressed in units of Erlangs, even though it's dimensionless.
  • He does not develop his solutions by starting with the simpler M/M/1 queue. He solved the M/D/1 "one circuit" case in 1909.
  • He employs a constant (deterministic) service time with S=1 in his explicit derivations.
  • He solves much more than the M/M/m queue e.g., M/D/{1,2,3} which are non-Markovian queues! Hence, some of his "proofs" are not entirely kosher, but were only cleaned up many years later.
  • It's well-known that Erlang conjectured his results were also applicable to M/G/... type queues, but that was not proven for another 40 years.

The collected papers reveal that even though Erlang is best known today for the B and C formulae in his 1917 paper, he single-handedly developed considerably more queueing theory over the course of about 20 years. Indeed, he rightly deserves the mantle of The Father of Queueing Theory.

No comments: