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."""
28 class SearchResults(Enum):
29 """Result of the drop rate search."""
37 """Type of rate units."""
39 PACKETS_PER_SECOND = 2
44 class LossAcceptanceType(Enum):
45 """Type of the loss acceptance criteria."""
51 class SearchResultType(Enum):
52 """Type of search result evaluation."""
57 class DropRateSearch(metaclass=ABCMeta):
58 """Abstract class with search algorithm implementation."""
61 # duration of traffic run (binary, linear)
63 # initial start rate (binary, linear)
64 self._rate_start = 100
65 # step of the linear search, unit: RateType (self._rate_type)
66 self._rate_linear_step = 10
67 # last rate of the binary search, unit: RateType (self._rate_type)
68 self._last_binary_rate = 0
69 # linear search direction, permitted values: SearchDirection
70 self._search_linear_direction = SearchDirection.TOP_DOWN
71 # upper limit of search, unit: RateType (self._rate_type)
73 # lower limit of search, unit: RateType (self._rate_type)
75 # permitted values: RateType
76 self._rate_type = RateType.PERCENTAGE
77 # accepted loss during search, units: LossAcceptanceType
78 self._loss_acceptance = 0
79 # permitted values: LossAcceptanceType
80 self._loss_acceptance_type = LossAcceptanceType.FRAMES
81 # size of frames to send
82 self._frame_size = u"64"
83 # binary convergence criterion type is self._rate_type
84 self._binary_convergence_threshold = 5000
85 # numbers of traffic runs during one rate step
86 self._max_attempts = 1
87 # type of search result evaluation, unit: SearchResultType
88 self._search_result_type = SearchResultType.BEST_OF_N
91 self._search_result = None
92 self._search_result_rate = None
95 def get_latency(self):
96 """Return min/avg/max latency.
98 :returns: Latency stats.
104 self, rate, frame_size, loss_acceptance, loss_acceptance_type,
105 traffic_profile, skip_warmup=False):
106 """Send traffic from TG and measure count of dropped frames.
108 :param rate: Offered traffic load.
109 :param frame_size: Size of frame.
110 :param loss_acceptance: Permitted drop ratio or frames count.
111 :param loss_acceptance_type: Type of permitted loss.
112 :param traffic_profile: Module name to use for traffic generation.
113 :param skip_warmup: Start TRex without warmup traffic if true.
115 :type frame_size: str
116 :type loss_acceptance: float
117 :type loss_acceptance_type: LossAcceptanceType
118 :type traffic_profile: str
119 :type skip_warmup: bool
120 :returns: Drop threshold exceeded? (True/False)
124 def set_search_rate_boundaries(self, max_rate, min_rate):
125 """Set search boundaries: min,max.
127 :param max_rate: Upper value of search boundaries.
128 :param min_rate: Lower value of search boundaries.
129 :type max_rate: float
130 :type min_rate: float
132 :raises ValueError: If min rate is lower than 0 or higher than max rate.
134 if float(min_rate) <= 0:
135 msg = u"min_rate must be higher than 0"
136 elif float(min_rate) > float(max_rate):
137 msg = u"min_rate must be lower than max_rate"
139 self._rate_max = float(max_rate)
140 self._rate_min = float(min_rate)
142 raise ValueError(msg)
144 def set_loss_acceptance(self, loss_acceptance):
145 """Set loss acceptance threshold for PDR search.
147 :param loss_acceptance: Loss acceptance threshold for PDR search.
148 :type loss_acceptance: str
150 :raises ValueError: If loss acceptance is lower than zero.
152 if float(loss_acceptance) >= 0:
153 self._loss_acceptance = float(loss_acceptance)
155 raise ValueError(u"Loss acceptance must be higher or equal 0")
157 def get_loss_acceptance(self):
158 """Return configured loss acceptance threshold.
160 :returns: Loss acceptance threshold.
163 return self._loss_acceptance
165 def set_loss_acceptance_type_percentage(self):
166 """Set loss acceptance threshold type to percentage.
170 self._loss_acceptance_type = LossAcceptanceType.PERCENTAGE
172 def set_loss_acceptance_type_frames(self):
173 """Set loss acceptance threshold type to frames.
177 self._loss_acceptance_type = LossAcceptanceType.FRAMES
179 def loss_acceptance_type_is_percentage(self):
180 """Return true if loss acceptance threshold type is percentage,
183 :returns: True if loss acceptance threshold type is percentage.
186 return self._loss_acceptance_type == LossAcceptanceType.PERCENTAGE
188 def set_search_linear_step(self, step_rate):
189 """Set step size for linear search.
191 :param step_rate: Linear search step size.
192 :type step_rate: float
195 self._rate_linear_step = float(step_rate)
197 def set_search_rate_type_percentage(self):
198 """Set rate type to percentage of linerate.
202 self._set_search_rate_type(RateType.PERCENTAGE)
204 def set_search_rate_type_bps(self):
205 """Set rate type to bits per second.
209 self._set_search_rate_type(RateType.BITS_PER_SECOND)
211 def set_search_rate_type_pps(self):
212 """Set rate type to packets per second.
216 self._set_search_rate_type(RateType.PACKETS_PER_SECOND)
218 def _set_search_rate_type(self, rate_type):
219 """Set rate type to one of RateType-s.
221 :param rate_type: Type of rate to set.
222 :type rate_type: RateType
224 :raises Exception: If rate type is unknown.
226 if rate_type in RateType:
227 self._rate_type = rate_type
229 raise Exception(f"rate_type unknown: {rate_type}")
231 def set_search_frame_size(self, frame_size):
232 """Set size of frames to send.
234 :param frame_size: Size of frames.
235 :type frame_size: str
238 self._frame_size = frame_size
240 def set_duration(self, duration):
241 """Set the duration of single traffic run.
243 :param duration: Number of seconds for traffic to run.
247 self._duration = int(duration)
249 def get_duration(self):
250 """Return configured duration of single traffic run.
252 :returns: Number of seconds for traffic to run.
255 return self._duration
257 def set_binary_convergence_threshold(self, convergence):
258 """Set convergence for binary search.
260 :param convergence: Threshold value number.
261 :type convergence: float
264 self._binary_convergence_threshold = float(convergence)
266 def get_binary_convergence_threshold(self):
267 """Get convergence for binary search.
269 :returns: Threshold value number.
272 return self._binary_convergence_threshold
274 def get_rate_type_str(self):
275 """Return rate type representation.
277 :returns: String representation of rate type.
279 :raises ValueError: If rate type is unknown.
281 if self._rate_type == RateType.PERCENTAGE:
283 elif self._rate_type == RateType.BITS_PER_SECOND:
285 elif self._rate_type == RateType.PACKETS_PER_SECOND:
288 raise ValueError(u"RateType unknown")
291 def set_max_attempts(self, max_attempts):
292 """Set maximum number of traffic runs during one rate step.
294 :param max_attempts: Number of traffic runs.
295 :type max_attempts: int
297 :raises ValueError: If max attempts is lower than zero.
299 if int(max_attempts) > 0:
300 self._max_attempts = int(max_attempts)
302 raise ValueError(u"Max attempt must by greater than zero")
304 def get_max_attempts(self):
305 """Return maximum number of traffic runs during one rate step.
307 :returns: Number of traffic runs.
310 return self._max_attempts
312 def set_search_result_type_best_of_n(self):
313 """Set type of search result evaluation to Best of N.
317 self._set_search_result_type(SearchResultType.BEST_OF_N)
319 def set_search_result_type_worst_of_n(self):
320 """Set type of search result evaluation to Worst of N.
324 self._set_search_result_type(SearchResultType.WORST_OF_N)
326 def _set_search_result_type(self, search_type):
327 """Set type of search result evaluation to one of SearchResultType.
329 :param search_type: Type of search result evaluation to set.
330 :type search_type: SearchResultType
332 :raises ValueError: If search type is unknown.
334 if search_type in SearchResultType:
335 self._search_result_type = search_type
337 raise ValueError(f"search_type unknown: {search_type}")
340 def _get_best_of_n(res_list):
341 """Return best result of N traffic runs.
343 :param res_list: List of return values from all runs at one rate step.
345 :returns: True if at least one run is True, False otherwise.
348 # Return True if any element of the iterable is True.
352 def _get_worst_of_n(res_list):
353 """Return worst result of N traffic runs.
355 :param res_list: List of return values from all runs at one rate step.
357 :returns: False if at least one run is False, True otherwise.
360 # Return False if not all elements of the iterable are True.
363 def _get_res_based_on_search_type(self, res_list):
364 """Return result of search based on search evaluation type.
366 :param res_list: List of return values from all runs at one rate step.
368 :returns: Boolean based on search result type.
370 :raises ValueError: If search result type is unknown.
372 if self._search_result_type == SearchResultType.BEST_OF_N:
373 retval = self._get_best_of_n(res_list)
374 elif self._search_result_type == SearchResultType.WORST_OF_N:
375 retval = self._get_worst_of_n(res_list)
377 raise ValueError(u"Unknown search result type")
380 def linear_search(self, start_rate, traffic_profile):
381 """Linear search of rate with loss below acceptance criteria.
383 :param start_rate: Initial rate.
384 :param traffic_profile: Module name to use for traffic generation.
385 :type start_rate: float
386 :type traffic_profile: str
388 :raises ValueError: If start rate is not in range.
390 if not self._rate_min <= float(start_rate) <= self._rate_max:
391 raise ValueError(u"Start rate is not in min,max range")
393 rate = float(start_rate)
394 # the last but one step
400 for dummy in range(self._max_attempts):
403 rate, self._frame_size, self._loss_acceptance,
404 self._loss_acceptance_type, traffic_profile
408 res = self._get_res_based_on_search_type(res)
410 if self._search_linear_direction == SearchDirection.TOP_DOWN:
411 # loss occurred, decrease rate
414 rate -= self._rate_linear_step
415 if rate < self._rate_min:
416 if prev_rate != self._rate_min:
417 # one last step with rate set to _rate_min
418 rate = self._rate_min
420 self._search_result = SearchResults.FAILURE
421 self._search_result_rate = None
424 # no loss => non/partial drop rate found
426 self._search_result = SearchResults.SUCCESS
427 self._search_result_rate = rate
430 raise RuntimeError(u"Unknown search result")
432 raise Exception(u"Unknown search direction")
434 def verify_search_result(self):
435 """Fail if search was not successful.
437 :returns: Result rate and latency stats.
439 :raises Exception: If search failed.
441 if self._search_result in \
442 [SearchResults.SUCCESS, SearchResults.SUSPICIOUS]:
443 return self._search_result_rate, self.get_latency()
444 raise Exception(u"Search FAILED")
447 self, b_min, b_max, traffic_profile, skip_max_rate=False,
449 """Binary search of rate with loss below acceptance criteria.
451 :param b_min: Min range rate.
452 :param b_max: Max range rate.
453 :param traffic_profile: Module name to use for traffic generation.
454 :param skip_max_rate: Start with max rate first
455 :param skip_warmup: Start TRex without warmup traffic if true.
458 :type traffic_profile: str
459 :type skip_max_rate: bool
460 :type skip_warmup: bool
462 :raises ValueError: If input values are not valid.
464 if not self._rate_min <= float(b_min) <= self._rate_max:
465 raise ValueError(u"Min rate is not in min,max range")
466 if not self._rate_min <= float(b_max) <= self._rate_max:
467 raise ValueError(u"Max rate is not in min,max range")
468 if float(b_max) < float(b_min):
469 raise ValueError(u"Min rate is greater than max rate")
471 # rate is half of interval + start of interval if not using max rate
472 rate = ((float(b_max) - float(b_min)) / 2) + float(b_min) \
473 if skip_max_rate else float(b_max)
475 # rate diff with previous run
476 rate_diff = abs(self._last_binary_rate - rate)
478 # convergence criterium
479 if float(rate_diff) < float(self._binary_convergence_threshold):
480 self._search_result = SearchResults.SUCCESS \
481 if self._search_result_rate else SearchResults.FAILURE
484 self._last_binary_rate = rate
487 for dummy in range(self._max_attempts):
488 res.append(self.measure_loss(
489 rate, self._frame_size, self._loss_acceptance,
490 self._loss_acceptance_type, traffic_profile,
491 skip_warmup=skip_warmup
494 res = self._get_res_based_on_search_type(res)
496 # loss occurred and it was above acceptance criteria
498 self.binary_search(b_min, rate, traffic_profile, True, True)
499 # there was no loss / loss below acceptance criteria
501 self._search_result_rate = rate
502 self.binary_search(rate, b_max, traffic_profile, True, True)
504 def combined_search(self, start_rate, traffic_profile):
505 """Combined search of rate with loss below acceptance criteria.
507 :param start_rate: Initial rate.
508 :param traffic_profile: Module name to use for traffic generation.
509 :type start_rate: float
510 :type traffic_profile: str
512 :raises RuntimeError: If linear search failed.
514 self.linear_search(start_rate, traffic_profile)
516 if self._search_result in \
517 [SearchResults.SUCCESS, SearchResults.SUSPICIOUS]:
518 b_min = self._search_result_rate
519 b_max = self._search_result_rate + self._rate_linear_step
521 # we found max rate by linear search
522 if self.floats_are_close_equal(float(b_min), self._rate_max):
525 # limiting binary range max value into max range
526 if float(b_max) > self._rate_max:
527 b_max = self._rate_max
530 temp_rate = self._search_result_rate
531 self._search_result_rate = None
533 # we will use binary search to refine search in one linear step
534 self.binary_search(b_min, b_max, traffic_profile, True)
537 # linear search succeed but binary failed or suspicious
538 if self._search_result != SearchResults.SUCCESS:
539 self._search_result = SearchResults.SUSPICIOUS
540 self._search_result_rate = temp_rate
541 # linear and binary search succeed
545 raise RuntimeError(u"Linear search FAILED")
548 def floats_are_close_equal(num_a, num_b, rel_tol=1e-9, abs_tol=0.0):
549 """Compares two float numbers for close equality.
551 :param num_a: First number to compare.
552 :param num_b: Second number to compare.
553 :param rel_tol: The relative tolerance.
554 :param abs_tol: The minimum absolute tolerance level. (Optional,
560 :returns: Returns True if num_a is close in value to num_b or equal.
563 :raises ValueError: If input values are not valid.
568 if rel_tol < 0.0 or abs_tol < 0.0:
569 raise ValueError(u"Error tolerances must be non-negative")
571 return abs(num_b - num_a) <= max(
572 rel_tol * max(abs(num_a), abs(num_b)), abs_tol