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