ef94fd1f73f7a4a912c374183555f2d8dd23f6b0
[csit.git] / docs / ietf / draft-vpolak-mkonstan-bmwg-mlrsearch-00.md
1 ---
2 title: Multiple Loss Ratio Search for Packet Throughput (MLRsearch)
3 # abbrev: MLRsearch
4 docname: draft-vpolak-mkonstan-bmwg-mlrsearch-00
5 date: 2018-11-13
6
7 ipr: trust200902
8 area: ops
9 wg: Benchmarking Working Group
10 kw: Internet-Draft
11 cat: info
12
13 coding: us-ascii
14 pi:    # can use array (if all yes) or hash here
15 #  - toc
16 #  - sortrefs
17 #  - symrefs
18   toc: yes
19   sortrefs:   # defaults to yes
20   symrefs: yes
21
22 author:
23       -
24         ins: M. Konstantynowicz
25         name: Maciek Konstantynowicz
26         org: Cisco Systems
27         role: editor
28         email: mkonstan@cisco.com
29       -
30         ins: V. Polak
31         name: Vratko Polak
32         org: Cisco Systems
33         role: editor
34         email: vrpolak@cisco.com
35
36 normative:
37   RFC2544:
38   RFC8174:
39
40 informative:
41
42
43 --- abstract
44
45 This document proposes changes to [RFC2544], specifically to packet
46 throughput search methodology, by defining a new search algorithm
47 referred to as Multiple Loss Ratio search (MLRsearch for short). Instead
48 of relying on binary search with pre-set starting offered load, it
49 proposes a novel approach discovering the starting point in the initial
50 phase, and then searching for packet throughput based on defined packet
51 loss ratio (PLR) input criteria and defined final trial duration time.
52 One of the key design principles behind MLSsearch is minimizing the
53 total test duration and searching for multiple packet throughput rates
54 (each with a corresponding PLR) concurrently, instead of doing it
55 sequentially.
56
57 The main motivation behind MLRsearch is the new set of challenges and
58 requirements posed by NFV (Network Function Virtualization),
59 specifically software based implementations of NFV data planes. Using
60 [RFC2544] in the experience of the authors yields often not repetitive
61 and not replicable end results due to a large number of factors that are
62 out of scope for this draft. MLRsearch aims to address this chalenge and
63 define a common (standard?) way to evaluate NFV packet throughput
64 performance that takes into account varying characteristics of NFV
65 systems under test.
66
67 --- middle
68
69 # Terminology
70
71 * NDR - Non-Drop Rate, a packet throughput metric with Packet Loss Ratio
72   equal zero (a zero packet loss), expressed in packets-per-second
73   (pps). NDR packet throughput has an associated metric oftentimes
74   referred to as NDR bandwidth expressed in bits-per-second (bps), and
75   calculated as a product of:
76   * NDR packet rate for specific packet (frame) size, and
77   * Packet (L2 frame size) size in bits plus any associated L1 overhead.
78 * PLR - Packet Loss Ratio, a packet loss metric calculated as a ratio of
79  (packets_transmitted - packets_received) to packets_transmitted, over
80  the test trial duration.
81 * PDR - Partial-Drop Rate, a packet throughput metric with Packet Loss
82   Ratio greater than zero (a non-zero packet loss), expressed in
83   packets-per-second (pps). PDR packet throughput has an associated
84   metric oftentimes referred to as PDR bandwidth expressed in bits-per-
85   second (bps), and calculated as a product of:
86   * PDR packet rate for specific packet (frame) size, and
87   * Packet (L2 frame size) size in bits plus any associated L1 overhead.
88
89 # MLRsearch Background
90
91 Multiple Loss Rate search (MLRsearch) is a packet throughput search
92 algorithm suitable for deterministic (as opposed to probabilistic)
93 systems. MLRsearch discovers multiple packet throughput rates in a
94 single search, each rate associated with a distinct Packet Loss Ratio
95 (PLR) criteria.
96
97 Two popular names for particular PLR criteria are Non-Drop Rate (NDR,
98 with PLR=0, zero packet loss) and Partial Drop Rate (PDR, with PLR>0,
99 non-zero packet loss). MLRsearch discovers NDR and PDR in a single
100 search reducing required execution time compared to separate binary
101 searches for NDR and PDR. MLRsearch reduces execution time even further
102 by relying on shorter trial durations of intermediate steps, with only
103 the final measurements conducted at the specified final trial duration.
104 This results in the shorter overall search execution time when compared
105 to a standard NDR/PDR binary search, while guaranteeing the same or
106 similar results.
107 (TODO: Specify "standard" in the previous sentence.)
108
109 If needed, MLRsearch can be easily adopted to discover more throughput
110 rates with different pre-defined PLRs.
111
112 Unless otherwise noted, all throughput rates are *always* bi-directional
113 aggregates of two equal (symmetric) uni-directional packet rates
114 received and reported by an external traffic generator.
115
116 # MLRsearch Overview
117
118 The main properties of MLRsearch:
119
120 * MLRsearch is a duration aware multi-phase multi-rate search algorithm.
121   * Initial phase determines promising starting interval for the search.
122   * Intermediate phases progress towards defined final search criteria.
123   * Final phase executes measurements according to the final search
124     criteria.
125 * **Initial phase**:
126   * Uses link rate as a starting transmit rate and discovers the Maximum
127     Receive Rate (MRR) used as an input to the first intermediate phase.
128 * **Intermediate phases**:
129   * Start with initial trial duration (in the first phase) and converge
130     geometrically towards the final trial duration (in the final phase).
131   * Track two values for NDR and two for PDR.
132     * The values are called (NDR or PDR) lower_bound and upper_bound.
133     * Each value comes from a specific trial measurement
134       (most recent for that transmit rate),
135       and as such the value is associated with that measurement's duration and loss.
136     * A bound can be invalid, for example if NDR lower_bound
137       has been measured with nonzero loss.
138     * Invalid bounds are not real boundaries for the searched value,
139       but are needed to track interval widths.
140     * Valid bounds are real boundaries for the searched value.
141     * Each non-initial phase ends with all bounds valid.
142   * Start with a large (lower_bound, upper_bound) interval width and
143     geometrically converge towards the width goal (measurement resolution)
144     of the phase. Each phase halves the previous width goal.
145   * Use internal and external searches:
146     * External search - measures at transmit rates outside the (lower_bound,
147       upper_bound) interval. Activated when a bound is invalid,
148       to search for a new valid bound by doubling the interval width.
149       It is a variant of `exponential search`_.
150     * Internal search - `binary search`_, measures at transmit rates within the
151       (lower_bound, upper_bound) valid interval, halving the interval width.
152 * **Final phase** is executed with the final test trial duration, and the final
153   width goal that determines resolution of the overall search.
154   Intermediate phases together with the final phase are called non-initial phases.
155
156 The main benefits of MLRsearch vs. binary search include:
157
158 * In general MLRsearch is likely to execute more search trials overall, but
159   less trials at a set final duration.
160 * In well behaving cases it greatly reduces (>50%) the overall duration
161   compared to a single PDR (or NDR) binary search duration,
162   while finding multiple drop rates.
163 * In all cases MLRsearch yields the same or similar results to binary search.
164 * Note: both binary search and MLRsearch are susceptible to reporting
165   non-repeatable results across multiple runs for very bad behaving
166   cases.
167
168 Caveats:
169
170 * Worst case MLRsearch can take longer than a binary search e.g. in case of
171   drastic changes in behaviour for trials at varying durations.
172
173 # Sample Implementation
174
175 Following is a brief description of a sample MLRsearch implementation
176 based on the open-source code running in FD.io CSIT project as part of a
177 Continuous Integration / Continuous Development (CI/CD) framework.
178
179 ## Input Parameters
180
181 1. **maximum_transmit_rate** - maximum packet transmit rate to be used by
182    external traffic generator, limited by either the actual Ethernet
183    link rate or traffic generator NIC model capabilities. Sample
184    defaults: 2 * 14.88 Mpps for 64B 10GE link rate,
185    2 * 18.75 Mpps for 64B 40GE NIC maximum rate.
186 2. **minimum_transmit_rate** - minimum packet transmit rate to be used for
187    measurements. MLRsearch fails if lower transmit rate needs to be
188    used to meet search criteria. Default: 2 * 10 kpps (could be higher).
189 3. **final_trial_duration** - required trial duration for final rate
190    measurements. Default: 30 sec.
191 4. **initial_trial_duration** - trial duration for initial MLRsearch phase.
192    Default: 1 sec.
193 5. **final_relative_width** - required measurement resolution expressed as
194    (lower_bound, upper_bound) interval width relative to upper_bound.
195    Default: 0.5%.
196 6. **packet_loss_ratio** - maximum acceptable PLR search criteria for
197    PDR measurements. Default: 0.5%.
198 7. **number_of_intermediate_phases** - number of phases between the initial
199    phase and the final phase. Impacts the overall MLRsearch duration.
200    Less phases are required for well behaving cases, more phases
201    may be needed to reduce the overall search duration for worse behaving cases.
202    Default (2). (Value chosen based on limited experimentation to date.
203    More experimentation needed to arrive to clearer guidelines.)
204
205 ## Initial phase
206
207 1. First trial measures at maximum rate and discovers MRR.
208    a. *in*: trial_duration = initial_trial_duration.
209    b. *in*: offered_transmit_rate = maximum_transmit_rate.
210    c. *do*: single trial.
211    d. *out*: measured loss ratio.
212    e. *out*: mrr = measured receive rate.
213 2. Second trial measures at MRR and discovers MRR2.
214    a. *in*: trial_duration = initial_trial_duration.
215    b. *in*: offered_transmit_rate = MRR.
216    c. *do*: single trial.
217    d. *out*: measured loss ratio.
218    e. *out*: mrr2 = measured receive rate.
219 3. Third trial measures at MRR2.
220    a. *in*: trial_duration = initial_trial_duration.
221    b. *in*: offered_transmit_rate = MRR2.
222    c. *do*: single trial.
223    d. *out*: measured loss ratio.
224
225 ## Non-initial phases
226
227 1. Main loop:
228    a. *in*: trial_duration for the current phase.
229       Set to initial_trial_duration for the first intermediate phase;
230       to final_trial_duration for the final phase;
231       or to the element of interpolating geometric sequence
232       for other intermediate phases.
233       For example with two intermediate phases, trial_duration
234       of the second intermediate phase is the geometric average
235       of initial_strial_duration and final_trial_duration.
236    b. *in*: relative_width_goal for the current phase.
237       Set to final_relative_width for the final phase;
238       doubled for each preceding phase.
239       For example with two intermediate phases,
240       the first intermediate phase uses quadruple of final_relative_width
241       and the second intermediate phase uses double of final_relative_width.
242    c. *in*: ndr_interval, pdr_interval from the previous main loop iteration
243       or the previous phase.
244       If the previous phase is the initial phase, both intervals have
245       lower_bound = MRR2, uper_bound = MRR.
246       Note that the initial phase is likely to create intervals with invalid bounds.
247    d. *do*: According to the procedure described in point 2,
248       either exit the phase (by jumping to 1.g.),
249       or prepare new transmit rate to measure with.
250    e. *do*: Perform the trial measurement at the new transmit rate
251       and trial_duration, compute its loss ratio.
252    f. *do*: Update the bounds of both intervals, based on the new measurement.
253       The actual update rules are numerous, as NDR external search
254       can affect PDR interval and vice versa, but the result
255       agrees with rules of both internal and external search.
256       For example, any new measurement below an invalid lower_bound
257       becomes the new lower_bound, while the old measurement
258       (previously acting as the invalid lower_bound)
259       becomes a new and valid upper_bound.
260       Go to next iteration (1.c.), taking the updated intervals as new input.
261    g. *out*: current ndr_interval and pdr_interval.
262       In the final phase this is also considered
263       to be the result of the whole search.
264       For other phases, the next phase loop is started
265       with the current results as an input.
266 2. New transmit rate (or exit) calculation (for 1.d.):
267    * If there is an invalid bound then prepare for external search:
268      * *If* the most recent measurement at NDR lower_bound transmit rate
269        had the loss higher than zero, then
270        the new transmit rate is NDR lower_bound
271        decreased by two NDR interval widths.
272      * Else, *if* the most recent measurement at PDR lower_bound
273        transmit rate had the loss higher than PLR, then
274        the new transmit rate is PDR lower_bound
275        decreased by two PDR interval widths.
276      * Else, *if* the most recent measurement at NDR upper_bound
277        transmit rate had no loss, then
278        the new transmit rate is NDR upper_bound
279        increased by two NDR interval widths.
280      * Else, *if* the most recent measurement at PDR upper_bound
281        transmit rate had the loss lower or equal to PLR, then
282        the new transmit rate is PDR upper_bound
283        increased by two PDR interval widths.
284    * If interval width is higher than the current phase goal:
285      * Else, *if* NDR interval does not meet the current phase width goal,
286        prepare for internal search. The new transmit rate is
287        (NDR lower bound + NDR upper bound) / 2.
288      * Else, *if* PDR interval does not meet the current phase width goal,
289        prepare for internal search. The new transmit rate is
290        (PDR lower bound + PDR upper bound) / 2.
291    * Else, *if* some bound has still only been measured at a lower duration,
292      prepare to re-measure at the current duration (and the same transmit rate).
293      The order of priorities is:
294      * NDR lower_bound,
295      * PDR lower_bound,
296      * NDR upper_bound,
297      * PDR upper_bound.
298    * *Else*, do not prepare any new rate, to exit the phase.
299      This ensures that at the end of each non-initial phase
300      all intervals are valid, narrow enough, and measured
301      at current phase trial duration.
302
303 # Known Implementations
304
305 The only known working implementatin of MLRsearch is in Linux Foundation
306 FD.io CSIT project. https://wiki.fd.io/view/CSIT. https://git.fd.io/csit/.
307
308 ## FD.io CSIT Implementation Deviations
309
310 This document so far has been describing a simplified version of MLRsearch algorithm.
311 The full algorithm as implemented contains additional logic,
312 which makes some of the details (but not general ideas) above incorrect.
313 Here is a short description of the additional logic as a list of principles,
314 explaining their main differences from (or additions to) the simplified description,
315 but without detailing their mutual interaction.
316
317 1. *Logarithmic transmit rate.*
318    In order to better fit the relative width goal,
319    the interval doubling and halving is done differently.
320    For example, the middle of 2 and 8 is 4, not 5.
321 2. *Optimistic maximum rate.*
322    The increased rate is never higher than the maximum rate.
323    Upper bound at that rate is always considered valid.
324 3. *Pessimistic minimum rate.*
325    The decreased rate is never lower than the minimum rate.
326    If a lower bound at that rate is invalid,
327    a phase stops refining the interval further (until it gets re-measured).
328 4. *Conservative interval updates.*
329    Measurements above current upper bound never update a valid upper bound,
330    even if drop ratio is low.
331    Measurements below current lower bound always update any lower bound
332    if drop ratio is high.
333 5. *Ensure sufficient interval width.*
334    Narrow intervals make external search take more time to find a valid bound.
335    If the new transmit increased or decreased rate would result in width
336    less than the current goal, increase/decrease more.
337    This can happen if the measurement for the other interval
338    makes the current interval too narrow.
339    Similarly, take care the measurements in the initial phase
340    create wide enough interval.
341 6. *Timeout for bad cases.*
342    The worst case for MLRsearch is when each phase converges to intervals
343    way different than the results of the previous phase.
344    Rather than suffer total search time several times larger
345    than pure binary search, the implemented tests fail themselves
346    when the search takes too long (given by argument *timeout*).
347
348 # IANA Considerations
349
350 ..
351
352 # Security Considerations
353
354 ..
355
356 # Acknowledgements
357
358 ..
359
360 --- back

©2016 FD.io a Linux Foundation Collaborative Project. All Rights Reserved.
Linux Foundation is a registered trademark of The Linux Foundation. Linux is a registered trademark of Linus Torvalds.
Please see our privacy policy and terms of use.