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 OptimizedSearchAlgorithm class."""
20 from .AbstractSearchAlgorithm import AbstractSearchAlgorithm
21 from .NdrPdrResult import NdrPdrResult
22 from .ReceiveRateInterval import ReceiveRateInterval
25 class OptimizedSearchAlgorithm(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 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 class ProgressState(object):
79 """Structure containing data to be passed around in recursion."""
82 self, result, phases, duration, width_goal, packet_loss_ratio,
83 minimum_transmit_rate, maximum_transmit_rate):
84 """Convert and store the argument values.
86 :param result: Current measured NDR and PDR intervals.
87 :param phases: How many intermediate phases to perform
88 before the current one.
89 :param duration: Trial duration to use in the current phase [s].
90 :param width_goal: The goal relative width for the curreent phase.
91 :param packet_loss_ratio: PDR fraction for the current search.
92 :param minimum_transmit_rate: Minimum target transmit rate
93 for the current search [pps].
94 :param maximum_transmit_rate: Maximum target transmit rate
95 for the current search [pps].
96 :type result: NdrPdrResult
99 :type width_goal: float
100 :type packet_loss_ratio: float
101 :type minimum_transmit_rate: float
102 :type maximum_transmit_rate: float
105 self.phases = int(phases)
106 self.duration = float(duration)
107 self.width_goal = float(width_goal)
108 self.packet_loss_ratio = float(packet_loss_ratio)
109 self.minimum_transmit_rate = float(minimum_transmit_rate)
110 self.maximum_transmit_rate = float(maximum_transmit_rate)
112 def __init__(self, rate_provider, final_relative_width=0.005,
113 final_trial_duration=30.0, initial_trial_duration=1.0,
114 number_of_intermediate_phases=2, timeout=600.0):
115 """Store rate provider and additional arguments.
117 :param rate_provider: Rate provider to use by this search object.
118 :param final_relative_width: Final lower bound transmit rate
119 cannot be more distant that this multiple of upper bound [1].
120 :param final_trial_duration: Trial duration for the final phase [s].
121 :param initial_trial_duration: Trial duration for the initial phase
122 and also for the first intermediate phase [s].
123 :param number_of_intermediate_phases: Number of intermediate phases
124 to perform before the final phase [1].
125 :param timeout: The search will fail itself when not finished
126 before this overall time [s].
127 :type rate_provider: AbstractRateProvider
128 :type final_relative_width: float
129 :type final_trial_duration: float
130 :type initial_trial_duration: int
131 :type number_of_intermediate_phases: int
134 super(OptimizedSearchAlgorithm, self).__init__(rate_provider)
135 self.final_trial_duration = float(final_trial_duration)
136 self.final_relative_width = float(final_relative_width)
137 self.number_of_intermediate_phases = int(number_of_intermediate_phases)
138 self.initial_trial_duration = float(initial_trial_duration)
139 self.timeout = float(timeout)
141 def narrow_down_ndr_and_pdr(
142 self, minimum_transmit_rate, maximum_transmit_rate,
144 """Perform initial phase, create state object, proceed with next phases.
146 :param minimum_transmit_rate: Minimal target transmit rate [pps].
147 :param maximum_transmit_rate: Maximal target transmit rate [pps].
148 :param packet_loss_ratio: Fraction of packets lost, for PDR [1].
149 :type minimum_transmit_rate: float
150 :type maximum_transmit_rate: float
151 :type packet_loss_ratio: float
152 :returns: Structure containing narrowed down intervals
153 and their measurements.
155 :raises RuntimeError: If total duration is larger than timeout.
157 minimum_transmit_rate = float(minimum_transmit_rate)
158 maximum_transmit_rate = float(maximum_transmit_rate)
159 packet_loss_ratio = float(packet_loss_ratio)
160 line_measurement = self.rate_provider.measure(
161 self.initial_trial_duration, maximum_transmit_rate)
162 # 0.999 is to avoid rounding errors which make
163 # the subsequent logic think the width is too broad.
165 minimum_transmit_rate,
166 maximum_transmit_rate * (1.0 - 0.999 * self.final_relative_width))
168 max_lo, max(minimum_transmit_rate, line_measurement.receive_rate))
169 mrr_measurement = self.rate_provider.measure(
170 self.initial_trial_duration, mrr)
171 # Attempt to get narrower width.
173 minimum_transmit_rate,
174 mrr * (1.0 - 0.999 * self.final_relative_width))
175 mrr2 = min(max2_lo, mrr_measurement.receive_rate)
176 if mrr2 > minimum_transmit_rate:
177 line_measurement = mrr_measurement
178 mrr_measurement = self.rate_provider.measure(
179 self.initial_trial_duration, mrr2)
180 starting_interval = ReceiveRateInterval(
181 mrr_measurement, line_measurement)
182 starting_result = NdrPdrResult(starting_interval, starting_interval)
183 state = self.ProgressState(
184 starting_result, self.number_of_intermediate_phases,
185 self.final_trial_duration, self.final_relative_width,
186 packet_loss_ratio, minimum_transmit_rate, maximum_transmit_rate)
187 state = self.ndrpdr(state)
190 def _measure_and_update_state(self, state, transmit_rate):
191 """Perform trial measurement, update bounds, return new state.
193 :param state: State before this measurement.
194 :param transmit_rate: Target transmit rate for this measurement [pps].
195 :type state: ProgressState
196 :type transmit_rate: float
197 :returns: State after the measurement.
198 :rtype: ProgressState
200 # TODO: Implement https://stackoverflow.com/a/24683360
201 # to avoid the string manipulation if log verbosity is too low.
202 logging.info("result before update: %s", state.result)
204 "relative widths in goals: %s", state.result.width_in_goals(
205 self.final_relative_width))
206 measurement = self.rate_provider.measure(state.duration, transmit_rate)
207 ndr_interval = self._new_interval(
208 state.result.ndr_interval, measurement, 0.0)
209 pdr_interval = self._new_interval(
210 state.result.pdr_interval, measurement, state.packet_loss_ratio)
211 state.result = NdrPdrResult(ndr_interval, pdr_interval)
215 def _new_interval(old_interval, measurement, packet_loss_ratio):
216 """Return new interval with bounds updated according to the measurement.
218 :param old_interval: The current interval before the measurement.
219 :param measurement: The new meaqsurement to take into account.
220 :param packet_loss_ratio: Fraction for PDR (or zero for NDR).
221 :type old_interval: ReceiveRateInterval
222 :type measurement: ReceiveRateMeasurement
223 :type packet_loss_ratio: float
224 :returns: The updated interval.
225 :rtype: ReceiveRateInterval
227 old_lo, old_hi = old_interval.measured_low, old_interval.measured_high
228 # Priority zero: direct replace if the target Tr is the same.
229 if measurement.target_tr in (old_lo.target_tr, old_hi.target_tr):
230 if measurement.target_tr == old_lo.target_tr:
231 return ReceiveRateInterval(measurement, old_hi)
233 return ReceiveRateInterval(old_lo, measurement)
234 # Priority one: invalid lower bound allows only one type of update.
235 if old_lo.loss_fraction > packet_loss_ratio:
236 # We can only expand down, old bound becomes valid upper one.
237 if measurement.target_tr < old_lo.target_tr:
238 return ReceiveRateInterval(measurement, old_lo)
241 # Lower bound is now valid.
242 # Next priorities depend on target Tr.
243 if measurement.target_tr < old_lo.target_tr:
244 # Lower external measurement, relevant only
245 # if the new measurement has high loss rate.
246 if measurement.loss_fraction > packet_loss_ratio:
247 # Returning the broader interval as old_lo
248 # would be invalid upper bound.
249 return ReceiveRateInterval(measurement, old_hi)
250 elif measurement.target_tr > old_hi.target_tr:
251 # Upper external measurement, only relevant for invalid upper bound.
252 if old_hi.loss_fraction <= packet_loss_ratio:
253 # Old upper bound becomes valid new lower bound.
254 return ReceiveRateInterval(old_hi, measurement)
256 # Internal measurement, replaced boundary
257 # depends on measured loss fraction.
258 if measurement.loss_fraction > packet_loss_ratio:
259 # We have found a narrow valid interval,
260 # regardless of whether old upper bound was valid.
261 return ReceiveRateInterval(old_lo, measurement)
263 # In ideal world, we would not want to shrink interval
264 # if upper bound is not valid.
265 # In the real world, we want to shrink it for
266 # "invalid upper bound at maximal rate" case.
267 return ReceiveRateInterval(measurement, old_hi)
268 # Fallback, the interval is unchanged by the measurement.
272 def double_relative_width(relative_width):
273 """Return relative width corresponding to double logarithmic width.
275 :param relative_width: The base relative width to double.
276 :type relative_width: float
277 :returns: The relative width of double logarithmic size.
280 return 1.999 * relative_width - relative_width * relative_width
281 # The number should be 2.0, but we want to avoid rounding errors,
282 # and ensure half of double is not larger than the original value.
285 def double_step_down(relative_width, current_bound):
286 """Return rate of double logarithmic width below.
288 :param relative_width: The base relative width to double.
289 :param current_bound: The current target transmit rate to move [pps].
290 :type relative_width: float
291 :type current_bound: float
292 :returns: Transmit rate smaller by logarithmically double width [pps].
295 return current_bound * (
296 1.0 - OptimizedSearchAlgorithm.double_relative_width(
300 def double_step_up(relative_width, current_bound):
301 """Return rate of double logarithmic width above.
303 :param relative_width: The base relative width to double.
304 :param current_bound: The current target transmit rate to move [pps].
305 :type relative_width: float
306 :type current_bound: float
307 :returns: Transmit rate larger by logarithmically double width [pps].
310 return current_bound / (
311 1.0 - OptimizedSearchAlgorithm.double_relative_width(
315 def half_relative_width(relative_width):
316 """Return relative width corresponding to half logarithmic width.
318 :param relative_width: The base relative width to halve.
319 :type relative_width: float
320 :returns: The relative width of half logarithmic size.
323 return 1.0 - math.sqrt(1.0 - relative_width)
326 def half_step_up(relative_width, current_bound):
327 """Return rate of half logarithmic width above.
329 :param relative_width: The base relative width to halve.
330 :param current_bound: The current target transmit rate to move [pps].
331 :type relative_width: float
332 :type current_bound: float
333 :returns: Transmit rate larger by logarithmically half width [pps].
336 return current_bound / (
337 1.0 - OptimizedSearchAlgorithm.half_relative_width(relative_width))
339 def ndrpdr(self, state):
340 """Pefrom trials for this phase. Return the new state when done.
342 :param state: State before this phase.
343 :type state: ProgressState
344 :returns: The updates state.
345 :rtype: ProgressState
346 :raises RuntimeError: If total duration is larger than timeout.
349 # We need to finish preceding intermediate phases first.
350 saved_phases = state.phases
352 # Preceding phases have shorter duration.
353 saved_duration = state.duration
354 duration_multiplier = state.duration / self.initial_trial_duration
355 phase_exponent = float(state.phases) / saved_phases
356 state.duration = self.initial_trial_duration * math.pow(
357 duration_multiplier, phase_exponent)
358 # Shorter durations do not need that narrow widths.
359 saved_width = state.width_goal
360 state.width_goal = self.double_relative_width(state.width_goal)
362 state = self.ndrpdr(state)
363 # Restore the state for current phase.
364 state.duration = saved_duration
365 state.width_goal = saved_width
366 state.phases = saved_phases # Not needed, but just in case.
368 "starting iterations with duration %s and relative width goal %s",
369 state.duration, state.width_goal)
370 start_time = time.time()
372 if time.time() > start_time + self.timeout:
373 raise RuntimeError("Optimized search takes too long.")
374 # Order of priorities: improper bounds (nl, pl, nh, ph),
375 # then narrowing relative Tr widths.
376 # Durations are not priorities yet,
377 # they will settle on their own hopefully.
378 ndr_lo = state.result.ndr_interval.measured_low
379 ndr_hi = state.result.ndr_interval.measured_high
380 pdr_lo = state.result.pdr_interval.measured_low
381 pdr_hi = state.result.pdr_interval.measured_high
383 state.width_goal, state.result.ndr_interval.rel_tr_width)
385 state.width_goal, state.result.pdr_interval.rel_tr_width)
386 # If we are hitting maximal or minimal rate, we cannot shift,
387 # but we can re-measure.
388 if ndr_lo.loss_fraction > 0.0:
389 if ndr_lo.target_tr > state.minimum_transmit_rate:
391 state.minimum_transmit_rate,
392 self.double_step_down(ndr_rel_width, ndr_lo.target_tr))
393 logging.info("ndr lo external %s", new_tr)
394 state = self._measure_and_update_state(state, new_tr)
396 elif ndr_lo.duration < state.duration:
397 logging.info("ndr lo minimal re-measure")
398 state = self._measure_and_update_state(
399 state, state.minimum_transmit_rate)
401 if pdr_lo.loss_fraction > state.packet_loss_ratio:
402 if pdr_lo.target_tr > state.minimum_transmit_rate:
404 state.minimum_transmit_rate,
405 self.double_step_down(pdr_rel_width, pdr_lo.target_tr))
406 logging.info("pdr lo external %s", new_tr)
407 state = self._measure_and_update_state(state, new_tr)
409 elif pdr_lo.duration < state.duration:
410 logging.info("pdr lo minimal re-measure")
411 state = self._measure_and_update_state(
412 state, state.minimum_transmit_rate)
414 if ndr_hi.loss_fraction <= 0.0:
415 if ndr_hi.target_tr < state.maximum_transmit_rate:
417 state.maximum_transmit_rate,
418 self.double_step_up(ndr_rel_width, ndr_hi.target_tr))
419 logging.info("ndr hi external %s", new_tr)
420 state = self._measure_and_update_state(state, new_tr)
422 elif ndr_hi.duration < state.duration:
423 logging.info("ndr hi maximal re-measure")
424 state = self._measure_and_update_state(
425 state, state.maximum_transmit_rate)
427 if pdr_hi.loss_fraction <= state.packet_loss_ratio:
428 if pdr_hi.target_tr < state.maximum_transmit_rate:
430 state.maximum_transmit_rate,
431 self.double_step_up(pdr_rel_width, pdr_hi.target_tr))
432 logging.info("pdr hi external %s", new_tr)
433 state = self._measure_and_update_state(state, new_tr)
435 elif pdr_hi.duration < state.duration:
436 logging.info("ndr hi maximal re-measure")
437 state = self._measure_and_update_state(
438 state, state.maximum_transmit_rate)
440 # If we are hitting maximum_transmit_rate,
441 # it is still worth narrowing width,
442 # hoping large enough Df will happen.
443 # But if we are hitting the minimal rate (at current duration),
444 # no additional measurement will help with that,
445 # so we can stop narrowing in this phase.
446 if (ndr_lo.target_tr <= state.minimum_transmit_rate
447 and ndr_lo.loss_fraction > 0.0):
449 if (pdr_lo.target_tr <= state.minimum_transmit_rate
450 and pdr_lo.loss_fraction > state.packet_loss_ratio):
452 if max(ndr_rel_width, pdr_rel_width) > state.width_goal:
453 # We have to narrow some width.
454 if ndr_rel_width >= pdr_rel_width:
455 new_tr = self.half_step_up(ndr_rel_width, ndr_lo.target_tr)
456 logging.info("Bisecting for NDR at %s", new_tr)
457 state = self._measure_and_update_state(state, new_tr)
460 new_tr = self.half_step_up(pdr_rel_width, pdr_lo.target_tr)
461 logging.info("Bisecting for PDR at %s", new_tr)
462 state = self._measure_and_update_state(state, new_tr)
464 # We do not need to improve width, but there still might be
465 # some measurements with smaller duration.
466 # We need to re-measure with full duration, possibly
467 # creating invalid bounds to resolve (thus broadening width).
468 if ndr_lo.duration < state.duration:
469 logging.info("re-measuring NDR lower bound")
470 self._measure_and_update_state(state, ndr_lo.target_tr)
472 if pdr_lo.duration < state.duration:
473 logging.info("re-measuring PDR lower bound")
474 self._measure_and_update_state(state, pdr_lo.target_tr)
476 # Except when lower bounds have high Df, in that case
477 # we do not need to re-measure _upper_ bounds.
478 if ndr_hi.duration < state.duration and ndr_rel_width > 0.0:
479 logging.info("re-measuring NDR upper bound")
480 self._measure_and_update_state(state, ndr_hi.target_tr)
482 if pdr_hi.duration < state.duration and pdr_rel_width > 0.0:
483 logging.info("re-measuring PDR upper bound")
484 self._measure_and_update_state(state, pdr_hi.target_tr)
486 # Widths are narrow (or lower bound minimal), bound measurements
487 # are long enough, we can return.
488 logging.info("phase done")