1 // Copyright (C) 2020, Cloudflare, Inc. 2 // Copyright (C) 2017, Google, Inc. 3 // 4 // Use of this source code is governed by the following BSD-style license: 5 // 6 // Redistribution and use in source and binary forms, with or without 7 // modification, are permitted provided that the following conditions are 8 // met: 9 // 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above 13 // copyright notice, this list of conditions and the following disclaimer 14 // in the documentation and/or other materials provided with the 15 // distribution. 16 // 17 // * Neither the name of Google Inc. nor the names of its 18 // contributors may be used to endorse or promote products derived from 19 // this software without specific prior written permission. 20 // 21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 33 // lib/minmax.c: windowed min/max tracker 34 // 35 // Kathleen Nichols' algorithm for tracking the minimum (or maximum) 36 // value of a data stream over some fixed time interval. (E.g., 37 // the minimum RTT over the past five minutes.) It uses constant 38 // space and constant time per update yet almost always delivers 39 // the same minimum as an implementation that has to keep all the 40 // data in the window. 41 // 42 // The algorithm keeps track of the best, 2nd best & 3rd best min 43 // values, maintaining an invariant that the measurement time of 44 // the n'th best >= n-1'th best. It also makes sure that the three 45 // values are widely separated in the time window since that bounds 46 // the worse case error when that data is monotonically increasing 47 // over the window. 48 // 49 // Upon getting a new min, we can forget everything earlier because 50 // it has no value - the new min is <= everything else in the window 51 // by definition and it's the most recent. So we restart fresh on 52 // every new min and overwrites 2nd & 3rd choices. The same property 53 // holds for 2nd & 3rd best. 54 55 use std::time::Duration; 56 use std::time::Instant; 57 58 #[derive(Copy, Clone)] 59 struct MinmaxSample<T> { 60 time: Instant, 61 value: T, 62 } 63 64 pub struct Minmax<T> { 65 estimate: [MinmaxSample<T>; 3], 66 } 67 68 impl<T: PartialOrd + Copy> Minmax<T> { new(val: T) -> Self69 pub fn new(val: T) -> Self { 70 Minmax { 71 estimate: [MinmaxSample { 72 time: Instant::now(), 73 value: val, 74 }; 3], 75 } 76 } 77 78 /// Resets the estimates to the given value. reset(&mut self, time: Instant, meas: T) -> T79 pub fn reset(&mut self, time: Instant, meas: T) -> T { 80 let val = MinmaxSample { time, value: meas }; 81 82 for i in self.estimate.iter_mut() { 83 *i = val; 84 } 85 86 self.estimate[0].value 87 } 88 89 /// Updates the min estimate based on the given measurement, and returns it. running_min(&mut self, win: Duration, time: Instant, meas: T) -> T90 pub fn running_min(&mut self, win: Duration, time: Instant, meas: T) -> T { 91 let val = MinmaxSample { time, value: meas }; 92 93 let delta_time = time.duration_since(self.estimate[2].time); 94 95 // Reset if there's nothing in the window or a new min value is found. 96 if val.value <= self.estimate[0].value || delta_time > win { 97 return self.reset(time, meas); 98 } 99 100 if val.value <= self.estimate[1].value { 101 self.estimate[2] = val; 102 self.estimate[1] = val; 103 } else if val.value <= self.estimate[2].value { 104 self.estimate[2] = val; 105 } 106 107 self.subwin_update(win, time, meas) 108 } 109 110 /// Updates the max estimate based on the given measurement, and returns it. running_max(&mut self, win: Duration, time: Instant, meas: T) -> T111 pub fn running_max(&mut self, win: Duration, time: Instant, meas: T) -> T { 112 let val = MinmaxSample { time, value: meas }; 113 114 let delta_time = time.duration_since(self.estimate[2].time); 115 116 // Reset if there's nothing in the window or a new max value is found. 117 if val.value >= self.estimate[0].value || delta_time > win { 118 return self.reset(time, meas); 119 } 120 121 if val.value >= self.estimate[1].value { 122 self.estimate[2] = val; 123 self.estimate[1] = val; 124 } else if val.value >= self.estimate[2].value { 125 self.estimate[2] = val 126 } 127 128 self.subwin_update(win, time, meas) 129 } 130 131 /// As time advances, update the 1st, 2nd and 3rd estimates. subwin_update(&mut self, win: Duration, time: Instant, meas: T) -> T132 fn subwin_update(&mut self, win: Duration, time: Instant, meas: T) -> T { 133 let val = MinmaxSample { time, value: meas }; 134 135 let delta_time = time.duration_since(self.estimate[0].time); 136 137 if delta_time > win { 138 // Passed entire window without a new val so make 2nd estimate the 139 // new val & 3rd estimate the new 2nd choice. we may have to iterate 140 // this since our 2nd estimate may also be outside the window (we 141 // checked on entry that the third estimate was in the window). 142 self.estimate[0] = self.estimate[1]; 143 self.estimate[1] = self.estimate[2]; 144 self.estimate[2] = val; 145 146 if time.duration_since(self.estimate[0].time) > win { 147 self.estimate[0] = self.estimate[1]; 148 self.estimate[1] = self.estimate[2]; 149 self.estimate[2] = val; 150 } 151 } else if self.estimate[1].time == self.estimate[0].time && 152 delta_time > win.div_f32(4.0) 153 { 154 // We've passed a quarter of the window without a new val so take a 155 // 2nd estimate from the 2nd quarter of the window. 156 self.estimate[2] = val; 157 self.estimate[1] = val; 158 } else if self.estimate[2].time == self.estimate[1].time && 159 delta_time > win.div_f32(2.0) 160 { 161 // We've passed half the window without finding a new val so take a 162 // 3rd estimate from the last half of the window. 163 self.estimate[2] = val; 164 } 165 166 self.estimate[0].value 167 } 168 } 169 170 #[cfg(test)] 171 mod tests { 172 use super::*; 173 174 #[test] reset_filter_rtt()175 fn reset_filter_rtt() { 176 let mut f = Minmax::new(Duration::ZERO); 177 let now = Instant::now(); 178 let rtt = Duration::from_millis(50); 179 180 let rtt_min = f.reset(now, rtt); 181 assert_eq!(rtt_min, rtt); 182 183 assert_eq!(f.estimate[0].time, now); 184 assert_eq!(f.estimate[0].value, rtt); 185 186 assert_eq!(f.estimate[1].time, now); 187 assert_eq!(f.estimate[1].value, rtt); 188 189 assert_eq!(f.estimate[2].time, now); 190 assert_eq!(f.estimate[2].value, rtt); 191 } 192 193 #[test] reset_filter_bandwidth()194 fn reset_filter_bandwidth() { 195 let mut f = Minmax::new(0); 196 let now = Instant::now(); 197 let bw = 2000; 198 199 let bw_min = f.reset(now, bw); 200 assert_eq!(bw_min, bw); 201 202 assert_eq!(f.estimate[0].time, now); 203 assert_eq!(f.estimate[0].value, bw); 204 205 assert_eq!(f.estimate[1].time, now); 206 assert_eq!(f.estimate[1].value, bw); 207 208 assert_eq!(f.estimate[2].time, now); 209 assert_eq!(f.estimate[2].value, bw); 210 } 211 212 #[test] get_windowed_min_rtt()213 fn get_windowed_min_rtt() { 214 let mut f = Minmax::new(Duration::ZERO); 215 let rtt_25 = Duration::from_millis(25); 216 let rtt_24 = Duration::from_millis(24); 217 let win = Duration::from_millis(500); 218 let mut time = Instant::now(); 219 220 let mut rtt_min = f.reset(time, rtt_25); 221 assert_eq!(rtt_min, rtt_25); 222 223 time += Duration::from_millis(250); 224 rtt_min = f.running_min(win, time, rtt_24); 225 assert_eq!(rtt_min, rtt_24); 226 assert_eq!(f.estimate[1].value, rtt_24); 227 assert_eq!(f.estimate[2].value, rtt_24); 228 229 time += Duration::from_millis(600); 230 rtt_min = f.running_min(win, time, rtt_25); 231 assert_eq!(rtt_min, rtt_25); 232 assert_eq!(f.estimate[1].value, rtt_25); 233 assert_eq!(f.estimate[2].value, rtt_25); 234 } 235 236 #[test] get_windowed_min_bandwidth()237 fn get_windowed_min_bandwidth() { 238 let mut f = Minmax::new(0); 239 let bw_200 = 200; 240 let bw_500 = 500; 241 let win = Duration::from_millis(500); 242 let mut time = Instant::now(); 243 244 let mut bw_min = f.reset(time, bw_500); 245 assert_eq!(bw_min, bw_500); 246 247 time += Duration::from_millis(250); 248 bw_min = f.running_min(win, time, bw_200); 249 assert_eq!(bw_min, bw_200); 250 assert_eq!(f.estimate[1].value, bw_200); 251 assert_eq!(f.estimate[2].value, bw_200); 252 253 time += Duration::from_millis(600); 254 bw_min = f.running_min(win, time, bw_500); 255 assert_eq!(bw_min, bw_500); 256 assert_eq!(f.estimate[1].value, bw_500); 257 assert_eq!(f.estimate[2].value, bw_500); 258 } 259 260 #[test] get_windowed_max_rtt()261 fn get_windowed_max_rtt() { 262 let mut f = Minmax::new(Duration::ZERO); 263 let rtt_25 = Duration::from_millis(25); 264 let rtt_24 = Duration::from_millis(24); 265 let win = Duration::from_millis(500); 266 let mut time = Instant::now(); 267 268 let mut rtt_max = f.reset(time, rtt_24); 269 assert_eq!(rtt_max, rtt_24); 270 271 time += Duration::from_millis(250); 272 rtt_max = f.running_max(win, time, rtt_25); 273 assert_eq!(rtt_max, rtt_25); 274 assert_eq!(f.estimate[1].value, rtt_25); 275 assert_eq!(f.estimate[2].value, rtt_25); 276 277 time += Duration::from_millis(600); 278 rtt_max = f.running_max(win, time, rtt_24); 279 assert_eq!(rtt_max, rtt_24); 280 assert_eq!(f.estimate[1].value, rtt_24); 281 assert_eq!(f.estimate[2].value, rtt_24); 282 } 283 284 #[test] get_windowed_max_bandwidth()285 fn get_windowed_max_bandwidth() { 286 let mut f = Minmax::new(0); 287 let bw_200 = 200; 288 let bw_500 = 500; 289 let win = Duration::from_millis(500); 290 let mut time = Instant::now(); 291 292 let mut bw_max = f.reset(time, bw_200); 293 assert_eq!(bw_max, bw_200); 294 295 time += Duration::from_millis(5000); 296 bw_max = f.running_max(win, time, bw_500); 297 assert_eq!(bw_max, bw_500); 298 assert_eq!(f.estimate[1].value, bw_500); 299 assert_eq!(f.estimate[2].value, bw_500); 300 301 time += Duration::from_millis(600); 302 bw_max = f.running_max(win, time, bw_200); 303 assert_eq!(bw_max, bw_200); 304 assert_eq!(f.estimate[1].value, bw_200); 305 assert_eq!(f.estimate[2].value, bw_200); 306 } 307 308 #[test] get_windowed_min_estimates_rtt()309 fn get_windowed_min_estimates_rtt() { 310 let mut f = Minmax::new(Duration::ZERO); 311 let rtt_25 = Duration::from_millis(25); 312 let rtt_24 = Duration::from_millis(24); 313 let rtt_23 = Duration::from_millis(23); 314 let rtt_22 = Duration::from_millis(22); 315 let win = Duration::from_secs(1); 316 let mut time = Instant::now(); 317 318 let mut rtt_min = f.reset(time, rtt_23); 319 assert_eq!(rtt_min, rtt_23); 320 321 time += Duration::from_millis(300); 322 rtt_min = f.running_min(win, time, rtt_24); 323 assert_eq!(rtt_min, rtt_23); 324 assert_eq!(f.estimate[1].value, rtt_24); 325 assert_eq!(f.estimate[2].value, rtt_24); 326 327 time += Duration::from_millis(300); 328 rtt_min = f.running_min(win, time, rtt_25); 329 assert_eq!(rtt_min, rtt_23); 330 assert_eq!(f.estimate[1].value, rtt_24); 331 assert_eq!(f.estimate[2].value, rtt_25); 332 333 time += Duration::from_millis(300); 334 rtt_min = f.running_min(win, time, rtt_22); 335 assert_eq!(rtt_min, rtt_22); 336 assert_eq!(f.estimate[1].value, rtt_22); 337 assert_eq!(f.estimate[2].value, rtt_22); 338 } 339 340 #[test] get_windowed_min_estimates_bandwidth()341 fn get_windowed_min_estimates_bandwidth() { 342 let mut f = Minmax::new(0); 343 let bw_500 = 500; 344 let bw_400 = 400; 345 let bw_300 = 300; 346 let bw_200 = 200; 347 let win = Duration::from_secs(1); 348 let mut time = Instant::now(); 349 350 let mut bw_min = f.reset(time, bw_300); 351 assert_eq!(bw_min, bw_300); 352 353 time += Duration::from_millis(300); 354 bw_min = f.running_min(win, time, bw_400); 355 assert_eq!(bw_min, bw_300); 356 assert_eq!(f.estimate[1].value, bw_400); 357 assert_eq!(f.estimate[2].value, bw_400); 358 359 time += Duration::from_millis(300); 360 bw_min = f.running_min(win, time, bw_500); 361 assert_eq!(bw_min, bw_300); 362 assert_eq!(f.estimate[1].value, bw_400); 363 assert_eq!(f.estimate[2].value, bw_500); 364 365 time += Duration::from_millis(300); 366 bw_min = f.running_min(win, time, bw_200); 367 assert_eq!(bw_min, bw_200); 368 assert_eq!(f.estimate[1].value, bw_200); 369 assert_eq!(f.estimate[2].value, bw_200); 370 } 371 372 #[test] get_windowed_max_estimates_rtt()373 fn get_windowed_max_estimates_rtt() { 374 let mut f = Minmax::new(Duration::ZERO); 375 let rtt_25 = Duration::from_millis(25); 376 let rtt_24 = Duration::from_millis(24); 377 let rtt_23 = Duration::from_millis(23); 378 let rtt_26 = Duration::from_millis(26); 379 let win = Duration::from_secs(1); 380 let mut time = Instant::now(); 381 382 let mut rtt_max = f.reset(time, rtt_25); 383 assert_eq!(rtt_max, rtt_25); 384 385 time += Duration::from_millis(300); 386 rtt_max = f.running_max(win, time, rtt_24); 387 assert_eq!(rtt_max, rtt_25); 388 assert_eq!(f.estimate[1].value, rtt_24); 389 assert_eq!(f.estimate[2].value, rtt_24); 390 391 time += Duration::from_millis(300); 392 rtt_max = f.running_max(win, time, rtt_23); 393 assert_eq!(rtt_max, rtt_25); 394 assert_eq!(f.estimate[1].value, rtt_24); 395 assert_eq!(f.estimate[2].value, rtt_23); 396 397 time += Duration::from_millis(300); 398 rtt_max = f.running_max(win, time, rtt_26); 399 assert_eq!(rtt_max, rtt_26); 400 assert_eq!(f.estimate[1].value, rtt_26); 401 assert_eq!(f.estimate[2].value, rtt_26); 402 } 403 404 #[test] get_windowed_max_estimates_bandwidth()405 fn get_windowed_max_estimates_bandwidth() { 406 let mut f = Minmax::new(0); 407 let bw_500 = 500; 408 let bw_400 = 400; 409 let bw_300 = 300; 410 let bw_600 = 600; 411 let win = Duration::from_secs(1); 412 let mut time = Instant::now(); 413 414 let mut bw_max = f.reset(time, bw_500); 415 assert_eq!(bw_max, bw_500); 416 417 time += Duration::from_millis(300); 418 bw_max = f.running_max(win, time, bw_400); 419 assert_eq!(bw_max, bw_500); 420 assert_eq!(f.estimate[1].value, bw_400); 421 assert_eq!(f.estimate[2].value, bw_400); 422 423 time += Duration::from_millis(300); 424 bw_max = f.running_max(win, time, bw_300); 425 assert_eq!(bw_max, bw_500); 426 assert_eq!(f.estimate[1].value, bw_400); 427 assert_eq!(f.estimate[2].value, bw_300); 428 429 time += Duration::from_millis(300); 430 bw_max = f.running_max(win, time, bw_600); 431 assert_eq!(bw_max, bw_600); 432 assert_eq!(f.estimate[1].value, bw_600); 433 assert_eq!(f.estimate[2].value, bw_600); 434 } 435 } 436