1 # Copyright (c) 2016 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."""
65 __metaclass__ = ABCMeta
68 # duration of traffic run (binary, linear)
70 # initial start rate (binary, linear)
71 self._rate_start = 100
72 # step of the linear search, unit: RateType (self._rate_type)
73 self._rate_linear_step = 10
74 # last rate of the binary search, unit: RateType (self._rate_type)
75 self._last_binary_rate = 0
76 # linear search direction, permitted values: SearchDirection
77 self._search_linear_direction = SearchDirection.TOP_DOWN
78 # upper limit of search, unit: RateType (self._rate_type)
80 # lower limit of search, unit: RateType (self._rate_type)
82 # permitted values: RateType
83 self._rate_type = RateType.PERCENTAGE
84 # accepted loss during search, units: LossAcceptanceType
85 self._loss_acceptance = 0
86 # permitted values: LossAcceptanceType
87 self._loss_acceptance_type = LossAcceptanceType.FRAMES
88 # size of frames to send
89 self._frame_size = "64"
90 # binary convergence criterium type is self._rate_type
91 self._binary_convergence_threshold = 5000
92 # numbers of traffic runs during one rate step
93 self._max_attempts = 1
94 # type of search result evaluation, unit: SearchResultType
95 self._search_result_type = SearchResultType.BEST_OF_N
98 self._search_result = None
99 self._search_result_rate = None
102 def get_latency(self):
103 """Return min/avg/max latency.
105 :returns: Latency stats.
111 def measure_loss(self, rate, frame_size, loss_acceptance,
112 loss_acceptance_type, traffic_type):
113 """Send traffic from TG and measure count of dropped frames.
115 :param rate: Offered traffic load.
116 :param frame_size: Size of frame.
117 :param loss_acceptance: Permitted drop ratio or frames count.
118 :param loss_acceptance_type: Type of permitted loss.
119 :param traffic_type: Traffic profile ([2,3]-node-L[2,3], ...).
121 :type frame_size: str
122 :type loss_acceptance: float
123 :type loss_acceptance_type: LossAcceptanceType
124 :type traffic_type: str
125 :returns: Drop threshold exceeded? (True/False)
130 def set_search_rate_boundaries(self, max_rate, min_rate):
131 """Set search boundaries: min,max.
133 :param max_rate: Upper value of search boundaries.
134 :param min_rate: Lower value of search boundaries.
135 :type max_rate: float
136 :type min_rate: float
138 :raises: ValueError if min rate is lower than 0 and higher than max rate
140 if float(min_rate) <= 0:
141 raise ValueError("min_rate must be higher than 0")
142 elif float(min_rate) > float(max_rate):
143 raise ValueError("min_rate must be lower than max_rate")
145 self._rate_max = float(max_rate)
146 self._rate_min = float(min_rate)
148 def set_loss_acceptance(self, loss_acceptance):
149 """Set loss acceptance treshold for PDR search.
151 :param loss_acceptance: Loss acceptance treshold for PDR search.
152 :type loss_acceptance: str
154 :raises: ValueError if loss acceptance is lower than zero
156 if float(loss_acceptance) < 0:
157 raise ValueError("Loss acceptance must be higher or equal 0")
159 self._loss_acceptance = float(loss_acceptance)
161 def get_loss_acceptance(self):
162 """Return configured loss acceptance treshold.
164 :returns: Loss acceptance treshold.
167 return self._loss_acceptance
169 def set_loss_acceptance_type_percentage(self):
170 """Set loss acceptance treshold type to percentage.
174 self._loss_acceptance_type = LossAcceptanceType.PERCENTAGE
176 def set_loss_acceptance_type_frames(self):
177 """Set loss acceptance treshold type to frames.
181 self._loss_acceptance_type = LossAcceptanceType.FRAMES
183 def loss_acceptance_type_is_percentage(self):
184 """Return true if loss acceptance treshold type is percentage,
187 :returns: True if loss acceptance treshold type is percentage.
190 return self._loss_acceptance_type == LossAcceptanceType.PERCENTAGE
192 def set_search_linear_step(self, step_rate):
193 """Set step size for linear search.
195 :param step_rate: Linear search step size.
196 :type step_rate: float
199 self._rate_linear_step = float(step_rate)
201 def set_search_rate_type_percentage(self):
202 """Set rate type to percentage of linerate.
206 self._set_search_rate_type(RateType.PERCENTAGE)
208 def set_search_rate_type_bps(self):
209 """Set rate type to bits per second.
213 self._set_search_rate_type(RateType.BITS_PER_SECOND)
215 def set_search_rate_type_pps(self):
216 """Set rate type to packets per second.
220 self._set_search_rate_type(RateType.PACKETS_PER_SECOND)
222 def _set_search_rate_type(self, rate_type):
223 """Set rate type to one of RateType-s.
225 :param rate_type: Type of rate to set.
226 :type rate_type: RateType
228 :raises: Exception if rate type is unknown
230 if rate_type not in RateType:
231 raise Exception("rate_type unknown: {}".format(rate_type))
233 self._rate_type = rate_type
235 def set_search_frame_size(self, frame_size):
236 """Set size of frames to send.
238 :param frame_size: Size of frames.
239 :type frame_size: str
242 self._frame_size = frame_size
244 def set_duration(self, duration):
245 """Set the duration of single traffic run.
247 :param duration: Number of seconds for traffic to run.
251 self._duration = int(duration)
253 def get_duration(self):
254 """Return configured duration of single traffic run.
256 :returns: Number of seconds for traffic to run.
259 return self._duration
261 def set_binary_convergence_threshold(self, convergence):
262 """Set convergence for binary search.
264 :param convergence: Treshold value number.
265 :type convergence: float
268 self._binary_convergence_threshold = float(convergence)
270 def get_binary_convergence_threshold(self):
271 """Get convergence for binary search.
273 :returns: Treshold value number.
276 return self._binary_convergence_threshold
278 def get_rate_type_str(self):
279 """Return rate type representation.
281 :returns: String representation of rate type.
283 :raises: ValueError if rate type is unknown
285 if self._rate_type == RateType.PERCENTAGE:
287 elif self._rate_type == RateType.BITS_PER_SECOND:
289 elif self._rate_type == RateType.PACKETS_PER_SECOND:
292 raise ValueError("RateType unknown")
294 def set_max_attempts(self, max_attempts):
295 """Set maximum number of traffic runs during one rate step.
297 :param max_attempts: Number of traffic runs.
298 :type max_attempts: int
300 :raises: ValueError if max attempts is lower than zero
302 if int(max_attempts) > 0:
303 self._max_attempts = int(max_attempts)
305 raise ValueError("Max attempt must by greater than zero")
307 def get_max_attempts(self):
308 """Return maximum number of traffic runs during one rate step.
310 :returns: Number of traffic runs.
313 return self._max_attempts
315 def set_search_result_type_best_of_n(self):
316 """Set type of search result evaluation to Best of N.
320 self._set_search_result_type(SearchResultType.BEST_OF_N)
322 def set_search_result_type_worst_of_n(self):
323 """Set type of search result evaluation to Worst of N.
327 self._set_search_result_type(SearchResultType.WORST_OF_N)
329 def _set_search_result_type(self, search_type):
330 """Set type of search result evaluation to one of SearchResultType.
332 :param search_type: Type of search result evaluation to set.
333 :type search_type: SearchResultType
335 :raises: ValueError if search type is unknown
337 if search_type not in SearchResultType:
338 raise ValueError("search_type unknown: {}".format(search_type))
340 self._search_result_type = search_type
343 def _get_best_of_n(res_list):
344 """Return best result of N traffic runs.
346 :param res_list: List of return values from all runs at one rate step.
348 :returns: True if at least one run is True, False otherwise.
351 # Return True if any element of the iterable is True.
355 def _get_worst_of_n(res_list):
356 """Return worst result of N traffic runs.
358 :param res_list: List of return values from all runs at one rate step.
360 :returns: False if at least one run is False, True otherwise.
363 # Return False if not all elements of the iterable are True.
366 def _get_res_based_on_search_type(self, res_list):
367 """Return result of search based on search evaluation type.
369 :param res_list: List of return values from all runs at one rate step.
371 :returns: Boolean based on search result type.
373 :raises: ValueError if search result type is unknown
375 if self._search_result_type == SearchResultType.BEST_OF_N:
376 return self._get_best_of_n(res_list)
377 elif self._search_result_type == SearchResultType.WORST_OF_N:
378 return self._get_worst_of_n(res_list)
380 raise ValueError("Unknown search result type")
382 def linear_search(self, start_rate, traffic_type):
383 """Linear search of rate with loss below acceptance criteria.
385 :param start_rate: Initial rate.
386 :param traffic_type: Traffic profile.
387 :type start_rate: float
388 :type traffic_type: str
390 :raises: ValueError if start rate is not in range
393 if not self._rate_min <= float(start_rate) <= self._rate_max:
394 raise ValueError("Start rate is not in min,max range")
396 rate = float(start_rate)
397 # the last but one step
403 for dummy in range(self._max_attempts):
404 res.append(self.measure_loss(rate, self._frame_size,
405 self._loss_acceptance,
406 self._loss_acceptance_type,
409 res = self._get_res_based_on_search_type(res)
411 if self._search_linear_direction == SearchDirection.BOTTOM_UP:
412 # loss occurred and it was above acceptance criteria
414 # if this is first run then we didn't find drop rate
415 if prev_rate is None:
416 self._search_result = SearchResults.FAILURE
417 self._search_result_rate = None
419 # else we found the rate, which is value from previous run
421 self._search_result = SearchResults.SUCCESS
422 self._search_result_rate = prev_rate
424 # there was no loss / loss below acceptance criteria
427 rate += self._rate_linear_step
428 if rate > self._rate_max:
429 if prev_rate != self._rate_max:
430 # one last step with rate set to _rate_max
431 rate = self._rate_max
434 self._search_result = SearchResults.SUCCESS
435 self._search_result_rate = prev_rate
440 raise RuntimeError("Unknown search result")
442 elif self._search_linear_direction == SearchDirection.TOP_DOWN:
443 # loss occurred, decrease rate
446 rate -= self._rate_linear_step
447 if rate < self._rate_min:
448 if prev_rate != self._rate_min:
449 # one last step with rate set to _rate_min
450 rate = self._rate_min
453 self._search_result = SearchResults.FAILURE
454 self._search_result_rate = None
458 # no loss => non/partial drop rate found
460 self._search_result = SearchResults.SUCCESS
461 self._search_result_rate = rate
464 raise RuntimeError("Unknown search result")
466 raise Exception("Unknown search direction")
468 raise Exception("Wrong codepath")
470 def verify_search_result(self):
471 """Fail if search was not successful.
473 :returns: Result rate and latency stats.
475 :raises: Exception if search failed
477 if self._search_result == SearchResults.FAILURE:
478 raise Exception('Search FAILED')
479 elif self._search_result in [SearchResults.SUCCESS,
480 SearchResults.SUSPICIOUS]:
481 return self._search_result_rate, self.get_latency()
483 def binary_search(self, b_min, b_max, traffic_type, skip_max_rate=False):
484 """Binary search of rate with loss below acceptance criteria.
486 :param b_min: Min range rate.
487 :param b_max: Max range rate.
488 :param traffic_type: Traffic profile.
489 :param skip_max_rate: Start with max rate first
492 :type traffic_type: str
493 :type skip_max_rate: bool
495 :raises: ValueError if input values are not valid
498 if not self._rate_min <= float(b_min) <= self._rate_max:
499 raise ValueError("Min rate is not in min,max range")
500 if not self._rate_min <= float(b_max) <= self._rate_max:
501 raise ValueError("Max rate is not in min,max range")
502 if float(b_max) < float(b_min):
503 raise ValueError("Min rate is greater than max rate")
507 # rate is half of interval + start of interval
508 rate = ((float(b_max) - float(b_min)) / 2) + float(b_min)
510 # rate is max of interval
512 # rate diff with previous run
513 rate_diff = abs(self._last_binary_rate - rate)
515 # convergence criterium
516 if float(rate_diff) < float(self._binary_convergence_threshold):
517 if not self._search_result_rate:
518 self._search_result = SearchResults.FAILURE
520 self._search_result = SearchResults.SUCCESS
523 self._last_binary_rate = rate
526 for dummy in range(self._max_attempts):
527 res.append(self.measure_loss(rate, self._frame_size,
528 self._loss_acceptance,
529 self._loss_acceptance_type,
532 res = self._get_res_based_on_search_type(res)
534 # loss occurred and it was above acceptance criteria
536 self.binary_search(b_min, rate, traffic_type, True)
537 # there was no loss / loss below acceptance criteria
539 self._search_result_rate = rate
540 self.binary_search(rate, b_max, traffic_type, True)
542 def combined_search(self, start_rate, traffic_type):
543 """Combined search of rate with loss below acceptance criteria.
545 :param start_rate: Initial rate.
546 :param traffic_type: Traffic profile.
547 :type start_rate: float
548 :type traffic_type: str
550 :raises: RuntimeError if linear search failed
553 self.linear_search(start_rate, traffic_type)
555 if self._search_result in [SearchResults.SUCCESS,
556 SearchResults.SUSPICIOUS]:
557 b_min = self._search_result_rate
558 b_max = self._search_result_rate + self._rate_linear_step
560 # we found max rate by linear search
561 if self.floats_are_close_equal(float(b_min), self._rate_max):
564 # limiting binary range max value into max range
565 if float(b_max) > self._rate_max:
566 b_max = self._rate_max
569 temp_rate = self._search_result_rate
570 self._search_result_rate = None
572 # we will use binary search to refine search in one linear step
573 self.binary_search(b_min, b_max, traffic_type, True)
575 # linear and binary search succeed
576 if self._search_result == SearchResults.SUCCESS:
578 # linear search succeed but binary failed or suspicious
580 self._search_result = SearchResults.SUSPICIOUS
581 self._search_result_rate = temp_rate
583 raise RuntimeError("Linear search FAILED")
586 def floats_are_close_equal(num_a, num_b, rel_tol=1e-9, abs_tol=0.0):
587 """Compares two float numbers for close equality.
589 :param num_a: First number to compare.
590 :param num_b: Second number to compare.
591 :param rel_tol=1e-9: The relative tolerance.
592 :param abs_tol=0.0: The minimum absolute tolerance level.
597 :returns: Returns True if num_a is close in value to num_b or equal.
600 :raises: ValueError if input values are not valid
606 if rel_tol < 0.0 or abs_tol < 0.0:
607 raise ValueError('Error tolerances must be non-negative')
609 return abs(num_b - num_a) <= max(rel_tol * max(abs(num_a), abs(num_b)),