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     def linear_search(self, start_rate, traffic_type):
 324         """Linear search of rate with loss below acceptance criteria.
 325
 326         :param start_rate: Initial rate.
 327         :param traffic_type: Traffic profile.
 328         :type start_rate: float
 329         :type traffic_type: str
 330         :return: nothing
 331         """
 332
 333         if not self._rate_min <= float(start_rate) <= self._rate_max:
 334             raise ValueError("Start rate is not in min,max range")
 335
 336         rate = float(start_rate)
 337         # the last but one step
 338         prev_rate = None
 339
 340         # linear search
 341         while True:
 342             res = []
 343             for dummy in range(self._max_attempts):
 344                 res.append(self.measure_loss(rate, self._frame_size,
 345                                              self._loss_acceptance,
 346                                              self._loss_acceptance_type,
 347                                              traffic_type))
 348
 349             res = self._get_res_based_on_search_type(res)
 350
 351             if self._search_linear_direction == SearchDirection.BOTTOM_UP:
 352                 # loss occurred and it was above acceptance criteria
 353                 if not res:
 354                     # if this is first run then we didn't find drop rate
 355                     if prev_rate is None:
 356                         self._search_result = SearchResults.FAILURE
 357                         self._search_result_rate = None
 358                         return
 359                     # else we found the rate, which is value from previous run
 360                     else:
 361                         self._search_result = SearchResults.SUCCESS
 362                         self._search_result_rate = prev_rate
 363                         return
 364                 # there was no loss / loss below acceptance criteria
 365                 elif res:
 366                     prev_rate = rate
 367                     rate += self._rate_linear_step
 368                     if rate > self._rate_max:
 369                         if prev_rate != self._rate_max:
 370                             # one last step with rate set to _rate_max
 371                             rate = self._rate_max
 372                             continue
 373                         else:
 374                             self._search_result = SearchResults.SUCCESS
 375                             self._search_result_rate = prev_rate
 376                             return
 377                     else:
 378                         continue
 379                 else:
 380                     raise RuntimeError("Unknown search result")
 381
 382             elif self._search_linear_direction == SearchDirection.TOP_DOWN:
 383                 # loss occurred, decrease rate
 384                 if not res:
 385                     prev_rate = rate
 386                     rate -= self._rate_linear_step
 387                     if rate < self._rate_min:
 388                         if prev_rate != self._rate_min:
 389                             # one last step with rate set to _rate_min
 390                             rate = self._rate_min
 391                             continue
 392                         else:
 393                             self._search_result = SearchResults.FAILURE
 394                             self._search_result_rate = None
 395                             return
 396                     else:
 397                         continue
 398                 # no loss => non/partial drop rate found
 399                 elif res:
 400                     self._search_result = SearchResults.SUCCESS
 401                     self._search_result_rate = rate
 402                     return
 403                 else:
 404                     raise RuntimeError("Unknown search result")
 405             else:
 406                 raise Exception("Unknown search direction")
 407
 408         raise Exception("Wrong codepath")
 409
 410     def verify_search_result(self):
 411         """Fail if search was not successful.
 412
 413         :return: Result rate.
 414         :rtype: float
 415         """
 416         if self._search_result == SearchResults.FAILURE:
 417             raise Exception('Search FAILED')
 418         elif self._search_result in [SearchResults.SUCCESS,
 419                                      SearchResults.SUSPICIOUS]:
 420             return self._search_result_rate
 421
 422     def binary_search(self, b_min, b_max, traffic_type, skip_max_rate=False):
 423         """Binary search of rate with loss below acceptance criteria.
 424
 425         :param b_min: Min range rate.
 426         :param b_max: Max range rate.
 427         :param traffic_type: Traffic profile.
 428         :param skip_max_rate: Start with max rate first
 429         :type b_min: float
 430         :type b_max: float
 431         :type traffic_type: str
 432         :type skip_max_rate: bool
 433         :return: nothing
 434         """
 435
 436         if not self._rate_min <= float(b_min) <= self._rate_max:
 437             raise ValueError("Min rate is not in min,max range")
 438         if not self._rate_min <= float(b_max) <= self._rate_max:
 439             raise ValueError("Max rate is not in min,max range")
 440         if float(b_max) < float(b_min):
 441             raise ValueError("Min rate is greater than max rate")
 442
 443         # binary search
 444         if skip_max_rate:
 445             # rate is half of interval + start of interval
 446             rate = ((float(b_max) - float(b_min)) / 2) + float(b_min)
 447         else:
 448             # rate is max of interval
 449             rate =  float(b_max)
 450         # rate diff with previous run
 451         rate_diff = abs(self._last_binary_rate - rate)
 452
 453         # convergence criterium
 454         if float(rate_diff) < float(self._binary_convergence_threshold):
 455             if not self._search_result_rate:
 456                 self._search_result = SearchResults.FAILURE
 457             else:
 458                 self._search_result = SearchResults.SUCCESS
 459             return
 460
 461         self._last_binary_rate = rate
 462
 463         res = []
 464         for dummy in range(self._max_attempts):
 465             res.append(self.measure_loss(rate, self._frame_size,
 466                                          self._loss_acceptance,
 467                                          self._loss_acceptance_type,
 468                                          traffic_type))
 469
 470         res = self._get_res_based_on_search_type(res)
 471
 472         # loss occurred and it was above acceptance criteria
 473         if not res:
 474             self.binary_search(b_min, rate, traffic_type, True)
 475         # there was no loss / loss below acceptance criteria
 476         else:
 477             self._search_result_rate = rate
 478             self.binary_search(rate, b_max, traffic_type, True)
 479
 480     def combined_search(self, start_rate, traffic_type):
 481         """Combined search of rate with loss below acceptance criteria.
 482
 483         :param start_rate: Initial rate.
 484         :param traffic_type: Traffic profile.
 485         :type start_rate: float
 486         :type traffic_type: str
 487         :return: nothing
 488         """
 489
 490         self.linear_search(start_rate, traffic_type)
 491
 492         if self._search_result in [SearchResults.SUCCESS,
 493                                    SearchResults.SUSPICIOUS]:
 494             b_min = self._search_result_rate
 495             b_max = self._search_result_rate + self._rate_linear_step
 496
 497             # we found max rate by linear search
 498             if self.floats_are_close_equal(float(b_min), self._rate_max):
 499                 return
 500
 501             # limiting binary range max value into max range
 502             if float(b_max) > self._rate_max:
 503                 b_max = self._rate_max
 504
 505             # reset result rate
 506             temp_rate = self._search_result_rate
 507             self._search_result_rate = None
 508
 509             # we will use binary search to refine search in one linear step
 510             self.binary_search(b_min, b_max, traffic_type, True)
 511
 512             # linear and binary search succeed
 513             if self._search_result == SearchResults.SUCCESS:
 514                 return
 515             # linear search succeed but binary failed or suspicious
 516             else:
 517                 self._search_result = SearchResults.SUSPICIOUS
 518                 self._search_result_rate = temp_rate
 519         else:
 520             raise RuntimeError("Linear search FAILED")
 521
 522     @staticmethod
 523     def floats_are_close_equal(num_a, num_b, rel_tol=1e-9, abs_tol=0.0):
 524         """Compares two float numbers for close equality.
 525
 526         :param num_a: First number to compare.
 527         :param num_b: Second number to compare.
 528         :param rel_tol=1e-9: The relative tolerance.
 529         :param abs_tol=0.0: The minimum absolute tolerance level.
 530         :type num_a: float
 531         :type num_b: float
 532         :type rel_tol: float
 533         :type abs_tol: float
 534         :return: Returns True if num_a is close in value to num_b or equal.
 535                  False otherwise.
 536         :rtype: boolean
 537         """
 538
 539         if num_a == num_b:
 540             return True
 541
 542         if rel_tol < 0.0 or abs_tol < 0.0:
 543             raise ValueError('Error tolerances must be non-negative')
 544
 545         return abs(num_b - num_a) <= max(rel_tol * max(abs(num_a), abs(num_b)),
 546                                          abs_tol)
 547