1 # Copyright (c) 2020 Cisco and/or its affiliates.
2 # Licensed under the Apache License, Version 2.0 (the "License");
3 # you may not use this file except in compliance with the License.
4 # You may obtain a copy of the License at:
6 # http://www.apache.org/licenses/LICENSE-2.0
8 # Unless required by applicable law or agreed to in writing, software
9 # distributed under the License is distributed on an "AS IS" BASIS,
10 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 # See the License for the specific language governing permissions and
12 # limitations under the License.
14 """Module defining MultipleLossRatioSearch class."""
20 from .AbstractSearchAlgorithm import AbstractSearchAlgorithm
21 from .NdrPdrResult import NdrPdrResult
22 from .ReceiveRateInterval import ReceiveRateInterval
25 class MultipleLossRatioSearch(AbstractSearchAlgorithm):
26 """Optimized binary search algorithm for finding NDR and PDR bounds.
28 Traditional binary search algorithm needs initial interval
29 (lower and upper bound), and returns final interval after bisecting
30 (until some exit condition is met).
31 The exit condition is usually related to the interval width,
32 (upper bound value minus lower bound value).
34 The optimized algorithm contains several improvements
35 aimed to reduce overall search time.
37 One improvement is searching for two intervals at once.
38 The intervals are for NDR (No Drop Rate) and PDR (Partial Drop Rate).
40 Next improvement is that the initial interval does not need to be valid.
41 Imagine initial interval (10, 11) where 11 is smaller
42 than the searched value.
43 The algorithm will try (11, 13) interval next, and if 13 is still smaller,
44 (13, 17) and so on, doubling width until the upper bound is valid.
45 The part when interval expands is called external search,
46 the part when interval is bisected is called internal search.
48 Next improvement is that trial measurements at small trial duration
49 can be used to find a reasonable interval for full trial duration search.
50 This results in more trials performed, but smaller overall duration
53 Next improvement is bisecting in logarithmic quantities,
54 so that exit criteria can be independent of measurement units.
56 Next improvement is basing the initial interval on receive rates.
58 Final improvement is exiting early if the minimal value
59 is not a valid lower bound.
61 The complete search consist of several phases,
62 each phase performing several trial measurements.
63 Initial phase creates initial interval based on receive rates
64 at maximum rate and at maximum receive rate (MRR).
65 Final phase and preceding intermediate phases are performing
66 external and internal search steps,
67 each resulting interval is the starting point for the next phase.
68 The resulting interval of final phase is the result of the whole algorithm.
70 Each non-initial phase uses its own trial duration and width goal.
71 Any non-initial phase stops searching (for NDR or PDR independently)
72 when minimum is not a valid lower bound (at current duration),
73 or all of the following is true:
74 Both bounds are valid, bound bounds are measured at the current phase
75 trial duration, interval width is less than the width goal
78 TODO: Review and update this docstring according to rst docs.
79 TODO: Support configurable number of Packet Loss Ratios.
83 """Structure containing data to be passed around in recursion."""
86 self, result, phases, duration, width_goal, packet_loss_ratio,
87 minimum_transmit_rate, maximum_transmit_rate):
88 """Convert and store the argument values.
90 :param result: Current measured NDR and PDR intervals.
91 :param phases: How many intermediate phases to perform
92 before the current one.
93 :param duration: Trial duration to use in the current phase [s].
94 :param width_goal: The goal relative width for the curreent phase.
95 :param packet_loss_ratio: PDR fraction for the current search.
96 :param minimum_transmit_rate: Minimum target transmit rate
97 for the current search [pps].
98 :param maximum_transmit_rate: Maximum target transmit rate
99 for the current search [pps].
100 :type result: NdrPdrResult.NdrPdrResult
102 :type duration: float
103 :type width_goal: float
104 :type packet_loss_ratio: float
105 :type minimum_transmit_rate: float
106 :type maximum_transmit_rate: float
109 self.phases = int(phases)
110 self.duration = float(duration)
111 self.width_goal = float(width_goal)
112 self.packet_loss_ratio = float(packet_loss_ratio)
113 self.minimum_transmit_rate = float(minimum_transmit_rate)
114 self.maximum_transmit_rate = float(maximum_transmit_rate)
117 self, measurer, final_relative_width=0.005,
118 final_trial_duration=30.0, initial_trial_duration=1.0,
119 number_of_intermediate_phases=2, timeout=600.0, doublings=1):
120 """Store the measurer object and additional arguments.
122 :param measurer: Rate provider to use by this search object.
123 :param final_relative_width: Final lower bound transmit rate
124 cannot be more distant that this multiple of upper bound [1].
125 :param final_trial_duration: Trial duration for the final phase [s].
126 :param initial_trial_duration: Trial duration for the initial phase
127 and also for the first intermediate phase [s].
128 :param number_of_intermediate_phases: Number of intermediate phases
129 to perform before the final phase [1].
130 :param timeout: The search will fail itself when not finished
131 before this overall time [s].
132 :param doublings: How many doublings to do in external search step.
133 Default 1 is suitable for fairly stable tests,
134 less stable tests might get better overal duration with 2 or more.
135 :type measurer: AbstractMeasurer.AbstractMeasurer
136 :type final_relative_width: float
137 :type final_trial_duration: float
138 :type initial_trial_duration: float
139 :type number_of_intermediate_phases: int
143 super(MultipleLossRatioSearch, self).__init__(measurer)
144 self.final_trial_duration = float(final_trial_duration)
145 self.final_relative_width = float(final_relative_width)
146 self.number_of_intermediate_phases = int(number_of_intermediate_phases)
147 self.initial_trial_duration = float(initial_trial_duration)
148 self.timeout = float(timeout)
149 self.doublings = int(doublings)
152 def double_relative_width(relative_width):
153 """Return relative width corresponding to double logarithmic width.
155 :param relative_width: The base relative width to double.
156 :type relative_width: float
157 :returns: The relative width of double logarithmic size.
160 return 1.999 * relative_width - relative_width * relative_width
161 # The number should be 2.0, but we want to avoid rounding errors,
162 # and ensure half of double is not larger than the original value.
165 def double_step_down(relative_width, current_bound):
166 """Return rate of double logarithmic width below.
168 :param relative_width: The base relative width to double.
169 :param current_bound: The current target transmit rate to move [pps].
170 :type relative_width: float
171 :type current_bound: float
172 :returns: Transmit rate smaller by logarithmically double width [pps].
175 return current_bound * (
176 1.0 - MultipleLossRatioSearch.double_relative_width(relative_width)
180 def expand_down(relative_width, doublings, current_bound):
181 """Return rate of expanded logarithmic width below.
183 :param relative_width: The base relative width to double.
184 :param doublings: How many doublings to do for expansion.
185 :param current_bound: The current target transmit rate to move [pps].
186 :type relative_width: float
188 :type current_bound: float
189 :returns: Transmit rate smaller by logarithmically double width [pps].
192 for _ in range(doublings):
193 relative_width = MultipleLossRatioSearch.double_relative_width(
196 return current_bound * (1.0 - relative_width)
199 def double_step_up(relative_width, current_bound):
200 """Return rate of double logarithmic width above.
202 :param relative_width: The base relative width to double.
203 :param current_bound: The current target transmit rate to move [pps].
204 :type relative_width: float
205 :type current_bound: float
206 :returns: Transmit rate larger by logarithmically double width [pps].
209 return current_bound / (
210 1.0 - MultipleLossRatioSearch.double_relative_width(relative_width)
214 def expand_up(relative_width, doublings, current_bound):
215 """Return rate of expanded logarithmic width above.
217 :param relative_width: The base relative width to double.
218 :param doublings: How many doublings to do for expansion.
219 :param current_bound: The current target transmit rate to move [pps].
220 :type relative_width: float
222 :type current_bound: float
223 :returns: Transmit rate smaller by logarithmically double width [pps].
226 for _ in range(doublings):
227 relative_width = MultipleLossRatioSearch.double_relative_width(
230 return current_bound / (1.0 - relative_width)
233 def half_relative_width(relative_width):
234 """Return relative width corresponding to half logarithmic width.
236 :param relative_width: The base relative width to halve.
237 :type relative_width: float
238 :returns: The relative width of half logarithmic size.
241 return 1.0 - math.sqrt(1.0 - relative_width)
244 def half_step_up(relative_width, current_bound):
245 """Return rate of half logarithmic width above.
247 :param relative_width: The base relative width to halve.
248 :param current_bound: The current target transmit rate to move [pps].
249 :type relative_width: float
250 :type current_bound: float
251 :returns: Transmit rate larger by logarithmically half width [pps].
254 return current_bound / (
255 1.0 - MultipleLossRatioSearch.half_relative_width(relative_width)
258 def narrow_down_ndr_and_pdr(
259 self, minimum_transmit_rate, maximum_transmit_rate,
261 """Perform initial phase, create state object, proceed with next phases.
263 :param minimum_transmit_rate: Minimal target transmit rate [pps].
264 :param maximum_transmit_rate: Maximal target transmit rate [pps].
265 :param packet_loss_ratio: Fraction of packets lost, for PDR [1].
266 :type minimum_transmit_rate: float
267 :type maximum_transmit_rate: float
268 :type packet_loss_ratio: float
269 :returns: Structure containing narrowed down intervals
270 and their measurements.
271 :rtype: NdrPdrResult.NdrPdrResult
272 :raises RuntimeError: If total duration is larger than timeout.
274 minimum_transmit_rate = float(minimum_transmit_rate)
275 maximum_transmit_rate = float(maximum_transmit_rate)
276 packet_loss_ratio = float(packet_loss_ratio)
277 line_measurement = self.measurer.measure(
278 self.initial_trial_duration, maximum_transmit_rate)
279 initial_width_goal = self.final_relative_width
280 for _ in range(self.number_of_intermediate_phases):
281 initial_width_goal = self.double_relative_width(initial_width_goal)
282 max_lo = maximum_transmit_rate * (1.0 - initial_width_goal)
284 minimum_transmit_rate, min(max_lo, line_measurement.receive_rate)
286 mrr_measurement = self.measurer.measure(
287 self.initial_trial_duration, mrr
289 # Attempt to get narrower width.
290 if mrr_measurement.loss_fraction > 0.0:
291 max2_lo = mrr * (1.0 - initial_width_goal)
292 mrr2 = min(max2_lo, mrr_measurement.receive_rate)
294 mrr2 = mrr / (1.0 - initial_width_goal)
295 if minimum_transmit_rate < mrr2 < maximum_transmit_rate:
296 line_measurement = mrr_measurement
297 mrr_measurement = self.measurer.measure(
298 self.initial_trial_duration, mrr2)
300 line_measurement, mrr_measurement = \
301 (mrr_measurement, line_measurement)
302 starting_interval = ReceiveRateInterval(
303 mrr_measurement, line_measurement)
304 starting_result = NdrPdrResult(starting_interval, starting_interval)
305 state = self.ProgressState(
306 starting_result, self.number_of_intermediate_phases,
307 self.final_trial_duration, self.final_relative_width,
308 packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate
310 state = self.ndrpdr(state)
313 def _measure_and_update_state(self, state, transmit_rate):
314 """Perform trial measurement, update bounds, return new state.
316 :param state: State before this measurement.
317 :param transmit_rate: Target transmit rate for this measurement [pps].
318 :type state: ProgressState
319 :type transmit_rate: float
320 :returns: State after the measurement.
321 :rtype: ProgressState
323 # TODO: Implement https://stackoverflow.com/a/24683360
324 # to avoid the string manipulation if log verbosity is too low.
325 logging.info(f"result before update: {state.result}")
327 f"relative widths in goals: "
328 f"{state.result.width_in_goals(self.final_relative_width)}"
330 measurement = self.measurer.measure(state.duration, transmit_rate)
331 ndr_interval = self._new_interval(
332 state.result.ndr_interval, measurement, 0.0
334 pdr_interval = self._new_interval(
335 state.result.pdr_interval, measurement, state.packet_loss_ratio
337 state.result = NdrPdrResult(ndr_interval, pdr_interval)
341 def _new_interval(old_interval, measurement, packet_loss_ratio):
342 """Return new interval with bounds updated according to the measurement.
344 :param old_interval: The current interval before the measurement.
345 :param measurement: The new meaqsurement to take into account.
346 :param packet_loss_ratio: Fraction for PDR (or zero for NDR).
347 :type old_interval: ReceiveRateInterval.ReceiveRateInterval
348 :type measurement: ReceiveRateMeasurement.ReceiveRateMeasurement
349 :type packet_loss_ratio: float
350 :returns: The updated interval.
351 :rtype: ReceiveRateInterval.ReceiveRateInterval
353 old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
354 new_lo = new_hi = None
355 # Priority zero: direct replace if the target Tr is the same.
356 if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
357 if measurement.target_tr == old_lo.target_tr:
361 # Priority one: invalid lower bound allows only one type of update.
362 elif old_lo.loss_fraction > packet_loss_ratio:
363 # We can only expand down, old bound becomes valid upper one.
364 if measurement.target_tr < old_lo.target_tr:
365 new_lo, new_hi = measurement, old_lo
369 # Lower bound is now valid.
370 # Next priorities depend on target Tr.
371 elif measurement.target_tr < old_lo.target_tr:
372 # Lower external measurement, relevant only
373 # if the new measurement has high loss rate.
374 if measurement.loss_fraction > packet_loss_ratio:
375 # Returning the broader interval as old_lo
376 # would be invalid upper bound.
378 elif measurement.target_tr > old_hi.target_tr:
379 # Upper external measurement, only relevant for invalid upper bound.
380 if old_hi.loss_fraction <= packet_loss_ratio:
381 # Old upper bound becomes valid new lower bound.
382 new_lo, new_hi = old_hi, measurement
384 # Internal measurement, replaced boundary
385 # depends on measured loss fraction.
386 if measurement.loss_fraction > packet_loss_ratio:
387 # We have found a narrow valid interval,
388 # regardless of whether old upper bound was valid.
391 # In ideal world, we would not want to shrink interval
392 # if upper bound is not valid.
393 # In the real world, we want to shrink it for
394 # "invalid upper bound at maximal rate" case.
397 return ReceiveRateInterval(
398 old_lo if new_lo is None else new_lo,
399 old_hi if new_hi is None else new_hi
402 def ndrpdr(self, state):
403 """Perform trials for this phase. Return the new state when done.
405 :param state: State before this phase.
406 :type state: ProgressState
407 :returns: The updated state.
408 :rtype: ProgressState
409 :raises RuntimeError: If total duration is larger than timeout.
411 start_time = time.time()
413 # We need to finish preceding intermediate phases first.
414 saved_phases = state.phases
416 # Preceding phases have shorter duration.
417 saved_duration = state.duration
418 duration_multiplier = state.duration / self.initial_trial_duration
419 phase_exponent = float(state.phases) / saved_phases
420 state.duration = self.initial_trial_duration * math.pow(
421 duration_multiplier, phase_exponent
423 # Shorter durations do not need that narrow widths.
424 saved_width = state.width_goal
425 state.width_goal = self.double_relative_width(state.width_goal)
427 state = self.ndrpdr(state)
428 # Restore the state for current phase.
429 state.duration = saved_duration
430 state.width_goal = saved_width
431 state.phases = saved_phases # Not needed, but just in case.
434 f"starting iterations with duration {state.duration} and relative "
435 f"width goal {state.width_goal}"
438 if time.time() > start_time + self.timeout:
439 raise RuntimeError(u"Optimized search takes too long.")
440 # Order of priorities: invalid bounds (nl, pl, nh, ph),
441 # then narrowing relative Tr widths.
442 # Durations are not priorities yet,
443 # they will settle on their own hopefully.
444 ndr_lo = state.result.ndr_interval.measured_low
445 ndr_hi = state.result.ndr_interval.measured_high
446 pdr_lo = state.result.pdr_interval.measured_low
447 pdr_hi = state.result.pdr_interval.measured_high
449 state.width_goal, state.result.ndr_interval.rel_tr_width
452 state.width_goal, state.result.pdr_interval.rel_tr_width
454 # If we are hitting maximal or minimal rate, we cannot shift,
455 # but we can re-measure.
456 new_tr = self._ndrpdr_loss_fraction(
457 state, ndr_lo, ndr_hi, pdr_lo, pdr_hi, ndr_rel_width,
461 if new_tr is not None:
462 state = self._measure_and_update_state(state, new_tr)
465 # If we are hitting maximum_transmit_rate,
466 # it is still worth narrowing width,
467 # hoping large enough loss fraction will happen.
468 # But if we are hitting the minimal rate (at current duration),
469 # no additional measurement will help with that,
470 # so we can stop narrowing in this phase.
471 if (ndr_lo.target_tr <= state.minimum_transmit_rate
472 and ndr_lo.loss_fraction > 0.0):
474 if (pdr_lo.target_tr <= state.minimum_transmit_rate
475 and pdr_lo.loss_fraction > state.packet_loss_ratio):
478 new_tr = self._ndrpdr_width_goal(
479 state, ndr_lo, pdr_lo, ndr_rel_width, pdr_rel_width
482 if new_tr is not None:
483 state = self._measure_and_update_state(state, new_tr)
486 # We do not need to improve width, but there still might be
487 # some measurements with smaller duration.
488 new_tr = self._ndrpdr_duration(
489 state, ndr_lo, ndr_hi, pdr_lo, pdr_hi, ndr_rel_width,
493 if new_tr is not None:
494 state = self._measure_and_update_state(state, new_tr)
497 # Widths are narrow (or lower bound minimal), bound measurements
498 # are long enough, we can return.
499 logging.info(u"phase done")
503 def _ndrpdr_loss_fraction(
504 self, state, ndr_lo, ndr_hi, pdr_lo, pdr_hi, ndr_rel_width,
506 """Perform loss_fraction-based trials within a ndrpdr phase
508 :param state: current state
509 :param ndr_lo: ndr interval measured low
510 :param ndr_hi: ndr interval measured high
511 :param pdr_lo: pdr interval measured low
512 :param pdr_hi: pdr interval measured high
513 :param ndr_rel_width: ndr interval relative width
514 :param pdr_rel_width: pdr interval relative width
515 :type state: ProgressState
516 :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
517 :type ndr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
518 :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
519 :type pdr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
520 :type ndr_rel_width: float
521 :type pdr_rel_width: float
522 :returns: a new transmit rate if one should be applied
526 if ndr_lo.loss_fraction > 0.0:
527 if ndr_lo.target_tr > state.minimum_transmit_rate:
529 state.minimum_transmit_rate, self.expand_down(
530 ndr_rel_width, self.doublings, ndr_lo.target_tr
533 logging.info(f"ndr lo external {result}")
534 elif ndr_lo.duration < state.duration:
535 result = state.minimum_transmit_rate
536 logging.info(u"ndr lo minimal re-measure")
538 if result is None and pdr_lo.loss_fraction > state.packet_loss_ratio:
539 if pdr_lo.target_tr > state.minimum_transmit_rate:
541 state.minimum_transmit_rate, self.expand_down(
542 pdr_rel_width, self.doublings, pdr_lo.target_tr
545 logging.info(f"pdr lo external {result}")
546 elif pdr_lo.duration < state.duration:
547 result = state.minimum_transmit_rate
548 logging.info(u"pdr lo minimal re-measure")
550 if result is None and ndr_hi.loss_fraction <= 0.0:
551 if ndr_hi.target_tr < state.maximum_transmit_rate:
553 state.maximum_transmit_rate, self.expand_up(
554 ndr_rel_width, self.doublings, ndr_hi.target_tr
557 logging.info(f"ndr hi external {result}")
558 elif ndr_hi.duration < state.duration:
559 result = state.maximum_transmit_rate
560 logging.info(u"ndr hi maximal re-measure")
562 if result is None and pdr_hi.loss_fraction <= state.packet_loss_ratio:
563 if pdr_hi.target_tr < state.maximum_transmit_rate:
565 state.maximum_transmit_rate, self.expand_up(
566 pdr_rel_width, self.doublings, pdr_hi.target_tr
569 logging.info(f"pdr hi external {result}")
570 elif pdr_hi.duration < state.duration:
571 result = state.maximum_transmit_rate
572 logging.info(u"ndr hi maximal re-measure")
575 def _ndrpdr_width_goal(
576 self, state, ndr_lo, pdr_lo, ndr_rel_width, pdr_rel_width):
577 """Perform width_goal-based trials within a ndrpdr phase
579 :param state: current state
580 :param ndr_lo: ndr interval measured low
581 :param pdr_lo: pdr interval measured low
582 :param ndr_rel_width: ndr interval relative width
583 :param pdr_rel_width: pdr interval relative width
584 :type state: ProgressState
585 :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
586 :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
587 :type ndr_rel_width: float
588 :type pdr_rel_width: float
589 :returns: a new transmit rate if one should be applied
591 Return a new transmit rate if one should be applied.
593 if ndr_rel_width > state.width_goal:
594 # We have to narrow NDR width first, as NDR internal search
595 # can invalidate PDR (but not vice versa).
596 result = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
597 logging.info(f"Bisecting for NDR at {result}")
598 elif pdr_rel_width > state.width_goal:
599 # PDR internal search.
600 result = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
601 logging.info(f"Bisecting for PDR at {result}")
607 def _ndrpdr_duration(
608 state, ndr_lo, ndr_hi, pdr_lo, pdr_hi, ndr_rel_width,
610 """Perform duration-based trials within a ndrpdr phase
612 :param state: current state
613 :param ndr_lo: ndr interval measured low
614 :param ndr_hi: ndr interval measured high
615 :param pdr_lo: pdr interval measured low
616 :param pdr_hi: pdr interval measured high
617 :param ndr_rel_width: ndr interval relative width
618 :param pdr_rel_width: pdr interval relative width
619 :type state: ProgressState
620 :type ndr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
621 :type ndr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
622 :type pdr_lo: ReceiveRateMeasurement.ReceiveRateMeasurement
623 :type pdr_hi: ReceiveRateMeasurement.ReceiveRateMeasurement
624 :type ndr_rel_width: float
625 :type pdr_rel_width: float
626 :returns: a new transmit rate if one should be applied
629 # We need to re-measure with full duration, possibly
630 # creating invalid bounds to resolve (thus broadening width).
631 if ndr_lo.duration < state.duration:
632 result = ndr_lo.target_tr
633 logging.info(u"re-measuring NDR lower bound")
634 elif pdr_lo.duration < state.duration:
635 result = pdr_lo.target_tr
636 logging.info(u"re-measuring PDR lower bound")
637 # Except when lower bounds have high loss fraction, in that case
638 # we do not need to re-measure _upper_ bounds.
639 elif ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
640 result = ndr_hi.target_tr
641 logging.info(u"re-measuring NDR upper bound")
642 elif pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
643 result = pdr_hi.target_tr
644 logging.info(u"re-measuring PDR upper bound")