Implement THROTTLED priority semantics.

net/base/quantile_estimator.cc

Index: net/base/quantile_estimator.cc
diff --git a/net/base/quantile_estimator.cc b/net/base/quantile_estimator.cc
new file mode 100644
index 0000000000000000000000000000000000000000..b4ed7e2d1839a81760577dc6be81a454f8c5bd85
--- /dev/null
+++ b/net/base/quantile_estimator.cc
@@ -0,0 +1,93 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "quantile_estimator.h"
+
+#include "base/bind.h"
+#include "base/callback.h"
+#include "base/rand_util.h"
+
+namespace {
+
+// Random number wrapper to allow substitutions for testing.
+int GenerateRand0To99() {
+  return base::RandInt(0, 99);
+}
+
+}  // namespace
+
+namespace net {
+
+// The algorithm used for quantile estimation is "Algorithm 3" from
+// http://arxiv.org/pdf/1407.1121v1.pdf.  There are several parts to the

[Charlie Harrison, 2016/09/01 18:17:52]

https url?

[Randy Smith (Not in Mondays), 2016/09/18 19:12:35]

Done.

+// algorithm:
+// * The estimate is conditionally moved towards the sample by a step amount.
+//   This means that if the samples are clustered around a value the estimates
+//   will converge to that sample.
+// * The quantile requested (e.g. 90%l) is handled by the conditional move.

[Charlie Harrison, 2016/09/01 18:17:53]

I think you have this backwards. Let's go off of algorithm 2 for simplicity (and
use 90%l). So, step is either -1 or 1.

Assume the estimate (e) is correct. We'd like the expected value of a move to be
zero. Let s be the sample.

E[move | e = 90%l] = 0
= 1 * P(move_up | s > e) * P(s > e) + (-1) * P(move_down | s < e) * P(s < e)
= p * P(s > e) - q * P(s < e)
= p * 1/10 - q * 9/10

so:
p = 9q, so P(move_up | s > e) = .9 and P(move_down | s < e) = .1

[Randy Smith (Not in Mondays), 2016/09/18 19:12:35]

Whoops!!  Thank you for catching that.   And I had it wrong in the code, too. 
That makes me pretty deeply disturbed about the tests.  

+//   The estimate is only moved towards the sample if a random number between
+//   0 and 1 falls on the side of the quantile the sample must be in to
+//   indicate that quantile must be adjusted.  E.g. in the case of the 90%l
+//   estimation, the estimate would only move up in 10% of the cases in which
+//   the sample was above the estimate, but it would move down in 90% of the
+//   cases in which the sample was below the estimate.
+// * Every time the estimate moves in the same direction, the step amount is
+//   increased by one, and every time the estimate reverses direction, the
+//   step amount is decreased (to 1, if greater than 1, by one, if zero or
+//   negative).  The effective step amount is Max(step, 1).
+// * If the estimate would be moved beyond the sample causing its move,
+//   it is moved to be equal to the same (and the step amount set to the
+//   distance to the sample).
+// See the paper for further details.
+
+QuantileEstimator::QuantileEstimator(int quantile, int initial_estimate)
+    : quantile_(quantile),
+      sign_positive_(true),
+      current_estimate_(initial_estimate),
+      current_step_(1),
+      generator_callback_(base::Bind(&GenerateRand0To99)) {}
+
+QuantileEstimator::~QuantileEstimator() {}
+
+void QuantileEstimator::AddSample(int sample) {
+  int rand100 = generator_callback_.Run();
+  if (sample > current_estimate_ && rand100 >= quantile_) {
+    current_step_ += sign_positive_ ? 1 : -1;
+    current_estimate_ += (current_step_ > 0) ? current_step_ : 1;
+
+    // Clamp movement to distance to sample.
+    if (current_estimate_ > sample) {
+      current_step_ -= current_estimate_ - sample;
+      current_estimate_ = sample;
+    }
+
+    // If we've reversed direction, reset the step down.
+    if (!sign_positive_ && current_step_ > 1)
+      current_step_ = 1;
+
+    sign_positive_ = true;
+  } else if (sample < current_estimate_ && rand100 < quantile_) {
+    current_step_ += !sign_positive_ ? 1 : -1;
+    current_estimate_ -= (current_step_ > 0) ? current_step_ : 1;
+
+    // Clamp movement to distance to sample.
+    if (current_estimate_ < sample) {
+      current_step_ -= sample - current_estimate_;
+      current_estimate_ = sample;
+    }
+
+    // If we've reversed direction, reset the step down.
+    if (sign_positive_ && current_step_ > 1)
+      current_step_ = 1;
+
+    sign_positive_ = false;
+  }
+}
+
+void QuantileEstimator::SetRandomNumberGeneratorForTesting(
+    RandomNumberCallback generator_callback) {
+  generator_callback_ = generator_callback;
+}
+
+}  // namespace net