resources/libraries/python/DropRateSearch.py

   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:
   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_profile, 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_profile: Module name to use for traffic generation.
 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_profile: str
 126         :type skip_warmup: 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_profile):
 385         """Linear search of rate with loss below acceptance criteria.
 386
 387         :param start_rate: Initial rate.
 388         :param traffic_profile: Module name to use for traffic generation.
 389         :type start_rate: float
 390         :type traffic_profile: 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(
 407                     rate, self._frame_size, self._loss_acceptance,
 408                     self._loss_acceptance_type, traffic_profile))
 409
 410             res = self._get_res_based_on_search_type(res)
 411
 412             if self._search_linear_direction == SearchDirection.TOP_DOWN:
 413                 # loss occurred, decrease rate
 414                 if not res:
 415                     prev_rate = rate
 416                     rate -= self._rate_linear_step
 417                     if rate < self._rate_min:
 418                         if prev_rate != self._rate_min:
 419                             # one last step with rate set to _rate_min
 420                             rate = self._rate_min
 421                             continue
 422                         else:
 423                             self._search_result = SearchResults.FAILURE
 424                             self._search_result_rate = None
 425                             return
 426                     else:
 427                         continue
 428                 # no loss => non/partial drop rate found
 429                 elif res:
 430                     self._search_result = SearchResults.SUCCESS
 431                     self._search_result_rate = rate
 432                     return
 433                 else:
 434                     raise RuntimeError("Unknown search result")
 435             else:
 436                 raise Exception("Unknown search direction")
 437
 438     def verify_search_result(self):
 439         """Fail if search was not successful.
 440
 441         :returns: Result rate and latency stats.
 442         :rtype: tuple
 443         :raises Exception: If search failed.
 444         """
 445         if self._search_result in [
 446                 SearchResults.SUCCESS, SearchResults.SUSPICIOUS]:
 447             return self._search_result_rate, self.get_latency()
 448         raise Exception('Search FAILED')
 449
 450     def binary_search(self, b_min, b_max, traffic_profile, skip_max_rate=False,
 451                       skip_warmup=False):
 452         """Binary search of rate with loss below acceptance criteria.
 453
 454         :param b_min: Min range rate.
 455         :param b_max: Max range rate.
 456         :param traffic_profile: Module name to use for traffic generation.
 457         :param skip_max_rate: Start with max rate first
 458         :param skip_warmup: Start TRex without warmup traffic if true.
 459         :type b_min: float
 460         :type b_max: float
 461         :type traffic_profile: str
 462         :type skip_max_rate: bool
 463         :type skip_warmup: bool
 464         :returns: nothing
 465         :raises ValueError: If input values are not valid.
 466         """
 467
 468         if not self._rate_min <= float(b_min) <= self._rate_max:
 469             raise ValueError("Min rate is not in min,max range")
 470         if not self._rate_min <= float(b_max) <= self._rate_max:
 471             raise ValueError("Max rate is not in min,max range")
 472         if float(b_max) < float(b_min):
 473             raise ValueError("Min rate is greater than max rate")
 474
 475         # rate is half of interval + start of interval if not using max rate
 476         rate = ((float(b_max) - float(b_min)) / 2) + float(b_min) \
 477             if skip_max_rate else float(b_max)
 478
 479         # rate diff with previous run
 480         rate_diff = abs(self._last_binary_rate - rate)
 481
 482         # convergence criterium
 483         if float(rate_diff) < float(self._binary_convergence_threshold):
 484             self._search_result = SearchResults.SUCCESS \
 485                 if self._search_result_rate else SearchResults.FAILURE
 486             return
 487
 488         self._last_binary_rate = rate
 489
 490         res = []
 491         for dummy in range(self._max_attempts):
 492             res.append(self.measure_loss(
 493                 rate, self._frame_size, self._loss_acceptance,
 494                 self._loss_acceptance_type, traffic_profile,
 495                 skip_warmup=skip_warmup))
 496
 497         res = self._get_res_based_on_search_type(res)
 498
 499         # loss occurred and it was above acceptance criteria
 500         if not res:
 501             self.binary_search(b_min, rate, traffic_profile, True, True)
 502         # there was no loss / loss below acceptance criteria
 503         else:
 504             self._search_result_rate = rate
 505             self.binary_search(rate, b_max, traffic_profile, True, True)
 506
 507     def combined_search(self, start_rate, traffic_profile):
 508         """Combined search of rate with loss below acceptance criteria.
 509
 510         :param start_rate: Initial rate.
 511         :param traffic_profile: Module name to use for traffic generation.
 512         :type start_rate: float
 513         :type traffic_profile: str
 514         :returns: nothing
 515         :raises RuntimeError: If linear search failed.
 516         """
 517
 518         self.linear_search(start_rate, traffic_profile)
 519
 520         if self._search_result in [SearchResults.SUCCESS,
 521                                    SearchResults.SUSPICIOUS]:
 522             b_min = self._search_result_rate
 523             b_max = self._search_result_rate + self._rate_linear_step
 524
 525             # we found max rate by linear search
 526             if self.floats_are_close_equal(float(b_min), self._rate_max):
 527                 return
 528
 529             # limiting binary range max value into max range
 530             if float(b_max) > self._rate_max:
 531                 b_max = self._rate_max
 532
 533             # reset result rate
 534             temp_rate = self._search_result_rate
 535             self._search_result_rate = None
 536
 537             # we will use binary search to refine search in one linear step
 538             self.binary_search(b_min, b_max, traffic_profile, True)
 539
 540             # linear and binary search succeed
 541             if self._search_result == SearchResults.SUCCESS:
 542                 return
 543             # linear search succeed but binary failed or suspicious
 544             else:
 545                 self._search_result = SearchResults.SUSPICIOUS
 546                 self._search_result_rate = temp_rate
 547         else:
 548             raise RuntimeError("Linear search FAILED")
 549
 550     @staticmethod
 551     def floats_are_close_equal(num_a, num_b, rel_tol=1e-9, abs_tol=0.0):
 552         """Compares two float numbers for close equality.
 553
 554         :param num_a: First number to compare.
 555         :param num_b: Second number to compare.
 556         :param rel_tol=1e-9: The relative tolerance.
 557         :param abs_tol=0.0: The minimum absolute tolerance level.
 558         :type num_a: float
 559         :type num_b: float
 560         :type rel_tol: float
 561         :type abs_tol: float
 562         :returns: Returns True if num_a is close in value to num_b or equal.
 563                  False otherwise.
 564         :rtype: boolean
 565         :raises ValueError: If input values are not valid.
 566         """
 567
 568         if num_a == num_b:
 569             return True
 570
 571         if rel_tol < 0.0 or abs_tol < 0.0:
 572             raise ValueError('Error tolerances must be non-negative')
 573
 574         return abs(num_b - num_a) <= max(rel_tol * max(abs(num_a), abs(num_b)),
 575                                          abs_tol)