1 # Copyright (c) 2019 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 """Drop rate search algorithms"""
16 from abc import ABCMeta, abstractmethod
17 from enum import Enum, unique
21 class SearchDirection(Enum):
22 """Direction of linear search."""
29 class SearchResults(Enum):
30 """Result of the drop rate search."""
39 """Type of rate units."""
42 PACKETS_PER_SECOND = 2
47 class LossAcceptanceType(Enum):
48 """Type of the loss acceptance criteria."""
55 class SearchResultType(Enum):
56 """Type of search result evaluation."""
62 class DropRateSearch(object):
63 """Abstract class with search algorithm implementation."""
64 #TODO DropRateSearch should be refactored as part of CSIT-1378
65 #pylint: disable=too-many-instance-attributes
67 __metaclass__ = ABCMeta
70 # duration of traffic run (binary, linear)
72 # initial start rate (binary, linear)
73 self._rate_start = 100
74 # step of the linear search, unit: RateType (self._rate_type)
75 self._rate_linear_step = 10
76 # last rate of the binary search, unit: RateType (self._rate_type)
77 self._last_binary_rate = 0
78 # linear search direction, permitted values: SearchDirection
79 self._search_linear_direction = SearchDirection.TOP_DOWN
80 # upper limit of search, unit: RateType (self._rate_type)
82 # lower limit of search, unit: RateType (self._rate_type)
84 # permitted values: RateType
85 self._rate_type = RateType.PERCENTAGE
86 # accepted loss during search, units: LossAcceptanceType
87 self._loss_acceptance = 0
88 # permitted values: LossAcceptanceType
89 self._loss_acceptance_type = LossAcceptanceType.FRAMES
90 # size of frames to send
91 self._frame_size = "64"
92 # binary convergence criterium type is self._rate_type
93 self._binary_convergence_threshold = 5000
94 # numbers of traffic runs during one rate step
95 self._max_attempts = 1
96 # type of search result evaluation, unit: SearchResultType
97 self._search_result_type = SearchResultType.BEST_OF_N
100 self._search_result = None
101 self._search_result_rate = None
104 def get_latency(self):
105 """Return min/avg/max latency.
107 :returns: Latency stats.
113 def measure_loss(self, rate, frame_size, loss_acceptance,
114 loss_acceptance_type, traffic_profile, skip_warmup=False):
115 """Send traffic from TG and measure count of dropped frames.
117 :param rate: Offered traffic load.
118 :param frame_size: Size of frame.
119 :param loss_acceptance: Permitted drop ratio or frames count.
120 :param loss_acceptance_type: Type of permitted loss.
121 :param traffic_profile: Module name to use for traffic generation.
122 :param skip_warmup: Start TRex without warmup traffic if true.
124 :type frame_size: str
125 :type loss_acceptance: float
126 :type loss_acceptance_type: LossAcceptanceType
127 :type traffic_profile: str
128 :type skip_warmup: bool
129 :returns: Drop threshold exceeded? (True/False)
134 def set_search_rate_boundaries(self, max_rate, min_rate):
135 """Set search boundaries: min,max.
137 :param max_rate: Upper value of search boundaries.
138 :param min_rate: Lower value of search boundaries.
139 :type max_rate: float
140 :type min_rate: float
142 :raises ValueError: If min rate is lower than 0 or higher than max rate.
144 if float(min_rate) <= 0:
145 raise ValueError("min_rate must be higher than 0")
146 elif float(min_rate) > float(max_rate):
147 raise ValueError("min_rate must be lower than max_rate")
149 self._rate_max = float(max_rate)
150 self._rate_min = float(min_rate)
152 def set_loss_acceptance(self, loss_acceptance):
153 """Set loss acceptance treshold for PDR search.
155 :param loss_acceptance: Loss acceptance treshold for PDR search.
156 :type loss_acceptance: str
158 :raises ValueError: If loss acceptance is lower than zero.
160 if float(loss_acceptance) < 0:
161 raise ValueError("Loss acceptance must be higher or equal 0")
163 self._loss_acceptance = float(loss_acceptance)
165 def get_loss_acceptance(self):
166 """Return configured loss acceptance treshold.
168 :returns: Loss acceptance treshold.
171 return self._loss_acceptance
173 def set_loss_acceptance_type_percentage(self):
174 """Set loss acceptance treshold type to percentage.
178 self._loss_acceptance_type = LossAcceptanceType.PERCENTAGE
180 def set_loss_acceptance_type_frames(self):
181 """Set loss acceptance treshold type to frames.
185 self._loss_acceptance_type = LossAcceptanceType.FRAMES
187 def loss_acceptance_type_is_percentage(self):
188 """Return true if loss acceptance treshold type is percentage,
191 :returns: True if loss acceptance treshold type is percentage.
194 return self._loss_acceptance_type == LossAcceptanceType.PERCENTAGE
196 def set_search_linear_step(self, step_rate):
197 """Set step size for linear search.
199 :param step_rate: Linear search step size.
200 :type step_rate: float
203 self._rate_linear_step = float(step_rate)
205 def set_search_rate_type_percentage(self):
206 """Set rate type to percentage of linerate.
210 self._set_search_rate_type(RateType.PERCENTAGE)
212 def set_search_rate_type_bps(self):
213 """Set rate type to bits per second.
217 self._set_search_rate_type(RateType.BITS_PER_SECOND)
219 def set_search_rate_type_pps(self):
220 """Set rate type to packets per second.
224 self._set_search_rate_type(RateType.PACKETS_PER_SECOND)
226 def _set_search_rate_type(self, rate_type):
227 """Set rate type to one of RateType-s.
229 :param rate_type: Type of rate to set.
230 :type rate_type: RateType
232 :raises Exception: If rate type is unknown.
234 if rate_type not in RateType:
235 raise Exception("rate_type unknown: {}".format(rate_type))
237 self._rate_type = rate_type
239 def set_search_frame_size(self, frame_size):
240 """Set size of frames to send.
242 :param frame_size: Size of frames.
243 :type frame_size: str
246 self._frame_size = frame_size
248 def set_duration(self, duration):
249 """Set the duration of single traffic run.
251 :param duration: Number of seconds for traffic to run.
255 self._duration = int(duration)
257 def get_duration(self):
258 """Return configured duration of single traffic run.
260 :returns: Number of seconds for traffic to run.
263 return self._duration
265 def set_binary_convergence_threshold(self, convergence):
266 """Set convergence for binary search.
268 :param convergence: Treshold value number.
269 :type convergence: float
272 self._binary_convergence_threshold = float(convergence)
274 def get_binary_convergence_threshold(self):
275 """Get convergence for binary search.
277 :returns: Treshold value number.
280 return self._binary_convergence_threshold
282 def get_rate_type_str(self):
283 """Return rate type representation.
285 :returns: String representation of rate type.
287 :raises ValueError: If rate type is unknown.
289 if self._rate_type == RateType.PERCENTAGE:
291 elif self._rate_type == RateType.BITS_PER_SECOND:
293 elif self._rate_type == RateType.PACKETS_PER_SECOND:
296 raise ValueError("RateType unknown")
298 def set_max_attempts(self, max_attempts):
299 """Set maximum number of traffic runs during one rate step.
301 :param max_attempts: Number of traffic runs.
302 :type max_attempts: int
304 :raises ValueError: If max attempts is lower than zero.
306 if int(max_attempts) > 0:
307 self._max_attempts = int(max_attempts)
309 raise ValueError("Max attempt must by greater than zero")
311 def get_max_attempts(self):
312 """Return maximum number of traffic runs during one rate step.
314 :returns: Number of traffic runs.
317 return self._max_attempts
319 def set_search_result_type_best_of_n(self):
320 """Set type of search result evaluation to Best of N.
324 self._set_search_result_type(SearchResultType.BEST_OF_N)
326 def set_search_result_type_worst_of_n(self):
327 """Set type of search result evaluation to Worst of N.
331 self._set_search_result_type(SearchResultType.WORST_OF_N)
333 def _set_search_result_type(self, search_type):
334 """Set type of search result evaluation to one of SearchResultType.
336 :param search_type: Type of search result evaluation to set.
337 :type search_type: SearchResultType
339 :raises ValueError: If search type is unknown.
341 if search_type not in SearchResultType:
342 raise ValueError("search_type unknown: {}".format(search_type))
344 self._search_result_type = search_type
347 def _get_best_of_n(res_list):
348 """Return best result of N traffic runs.
350 :param res_list: List of return values from all runs at one rate step.
352 :returns: True if at least one run is True, False otherwise.
355 # Return True if any element of the iterable is True.
359 def _get_worst_of_n(res_list):
360 """Return worst result of N traffic runs.
362 :param res_list: List of return values from all runs at one rate step.
364 :returns: False if at least one run is False, True otherwise.
367 # Return False if not all elements of the iterable are True.
370 def _get_res_based_on_search_type(self, res_list):
371 """Return result of search based on search evaluation type.
373 :param res_list: List of return values from all runs at one rate step.
375 :returns: Boolean based on search result type.
377 :raises ValueError: If search result type is unknown.
379 if self._search_result_type == SearchResultType.BEST_OF_N:
380 return self._get_best_of_n(res_list)
381 elif self._search_result_type == SearchResultType.WORST_OF_N:
382 return self._get_worst_of_n(res_list)
384 raise ValueError("Unknown search result type")
386 def linear_search(self, start_rate, traffic_profile):
387 """Linear search of rate with loss below acceptance criteria.
389 :param start_rate: Initial rate.
390 :param traffic_profile: Module name to use for traffic generation.
391 :type start_rate: float
392 :type traffic_profile: str
394 :raises ValueError: If start rate is not in range.
397 if not self._rate_min <= float(start_rate) <= self._rate_max:
398 raise ValueError("Start rate is not in min,max range")
400 rate = float(start_rate)
401 # the last but one step
407 for dummy in range(self._max_attempts):
408 res.append(self.measure_loss(
409 rate, self._frame_size, self._loss_acceptance,
410 self._loss_acceptance_type, traffic_profile))
412 res = self._get_res_based_on_search_type(res)
414 if self._search_linear_direction == SearchDirection.TOP_DOWN:
415 # loss occurred, decrease rate
418 rate -= self._rate_linear_step
419 if rate < self._rate_min:
420 if prev_rate != self._rate_min:
421 # one last step with rate set to _rate_min
422 rate = self._rate_min
425 self._search_result = SearchResults.FAILURE
426 self._search_result_rate = None
430 # no loss => non/partial drop rate found
432 self._search_result = SearchResults.SUCCESS
433 self._search_result_rate = rate
436 raise RuntimeError("Unknown search result")
438 raise Exception("Unknown search direction")
440 def verify_search_result(self):
441 """Fail if search was not successful.
443 :returns: Result rate and latency stats.
445 :raises Exception: If search failed.
447 if self._search_result in [
448 SearchResults.SUCCESS, SearchResults.SUSPICIOUS]:
449 return self._search_result_rate, self.get_latency()
450 raise Exception('Search FAILED')
452 def binary_search(self, b_min, b_max, traffic_profile, skip_max_rate=False,
454 """Binary search of rate with loss below acceptance criteria.
456 :param b_min: Min range rate.
457 :param b_max: Max range rate.
458 :param traffic_profile: Module name to use for traffic generation.
459 :param skip_max_rate: Start with max rate first
460 :param skip_warmup: Start TRex without warmup traffic if true.
463 :type traffic_profile: str
464 :type skip_max_rate: bool
465 :type skip_warmup: bool
467 :raises ValueError: If input values are not valid.
470 if not self._rate_min <= float(b_min) <= self._rate_max:
471 raise ValueError("Min rate is not in min,max range")
472 if not self._rate_min <= float(b_max) <= self._rate_max:
473 raise ValueError("Max rate is not in min,max range")
474 if float(b_max) < float(b_min):
475 raise ValueError("Min rate is greater than max rate")
477 # rate is half of interval + start of interval if not using max rate
478 rate = ((float(b_max) - float(b_min)) / 2) + float(b_min) \
479 if skip_max_rate else float(b_max)
481 # rate diff with previous run
482 rate_diff = abs(self._last_binary_rate - rate)
484 # convergence criterium
485 if float(rate_diff) < float(self._binary_convergence_threshold):
486 self._search_result = SearchResults.SUCCESS \
487 if self._search_result_rate else SearchResults.FAILURE
490 self._last_binary_rate = rate
493 for dummy in range(self._max_attempts):
494 res.append(self.measure_loss(
495 rate, self._frame_size, self._loss_acceptance,
496 self._loss_acceptance_type, traffic_profile,
497 skip_warmup=skip_warmup))
499 res = self._get_res_based_on_search_type(res)
501 # loss occurred and it was above acceptance criteria
503 self.binary_search(b_min, rate, traffic_profile, True, True)
504 # there was no loss / loss below acceptance criteria
506 self._search_result_rate = rate
507 self.binary_search(rate, b_max, traffic_profile, True, True)
509 def combined_search(self, start_rate, traffic_profile):
510 """Combined search of rate with loss below acceptance criteria.
512 :param start_rate: Initial rate.
513 :param traffic_profile: Module name to use for traffic generation.
514 :type start_rate: float
515 :type traffic_profile: str
517 :raises RuntimeError: If linear search failed.
520 self.linear_search(start_rate, traffic_profile)
522 if self._search_result in [SearchResults.SUCCESS,
523 SearchResults.SUSPICIOUS]:
524 b_min = self._search_result_rate
525 b_max = self._search_result_rate + self._rate_linear_step
527 # we found max rate by linear search
528 if self.floats_are_close_equal(float(b_min), self._rate_max):
531 # limiting binary range max value into max range
532 if float(b_max) > self._rate_max:
533 b_max = self._rate_max
536 temp_rate = self._search_result_rate
537 self._search_result_rate = None
539 # we will use binary search to refine search in one linear step
540 self.binary_search(b_min, b_max, traffic_profile, True)
542 # linear and binary search succeed
543 if self._search_result == SearchResults.SUCCESS:
545 # linear search succeed but binary failed or suspicious
547 self._search_result = SearchResults.SUSPICIOUS
548 self._search_result_rate = temp_rate
550 raise RuntimeError("Linear search FAILED")
553 def floats_are_close_equal(num_a, num_b, rel_tol=1e-9, abs_tol=0.0):
554 """Compares two float numbers for close equality.
556 :param num_a: First number to compare.
557 :param num_b: Second number to compare.
558 :param rel_tol=1e-9: The relative tolerance.
559 :param abs_tol=0.0: The minimum absolute tolerance level.
564 :returns: Returns True if num_a is close in value to num_b or equal.
567 :raises ValueError: If input values are not valid.
573 if rel_tol < 0.0 or abs_tol < 0.0:
574 raise ValueError('Error tolerances must be non-negative')
576 return abs(num_b - num_a) <= max(rel_tol * max(abs(num_a), abs(num_b)),