Implement THROTTLED priority semantics.

net/base/quantile_estimator.h

+// 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.
+
+#ifndef NET_BASE_QUANTILE_ESTIMATOR_H_
+#define NET_BASE_QUANTILE_ESTIMATOR_H_
+
+#include "base/callback.h"
+#include "base/macros.h"
+#include "net/base/net_export.h"
+
+namespace net {
+
+// This class estimates statistical quantiles (e.g. 10%l, 50%l) for
+// integer distributions presented in stream form.  These estimates adjust
+// automatically when the stream distribution changes.
+// TODO(rdsmith): Expand to floating point, when there's a use case for that

[mmenke, 2016/09/19 15:26:17]

Expand what to floating point?  The estimate, or the quantile argument?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:27]

The estimate.  Clarified the commetn.

+// that deserves the extra complexity and pitfalls of floating point
+// arithmetic.
+class NET_EXPORT QuantileEstimator {
+ public:
+  using RandomNumberCallback = base::Callback<int(void)>;
+
+  static const int kMedianQuantile = 50;
+
+  // |quantile| is a number between 0 and 100 indicating what quantile
+  // should be estimated (e.g. 50 would be a median estimate).
+  // |initial_estimate| is the value the class is seeded with; in other
+  // words, if AddSample() is never called,
+  // |CurrentEstimate() == initial_estimate|.
+  QuantileEstimator(int quantile, int initial_estimate);

[mmenke, 2016/09/19 15:26:17]

I think this should technically be Percentile, not Quantile?  Quantile implies
one of a fixed number of equal-sized groups.  In this case, we estimate the
value at a particular percentile.  I'm not sure what the 50th quantile even
means, in an absolute sense.  The 50th percentile, on the other hand...

If by expand to floating point, you mean the quantile argument, then percentile
may not be accurate, but I don't think quantile is, either.  Is there a related
term that doesn't have the equal-sized buckets assumption?

[Randy Smith (Not in Mondays), 2016/09/22 21:52:27]

That sounds right to me.  Ok, one large scale name change coming up :-}. 
I meant the estimate, not the quantile argument.

+
+  ~QuantileEstimator();
+
+  int current_estimate() const { return current_estimate_; }
+  void AddSample(int sample);
+
+  // Specify a callback that will generate a "random" number
+  // in the range [0,99] on each call.  Used so that tests can
+  // rely on reproducible behavior.
+  void SetRandomNumberGeneratorForTesting(
+      RandomNumberCallback generator_callback);
+
+ private:
+  const int quantile_;
+
+  bool sign_positive_;
+  int current_estimate_;
+  int current_step_;
+
+  RandomNumberCallback generator_callback_;
+
+  DISALLOW_COPY_AND_ASSIGN(QuantileEstimator);
+};
+
+}  // namespace net
+
+#endif  // NET_BASE_QUANTILE_ESTIMATOR_H_