1 # Copyright (c) 2018 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.
82 class ProgressState(object):
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)
116 def __init__(self, measurer, final_relative_width=0.005,
117 final_trial_duration=30.0, initial_trial_duration=1.0,
118 number_of_intermediate_phases=2, timeout=600.0, doublings=1):
119 """Store the measurer object and additional arguments.
121 :param measurer: Rate provider to use by this search object.
122 :param final_relative_width: Final lower bound transmit rate
123 cannot be more distant that this multiple of upper bound [1].
124 :param final_trial_duration: Trial duration for the final phase [s].
125 :param initial_trial_duration: Trial duration for the initial phase
126 and also for the first intermediate phase [s].
127 :param number_of_intermediate_phases: Number of intermediate phases
128 to perform before the final phase [1].
129 :param timeout: The search will fail itself when not finished
130 before this overall time [s].
131 :param doublings: How many doublings to do in external search step.
132 Default 1 is suitable for fairly stable tests,
133 less stable tests might get better overal duration with 2 or more.
134 :type measurer: AbstractMeasurer.AbstractMeasurer
135 :type final_relative_width: float
136 :type final_trial_duration: float
137 :type initial_trial_duration: int
138 :type number_of_intermediate_phases: int
142 super(MultipleLossRatioSearch, self).__init__(measurer)
143 self.final_trial_duration = float(final_trial_duration)
144 self.final_relative_width = float(final_relative_width)
145 self.number_of_intermediate_phases = int(number_of_intermediate_phases)
146 self.initial_trial_duration = float(initial_trial_duration)
147 self.timeout = float(timeout)
148 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(
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(
195 return current_bound * (1.0 - relative_width)
198 def double_step_up(relative_width, current_bound):
199 """Return rate of double logarithmic width above.
201 :param relative_width: The base relative width to double.
202 :param current_bound: The current target transmit rate to move [pps].
203 :type relative_width: float
204 :type current_bound: float
205 :returns: Transmit rate larger by logarithmically double width [pps].
208 return current_bound / (
209 1.0 - MultipleLossRatioSearch.double_relative_width(
213 def expand_up(relative_width, doublings, current_bound):
214 """Return rate of expanded logarithmic width above.
216 :param relative_width: The base relative width to double.
217 :param doublings: How many doublings to do for expansion.
218 :param current_bound: The current target transmit rate to move [pps].
219 :type relative_width: float
221 :type current_bound: float
222 :returns: Transmit rate smaller by logarithmically double width [pps].
225 for _ in range(doublings):
226 relative_width = MultipleLossRatioSearch.double_relative_width(
228 return current_bound / (1.0 - relative_width)
231 def half_relative_width(relative_width):
232 """Return relative width corresponding to half logarithmic width.
234 :param relative_width: The base relative width to halve.
235 :type relative_width: float
236 :returns: The relative width of half logarithmic size.
239 return 1.0 - math.sqrt(1.0 - relative_width)
242 def half_step_up(relative_width, current_bound):
243 """Return rate of half logarithmic width above.
245 :param relative_width: The base relative width to halve.
246 :param current_bound: The current target transmit rate to move [pps].
247 :type relative_width: float
248 :type current_bound: float
249 :returns: Transmit rate larger by logarithmically half width [pps].
252 return current_bound / (
253 1.0 - MultipleLossRatioSearch.half_relative_width(relative_width))
255 def narrow_down_ndr_and_pdr(
256 self, minimum_transmit_rate, maximum_transmit_rate,
258 """Perform initial phase, create state object, proceed with next phases.
260 :param minimum_transmit_rate: Minimal target transmit rate [pps].
261 :param maximum_transmit_rate: Maximal target transmit rate [pps].
262 :param packet_loss_ratio: Fraction of packets lost, for PDR [1].
263 :type minimum_transmit_rate: float
264 :type maximum_transmit_rate: float
265 :type packet_loss_ratio: float
266 :returns: Structure containing narrowed down intervals
267 and their measurements.
268 :rtype: NdrPdrResult.NdrPdrResult
269 :raises RuntimeError: If total duration is larger than timeout.
271 minimum_transmit_rate = float(minimum_transmit_rate)
272 maximum_transmit_rate = float(maximum_transmit_rate)
273 packet_loss_ratio = float(packet_loss_ratio)
274 line_measurement = self.measurer.measure(
275 self.initial_trial_duration, maximum_transmit_rate)
276 initial_width_goal = self.final_relative_width
277 for _ in range(self.number_of_intermediate_phases):
278 initial_width_goal = self.double_relative_width(initial_width_goal)
279 max_lo = maximum_transmit_rate * (1.0 - initial_width_goal)
281 minimum_transmit_rate,
282 min(max_lo, line_measurement.receive_rate))
283 mrr_measurement = self.measurer.measure(
284 self.initial_trial_duration, mrr)
285 # Attempt to get narrower width.
286 if mrr_measurement.loss_fraction > 0.0:
287 max2_lo = mrr * (1.0 - initial_width_goal)
288 mrr2 = min(max2_lo, mrr_measurement.receive_rate)
290 mrr2 = mrr / (1.0 - initial_width_goal)
291 if mrr2 > minimum_transmit_rate and mrr2 < maximum_transmit_rate:
292 line_measurement = mrr_measurement
293 mrr_measurement = self.measurer.measure(
294 self.initial_trial_duration, mrr2)
296 buf = line_measurement
297 line_measurement = mrr_measurement
298 mrr_measurement = buf
299 starting_interval = ReceiveRateInterval(
300 mrr_measurement, line_measurement)
301 starting_result = NdrPdrResult(starting_interval, starting_interval)
302 state = self.ProgressState(
303 starting_result, self.number_of_intermediate_phases,
304 self.final_trial_duration, self.final_relative_width,
305 packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate)
306 state = self.ndrpdr(state)
309 def _measure_and_update_state(self, state, transmit_rate):
310 """Perform trial measurement, update bounds, return new state.
312 :param state: State before this measurement.
313 :param transmit_rate: Target transmit rate for this measurement [pps].
314 :type state: ProgressState
315 :type transmit_rate: float
316 :returns: State after the measurement.
317 :rtype: ProgressState
319 # TODO: Implement https://stackoverflow.com/a/24683360
320 # to avoid the string manipulation if log verbosity is too low.
321 logging.info("result before update: %s", state.result)
323 "relative widths in goals: %s", state.result.width_in_goals(
324 self.final_relative_width))
325 measurement = self.measurer.measure(state.duration, transmit_rate)
326 ndr_interval = self._new_interval(
327 state.result.ndr_interval, measurement, 0.0)
328 pdr_interval = self._new_interval(
329 state.result.pdr_interval, measurement, state.packet_loss_ratio)
330 state.result = NdrPdrResult(ndr_interval, pdr_interval)
334 def _new_interval(old_interval, measurement, packet_loss_ratio):
335 """Return new interval with bounds updated according to the measurement.
337 :param old_interval: The current interval before the measurement.
338 :param measurement: The new meaqsurement to take into account.
339 :param packet_loss_ratio: Fraction for PDR (or zero for NDR).
340 :type old_interval: ReceiveRateInterval.ReceiveRateInterval
341 :type measurement: ReceiveRateMeasurement.ReceiveRateMeasurement
342 :type packet_loss_ratio: float
343 :returns: The updated interval.
344 :rtype: ReceiveRateInterval.ReceiveRateInterval
346 old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
347 # Priority zero: direct replace if the target Tr is the same.
348 if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
349 if measurement.target_tr == old_lo.target_tr:
350 return ReceiveRateInterval(measurement, old_hi)
352 return ReceiveRateInterval(old_lo, measurement)
353 # Priority one: invalid lower bound allows only one type of update.
354 if old_lo.loss_fraction > packet_loss_ratio:
355 # We can only expand down, old bound becomes valid upper one.
356 if measurement.target_tr < old_lo.target_tr:
357 return ReceiveRateInterval(measurement, old_lo)
360 # Lower bound is now valid.
361 # Next priorities depend on target Tr.
362 if measurement.target_tr < old_lo.target_tr:
363 # Lower external measurement, relevant only
364 # if the new measurement has high loss rate.
365 if measurement.loss_fraction > packet_loss_ratio:
366 # Returning the broader interval as old_lo
367 # would be invalid upper bound.
368 return ReceiveRateInterval(measurement, old_hi)
369 elif measurement.target_tr > old_hi.target_tr:
370 # Upper external measurement, only relevant for invalid upper bound.
371 if old_hi.loss_fraction <= packet_loss_ratio:
372 # Old upper bound becomes valid new lower bound.
373 return ReceiveRateInterval(old_hi, measurement)
375 # Internal measurement, replaced boundary
376 # depends on measured loss fraction.
377 if measurement.loss_fraction > packet_loss_ratio:
378 # We have found a narrow valid interval,
379 # regardless of whether old upper bound was valid.
380 return ReceiveRateInterval(old_lo, measurement)
382 # In ideal world, we would not want to shrink interval
383 # if upper bound is not valid.
384 # In the real world, we want to shrink it for
385 # "invalid upper bound at maximal rate" case.
386 return ReceiveRateInterval(measurement, old_hi)
387 # Fallback, the interval is unchanged by the measurement.
390 def ndrpdr(self, state):
391 """Pefrom trials for this phase. Return the new state when done.
393 :param state: State before this phase.
394 :type state: ProgressState
395 :returns: The updated state.
396 :rtype: ProgressState
397 :raises RuntimeError: If total duration is larger than timeout.
399 start_time = time.time()
401 # We need to finish preceding intermediate phases first.
402 saved_phases = state.phases
404 # Preceding phases have shorter duration.
405 saved_duration = state.duration
406 duration_multiplier = state.duration / self.initial_trial_duration
407 phase_exponent = float(state.phases) / saved_phases
408 state.duration = self.initial_trial_duration * math.pow(
409 duration_multiplier, phase_exponent)
410 # Shorter durations do not need that narrow widths.
411 saved_width = state.width_goal
412 state.width_goal = self.double_relative_width(state.width_goal)
414 state = self.ndrpdr(state)
415 # Restore the state for current phase.
416 state.duration = saved_duration
417 state.width_goal = saved_width
418 state.phases = saved_phases # Not needed, but just in case.
420 "starting iterations with duration %s and relative width goal %s",
421 state.duration, state.width_goal)
423 if time.time() > start_time + self.timeout:
424 raise RuntimeError("Optimized search takes too long.")
425 # Order of priorities: invalid bounds (nl, pl, nh, ph),
426 # then narrowing relative Tr widths.
427 # Durations are not priorities yet,
428 # they will settle on their own hopefully.
429 ndr_lo = state.result.ndr_interval.measured_low
430 ndr_hi = state.result.ndr_interval.measured_high
431 pdr_lo = state.result.pdr_interval.measured_low
432 pdr_hi = state.result.pdr_interval.measured_high
434 state.width_goal, state.result.ndr_interval.rel_tr_width)
436 state.width_goal, state.result.pdr_interval.rel_tr_width)
437 # If we are hitting maximal or minimal rate, we cannot shift,
438 # but we can re-measure.
439 if ndr_lo.loss_fraction > 0.0:
440 if ndr_lo.target_tr > state.minimum_transmit_rate:
442 state.minimum_transmit_rate,
444 ndr_rel_width, self.doublings, ndr_lo.target_tr))
445 logging.info("ndr lo external %s", new_tr)
446 state = self._measure_and_update_state(state, new_tr)
448 elif ndr_lo.duration < state.duration:
449 logging.info("ndr lo minimal re-measure")
450 state = self._measure_and_update_state(
451 state, state.minimum_transmit_rate)
453 if pdr_lo.loss_fraction > state.packet_loss_ratio:
454 if pdr_lo.target_tr > state.minimum_transmit_rate:
456 state.minimum_transmit_rate,
458 pdr_rel_width, self.doublings, pdr_lo.target_tr))
459 logging.info("pdr lo external %s", new_tr)
460 state = self._measure_and_update_state(state, new_tr)
462 elif pdr_lo.duration < state.duration:
463 logging.info("pdr lo minimal re-measure")
464 state = self._measure_and_update_state(
465 state, state.minimum_transmit_rate)
467 if ndr_hi.loss_fraction <= 0.0:
468 if ndr_hi.target_tr < state.maximum_transmit_rate:
470 state.maximum_transmit_rate,
472 ndr_rel_width, self.doublings, ndr_hi.target_tr))
473 logging.info("ndr hi external %s", new_tr)
474 state = self._measure_and_update_state(state, new_tr)
476 elif ndr_hi.duration < state.duration:
477 logging.info("ndr hi maximal re-measure")
478 state = self._measure_and_update_state(
479 state, state.maximum_transmit_rate)
481 if pdr_hi.loss_fraction <= state.packet_loss_ratio:
482 if pdr_hi.target_tr < state.maximum_transmit_rate:
484 state.maximum_transmit_rate,
486 pdr_rel_width, self.doublings, pdr_hi.target_tr))
487 logging.info("pdr hi external %s", new_tr)
488 state = self._measure_and_update_state(state, new_tr)
490 elif pdr_hi.duration < state.duration:
491 logging.info("ndr hi maximal re-measure")
492 state = self._measure_and_update_state(
493 state, state.maximum_transmit_rate)
495 # If we are hitting maximum_transmit_rate,
496 # it is still worth narrowing width,
497 # hoping large enough loss fraction will happen.
498 # But if we are hitting the minimal rate (at current duration),
499 # no additional measurement will help with that,
500 # so we can stop narrowing in this phase.
501 if (ndr_lo.target_tr <= state.minimum_transmit_rate
502 and ndr_lo.loss_fraction > 0.0):
504 if (pdr_lo.target_tr <= state.minimum_transmit_rate
505 and pdr_lo.loss_fraction > state.packet_loss_ratio):
507 if ndr_rel_width > state.width_goal:
508 # We have to narrow NDR width first, as NDR internal search
509 # can invalidate PDR (but not vice versa).
510 new_tr = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
511 logging.info("Bisecting for NDR at %s", new_tr)
512 state = self._measure_and_update_state(state, new_tr)
514 if pdr_rel_width > state.width_goal:
515 # PDR iternal search.
516 new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
517 logging.info("Bisecting for PDR at %s", new_tr)
518 state = self._measure_and_update_state(state, new_tr)
520 # We do not need to improve width, but there still might be
521 # some measurements with smaller duration.
522 # We need to re-measure with full duration, possibly
523 # creating invalid bounds to resolve (thus broadening width).
524 if ndr_lo.duration < state.duration:
525 logging.info("re-measuring NDR lower bound")
526 self._measure_and_update_state(state, ndr_lo.target_tr)
528 if pdr_lo.duration < state.duration:
529 logging.info("re-measuring PDR lower bound")
530 self._measure_and_update_state(state, pdr_lo.target_tr)
532 # Except when lower bounds have high loss fraction, in that case
533 # we do not need to re-measure _upper_ bounds.
534 if ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
535 logging.info("re-measuring NDR upper bound")
536 self._measure_and_update_state(state, ndr_hi.target_tr)
538 if pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
539 logging.info("re-measuring PDR upper bound")
540 self._measure_and_update_state(state, pdr_hi.target_tr)
542 # Widths are narrow (or lower bound minimal), bound measurements
543 # are long enough, we can return.
544 logging.info("phase done")