Store network quality samples so we can compute percentiles.

net/base/network_quality_estimator.cc

 // Copyright 2015 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 "net/base/network_quality_estimator.h"
 
 #include <string>
 
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
 #include "net/base/net_util.h"
 #include "net/base/network_quality.h"
 #include "net/url_request/url_request.h"
 #include "url/gurl.h"
 
 namespace net {
 
+// Maximum number of observations to hold in the ObservationBuffer.

[mmenke, 2015/06/12 17:34:42]

Description should go with the variable declaration (If it's already there, no
need to have it in both places)

[tbansal1, 2015/06/12 19:14:46]

Done.

+const size_t NetworkQualityEstimator::ObservationBuffer::kMaximumObservations =
+    500;

[mmenke, 2015/06/12 17:34:42]

Your other constants are inlined in the header.  Can we do that with this one,
too, or does the fact it's a size_t cause issues?

[tbansal1, 2015/06/12 19:14:46]

Yes, I tried that before: size_t causes issues.

+
 NetworkQualityEstimator::NetworkQualityEstimator()
     : NetworkQualityEstimator(false) {
 }
 
 NetworkQualityEstimator::NetworkQualityEstimator(
     bool allow_local_host_requests_for_tests)
     : allow_localhost_requests_(allow_local_host_requests_for_tests),
       last_connection_change_(base::TimeTicks::Now()),
       current_connection_type_(NetworkChangeNotifier::GetConnectionType()),
-      bytes_read_since_last_connection_change_(false),
+      fastest_rtt_since_last_connection_change_(base::TimeDelta::Max()),
       peak_kbps_since_last_connection_change_(0) {
   static_assert(kMinRequestDurationMicroseconds > 0,
                 "Minimum request duration must be > 0");
   NetworkChangeNotifier::AddConnectionTypeObserver(this);
 }
 
 NetworkQualityEstimator::~NetworkQualityEstimator() {
   DCHECK(thread_checker_.CalledOnValidThread());
   NetworkChangeNotifier::RemoveConnectionTypeObserver(this);
 }
 
-void NetworkQualityEstimator::NotifyDataReceived(const URLRequest& request,
-                                                 int64_t prefilter_bytes_read) {
+void NetworkQualityEstimator::NotifyDataReceived(
+    const URLRequest& request,
+    int64_t cumulative_prefilter_bytes_read,
+    int64_t prefiltered_bytes_read) {
   DCHECK(thread_checker_.CalledOnValidThread());
-  DCHECK_GT(prefilter_bytes_read, 0);
+  DCHECK_GT(cumulative_prefilter_bytes_read, 0);
+  DCHECK_GT(prefiltered_bytes_read, 0);
 
   if (!request.url().is_valid() ||
       (!allow_localhost_requests_ && IsLocalhost(request.url().host())) ||
       !request.url().SchemeIsHTTPOrHTTPS() ||
       // Verify that response headers are received, so it can be ensured that
       // response is not cached.
       request.response_info().response_time.is_null() || request.was_cached() ||
       request.creation_time() < last_connection_change_) {
     return;
   }
 
   base::TimeTicks now = base::TimeTicks::Now();
   base::TimeDelta request_duration = now - request.creation_time();
   DCHECK_GE(request_duration, base::TimeDelta());
-  if (!bytes_read_since_last_connection_change_)
-    fastest_RTT_since_last_connection_change_ = request_duration;
 
-  bytes_read_since_last_connection_change_ = true;
-  if (request_duration < fastest_RTT_since_last_connection_change_)
-    fastest_RTT_since_last_connection_change_ = request_duration;
+  // Only add RTT observation if this is the first read for this response.
+  if (cumulative_prefilter_bytes_read == prefiltered_bytes_read) {
+    if (request_duration < fastest_rtt_since_last_connection_change_)
+      fastest_rtt_since_last_connection_change_ = request_duration;
+
+    rtt_msec_observations_.AddObservation(
+        Observation(request_duration.InMilliseconds(), now));
+  }
 
   // Ignore tiny transfers which will not produce accurate rates.
   // Ignore short duration transfers.
-  if (prefilter_bytes_read >= kMinTransferSizeInBytes &&
+  if (cumulative_prefilter_bytes_read >= kMinTransferSizeInBytes &&
       request_duration >=
           base::TimeDelta::FromMicroseconds(kMinRequestDurationMicroseconds)) {
-    uint64_t kbps = static_cast<uint64_t>(prefilter_bytes_read * 8 * 1000 /
-                                          request_duration.InMicroseconds());
-    if (kbps > peak_kbps_since_last_connection_change_)
-      peak_kbps_since_last_connection_change_ = kbps;
+    int32_t kbps =
+        static_cast<int32_t>(cumulative_prefilter_bytes_read * 8 * 1000 /
+                             request_duration.InMicroseconds());
+
+    if (kbps > 0) {

[mmenke, 2015/06/12 17:34:42]

This doesn't cover all overflow cases.  Consider that 0x70000001 * 8000 will
give a value of 8000.

Moreover, if overflow seems unlikely, consider that this overflows at a rate of
merely 2gigabits per microsecond, which is actually just 268 kBps.

Suggest just using InSecondsF() and explicitly comparing to max int.

Also suggest a test for the overflow case.

[tbansal1, 2015/06/12 19:14:46]

Fixed but how is 2 gigabits per microsecond ==  268 kBps?

Also, not sure how to write a test that is not flaky. I can pass INT_MAX bytes
to this function, but that does not guarantee it will trigger overflow detection
and correction (depending on how long machine sleeps etc.).

[mmenke, 2015/06/12 19:36:06]

Sorry, my mistake.  What I meant was this overflows when
cumulative_prefilter_bytes_read is 268k, which is gets you 8000 * 268,000 =
2,000,000,000, and I was thinking we divide by microseconds, so...it must by 268
kbps!  (Oops)
The bytes read we pass in is an int64.  If we pass in 2.21 petabytes, regardless
of any skew in the time, that should be enough, no?

[tbansal1, 2015/06/12 19:56:26]

Not sure. Because |cumulative_prefilter_bytes_read| is int64_t, the product has
to hit 2,000,000,000 * 2,000,000,000 (not just 2,000,000,000). And,
InMicroseconds() is int64 too.

Btw, I totally agree that this was probably confusing. The updated method is
cleaner.
If 2.21 petabytes are received in 1 petaseconds, then there won;t be an
overflow. But yeah, 1 peta second is obviously impossible. So, added the test.

[mmenke, 2015/06/12 20:31:41]

Ah, right.  I realized that yesterday, but today is Friday (which changes
everything).  :)

+      if (kbps > peak_kbps_since_last_connection_change_)
+        peak_kbps_since_last_connection_change_ = kbps;
+
+      kbps_observations_.AddObservation(Observation(kbps, now));

[mmenke, 2015/06/12 18:08:18]

Also, I wonder about repeatedly adding observations for the same download.  One
download from a slow server completely swamps everything else.  Wonder if it
would be better to more of a cumulative bandwidth thing - add up all new bytes
received over a unit of time, and use that for the estimate.  Admittedly,
doesn't handle the case where we aren't fully utilizing out bandwidth.

Anyhow, just a thought for another time - not suggesting you rework this CL.

[tbansal1, 2015/06/12 19:14:46]

Yes, I have been playing around with it. General observation is that
bandwidth estimate is more accurate when there is more data. So, we plan to do
bandwidth sampling at the end of the request.

[mmenke, 2015/06/12 19:36:06]

You could also try subtracting out 1/2 of rtt from the duration, and see if that
helps (Once you switch to using LoadTimingInfo).

[tbansal1, 2015/06/12 19:56:26]

Good suggestion. Will do that.

+    }
   }
 }
 
 void NetworkQualityEstimator::OnConnectionTypeChanged(
     NetworkChangeNotifier::ConnectionType type) {
   DCHECK(thread_checker_.CalledOnValidThread());
-  if (bytes_read_since_last_connection_change_) {
+  if (fastest_rtt_since_last_connection_change_ != base::TimeDelta::Max()) {
     switch (current_connection_type_) {
       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_ETHERNET:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Ethernet",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_WIFI:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_2G:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.2G",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_3G:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.3G",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_4G:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.4G",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_NONE:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Bluetooth",
-                            fastest_RTT_since_last_connection_change_);
+                            fastest_rtt_since_last_connection_change_);
         break;
       default:
         NOTREACHED();
         break;
     }
   }
 
   if (peak_kbps_since_last_connection_change_) {
     switch (current_connection_type_) {
       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
@@ skipping 28 matching lines @@
         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Bluetooth",
                              peak_kbps_since_last_connection_change_);
         break;
       default:
         NOTREACHED();
         break;
     }
   }
 
   last_connection_change_ = base::TimeTicks::Now();
-  bytes_read_since_last_connection_change_ = false;
   peak_kbps_since_last_connection_change_ = 0;
+  fastest_rtt_since_last_connection_change_ = base::TimeDelta::Max();
+  kbps_observations_.Clear();
+  rtt_msec_observations_.Clear();
   current_connection_type_ = type;
 }
 
-NetworkQuality NetworkQualityEstimator::GetEstimate() const {
+NetworkQuality NetworkQualityEstimator::GetPeakEstimate() const {
   DCHECK(thread_checker_.CalledOnValidThread());
 
-  if (!bytes_read_since_last_connection_change_) {
-    return NetworkQuality(fastest_RTT_since_last_connection_change_, 0,
-                          peak_kbps_since_last_connection_change_, 0);
-  }
-  if (!peak_kbps_since_last_connection_change_) {
-    return NetworkQuality(fastest_RTT_since_last_connection_change_, 0.1,
-                          peak_kbps_since_last_connection_change_, 0);
-  }
-  return NetworkQuality(fastest_RTT_since_last_connection_change_, 0.1,
-                        peak_kbps_since_last_connection_change_, 0.1);
+  return NetworkQuality(fastest_rtt_since_last_connection_change_,
+                        peak_kbps_since_last_connection_change_);
+}
+
+NetworkQualityEstimator::Observation::Observation(int32_t value,
+                                                  base::TimeTicks timestamp)
+    : value(value), timestamp(timestamp) {
+  DCHECK_GE(value, 0);
+  DCHECK(!timestamp.is_null());
+}
+
+NetworkQualityEstimator::Observation::~Observation() {
+}
+
+NetworkQualityEstimator::ObservationBuffer::ObservationBuffer() {
+  static_assert(kMaximumObservations > 0U,
+                "Minimum size of observation buffer must be > 0");
+}
+
+NetworkQualityEstimator::ObservationBuffer::~ObservationBuffer() {
+}
+
+void NetworkQualityEstimator::ObservationBuffer::AddObservation(
+    const Observation& observation) {
+  DCHECK_LE(observations_.size(), kMaximumObservations);
+  // Evict the oldest element if the buffer is already full.
+  if (observations_.size() == kMaximumObservations)
+    observations_.pop_front();
+
+  observations_.push_back(observation);
+  DCHECK_LE(observations_.size(), kMaximumObservations);
+}
+
+size_t NetworkQualityEstimator::ObservationBuffer::Size() const {
+  return observations_.size();
+}
+
+void NetworkQualityEstimator::ObservationBuffer::Clear() {
+  observations_.clear();
+  DCHECK(observations_.empty());
 }
 
 }  // namespace net