< 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/ |