Wednesday, March 15, 2017

Morphing M/M/m: A New View of an Old Queue

The following abstract has been accepted for presentation at the 21st Conference of the International Federation of Operational Research Societies — IFORS 2017, Quebec City, Canada.

  • Update July 31, 2017: Here are my IFORS slides
  • Update June 08, 2018: In response to an audience question at my IFORS 2017 session, I have now demonstrated that there is an upper bound for the error in the morphing approximation. See footnotes below.
  • Update August 18, 2020: This new paper has the complete exact solution method that I had been seeking all along.

This year is the centenary of A. K. Erlang's paper [1] on the determination of waiting times in an M/D/m queue with $m$ telephone lines.* Today, M/M/m queues are used to model such systems as, call centers [3], multicore computers [4,5] and the Internet [6,7]. Unfortunately, those who should be using M/M/m models often do not have sufficient background in applied probability theory. Our remedy defines a morphing approximation to the exact M/M/m queue [3] that is accurate to within 10% for typical applications. The morphing formula for the residence-time, $R(m,\rho)$, is both simpler and more intuitive than the exact solution involving the Erlang-C function. We have also developed an animation of this morphing process. An outstanding challenge, however, has been to elucidate the nature of the corrections that transform the approximate morphing solutions into the exact Erlang solutions. In this presentation, we show:
  • The morphing solutions correspond to the $m$-roots of unity in the complex $z$-plane.
  • The exact solutions can be expressed as a rational function, $R(m,z)$.
  • The poles of $R(m,z)$ lie inside the unit disk, $|z| < 1$, and converge around the Szego; curve [8] as $m$ is increased.
  • The correction factor for the morphing model is defined by the deflated polynomial belonging to $R(m,z)$.
  • The pattern of poles in the $z$-plane provides a convenient visualization of how the morphing solutions differ from the exact solutions.

* Originally, Erlang assumed the call holding time, or mean service time $S$, was deterministic with unit period, $S=1$ [1,2]. The generalization to exponentially distributed service periods came later. Ironically, the exponential case is easier to solve than the apparently simpler deterministic case. That's why the M/D/1 queue is never the first example discussed in queueing theory textbooks.
† The derivation of the morphing model is presented in Section 2.6.6 of the 2005 edition of [4], although the word "morphing" is not used there. The reason is, I didn't know how to produce the exact result from it, and emphasizing it would likely have drawn unwarranted attention from Springer-Verlag editors. By the time I was writing the 2011 edition of [4], I was certain the approximate formula did reflect the morphing concept in its own right, even though I still didn't know how to connect it to the exact result. Hence, the verb "morphs" timidly makes its first and only appearance in the boxed text following equation 4.61.
‡ The relative error peaks at 10% for $m \sim 20$ and $\rho \sim 90\%$, then peaks again at 20% for $m \sim 2000$ and the servers running 99.9% busy. However, the rate of increase in peak error attenuates such that the maximum error is less than 25%, even as $m \rightarrow \infty$ and $\rho \rightarrow 100\%$. A plot of the corresponding curves gives a clearer picture. This behavior is not at all obvious. Prior to this result, it could have been that the relative error climbed to 100% with increasing $m$ and $\rho$.

References

  1. A. K. Erlang, "Solution of Some Problems in the Theory of Probabilities of Significance in Automatic Telephone Exchanges," Electroteknikeren, v. 13, p. 5, 1917.
  2. A. K. Erlang, "The Theory of Probabilities and Telephone Conversations," Nyt Tidsskrift for Matematik B, vol 20, 1909.
  3. E. Chromy, T. Misuth, M. Kavacky, "Erlang C Formula and Its Use In The Call Centers," Advances in Electrical and Electronic Engineering, Vol. 9, No. 1, March 2011.
  4. N. J. Gunther, Analyzing Computer System Performance with Perl::PDQ, Springer-Verlag, 2005 and 2011.
  5. N. J. Gunther, S. Subramanyam, and S. Parvu, "A Methodology for Optimizing Multithreaded System Performance on Multicore Platforms," in Programming Multicore and Many-core Computing Systems, eds. S. Pllana and F. Xhafa, Wiley Series on Parallel and Distributed Computing, February 2017.
  6. N. J. Gunther, "Numerical Investigations of Physical Power-law Models of Internet Traffic Using the Renormalization Group," IFORS 2005, Honolulu, Hawaii, July 11—15.
  7. T. Bonald, J. W. Roberts, "Internet and the Erlang formula," ACM SIGCOMM Computer Communication Review, Volume 42, Number 1, January 2012.
  8. C. Diaz Mendoza and R. Orive, "The Szegő curve and Laguerre polynomials with large negative parameters," Journal of Mathematical Analysis and Applications, Volume 379, Issue 1, Pages 305—315, 1 July 2011.

9 comments:

ks said...

Hi,
How does this compare to approximations:
1. section 2.7 of Analyzing Computer System Performance With Perl::PDQ
R approx. equal to S/(1 - Power(p,M))

2. In 1977,Hirotaka Sakasegawa wrote a paper that describes the derivation and behavior of a more accurate approximation. This is mentioned in "The Essential Guide To Queueing Theory" by Barron Schwartz

ks said...

Hi,
How does this compare to approximations:
1. section 2.7 of Analyzing Computer System Performance With Perl::PDQ
R approx. equal to S/(1 - Power(p,M))

2. In 1977,Hirotaka Sakasegawa wrote a paper that describes the derivation and behavior of a more accurate approximation. This is mentioned in "The Essential Guide To Queueing Theory" by Barron Schwartz

Neil Gunther said...

The formula you quote from my PPDQ book is what I now boldly refer to as the "morphing model" or morphing approximation to the exact result for R in M/M/m (which Erlang published in 1917). In my book, I prove that the morphing approximation can be derived analytically from a truncated geometric series. In my IFORS talk, I prove that the exact result corresponds to a truncated exponential series and the analytic bridge between the two (the thing I'd been searching for) involves a very complicated m-th degree polynomial in ρ (which is why it took me so long to find it). Although its form is completely unintuitive, it becomes far more transparent by visualizing the asymmetric location of its zeros and poles in the complex plane. The corresponding morphing approximation is simply the symmetric m-th roots of unity.

The Sakasegawa result seems to be nothing more than numerical voodoo. It offers no insight into the analytic structure of R or C, as far as I can tell. Moreover, I've never seen that result cited in textbooks written by serious queueing theorists. If you just want numbers, and don't care where they come from, why bother with approximations? Just encode the exact Erlang formula. The exact algorithm (a few lines of code or an Excel macro) is also in my book. See p.85 of the 2004 edition or p.125 (Listing 4.6) of the 2nd edition.

Neil Gunther said...
This comment has been removed by the author.
Neil Gunther said...

Here is the visualization in the complex plane for m = 1, 2, 3, up to 256 servers. You see the (green) morphing model zeros densely sitting on the circumference, whereas the Erlang zeros coalesce around the (red) Szego curve inside the unit disk.

Quite apart from its own intriguing beauty, this visualization provides a stark realization of how by simply adding another server to an M/M/1 queue puts you on the road to unbelievable complexity. No wonder it took A.K. Erlang almost 10 years to solve it. :)

Neil Gunther said...

Another virtue of the morphing model (over the Sakasegawa numerical approximation) is that the ρ^m term has a physical meaning. As I explain in my IFORS presentation, ρ^1 can be interpreted as the probability of finding the server busy (utilization) and having to wait. ρ^2 is the probability of finding both servers busy in M/M/2. There's a kind of dependency between the 2 servers reflected in the power of 2. Similarly for ρ^3, and so on. That's a bit strange b/c the servers are statistically independent ... by definition! But's that not where the dependency lies. Rather, it's lies in what the HOL customer sees. Even if all m-1 servers are busy, the HOL gets serviced by the one available server. That's a kind of parallelism in the M/M/m and the morphing model contains that effect explicitly, but only as an approximation (it turns out) due to assuming parallel queues.

This intuition is not very well elucidated in my book, b/c I hadn't fully grasped it when writing. However, I do go into this aspect more in a 2011 blog post entitled, The Multiserver Numbers Game. Out of playing this game drops the truncated geometric series of the morphing model. :)

Neil Gunther said...

While I'm thinking about it, it's very significant that the morphing equation for R has the same algebraic form as for an M/M/1 queue with the only difference being the m exponent. M/M/1 is the morphing model with m=1. Although the formula is less accurate numerically than Sakasegawa, it's much easier for people unfamiliar with queueing theory to comprehend (my Guerrilla approach) the form. But, most importantly, the morphing model actually explains about 90% of what is going on in the M/M/m queue. The better numerical accuracy of Sakasegawa is irrelevant.

ks said...

Thanks so much for the great info.

Neil Gunther said...

My IFORS-2017 presentation slides are now available for download.