10
$\begingroup$

I've sampled a real world process, network ping times. The "round-trip-time" is measured in milliseconds. Results are plotted in a histogram:

enter image description here

Ping times have a minimum value, but a long upper tail.

I want to know what statistical distribution this is, and how to estimate its parameters.

Even though the distribution is not a normal distribution, I can still show what I am trying to achieve.

The normal distribution uses the function:

enter image description here

with the two parameters

  • μ (mean)
  • σ2  (variance)

Parameter estimation

The formulas for estimating the two parameters are:

alt text

Applying these formulas against the data I have in Excel, I get:

  • μ = 10.9558 (mean)
  • σ2  = 67.4578 (variance)

With these parameters I can plot the "normal" distribution over top my sampled data:

enter image description here

Obviously it's not a normal distribution. A normal distribution has an infinite top and bottom tail, and is symmetrical. This distribution is not symmetrical.


What principles would I apply, what flowchart, would I apply to determine what kind of distribution this is?

And cutting to the chase, what is the formula for that distribution, and what are the formulas to estimate its parameters?


I want to get the distribution so I can get the "average" value, as well as the "spread":

enter image description here

I am actually plotting the histrogram in software, and I want to overlay the theoretical distribution:

enter image description here

Tags: sampling, statistics, parameter-estimation, normal-distribution

$\endgroup$
7
  • 2
    $\begingroup$ Out of curiosity, have you tried asking this question on stats.stackexchange.com ? (I think your question is appropriate here as well, but you might get more/different answers there.) $\endgroup$
    – Isaac
    Aug 5, 2010 at 19:17
  • $\begingroup$ i'll copy-pasta it there; me an my 1 rep. $\endgroup$
    – Ian Boyd
    Aug 5, 2010 at 19:23
  • $\begingroup$ My understanding is that there is a large literature on stuff like network ping times and the answer is probably in a paper somewhere. $\endgroup$ Aug 5, 2010 at 20:00
  • 2
    $\begingroup$ Have you tried to use ccsl.mae.cornell.edu/eureqa ? $\endgroup$
    – j.p.
    Aug 6, 2010 at 11:54
  • $\begingroup$ Link to the question on stats.stackexchange. $\endgroup$
    – Larry Wang
    Aug 6, 2010 at 12:44

4 Answers 4

3
$\begingroup$

I'd vote for a Poisson distribution with a constant offset.

A hand-wavy reasoning might be that the round trip time is due to a constant offset being the best-case round-trip time assuming no delays due to router queues (= wave propagation velocity over physical distance, + minimum processing time), with "rare events" (see wikipedia page) corresponding to queueing delays in one or more routers that make up the network path(s).

As far as parameter estimation goes, I'm not familiar with how to do it for samples taken from a (suspected) Poisson distribution, but I'm sure you could find something on the Internet.

aha, here we go: http://en.wikipedia.org/wiki/Poisson_distribution#Parameter_estimation -- you could use this after subtracting off the minimum of a large number of samples.


drat, stupid me, I glossed over the fact that Poisson = discrete probability distribution.

$\endgroup$
2
  • $\begingroup$ +1: As response times are measured in ms, what's the problem with Poisson being discrete? $\endgroup$
    – j.p.
    Aug 6, 2010 at 12:02
  • $\begingroup$ b/c there's a difference between a discrete-valued process, and a continuous-valued process whose output is quantized. in any case at least it's an approximation to reality. $\endgroup$
    – Jason S
    Aug 6, 2010 at 12:58
3
$\begingroup$

Sounds an awful lot like the conditions you would expect for an Erlang distribution to me- it also looks a lot like one...

Erlang distributions model the times between occurrences in poisson processes and are frequently used as parts of models of internet traffic.

My interpretation is this: as a site sending back a signal, one processes and sends stuff for a given user in an approximately poisson process (the approximate 'limit' of bernoilli trials p-> stuff for user 1-p -> stuff for a different user) and the time spent waiting for one to occur is therefore distributed Erlangwise, with a shift to the right (to account for the user's sending of the signal). This gives the shape you have above :)

Edit: This should be Erlang-2 if that is not already clear, since receiving and sending are two poisson occurrences from the same distribution depending (as indicated above) on traffic [That is: occurrence 1- server has free bit to process receiving, occurrence 2- computer has free bit to process sending]

$\endgroup$
2
  • $\begingroup$ +1, but it could be more than 2, since there are often intermediate routers between computers. (hence the beauty of the network) $\endgroup$
    – Jason S
    Aug 6, 2010 at 12:59
  • $\begingroup$ Maybe then, for interpolation's sake, just fit it to a gamma with some real 2<k<3? $\endgroup$ Aug 6, 2010 at 13:33
2
$\begingroup$

The go-to distribution for things like wait times is the Exponential. Yours doesn't look exactly the same because of the tiny lower tail, but I would be inclined to attribute that to noise/measurement error. (The assumption of independence of events is almost certainly wrong for ping times, but it's probably still your best choice.)

Also, you would probably be better off asking this sort of question on the stats site.


Edit: As pointed out by Srikant Vadali, the Gamma distribution is more general and can account for a non-negligible short tail, so may be a more appropriate choice. It's easier to estimate the parameter for the exponential, though.

$\endgroup$
3
  • 2
    $\begingroup$ Oh good lord, i just filtered though the dozens of Stack sites to find the "dummy version" of math. (as opposed to the snobbish mathoverflow). Why do you think that ping round-trip-times are not independant? It measures the response time of the network at that moment. $\endgroup$
    – Ian Boyd
    Aug 5, 2010 at 19:22
  • $\begingroup$ @Ian Well, I'd expect there to be some systematic correlation in network latency -- that is, if my ping now is slow, my ping in 1 second is likely to be too. But perhaps it's more volatile than I realise. (As to the stats thing, as @Isaac says, it's not off topic here, just there may be more specialised knowledge on hand there.) $\endgroup$
    – walkytalky
    Aug 5, 2010 at 19:29
  • $\begingroup$ @Ian If you want to take in that you are measuring something over the Internet, you are going to have encode that information mathematically. The exponential is just a quick approximation. $\endgroup$ Aug 5, 2010 at 19:31
2
$\begingroup$

From the comments on stats.stackexchange, it seems like you may not care too much about the distribution, but just a pretty curve to overlay on your graph. In which case, some kind of spline is your best bet. Use some kind of curves with asymptotes at y=0 for your upper- and lower-most segments, and whatever fits best in between.

If you do actually care about the underlying distribution:
The first step would be to use whatever outside knowledge you have to characterize the distribution. For example:
Network ping is a sum of independent wait times (the individual nodes in the network). This would suggest a Gamma/Erlang distribution if each of these steps is identical, and a more complex distribution if they are not.
Ping is a measure of time until the computer at the other end responds to your request, the likelihood of which is proportional to the time elapsed. This would suggest a Weibull distribution.
Ping time is the accumulation of a large number of factors that all have a multiplicative effect on the result. Then a log-normal distribution would be best. I don't know enough about networking to say anything about the accuracy of any of the above models, and it's also perfectly likely that ping time follows some other model which I haven't thought of. I just wanted to demonstrate the idea: that you should think about what factors contribute to the thing you are trying to model, and how they interact.

And, of course, the distribution does not necessarily have to be a known one! In which case the above won't get you very far! In this case you might want to come up with your own empirical distribution, for which a variety of methods exist. The most common are to take your measurements as the distribution (as long as you have a sufficiently large number) or to take each of those data points and treat it as the center of some uniform/normal/other distribution, and sum everything with appropriate scaling.

After you know the type of distribution, you may also be able to use domain knowledge to estimate some of its parameters. For example, you might guess at the number of exponentials being summed based on the shape of the network. You can also use your measured mean and variance to form estimates of the distribution parameters. For example, if you thought that your distribution was a Gamma(3,θ), then you could use your measured variance to estimate θ=4.74182454 based on our known formula for variance of a Gamma Distribution.

Once you have your guess at a distribution, you will want to test its goodness of fit.

For this, the standard method would be to apply the one-sample Kolmogorov-Smirnov test.

Other potentially applicable tests are the Cramer-von-Mises, Anderson-Darling, or chi-square tests.

This is incomplete, I will add more later.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .