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     #TODO DropRateSearch should be refactored as part of CSIT-1378
  65     #pylint: disable=too-many-instance-attributes
  66
  67     __metaclass__ = ABCMeta
  68
  69     def __init__(self):
  70         # duration of traffic run (binary, linear)
  71         self._duration = 60
  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)
  81         self._rate_max = 100
  82         # lower limit of search, unit: RateType (self._rate_type)
  83         self._rate_min = 1
  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
  98
  99         # result of search
 100         self._search_result = None
 101         self._search_result_rate = None
 102
 103     @abstractmethod
 104     def get_latency(self):
 105         """Return min/avg/max latency.
 106
 107         :returns: Latency stats.
 108         :rtype: list
 109         """
 110         pass
 111
 112     @abstractmethod
 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.
 116
 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.
 123         :type rate: int
 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)
 130         :rtype: bool
 131         """
 132         pass
 133
 134     def set_search_rate_boundaries(self, max_rate, min_rate):
 135         """Set search boundaries: min,max.
 136
 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
 141         :returns: nothing
 142         :raises ValueError: If min rate is lower than 0 or higher than max rate.
 143         """
 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")
 148         else:
 149             self._rate_max = float(max_rate)
 150             self._rate_min = float(min_rate)
 151
 152     def set_loss_acceptance(self, loss_acceptance):
 153         """Set loss acceptance treshold for PDR search.
 154
 155         :param loss_acceptance: Loss acceptance treshold for PDR search.
 156         :type loss_acceptance: str
 157         :returns: nothing
 158         :raises ValueError: If loss acceptance is lower than zero.
 159         """
 160         if float(loss_acceptance) < 0:
 161             raise ValueError("Loss acceptance must be higher or equal 0")
 162         else:
 163             self._loss_acceptance = float(loss_acceptance)
 164
 165     def get_loss_acceptance(self):
 166         """Return configured loss acceptance treshold.
 167
 168         :returns: Loss acceptance treshold.
 169         :rtype: float
 170         """
 171         return self._loss_acceptance
 172
 173     def set_loss_acceptance_type_percentage(self):
 174         """Set loss acceptance treshold type to percentage.
 175
 176         :returns: nothing
 177         """
 178         self._loss_acceptance_type = LossAcceptanceType.PERCENTAGE
 179
 180     def set_loss_acceptance_type_frames(self):
 181         """Set loss acceptance treshold type to frames.
 182
 183         :returns: nothing
 184         """
 185         self._loss_acceptance_type = LossAcceptanceType.FRAMES
 186
 187     def loss_acceptance_type_is_percentage(self):
 188         """Return true if loss acceptance treshold type is percentage,
 189            false otherwise.
 190
 191         :returns: True if loss acceptance treshold type is percentage.
 192         :rtype: boolean
 193         """
 194         return self._loss_acceptance_type == LossAcceptanceType.PERCENTAGE
 195
 196     def set_search_linear_step(self, step_rate):
 197         """Set step size for linear search.
 198
 199         :param step_rate: Linear search step size.
 200         :type step_rate: float
 201         :returns: nothing
 202         """
 203         self._rate_linear_step = float(step_rate)
 204
 205     def set_search_rate_type_percentage(self):
 206         """Set rate type to percentage of linerate.
 207
 208         :returns: nothing
 209         """
 210         self._set_search_rate_type(RateType.PERCENTAGE)
 211
 212     def set_search_rate_type_bps(self):
 213         """Set rate type to bits per second.
 214
 215         :returns: nothing
 216         """
 217         self._set_search_rate_type(RateType.BITS_PER_SECOND)
 218
 219     def set_search_rate_type_pps(self):
 220         """Set rate type to packets per second.
 221
 222         :returns: nothing
 223         """
 224         self._set_search_rate_type(RateType.PACKETS_PER_SECOND)
 225
 226     def _set_search_rate_type(self, rate_type):
 227         """Set rate type to one of RateType-s.
 228
 229         :param rate_type: Type of rate to set.
 230         :type rate_type: RateType
 231         :returns: nothing
 232         :raises Exception: If rate type is unknown.
 233         """
 234         if rate_type not in RateType:
 235             raise Exception("rate_type unknown: {}".format(rate_type))
 236         else:
 237             self._rate_type = rate_type
 238
 239     def set_search_frame_size(self, frame_size):
 240         """Set size of frames to send.
 241
 242         :param frame_size: Size of frames.
 243         :type frame_size: str
 244         :returns: nothing
 245         """
 246         self._frame_size = frame_size
 247
 248     def set_duration(self, duration):
 249         """Set the duration of single traffic run.
 250
 251         :param duration: Number of seconds for traffic to run.
 252         :type duration: int
 253         :returns: nothing
 254         """
 255         self._duration = int(duration)
 256
 257     def get_duration(self):
 258         """Return configured duration of single traffic run.
 259
 260         :returns: Number of seconds for traffic to run.
 261         :rtype: int
 262         """
 263         return self._duration
 264
 265     def set_binary_convergence_threshold(self, convergence):
 266         """Set convergence for binary search.
 267
 268         :param convergence: Treshold value number.
 269         :type convergence: float
 270         :returns: nothing
 271         """
 272         self._binary_convergence_threshold = float(convergence)
 273
 274     def get_binary_convergence_threshold(self):
 275         """Get convergence for binary search.
 276
 277         :returns: Treshold value number.
 278         :rtype: float
 279         """
 280         return self._binary_convergence_threshold
 281
 282     def get_rate_type_str(self):
 283         """Return rate type representation.
 284
 285         :returns: String representation of rate type.
 286         :rtype: str
 287         :raises ValueError: If rate type is unknown.
 288         """
 289         if self._rate_type == RateType.PERCENTAGE:
 290             return "%"
 291         elif self._rate_type == RateType.BITS_PER_SECOND:
 292             return "bps"
 293         elif self._rate_type == RateType.PACKETS_PER_SECOND:
 294             return "pps"
 295         else:
 296             raise ValueError("RateType unknown")
 297
 298     def set_max_attempts(self, max_attempts):
 299         """Set maximum number of traffic runs during one rate step.
 300
 301         :param max_attempts: Number of traffic runs.
 302         :type max_attempts: int
 303         :returns: nothing
 304         :raises ValueError: If max attempts is lower than zero.
 305         """
 306         if int(max_attempts) > 0:
 307             self._max_attempts = int(max_attempts)
 308         else:
 309             raise ValueError("Max attempt must by greater than zero")
 310
 311     def get_max_attempts(self):
 312         """Return maximum number of traffic runs during one rate step.
 313
 314         :returns: Number of traffic runs.
 315         :rtype: int
 316         """
 317         return self._max_attempts
 318
 319     def set_search_result_type_best_of_n(self):
 320         """Set type of search result evaluation to Best of N.
 321
 322         :returns: nothing
 323         """
 324         self._set_search_result_type(SearchResultType.BEST_OF_N)
 325
 326     def set_search_result_type_worst_of_n(self):
 327         """Set type of search result evaluation to Worst of N.
 328
 329         :returns: nothing
 330         """
 331         self._set_search_result_type(SearchResultType.WORST_OF_N)
 332
 333     def _set_search_result_type(self, search_type):
 334         """Set type of search result evaluation to one of SearchResultType.
 335
 336         :param search_type: Type of search result evaluation to set.
 337         :type search_type: SearchResultType
 338         :returns: nothing
 339         :raises ValueError: If search type is unknown.
 340         """
 341         if search_type not in SearchResultType:
 342             raise ValueError("search_type unknown: {}".format(search_type))
 343         else:
 344             self._search_result_type = search_type
 345
 346     @staticmethod
 347     def _get_best_of_n(res_list):
 348         """Return best result of N traffic runs.
 349
 350         :param res_list: List of return values from all runs at one rate step.
 351         :type res_list: list
 352         :returns: True if at least one run is True, False otherwise.
 353         :rtype: boolean
 354         """
 355         # Return True if any element of the iterable is True.
 356         return any(res_list)
 357
 358     @staticmethod
 359     def _get_worst_of_n(res_list):
 360         """Return worst result of N traffic runs.
 361
 362         :param res_list: List of return values from all runs at one rate step.
 363         :type res_list: list
 364         :returns: False if at least one run is False, True otherwise.
 365         :rtype: boolean
 366         """
 367         # Return False if not all elements of the iterable are True.
 368         return all(res_list)
 369
 370     def _get_res_based_on_search_type(self, res_list):
 371         """Return result of search based on search evaluation type.
 372
 373         :param res_list: List of return values from all runs at one rate step.
 374         :type res_list: list
 375         :returns: Boolean based on search result type.
 376         :rtype: boolean
 377         :raises ValueError: If search result type is unknown.
 378         """
 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)
 383         else:
 384             raise ValueError("Unknown search result type")
 385
 386     def linear_search(self, start_rate, traffic_profile):
 387         """Linear search of rate with loss below acceptance criteria.
 388
 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
 393         :returns: nothing
 394         :raises ValueError: If start rate is not in range.
 395         """
 396
 397         if not self._rate_min <= float(start_rate) <= self._rate_max:
 398             raise ValueError("Start rate is not in min,max range")
 399
 400         rate = float(start_rate)
 401         # the last but one step
 402         prev_rate = None
 403
 404         # linear search
 405         while True:
 406             res = []
 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))
 411
 412             res = self._get_res_based_on_search_type(res)
 413
 414             if self._search_linear_direction == SearchDirection.TOP_DOWN:
 415                 # loss occurred, decrease rate
 416                 if not res:
 417                     prev_rate = 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
 423                             continue
 424                         else:
 425                             self._search_result = SearchResults.FAILURE
 426                             self._search_result_rate = None
 427                             return
 428                     else:
 429                         continue
 430                 # no loss => non/partial drop rate found
 431                 elif res:
 432                     self._search_result = SearchResults.SUCCESS
 433                     self._search_result_rate = rate
 434                     return
 435                 else:
 436                     raise RuntimeError("Unknown search result")
 437             else:
 438                 raise Exception("Unknown search direction")
 439
 440     def verify_search_result(self):
 441         """Fail if search was not successful.
 442
 443         :returns: Result rate and latency stats.
 444         :rtype: tuple
 445         :raises Exception: If search failed.
 446         """
 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')
 451
 452     def binary_search(self, b_min, b_max, traffic_profile, skip_max_rate=False,
 453                       skip_warmup=False):
 454         """Binary search of rate with loss below acceptance criteria.
 455
 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.
 461         :type b_min: float
 462         :type b_max: float
 463         :type traffic_profile: str
 464         :type skip_max_rate: bool
 465         :type skip_warmup: bool
 466         :returns: nothing
 467         :raises ValueError: If input values are not valid.
 468         """
 469
 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")
 476
 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)
 480
 481         # rate diff with previous run
 482         rate_diff = abs(self._last_binary_rate - rate)
 483
 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
 488             return
 489
 490         self._last_binary_rate = rate
 491
 492         res = []
 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))
 498
 499         res = self._get_res_based_on_search_type(res)
 500
 501         # loss occurred and it was above acceptance criteria
 502         if not res:
 503             self.binary_search(b_min, rate, traffic_profile, True, True)
 504         # there was no loss / loss below acceptance criteria
 505         else:
 506             self._search_result_rate = rate
 507             self.binary_search(rate, b_max, traffic_profile, True, True)
 508
 509     def combined_search(self, start_rate, traffic_profile):
 510         """Combined search of rate with loss below acceptance criteria.
 511
 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
 516         :returns: nothing
 517         :raises RuntimeError: If linear search failed.
 518         """
 519
 520         self.linear_search(start_rate, traffic_profile)
 521
 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
 526
 527             # we found max rate by linear search
 528             if self.floats_are_close_equal(float(b_min), self._rate_max):
 529                 return
 530
 531             # limiting binary range max value into max range
 532             if float(b_max) > self._rate_max:
 533                 b_max = self._rate_max
 534
 535             # reset result rate
 536             temp_rate = self._search_result_rate
 537             self._search_result_rate = None
 538
 539             # we will use binary search to refine search in one linear step
 540             self.binary_search(b_min, b_max, traffic_profile, True)
 541
 542             # linear and binary search succeed
 543             if self._search_result == SearchResults.SUCCESS:
 544                 return
 545             # linear search succeed but binary failed or suspicious
 546             else:
 547                 self._search_result = SearchResults.SUSPICIOUS
 548                 self._search_result_rate = temp_rate
 549         else:
 550             raise RuntimeError("Linear search FAILED")
 551
 552     @staticmethod
 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.
 555
 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.
 560         :type num_a: float
 561         :type num_b: float
 562         :type rel_tol: float
 563         :type abs_tol: float
 564         :returns: Returns True if num_a is close in value to num_b or equal.
 565                  False otherwise.
 566         :rtype: boolean
 567         :raises ValueError: If input values are not valid.
 568         """
 569
 570         if num_a == num_b:
 571             return True
 572
 573         if rel_tol < 0.0 or abs_tol < 0.0:
 574             raise ValueError('Error tolerances must be non-negative')
 575
 576         return abs(num_b - num_a) <= max(rel_tol * max(abs(num_a), abs(num_b)),
 577                                          abs_tol)