tag:blogger.com,1999:blog-6977755959349847093.post3117508419235500839..comments2018-06-19T08:30:07.681-07:00Comments on The Pith of Performance: Morphing M/M/m: A New View of an Old QueueNeil Guntherhttp://www.blogger.com/profile/11441377418482735926noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-6977755959349847093.post-84211229468974505752017-07-19T04:35:35.043-07:002017-07-19T04:35:35.043-07:00My IFORS-2017 presentation slides are now availabl...My IFORS-2017 <a href="https://speakerdeck.com/drqz/m-a-new-view-of-an-old-queue" rel="nofollow">presentation slides</a> are now available for download.Neil Guntherhttps://www.blogger.com/profile/11441377418482735926noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-16721496512496427982017-07-17T20:28:25.360-07:002017-07-17T20:28:25.360-07:00Thanks so much for the great info.Thanks so much for the great info.kshttps://www.blogger.com/profile/16640185679910305713noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-23417852435699246292017-07-17T08:21:58.893-07:002017-07-17T08:21:58.893-07:00While I'm thinking about it, it's very sig...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 <a href="http://www.perfdynamics.com" rel="nofollow">Guerrilla approach</a>) 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.Neil Guntherhttps://www.blogger.com/profile/11441377418482735926noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-47108090037740133862017-07-15T13:01:59.684-07:002017-07-15T13:01:59.684-07:00Another virtue of the morphing model (over the Sak...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. <br /><br />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, <a href="http://perfdynamics.blogspot.com/2011/07/the-multiserver-numbers-game.html" rel="nofollow">The Multiserver Numbers Game</a>. Out of playing this game drops the truncated geometric series of the morphing model. :)Neil Guntherhttps://www.blogger.com/profile/11441377418482735926noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-34241697461085708072017-07-15T11:59:37.699-07:002017-07-15T11:59:37.699-07:00Here is the visualization in the complex plane for...Here is the <a href="https://twitter.com/DrQz/status/843129835194994688" rel="nofollow">visualization</a> 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. <br /><br />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 Guntherhttps://www.blogger.com/profile/11441377418482735926noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-27469936597685838082017-07-15T11:42:41.227-07:002017-07-15T11:42:41.227-07:00This comment has been removed by the author.Neil Guntherhttps://www.blogger.com/profile/11441377418482735926noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-53418060535053246982017-07-15T11:07:20.156-07:002017-07-15T11:07:20.156-07:00The formula you quote from my PPDQ book is what I ...The formula you quote from my <a href="http://www.perfdynamics.com/books.html" rel="nofollow">PPDQ book</a> 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.<br /><br />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 <a href="http://www.perfdynamics.com/books.html" rel="nofollow">book</a>. See p.85 of the 2004 edition or p.125 (Listing 4.6) of the 2nd edition.Neil Guntherhttps://www.blogger.com/profile/11441377418482735926noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-85689250285659594582017-07-15T09:56:54.918-07:002017-07-15T09:56:54.918-07:00Hi,
How does this compare to approximations:
1. se...Hi,<br />How does this compare to approximations:<br />1. section 2.7 of Analyzing Computer System Performance With Perl::PDQ<br />R approx. equal to S/(1 - Power(p,M))<br /><br />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 Schwartzkshttps://www.blogger.com/profile/16640185679910305713noreply@blogger.comtag:blogger.com,1999:blog-6977755959349847093.post-53348623751823579932017-07-15T09:56:37.157-07:002017-07-15T09:56:37.157-07:00Hi,
How does this compare to approximations:
1. se...Hi,<br />How does this compare to approximations:<br />1. section 2.7 of Analyzing Computer System Performance With Perl::PDQ<br />R approx. equal to S/(1 - Power(p,M))<br /><br />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 Schwartzkshttps://www.blogger.com/profile/16640185679910305713noreply@blogger.com