Add in-memory caching of network quality estimates across network changes.

net/base/network_quality_estimator.cc

Index: net/base/network_quality_estimator.cc
diff --git a/net/base/network_quality_estimator.cc b/net/base/network_quality_estimator.cc
index 1e84fb1bfdaff473cee94a2821d8d27f6e374d3c..a5bbbadd61a2933ea5385514f7ad50d597b3eb21 100644
--- a/net/base/network_quality_estimator.cc
+++ b/net/base/network_quality_estimator.cc
@@ -8,7 +8,6 @@
 #include <algorithm>
 #include <cmath>
 #include <limits>
-#include <string>
 #include <vector>
 
 #include "base/logging.h"
@@ -16,16 +15,19 @@
 #include "base/metrics/histogram_base.h"
 #include "base/strings/safe_sprintf.h"
 #include "base/strings/string_number_conversions.h"
+#include "build/build_config.h"
 #include "net/base/load_flags.h"
 #include "net/base/load_timing_info.h"
 #include "net/base/net_util.h"
+#include "net/base/network_interfaces.h"
 #include "net/url_request/url_request.h"
 #include "url/gurl.h"
 
-namespace {
+#if defined(OS_ANDROID)
+#include "net/android/network_library.h"
+#endif  // OS_ANDROID
 
-// Maximum number of observations that can be held in the ObservationBuffer.
-const size_t kMaximumObservationsBufferSize = 300;
+namespace {
 
 // Default value of the half life (in seconds) for computing time weighted
 // percentiles. Every half life, the weight of all observations reduces by
@@ -115,6 +117,10 @@ base::HistogramBase* GetHistogram(
 
 namespace net {
 
+const size_t NetworkQualityEstimator::kMaximumNetworkQualityCacheSize = 10;

[pauljensen, 2015/07/14 11:59:03]

how about initializing this in the header like the other constants there?

[tbansal1, 2015/07/14 19:51:48]

I get linking error:
../../net/base/network_quality_estimator.cc:692: error: undefined reference to
'net::NetworkQualityEstimator::kMaximumNetworkQualityCacheSize'

I believe it is because it is size_t. Changing it to int fixes the error.

[pauljensen, 2015/07/14 20:19:59]

Can you track this down further?  Use objdump or nm to figure out if the
definition is present or if the symbol names don't match or what is going on
here.  Is it related to NET_EXPORT_PRIVATE?
There are litterally hundreds of instances of this elsewhere in Chrome:
https://code.google.com/p/chromium/codesearch#search/&q=%22static%20const%20s...

+
+const size_t NetworkQualityEstimator::kMaximumObservationsBufferSize = 300;

[pauljensen, 2015/07/14 11:59:03]

ditto

[tbansal1, 2015/07/14 19:51:48]

See reply above.

+
 NetworkQualityEstimator::NetworkQualityEstimator(
     const std::map<std::string, std::string>& variation_params)
     : NetworkQualityEstimator(variation_params, false, false) {
@@ -127,20 +133,26 @@ NetworkQualityEstimator::NetworkQualityEstimator(
     : allow_localhost_requests_(allow_local_host_requests_for_tests),
       allow_small_responses_(allow_smaller_responses_for_tests),
       last_connection_change_(base::TimeTicks::Now()),
-      current_connection_type_(NetworkChangeNotifier::GetConnectionType()),
-      fastest_rtt_since_last_connection_change_(NetworkQuality::InvalidRTT()),
-      peak_kbps_since_last_connection_change_(
-          NetworkQuality::kInvalidThroughput),
+      current_network_id_(
+          NetworkID(NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN,
+                    std::string())),
       kbps_observations_(GetWeightMultiplierPerSecond(variation_params)),
       rtt_msec_observations_(GetWeightMultiplierPerSecond(variation_params)) {
   static_assert(kMinRequestDurationMicroseconds > 0,
                 "Minimum request duration must be > 0");
   static_assert(kDefaultHalfLifeSeconds > 0,
                 "Default half life duration must be > 0");
+  static_assert(kMaximumNetworkQualityCacheSize > 0,
+                "Size of the network quality cache must be > 0");
+  // This limit should not be increased unless the logic for removing the
+  // oldest cache entry is rewritten to use a doubly-linked-list LRU queue.
+  static_assert(kMaximumNetworkQualityCacheSize <= 10,
+                "Size of the network quality cache must <= 10");
 
   ObtainOperatingParams(variation_params);
-  AddDefaultEstimates();
   NetworkChangeNotifier::AddConnectionTypeObserver(this);
+  current_network_id_ = GetCurrentNetworkID();
+  AddDefaultEstimates();
 }
 
 void NetworkQualityEstimator::ObtainOperatingParams(
@@ -182,18 +194,16 @@ void NetworkQualityEstimator::ObtainOperatingParams(
 
 void NetworkQualityEstimator::AddDefaultEstimates() {
   DCHECK(thread_checker_.CalledOnValidThread());
-
-  if (default_observations_[current_connection_type_].rtt() !=
+  if (default_observations_[current_network_id_.type].rtt() !=
       NetworkQuality::InvalidRTT()) {
     rtt_msec_observations_.AddObservation(Observation(
-        default_observations_[current_connection_type_].rtt().InMilliseconds(),
+        default_observations_[current_network_id_.type].rtt().InMilliseconds(),
         base::TimeTicks::Now()));
   }
-
-  if (default_observations_[current_connection_type_]
+  if (default_observations_[current_network_id_.type]
           .downstream_throughput_kbps() != NetworkQuality::kInvalidThroughput) {
     kbps_observations_.AddObservation(
-        Observation(default_observations_[current_connection_type_]
+        Observation(default_observations_[current_network_id_.type]
                         .downstream_throughput_kbps(),
                     base::TimeTicks::Now()));
   }
@@ -250,8 +260,10 @@ void NetworkQualityEstimator::NotifyDataReceived(
     // headers were received.
     base::TimeDelta observed_rtt = headers_received_time - request_start_time;
     DCHECK_GE(observed_rtt, base::TimeDelta());
-    if (observed_rtt < fastest_rtt_since_last_connection_change_)
-      fastest_rtt_since_last_connection_change_ = observed_rtt;
+    if (observed_rtt < peak_network_quality_.rtt()) {
+      peak_network_quality_ = NetworkQuality(
+          observed_rtt, peak_network_quality_.downstream_throughput_kbps());
+    }
 
     rtt_msec_observations_.AddObservation(
         Observation(observed_rtt.InMilliseconds(), now));
@@ -292,8 +304,10 @@ void NetworkQualityEstimator::NotifyDataReceived(
       kbps = 1;
 
     if (kbps > 0) {
-      if (kbps > peak_kbps_since_last_connection_change_)
-        peak_kbps_since_last_connection_change_ = kbps;
+      if (kbps > peak_network_quality_.downstream_throughput_kbps()) {
+        peak_network_quality_ =
+            NetworkQuality(peak_network_quality_.rtt(), kbps);
+      }
 
       kbps_observations_.AddObservation(Observation(kbps, now));
     }
@@ -308,18 +322,18 @@ void NetworkQualityEstimator::RecordRTTUMA(int32_t estimated_value_msec,
   if (estimated_value_msec >= actual_value_msec) {
     base::HistogramBase* difference_rtt =
         GetHistogram("DifferenceRTTEstimatedAndActual.",
-                     current_connection_type_, 10 * 1000);  // 10 seconds
+                     current_network_id_.type, 10 * 1000);  // 10 seconds
     difference_rtt->Add(estimated_value_msec - actual_value_msec);
   } else {
     base::HistogramBase* difference_rtt =
         GetHistogram("DifferenceRTTActualAndEstimated.",
-                     current_connection_type_, 10 * 1000);  // 10 seconds
+                     current_network_id_.type, 10 * 1000);  // 10 seconds
     difference_rtt->Add(actual_value_msec - estimated_value_msec);
   }
 
   // Record all the RTT observations.
   base::HistogramBase* rtt_observations =
-      GetHistogram("RTTObservations.", current_connection_type_,
+      GetHistogram("RTTObservations.", current_network_id_.type,
                    10 * 1000);  // 10 seconds upper bound
   rtt_observations->Add(actual_value_msec);
 
@@ -331,91 +345,95 @@ void NetworkQualityEstimator::RecordRTTUMA(int32_t estimated_value_msec,
   // Record the accuracy of estimation by recording the ratio of estimated
   // value to the actual value.
   base::HistogramBase* ratio_median_rtt = GetHistogram(
-      "RatioEstimatedToActualRTT.", current_connection_type_, 1000);
+      "RatioEstimatedToActualRTT.", current_network_id_.type, 1000);
   ratio_median_rtt->Add(ratio);
 }
 
 void NetworkQualityEstimator::OnConnectionTypeChanged(
     NetworkChangeNotifier::ConnectionType type) {
   DCHECK(thread_checker_.CalledOnValidThread());
-  if (fastest_rtt_since_last_connection_change_ !=
-      NetworkQuality::InvalidRTT()) {
-    switch (current_connection_type_) {
+  if (peak_network_quality_.rtt() != NetworkQuality::InvalidRTT()) {
+    switch (current_network_id_.type) {
       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
-                            fastest_rtt_since_last_connection_change_);
+                            peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_ETHERNET:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Ethernet",
-                            fastest_rtt_since_last_connection_change_);
+                            peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_WIFI:
-        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi",
-                            fastest_rtt_since_last_connection_change_);
+        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi", peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_2G:
-        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.2G",
-                            fastest_rtt_since_last_connection_change_);
+        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.2G", peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_3G:
-        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.3G",
-                            fastest_rtt_since_last_connection_change_);
+        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.3G", peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_4G:
-        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.4G",
-                            fastest_rtt_since_last_connection_change_);
+        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.4G", peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_NONE:
-        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None",
-                            fastest_rtt_since_last_connection_change_);
+        UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None", peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Bluetooth",
-                            fastest_rtt_since_last_connection_change_);
+                            peak_network_quality_.rtt());
         break;
       default:
-        NOTREACHED();
+        NOTREACHED() << "Unexpected connection type = "
+                     << current_network_id_.type;
         break;
     }
   }
 
-  if (peak_kbps_since_last_connection_change_ !=
+  if (peak_network_quality_.downstream_throughput_kbps() !=
       NetworkQuality::kInvalidThroughput) {
-    switch (current_connection_type_) {
+    switch (current_network_id_.type) {
       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Unknown",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.Unknown",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       case NetworkChangeNotifier::CONNECTION_ETHERNET:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Ethernet",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.Ethernet",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       case NetworkChangeNotifier::CONNECTION_WIFI:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Wifi",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.Wifi",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       case NetworkChangeNotifier::CONNECTION_2G:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.2G",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.2G",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       case NetworkChangeNotifier::CONNECTION_3G:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.3G",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.3G",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       case NetworkChangeNotifier::CONNECTION_4G:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.4G",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.4G",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       case NetworkChangeNotifier::CONNECTION_NONE:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.None",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.None",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
-        UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Bluetooth",
-                             peak_kbps_since_last_connection_change_);
+        UMA_HISTOGRAM_COUNTS(
+            "NQE.PeakKbps.Bluetooth",
+            peak_network_quality_.downstream_throughput_kbps());
         break;
       default:
-        NOTREACHED();
+        NOTREACHED() << "Unexpected connection type = "
+                     << current_network_id_.type;
         break;
     }
   }
@@ -424,7 +442,7 @@ void NetworkQualityEstimator::OnConnectionTypeChanged(
   if (GetEstimate(&network_quality)) {
     // Add the 50th percentile value.
     base::HistogramBase* rtt_percentile =
-        GetHistogram("RTT.Percentile50.", current_connection_type_,
+        GetHistogram("RTT.Percentile50.", current_network_id_.type,
                      10 * 1000);  // 10 seconds
     rtt_percentile->Add(network_quality.rtt().InMilliseconds());
 
@@ -438,27 +456,32 @@ void NetworkQualityEstimator::OnConnectionTypeChanged(
 
       rtt_percentile = GetHistogram(
           "RTT.Percentile" + std::string(percentile_stringified) + ".",
-          current_connection_type_, 10 * 1000);  // 10 seconds
+          current_network_id_.type, 10 * 1000);  // 10 seconds
       rtt_percentile->Add(network_quality.rtt().InMilliseconds());
     }
   }
 
+  // Write the estimates of the previous network to the cache.
+  CacheNetworkQualityEstimate();
+
+  // Clear the local state.
   last_connection_change_ = base::TimeTicks::Now();
-  peak_kbps_since_last_connection_change_ = NetworkQuality::kInvalidThroughput;
-  fastest_rtt_since_last_connection_change_ = NetworkQuality::InvalidRTT();
+  peak_network_quality_ = NetworkQuality();
   kbps_observations_.Clear();
   rtt_msec_observations_.Clear();
-  current_connection_type_ = type;
+  current_network_id_ = GetCurrentNetworkID();
 
-  AddDefaultEstimates();
+  // Read any cached estimates for the new network. If cached estimates are
+  // unavailable, add the default estimates.
+  if (!ReadCachedNetworkQualityEstimate())
+    AddDefaultEstimates();
   estimated_median_network_quality_ = NetworkQuality();
 }
 
 NetworkQuality NetworkQualityEstimator::GetPeakEstimate() const {
   DCHECK(thread_checker_.CalledOnValidThread());
 
-  return NetworkQuality(fastest_rtt_since_last_connection_change_,
-                        peak_kbps_since_last_connection_change_);
+  return peak_network_quality_;
 }
 
 bool NetworkQualityEstimator::GetEstimate(NetworkQuality* median) const {
@@ -470,17 +493,6 @@ bool NetworkQualityEstimator::GetEstimate(NetworkQuality* median) const {
   return true;
 }
 
-size_t NetworkQualityEstimator::GetMaximumObservationBufferSizeForTests()
-    const {
-  return kMaximumObservationsBufferSize;
-}
-
-bool NetworkQualityEstimator::VerifyBufferSizeForTests(
-    size_t expected_size) const {
-  return kbps_observations_.Size() == expected_size &&
-         rtt_msec_observations_.Size() == expected_size;
-}
-
 NetworkQualityEstimator::Observation::Observation(int32_t value,
                                                   base::TimeTicks timestamp)
     : value(value), timestamp(timestamp) {
@@ -596,4 +608,133 @@ int32_t NetworkQualityEstimator::ObservationBuffer::GetPercentile(
   return weighted_observations.at(weighted_observations.size() - 1).value;
 }
 
+NetworkQualityEstimator::NetworkID
+NetworkQualityEstimator::GetCurrentNetworkID() const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  // TODO(tbansal): crbug.com/498068 Add NetworkQualityEstimatorAndroid class
+  // that overrides this method on the Android platform.
+
+  // It is possible that the connection type changed between when
+  // GetConnectionType() was called and when the API to determine the
+  // network name was called. Check if that happened and retry until the
+  // connection type stabilizes. This is an imperfect solution but should
+  // capture majority of cases, and should not significantly affect estimates
+  // (that are approximate to begin with).
+  while (true) {
+    NetworkQualityEstimator::NetworkID network_id(
+        NetworkChangeNotifier::GetConnectionType(), std::string());
+
+    switch (network_id.type) {
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN:
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_NONE:
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_BLUETOOTH:
+        break;
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_ETHERNET:
+        network_id.id = "Ethernet";
+        break;
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_WIFI:
+#if defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS)
+        network_id.id = GetWifiSSID();
+        break;
+#else
+        break;
+#endif

[pauljensen, 2015/07/14 11:59:03]

#if ...
   ...
   break;
#else
   break;
#endif
->
#if ...
   ...
#endif
   break;

[tbansal1, 2015/07/14 19:51:48]

Done.

+      case NetworkChangeNotifier::ConnectionType::CONNECTION_2G:
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_3G:
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_4G:
+#if defined(OS_ANDROID)
+        network_id.id = android::GetTelephonyNetworkOperator();
+        break;
+#else
+        break;
+#endif

[pauljensen, 2015/07/14 11:59:02]

ditto

[tbansal1, 2015/07/14 19:51:47]

Done.

+      default:
+        NOTREACHED() << "Unexpected connection type = " << network_id.type;
+    }

[pauljensen, 2015/07/14 11:59:03]

break;

[tbansal1, 2015/07/14 19:51:48]

Done.

+
+    if (network_id.type == NetworkChangeNotifier::GetConnectionType())
+      return network_id;
+  }
+  NOTREACHED();
+}
+
+bool NetworkQualityEstimator::ReadCachedNetworkQualityEstimate() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  // If the network name is unavailable, caching should not be performed.
+  if (current_network_id_.id.empty())
+    return false;
+
+  CachedNetworkQualities::iterator it =
+      cached_network_qualities_.find(current_network_id_);
+
+  if (it == cached_network_qualities_.end())
+    return false;
+
+  NetworkQuality network_quality(
+      it->second->network_quality().rtt(),
+      it->second->network_quality().downstream_throughput_kbps());
+
+  DCHECK_NE(NetworkQuality::InvalidRTT(), network_quality.rtt());
+  DCHECK_NE(NetworkQuality::kInvalidThroughput,
+            network_quality.downstream_throughput_kbps());
+
+  kbps_observations_.AddObservation(Observation(
+      network_quality.downstream_throughput_kbps(), base::TimeTicks::Now()));
+  rtt_msec_observations_.AddObservation(Observation(
+      network_quality.rtt().InMilliseconds(), base::TimeTicks::Now()));
+  return true;
+}
+
+void NetworkQualityEstimator::CacheNetworkQualityEstimate() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK_LE(cached_network_qualities_.size(), kMaximumNetworkQualityCacheSize);
+
+  // If the network name is unavailable, caching should not be performed.
+  if (current_network_id_.id.empty())
+    return;
+
+  NetworkQuality network_quality;
+  if (!GetEstimate(&network_quality))
+    return;
+
+  DCHECK_NE(NetworkQuality::InvalidRTT(), network_quality.rtt());
+  DCHECK_NE(NetworkQuality::kInvalidThroughput,
+            network_quality.downstream_throughput_kbps());
+
+  if (cached_network_qualities_.size() == kMaximumNetworkQualityCacheSize) {
+    // Remove the oldest entry.
+    CachedNetworkQualities::iterator oldest_entry_iterator =
+        cached_network_qualities_.begin();
+
+    for (CachedNetworkQualities::iterator it =
+             cached_network_qualities_.begin();
+         it != cached_network_qualities_.end(); ++it) {
+      if ((it->second)->OlderThan(*(oldest_entry_iterator->second.get())))
+        oldest_entry_iterator = it;
+    }
+    cached_network_qualities_.erase(oldest_entry_iterator);
+  }
+  DCHECK_LT(cached_network_qualities_.size(), kMaximumNetworkQualityCacheSize);
+
+  cached_network_qualities_[current_network_id_].reset(
+      new CachedNetworkQuality(network_quality));
+  DCHECK_LE(cached_network_qualities_.size(), kMaximumNetworkQualityCacheSize);
+}
+
+NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
+    const NetworkQuality& network_quality)
+    : last_update_time_(base::TimeTicks::Now()),
+      network_quality_(network_quality) {
+}
+
+NetworkQualityEstimator::CachedNetworkQuality::~CachedNetworkQuality() {
+}
+
+bool NetworkQualityEstimator::CachedNetworkQuality::OlderThan(
+    const CachedNetworkQuality& cached_network_quality) const {
+  return last_update_time_ < cached_network_quality.last_update_time_;
+}
+
 }  // namespace net