resources/libraries/python/DropRateSearch.py

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