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