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