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 @unique
  20 class SearchDirection(Enum):
  21     """Direction of linear search."""
  22
  23     TOP_DOWN = 1
  24     BOTTOM_UP = 2
  25
  26 @unique
  27 class SearchResults(Enum):
  28     """Result of the drop rate search."""
  29
  30     SUCCESS = 1
  31     FAILURE = 2
  32     SUSPICIOUS = 3
  33
  34 @unique
  35 class RateType(Enum):
  36     """Type of rate units."""
  37
  38     PERCENTAGE = 1
  39     PACKETS_PER_SECOND = 2
  40     BITS_PER_SECOND = 3
  41
  42 @unique
  43 class LossAcceptanceType(Enum):
  44     """Type of the loss acceptance criteria."""
  45
  46     FRAMES = 1
  47     PERCENTAGE = 2
  48
  49 @unique
  50 class SearchResultType(Enum):
  51     """Type of search result evaluation."""
  52
  53     BEST_OF_N = 1
  54     WORST_OF_N = 2
  55
  56 class DropRateSearch(object):
  57     """Abstract class with search algorithm implementation."""
  58
  59     __metaclass__ = ABCMeta
  60
  61     def __init__(self):
  62         #duration of traffic run (binary, linear)
  63         self._duration = 60
  64         #initial start rate (binary, linear)
  65         self._rate_start = 100
  66         #step of the linear search, unit: RateType (self._rate_type)
  67         self._rate_linear_step = 10
  68         #last rate of the binary search, unit: RateType (self._rate_type)
  69         self._last_binary_rate = 0
  70         #linear search direction, permitted values: SearchDirection
  71         self._search_linear_direction = SearchDirection.TOP_DOWN
  72         #upper limit of search, unit: RateType (self._rate_type)
  73         self._rate_max = 100
  74         #lower limit of search, unit: RateType (self._rate_type)
  75         self._rate_min = 1
  76         #permitted values: RateType
  77         self._rate_type = RateType.PERCENTAGE
  78         #accepted loss during search, units: LossAcceptanceType
  79         self._loss_acceptance = 0
  80         #permitted values: LossAcceptanceType
  81         self._loss_acceptance_type = LossAcceptanceType.FRAMES
  82         #size of frames to send
  83         self._frame_size = "64"
  84         #binary convergence criterium type is self._rate_type
  85         self._binary_convergence_threshold = 100000
  86         #numbers of traffic runs during one rate step
  87         self._max_attempts = 1
  88         #type of search result evaluation, unit: SearchResultType
  89         self._search_result_type = SearchResultType.BEST_OF_N
  90
  91         #result of search
  92         self._search_result = None
  93         self._search_result_rate = None
  94
  95     @abstractmethod
  96     def measure_loss(self, rate, frame_size, loss_acceptance,
  97                      loss_acceptance_type, traffic_type):
  98         """Send traffic from TG and measure count of dropped frames.
  99
 100         :param rate: offered traffic load
 101         :param frame_size: size of frame
 102         :param loss_acceptance: permitted drop ratio or frames count
 103         :param loss_acceptance_type: type of permitted loss
 104         :param traffic_type: traffic profile ([2,3]-node-L[2,3], ...)
 105         :type rate: int
 106         :type frame_size: str
 107         :type loss_acceptance: float
 108         :type loss_acceptance_type: LossAcceptanceType
 109         :type traffic_type: str
 110         :return: drop threshold exceeded? (True/False)
 111         :rtype bool
 112         """
 113         pass
 114
 115     def set_search_rate_boundaries(self, max_rate, min_rate):
 116         """Set search boundaries: min,max.
 117
 118         :param max_rate: upper value of search boundaries
 119         :param min_rate: lower value of search boundaries
 120         :type max_rate: float
 121         :type min_rate: float
 122         :return: nothing
 123         """
 124         if float(min_rate) <= 0:
 125             raise ValueError("min_rate must be higher than 0")
 126         elif float(min_rate) > float(max_rate):
 127             raise ValueError("min_rate must be lower than max_rate")
 128         else:
 129             self._rate_max = float(max_rate)
 130             self._rate_min = float(min_rate)
 131
 132     def set_search_linear_step(self, step_rate):
 133         """Set step size for linear search.
 134
 135         :param step_rate: linear search step size
 136         :type step_rate: float
 137         :return: nothing
 138         """
 139         self._rate_linear_step = float(step_rate)
 140
 141     def set_search_rate_type_percentage(self):
 142         """Set rate type to percentage of linerate.
 143
 144         :return: nothing
 145         """
 146         self._set_search_rate_type(RateType.PERCENTAGE)
 147
 148     def set_search_rate_type_bps(self):
 149         """Set rate type to bits per second.
 150
 151         :return: nothing
 152         """
 153         self._set_search_rate_type(RateType.BITS_PER_SECOND)
 154
 155     def set_search_rate_type_pps(self):
 156         """Set rate type to packets per second.
 157
 158         :return: nothing
 159         """
 160         self._set_search_rate_type(RateType.PACKETS_PER_SECOND)
 161
 162     def _set_search_rate_type(self, rate_type):
 163         """Set rate type to one of RateType-s.
 164
 165         :param rate_type: type of rate to set
 166         :type rate_type: RateType
 167         :return: nothing
 168         """
 169         if rate_type not in RateType:
 170             raise Exception("rate_type unknown: {}".format(rate_type))
 171         else:
 172             self._rate_type = rate_type
 173
 174     def set_search_frame_size(self, frame_size):
 175         """Set size of frames to send.
 176
 177         :param frame_size: size of frames
 178         :type frame_size: str
 179         :return: nothing
 180         """
 181         self._frame_size = frame_size
 182
 183     def set_duration(self, duration):
 184         """Set the duration of single traffic run.
 185
 186         :param duration: number of seconds for traffic to run
 187         :type duration: int
 188         :return: nothing
 189         """
 190         self._duration = int(duration)
 191
 192     def get_duration(self):
 193         """Return configured duration of single traffic run.
 194
 195         :return: number of seconds for traffic to run
 196         :rtype: int
 197         """
 198         return self._duration
 199
 200     def set_binary_convergence_threshold(self, convergence):
 201         """Set convergence for binary search.
 202
 203         :param convergence: treshold value number
 204         :type convergence: float
 205         :return: nothing
 206         """
 207         self._binary_convergence_threshold = float(convergence)
 208
 209     def get_binary_convergence_threshold(self):
 210         """Get convergence for binary search.
 211
 212         :return: treshold value number
 213         :rtype: float
 214         """
 215         return self._binary_convergence_threshold
 216
 217     def get_rate_type_str(self):
 218         """Return rate type representation.
 219
 220         :return: string representation of rate type
 221         :rtype: str
 222         """
 223         if self._rate_type == RateType.PERCENTAGE:
 224             return "%"
 225         elif self._rate_type == RateType.BITS_PER_SECOND:
 226             return "bps"
 227         elif self._rate_type == RateType.PACKETS_PER_SECOND:
 228             return "pps"
 229         else:
 230             raise ValueError("RateType unknown")
 231
 232     def set_max_attempts(self, max_attempts):
 233         """Set maximum number of traffic runs during one rate step.
 234
 235         :param max_attempts: number of traffic runs
 236         :type max_attempts: int
 237         :return: nothing
 238         """
 239         if int(max_attempts) > 0:
 240             self._max_attempts = int(max_attempts)
 241         else:
 242             raise ValueError("Max attempt must by greater then zero")
 243
 244     def get_max_attempts(self):
 245         """Return maximum number of traffic runs during one rate step.
 246
 247         :return: number of traffic runs
 248         :rtype: int
 249         """
 250         return self._max_attempts
 251
 252     def set_search_result_type_best_of_n(self):
 253         """Set type of search result evaluation to Best of N.
 254
 255         :return: nothing
 256         """
 257         self._set_search_result_type(SearchResultType.BEST_OF_N)
 258
 259     def set_search_result_type_worst_of_n(self):
 260         """Set type of search result evaluation to Worst of N.
 261
 262         :return: nothing
 263         """
 264         self._set_search_result_type(SearchResultType.WORST_OF_N)
 265
 266     def _set_search_result_type(self, search_type):
 267         """Set type of search result evaluation to one of SearchResultType.
 268
 269         :param search_type: type of search result evaluation to set
 270         :type search_type: SearchResultType
 271         :return: nothing
 272         """
 273         if search_type not in SearchResultType:
 274             raise ValueError("search_type unknown: {}".format(search_type))
 275         else:
 276             self._search_result_type = search_type
 277
 278     def _get_best_of_n(self, res_list):
 279         """Return best result of N traffic runs.
 280
 281         :param res_list: list of return values from all runs at one rate step
 282         :type res_list: list
 283         :return: True if at least one run is True, False otherwise
 284         :rtype: boolean
 285         """
 286         #Return True if any element of the iterable is True.
 287         return any(res_list)
 288
 289     def _get_worst_of_n(self, res_list):
 290         """Return worst result of N traffic runs.
 291
 292         :param res_list: list of return values from all runs at one rate step
 293         :type res_list: list
 294         :return: False if at least one run is False, True otherwise
 295         :rtype: boolean
 296         """
 297         #Return False if not all elements of the iterable are True.
 298         return not all(res_list)
 299
 300     def _get_result_based_on_search_type(self, res_list):
 301         """Return result of search based on search evaluation type.
 302
 303         :param res_list: list of return values from all runs at one rate step
 304         :type res_list: list
 305         :return: Boolean based on search result type
 306         :rtype: boolean
 307         """
 308         if self._search_result_type == SearchResultType.BEST_OF_N:
 309             return self._get_best_of_n(res_list)
 310         elif self._search_result_type == SearchResultType.WORST_OF_N:
 311             return self._get_worst_of_n(res_list)
 312         else:
 313             raise ValueError("Unknown search result type")
 314
 315
 316     def linear_search(self, start_rate, traffic_type):
 317         """Linear search of rate with loss below acceptance criteria.
 318
 319         :param start_rate: initial rate
 320         :param traffic_type: traffic profile
 321         :type start_rate: float
 322         :param traffic_type: str
 323         :return: nothing
 324         """
 325
 326         if not self._rate_min <= float(start_rate) <= self._rate_max:
 327             raise ValueError("Start rate is not in min,max range")
 328
 329         rate = float(start_rate)
 330         #the last but one step
 331         prev_rate = None
 332
 333         #linear search
 334         while True:
 335             res = []
 336             for n in range(self._max_attempts):
 337                 res.append(self.measure_loss(rate, self._frame_size,
 338                                              self._loss_acceptance,
 339                                              self._loss_acceptance_type,
 340                                              traffic_type))
 341
 342             res = self._get_result_based_on_search_type(res)
 343
 344             if self._search_linear_direction == SearchDirection.BOTTOM_UP:
 345                 #loss occured and it was above acceptance criteria
 346                 if res == False:
 347                     #if this is first run then we didn't find drop rate
 348                     if prev_rate == None:
 349                         self._search_result = SearchResults.FAILURE
 350                         self._search_result_rate = None
 351                         return
 352                     # else we found the rate, which is value from previous run
 353                     else:
 354                         self._search_result = SearchResults.SUCCESS
 355                         self._search_result_rate = prev_rate
 356                         return
 357                 #there was no loss / loss below acceptance criteria
 358                 elif res == True:
 359                     prev_rate = rate
 360                     rate += self._rate_linear_step
 361                     if rate > self._rate_max:
 362                         if prev_rate != self._rate_max:
 363                             #one last step with rate set to _rate_max
 364                             rate = self._rate_max
 365                             continue
 366                         else:
 367                             self._search_result = SearchResults.SUCCESS
 368                             self._search_result_rate = prev_rate
 369                             return
 370                     else:
 371                         continue
 372                 else:
 373                     raise RuntimeError("Unknown search result")
 374
 375             elif self._search_linear_direction == SearchDirection.TOP_DOWN:
 376                 #loss occured, decrease rate
 377                 if res == False:
 378                     prev_rate = rate
 379                     rate -= self._rate_linear_step
 380                     if rate < self._rate_min:
 381                         if prev_rate != self._rate_min:
 382                             #one last step with rate set to _rate_min
 383                             rate = self._rate_min
 384                             continue
 385                         else:
 386                             self._search_result = SearchResults.FAILURE
 387                             self._search_result_rate = None
 388                             return
 389                     else:
 390                         continue
 391                 #no loss => non/partial drop rate found
 392                 elif res == True:
 393                     self._search_result = SearchResults.SUCCESS
 394                     self._search_result_rate = rate
 395                     return
 396                 else:
 397                     raise RuntimeError("Unknown search result")
 398             else:
 399                 raise Exception("Unknown search direction")
 400
 401         raise Exception("Wrong codepath")
 402
 403     def verify_search_result(self):
 404         """Fail if search was not successful.
 405
 406         :return: result rate
 407         :rtype: float
 408         """
 409         if self._search_result == SearchResults.FAILURE:
 410             raise Exception('Search FAILED')
 411         elif self._search_result in [SearchResults.SUCCESS, SearchResults.SUSPICIOUS]:
 412             return self._search_result_rate
 413
 414     def binary_search(self, b_min, b_max, traffic_type):
 415         """Binary search of rate with loss below acceptance criteria.
 416
 417         :param b_min: min range rate
 418         :param b_max: max range rate
 419         :param traffic_type: traffic profile
 420         :type b_min: float
 421         :type b_max: float
 422         :type traffic_type: str
 423         :return: nothing
 424         """
 425
 426         if not self._rate_min <= float(b_min) <= self._rate_max:
 427             raise ValueError("Min rate is not in min,max range")
 428         if not self._rate_min <= float(b_max) <= self._rate_max:
 429             raise ValueError("Max rate is not in min,max range")
 430         if float(b_max) < float(b_min):
 431             raise ValueError("Min rate is greater then max rate")
 432
 433         #binary search
 434         #rate is half of interval + start of interval
 435         rate = ((float(b_max) - float(b_min)) / 2) + float(b_min)
 436         #rate diff with previous run
 437         rate_diff = abs(self._last_binary_rate - rate)
 438
 439         #convergence criterium
 440         if float(rate_diff) < float(self._binary_convergence_threshold):
 441             if not self._search_result_rate:
 442                 self._search_result = SearchResults.FAILURE
 443             else:
 444                 self._search_result = SearchResults.SUCCESS
 445             return
 446
 447         self._last_binary_rate = rate
 448
 449         res = []
 450         for n in range(self._max_attempts):
 451             res.append(self.measure_loss(rate, self._frame_size,
 452                                          self._loss_acceptance,
 453                                          self._loss_acceptance_type,
 454                                          traffic_type))
 455
 456         res = self._get_result_based_on_search_type(res)
 457
 458         #loss occured and it was above acceptance criteria
 459         if res == False:
 460             self.binary_search(b_min, rate, traffic_type)
 461         #there was no loss / loss below acceptance criteria
 462         elif res == True:
 463             self._search_result_rate = rate
 464             self.binary_search(rate, b_max, traffic_type)
 465         else:
 466             raise RuntimeError("Unknown search result")
 467
 468     def combined_search(self):
 469         raise NotImplementedError