Subject: [bmwg] Mean vs Median

From: "GEORGESCU LIVIU MARIUS" <[email-masked]>
Date: Tue, 03 Nov 2015 14:57:54 +0900

Hello BMWG,

Following some of the discussion we had in IETF93 about using either mean or median as a summarizing function for the results of multiple test iterations, I added the following section in http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00 
.

10(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-10). Summarizing function and repeatability To ensure the stability of the benchmarking scores obtained using the tests presented in Sections 6(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-6)-9(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-9), multiple test iterations are recommended. Following the recommendations of RFC2544(http://tools.ietf.org/html/rfc2544), the average was chosen to be the summarizing function for the reported values. While median can be an alternative summarizing function, a rationale for using one or the other is needed. The median can be useful for summarizing especially when outliers are not a desired quantity. However, in the overall performance of a network device the outliers can represent a malfunction or misconfiguration in the DUT, which should be taken into account. The average is a more inclusive summarizing function. Moreover, as underlined in [DeNijs(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#ref-DeNijs)], the average is less exposed to statistical uncertainty. These reasons make it the RECOMMENDED summarizing function for the results of different test iterations, unless stated otherwise. To express the repeatability of the benchmarking tests through a number, the Margin of error (MoE) can be used. Of course, other functions, such as standard error could be employed as well. The advantage the MoE has is expressing an associated confidence interval by using the alpha parameter. The recommended formula for calculating the MoE is presented in 

 Section 6.3.1(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-6.3.1).

After discussing this rationale with Al (Morton) and Kostas (Pentakousis), I am tending to lean towards using median. One of the reasons is non-normal probability distribution cases (e.g. bimodal distribution), where the Mean might not mean much (trying to paraphrase Al). One could add a step in the procedure like "analyze the probability distribution of the 20 measurements after deciding the summarizing function", but this might be an undesired over-complication. In any case, I think a measure of variance should be provided with the summarized results, in order to express the stability/repeatability of the results.

Since the rationale for using Mean or Median (or ...) could be reused in other documents produced by this WG, I would like to ask for more feedback on this subject.

Best regards,
Marius

---

From: Stenio Fernandes <[email-masked]>
Date: Tue, 3 Nov 2015 06:45:04 -0200

my two cents on this... see inline comments

this is my first interaction with the wg... so, bear with me if i'm a bit
wordy :-)

stenio

On Tu
e, Nov 3, 2015 at 3:57 AM, GEORGESCU LIVIU MARIUS <[email-masked]
<https://mail.google.com/mail/?view=cm&fs=1&tf=1&to=[email-masked]>
> wrote:

> Hello BMWG,
>
> Following some of the discussion we had in IETF93 about using either mean
> or median as a summarizing function for the results of multiple test
> iterations, I added the following section in
> http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00
> .
>
> 10 <http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-10>. Summarizing function and repeatability
>
>    To ensure the stability of the benchmarking scores obtained using
>    the tests presented in Sections 6 <http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-6>-9 <http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-9>, multiple test iterations are
>    recommended. Following the recommendations of RFC2544 <http://tools.ietf.org/html/rfc2544>, the average
>    was chosen to be the summarizing function for the reported values.
>    While median can be an alternative summarizing function, a rationale
>    for using one or the other is needed.
>
>

average is a colloquial term. although, in this context, there might be
nothing wrong with that, imho precise terms are preferred. measures of
central tendency could be used as the general term, where mean and median
fit in.

>    The median can be useful for summarizing especially when outliers
>    are not a desired quantity. However, in the overall performance of a
>    network device the outliers can represent a malfunction or
>    misconfiguration in the DUT, which should be taken into account.
>
>
a word of caution here... a number of phenomena in computer networks
follows a heavy-tailed probability distribution function, which means that
there is a non-negligible probability that a random variable will take huge
values. these values might be erroneously considered as outliers.

>    The average is a more inclusive summarizing function. Moreover, as
>    underlined in [DeNijs <http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#ref-DeNijs>], the average is less exposed to statistical
>    uncertainty. These reasons make it the RECOMMENDED summarizing
>    function for the results of different test iterations, unless stated
>    otherwise.
>
>
i'm having a hard time to understand this paragraph... i) "inclusive" is
very vague; ii) "less exposed to uncertainty" is confusing. the mean is
just a measure of centrality, whereas measures of dispersions (e.g., sd,
variance) can be used to assess the degree of uncertainty around that
measure (think of confidence intervals).

i know this is not the objective of the document, but the recommendation
could be very simple. for example, stating that *one should assess
statistical significance of results *would be enough, and then pointing out
to a strong reference. le boudec's book seems appropriate here (cf. chap 2).

free pdf at http://perfeval.epfl.ch/

@book{leboudec2010performance,
   title={Performance Evaluation of Computer and Communication Systems},
   author={Le Boudec, Jean-Yves},
   year={2010},
   publisher={EPFL Press, Lausanne, Switzerland}
}

>    To express the repeatability of the benchmarking tests through a
>    number, the Margin of error (MoE) can be used. Of course, other
>    functions, such as standard error could be employed as well. The
>    advantage the MoE has is expressing an associated confidence
>    interval by using the alpha parameter.
>
>    The recommended formula for calculating the MoE is presented in
>
> Section 6.3.1
> <http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-6.3.1>
> .
>
> After discussing this rationale with Al (Morton) and Kostas (Pentakousis),
> I am tending to lean towards using median. One of the reasons is non-normal
> probability distribution cases (e.g. bimodal distribution), where the Mean
> might not mean much (trying to paraphrase Al). One could add a step in the
> procedure like "analyze the probability distribution of the 20 measurements
> after deciding the summarizing function", but this might be an undesired
> over-complication. In any case, I think a measure of variance should be
> provided with the summarized results, in order to express the
> stability/repeatability of the results.
>
>
if the document will not give detailed approaches for summarizing
performance data (and i think it shouldn't), it should provied the simplest
recommendation as possible. otherwise, in order to be scientifically
correct, lots of assumptions must be made and provided, like iid, which
might not hold true for all cases.

> Since the rationale for using Mean or Median (or ...) could be reused in
> other documents produced by this WG, I would like to ask for more feedback
> on this subject.
>
> Best regards,
> Marius
>
>
>
>
>
>
>
>
> _______________________________________________
> bmwg mailing list
> [email-masked]
> <https://mail.google.com/mail/?view=cm&fs=1&tf=1&to=[email-masked]>
> https://www.ietf.org/mailman/listinfo/bmwg
>
>

-- 
Prof. Stenio Fernandes
CIn/UFPE
http://www.steniofernandes.com

---

From: "GEORGESCU LIVIU MARIUS" <[email-masked]>
Date: Wed, 04 Nov 2015 01:41:52 +0900

> 
> 
> 
> 
> Hello Stenio,
>  
>  
>  
> Thanks for your comments. Please see my comments inline.
>  
>  
>  
> From: [email-masked]
> [mailto:[email-masked] <[email-masked]>]
> On Behalf Of Stenio Fernandes
> 
> Sent: Tuesday, November 3, 2015 5:45 PM
> 
> To: GEORGESCU LIVIU MARIUS <[email-masked]>
> 
> Cc: [email-masked]; [email-masked]
> 
> Subject: Re: [bmwg] Mean vs Median
>  
>  
>  
> this is my first interaction with the wg... so, bear
> with me if i'm a bit wordy :-)
>  
>  
>  
> stenio
>  
>  
>  
>  
>  
> Thanks for joining the discussion.
>  
>  
>  
> On Tu
>  
> e, Nov 3, 2015 at 3:57 AM, GEORGESCU LIVIU MARIUS <[email-masked](https://mail.google.com/mail/?view=cm&fs=1&tf=1&to=[email-masked])> wrote:
>  
> Hello BMWG,
>  
>  
>  
> Following some of the discussion we had in IETF93 about
> using either mean or median as a summarizing function for the results of
> multiple test iterations, I added the following section in http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00 
>  
> .
>  10. Summarizing function
> and repeatability 
>  
> 
>  
> 
>  the tests presented in Sections 6(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-6)-9(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-9), multiple test iterations are
> 
>  recommended. Following the recommendations of RFC2544(http://tools.ietf.org/html/rfc2544), the average
> 
> average is a colloquial term. although, in this context,
> there might be nothing wrong with that, imho precise terms are preferred.
> measures of central tendency could be used as the general term, where mean and
> median fit in. 
>  
>  
>  
> Average seems to be a term accepted and used by industry, and
> not just a “colloquial” term. We could quibble about definitions and what
> we need to follow just as well. I prefer to go with RFC2544.
>  
>  
>  
>  underlined in [DeNijs(http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#ref-DeNijs)], the average is less exposed to statistical
> 
> i'm having a hard time to understand this paragraph... i)
> "inclusive" is very vague; ii) "less exposed to uncertainty"
> is confusing. the mean is just a measure of centrality, whereas measures of
> dispersions (e.g., sd, variance) can be used to assess the degree of
> uncertainty around that measure (think of confidence intervals).
>  
> i know this is not the objective of the document, but the
> recommendation could be very simple. for example, stating that one should
> assess statistical significance of results would be enough, and then
> pointing out to a strong reference. le boudec's book seems appropriate
> here (cf. chap 2).
>  
>  
>  
> Just assessing statistical significance would be great. I would
> recommend the study of this book: “Jain, Raj. The art of computer systems
> performance analysis. John Wiley & Sons, 2008.”
>  
> I wonder if text like this in an RFC would see the print.
>  
> I am sure this would be perfect for certain types of academic
> papers. I would rather have a clearer recommendation.
>  
>  
>  
> Section 6.3.1.
> if the document will not give detailed approaches for
> summarizing performance data (and i think it shouldn't), it should provied the
> simplest recommendation as possible. otherwise, in order to be scientifically
> correct, lots of assumptions must be made and provided, like iid, which might
> not hold true for all cases.
>  
>  
>  
> In order to be scientifically correct, the most important
> part would be to assess the probability distribution of the data. I am trying
> to find a solution where that wouldn’t be necessary. Of course it would
> not hold for all cases, but the goal is to find a pareto-optimal solution where
> the summarized result would be representative enough for the test sample and
> simple enough to obtain. Or at least that’s how I see things.
>  
>  
>  
> Marius
>  
>  
>

---

From: Stenio Fernandes <[email-masked]>
Date: Thu, 5 Nov 2015 13:21:13 -0200

it seems we're converging here.

my understanding now is that if the recommendation is too broad as i
suggested, it might not be very useful, since people might not know
what/how to do exactly. but if it is too specific, lots of assumptions
about the data have to be made without really knowing the actual data.

a compromise may be in encouraging getting enough data samples (n>30,
preferably many more), evaluating measures of centrality, dispersion, and
error, so that the recommendation is clear enough, but neither too generic
nor too specific.

jain's book is a classic one, but a bit old on the examples. le boudec's
book is kind of new and specific to computer networks, although he has a
heavy hand on math.

cheers,

stenio

On Tue, Nov 3, 2015 at 2:36 PM, Marius Georgescu <
[email-masked]> wrote:

> *From:* [email-masked] [mailto:[email-masked]] *On
> Behalf Of *Stenio Fernandes
> *Sent:* Tuesday, November 3, 2015 5:45 PM
> *To:* GEORGESCU LIVIU MARIUS <[email-masked]>
> *Cc:* [email-masked]; [email-masked]
> *Subject:* Re: [bmwg] Mean vs Median
>
>
>
> <https://mail.google.com/mail/?view=cm&fs=1&tf=1&to=[email-masked]>>
> wrote:
>
> Hello BMWG,
>
>
>
> 10
> <http://tools.ietf.org/html/draft-ietf-bmwg-ipv6-tran-tech-benchmarking-00#section-10>.
> Summarizing function and repeatability
>
>
>
>
>
> Average seems to be a term accepted and used by industry, and not just a
> “colloquial” term. We could  quibble about definitions and what we need to
> follow just as well. I prefer to go with RFC2544.
>
>
>
> statistical significance of results *would be enough, and then pointing
> out to a strong reference. le boudec's book seems appropriate here (cf.
> chap 2).
>
>
>
> Just assessing statistical significance would be great. I would recommend
> the study of this book: “Jain, Raj. *The art of computer systems
> performance analysis*. John Wiley & Sons, 2008.”
>
> I am sure this would be perfect for certain types of academic papers. I
> would rather have a clearer recommendation.
>
>
>
> In order  to be scientifically correct, the most important part would be
> to assess the probability distribution of the data. I am trying to find a
> solution where that wouldn’t be necessary.  Of course it would not hold for
> all cases, but the goal is to find a pareto-optimal solution where the
> summarized result would be representative enough for the test sample and

---

From: Paul Emmerich <[email-masked]>
Date: Mon, 9 Nov 2015 18:40:33 +0100

Hi,

On 03.11.15 09:45, Stenio Fernandes wrote:
> follows a heavy-tailed probability distribution function, which means
> that there is a non-negligible probability that a random variable will
> take huge values. these values might be erroneously considered as outliers.

this is a really important point. I have benchmarked software where the 
99th percentile of the latency is twice the average/median and the 
99.9th percentile ten times the average/median.
This is an important performance characteristic for latency-sensitive 
applications that isn't captured by taking just 20 measurements. So I'd 
really like to see a standard that calls for thousands of latency 
measurements to capture this properly.

You can also get interesting insights into a black-box device by looking 
at histograms/probability density functions. For example, you can figure 
out if the device processes packets in batches, estimate the batch size, 
figure out at which rates interrupt moderation algorithms change etc. 
(This is, of course, not really a performance metric, just an 
interesting insight.)

Paul

-- 
Paul Emmerich
Technical University of Munich (TUM)
Department of Informatics
Chair for Network Architectures and Services

---

From: Marius Georgescu <[email-masked]>
Date: Tue, 10 Nov 2015 10:18:58 +0900

Hi Paul,

Please see my answers inline.

> On Nov 10, 2015, at 02:40, Paul Emmerich <[email-masked]> wrote:
> 
> Hi,
> 
> this is a really important point. I have benchmarked software where the 99th percentile of the latency is twice the average/median and the 99.9th percentile ten times the average/median.

Can you give us more context (test setup; physical/virtualized tester/DUT; one tester/sender_receiver tester ... ) on these measurements?

> This is an important performance characteristic for latency-sensitive applications that isn't captured by taking just 20 measurements. So I'd really like to see a standard that calls for thousands of latency measurements to capture this properly.
> 

I think we should keep practicality in mind here. If we follow RFC2544.latency measurement, the frame stream has to be 2 min long. 2000 min ~ 33h  of testing for just one test sounds unreasonable to me. I would agree to have a lower bound for the sample size as RFC2544 actually recommends (n > 20). 

> You can also get interesting insights into a black-box device by looking at histograms/probability density functions. For example, you can figure out if the device processes packets in batches, estimate the batch size, figure out at which rates interrupt moderation algorithms change etc. (This is, of course, not really a performance metric, just an interesting insight.)
> 

I agree this is an interesting insight. It can also be the base for a decision between summarizing functions. However, in the light of consistency and simplicity of the methodology, I think we would need to recommend one function. We could do that depending on the metric/DUT characteristics, previous testing behavior …

---

From: "MORTON, ALFRED C (AL)" <[email-masked]>
Date: Mon, 9 Nov 2015 20:40:41 -0500

Hi Marius, Paul, and all who have contributed so far.

a quick reply/differing opinion below.

> -----Original Message-----
> From: bmwg [mailto:[email-masked]] On Behalf Of Marius Georgescu
...
> >> that there is a non-negligible probability that a random variable
> >> will take huge values. these values might be erroneously considered
> as outliers.
> >
> > this is a really important point. I have benchmarked software where
> the 99th percentile of the latency is twice the average/median and the
> Can you give us more context (test setup; physical/virtualized
> tester/DUT; one tester/sender_receiver tester ... ) on these
> measurements?
[ACM] 
My understanding (and I've seen some results, but I've had trouble
re-locating them) is that both outliers and bimodal distributions
are more common in the world of virtual DUTs than they were in the
physical/past. Not only does this affect analysis, but the threshold
waiting time for packet arrival must be chosen carefully to even
measure such outliers.

> I think we should keep practicality in mind here. If we follow
> RFC2544.latency measurement, the frame stream has to be 2 min long. 2000
> min ~ 33h  of testing for just one test sounds unreasonable to me. I
> would agree to have a lower bound for the sample size as RFC2544
> actually recommends (n > 20).
[ACM] 
Latency (delay) and delay variation need many single delay measurements
to be meaningful. One way to view the variation is for a single flow of
packets with spacing that might come from an application, say 20ms spacing
for VoIP. Collecting a few thousand of such packets should not take so long.

> 
> > You can also get interesting insights into a black-box device by
> > looking at histograms/probability density functions. For example, you
> > can figure out if the device processes packets in batches, estimate
> > the batch size, figure out at which rates interrupt moderation
> > algorithms change etc. (This is, of course, not really a performance
> > metric, just an interesting insight.)
> >
> 
> I agree this is an interesting insight. It can also be the base for a
> decision between summarizing functions. However, in the light of
> consistency and simplicity of the methodology, I think we would need to
> recommend one function. We could do that depending on the metric/DUT
> characteristics, previous testing behavior …
[ACM] 
I agree the right summary statistics can only be chosen after an examination
of the raw distribution for a particular scenario.  If Bi-modal, the central
statistics of the sample could be meaningless. Without this examination,
I don't think one recommendation can always be right.

my 2 cents
Al
(as a participant)

---

From: Marius Georgescu <[email-masked]>
Date: Tue, 10 Nov 2015 14:24:45 +0900

Hello Al,

Thank you very much for joining the discussion. 
Please find my comments inline. 

> On Nov 10, 2015, at 10:40, MORTON, ALFRED C (AL) <[email-masked]> wrote:
> 
[MG]  
I think there is one thing that needs clarification. The procedure in RFC2544 says:

“The stream SHOULD be at least 120 seconds in duration.An identifying tag SHOULD be included in one frame after 60 seconds with the type of tag being implementation dependent.”

I never got to ask Scott this, but  would it make sense to tag more than one frame? If we tag all the frames in the stream, we would have (depending on the throughput) thousands of measurements in 60 seconds.  

> I don't think one recommendation can always be right.
[MG] I agree that analyzing the probability distribution is the best way to choose, but maybe not the most consistent procedure. I had a short discussion about this with Scott before the BMWG meeting. In my understanding of his feedback, the consistency in recommending a summarizing function is more important. In other words, if we leave room for interpreting the data, the results might be more misleading than if we choose  the “wrong”  summarizing function.

Best regards,
Marius

---

From: "MORTON, ALFRED C (AL)" <[email-masked]>
Date: Tue, 10 Nov 2015 01:22:09 -0500

Hi Marius,

On your first comment below, yes, we need to move beyond the 
RFC2544 latency of a single packet in new work (while keeping the 
intent of earlier work in mind).

On your second point, relaying Scott's comment about hard and fast rules:
I guess I would tend toward reporting the Median for any distribution
(it's not subject to the outliers like mean), but I still believe
that one statistic is not enough - a metric of variation is needed.

Al
(as participant)

> Sent: Tuesday, November 10, 2015 12:25 AM
> To: [email-masked]
> >>>> a word of caution here... a number of phenomena in computer
> >>>> networks follows a heavy-tailed probability distribution function,
> >>>> which means that there is a non-negligible probability that a
> >>>> random variable will take huge values. these values might be
> >>>> erroneously considered
> >> as outliers.
> >>>
> >> the 99th percentile of the latency is twice the average/median and
> >> the 99.9th percentile ten times the average/median.
> >>
> > re-locating them) is that both outliers and bimodal distributions are
> > more common in the world of virtual DUTs than they were in the
> >> applications that isn't captured by taking just 20 measurements. So
> >> I'd really like to see a standard that calls for thousands of latency
> >> RFC2544.latency measurement, the frame stream has to be 2 min long.
> >> 2000 min ~ 33h  of testing for just one test sounds unreasonable to
> >> me. I would agree to have a lower bound for the sample size as
> >> RFC2544 actually recommends (n > 20).
> > [ACM]
> > Latency (delay) and delay variation need many single delay
> > measurements to be meaningful. One way to view the variation is for a
> > single flow of packets with spacing that might come from an
> > application, say 20ms spacing for VoIP. Collecting a few thousand of
> such packets should not take so long.
> [MG]
> “The stream SHOULD be at least 120 seconds in duration.An identifying
> tag SHOULD be included in one frame after 60 seconds with the type of
> tag being implementation dependent.”
> 
> I never got to ask Scott this, but  would it make sense to tag more than
> one frame? If we tag all the frames in the stream, we would have
> (depending on the throughput) thousands of measurements in 60 seconds.
> 
> >
> >>
> >>> looking at histograms/probability density functions. For example,
> >>> you can figure out if the device processes packets in batches,
> >>> estimate the batch size, figure out at which rates interrupt
> >>> moderation algorithms change etc. (This is, of course, not really a
> >>> performance metric, just an interesting insight.)
> >>>
> >>
> >> consistency and simplicity of the methodology, I think we would need
> >> to recommend one function. We could do that depending on the
> >> metric/DUT characteristics, previous testing behavior …
> > [ACM]
> > I agree the right summary statistics can only be chosen after an
> > examination of the raw distribution for a particular scenario.  If
> > Bi-modal, the central statistics of the sample could be meaningless.
> > Without this examination, I don't think one recommendation can always
> be right.
> >
> [MG] I agree that analyzing the probability distribution is the best way
> to choose, but maybe not the most consistent procedure. I had a short
> discussion about this with Scott before the BMWG meeting. In my
> understanding of his feedback, the consistency in recommending a
> summarizing function is more important. In other words, if we leave room
> for interpreting the data, the results might be more misleading than if
> we choose  the “wrong”  summarizing function.
> 
> Best regards,
> Marius

---

From: Marius Georgescu <[email-masked]>
Date: Tue, 10 Nov 2015 16:15:57 +0900

Hello Al,
> On Nov 10, 2015, at 15:22, MORTON, ALFRED C (AL) <[email-masked]> wrote:
> 
> Hi Marius,
> 
[MG]
Then, should we agree upon a new procedure for latency in one of the working group items/new working group item? Or maybe reference another procedure for Latency ? - I don’t know any better one.  
> that one statistic is not enough - a metric of variation is needed.
[MG]
I guess we can be sure there’s no perfect solution here.
After talking with you and Kostas about it, I am tending more towards median myself. 
For physical testing, the distribution tends to be normal (at least for my testing experiences). In this context the difference between mean and median would be negligible. 
Since in the virtual world (the future) bimodal is the new normal (if i may say so :), median seems like a better choice. 
I fully agree we should have an additional statistic, accounting for the variance somehow. I proposed the Margin of error. It can be the standard deviation, the standard error … 

Best regards,
Marius

---

From: Paul Emmerich <[email-masked]>
Date: Wed, 11 Nov 2015 10:29:31 +0100

Hi,

> I fully agree we should have an additional statistic, accounting for the variance somehow. I proposed the Margin of error. It can be the standard deviation, the standard error …
normally distributed latencies are actually pretty rare when testing 
devices that do any part of the processing in software. It doesn't even 
have to be virtualized. The main reason for this is batch processing of 
packets which drastically improves the performance.

Simple batching leads to a uniform distribution. However, there are 
different algorithms trying to optimize for different things in a 
typical software router which leads to really weird distributions.
For example, Linux uses polling in the NAPI to reduce interrupts and 
increase the batch size, but many drivers like Intel's ixgbe also 
feature a second interrupt moderation algorithm that further reduces 
interrupts. Both systems interact and you get weird distributions.
You can read more about interrupt handling for network processing in 
Linux in my paper about it at [1] if you are interested. (However, the 
paper does not yet look at distributions, it only states a few percentiles.)

I've uploaded an excerpt from one of my papers here [2] which shows the 
latency of a Linux system running Open vSwitch without any 
virtualization. An excerpt from the same paper with virtualization is 
available at [3], this looks more like a normal distribution with a long 
tail. (The paper is currently under peer review for a journal and will 
hopefully be published soon, I can share a pre-print privately with 
anyone who is interested in the full paper.)

Paul

[1] 
http://www.net.in.tum.de/fileadmin/bibtex/publications/papers/SPECTS15NAPIoptimization.pdf
[2] 
https://www.dropbox.com/s/dl9tmslubyd2j7m/Screenshot%202015-11-11%2010.17.05.png?dl=1
[3] 
https://www.dropbox.com/s/tia2lwhlt08hl8l/Screenshot%202015-11-11%2010.24.57.png?dl=1

---

From: Paul Emmerich <[email-masked]>
Date: Wed, 11 Nov 2015 15:11:04 +0100

Hi,

 > Can you give us more context (test setup; physical/virtualized 
tester/DUT; one tester/sender_receiver tester ... ) on these measurements?

Example 1: forwarding UDP packets with a userspace application at 20% of 
the maximum possible load between two ports (unidirectional, MoonGen as 
packet generator externally)

Median latency: 42 us, 99th perc: 45 us, 99.9th perc: 71 us

I then moved the same setup into a KVM VM connected via Open vSwitch and 
a VirtIO vNIC and the latency distribution changed (at 20% of the 
maximum load of the new setup). The traffic still came from an external 
host.

Median latency: 205 us, 99th perc: 341 us, 99.9th perc: 3030 us

Example 2: see my other email from earlier today. The long tail there 
isn't quite as long because it uses a "proper" packet forwarder instead 
of a userspace application. But the only reason it isn't as bad there is 
because there was no other load on the system.

Example 3: interesting things happen once other stuff runs on the same 
hypervisor. Note that this is a typical scenario for fancy NFV setups 
where you just deploy your VM whereever. The other VMs compete for 
resources and this can lead to excessive delays. There is an interesting 
paper by Whiteaker et al. which looks at latencies with Xen and 
Linux-VServer virtualization [1].

Is there a good reason why this can't be changed to something more 
modern for a new standard? For example, I usually aim for 1000 
timestamped packets per second in my tests which works just fine.

Paul

[1] http://ccr.sigcomm.org/online/files/p39-v41n1f2-whiteakerPS.pdf

---

From: Stenio Fernandes <[email-masked]>
Date: Wed, 11 Nov 2015 16:46:06 -0200

Very interesting results, Paul. I'd like to have a look at the results in
the journal paper.

In the past, statisticians struggled with a shortage of samples to do their
stuff. This is not the case for the computer networking people as we are
constantly flooded with samples.

The discussions so far have led me to conclude that in the context here,
there is no need to make any assumptions on the sample set. Any specific
measure of centrality or dispersion might not be precise enough in some
cases. As stated by others, mean/median would work for well-behaved (e.g.,
normally distributed) data, but would not work for multi-modal or
heavy-tailed ones. Recall that heavy-tailed distributions are usually
characterized by the shape and location parameters instead of mean and
variance. Regarding the number of samples, it is really tough to
characterize heavy-tailed or multi-modal distributions with a few samples,
even using advanced algorithms for maximum-likelihood estimation.

 Stenio

On Wed, Nov 11, 2015 at 12:11 PM, Paul Emmerich <[email-masked]>
wrote:

> I then moved the same setup into a KVM VM connected via Open vSwitch and a
> VirtIO vNIC and the latency distribution changed (at 20% of the maximum
> load of the new setup). The traffic still came from an external host.
>
> isn't quite as long because it uses a "proper" packet forwarder instead of
> a userspace application. But the only reason it isn't as bad there is
> hypervisor. Note that this is a typical scenario for fancy NFV setups where
> you just deploy your VM whereever. The other VMs compete for resources and
> this can lead to excessive delays. There is an interesting paper by
> Whiteaker et al. which looks at latencies with Xen and Linux-VServer
> virtualization [1].
>
>
> min ~ 33h  of testing for just one test sounds unreasonable to me. I would
> agree to have a lower bound for the sample size as RFC2544 actually
> recommends (n > 20).
>
> Is there a good reason why this can't be changed to something more modern
> for a new standard? For example, I usually aim for 1000 timestamped packets
> per second in my tests which works just fine.
>
>
> Paul
>

---

From: Marius Georgescu <[email-masked]>
Date: Thu, 12 Nov 2015 17:01:43 +0900

Hi Paul,

> On Nov 11, 2015, at 23:11, Paul Emmerich <[email-masked]> wrote:
> 
> Hi,
> 
> Example 1: forwarding UDP packets with a userspace application at 20% of the maximum possible load between two ports (unidirectional, MoonGen as packet generator externally)
> 
> I then moved the same setup into a KVM VM connected via Open vSwitch and a VirtIO vNIC and the latency distribution changed (at 20% of the maximum load of the new setup). The traffic still came from an external host.
> 
> Example 2: see my other email from earlier today. The long tail there isn't quite as long because it uses a "proper" packet forwarder instead of a userspace application. But the only reason it isn't as bad there is because there was no other load on the system.
> 

Thanks for sharing the results. They are indeed quite relevant. I would like to see the rest of the draft, if possible. 

> Example 3: interesting things happen once other stuff runs on the same hypervisor. Note that this is a typical scenario for fancy NFV setups where you just deploy your VM whereever. The other VMs compete for resources and this can lead to excessive delays. There is an interesting paper by Whiteaker et al. which looks at latencies with Xen and Linux-VServer virtualization [1].
> 
> 
> Is there a good reason why this can't be changed to something more modern for a new standard? For example, I usually aim for 1000 timestamped packets per second in my tests which works just fine.

I don’t think it would be a problem to have n>1000, as long as the test time would be 120s (or something more reasonable than 33h).

---

From: Marius Georgescu <[email-masked]>
Date: Thu, 12 Nov 2015 17:30:21 +0900

Hello Stenio,

> On Nov 12, 2015, at 03:46, Stenio Fernandes <[email-masked]> wrote:
> 
> Very interesting results, Paul. I'd like to have a look at the results in the journal paper.
> 
> In the past, statisticians struggled with a shortage of samples to do their stuff. This is not the case for the computer networking people as we are constantly flooded with samples. 
> 
> The discussions so far have led me to conclude that in the context here, there is no need to make any assumptions on the sample set. Any specific measure of centrality or dispersion might not be precise enough in some cases. As stated by others, mean/median would work for well-behaved (e.g., normally distributed) data, but would not work for multi-modal or heavy-tailed ones. Recall that heavy-tailed distributions are usually characterized by the shape and location parameters instead of mean and variance. Regarding the number of samples, it is really tough to characterize heavy-tailed or multi-modal distributions with a few samples, even using advanced algorithms for maximum-likelihood estimation. 

As stated in the email to Paul, I don’t think increasing the sample size would be a problem, as long as the (minimum) test time is within reasonable limits. I agree that the stability of the dataset is important. However, a more stable dataset would still need to be summarized/reported. If not average (arithmetic mean), median … how can we meaningfully and consistently express a test result ? 

From the Al and Paul’s examples/replies as well as other discussions I had in IETF94 about this, a “fast&hard” solution could be the Median + a measure of variance.

Marius

---

From: Paul Emmerich <[email-masked]>
Date: Thu, 12 Nov 2015 13:38:54 +0100

Hi,

> tester/DUT; one tester/sender_receiver tester ... ) on these measurements?

I also found an example for a non-normally distributed latency on a 
hardware switch.

Test setup: two flows of traffic coming from different ports on the 
switch that are directed to a single output port. The sum of two 
incoming flows is less than the capacity of the outgoing link, so this 
is not an overload scenario but a typical load scenario for a switch.

This setup results in a bimodal latency distribution, each packet either 
has to wait for a short time if there is a packet from the other flow 
currently being transmitted, or it can be transmitted immediately if the 
link is free.

The buffers on the switch are virtually empty as I used constant 
inter-packet spacings.

The histogram of a 1 Gbit/s flow is available at [1]. The second 
competing flow was 4 Gbit/s in this test setup, however, the slower flow 
shown in the graph was prioritized (which doesn't matter as the output 
was not overloaded). Changing the relative rates changes which of the 
two peaks dominates, but the basic building blocks are still the two 
normal distributions.

A median value is often completely meaningless in such a scenario.

Paul

[1] https://www.dropbox.com/s/xbgelt336ade0dx/two-flows-pica8.pdf?dl=1

---

From: Paul Emmerich <[email-masked]>
Date: Thu, 12 Nov 2015 14:04:12 +0100

Hi,

On 11.11.15 19:46, Stenio Fernandes wrote:
> cases. As stated by others, mean/median would work for well-behaved
> (e.g., normally distributed) data, but would not work for multi-modal or
> characterize heavy-tailed or multi-modal distributions with a few
> samples, even using advanced algorithms for maximum-likelihood estimation.
my suggestion would be characterizing the latency by providing several 
percentiles. I'd suggest using 10, 20, ... 90, 99, (and maybe 99.9 if we 
define the required number of samples as large enough to capture long 
tails). This is still a small number of data points that can easily be 
included in a test report. But it is effectively a quantized CDF and 
therefore captures the whole distribution including its shape reasonably 
well.

Paul

---

From: "Marius Georgescu" <[email-masked]>
Date: Fri, 13 Nov 2015 00:19:58 +0900

[MG]  Thanks for sharing your paper. I am not sure if this solution would
make a good comparison base. As I see it, the test report has to be
synthetic enough to allow easy comparison. Reporting a single number might
not be enough, but reporting 10 numbers is too much imo.

---

From: Paul Emmerich <[email-masked]>
Date: Thu, 12 Nov 2015 17:55:50 +0100

> not be enough, but reporting 10 numbers is too much imo.

Maybe the latency report can be split into two categories: typical 
latency and worst-case latency. The former being something like average 
and standard deviation (or median and 1st/3rd quartile), the latter the 
90th and 99th percentile? A full test report should (optionally?) 
include the full CDF or histogram as a graph.

  Paul

---

From: "MORTON, ALFRED C (AL)" <[email-masked]>
Date: Thu, 12 Nov 2015 13:32:48 -0500

> From: bmwg [mailto:[email-masked]] On Behalf Of Paul Emmerich
> Sent: Thursday, November 12, 2015 11:56 AM
> To: [email-masked]
> > [MG]  Thanks for sharing your paper. I am not sure if this solution
> > would make a good comparison base. As I see it, the test report has to
> > be synthetic enough to allow easy comparison. Reporting a single
> > number might not be enough, but reporting 10 numbers is too much imo.
> 
[ACM] 
I have been suggesting (in many places and drafts) that the "worst case"
delay should be characterized with RFC5481 PDV, so that it is a view of
delay variation and more easily comparable across test runs. The High
percentile as a single measure of PDV is built-in, and of course the
CDF or histogram is a possibility:
https://tools.ietf.org/html/rfc5481#section-4.2

Al
(as a participant)

---

From: Marius Georgescu <[email-masked]>
Date: Fri, 13 Nov 2015 09:43:16 +0900

> On Nov 13, 2015, at 01:55, Paul Emmerich <[email-masked]> wrote:
> 
> Maybe the latency report can be split into two categories: typical latency and worst-case latency. The former being something like average and standard deviation (or median and 1st/3rd quartile), the latter the 90th and 99th percentile? A full test report should (optionally?) include the full CDF or histogram as a graph.
> 

MG: That sounds like a good idea to me. In the light of recent discussions, maybe median + 1st&3rd quartiles would be a better choice for the "typical latency” (i was thinking regular/common latency could be more descriptive name). A  MAY for fine grain analysis with histograms sounds good as well.

---

From: Marius Georgescu <[email-masked]>
Date: Fri, 13 Nov 2015 09:57:26 +0900

> On Nov 13, 2015, at 03:32, MORTON, ALFRED C (AL) <[email-masked]> wrote:
> 
MG: I like the idea of using the 99.9th percentile as a single measure for the “Worst case” latency.

---

From: Stenio Fernandes <[email-masked]>
Date: Fri, 13 Nov 2015 09:34:07 -0500

On Thu, Nov 12, 2015 at 7:57 PM, Marius Georgescu <[email-masked]

> the “Worst case” latency.

[SF] it seems an interesting approach to keep it simple. ECDFs or
histograms would also help, but in the case of data that follows
heavy-tailed distributions, the graphs would be really weird. They are
better presented in a log-log scale and sometimes as an inverted ECDF.
Anyway, the general approach for further analysis is within the scope of
Exploratory Data Analysis (EDA), which includes all descriptive statistics
and graphical methods. So, I agree with the idea of having typical and
worst-case analysis, and for the optional full report a suggestion could be
to make an EDA on the data. And I would suggest NIST's Engineering
Statistics Handbook (free, online) for further reference (cf. chapter on
EDA: http://www.itl.nist.gov/div898/handbook/eda/section1/eda1.htm)