Fix warnings reported by gen_doc.sh
[csit.git] / resources / libraries / python / DropRateSearch.py
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:
5 #
6 #     http://www.apache.org/licenses/LICENSE-2.0
7 #
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.
13
14 """Drop rate search algorithms"""
15
16 from abc import ABCMeta, abstractmethod
17 from enum import Enum, unique
18
19
20 @unique
21 class SearchDirection(Enum):
22     """Direction of linear search."""
23
24     TOP_DOWN = 1
25     BOTTOM_UP = 2
26
27
28 @unique
29 class SearchResults(Enum):
30     """Result of the drop rate search."""
31
32     SUCCESS = 1
33     FAILURE = 2
34     SUSPICIOUS = 3
35
36
37 @unique
38 class RateType(Enum):
39     """Type of rate units."""
40
41     PERCENTAGE = 1
42     PACKETS_PER_SECOND = 2
43     BITS_PER_SECOND = 3
44
45
46 @unique
47 class LossAcceptanceType(Enum):
48     """Type of the loss acceptance criteria."""
49
50     FRAMES = 1
51     PERCENTAGE = 2
52
53
54 @unique
55 class SearchResultType(Enum):
56     """Type of search result evaluation."""
57
58     BEST_OF_N = 1
59     WORST_OF_N = 2
60
61
62 class DropRateSearch(object):
63     """Abstract class with search algorithm implementation."""
64
65     __metaclass__ = ABCMeta
66
67     def __init__(self):
68         # duration of traffic run (binary, linear)
69         self._duration = 60
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)
79         self._rate_max = 100
80         # lower limit of search, unit: RateType (self._rate_type)
81         self._rate_min = 1
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
96
97         # result of search
98         self._search_result = None
99         self._search_result_rate = None
100
101     @abstractmethod
102     def get_latency(self):
103         """Return min/avg/max latency.
104
105         :returns: Latency stats.
106         :rtype: list
107         """
108         pass
109
110     @abstractmethod
111     def measure_loss(self, rate, frame_size, loss_acceptance,
112                      loss_acceptance_type, traffic_type, skip_warmup=False):
113         """Send traffic from TG and measure count of dropped frames.
114
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], ...).
120         :param skip_warmup: Start TRex without warmup traffic if true.
121         :type rate: int
122         :type frame_size: str
123         :type loss_acceptance: float
124         :type loss_acceptance_type: LossAcceptanceType
125         :type traffic_type: str
126         :type traffic_type: bool
127         :returns: Drop threshold exceeded? (True/False)
128         :rtype: bool
129         """
130         pass
131
132     def set_search_rate_boundaries(self, max_rate, min_rate):
133         """Set search boundaries: min,max.
134
135         :param max_rate: Upper value of search boundaries.
136         :param min_rate: Lower value of search boundaries.
137         :type max_rate: float
138         :type min_rate: float
139         :returns: nothing
140         :raises ValueError: If min rate is lower than 0 or higher than max rate.
141         """
142         if float(min_rate) <= 0:
143             raise ValueError("min_rate must be higher than 0")
144         elif float(min_rate) > float(max_rate):
145             raise ValueError("min_rate must be lower than max_rate")
146         else:
147             self._rate_max = float(max_rate)
148             self._rate_min = float(min_rate)
149
150     def set_loss_acceptance(self, loss_acceptance):
151         """Set loss acceptance treshold for PDR search.
152
153         :param loss_acceptance: Loss acceptance treshold for PDR search.
154         :type loss_acceptance: str
155         :returns: nothing
156         :raises ValueError: If loss acceptance is lower than zero.
157         """
158         if float(loss_acceptance) < 0:
159             raise ValueError("Loss acceptance must be higher or equal 0")
160         else:
161             self._loss_acceptance = float(loss_acceptance)
162
163     def get_loss_acceptance(self):
164         """Return configured loss acceptance treshold.
165
166         :returns: Loss acceptance treshold.
167         :rtype: float
168         """
169         return self._loss_acceptance
170
171     def set_loss_acceptance_type_percentage(self):
172         """Set loss acceptance treshold type to percentage.
173
174         :returns: nothing
175         """
176         self._loss_acceptance_type = LossAcceptanceType.PERCENTAGE
177
178     def set_loss_acceptance_type_frames(self):
179         """Set loss acceptance treshold type to frames.
180
181         :returns: nothing
182         """
183         self._loss_acceptance_type = LossAcceptanceType.FRAMES
184
185     def loss_acceptance_type_is_percentage(self):
186         """Return true if loss acceptance treshold type is percentage,
187            false otherwise.
188
189         :returns: True if loss acceptance treshold type is percentage.
190         :rtype: boolean
191         """
192         return self._loss_acceptance_type == LossAcceptanceType.PERCENTAGE
193
194     def set_search_linear_step(self, step_rate):
195         """Set step size for linear search.
196
197         :param step_rate: Linear search step size.
198         :type step_rate: float
199         :returns: nothing
200         """
201         self._rate_linear_step = float(step_rate)
202
203     def set_search_rate_type_percentage(self):
204         """Set rate type to percentage of linerate.
205
206         :returns: nothing
207         """
208         self._set_search_rate_type(RateType.PERCENTAGE)
209
210     def set_search_rate_type_bps(self):
211         """Set rate type to bits per second.
212
213         :returns: nothing
214         """
215         self._set_search_rate_type(RateType.BITS_PER_SECOND)
216
217     def set_search_rate_type_pps(self):
218         """Set rate type to packets per second.
219
220         :returns: nothing
221         """
222         self._set_search_rate_type(RateType.PACKETS_PER_SECOND)
223
224     def _set_search_rate_type(self, rate_type):
225         """Set rate type to one of RateType-s.
226
227         :param rate_type: Type of rate to set.
228         :type rate_type: RateType
229         :returns: nothing
230         :raises Exception: If rate type is unknown.
231         """
232         if rate_type not in RateType:
233             raise Exception("rate_type unknown: {}".format(rate_type))
234         else:
235             self._rate_type = rate_type
236
237     def set_search_frame_size(self, frame_size):
238         """Set size of frames to send.
239
240         :param frame_size: Size of frames.
241         :type frame_size: str
242         :returns: nothing
243         """
244         self._frame_size = frame_size
245
246     def set_duration(self, duration):
247         """Set the duration of single traffic run.
248
249         :param duration: Number of seconds for traffic to run.
250         :type duration: int
251         :returns: nothing
252         """
253         self._duration = int(duration)
254
255     def get_duration(self):
256         """Return configured duration of single traffic run.
257
258         :returns: Number of seconds for traffic to run.
259         :rtype: int
260         """
261         return self._duration
262
263     def set_binary_convergence_threshold(self, convergence):
264         """Set convergence for binary search.
265
266         :param convergence: Treshold value number.
267         :type convergence: float
268         :returns: nothing
269         """
270         self._binary_convergence_threshold = float(convergence)
271
272     def get_binary_convergence_threshold(self):
273         """Get convergence for binary search.
274
275         :returns: Treshold value number.
276         :rtype: float
277         """
278         return self._binary_convergence_threshold
279
280     def get_rate_type_str(self):
281         """Return rate type representation.
282
283         :returns: String representation of rate type.
284         :rtype: str
285         :raises ValueError: If rate type is unknown.
286         """
287         if self._rate_type == RateType.PERCENTAGE:
288             return "%"
289         elif self._rate_type == RateType.BITS_PER_SECOND:
290             return "bps"
291         elif self._rate_type == RateType.PACKETS_PER_SECOND:
292             return "pps"
293         else:
294             raise ValueError("RateType unknown")
295
296     def set_max_attempts(self, max_attempts):
297         """Set maximum number of traffic runs during one rate step.
298
299         :param max_attempts: Number of traffic runs.
300         :type max_attempts: int
301         :returns: nothing
302         :raises ValueError: If max attempts is lower than zero.
303         """
304         if int(max_attempts) > 0:
305             self._max_attempts = int(max_attempts)
306         else:
307             raise ValueError("Max attempt must by greater than zero")
308
309     def get_max_attempts(self):
310         """Return maximum number of traffic runs during one rate step.
311
312         :returns: Number of traffic runs.
313         :rtype: int
314         """
315         return self._max_attempts
316
317     def set_search_result_type_best_of_n(self):
318         """Set type of search result evaluation to Best of N.
319
320         :returns: nothing
321         """
322         self._set_search_result_type(SearchResultType.BEST_OF_N)
323
324     def set_search_result_type_worst_of_n(self):
325         """Set type of search result evaluation to Worst of N.
326
327         :returns: nothing
328         """
329         self._set_search_result_type(SearchResultType.WORST_OF_N)
330
331     def _set_search_result_type(self, search_type):
332         """Set type of search result evaluation to one of SearchResultType.
333
334         :param search_type: Type of search result evaluation to set.
335         :type search_type: SearchResultType
336         :returns: nothing
337         :raises ValueError: If search type is unknown.
338         """
339         if search_type not in SearchResultType:
340             raise ValueError("search_type unknown: {}".format(search_type))
341         else:
342             self._search_result_type = search_type
343
344     @staticmethod
345     def _get_best_of_n(res_list):
346         """Return best result of N traffic runs.
347
348         :param res_list: List of return values from all runs at one rate step.
349         :type res_list: list
350         :returns: True if at least one run is True, False otherwise.
351         :rtype: boolean
352         """
353         # Return True if any element of the iterable is True.
354         return any(res_list)
355
356     @staticmethod
357     def _get_worst_of_n(res_list):
358         """Return worst result of N traffic runs.
359
360         :param res_list: List of return values from all runs at one rate step.
361         :type res_list: list
362         :returns: False if at least one run is False, True otherwise.
363         :rtype: boolean
364         """
365         # Return False if not all elements of the iterable are True.
366         return all(res_list)
367
368     def _get_res_based_on_search_type(self, res_list):
369         """Return result of search based on search evaluation type.
370
371         :param res_list: List of return values from all runs at one rate step.
372         :type res_list: list
373         :returns: Boolean based on search result type.
374         :rtype: boolean
375         :raises ValueError: If search result type is unknown.
376         """
377         if self._search_result_type == SearchResultType.BEST_OF_N:
378             return self._get_best_of_n(res_list)
379         elif self._search_result_type == SearchResultType.WORST_OF_N:
380             return self._get_worst_of_n(res_list)
381         else:
382             raise ValueError("Unknown search result type")
383
384     def linear_search(self, start_rate, traffic_type):
385         """Linear search of rate with loss below acceptance criteria.
386
387         :param start_rate: Initial rate.
388         :param traffic_type: Traffic profile.
389         :type start_rate: float
390         :type traffic_type: str
391         :returns: nothing
392         :raises ValueError: If start rate is not in range.
393         """
394
395         if not self._rate_min <= float(start_rate) <= self._rate_max:
396             raise ValueError("Start rate is not in min,max range")
397
398         rate = float(start_rate)
399         # the last but one step
400         prev_rate = None
401
402         # linear search
403         while True:
404             res = []
405             for dummy in range(self._max_attempts):
406                 res.append(self.measure_loss(rate, self._frame_size,
407                                              self._loss_acceptance,
408                                              self._loss_acceptance_type,
409                                              traffic_type))
410
411             res = self._get_res_based_on_search_type(res)
412
413             if self._search_linear_direction == SearchDirection.BOTTOM_UP:
414                 # loss occurred and it was above acceptance criteria
415                 if not res:
416                     # if this is first run then we didn't find drop rate
417                     if prev_rate is None:
418                         self._search_result = SearchResults.FAILURE
419                         self._search_result_rate = None
420                     # else we found the rate, which is value from previous run
421                     else:
422                         self._search_result = SearchResults.SUCCESS
423                         self._search_result_rate = prev_rate
424                     return
425                 # there was no loss / loss below acceptance criteria
426                 elif res:
427                     prev_rate = rate
428                     rate += self._rate_linear_step
429                     if rate > self._rate_max:
430                         if prev_rate != self._rate_max:
431                             # one last step with rate set to _rate_max
432                             rate = self._rate_max
433                             continue
434                         else:
435                             self._search_result = SearchResults.SUCCESS
436                             self._search_result_rate = prev_rate
437                             return
438                     else:
439                         continue
440                 else:
441                     raise RuntimeError("Unknown search result")
442
443             elif self._search_linear_direction == SearchDirection.TOP_DOWN:
444                 # loss occurred, decrease rate
445                 if not res:
446                     prev_rate = rate
447                     rate -= self._rate_linear_step
448                     if rate < self._rate_min:
449                         if prev_rate != self._rate_min:
450                             # one last step with rate set to _rate_min
451                             rate = self._rate_min
452                             continue
453                         else:
454                             self._search_result = SearchResults.FAILURE
455                             self._search_result_rate = None
456                             return
457                     else:
458                         continue
459                 # no loss => non/partial drop rate found
460                 elif res:
461                     self._search_result = SearchResults.SUCCESS
462                     self._search_result_rate = rate
463                     return
464                 else:
465                     raise RuntimeError("Unknown search result")
466             else:
467                 raise Exception("Unknown search direction")
468
469         raise Exception("Wrong codepath")
470
471     def verify_search_result(self):
472         """Fail if search was not successful.
473
474         :returns: Result rate and latency stats.
475         :rtype: tuple
476         :raises Exception: If search failed.
477         """
478         if self._search_result == SearchResults.FAILURE:
479             raise Exception('Search FAILED')
480         elif self._search_result in [SearchResults.SUCCESS,
481                                      SearchResults.SUSPICIOUS]:
482             return self._search_result_rate, self.get_latency()
483
484     def binary_search(self, b_min, b_max, traffic_type, skip_max_rate=False,
485                       skip_warmup=False):
486         """Binary search of rate with loss below acceptance criteria.
487
488         :param b_min: Min range rate.
489         :param b_max: Max range rate.
490         :param traffic_type: Traffic profile.
491         :param skip_max_rate: Start with max rate first
492         :param skip_warmup: Start TRex without warmup traffic if true.
493         :type b_min: float
494         :type b_max: float
495         :type traffic_type: str
496         :type skip_max_rate: bool
497         :type skip_warmup: bool
498         :returns: nothing
499         :raises ValueError: If input values are not valid.
500         """
501
502         if not self._rate_min <= float(b_min) <= self._rate_max:
503             raise ValueError("Min rate is not in min,max range")
504         if not self._rate_min <= float(b_max) <= self._rate_max:
505             raise ValueError("Max rate is not in min,max range")
506         if float(b_max) < float(b_min):
507             raise ValueError("Min rate is greater than max rate")
508
509         # rate is half of interval + start of interval if not using max rate
510         rate = ((float(b_max) - float(b_min)) / 2) + float(b_min) \
511             if skip_max_rate else float(b_max)
512
513         # rate diff with previous run
514         rate_diff = abs(self._last_binary_rate - rate)
515
516         # convergence criterium
517         if float(rate_diff) < float(self._binary_convergence_threshold):
518             self._search_result = SearchResults.SUCCESS \
519                 if self._search_result_rate else SearchResults.FAILURE
520             return
521
522         self._last_binary_rate = rate
523
524         res = []
525         for dummy in range(self._max_attempts):
526             res.append(self.measure_loss(rate, self._frame_size,
527                                          self._loss_acceptance,
528                                          self._loss_acceptance_type,
529                                          traffic_type, skip_warmup=skip_warmup))
530
531         res = self._get_res_based_on_search_type(res)
532
533         # loss occurred and it was above acceptance criteria
534         if not res:
535             self.binary_search(b_min, rate, traffic_type, True, True)
536         # there was no loss / loss below acceptance criteria
537         else:
538             self._search_result_rate = rate
539             self.binary_search(rate, b_max, traffic_type, True, True)
540
541     def combined_search(self, start_rate, traffic_type):
542         """Combined search of rate with loss below acceptance criteria.
543
544         :param start_rate: Initial rate.
545         :param traffic_type: Traffic profile.
546         :type start_rate: float
547         :type traffic_type: str
548         :returns: nothing
549         :raises RuntimeError: If linear search failed.
550         """
551
552         self.linear_search(start_rate, traffic_type)
553
554         if self._search_result in [SearchResults.SUCCESS,
555                                    SearchResults.SUSPICIOUS]:
556             b_min = self._search_result_rate
557             b_max = self._search_result_rate + self._rate_linear_step
558
559             # we found max rate by linear search
560             if self.floats_are_close_equal(float(b_min), self._rate_max):
561                 return
562
563             # limiting binary range max value into max range
564             if float(b_max) > self._rate_max:
565                 b_max = self._rate_max
566
567             # reset result rate
568             temp_rate = self._search_result_rate
569             self._search_result_rate = None
570
571             # we will use binary search to refine search in one linear step
572             self.binary_search(b_min, b_max, traffic_type, True)
573
574             # linear and binary search succeed
575             if self._search_result == SearchResults.SUCCESS:
576                 return
577             # linear search succeed but binary failed or suspicious
578             else:
579                 self._search_result = SearchResults.SUSPICIOUS
580                 self._search_result_rate = temp_rate
581         else:
582             raise RuntimeError("Linear search FAILED")
583
584     @staticmethod
585     def floats_are_close_equal(num_a, num_b, rel_tol=1e-9, abs_tol=0.0):
586         """Compares two float numbers for close equality.
587
588         :param num_a: First number to compare.
589         :param num_b: Second number to compare.
590         :param rel_tol=1e-9: The relative tolerance.
591         :param abs_tol=0.0: The minimum absolute tolerance level.
592         :type num_a: float
593         :type num_b: float
594         :type rel_tol: float
595         :type abs_tol: float
596         :returns: Returns True if num_a is close in value to num_b or equal.
597                  False otherwise.
598         :rtype: boolean
599         :raises ValueError: If input values are not valid.
600         """
601
602         if num_a == num_b:
603             return True
604
605         if rel_tol < 0.0 or abs_tol < 0.0:
606             raise ValueError('Error tolerances must be non-negative')
607
608         return abs(num_b - num_a) <= max(rel_tol * max(abs(num_a), abs(num_b)),
609                                          abs_tol)

©2016 FD.io a Linux Foundation Collaborative Project. All Rights Reserved.
Linux Foundation is a registered trademark of The Linux Foundation. Linux is a registered trademark of Linus Torvalds.
Please see our privacy policy and terms of use.