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 class DropRateSearch(object):
  50     """Abstract class with search algorithm implementation"""
  51
  52     __metaclass__ = ABCMeta
  53
  54     def __init__(self):
  55         #duration of traffic run (binary, linear)
  56         self._duration = 60
  57         #initial start rate (binary, linear)
  58         self._rate_start = 100
  59         #step of the linear search, unit: RateType (self._rate_type)
  60         self._rate_linear_step = 10
  61         #last rate of the binary search, unit: RateType (self._rate_type)
  62         self._last_binary_rate = 0
  63         #linear search direction, permitted values: SearchDirection
  64         self._search_linear_direction = SearchDirection.TOP_DOWN
  65         #upper limit of search, unit: RateType (self._rate_type)
  66         self._rate_max = 100
  67         #lower limit of search, unit: RateType (self._rate_type)
  68         self._rate_min = 1
  69         #permitted values: RateType
  70         self._rate_type = RateType.PERCENTAGE
  71         #accepted loss during search, units: LossAcceptanceType
  72         self._loss_acceptance = 0
  73         #permitted values: LossAcceptanceType
  74         self._loss_acceptance_type = LossAcceptanceType.FRAMES
  75         #size of frames to send
  76         self._frame_size = "64"
  77         #binary convergence criterium type is self._rate_type
  78         self._binary_convergence_threshold = 100000
  79         #numbers of traffic runs during one rate step
  80         self._max_attempts = 1
  81
  82         #result of search
  83         self._search_result = None
  84         self._search_result_rate = None
  85
  86     @abstractmethod
  87     def measure_loss(self, rate, frame_size, loss_acceptance,
  88                      loss_acceptance_type, traffic_type):
  89         """Send traffic from TG and measure count of dropped frames
  90
  91         :param rate: offered traffic load
  92         :param frame_size: size of frame
  93         :param loss_acceptance: permitted drop ratio or frames count
  94         :param loss_acceptance_type: type of permitted loss
  95         :param traffic_type: traffic profile ([2,3]-node-L[2,3], ...)
  96         :type rate: int
  97         :type frame_size: str
  98         :type loss_acceptance: float
  99         :type loss_acceptance_type: LossAcceptanceType
 100         :type traffic_type: str
 101         :return: drop threshold exceeded? (True/False)
 102         :rtype bool
 103         """
 104         pass
 105
 106     def set_search_rate_boundaries(self, max_rate, min_rate):
 107         """Set search boundaries: min,max
 108
 109         :param max_rate: upper value of search boundaries
 110         :param min_rate: lower value of search boundaries
 111         :type max_rate: float
 112         :type min_rate: float
 113         :return: nothing
 114         """
 115         if float(min_rate) <= 0:
 116             raise ValueError("min_rate must be higher than 0")
 117         elif float(min_rate) > float(max_rate):
 118             raise ValueError("min_rate must be lower than max_rate")
 119         else:
 120             self._rate_max = float(max_rate)
 121             self._rate_min = float(min_rate)
 122
 123     def set_search_linear_step(self, step_rate):
 124         """Set step size for linear search
 125
 126         :param step_rate: linear search step size
 127         :type step_rate: float
 128         :return: nothing
 129         """
 130         self._rate_linear_step = float(step_rate)
 131
 132     def set_search_rate_type_percentage(self):
 133         """Set rate type to percentage of linerate
 134
 135         :return: nothing
 136         """
 137         self._set_search_rate_type(RateType.PERCENTAGE)
 138
 139     def set_search_rate_type_bps(self):
 140         """Set rate type to bits per second
 141
 142         :return: nothing
 143         """
 144         self._set_search_rate_type(RateType.BITS_PER_SECOND)
 145
 146     def set_search_rate_type_pps(self):
 147         """Set rate type to packets per second
 148
 149         :return: nothing
 150         """
 151         self._set_search_rate_type(RateType.PACKETS_PER_SECOND)
 152
 153     def _set_search_rate_type(self, rate_type):
 154         """Set rate type to one of RateType-s
 155
 156         :param rate_type: type of rate to set
 157         :type rate_type: RateType
 158         :return: nothing
 159         """
 160         if rate_type not in RateType:
 161             raise Exception("rate_type unknown: {}".format(rate_type))
 162         else:
 163             self._rate_type = rate_type
 164
 165     def set_search_frame_size(self, frame_size):
 166         """Set size of frames to send
 167
 168         :param frame_size: size of frames
 169         :type frame_size: str
 170         :return: nothing
 171         """
 172         self._frame_size = frame_size
 173
 174     def set_duration(self, duration):
 175         """Set the duration of single traffic run
 176
 177         :param duration: number of seconds for traffic to run
 178         :type duration: int
 179         :return: nothing
 180         """
 181         self._duration = int(duration)
 182
 183     def get_duration(self):
 184         """Return configured duration of single traffic run
 185
 186         :return: number of seconds for traffic to run
 187         :rtype: int
 188         """
 189         return self._duration
 190
 191     def set_binary_convergence_threshold(self, convergence):
 192         """Set convergence for binary search
 193
 194         :param convergence: treshold value number
 195         :type convergence: float
 196         :return: nothing
 197         """
 198         self._binary_convergence_threshold = float(convergence)
 199
 200     def get_binary_convergence_threshold(self):
 201         """Get convergence for binary search
 202
 203         :return: treshold value number
 204         :rtype: float
 205         """
 206         return self._binary_convergence_threshold
 207
 208     def get_rate_type_str(self):
 209         """Return rate type representation
 210
 211         :return: string representation of rate type
 212         :rtype: str
 213         """
 214         if self._rate_type == RateType.PERCENTAGE:
 215             return "%"
 216         elif self._rate_type == RateType.BITS_PER_SECOND:
 217             return "bps"
 218         elif self._rate_type == RateType.PACKETS_PER_SECOND:
 219             return "pps"
 220         else:
 221             raise ValueError("RateType unknown")
 222
 223     def linear_search(self, start_rate, traffic_type):
 224         """Linear search of rate with loss below acceptance criteria
 225
 226         :param start_rate: initial rate
 227         :param traffic_type: traffic profile
 228         :type start_rate: float
 229         :param traffic_type: str
 230         :return: nothing
 231         """
 232
 233         if not self._rate_min <= float(start_rate) <= self._rate_max:
 234             raise ValueError("Start rate is not in min,max range")
 235
 236         rate = float(start_rate)
 237         #the last but one step
 238         prev_rate = None
 239
 240         #linear search
 241         while True:
 242             res = self.measure_loss(rate, self._frame_size,
 243                                     self._loss_acceptance,
 244                                     self._loss_acceptance_type,
 245                                     traffic_type)
 246             if self._search_linear_direction == SearchDirection.BOTTOM_UP:
 247                 #loss occured and it was above acceptance criteria
 248                 if res == False:
 249                     #if this is first run then we didn't find drop rate
 250                     if prev_rate == None:
 251                         self._search_result = SearchResults.FAILURE
 252                         self._search_result_rate = None
 253                         return
 254                     # else we found the rate, which is value from previous run
 255                     else:
 256                         self._search_result = SearchResults.SUCCESS
 257                         self._search_result_rate = prev_rate
 258                         return
 259                 #there was no loss / loss below acceptance criteria
 260                 elif res == True:
 261                     prev_rate = rate
 262                     rate += self._rate_linear_step
 263                     if rate > self._rate_max:
 264                         if prev_rate != self._rate_max:
 265                             #one last step with rate set to _rate_max
 266                             rate = self._rate_max
 267                             continue
 268                         else:
 269                             self._search_result = SearchResults.SUCCESS
 270                             self._search_result_rate = prev_rate
 271                             return
 272                     else:
 273                         continue
 274                 else:
 275                     raise RuntimeError("Unknown search result")
 276
 277             elif self._search_linear_direction == SearchDirection.TOP_DOWN:
 278                 #loss occured, decrease rate
 279                 if res == False:
 280                     prev_rate = rate
 281                     rate -= self._rate_linear_step
 282                     if rate < self._rate_min:
 283                         if prev_rate != self._rate_min:
 284                             #one last step with rate set to _rate_min
 285                             rate = self._rate_min
 286                             continue
 287                         else:
 288                             self._search_result = SearchResults.FAILURE
 289                             self._search_result_rate = None
 290                             return
 291                     else:
 292                         continue
 293                 #no loss => non/partial drop rate found
 294                 elif res == True:
 295                     self._search_result = SearchResults.SUCCESS
 296                     self._search_result_rate = rate
 297                     return
 298                 else:
 299                     raise RuntimeError("Unknown search result")
 300             else:
 301                 raise Exception("Unknown search direction")
 302
 303         raise Exception("Wrong codepath")
 304
 305     def verify_search_result(self):
 306         """Fail if search was not successful
 307
 308         :return: result rate
 309         :rtype: float
 310         """
 311         if self._search_result == SearchResults.FAILURE:
 312             raise Exception('Search FAILED')
 313         elif self._search_result in [SearchResults.SUCCESS, SearchResults.SUSPICIOUS]:
 314             return self._search_result_rate
 315
 316     def binary_search(self, b_min, b_max, traffic_type):
 317         """Binary search of rate with loss below acceptance criteria
 318
 319         :param b_min: min range rate
 320         :param b_max: max range rate
 321         :param traffic_type: traffic profile
 322         :type b_min: float
 323         :type b_max: float
 324         :type traffic_type: str
 325         :return: nothing
 326         """
 327
 328         if not self._rate_min <= float(b_min) <= self._rate_max:
 329             raise ValueError("Min rate is not in min,max range")
 330         if not self._rate_min <= float(b_max) <= self._rate_max:
 331             raise ValueError("Max rate is not in min,max range")
 332         if float(b_max) < float(b_min):
 333             raise ValueError("Min rate is greater then max rate")
 334
 335         #binary search
 336         #rate is half of interval + start of interval
 337         rate = ((float(b_max) - float(b_min)) / 2) + float(b_min)
 338         #rate diff with previous run
 339         rate_diff = abs(self._last_binary_rate - rate)
 340
 341         #convergence criterium
 342         if float(rate_diff) < float(self._binary_convergence_threshold):
 343             if not self._search_result_rate:
 344                 self._search_result = SearchResults.FAILURE
 345             else:
 346                 self._search_result = SearchResults.SUCCESS
 347             return
 348
 349         self._last_binary_rate = rate
 350
 351         res = self.measure_loss(rate, self._frame_size,
 352                                 self._loss_acceptance,
 353                                 self._loss_acceptance_type,
 354                                 traffic_type)
 355         #loss occured and it was above acceptance criteria
 356         if res == False:
 357             self.binary_search(b_min, rate, traffic_type)
 358         #there was no loss / loss below acceptance criteria
 359         elif res == True:
 360             self._search_result_rate = rate
 361             self.binary_search(rate, b_max, traffic_type)
 362         else:
 363             raise RuntimeError("Unknown search result")
 364
 365     def combined_search(self):
 366         raise NotImplementedError