1 # Copyright (c) 2021 Cisco and/or its affiliates.
3 # you may not use this file except in compliance with the License.
4 # You may obtain a copy of the License at:
5 #
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.
14 """Module defining utility functions for manipulating intervals."""
16 import math
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.
32     :rtype: float
33     """
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,
45     even split is used.
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.
52     :rtype: float
53     """
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)
57     cwig = 2.0 * math.ceil(wig / 2.0)
58     fwig = 2.0 * math.ceil(wig * ROUNDING_CONSTANT / 2.0)
59     if wig <= 2.0 or cwig != fwig:
60         # Avoid too uneven splits.
61         return fallback_width
62     coefficient = cwig / 2
63     new_width = multiply_relative_width(goal_width, coefficient)
64     return new_width
66 def step_down(current_bound, relative_width):
67     """Return rate of logarithmic width below.
69     :param current_bound: The current target transmit rate to move [pps].
70     :param relative_width: The base relative width to use.
71     :type current_bound: float
72     :type relative_width: float
73     :returns: Transmit rate smaller by relative width [pps].
74     :rtype: float
75     """
76     return current_bound * (1.0 - relative_width)
78 def step_up(current_bound, relative_width):
79     """Return rate of logarithmic width above.
81     :param current_bound: The current target transmit rate to move [pps].
82     :param relative_width: The base relative width to use.
83     :type current_bound: float
84     :type relative_width: float
85     :returns: Transmit rate larger by logarithmically double width [pps].
86     :rtype: float
87     """
88     return current_bound / (1.0 - relative_width)
90 def multiple_step_down(current_bound, relative_width, coefficient):
91     """Return rate of multiplied logarithmic width below.
93     The multiplication happens in logarithmic space,
94     so the resulting applied relative width is always less than 1.
96     :param relative_width: The base relative width to double.
97     :param current_bound: The current target transmit rate to move [pps].
98     :param coefficient: Multiply by this in logarithmic space.
99     :type relative_width: float
100     :type current_bound: float
101     :type coefficient: float
102     :returns: Transmit rate smaller by logarithmically multiplied width [pps].
103     :rtype: float
104     """
105     new_width = multiply_relative_width(relative_width, coefficient)
106     return step_down(current_bound, new_width)
108 def multiple_step_up(current_bound, relative_width, coefficient):
109     """Return rate of double logarithmic width above.
111     The multiplication happens in logarithmic space,
112     so the resulting applied relative width is always less than 1.
114     :param current_bound: The current target transmit rate to move [pps].
115     :param relative_width: The base relative width to double.
116     :param coefficient: Multiply by this in logarithmic space.
117     :type current_bound: float
118     :type relative_width: float
119     :type coefficient: float
120     :returns: Transmit rate larger by logarithmically multiplied width [pps].
121     :rtype: float
122     """
123     new_width = multiply_relative_width(relative_width, coefficient)
124     return step_up(current_bound, new_width)
126 def half_step_up(current_bound, relative_width, goal_width):
127     """Return rate of half logarithmic width above.
129     :param relative_width: The base relative width to halve.
130     :param current_bound: The current target transmit rate to move [pps].
131     :type relative_width: float
132     :type current_bound: float
133     :returns: Transmit rate larger by logarithmically half width [pps].
134     :rtype: float
135     """
136     new_width = halve_relative_width(relative_width, goal_width)
137     return step_up(current_bound, new_width)