[bmwg] MLRsearch progress update

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

Short version:
No updated draft version yet.
New open points about throughput and related text of RFC 1242 and RFC 2544.
Some logic and terminology improvements, done in code only.

Long version (uses new terminology):

There are both practical and theoretical reasons
explaining why no new draft version is ready yet.

Theoretical reasons come from grey areas in RFC 1242 and RFC 2544.
Let me talk about those in some detail here.

The grey areas are related to a possibility of
(what I refer in this note as) a "loss inversion".
It is a phenomenon when a trial conducted at a higher load
has zero frame loss, but another trial conducted at a lower load
has a non-zero frame loss.

This is impossible to happen when looking only at trial outcomes
of one throuput search that uses simple bisection.
That is because with simple bisection, it is guaranteed
that all trials subsequent after a zero loss are conducted at higher loads,
and all trials subsequent after a non-zero loss are conducted at lower loads.

RFC 2544 formulations such as "the rate of the offered stream is reduced"
are perhaps aimed to prevent this phenomenon,
but only a stronger phrases like "all subsequent rates of the offered stream
shall be below" would achieve that goal.
The fact that MLRsearch can search for multiple loss ratio goals
means some trial outcomes can satisfy one loss ratio but not another,
so loss inversion cannot be prevented by limiting all subsequent loads.

The problematic occurences of loss inversion are those
where the larger load  outcome (zero loss) happened at final duration.
There are two sub-types of loss inversion, distinguished by the other trial
being done at the final (or shorter, respecively) trial duration.

The RFC 1242 motivation for througput is:
    Since even the loss of one frame in a
    data stream can cause significant delays while
    waiting for the higher level protocols to time out,
    it is useful to know the actual maximum data
    rate that the device can support.

It is not clear whether "the device can support" is supposed to mean
"the device can always support" or "the device can sometimes support".

The RFC 1242 definition of throughput is:
    The maximum rate at which none of the offered frames are dropped by the device.

As it mentions "the" offered frames, it probably refers to
the observed trial outcomes (not mere possibilities).

RFC 2544 is more specific:
    The throughput is the fastest rate at which the count of test frames
    transmitted by the DUT is equal to the number of test frames sent to
    it by the test equipment.

That would mean maximizing over observed outcomes, and in case of loss inversion
the higher load should be returned (it is the "can sometimes support" throughput).

MLRsearch instead searches below the smaller load,
as its goal is closer to estimating the "device can always support" load
(at least for trials at final duration).

Regarding loss inversion when the lossy lower load
is from shorter duration trial, RFC 2544 mentions the "final determination":
    The tests that involve some form of "binary
    search", for example the throughput test, to determine the exact
    result MAY use a shorter trial duration to minimize the length of the
    search procedure, but the final determination SHOULD be made with
    full length trials.

For the "device can sometimes support" throughput, this is not an issue
(no-loss shorter trial could have seen some loss if duration was longer).

MLRsearch honors the "final determination" requirement
by re-measuring any relevant bound at final trial duration
(the new outcome replaces the one from the shorter duration).
But, strictly speaking, any lossy short trial already disproves
"device can always support" hypothesis for that particular load.

So the current MLRsearch implementation is not really consistent,
neither with "always supports" nor with "sometimes supports"
interpretation of throughput.
In contrast, RFC 2544 is consistent with "cometimes supports",
and RFC 1242 definition is also consistent with "sometimes supports"
(only the motivation looks to be closer to "always supports").

MLRsearch could be made consistent with "sometimes supports",
simply by searching for higher loss ratios first.
Vratko prefers updating the throughput definition to be explicitly
"always supports", including losses from short duration trials.
There may be other options.
Either way, it is a big decision, to be done at BMWG level.
I guess it is the question of how relevant the RFC 1242 motivation still is.


Practical reasons (of no new draft) come mainly from more complicated logic.
Even though the actual Python code is now more modular and readable
compared to the previous version, the logic itself is more tightly coupled,
so it is harder to describe its abstractions.
For example, a search phase focusing on one loss ratio goals
has to be able to correctly handle "surprising" trial outcomes
(e.g. loss inversion or longer trial duration)
left over from a phase focused on another loss ratio goal.


For those interested in evolving implementation, there is a new
Python implementation currently at https://gerrit.fd.io/r/c/csit/+/36061
(marked as abandoned only while waiting for upgraded tooling)
it uses updated terminology and includes multiple logic updates.

Highlights:

+ Brand new APIs and more standardized terminology.
  Example: "zero loss load" instead of "NDR" or "throughput".

+ Trial durations in inner cycle, loss ratios in outer cycle.
  This means search for zero loss load (at final trial duration)
  completes before search for non-zero loss load starts
  (with initial trial duration).

+ Each loss ratio can have different width goal.

+ In uneven splits, the lower subinterval is the narrower one.

+ Additional ways to prevent wastefully narrow intervals.

+ Do as much math in integers as possible (to prevent rounding errors).
  The previous way of "conservative rounding" cannot work
  across more than one level of trial duration.

Vratko.