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)