Benchmarking Working Group M. Konstantynowicz, Ed.
Internet-Draft V. Polak, Ed.
Intended status: Informational Cisco Systems
Expires: May 17, 2019 November 13, 2018

Multiple Loss Ratio Search for Packet Throughput (MLRsearch)


This document proposes changes to [RFC2544], specifically to packet throughput search methodology, by defining a new search algorithm referred to as Multiple Loss Ratio search (MLRsearch for short). Instead of relying on binary search with pre-set starting offered load, it proposes a novel approach discovering the starting point in the initial phase, and then searching for packet throughput based on defined packet loss ratio (PLR) input criteria and defined final trial duration time. One of the key design principles behind MLSsearch is minimizing the total test duration and searching for multiple packet throughput rates (each with a corresponding PLR) concurrently, instead of doing it sequentially.

The main motivation behind MLRsearch is the new set of challenges and requirements posed by NFV (Network Function Virtualization), specifically software based implementations of NFV data planes. Using [RFC2544] in the experience of the authors yields often not repetitive and not replicable end results due to a large number of factors that are out of scope for this draft. MLRsearch aims to address this chalenge and define a common (standard?) way to evaluate NFV packet throughput performance that takes into account varying characteristics of NFV systems under test.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on May 17, 2019.

Copyright Notice

Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents ( in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

1. Terminology

2. MLRsearch Background

Multiple Loss Rate search (MLRsearch) is a packet throughput search algorithm suitable for deterministic (as opposed to probabilistic) systems. MLRsearch discovers multiple packet throughput rates in a single search, each rate associated with a distinct Packet Loss Ratio (PLR) criteria.

Two popular names for particular PLR criteria are Non-Drop Rate (NDR, with PLR=0, zero packet loss) and Partial Drop Rate (PDR, with PLR>0, non-zero packet loss). MLRsearch discovers NDR and PDR in a single search reducing required execution time compared to separate binary searches for NDR and PDR. MLRsearch reduces execution time even further by relying on shorter trial durations of intermediate steps, with only the final measurements conducted at the specified final trial duration. This results in the shorter overall search execution time when compared to a standard NDR/PDR binary search, while guaranteeing the same or similar results. (TODO: Specify "standard" in the previous sentence.)

If needed, MLRsearch can be easily adopted to discover more throughput rates with different pre-defined PLRs.

Unless otherwise noted, all throughput rates are always bi-directional aggregates of two equal (symmetric) uni-directional packet rates received and reported by an external traffic generator.

3. MLRsearch Overview

The main properties of MLRsearch:

The main benefits of MLRsearch vs. binary search include:


4. Sample Implementation

Following is a brief description of a sample MLRsearch implementation based on the open-source code running in CSIT project as part of a Continuous Integration / Continuous Development (CI/CD) framework.

4.1. Input Parameters

  1. maximum_transmit_rate - maximum packet transmit rate to be used by external traffic generator, limited by either the actual Ethernet link rate or traffic generator NIC model capabilities. Sample defaults: 2 * 14.88 Mpps for 64B 10GE link rate, 2 * 18.75 Mpps for 64B 40GE NIC maximum rate.
  2. minimum_transmit_rate - minimum packet transmit rate to be used for measurements. MLRsearch fails if lower transmit rate needs to be used to meet search criteria. Default: 2 * 10 kpps (could be higher).
  3. final_trial_duration - required trial duration for final rate measurements. Default: 30 sec.
  4. initial_trial_duration - trial duration for initial MLRsearch phase. Default: 1 sec.
  5. final_relative_width - required measurement resolution expressed as (lower_bound, upper_bound) interval width relative to upper_bound. Default: 0.5%.
  6. packet_loss_ratio - maximum acceptable PLR search criteria for PDR measurements. Default: 0.5%.
  7. number_of_intermediate_phases - number of phases between the initial phase and the final phase. Impacts the overall MLRsearch duration. Less phases are required for well behaving cases, more phases may be needed to reduce the overall search duration for worse behaving cases. Default (2). (Value chosen based on limited experimentation to date. More experimentation needed to arrive to clearer guidelines.)

4.2. Initial phase

  1. First trial measures at maximum rate and discovers MRR. a. in: trial_duration = initial_trial_duration. b. in: offered_transmit_rate = maximum_transmit_rate. c. do: single trial. d. out: measured loss ratio. e. out: mrr = measured receive rate.
  2. Second trial measures at MRR and discovers MRR2. a. in: trial_duration = initial_trial_duration. b. in: offered_transmit_rate = MRR. c. do: single trial. d. out: measured loss ratio. e. out: mrr2 = measured receive rate.
  3. Third trial measures at MRR2. a. in: trial_duration = initial_trial_duration. b. in: offered_transmit_rate = MRR2. c. do: single trial. d. out: measured loss ratio.

4.3. Non-initial phases

  1. Main loop: a. in: trial_duration for the current phase. Set to initial_trial_duration for the first intermediate phase; to final_trial_duration for the final phase; or to the element of interpolating geometric sequence for other intermediate phases. For example with two intermediate phases, trial_duration of the second intermediate phase is the geometric average of initial_strial_duration and final_trial_duration. b. in: relative_width_goal for the current phase. Set to final_relative_width for the final phase; doubled for each preceding phase. For example with two intermediate phases, the first intermediate phase uses quadruple of final_relative_width and the second intermediate phase uses double of final_relative_width. c. in: ndr_interval, pdr_interval from the previous main loop iteration or the previous phase. If the previous phase is the initial phase, both intervals have lower_bound = MRR2, uper_bound = MRR. Note that the initial phase is likely to create intervals with invalid bounds. d. do: According to the procedure described in point 2, either exit the phase (by jumping to 1.g.), or prepare new transmit rate to measure with. e. do: Perform the trial measurement at the new transmit rate and trial_duration, compute its loss ratio. f. do: Update the bounds of both intervals, based on the new measurement. The actual update rules are numerous, as NDR external search can affect PDR interval and vice versa, but the result agrees with rules of both internal and external search. For example, any new measurement below an invalid lower_bound becomes the new lower_bound, while the old measurement (previously acting as the invalid lower_bound) becomes a new and valid upper_bound. Go to next iteration (1.c.), taking the updated intervals as new input. g. out: current ndr_interval and pdr_interval. In the final phase this is also considered to be the result of the whole search. For other phases, the next phase loop is started with the current results as an input.
  2. New transmit rate (or exit) calculation (for 1.d.):

5. Known Implementations

The only known working implementatin of MLRsearch is in Linux Foundation CSIT project.

5.1. CSIT Implementation Deviations

This document so far has been describing a simplified version of MLRsearch algorithm. The full algorithm as implemented contains additional logic, which makes some of the details (but not general ideas) above incorrect. Here is a short description of the additional logic as a list of principles, explaining their main differences from (or additions to) the simplified description, but without detailing their mutual interaction.

  1. Logarithmic transmit rate. In order to better fit the relative width goal, the interval doubling and halving is done differently. For example, the middle of 2 and 8 is 4, not 5.
  2. Optimistic maximum rate. The increased rate is never higher than the maximum rate. Upper bound at that rate is always considered valid.
  3. Pessimistic minimum rate. The decreased rate is never lower than the minimum rate. If a lower bound at that rate is invalid, a phase stops refining the interval further (until it gets re-measured).
  4. Conservative interval updates. Measurements above current upper bound never update a valid upper bound, even if drop ratio is low. Measurements below current lower bound always update any lower bound if drop ratio is high.
  5. Ensure sufficient interval width. Narrow intervals make external search take more time to find a valid bound. If the new transmit increased or decreased rate would result in width less than the current goal, increase/decrease more. This can happen if the measurement for the other interval makes the current interval too narrow. Similarly, take care the measurements in the initial phase create wide enough interval.
  6. Timeout for bad cases. The worst case for MLRsearch is when each phase converges to intervals way different than the results of the previous phase. Rather than suffer total search time several times larger than pure binary search, the implemented tests fail themselves when the search takes too long (given by argument timeout).

6. IANA Considerations


7. Security Considerations


8. Acknowledgements


9. Normative References

[RFC2544] Bradner, S. and J. McQuaid, "Benchmarking Methodology for Network Interconnect Devices", RFC 2544, DOI 10.17487/RFC2544, March 1999.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017.

Authors' Addresses

Maciek Konstantynowicz (editor) Cisco Systems EMail:
Vratko Polak (editor) Cisco Systems EMail: