From: David Buckley <isreal-netdev-at-vger.kernel.org@bucko.me.uk>
To: netdev@vger.kernel.org
Subject: [PATCH] ping mdev rounding issue
Date: Tue, 11 Nov 2014 09:16:05 +0000 [thread overview]
Message-ID: <20141111091605.GA20540@cirno.bucko.me.uk> (raw)
[-- Attachment #1: Type: text/plain, Size: 2110 bytes --]
ping has a rounding issue in standard deviation computation.
It stores all values as integer micros, and computes standard deviation
as:
sqrt(SUM(time*time)/count - (SUM(time)/count)*(SUM(time)/count))
Because the second 'count' divide is performed before the multiply, a
rounding error results of the order O(sqrt(SUM(time)/count)).
Example: I ping my server twice. One takes 1000us, the second takes
1001us.
Standard deviation computed by ping is:
sqrt((1000000+1002001)/2 - ((1000+1001)/2)*((1000+1001)/2))
= sqrt(1001000 - 1000*1000) = sqrt(1000) = 31
So we got a 1us difference and report a 31 us standard deviation.
If the samples are 999 and 1001
sqrt((998001+1002001)/2 - ((999+1001)/2)*((999+1001)/2))
= sqrt(1000001 - 1000*1000) = sqrt(1) = 0
So more deviation makes for less /reported/ deviation.
This is reduced slightly in this case by more samples (100*1000+1001
reports deviation of 4us, for instance), but really it's caused by the
rounding error ((float)SUM(time)/count) - (SUM(time)/count) being
/multiplied/ by the average time. The expected error is of the order
sqrt(mean).
Example real-world bad computation:
PING 74.125.230.238 (74.125.230.238) 56(84) bytes of data.
64 bytes from 74.125.230.238: icmp_seq=1 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=2 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=3 ttl=51 time=16.2 ms
64 bytes from 74.125.230.238: icmp_seq=4 ttl=51 time=16.1 ms
^C
--- google.com ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 3003ms
rtt min/avg/max/mdev = 16.132/16.170/16.246/0.161 ms
With patch (attached):
PING 74.125.230.238 (74.125.230.238) 56(84) bytes of data.
64 bytes from 74.125.230.238: icmp_seq=1 ttl=51 time=16.0 ms
64 bytes from 74.125.230.238: icmp_seq=2 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=3 ttl=51 time=16.1 ms
64 bytes from 74.125.230.238: icmp_seq=4 ttl=51 time=16.1 ms
^C
--- 74.125.230.238 ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 3003ms
rtt min/avg/max/mdev = 16.045/16.128/16.197/0.054 ms
--
David Buckley
[-- Attachment #2: fix_rounding.patch --]
[-- Type: text/x-diff, Size: 793 bytes --]
--- a/ping_common.c 2014-11-11 00:02:07.000000000 +0000
+++ b/ping_common.c 2014-11-11 09:04:06.699021939 +0000
@@ -1016,14 +1016,17 @@
}
putchar('\n');
if (nreceived && timing) {
long tmdev;
+ long count = nreceived + nrepeats;
- tsum /= nreceived + nrepeats;
- tsum2 /= nreceived + nrepeats;
- tmdev = llsqrt(tsum2 - tsum * tsum);
+ // mdev = sqrt((tsum2/count) - (tsum/count)*(tsum2/count))
+ // However, we must be careful about rounding!
+ tmdev = llsqrt((tsum2 * count - tsum * tsum) / (count * count));
+ tsum2 /= count;
+ tsum /= count;
printf("rtt min/avg/max/mdev = %ld.%03ld/%lu.%03ld/%ld.%03ld/%ld.%03ld ms",
(long)tmin/1000, (long)tmin%1000,
(unsigned long)(tsum/1000), (long)(tsum%1000),
(long)tmax/1000, (long)tmax%1000,
reply other threads:[~2014-11-11 9:51 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20141111091605.GA20540@cirno.bucko.me.uk \
--to=isreal-netdev-at-vger.kernel.org@bucko.me.uk \
--cc=netdev@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox