1 # Copyright (c) 2021 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:
6 # http://www.apache.org/licenses/LICENSE-2.0
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.
14 """Module defining utility functions for manipulating intervals."""
19 ROUNDING_CONSTANT = 0.999999
21 def multiply_relative_width(relative_width, coefficient):
22 """Return relative width corresponding to multiplied logarithmic width.
24 The multiplication happens in logarithmic space,
25 so the resulting relative width is always less than 1.
27 :param relative_width: The base relative width to multiply.
28 :param coefficient: Multiply by this in logarithmic space.
29 :type relative_width: float
30 :type coefficient: float
31 :returns: The relative width of multiplied logarithmic size.
34 old_log_width = math.log(1.0 - relative_width)
35 # Slight decrease to prevent rounding errors from prolonging the search.
36 # TODO: Make the nines configurable.
37 new_log_width = old_log_width * coefficient * ROUNDING_CONSTANT
38 return 1.0 - math.exp(new_log_width)
40 def halve_relative_width(relative_width, goal_width):
41 """Return relative width corresponding to half logarithmic width.
43 The logic attempts to save some halvings in future by performing
44 uneven split. If rounding error risk is detected,
47 :param relative_width: The base relative width to halve.
48 :param goal_width: Width goal for final phase.
49 :type relative_width: float
50 :type goal_width: float
51 :returns: The relative width of half logarithmic size.
54 fallback_width = 1.0 - math.sqrt(1.0 - relative_width)
55 # Wig means Width In Goals.
56 wig = math.log(1.0 - relative_width) / math.log(1.0 - goal_width)
58 if wig <= 2.0 or cwig != math.ceil(wig * ROUNDING_CONSTANT):
60 coefficient = cwig // 2
61 new_width = multiply_relative_width(goal_width, coefficient)
64 def step_down(current_bound, relative_width):
65 """Return rate of logarithmic width below.
67 :param current_bound: The current target transmit rate to move [pps].
68 :param relative_width: The base relative width to use.
69 :type current_bound: float
70 :type relative_width: float
71 :returns: Transmit rate smaller by relative width [pps].
74 return current_bound * (1.0 - relative_width)
76 def step_up(current_bound, relative_width):
77 """Return rate of logarithmic width above.
79 :param current_bound: The current target transmit rate to move [pps].
80 :param relative_width: The base relative width to use.
81 :type current_bound: float
82 :type relative_width: float
83 :returns: Transmit rate larger by logarithmically double width [pps].
86 return current_bound / (1.0 - relative_width)
88 def multiple_step_down(current_bound, relative_width, coefficient):
89 """Return rate of multiplied logarithmic width below.
91 The multiplication happens in logarithmic space,
92 so the resulting applied relative width is always less than 1.
94 :param relative_width: The base relative width to double.
95 :param current_bound: The current target transmit rate to move [pps].
96 :param coefficient: Multiply by this in logarithmic space.
97 :type relative_width: float
98 :type current_bound: float
99 :type coefficient: float
100 :returns: Transmit rate smaller by logarithmically multiplied width [pps].
103 new_width = multiply_relative_width(relative_width, coefficient)
104 return step_down(current_bound, new_width)
106 def multiple_step_up(current_bound, relative_width, coefficient):
107 """Return rate of double logarithmic width above.
109 The multiplication happens in logarithmic space,
110 so the resulting applied relative width is always less than 1.
112 :param current_bound: The current target transmit rate to move [pps].
113 :param relative_width: The base relative width to double.
114 :param coefficient: Multiply by this in logarithmic space.
115 :type current_bound: float
116 :type relative_width: float
117 :type coefficient: float
118 :returns: Transmit rate larger by logarithmically multiplied width [pps].
121 new_width = multiply_relative_width(relative_width, coefficient)
122 return step_up(current_bound, new_width)
124 def half_step_up(current_bound, relative_width, goal_width):
125 """Return rate of half logarithmic width above.
127 :param relative_width: The base relative width to halve.
128 :param current_bound: The current target transmit rate to move [pps].
129 :type relative_width: float
130 :type current_bound: float
131 :returns: Transmit rate larger by logarithmically half width [pps].
134 new_width = halve_relative_width(relative_width, goal_width)
135 return step_up(current_bound, new_width)