Re: [bmwg] Call for views: draft-vpolak-mkonstan-bmwg-mlrsearch-03

["Vratko Polak -X (vrpolak - PANTHEON TECH SRO at Cisco)" <[e-mail]>]

> Have you done a case study, in which you compared
> the efficiency of MLR search with that of the traditional binary search? 

We did few things.

We compared search duration when we first employed MLRsearch.
Previously, we used binary search (two separate tests, for NDR and for PDR)
with trial duration 10 seconds.
MLRsearch implementation (single test searching for both values)
was using 30 second trial in the last phase
(and accuracy goal was more strict),
and it was still faster.
How much faster, that depends mainly on how stable the DUT behavior is.
When writing the draft, we chose the conservative
"it greatly reduces (>50%) the overall duration".

Before that, during development, I used a small simulator
(to verify MLRsearch works and how well it works).
I never got time to make it really usable,
but anyone can take a look [1] and try to make it work.

> How much faster is your algorithm than traditional binary search?

I think the best case is MLRsearch being 7 times faster.
In worst case MLRsearch is slower than binary search,
but that needs really adversarial DUT behavior (or very bad luck).
Mere "unstable" DUT behavior is usually not enough.

> Could we state something like
> "MLR produces better quality results than binary search" ?

In practice yes. In theory no.

Strictly speaking, the result comes from (the internal search part of)
the last phase of MLR search, which is equivalent to bisection.
Everything that happens before affects only total duration,
not the final result.

Obviously, improved speed allows users to use more narrow target width,
and longer trial duration, improving quality of the result.

Less obviously, earlier phases of MLRsearch are affecting
the position of the final bisection interval.
For deterministic systems it should not matter,
but for less deterministic systems it does.
In my experience there are two effects.
Firstly, having multiple intermediate phases
means more extreme results are less probable.
Secondly, the initial phase (with mrr and mrr2)
is likely to start the search in higher values.
Overall, MLRsearch tends to give results
with higher average, but smaller standard deviation.
But in practice the differences are quite small,
trial duration alone usually has larger effect.

> Please send me a pointer, if you have published such results!

Have you seen the graphs in our presentations?
They come from real tests, but it is not many data points,
and they were selected to show a situation when "something notable" happens.

We are publishing results from our official testing, but only the values
(NDR and PDR, lower bound for each, from 10 runs per test),
duration is not visible.
As we have many tests, we had never run the full set for both searches.

Here [2] is last "release" using bisection,
and here [3] is the first with MLRsearch.
But the DUT tested (VPP) is also a different release,
so it is not an apples-to-apples comparison.
The links are showing "vhost" tests,
which are the least stable from the set.

> I wonder if you are willing to do an update

Yes, updates are on my TODO list.

On implementation front I plan to support configurable number
of loss ratios (not just NDR and PDR).

On documentation front I plan to discuss more deeply
some trade-offs and decisions in the implementation.

On combined front, improvements can be added
(use valid bound from neighboring loss ratio target
when a bound becomes invalid on re-measurement)
and removed (currently I think the "wider interval in earlier phase" idea
is too risky in bad case and not speedy enough in good case).

> in the near future (i.e. within a few weeks)

Hard to tell. I give it a 40% chance
that an update will arrive that soon.

Vratko.

[1] https://gerrit.fd.io/r/c/csit/+/11897
[2] https://docs.fd.io/csit/rls1804/report/vpp_performance_tests/packet_throughput_graphs/vm_vhost.html#ndr-throughput
[3] https://docs.fd.io/csit/rls1807/report/vpp_performance_tests/packet_throughput_graphs/vm_vhost.html#n-hsw-x520

-----Original Message-----
From: bmwg <[e-mail]> On Behalf Of Gabor LENCSE
Sent: Thursday, 2020-November-19 08:01
To: [e-mail]
Subject: Re: [bmwg] Call for views: draft-vpolak-mkonstan-bmwg-mlrsearch-03

Dear Authors,

I am interested in your draft. I promised (right now at the BMWG 
meeting) to review it. I wonder if you are willing to do an update in 
the near future (i.e. within a few weeks), as then I would review the 
updated version.

I also have questions. Have you done a case study, in which you compared 
the efficiency of MLR search with that of the traditional binary search? 
I would be interested in RFC 2544 compliant (zero loss rate) throughput 
measurements. How much faster is your algorithm than traditional binary 
search? Could we state something like "MLR produces better quality 
results than binary search" ?

Please send me a pointer, if you have published such results!

Cheers,

Gábor

On 11/18/2020 8:53 PM, Maciek Konstantynowicz (mkonstan) wrote:
> Dear BMWG Contributors,
>
> We would like to ask your view regarding draft-vpolak-mkonstan-bmwg-mlrsearch-03:
>
> 1. During the interim BMWG meeting post IETF-107 [1] there was quite some interests in working on this draft in BMWG:
>     a. Our (authors) understanding is that BMWG agreed to adopt this work as a BMWG draft and collaborate on making it into RFC.
>     b. But in the absence of the last statement being present in the meeting notes [1], we would like to re-confirm this.
>     c. If it is re-confirmed, we will re-post the draft with its name updated to draft-bmwg-mlrsearch.
>
> 2. If point 1. is cleared, we would like to then invite folks to collaborate closer with us and progress this draft to RFC:
>     a. Welcome all comments identifying areas that require clarification and/or gaps that need to be addressed.
>     b. Substantial additions and co-authors are welcome.
>
> We do have a discussion slot regarding above in the IETF-109 BMWG meeting, slides are available at [2].
>
> Cheers,
> Maciek and Vratko (authors)
>
> [1] notes-ietf-107-bmwg, https://etherpad.ietf.org:9009/p/notes-ietf-107-bmwg?useMonospaceFont=true
> [2] slides for draft-vpolak-mkonstan-bmwg-mlrsearch-03, https://datatracker.ietf.org/meeting/109/materials/slides-109-bmwg-multiple-loss-ratio-search-00
> _______________________________________________
> bmwg mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/bmwg

_______________________________________________
bmwg mailing list
[e-mail]
https://www.ietf.org/mailman/listinfo/bmwg