Eq. 2.63 in Perl::PDQ book

[Baron Schwartz]

Is there a name for the residence time formula, equation 2.63 on page 80 of Analyzing Computer System Performance With Perl::PDQ  (first edition) ?

R = S / (1-rho^M)

Neil, is that equation something you invented/discovered/derived yourself, or did you learn about it from someone else?

[DrQ]

I believe I first saw it at a CMG conference: in the mid-90s; if memory serves.  My impression is that it was a piece of IBM folklore that had been developed empirically to estimate LPAR capacity for MVS workloads. I've never seen a mathematical derivation, anywhere, other than my own.

My derivation comes from observing that the M/M/m server appears to "morph" from a parallel queueing facility at low traffic to a single high-speed M/M/1 server under heavy traffic.  Strange but true. As I've said elsewhere: there is no parallelism, just fast serialization.  :)  The question then becomes, what's the morphing function? The simplest candidate is a finite geometric series, and that's what you see in my book. Easy to understand and pretty close to exact. Good enough for Guerrillas.

I call it "heuristic" because it diverges from the exact formula by about 10% in the worst case. The reason for that lies, in part, in the way the M/M/m waiting line forms, i.e., buffering. Parallel queues (as the name suggests) each have their own buffer that can possibly become occupied, even briefly, at low loads, due to arrival fluctuations. But there aren't really m-buffers in M/M/m; there's only one. Expressing that uniqueness analytically, however, rapidly spawns a jungle of unintuitive mathematical terms (Gamma sums, etc.). Nonetheless, I can point you at terms in the jungle that do indeed correspond to a finite geometric series (morphing) but no longer in a way that makes intuitive sense or relates to the morphing model in an obvious fashion (e..g, simple correction terms).

Although it's just an idle (can I use that word?) curiosity, I've always felt it ought to be possible to derive the exact M/M/m formula intuitively, along the lines of the morphing approach without relying on probability theory or Markov chains, or any other sophisticated clutter. Then I could actually say I understood M/M/m. Well, I have discovered many different ways of deriving it (could easily be a paper on its own), but I'm not happy with any of them from an explanatory standpoint: my sole motivation being to provide more insight, not more fancy math. :/

[Baron Schwartz]

A while ago I mentioned an approximation to the Erlang C formula that Sakasegawa described in a paper in 1976, which I am attaching.

I just wrote a small program to compare the Erlang C, heuristic, and Sakasegawa approximations: https://github.com/VividCortex/approx-queueing-theory

Sakasegawa's approximation was derived by least-squares fitting and it doesn't give very good results in a lot of situations.

[Harry van der horst]

Dr Gunther,

you are to severe for yourself.

In the jungle of real life and the internet a deviation of 10 % in the worst case is ample.

Be happy and enjoy.

Kind regards and keep on the good work

harry

--
You received this message because you are subscribed to the Google Groups "Guerrilla Capacity Planning" group.
To unsubscribe from this group and stop receiving emails from it, send an email to guerrilla-capacity-...@googlegroups.com.
To post to this group, send email to guerrilla-cap...@googlegroups.com.
Visit this group at http://groups.google.com/group/guerrilla-capacity-planning.
For more options, visit https://groups.google.com/d/optout.

--

met hartelijke groeten/kind regards
harry van der Horst
M 0031643016999

[DrQ]

Dude, your Go code is no-go!

My MMA calculation of Mr. Sakasegawa's formula agree with his Table 3.3, e.g., for m=6 servers:

and for m=50 servers:

Furthermore, I know that for m=2 servers, the heuristic formula agrees identically with that based on the Erlang-C formula. That's due to the exact formula containing the heuristic formula at low orders in ρ. Mr. Sakasegawa, however, is not so contained.

Overall, it looks to me like Mr. Sakasegawa does better than the heuristic formula, especially for large-m and ρ > 0.5. The question is, why? How does an approximation with a radical exponent relate to the exact formula where such exponents don't arise analytically?

[Baron Schwartz]

Very odd. I seem to have an error in the Erlang and heuristic computations, but not the Sakasegawa. (My results for heuristic agree exactly with Erlang for m=2, but don't agree with yours; my Sakasegawa calculations agree with yours). I am staring and staring but I do not see my error.

As for Go... it's the language I do everything in these days. Installation, compilation, and redistribution are all orders of magnitude easier than R, Python, Perl or the like.

[Baron Schwartz]

I found and fixed my mistake. The code and results are updated.

[Baron Schwartz]

An interactive graphing demonstration of these three is at https://www.desmos.com/calculator/xn8hhw0i9b

[DrQ]

I'm still wondering why you brought up this 1976 paper.

Should we care about Mr. Sakagewara's result? My answer is, no.

Queueing theory journals were probably full of stuff like this, back in the day (well before my time, mind you).

As impressive as his formula might be numerically, I regard it as numerology. It probably served a reasonable purpose circa 1976 b/c it might have enabled the easier computation of a good asymptotic approximation to the exact Erlang-C function result using an HP calculator or similar. It reminds me of Ramanujan's famous asymptotic approximation for the number of integer partitions. 

Today, it serves no purpose b/c it's a trivial matter to implement the complete iterative algorithm in Excel, R, Go, or whatever environment and get the exact Erlang result (as you did). Who cares about good approximations anymore? Actually, Arnold Allen told me that the iterative algorithm was discovered not long after Erlang's paper in 1917, but was not widely known so, it's been rediscovered multiple times by various people.

The only reason I refer to the heuristic formula in my books and Guerrilla classes is b/c it offers a good first intuition regarding the exact Erlang-C formula. The power law makes it easy understand why adding more server capacity leads to better response-time performance. The accuracy is a secondary issue.The heuristic formula is also contained in the exact analytic form, in some sense.

None of these qualities apply to Mr. Sakagewara's formula. Moreover, he computes Lq, not R, and we usually prefer the latter to compare with performance measurements, so there is also some additional work to be done.

But other than that ...

[Baron Schwartz]

Well... from my point of view it's far easier to implement this approximation in a spreadsheet because it requires no iteration.

Doing Erlang-C in a spreadsheet requires macros or similar, which is always a problem. It often doesn't even work right across different versions of Excel, not to mention opening correctly in Google Docs or LibreOffice or the like.

But that's kind of a micro-optimization. I just find approximations fascinating. I have folders full of papers with approximations to things like the normal CDF and normal PDF. I can't explain why. Perhaps I am a numerologist. I feel safe in the knowledge that the FSM will forgive me.

I wrote the code because I wanted to understand how accurate the approximation is, nothing more. And implementing and checking math, and finding my mistakes and fixing them, often teaches me a great deal. In this case it taught me that I had overlooked a subtlety you highlighted in the Perl::PDQ book, that wait time in the queue is a bit more complicated than I thought (due to having to wait for the customer in service to finish).