Re: Derive (1) (request arrival rate & the utilization per request) from (utilization & its variance) and (2) std deviation of utilization when combining independent workloads

[DrQ]

Before we get too far into all your points, I can tell you immediately that your 

eq1.  avg(r)= avg(u)^2 / var(u)

can't possibly be correct on dimensional grounds. You are looking for a rate (inverse time) on the LHS, but you have entirely dimensionless quantities on the RHS.

The relationship b/w request rate and utilization is well known. In your notation:

avg(u) = avg(r) * avg(S)

where S is the mean service time for the corresponding requests. It's a variant of Little's law, although most people (including John Little) don't think of it that way.

From another perspective, the RHS of your eqn.(1) is actually the inverse of the squared coefficient of variation.

On Sunday, May 19, 2013 6:59:07 PM UTC-7, David Kra wrote:

This is my first post here. I would like everyone's critique on two items:

1. Working backwards from observed (utilization & its variance) to a synthetic (request arrival rate & the utilization per request) that would produce those same observations.
   
2. Combining independent workloads and determining the std deviation of the resulting aggregate workload.
   

Item 1) Working backwards from (utilization and its variance) to an (request arrival rate and the utilization per request) that would produce those observations.

I have logs of server utilization at the hour level over, say, a few months. Let's say I calculate the mean and variance of the 10am hour samples.

I have avg(u) and var(u). I want to derive the average request rate r, and resource consumption m per request that would produce those avg(u) and var(u).

I derive (see the algebra below) that the average rate is 

eq1.  avg(r)= avg(u)^2 / var(u) and 

the utilization per request is

eq2.  m=var(u)/avg(u)

Note: avg(u)^2  is not avg(u^2) 

Q1: Is this a valid thing to do? It looks way too easy.

If this is valid, then I can use this method to consider the impact of adding work to an existing mixed workload server without actually individually measuring each existing work type's rate and resource usage. This could be useful in planning for adding another independent workload. Less likely, the addition could be organic growth of all the existing workloads at the same rate, but that is highly unlikely to happen unless they are all driven by the same fundamental volume driver. 

Q2: Is this well known? 

Item 2) Combining independent workloads and determining the std deviation of the resulting aggregate workload.

The existing rate from above becomes r1 with existing utilization per request m1.  

The additional workload has rate r2 and utilization per request m2.

Averages add, so the total rate rt: 

eq3. rt = r1 + r2

eq4. var(rt) = var(r1) + var(r2) = r1 + r2, if we assume arrivals are Poison and the workloads are not correlated.

So the standard deviation, 

eq5. sigma(rt) = sqrt(r1+r2)

With regard to the utilizations, the total utilization is the sum of the separate utilizations,

eq6. ut = r1*m1 + r2*m2

But, even though the variance of the total request rate equaled the request rate, and the standard deviation of the total request rate is sqrt(r1+r2), we can't say the same for the utilization.

Remember that var(aX+bY)=a^2*var(X)+b^2*var(Y)+2*a*b*Cov(X,Y) see http://en.wikipedia.org/wiki/Variance#Basic_properties

So in our case, the variance of the utilization is

eq7. var(m1*r1+m2*r2) = (m1^2)*r1 + (m2^2)*r2

 

and its standard deviation is

eq8. sigma(ut) = sqrt((m1^2)*r1 + (m2^2)*r2)

 

This is important when adding work onto a mixed usage system, whether it is a mainframe or a virtualized x64 machine. 

It means that if we are sizing to handle a 4 sigma second we don't have to upgrade to handle a second that is both 4 sigma for the entire old workload and 4 sigma for the new workload..

Q3: Is this well known? 

 

==================

Derivation of working backwards.

 

eq9.  avg(u)=m*avg(r) , rearrange to give

eq10.  avg(r)=avg(u)/m, now square, so

eq11.  avg(r)^2 = avg(u)^2 / m^2

Consider that 

eq12.  var(u)=m^2 * var(r) and for Poisson arrivals, avg(r) = var(r)

eq13.  m^2 = var(u) / avg(r)

Substituting gives 

eq14.  avg(r)^2 = avg(u)^2 / (var(u) / avg(r) ) and cancelling gives

eq15.  avg(r)= avg(u)^2 / var(u)  So now we have the average rate.  

eq1. avg(u)=m*avg(r) , rearrange to give

eq16. m=avg(u)/avg(r) 

Substituting eq7 for avg(r) gives

eq2. m=var(u)/avg(u) , so now we have the utilization per transaction.

QED.

 

[DrQ]

> (1) Dimensional issues, solved, I think.

I think not. You are correct about the mean and var of the Poisson dsn being equal (mean and sd for the Exp dsn), but what has that got to do with the price of fish?

> I have never before seen a rate and service time both synthesized from the utilization and its variance.

You should by now be getting the idea that there's a good reason for that.

A rate metric or a time metric on the LHS of your eqn can only arise as a consequence of the metrics on the RHS involving time, either explicitly or implicitly. It can't come out of the vacuum. Any function of the utilization is still dimensionless and therefore  cannot produce a time or an inverse time dimension.

These 2 statements: "Derivation of working backwards." and  "This is not a derivation." appear to be contradictory.

On Tuesday, May 21, 2013 1:50:14 PM UTC-7, David Kra wrote:

Thank you for your reply.

(1) Dimensional issues, solved, I think.

(2) Anything useful new here?

(1) Dimensional issues, solved, I think

I think I figured out what the problem with the dimensional units is. For the Poisson distribution, the value of the variance is the same as the value of the average, even though the units are squared.  

var(x)= x * (units of x) 

var(100 req/sec) = 100 req^2/sec^2 

Now the algebra and dimensions work out: 

Derivation of working backwards.

eq9.  avg(u)=m*avg(r) , rearrange to give

eq10.  avg(r)=avg(u)/m, now square, so

eq11.  avg(r)^2 = avg(u)^2 / m^2

Consider that 

eq12.  var(u)=m^2 * var(r) and for Poisson arrivals, avg(r) = var(r) so

eq12a. var(u)=m^2 * avg(r) * (units of r)

eq13.  m^2 = var(u) / ( avg(r)* (units of r) )

Substituting the right side of eq13. into the right side of eq11. gives 

eq14.  avg(r)^2 = avg(u)^2 / (var(u) / ( avg(r)* (units of r)) ) and cancelling gives

eq15.  avg(r)= (avg(u)^2 / var(u)) * (units of r) So now we have the average rate and the dimensions work out too..  

Then to get the service per request,

eq1. avg(u)=m*avg(r) , rearrange to give

eq16. m=avg(u)/avg(r) 

Substituting eq15 for avg(r) gives

eq2. m=var(u)/avg(u) , so now we have the utilization per transaction.

QED.

(2) Anything useful new here?

Also, although, as you said,

The relationship b/w request rate and utilization is well known. In your notation:

avg(u) = avg(r) * avg(S)

I have never before seen a rate and service time both synthesized from the utilization and its variance.   

Is this a valid synthesis? 

(This is not a derivation. The calculated numbers are not expected to match a reality which includes multiple different and possibly independent workloads.)

==============================================

[Scott Johnson]

All I'm gonna say here is that when you decide to dance with the bear, you don't stop dancing when you're tired.

--
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Regards,

Scott Johnson

[Scott Johnson]

I didn't mean that in a bad way at all.  DrQz tirelessly points out the misunderstandings and logical fallacies.  I appreciate that; it takes that repetition to drive the point home for me.  If you hang something out there that he doesn't feel is correct, he'll try to help you see that.  And he'll keep helping, and helping, and helping :-)

On Wed, May 22, 2013 at 4:59 PM, David Kra <dakr...@gmail.com> wrote:

 "Dancing Bear" happens to be my favorite Mamas & Papas song. Here, though, I guess I beaten a horse to death.
Thank you all.

--
Regards,

Scott Johnson

--
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Regards,

Scott Johnson

[DrQ]

Which reminds me, you still haven't handed in your homework from a year ago. Here's the solution.

Disk parameters:

    Metric   ms

1     Seek 3.60

2  Latency 8.28

3      RPS 0.00

4 Transfer 1.66

Modeling results (ms):

  QModel ServTime WaitTime RespTime

1  D/D/1    13.54  0.00000 13.54000

2  M/D/1    13.54  6.77000 20.31000

3  M/M/1    13.54 13.54000 27.08000

4  M/G/1    13.54 17.34812 30.88812

Now your problem is to find the question in your email. Just being helpful. :))

To unsubscribe from this group and stop receiving emails from it, send an email to guerrilla-capacity-planning+unsub...@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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Regards,

Scott Johnson

[Scott Johnson]

As I recall, my questions were along the lines of - Nice but I'm not sure I understand it.  Do the columns represent different disks that are part of the same system?  If so, then you sum the response time in the bottom row to give you S?  What is used for the variance and the mean?  The different disk response times?  And where does rho come from?

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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Regards,

Scott Johnson

[DrQ]

Let's see if I can put this to bed numerically, starting with 2 key observations:

1. The algebra of your "derivation" requires that R (for "rate") be Poisson distributed: avg(R) = var(R) or avg(r) = var(r); your notation is inconsistent. In the notation of my books, X is the thruput or arrival rate (in steady state) and S is the service time, so that Little's law is U = X * S. In your notation LL is U = m * R. BTW,  U = m * R and avg(U) = m * avg(R) is the same thing b/c LL is a statement about mean values.
   
2. In my first response, I pointed out that the RHS of your proposed equation avg(R) = avg(U)^2 / var(U) is the inverse of the squared coeff of variaton: iSCoV.

Elaborating on Point 1:

The Poisson dsn is a discrete dsn b/c it has to do with counts or events, not rates. It can be thought of as the large-N approx to a Binomial dsn. It gives the prob that there will be, e.g., N phone calls arriving at a help center every minute. 

The Poisson dsn is expressed in terms of a single parameter, α > 0, which is dimensionless. Why? It is the average NUMBER of events occurring in the chosen interval of space or time; it is sometimes referred to as the "strength." The Poisson pmf contains a factor, exp(-α), so it has to be dimensionless b/c probabilities are dimensionless.

Compare this with the Exp dsn (the continuous dsn of time intervals b/w events). If for any time t > 0 the number of arrivals in the time interval [0, t] follows the Poisson distribution with mean α replaced by λt, then the inter-arrival periods are iid Exp random variables with mean 1/λ. The Exp pdf parameter λ must have the dimensions of inverse time in order that the α parameter of the corresponding Poisson dsn remain dimensionless. An inverse-time quantity is a frequency or rate; the arrival rate in queueing parlance.

In queueing models of computer performance, the inter-arrival periods or the service periods are often assumed to be Exp distd, not Poisson distd.

Elaborating on Point 2:

The following table shows the results of a simulation for 10,000 Poisson variates X. Their mean value was chosen to be 20. 

Arrivals dsn: Poisson, Service dsn: Constant using 10,000 variates

   Utilization ServiceTime   MeanX   Kraput      CoVu      CoVx   iSCoVx

1    0.9982900 0.050000000 19.9658 20.27966 0.2220596 0.2220596 20.27966

2    0.6655267 0.033333333 19.9658 20.27966 0.2220596 0.2220596 20.27966

3    0.4991450 0.025000000 19.9658 20.27966 0.2220596 0.2220596 20.27966

4    0.3993160 0.020000000 19.9658 20.27966 0.2220596 0.2220596 20.27966

5    0.3327633 0.016666667 19.9658 20.27966 0.2220596 0.2220596 20.27966

6    0.2852257 0.014285714 19.9658 20.27966 0.2220596 0.2220596 20.27966

7    0.2495725 0.012500000 19.9658 20.27966 0.2220596 0.2220596 20.27966

8    0.2218422 0.011111111 19.9658 20.27966 0.2220596 0.2220596 20.27966

9    0.1996580 0.010000000 19.9658 20.27966 0.2220596 0.2220596 20.27966

10   0.1815073 0.009090909 19.9658 20.27966 0.2220596 0.2220596 20.27966

The sample mean is mean(X) = 19.9658 ~ 20 (3rd col). In addition, I chose a set of variable service times (2nd col) and computed the corresponding varying utilization (1st col) using LL. This allows me to calculate your avg(R) or "rate" (I'll call it the "Kraput") in the 4th column. Notice that the Kraput is close to the mean of X but not identical to it. 

Note further that although the Kraput employs different utilization values as inputs from each of the 10 rows, it remains constant. This reflects your main claim, that you can use measurements of the single utilization metric to determine the throughput of the system, whereas LL requires the measurements of two input metrics.

However, notice that I also get the same value as the Kraput if I take (a) the CoVx of the random variates (X) in the 6th column, (b) square it and (c) invert it: "iSCoVx" (last col). This follows from your assumption that the service time (m in your notation) is constant and using LL.

What's going on here? 

This all goes back to my original observation, restated in point 2, above. For a Poisson dsn, the CoV = sd/mean = sqrt(α)/α = 1/sqrt(α). Therefore, the CoV^2 = SCoV = 1/α and the inverse of the SCoV or iSCoV = α. In other words, the iSCoV is the mean of the Poisson dsn or mean(X) in the above table. Hence, columns 3 and 7 are approximately equal for 10,000 variates. Columns 4 and 7 are the same thing, by definition of the ratio.

Clearly, the Mean(X) and iSCoVx are identical mathematically for the Poisson dsn. Then your equation follows trivially and your "derivation" is unnecessary. However, it is entirely misleading with regard to application to computer performance analysis. Why?

The Poisson parameter is dimensionless, for the reasons I gave above, so the the quantity on the LHS of your equation must also be dimensionless. But you want it to represent the thruput or arrival rate. Therefore, as I tried to point out in my previous responses, this relationship cannot be true in general. And it is not. The statistical mean (α) and the iSCoV (α) just happen to be identical numerically for the Poisson dsn. 

This point is easy to demonstrate by choosing the dsn to be Exp rather than Poisson:

Arrivals dsn: Exponential, Service dsn: Constant using 10,000 variates

   Utilization ServiceTime    MeanX    Kraput     CoVu     CoVx    iSCoVx

1    1.0038638 0.050000000 20.07728 0.9914595 1.004298 1.004298 0.9914595

2    0.6692425 0.033333333 20.07728 0.9914595 1.004298 1.004298 0.9914595

3    0.5019319 0.025000000 20.07728 0.9914595 1.004298 1.004298 0.9914595

4    0.4015455 0.020000000 20.07728 0.9914595 1.004298 1.004298 0.9914595

5    0.3346213 0.016666667 20.07728 0.9914595 1.004298 1.004298 0.9914595

6    0.2868182 0.014285714 20.07728 0.9914595 1.004298 1.004298 0.9914595

7    0.2509660 0.012500000 20.07728 0.9914595 1.004298 1.004298 0.9914595

8    0.2230808 0.011111111 20.07728 0.9914595 1.004298 1.004298 0.9914595

9    0.2007728 0.010000000 20.07728 0.9914595 1.004298 1.004298 0.9914595

10   0.1825207 0.009090909 20.07728 0.9914595 1.004298 1.004298 0.9914595

For the Exp dsn, the CoV = 1 by definition and the Kraput is similarly near 1, whereas the mean of these Exp distd variates is still chosen to be mean(X) = 20.

In other words, the correct dsn to provide rates (e.g., arrival rate) for computer performance analysis is the Exp dsn (as we do in queueing models). But that fails to support your claimed equation b/c its CoV or iSCoV = 1, always.

On Thursday, May 23, 2013 1:26:06 PM UTC-7, David Kra wrote:

* I was going to reply privately, because it was beginning to sound repetitive, but realized since this is a professional ad rem discussion, not a personal ad hominem attack, we should continue for my and others' illumination.

<Metadiscussion >

Picky, picky, picky terminology department: 

Dimensions vs. units of measure

Some of us, at least me, have been using dimensions and units of measure almost interchangeably here. They aren't. Length is a dimension. Kilometer is a unit of measure. I'LL try to be careful, but not complain about any others' misuses.

 

Synthesis vs Derivation

I derived a formula for a value using algebra. The value is synthetic because it does not purport to match the underlying reality. I used an observed average and variance to formulate a rate and workload that would produce that same average and variance.  The reality could be that there are actually multiple independent workloads, each with its own average and variance which, in aggregate, produce the observed average and variance.

 

</Metadiscussion >

This analysis does not apply merely to dimensionless utilization, though I claim that even utilization is not dimensionless!

u = m (CPU seconds/request) * r (requests/second)  has units of CPU, while its variance has the units of CPU^2

 

u = m (CPU seconds/request) * r (requests/hour)  has units of CPU seconds per hour, while its variance has the units of (CPU seconds per hour)^2.

 

u = m (instruction/request) * r (requests/second)  has units of instructions per second, while its variance has the units of (instructions per second)^2.

 

u = m ($ / withdrawal) * r (withdrawal/hour)  has units of $/hour, while its variance has the units of  ($/hour)^2.

Whether or not you agree, I would appreciate comments on the validity and usefulness of:

Given random variables, R and U, where U = m * R, and where R has a Poisson distribution, and

Given observed values for avg(U), and var(U),  we should find that the values of 

m = var(U) / avg(U) and that 

avg(R) = avg(U)^2 / var(U) 

 subject to the typical implications of sample size.

 

My take of the usefulness is that in many cases the data provided to me includes resource consumption during the period, but not the number of requests. Combining many samples during a consistent load period, lets me estimate the number of requests and resource per request. For ATM's for example, a consistent load might consist of the same hour of the day for each Tuesday, Wednesday, and Thursday other than the 1st and 15th of the month, which is admittedly, only about 12 samples per month for each hour (4 weeks * 3 days). ATM's are a bad example, however, because the reported data always provides the number of business transactions. 

<simpler derivation>

eq1.               U = m * R

eq2.          avg(U) = m * avg(R)

eq3.          var(U) = m^2 * var(R)

divide eq3 by eq2 to get

eq4. var(U) / avg(U) = (m^2) * avg(R) / ( m * var(R)) 

which, for the Poisson distribution, where avg(r) equals var(R) gives

eq5.   var(U)/avg(U) = m   

and if we substitute the lhs into the rhs of eq2, we get 

eq6.          avg(U) = (var(U) / avg(U)) * avg(R) which gives

eq7.          avg(R) = avg(U)^2 / var(U)

</simpler derivation>