lsquic_minmax.c revision 7d09751d 
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * Based on Google code released under BSD license here:
4 *  https://groups.google.com/forum/#!topic/bbr-dev/3RTgkzi5ZD8
5 */
6
7/*
8 * Copyright 2017, Google Inc.
9 *
10 * Use of this source code is governed by the following BSD-style license:
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions are
14 * met:
15 *
16 *    * Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 *    * Redistributions in binary form must reproduce the above
19 * copyright notice, this list of conditions and the following disclaimer
20 * in the documentation and/or other materials provided with the
21 * distribution.
22 *
23 *    * Neither the name of Google Inc. nor the names of its
24 * contributors may be used to endorse or promote products derived from
25 * this software without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
29 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
30 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
33 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
34 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
35 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
36 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
37 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 */
39
40/*
41 * Kathleen Nichols' algorithm for tracking the minimum (or maximum)
42 * value of a data stream over some fixed time interval.  (E.g.,
43 * the minimum RTT over the past five minutes.) It uses constant
44 * space and constant time per update yet almost always delivers
45 * the same minimum as an implementation that has to keep all the
46 * data in the window.
47 *
48 * The algorithm keeps track of the best, 2nd best & 3rd best min
49 * values, maintaining an invariant that the measurement time of
50 * the n'th best >= n-1'th best. It also makes sure that the three
51 * values are widely separated in the time window since that bounds
52 * the worse case error when that data is monotonically increasing
53 * over the window.
54 *
55 * Upon getting a new min, we can forget everything earlier because
56 * it has no value - the new min is <= everything else in the window
57 * by definition and it'samples the most recent. So we restart fresh on
58 * every new min and overwrites 2nd & 3rd choices. The same property
59 * holds for 2nd & 3rd best.
60 */
61
62#include <stdint.h>
63#include <string.h>
64
65#include "lsquic_minmax.h"
66
67/* As time advances, update the 1st, 2nd, and 3rd choices. */
68static void
69minmax_subwin_update (struct minmax *minmax, const struct minmax_sample *sample)
70{
71    uint64_t dt = sample->time - minmax->samples[0].time;
72
73    if (dt > minmax->window)
74    {
75        /*
76         * Passed entire window without a new sample so make 2nd
77         * choice the new sample & 3rd choice the new 2nd choice.
78         * we may have to iterate this since our 2nd choice
79         * may also be outside the window (we checked on entry
80         * that the third choice was in the window).
81         */
82        minmax->samples[0] = minmax->samples[1];
83        minmax->samples[1] = minmax->samples[2];
84        minmax->samples[2] = *sample;
85        if (sample->time - minmax->samples[0].time > minmax->window) {
86            minmax->samples[0] = minmax->samples[1];
87            minmax->samples[1] = minmax->samples[2];
88            minmax->samples[2] = *sample;
89        }
90    }
91    else if (minmax->samples[1].time == minmax->samples[0].time
92                                                && dt > minmax->window / 4)
93    {
94        /*
95         * We've passed a quarter of the window without a new sample
96         * so take a 2nd choice from the 2nd quarter of the window.
97         */
98        minmax->samples[2] = minmax->samples[1] = *sample;
99    }
100    else if (minmax->samples[2].time == minmax->samples[1].time
101                                                && dt > minmax->window / 2)
102    {
103        /*
104         * We've passed half the window without finding a new sample
105         * so take a 3rd choice from the last half of the window
106         */
107        minmax->samples[2] = *sample;
108    }
109}
110
111
112/* Check if new measurement updates the 1st, 2nd or 3rd choice max. */
113void
114lsquic_minmax_update_max (struct minmax *minmax, uint64_t now, uint64_t meas)
115{
116    struct minmax_sample sample = { .time = now, .value = meas };
117
118    if (minmax->samples[0].value == 0                                       /* uninitialized */
119            || sample.value >= minmax->samples[0].value                     /* found new max? */
120            || sample.time - minmax->samples[2].time > minmax->window)      /* nothing left in window? */
121    {
122        minmax_reset(minmax, sample);  /* forget earlier samples */
123        return;
124    }
125
126    if (sample.value >= minmax->samples[1].value)
127        minmax->samples[2] = minmax->samples[1] = sample;
128    else if (sample.value >= minmax->samples[2].value)
129        minmax->samples[2] = sample;
130
131    minmax_subwin_update(minmax, &sample);
132}
133
134
135/* Check if new measurement updates the 1st, 2nd or 3rd choice min. */
136void
137lsquic_minmax_update_min (struct minmax *minmax, uint64_t now, uint64_t meas)
138{
139    struct minmax_sample sample = { .time = now, .value = meas };
140
141    if (minmax->samples[0].value == 0                                       /* uninitialized */
142            || sample.value <= minmax->samples[0].value                     /* found new min? */
143            || sample.time - minmax->samples[2].time > minmax->window)      /* nothing left in window? */
144    {
145        minmax_reset(minmax, sample);  /* forget earlier samples */
146        return;
147    }
148
149    if (sample.value <= minmax->samples[1].value)
150        minmax->samples[2] = minmax->samples[1] = sample;
151    else if (sample.value <= minmax->samples[2].value)
152        minmax->samples[2] = sample;
153
154    minmax_subwin_update(minmax, &sample);
155}
156