resources/libraries/python/DropRateSearch.py

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