< draft-vpolak-bmwg-plrsearch-01.txt   draft-vpolak-bmwg-plrsearch-02.txt >
Benchmarking Working Group M. Konstantynowicz, Ed. Benchmarking Working Group M. Konstantynowicz, Ed.
Internet-Draft V. Polak, Ed. Internet-Draft V. Polak, Ed.
Intended status: Informational Cisco Systems Intended status: Informational Cisco Systems
Expires: September 12, 2019 March 11, 2019 Expires: January 9, 2020 July 08, 2019
Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch) Probabilistic Loss Ratio Search for Packet Throughput (PLRsearch)
draft-vpolak-bmwg-plrsearch-01 draft-vpolak-bmwg-plrsearch-02
Abstract Abstract
This document addresses challenges while applying methodologies This document addresses challenges while applying methodologies
described in [RFC2544] to benchmarking software based NFV (Network described in [RFC2544] to benchmarking software based NFV (Network
Function Virtualization) data planes over an extended period of time, Function Virtualization) data planes over an extended period of time,
sometimes referred to as "soak testing". Packet throughput search sometimes referred to as "soak testing". Packet throughput search
approach proposed by this document assumes that system under test is approach proposed by this document assumes that system under test is
probabilistic in nature, and not deterministic. probabilistic in nature, and not deterministic.
skipping to change at page 1, line 35 skipping to change at page 1, line 35
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 12, 2019. This Internet-Draft will expire on January 9, 2020.
Copyright Notice Copyright Notice
Copyright (c) 2019 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 22 skipping to change at page 2, line 22
3.1. Device Under Test . . . . . . . . . . . . . . . . . . . . 4 3.1. Device Under Test . . . . . . . . . . . . . . . . . . . . 4
3.2. System Under Test . . . . . . . . . . . . . . . . . . . . 4 3.2. System Under Test . . . . . . . . . . . . . . . . . . . . 4
3.3. SUT Configuration . . . . . . . . . . . . . . . . . . . . 4 3.3. SUT Configuration . . . . . . . . . . . . . . . . . . . . 4
3.4. SUT Setup . . . . . . . . . . . . . . . . . . . . . . . . 4 3.4. SUT Setup . . . . . . . . . . . . . . . . . . . . . . . . 4
3.5. Network Traffic . . . . . . . . . . . . . . . . . . . . . 5 3.5. Network Traffic . . . . . . . . . . . . . . . . . . . . . 5
3.6. Packet . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.6. Packet . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.6.1. Packet Offered . . . . . . . . . . . . . . . . . . . 5 3.6.1. Packet Offered . . . . . . . . . . . . . . . . . . . 5
3.6.2. Packet Received . . . . . . . . . . . . . . . . . . . 5 3.6.2. Packet Received . . . . . . . . . . . . . . . . . . . 5
3.6.3. Packet Lost . . . . . . . . . . . . . . . . . . . . . 5 3.6.3. Packet Lost . . . . . . . . . . . . . . . . . . . . . 5
3.6.4. Other Packets . . . . . . . . . . . . . . . . . . . . 5 3.6.4. Other Packets . . . . . . . . . . . . . . . . . . . . 5
3.6.5. Tasks As Packets . . . . . . . . . . . . . . . . . . 6
3.7. Traffic Profile . . . . . . . . . . . . . . . . . . . . . 6 3.7. Traffic Profile . . . . . . . . . . . . . . . . . . . . . 6
3.8. Traffic Generator . . . . . . . . . . . . . . . . . . . . 6 3.8. Traffic Generator . . . . . . . . . . . . . . . . . . . . 6
3.9. Offered Load . . . . . . . . . . . . . . . . . . . . . . 6 3.9. Offered Load . . . . . . . . . . . . . . . . . . . . . . 6
3.10. Trial Measurement . . . . . . . . . . . . . . . . . . . . 7 3.10. Trial Measurement . . . . . . . . . . . . . . . . . . . . 6
3.11. Trial Duration . . . . . . . . . . . . . . . . . . . . . 7 3.11. Trial Duration . . . . . . . . . . . . . . . . . . . . . 7
3.12. Packet Loss . . . . . . . . . . . . . . . . . . . . . . . 7 3.12. Packet Loss . . . . . . . . . . . . . . . . . . . . . . . 7
3.12.1. Loss Count . . . . . . . . . . . . . . . . . . . . . 7 3.12.1. Loss Count . . . . . . . . . . . . . . . . . . . . . 7
3.12.2. Loss Rate . . . . . . . . . . . . . . . . . . . . . 7 3.12.2. Loss Rate . . . . . . . . . . . . . . . . . . . . . 7
3.12.3. Loss Ratio . . . . . . . . . . . . . . . . . . . . . 8 3.12.3. Loss Ratio . . . . . . . . . . . . . . . . . . . . . 7
3.13. Trial Order Independent System . . . . . . . . . . . . . 8 3.13. Trial Order Independent System . . . . . . . . . . . . . 7
3.14. Trial Measurement Result Distribution . . . . . . . . . . 8 3.14. Trial Measurement Result Distribution . . . . . . . . . . 8
3.15. Average Loss Ratio . . . . . . . . . . . . . . . . . . . 8 3.15. Average Loss Ratio . . . . . . . . . . . . . . . . . . . 8
3.16. Duration Independent System . . . . . . . . . . . . . . . 9 3.16. Duration Independent System . . . . . . . . . . . . . . . 8
3.17. Load Regions . . . . . . . . . . . . . . . . . . . . . . 9 3.17. Load Regions . . . . . . . . . . . . . . . . . . . . . . 9
3.17.1. Zero Loss Region . . . . . . . . . . . . . . . . . . 9 3.17.1. Zero Loss Region . . . . . . . . . . . . . . . . . . 9
3.17.2. Guaranteed Loss Region . . . . . . . . . . . . . . . 9 3.17.2. Guaranteed Loss Region . . . . . . . . . . . . . . . 9
3.17.3. Non-Deterministic Region . . . . . . . . . . . . . . 9 3.17.3. Non-Deterministic Region . . . . . . . . . . . . . . 9
3.17.4. Normal Region Ordering . . . . . . . . . . . . . . . 10 3.17.4. Normal Region Ordering . . . . . . . . . . . . . . . 9
3.18. Deterministic System . . . . . . . . . . . . . . . . . . 10 3.18. Deterministic System . . . . . . . . . . . . . . . . . . 10
3.19. Througphput . . . . . . . . . . . . . . . . . . . . . . . 10 3.19. Througphput . . . . . . . . . . . . . . . . . . . . . . . 10
3.20. Deterministic Search . . . . . . . . . . . . . . . . . . 10 3.20. Deterministic Search . . . . . . . . . . . . . . . . . . 10
3.21. Probabilistic Search . . . . . . . . . . . . . . . . . . 11 3.21. Probabilistic Search . . . . . . . . . . . . . . . . . . 10
3.22. Loss Ratio Function . . . . . . . . . . . . . . . . . . . 11 3.22. Loss Ratio Function . . . . . . . . . . . . . . . . . . . 11
3.23. Target Loss Ratio . . . . . . . . . . . . . . . . . . . . 11 3.23. Target Loss Ratio . . . . . . . . . . . . . . . . . . . . 11
3.24. Critical Load . . . . . . . . . . . . . . . . . . . . . . 11 3.24. Critical Load . . . . . . . . . . . . . . . . . . . . . . 11
3.25. Critical Load Estimate . . . . . . . . . . . . . . . . . 11 3.25. Critical Load Estimate . . . . . . . . . . . . . . . . . 11
3.26. Fitting Function . . . . . . . . . . . . . . . . . . . . 11 3.26. Fitting Function . . . . . . . . . . . . . . . . . . . . 11
3.27. Shape of Fitting Function . . . . . . . . . . . . . . . . 12 3.27. Shape of Fitting Function . . . . . . . . . . . . . . . . 11
3.28. Parameter Space . . . . . . . . . . . . . . . . . . . . . 12 3.28. Parameter Space . . . . . . . . . . . . . . . . . . . . . 12
4. Abstract Algorithm . . . . . . . . . . . . . . . . . . . . . 12 4. Abstract Algorithm . . . . . . . . . . . . . . . . . . . . . 12
4.1. High level description . . . . . . . . . . . . . . . . . 12 4.1. High level description . . . . . . . . . . . . . . . . . 12
4.2. Main Ideas . . . . . . . . . . . . . . . . . . . . . . . 12 4.2. Main Ideas . . . . . . . . . . . . . . . . . . . . . . . 12
4.3. Probabilistic Notions . . . . . . . . . . . . . . . . . . 13 4.2.1. Trial Durations . . . . . . . . . . . . . . . . . . . 13
4.3.1. Loss Count Only . . . . . . . . . . . . . . . . . . . 13 4.2.2. Target Loss Ratio . . . . . . . . . . . . . . . . . . 13
4.3.2. Independent Trials . . . . . . . . . . . . . . . . . 13 4.3. PLRsearch Building Blocks . . . . . . . . . . . . . . . . 13
4.3.3. Trial Durations . . . . . . . . . . . . . . . . . . . 14 4.3.1. Bayesian Inference . . . . . . . . . . . . . . . . . 13
4.3.4. Target Loss Ratio . . . . . . . . . . . . . . . . . . 14 4.3.2. Iterative Search . . . . . . . . . . . . . . . . . . 14
4.3.5. Critical Load . . . . . . . . . . . . . . . . . . . . 14 4.3.3. Fitting Functions . . . . . . . . . . . . . . . . . . 14
4.3.6. Load Regions . . . . . . . . . . . . . . . . . . . . 15 4.3.4. Measurement Impact . . . . . . . . . . . . . . . . . 14
4.3.7. Finite Models . . . . . . . . . . . . . . . . . . . . 15 4.3.5. Fitting Function Coefficients Distribution . . . . . 15
4.4. PLRsearch Building Blocks . . . . . . . . . . . . . . . . 15 4.3.6. Exit Condition . . . . . . . . . . . . . . . . . . . 15
4.4.1. Bayesian Inference . . . . . . . . . . . . . . . . . 15 4.3.7. Integration . . . . . . . . . . . . . . . . . . . . . 15
4.4.2. Iterative Search . . . . . . . . . . . . . . . . . . 16 4.3.8. Optimizations . . . . . . . . . . . . . . . . . . . . 15
4.4.3. Poisson Distribution . . . . . . . . . . . . . . . . 16 4.3.9. Offered Load Selection . . . . . . . . . . . . . . . 16
4.4.4. Fitting Functions . . . . . . . . . . . . . . . . . . 16 4.3.10. Trend Analysis . . . . . . . . . . . . . . . . . . . 16
4.4.5. Measurement Impact . . . . . . . . . . . . . . . . . 17 5. Sample Implementation Specifics: FD.io CSIT . . . . . . . . . 16
4.4.6. Fitting Function Coefficients Distribution . . . . . 17 5.1. Measurement Delay . . . . . . . . . . . . . . . . . . . . 16
4.4.7. Integration . . . . . . . . . . . . . . . . . . . . . 18 5.2. Rounding Errors and Underflows . . . . . . . . . . . . . 17
4.4.8. Optimizations . . . . . . . . . . . . . . . . . . . . 18 5.3. Fitting Functions . . . . . . . . . . . . . . . . . . . . 17
5. Sample Implementation Specifics: FD.io CSIT . . . . . . . . . 18 5.3.1. Stretch Function . . . . . . . . . . . . . . . . . . 18
5.1. Measurement Delay . . . . . . . . . . . . . . . . . . . . 18 5.3.2. Erf Function . . . . . . . . . . . . . . . . . . . . 18
5.2. Rounding Errors and Underflows . . . . . . . . . . . . . 19 5.4. Prior Distributions . . . . . . . . . . . . . . . . . . . 19
5.3. Fitting Functions . . . . . . . . . . . . . . . . . . . . 19 5.5. Integrator . . . . . . . . . . . . . . . . . . . . . . . 19
5.3.1. Stretch Function . . . . . . . . . . . . . . . . . . 20 5.6. Offered Load Selection . . . . . . . . . . . . . . . . . 20
5.3.2. Erf Function . . . . . . . . . . . . . . . . . . . . 20 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20
5.4. Prior Distributions . . . . . . . . . . . . . . . . . . . 21 7. Security Considerations . . . . . . . . . . . . . . . . . . . 20
5.5. Integrator . . . . . . . . . . . . . . . . . . . . . . . 21 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 21
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
7. Security Considerations . . . . . . . . . . . . . . . . . . . 22 9.1. Normative References . . . . . . . . . . . . . . . . . . 21
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 22 9.2. Informative References . . . . . . . . . . . . . . . . . 21
9. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 21
9.1. Normative References . . . . . . . . . . . . . . . . . . 22
9.2. Informative References . . . . . . . . . . . . . . . . . 22
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22
1. Motivation 1. Motivation
Network providers are interested in throughput a system can sustain. Network providers are interested in throughput a system can sustain.
[RFC2544] assumes loss ratio is given by a deterministic function of [RFC2544] assumes loss ratio is given by a deterministic function of
offered load. But NFV software systems are not deterministic enough. offered load. But NFV software systems are not deterministic enough.
This makes deterministic algorithms (such as Binary Search per This makes deterministic algorithms (such as Binary Search per
[RFC2544] and [draft-vpolak-mkonstan-bmwg-mlrsearch] with single [RFC2544] and [draft-vpolak-mkonstan-bmwg-mlrsearch] with single
trial) to return results, which when repeated show relatively high trial) to return results, which when repeated show relatively high
skipping to change at page 4, line 30 skipping to change at page 4, line 27
software components (such as operating system kernel). It is not software components (such as operating system kernel). It is not
possible to run devices without also running the other components, possible to run devices without also running the other components,
and hardware resources are shared between both. and hardware resources are shared between both.
For purposes of testing, the whole set of hardware and software For purposes of testing, the whole set of hardware and software
components is called "system under test" (SUT). As SUT is the part components is called "system under test" (SUT). As SUT is the part
of the whole test setup performance of which can be measured by of the whole test setup performance of which can be measured by
[RFC2544] methods, this document uses SUT instead of [RFC2544] DUT. [RFC2544] methods, this document uses SUT instead of [RFC2544] DUT.
Device under test (DUT) can be re-introduced when analysing test Device under test (DUT) can be re-introduced when analysing test
results using whitebox techniques, but this document sticks to results using whitebox techniques, but that is outside the scope of
blackbox testing. this document.
3.2. System Under Test 3.2. System Under Test
System under test (SUT) is a part of the whole test setup whose System under test (SUT) is a part of the whole test setup whose
performance is to be benchmarked. The complete methodology contains performance is to be benchmarked. The complete methodology contains
other parts, whose performance is either already established, or not other parts, whose performance is either already established, or not
affecting the benchmarking result. affecting the benchmarking result.
3.3. SUT Configuration 3.3. SUT Configuration
skipping to change at page 5, line 15 skipping to change at page 5, line 15
3.5. Network Traffic 3.5. Network Traffic
Network traffic is a type of interaction between system under test Network traffic is a type of interaction between system under test
and the rest of the system (traffic generator), used to gather and the rest of the system (traffic generator), used to gather
information about the system under test performance. PLRsearch is information about the system under test performance. PLRsearch is
applicable only to areas where network traffic consists of packets. applicable only to areas where network traffic consists of packets.
3.6. Packet 3.6. Packet
Unit of interaction between traffic generator and the system under Unit of interaction between traffic generator and the system under
test. Term "packet" is used also as an abstractions of Ethernet test. Term "packet" is used also as an abstraction of Ethernet
frames. frames.
3.6.1. Packet Offered 3.6.1. Packet Offered
Packet can be offered, which means it is sent from traffic generator Packet can be offered, which means it is sent from traffic generator
to the system under test. to the system under test.
Each offered packet is assumed to become received or lost in a short Each offered packet is assumed to become received or lost in a short
time. time.
skipping to change at page 6, line 7 skipping to change at page 6, line 7
Usually, the number of packets lost is computed as the number of Usually, the number of packets lost is computed as the number of
packets offered, minus the number of packets received. packets offered, minus the number of packets received.
3.6.4. Other Packets 3.6.4. Other Packets
PLRsearch is not considering other packet behaviors known from PLRsearch is not considering other packet behaviors known from
networking (duplicated, reordered, greatly delayed), assuming the networking (duplicated, reordered, greatly delayed), assuming the
test specification reclassifies those behaviors to fit into the first test specification reclassifies those behaviors to fit into the first
three categories. three categories.
3.6.5. Tasks As Packets
Ethernet frames are the prime example of packets, but other units are
possible.
For example, a task processing system can fit the description.
Packet offered can stand for task submitted, packet received for task
processed successfully, and packet lost for task aborted (or not
processed successfully for some other reason).
In networking context, such a task can be a route update.
3.7. Traffic Profile 3.7. Traffic Profile
Usually, the performance of the system under test depends on a "type" Usually, the performance of the system under test depends on a "type"
of a particular packet (for example size), and "composition" if the of a particular packet (for example size), and "composition" if the
network traffic consists of a mixture of different packet types. network traffic consists of a mixture of different packet types.
Also, some systems under test contain multiple "ports" packets can be Also, some systems under test contain multiple "ports" packets can be
offered to and received from. offered to and received from.
All such qualities together (but not including properties of trial All such qualities together (but not including properties of trial
skipping to change at page 6, line 45 skipping to change at page 6, line 33
Traffic generator is the part of the whole test setup, distinct from Traffic generator is the part of the whole test setup, distinct from
the system under test, responsible both for offering packets in a the system under test, responsible both for offering packets in a
highly predictable manner (so the number of packets offered is highly predictable manner (so the number of packets offered is
known), and for counting received packets in a precise enough way (to known), and for counting received packets in a precise enough way (to
distinguish lost packets from tolerably delayed packets). distinguish lost packets from tolerably delayed packets).
Traffic generator must offer only packets compatible with the traffic Traffic generator must offer only packets compatible with the traffic
profile, and only count similarly compatible packets as received. profile, and only count similarly compatible packets as received.
Criteria defining which received packets are compatible are left for
test specification to decide.
3.9. Offered Load 3.9. Offered Load
Offered load is an aggregate rate (measured in packets per second) of Offered load is an aggregate rate (measured in packets per second) of
network traffic offered to the system under test, the rate is kept network traffic offered to the system under test, the rate is kept
constant for the duration of trial measurement. constant for the duration of trial measurement.
3.10. Trial Measurement 3.10. Trial Measurement
Trial measurement is a process of stressing (previously setup) system Trial measurement is a process of stressing (previously setup) system
under test by offering traffic of a particular offered load, for a under test by offering traffic of a particular offered load, for a
skipping to change at page 8, line 31 skipping to change at page 8, line 19
PLRsearch assumes the system under test is trial order independent. PLRsearch assumes the system under test is trial order independent.
In practice, most system under test are not entirely trial order In practice, most system under test are not entirely trial order
independent, but it is not easy to devise an algorithm taking that independent, but it is not easy to devise an algorithm taking that
into account. into account.
3.14. Trial Measurement Result Distribution 3.14. Trial Measurement Result Distribution
When a trial order independent system is subjected to repeated trial When a trial order independent system is subjected to repeated trial
measurements of constant offered load and duration, Law of Large measurements of constant duration and offered load, Law of Large
Numbers implies the observed loss count frequencies will converge to Numbers implies the observed loss count frequencies will converge to
a specific probability distribution over possible loss counts. a specific probability distribution over possible loss counts.
This probability distribution is called trial measurement result This probability distribution is called trial measurement result
distribution, and it depends on all properties fixed when defining distribution, and it depends on all properties fixed when defining
it. That includes the system under test, its chosen configuration, it. That includes the system under test, its chosen configuration,
the chosen traffic profile, the offered load and the trial duration. the chosen traffic profile, the offered load and the trial duration.
As the system is trial order independent, trial measurement result As the system is trial order independent, trial measurement result
distribution does not depend on results of few initial trial distribution does not depend on results of few initial trial
skipping to change at page 9, line 50 skipping to change at page 9, line 39
A particular offered load value is said to belong to guaranteed loss A particular offered load value is said to belong to guaranteed loss
region, if the probability of seeing zero loss trial measurement region, if the probability of seeing zero loss trial measurement
result (for non-negligible count of packets offered) is exactly zero, result (for non-negligible count of packets offered) is exactly zero,
or at least practically indistinguishable from zero. or at least practically indistinguishable from zero.
3.17.3. Non-Deterministic Region 3.17.3. Non-Deterministic Region
A particular offered load value is said to belong to non- A particular offered load value is said to belong to non-
deterministic region, if the probability of seeing zero loss trial deterministic region, if the probability of seeing zero loss trial
measurement result (for non-negligible count of packets offered) measurement result (for non-negligible count of packets offered) is
practically distinguishable from both zero and one. practically distinguishable from both zero and one.
3.17.4. Normal Region Ordering 3.17.4. Normal Region Ordering
Although theoretically the three regions can be arbitrary sets, this Although theoretically the three regions can be arbitrary sets, this
document assumes they are intervals, where zero loss region contains document assumes they are intervals, where zero loss region contains
values smaller than non-deterministic region, which in turn contains values smaller than non-deterministic region, which in turn contains
values smaller than guaranteed loss region. values smaller than guaranteed loss region.
3.18. Deterministic System 3.18. Deterministic System
A hypothetical duration independent system with normal region A hypothetical duration independent system with normal region
ordering, whose non-deterministic region is extremely narrow; only ordering, whose non-deterministic region is extremely narrow (only
present due to "practical distinguishibility" and cases when the present due to "practical distinguishibility" and cases when the
expected number of packets offered is not and integer. expected number of packets offered is not and integer).
A duration independent system which is not deterministic is called A duration independent system which is not deterministic is called
non- deterministic system. non- deterministic system.
3.19. Througphput 3.19. Througphput
Throughput is the highest offered load provably causing zero packet Throughput is the highest offered load provably causing zero packet
loss for trial measurements of duration at least 60 seconds. loss for trial measurements of duration at least 60 seconds.
For duration independent systems with normal region ordering, the For duration independent systems with normal region ordering, the
skipping to change at page 11, line 9 skipping to change at page 10, line 48
Multiple runs of a deterministic search launched against a non- Multiple runs of a deterministic search launched against a non-
deterministic system can return varied results within non- deterministic system can return varied results within non-
deterministic region. The exact distribution of deterministic search deterministic region. The exact distribution of deterministic search
results depends on the algorithm used. results depends on the algorithm used.
3.21. Probabilistic Search 3.21. Probabilistic Search
Any algorithm which performs probabilistic computations based on Any algorithm which performs probabilistic computations based on
observed results of trial measurements, and which does not assume observed results of trial measurements, and which does not assume
that non-deterministic region is practically absent is called that non-deterministic region is practically absent, is called
probabilistic search. probabilistic search.
A probabilistic search algorithm, which would assume that non- A probabilistic search algorithm, which would assume that non-
deterministic region is practically absent, does not really need to deterministic region is practically absent, does not really need to
perform probabilistic computations, so it would become a perform probabilistic computations, so it would become a
deterministic search. deterministic search.
While probabilistic search for estimating throughput is possible, it While probabilistic search for estimating throughput is possible, it
would need a careful model for boundary between zero loss region and would need a careful model for boundary between zero loss region and
non-deterministic region, and it would need a lot of measurements of non-deterministic region, and it would need a lot of measurements of
skipping to change at page 11, line 40 skipping to change at page 11, line 30
This function is initially unknown. This function is initially unknown.
3.23. Target Loss Ratio 3.23. Target Loss Ratio
Input parameter of PLRsearch. The average loss ratio the output of Input parameter of PLRsearch. The average loss ratio the output of
PLRsearch aims to achieve. PLRsearch aims to achieve.
3.24. Critical Load 3.24. Critical Load
Aggregate rate of network traffic, which would lead to average loss Aggregate rate of network traffic, which would lead to average loss
ratio exactly matching target loss ratio (when used as the offered ratio exactly matching target loss ratio, if used as the offered load
load for infinite many trial measurement). for infinite many trial measurement.
3.25. Critical Load Estimate 3.25. Critical Load Estimate
Any quantitative description of the possible critical load PLRsearch Any quantitative description of the possible critical load PLRsearch
is able to give after observing finite amount of trial measurements. is able to give after observing finite amount of trial measurements.
3.26. Fitting Function 3.26. Fitting Function
Any function PLRsearch uses internally instead of the unknown loss Any function PLRsearch uses internally instead of the unknown loss
ratio function. Typically chosen from small set of formulas (shapes) ratio function. Typically chosen from small set of formulas (shapes)
skipping to change at page 12, line 36 skipping to change at page 12, line 32
First group has a single argument: measurer. This is a callback First group has a single argument: measurer. This is a callback
(function) accepting offered load and duration, and returning the (function) accepting offered load and duration, and returning the
measured loss count. measured loss count.
Second group consists of load related arguments required for measurer Second group consists of load related arguments required for measurer
to work correctly, typically minimal and maximal load to offer. to work correctly, typically minimal and maximal load to offer.
Also, target loss ratio (if not hardcoded) is a required argument. Also, target loss ratio (if not hardcoded) is a required argument.
Third group consists of time related arguments. Typically the Third group consists of time related arguments. Typically the
duration for the first trial measurement, duration increment per duration for the first trial measurement, duration increment per
subsequent trial measurement and total time for search. Some subsequent trial measurement, and total time for search. Some
PLRsearch implementation may use estimation accuracy parameters as an PLRsearch implementation may use estimation accuracy parameters as an
exit condition instead of total search time. exit condition instead of total search time.
The returned quantities should describe the final (or best) estimate The returned quantities should describe the final (or best) estimate
of critical load. Implementers can chose any description that suits of critical load. Implementers can chose any description that suits
their users, typically it is average and standard deviation, or lower their users, typically it is average and standard deviation, or lower
and upper boundary. and upper boundary.
4.2. Main Ideas 4.2. Main Ideas
The search tries to perform measurements at offered load close to the The search tries to perform measurements at offered load close to the
critical load, because measurement results at offered loads far from critical load, because measurement results at offered loads far from
the critical load give less information on precise location of the the critical load give less information on precise location of the
critical load. As virtually every trial measurement result alters critical load. As virtually every trial measurement result alters
the estimate of the critical load, offered loads vary as they the estimate of the critical load, offered loads vary as they
approach the critical load. approach the critical load.
The only quantity of trial measurement result affecting the
computation is loss count. No latency (or other information) is
taken into account.
PLRsearch uses Bayesian Inference, computed using numerical PLRsearch uses Bayesian Inference, computed using numerical
integration, which takes long time to get reliable enough results. integration, which takes long time to get reliable enough results.
Therefore it takes some time before the most recent measurement Therefore it takes some time before the most recent measurement
result starts affecting subsequent offered loads and critical rate result starts affecting subsequent offered loads and critical rate
estimates. estimates.
During the search, PLRsearch spawns few processes that perform During the search, PLRsearch spawns few processes that perform
numerical computations, the main process is calling the measurer to numerical computations, the main process is calling the measurer to
perform trial measurements, without any significant delays between perform trial measurements, without any significant delays between
them. The durations of the trial measurements are increasing them. The durations of the trial measurements are increasing
linearly, as higher number of trial measurement results take longer linearly, as higher number of trial measurement results take longer
to process. to process.
4.3. Probabilistic Notions 4.2.1. Trial Durations
Before internals of PLRsearch are described, we need to define
notions valid for situations when loss ratio is not entirely
determined by offered load.
Some of the notions already incorporate assumptions the PLRsearch
algorithm applies.
4.3.1. Loss Count Only
It is assumed that the traffic generator detects duplicate packets on
receive, and reports this as an error.
No latency (or other information) is taken into account.
4.3.2. Independent Trials
PLRsearch still assumes the system under test can be subjected to
trial measurements. The loss count is no longer determined
precisely, but it is assumed that for every system under test, its
configuration, traffic type and trial duration, there is a
probability distribution over possible loss counts.
This implies trial measurements are probabilistic, but the
distribution is independent of possible previous trial measurements.
Independence from previous measurements is not guaranteed in the real
world. The previous measurements may improve performance (via long-
term warmup effects), or decrease performance (due to long-term
resource leaks).
4.3.3. Trial Durations
[RFC2544] motivates the usage of at least 60 second duration by the [RFC2544] motivates the usage of at least 60 second duration by the
idea of the system under test slowly running out of resources (such idea of the system under test slowly running out of resources (such
as memory buffers). as memory buffers).
Practical results when measuring NFV software systems show that Practical results when measuring NFV software systems show that
relative change of trial duration has negligible effects on average relative change of trial duration has negligible effects on average
loss ratio, compared to relative change in offered load. loss ratio, compared to relative change in offered load.
While the standard deviation of loss ratio usually shows some effects While the standard deviation of loss ratio usually shows some effects
of trial duration, they are hard to model; so further assumtions in of trial duration, they are hard to model. So PLRsearch assumes SUT
PLRsearch will make it insensitive to trial duration. is duration independent, and chooses trial durations only based on
numeric integration requirements.
4.3.4. Target Loss Ratio
Loss ratio function could be used to generalize throughput as the
biggest offered load which still leads to zero average loss ratio.
Unfortunately, most realistic loss ratio functions always predict
non- zero (even if negligible) average loss ratio.
On the other hand, users do not really require the average loss ratio
to be an exact zero. Most users are satisfied when the average loss
ratio is small enough.
One of PLRsearch inputs is called target loss ratio. It is the loss 4.2.2. Target Loss Ratio
ratio users would accept as negligible.
(TODO: Link to why we think 1e-7 is acceptable loss ratio.) (TODO: Link to why we think 1e-7 is acceptable loss ratio.)
4.3.5. Critical Load 4.3. PLRsearch Building Blocks
Critical load (sometimes called critical rate) is the offered load
which leads to average loss ratio to become exactly equal to the
target loss ratio.
In principle, there could be such loss ratio functions which allow
more than one offered load to achieve target loss ratio. To avoid
that, PLRsearch assumes only increasing loss ratio functions are
possible.
Similarly, some loss ratio functions may never return the target loss
ratio. PLRsearch assumes loss ratio function is continuous, that the
average loss ratio approaches zero as offered load approaches zero,
and that the average loss ratio approaches one as offered load
approaches infinity.
Under these assumptions, each loss ratio function has unique critical
load. PLRsearch attempts to locate the critical load.
4.3.6. Load Regions
Critical region is the interval of offered load close to critical
load, where single measurement is not likely to distinguish whether
the critical load is higher or lower than the current offered load.
In typical case of small target loss ratio, rates below critical
region form "zero loss region", and rates above form "high loss
region".
4.3.7. Finite Models
Of course, finite amount of trial measurements, each of finite
duration does not give enough information to pinpoint the critical
load exactly. Therefore the output of PLRsearch is just an estimate
with some precision.
Aside of the usual substitution of infinitely precise real numbers by
finitely precise floating point numbers, there are two other
instances within PLRsearch where an objects of high information are
replaced by objects of low information.
One is the probability distribution of loss count, which is replaced
by average loss ratio. The other is the loss ratio function, which
is replaced by a few parameters, to be described later.
4.4. PLRsearch Building Blocks
Here we define notions used by PLRsearch which are not applicable to Here we define notions used by PLRsearch which are not applicable to
other search methods, nor probabilistic systems under test, in other search methods, nor probabilistic systems under test in
general. general.
4.4.1. Bayesian Inference 4.3.1. Bayesian Inference
Having reduced the model space significantly, the task of estimating PLRsearch uses a fixed set of fitting function shapes, and uses
the critical load becomes simple enough so that Bayesian inference Bayesian inference to track posterior distribution on each fitting
can be used (instead of neural networks, or other Artifical function parameter space.
Intelligence methods).
In this case, the few parameters describing the loss ration function Specifically, the few parameters describing a fitting function become
become the model space. Given a prior over the model space, and the model space. Given a prior over the model space, and trial
trial duration results, a posterior distribution can be computed, duration results, a posterior distribution is computed, together with
together with quantities describing the critical load estimate. quantities describing the critical load estimate.
4.4.2. Iterative Search Likelihood of a particular loss count is computed using Poisson
distribution of average loss rate given by the fitting function (at
specific point of parameter space).
Side note: Binomial Distribution is a better fit compared to Poisson
distribution (acknowledging that the number of packets lost cannot be
higher than the number of packets offered), but the difference tends
to be relevant only in high loss region. Using Poisson distribution
lowers the impact of measurements in high loss region, thus helping
the algorithm to converge towards critical load faster.
4.3.2. Iterative Search
The idea PLRsearch is to iterate trial measurements, using Bayesian The idea PLRsearch is to iterate trial measurements, using Bayesian
inference to compute both the current estimate of the critical load inference to compute both the current estimate of the critical load
and the next offered load to measure at. and the next offered load to measure at.
The required numerical computations are done in parallel with the The required numerical computations are done in parallel with the
trial measurements. trial measurements.
This means the result of measurement "n" comes as an (additional) This means the result of measurement "n" comes as an (additional)
input to the computation running in parallel with measurement "n+1", input to the computation running in parallel with measurement "n+1",
and the outputs of the computation are used for determining the and the outputs of the computation are used for determining the
offered load for measurement "n+2". offered load for measurement "n+2".
Other schemes are possible, aimed to increase the number of Other schemes are possible, aimed to increase the number of
measurements (by decreasing their duration), which would have even measurements (by decreasing their duration), which would have even
higher number of measurements run before a result of a measurement higher number of measurements run before a result of a measurement
affects offered load. affects offered load.
4.4.3. Poisson Distribution 4.3.3. Fitting Functions
For given offered load, number of packets lost during trial
measurement is assumed to come from Poisson distribution, and the
(unknown) Poisson parameter is expressed as average loss ratio.
Side note: Binomial Distribution is a better fit compared to Poisson
distribution (acknowledging that the number of packets lost cannot be
higher than the number of packets offered), but the difference tends
to be relevant only in high loss region. Using Poisson distribution
lowers the impact of measurements in high loss region, thus helping
the algorithm to focus on critical region better.
4.4.4. Fitting Functions
There are great many increasing functions (as candidates for the loss
ratio function).
To make the space of possible functions more tractable, some other
simplifying assumptions are needed. As the algorithm will be
examining (also) loads very close to the critical load, linear
approximation to the loss rate function around the critical load is
important. But as the search algorithm needs to evaluate the
function also far away from the critical region, the approximate
function has to be reasonably behaved for every positive offered
load, specifically it cannot predict non- positive packet loss ratio.
Within this document, "fitting function" is the name for such a To make the space of possible loss ratio functions more tractable the
reasonably behaved function, which approximates the loss ratio algorithm uses only few fitting function shapes for its predicitons.
function well in the critical region. As the search algorithm needs to evaluate the function also far away
from the critical load, the fitting function have to be reasonably
behaved for every positive offered load, specifically cannot cannot
predict non-positive packet loss ratio.
4.4.5. Measurement Impact 4.3.4. Measurement Impact
Results from trials far from the critical region are likely to affect Results from trials far from the critical load are likely to affect
the critical rate estimate negatively, as the fitting function does the critical load estimate negatively, as the fitting functions do
not need to be a good approximation there. This is true mainly for not need to be good approximations there. This is true mainly for
high loss region, as in zero loss region even badly behaved fitting guaranteed loss region, as in zero loss region even badly behaved
function predicts loss count to be "almost zero", so seeing a fitting function predicts loss count to be "almost zero", so seeing a
measurement confirming the loss has been zero indeed has small measurement confirming the loss has been zero indeed has small
impact. impact.
Discarding some results, or "suppressing" their impact with ad-hoc Discarding some results, or "suppressing" their impact with ad-hoc
methods (other than using Poisson distribution instead of binomial) methods (other than using Poisson distribution instead of binomial)
is not used, as such methods tend to make the overall search is not used, as such methods tend to make the overall search
unstable. We rely on most of measurements being done (eventually) unstable. We rely on most of measurements being done (eventually)
within the critical region, and overweighting far-off measurements near the critical load, and overweighting far-off measurements
(eventually) for well- behaved fitting functions. (eventually) for well-behaved fitting functions.
Speaking about new trials, each next trial will be done at offered
load equal to the current average of the critical load. Alternative
methods for selecting offered load might be used, in an attempt to
speed up convergence. For example by employing the aforementioned
unstable ad-hoc methods.
4.4.6. Fitting Function Coefficients Distribution 4.3.5. Fitting Function Coefficients Distribution
To accomodate systems with different behaviours, the fitting function To accomodate systems with different behaviours, a fitting function
is expected to have few numeric parameters affecting its shape is expected to have few numeric parameters affecting its shape
(mainly affecting the linear approximation in the critical region). (mainly affecting the linear approximation in the critical region).
The general search algorithm can use whatever increasing fitting The general search algorithm can use whatever increasing fitting
function, some specific functions can described later. function, some specific functions are described later.
It is up to implementer to chose a fitting function and prior It is up to implementer to chose a fitting function and prior
distribution of its parameters. The rest of this document assumes distribution of its parameters. The rest of this document assumes
each parameter is independently and uniformly distributed over a each parameter is independently and uniformly distributed over a
common interval. Implementers are to add non-linear transformations common interval. Implementers are to add non-linear transformations
into their fitting functions if their prior is different. into their fitting functions if their prior is different.
4.3.6. Exit Condition
Exit condition for the search is either the standard deviation of the Exit condition for the search is either the standard deviation of the
critical load estimate becoming small enough (or similar), or overal critical load estimate becoming small enough (or similar), or overal
search time becoming long enough. search time becoming long enough.
The algorithm should report both average and standard deviation for The algorithm should report both average and standard deviation for
its critical load posterior. If the reported averages follow a trend its critical load posterior.
(without reaching equilibrium), average and standard deviation should
refer to the equilibrium estimates based on the trend, not to
immediate posterior values.
4.4.7. Integration 4.3.7. Integration
The posterior distributions for fitting function parameters will not The posterior distributions for fitting function parameters are not
be integrable in general. be integrable in general.
The search algorithm utilises the fact that trial measurement takes The search algorithm utilises the fact that trial measurement takes
some time, so this time can be used for numeric integration (using some time, so this time can be used for numeric integration (using
suitable method, such as Monte Carlo) to achieve sufficient suitable method, such as Monte Carlo) to achieve sufficient
precision. precision.
4.4.8. Optimizations 4.3.8. Optimizations
After enough trials, the posterior distribution will be concentrated After enough trials, the posterior distribution will be concentrated
in a narrow area of the parameter space. The integration method in a narrow area of the parameter space. The integration method
should take advantage of that. should take advantage of that.
Even in the concentrated area, the likelihood can be quite small, so Even in the concentrated area, the likelihood can be quite small, so
the integration algorithm should avoid underflow errors by some the integration algorithm should avoid underflow errors by some
means, for example by tracking the logarithm of the likelihood. means, for example by tracking the logarithm of the likelihood.
4.3.9. Offered Load Selection
The simplest rule is to set offered load for next trial measurememnt
equal to the current average (both over posterio and over fitting
function shapes) of the critical load estimate.
Contrary to critical load estimate computation, heuristic algorithms
affecting offered load selection do not introduce instability, and
can help with convergence speed.
4.3.10. Trend Analysis
If the reported averages follow a trend (maybe without reaching
equilibrium), average and standard deviation COULD refer to the
equilibrium estimates based on the trend, not to immediate posterior
values.
But such post-processing is discouraged, unless a clear reason for
the trend is known. Frequently, presence of such a trend is a sign
of some of PLRsearch assumption being violated (usually trial order
independence or duration independence).
It is RECOMMENDED to report any trend quantification together with
direct critical load estimate, so users can draw their own
conclusion. Alternatively, trend analysis may be a part of exit
conditions, requiring longer searches for systems displaying trends.
5. Sample Implementation Specifics: FD.io CSIT 5. Sample Implementation Specifics: FD.io CSIT
The search receives min_rate and max_rate values, to avoid The search receives min_rate and max_rate values, to avoid
measurements at offered loads not supporeted by the traffic measurements at offered loads not supporeted by the traffic
generator. generator.
The implemented tests cases use bidirectional traffic. The algorithm The implemented tests cases use bidirectional traffic. The algorithm
stores each rate as bidirectional rate (internally, the algorithm is stores each rate as bidirectional rate (internally, the algorithm is
agnostic to flows and directions, it only cares about overall counts agnostic to flows and directions, it only cares about overall counts
of packets sent and packets lost), but debug output from traffic of packets sent and packets lost), but debug output from traffic
skipping to change at page 19, line 6 skipping to change at page 17, line 13
traffic generator in use (T-Rex). traffic generator in use (T-Rex).
As measurements results come in, posterior distribution computation As measurements results come in, posterior distribution computation
takes more time (per sample), although there is a considerable takes more time (per sample), although there is a considerable
constant part (mostly for inverting the fitting functions). constant part (mostly for inverting the fitting functions).
Also, the integrator needs a fair amount of samples to reach the Also, the integrator needs a fair amount of samples to reach the
region the posterior distribution is concentrated at. region the posterior distribution is concentrated at.
And of course, speed of the integrator depends on computing power of And of course, speed of the integrator depends on computing power of
the CPU the algorithm is able to use. the CPUs the algorithm is able to use.
All those timing related effects are addressed by arithmetically All those timing related effects are addressed by arithmetically
increasing trial durations with configurable coefficients (currently increasing trial durations with configurable coefficients (currently
5.1 seconds for the first trial, each subsequent trial being 0.1 5.1 seconds for the first trial, each subsequent trial being 0.1
second longer). second longer).
5.2. Rounding Errors and Underflows 5.2. Rounding Errors and Underflows
In order to avoid them, the current implementation tracks natural In order to avoid them, the current implementation tracks natural
logarithm (instead of the original quantity) for any quantity which logarithm (instead of the original quantity) for any quantity which
is never negative. Logarithm of zero is minus infinity (not is never negative. Logarithm of zero is minus infinity (not
supported by Python), so special value "None" is used instead. supported by Python), so special value "None" is used instead.
Specific functions for frequent operations (such as "logarithm of sum Specific functions for frequent operations (such as "logarithm of sum
of exponentials") are defined to handle None correctly. of exponentials") are defined to handle None correctly.
5.3. Fitting Functions 5.3. Fitting Functions
Current implementation uses two fitting functions. In general, their Current implementation uses two fitting functions. In general, their
estimates for critical rate differ, which adds a simple source of estimates for critical rate differ, which adds a simple source of
systematic error, on top of randomness error reported by integrator. systematic error, on top of posterior dispersion reported by
Otherwise the reported stdev of critical rate estimate is integrator. Otherwise the reported stdev of critical rate estimate
unrealistically low. is unrealistically low.
Both functions are not only increasing, but also convex (meaning the Both functions are not only increasing, but also convex (meaning the
rate of increase is also increasing). rate of increase is also increasing).
As Primitive Function to any positive function is an increasing As Primitive Function to any positive function is an increasing
function, and Primitive Function to any increasing function is convex function, and Primitive Function to any increasing function is convex
function; both fitting functions were constructed as double Primitive function; both fitting functions were constructed as double Primitive
Function to a positive function (even though the intermediate Function to a positive function (even though the intermediate
increasing function is easier to describe). increasing function is easier to describe).
skipping to change at page 20, line 4 skipping to change at page 18, line 10
Both fitting functions have a "central point" and a "spread", varied Both fitting functions have a "central point" and a "spread", varied
by simply shifting and scaling (in x-axis, the offered load by simply shifting and scaling (in x-axis, the offered load
direction) the function to be doubly integrated. Scaling in y-axis direction) the function to be doubly integrated. Scaling in y-axis
(the loss rate direction) is fixed by the requirement of transfer (the loss rate direction) is fixed by the requirement of transfer
rate staying nearly constant in very high offered loads. rate staying nearly constant in very high offered loads.
In both fitting functions (as they are a double Primitive Function to In both fitting functions (as they are a double Primitive Function to
a symmetric function), the "central point" turns out to be equal to a symmetric function), the "central point" turns out to be equal to
the aforementioned limiting transfer rate, so the fitting function the aforementioned limiting transfer rate, so the fitting function
parameter is named "mrr", the same quantity our Maximum Receive Rate parameter is named "mrr", the same quantity CSIT Maximum Receive Rate
tests are designed to measure. tests are designed to measure.
Both fitting functions return logarithm of loss rate, to avoid Both fitting functions return logarithm of loss rate, to avoid
rounding errors and underflows. Parameters and offered load are not rounding errors and underflows. Parameters and offered load are not
given as logarithms, as they are not expected to be extreme, and the given as logarithms, as they are not expected to be extreme, and the
formulas are simpler that way. formulas are simpler that way.
Both fitting functions have several mathematically equivalent Both fitting functions have several mathematically equivalent
formulas, each can lead to an overflow or underflow in different formulas, each can lead to an overflow or underflow in different
places. Overflows can be eliminated by using different exact places. Overflows can be eliminated by using different exact
formulas for different argument ranges. Underflows can be avoided by formulas for different argument ranges. Underflows can be avoided by
using approximate formulas in affected argument ranges, such ranges using approximate formulas in affected argument ranges, such ranges
have their own formulas to compute. At the end, both fitting have their own formulas to compute. At the end, both fitting
function implementations contain multiple "if" branches, function implementations contain multiple "if" branches,
discontinuities are a possibility at range boundaries. discontinuities are a possibility at range boundaries.
Offered load for next trial measurement is the average of critical
rate estimate. During each measurement, two estimates are computed,
even though only one (in alternating order) is used for next offered
load.
5.3.1. Stretch Function 5.3.1. Stretch Function
The original function (before applying logarithm) is Primitive The original function (before applying logarithm) is Primitive
Function to Logistic Function. The name "stretch" is used for Function to Logistic Function. The name "stretch" is used for
related a function in context of neural networks with sigmoid related a function in context of neural networks with sigmoid
activation function. activation function.
Formula for stretch function: loss rate (r) computed from offered Formula for stretch fitting function: average loss rate (r) computed
load (b), mrr parameter (m) and spread parameter (a): from offered load (b), mrr parameter (m) and spread parameter (a),
given as InputForm of Wolfram language:
r = a (Log(E^(b/a) + E^(m/a)) - Log(1 + E^(m/a))) r = (a*(1 + E^(m/a))*Log[(E^(b/a) + E^(m/a))/(1 + E^(m/a))])/E^(m/a)
5.3.2. Erf Function 5.3.2. Erf Function
The original function is double Primitive Function to Gaussian The original function is double Primitive Function to Gaussian
Function. The name "erf" comes from error function, the first Function. The name "erf" comes from error function, the first
primitive to Gaussian. primitive to Gaussian.
Formula for erf function: loss rate (r) computed from offered load Formula for erf fitting function: average loss rate (r) computed from
(b), mrr parameter (m) and spread parameter (a): offered load (b), mrr parameter (m) and spread parameter (a), given
as InputForm of Wolfram language:
r = (b + (a (E^(-((b - m)^2/a^2)) - E^(-(m^2/a^2))))/Sqrt(Pi) + (b - r = ((a*(E^(-((b - m)^2/a^2)) - E^(-(m^2/a^2))))/Sqrt[Pi] + m*Erfc[m/a]
m) Erf((b - m)/a) - m Erf(m/a))/2 + (b - m)*Erfc[(-b + m)/a])/(1 + Erf[m/a])
5.4. Prior Distributions 5.4. Prior Distributions
The numeric integrator expects all the parameters to be distributed The numeric integrator expects all the parameters to be distributed
(independently and) uniformly on an interval (-1, 1). (independently and) uniformly on an interval (-1, 1).
As both "mrr" and "spread" parameters are positive and not not As both "mrr" and "spread" parameters are positive and not
dimensionless, a transformation is needed. Dimentionality is dimensionless, a transformation is needed. Dimentionality is
inherited from max_rate value. inherited from max_rate value.
The "mrr" parameter follows a Lomax Distribution with alpha equal to The "mrr" parameter follows a Lomax Distribution with alpha equal to
one, but shifted so that mrr is always greater than 1 packet per one, but shifted so that mrr is always greater than 1 packet per
second. second.
The "stretch" parameter is generated simply as the "mrr" value raised The "stretch" parameter is generated simply as the "mrr" value raised
to a random power between zero and one; thus it follows a Reciprocal to a random power between zero and one; thus it follows a Reciprocal
Distribution. Distribution.
skipping to change at page 22, line 8 skipping to change at page 20, line 8
default). default).
This combination showed the best behavior, as the integrator usually This combination showed the best behavior, as the integrator usually
follows two phases. First phase (where inherited biased distribution follows two phases. First phase (where inherited biased distribution
or single big sasmples are dominating) is mainly important for or single big sasmples are dominating) is mainly important for
locating the new area the posterior distribution is concentrated at. locating the new area the posterior distribution is concentrated at.
The second phase (dominated by whole sample population) is actually The second phase (dominated by whole sample population) is actually
relevant for the critical rate estimation. relevant for the critical rate estimation.
5.6. Offered Load Selection
First two measurements are hardcoded to happen at the middle of rate
interval and at max_rate. Next two measurements follow MRR-like
logic, offered load is decreased so that it would reach target loss
ratio if offered load decrease lead to equal decrease of loss rate.
Basis for offered load for next trial measurements is the integrated
average of current critical rate estimate, averaged over fitting
function.
There is one workaround implemented, aimed at reducing the number of
consequent zero loss measurements. The workaround first stores every
measurement result which loss ratio was the targed loss ratio or
higher. Sorted list (called lossy loads) of such results is
maintained.
When a sequence of one or more zero loss measurement results is
encountered, a smallest of lossy loads is drained from the list. If
the estimate average is smaller than the drained value, a weighted
average of this estimate and the drained value is used as the next
offered load. The weight of the drained value doubles with each
additional consecutive zero loss results.
This behavior helps the algorithm with convergence speed, as it does
not need so many zero loss result to get near critical load. Using
the smallest (not drained yet) of lossy loads makes it sure the new
offered load is unlikely to result in big loss region. Draining even
if the estimate is large enough helps to discard early measurements
when loss hapened at too low offered load. Current implementation
adds 4 copies of lossy loads and drains 3 of them, which leads to
fairly stable behavior even for somewhat inconsistent SUTs.
6. IANA Considerations 6. IANA Considerations
.. No requests of IANA.
7. Security Considerations 7. Security Considerations
.. Benchmarking activities as described in this memo are limited to
technology characterization of a DUT/SUT using controlled stimuli in
a laboratory environment, with dedicated address space and the
constraints specified in the sections above.
The benchmarking network topology will be an independent test setup
and MUST NOT be connected to devices that may forward the test
traffic into a production network or misroute traffic to the test
management network.
Further, benchmarking is performed on a "black-box" basis, relying
solely on measurements observable external to the DUT/SUT.
Special capabilities SHOULD NOT exist in the DUT/SUT specifically for
benchmarking purposes. Any implications for network security arising
from the DUT/SUT SHOULD be identical in the lab and in production
networks.
8. Acknowledgements 8. Acknowledgements
.. ..
9. References 9. References
9.1. Normative References 9.1. Normative References
[RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for [RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for
skipping to change at page 22, line 37 skipping to change at page 21, line 39
<https://www.rfc-editor.org/info/rfc2544>. <https://www.rfc-editor.org/info/rfc2544>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/info/rfc8174>. May 2017, <https://www.rfc-editor.org/info/rfc8174>.
9.2. Informative References 9.2. Informative References
[draft-vpolak-mkonstan-bmwg-mlrsearch] [draft-vpolak-mkonstan-bmwg-mlrsearch]
"Multiple Loss Ratio Search for Packet Throughput "Multiple Loss Ratio Search for Packet Throughput
(MLRsearch)", November 2018, <https://tools.ietf.org/html/ (MLRsearch)", July 2019, <https://tools.ietf.org/html/
draft-vpolak-mkonstan-bmwg-mlrsearch-00>. draft-vpolak-mkonstan-bmwg-mlrsearch>.
Authors' Addresses Authors' Addresses
Maciek Konstantynowicz (editor) Maciek Konstantynowicz (editor)
Cisco Systems Cisco Systems
Email: mkonstan@cisco.com Email: mkonstan@cisco.com
Vratko Polak (editor) Vratko Polak (editor)
Cisco Systems Cisco Systems
Email: vrpolak@cisco.com Email: vrpolak@cisco.com
 End of changes. 61 change blocks. 
249 lines changed or deleted 203 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/