Friday, January 18, 2008

Scalability Law as Queueing Model Proven

It never rains in California, it just pours. Not only have we had a lot of seasonal rain lately but it seems to be the season for proofs. In 2002, I proved that Amdahl's law is equivalent to a special kind of queueing behavior. This particular connection with queueing theory had not been made before. Here's a restatement of that theorem.

Unfortunately, blog fonts don't support proper math and the hyperlinks don't survive in the PNG. They are: Gunther 2005 and Guerrilla Capacity Planning.

The proof of Thm 1 begged the question, could a similar proof be constructed for my Universal Law of Scalability? I knew that any proof had to include a load-dependent server in order to produce the retrograde throughput effect (due to the quadratic p term in the denominator), but the choice of a functional form for that load-dependence was not clear to me, so I shelved it. Yesterday, it finally dawned on me! So, here now is the generalization of Thm 1.


Here's the link to my original 1993 paper.

My colleague, Jim Holtman, has recently done some discrete-event simulations which show that if he simply makes the service time proportional to the number of enqueued requests, the simulated throughput fits my universal law like a glove.

No comments: