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

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 <limits>
 #include <string>
 
 #include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
 #include "base/metrics/histogram.h"
+#include "build/build_config.h"
 #include "net/base/load_timing_info.h"
 #include "net/base/net_util.h"
-#include "net/base/network_quality.h"
+#include "net/base/network_interfaces.h"
 #include "net/url_request/url_request.h"
 #include "url/gurl.h"
 
-namespace {
-
-// Maximum number of observations that can be held in the ObservationBuffer.
-const size_t kMaximumObservationsBufferSize = 500;
-
-}  // namespace
+#if defined(OS_ANDROID)
+#include "net/android/network_library.h"
+#endif  // OS_ANDROID
 
 namespace net {
 
+const size_t NetworkQualityEstimator::kMaximumNetworkQualityCacheSize;
+
+const size_t NetworkQualityEstimator::kMaximumObservationsBufferSize;
+
 NetworkQualityEstimator::NetworkQualityEstimator()
     : NetworkQualityEstimator(false, false) {
 }
 
 NetworkQualityEstimator::NetworkQualityEstimator(
     bool allow_local_host_requests_for_tests,
     bool allow_smaller_responses_for_tests)
     : 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()),
+      current_network_id_(
+          NetworkID(NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN,
+                    std::string())),
       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");
+  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");
   NetworkChangeNotifier::AddConnectionTypeObserver(this);
+  current_network_id_ = GetCurrentNetworkID();
 }
 
 NetworkQualityEstimator::~NetworkQualityEstimator() {
   DCHECK(thread_checker_.CalledOnValidThread());
   NetworkChangeNotifier::RemoveConnectionTypeObserver(this);
 }
 
 void NetworkQualityEstimator::NotifyDataReceived(
     const URLRequest& request,
     int64_t cumulative_prefilter_bytes_read,
@@ skipping 76 matching lines @@
 
       kbps_observations_.AddObservation(Observation(kbps, now));
     }
   }
 }
 
 void NetworkQualityEstimator::OnConnectionTypeChanged(
     NetworkChangeNotifier::ConnectionType type) {
   DCHECK(thread_checker_.CalledOnValidThread());
   if (fastest_rtt_since_last_connection_change_ != base::TimeDelta::Max()) {
-    switch (current_connection_type_) {
+    switch (current_network_id_.type) {
       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
                             fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_ETHERNET:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Ethernet",
                             fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_WIFI:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi",
@@ skipping 13 matching lines @@
         break;
       case NetworkChangeNotifier::CONNECTION_NONE:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None",
                             fastest_rtt_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Bluetooth",
                             fastest_rtt_since_last_connection_change_);
         break;
       default:
-        NOTREACHED();
+        NOTREACHED() << "Unexpected connection type = "
+                     << current_network_id_.type;
         break;
     }
   }
 
   if (peak_kbps_since_last_connection_change_) {
-    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_);
         break;
       case NetworkChangeNotifier::CONNECTION_ETHERNET:
         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Ethernet",
                              peak_kbps_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_WIFI:
         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Wifi",
@@ skipping 13 matching lines @@
         break;
       case NetworkChangeNotifier::CONNECTION_NONE:
         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.None",
                              peak_kbps_since_last_connection_change_);
         break;
       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Bluetooth",
                              peak_kbps_since_last_connection_change_);
         break;
       default:
-        NOTREACHED();
+        NOTREACHED() << "Unexpected connection type = "
+                     << current_network_id_.type;
         break;
     }
   }
 
+  // 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_ = 0;
   fastest_rtt_since_last_connection_change_ = base::TimeDelta::Max();
   kbps_observations_.Clear();
   rtt_msec_observations_.Clear();
-  current_connection_type_ = type;
+
+  // Update the current network ID.
+  current_network_id_ = GetCurrentNetworkID();
+
+  // Read any cached estimates for the new network.
+  ReadCachedNetworkQualityEstimate();
+}
+
+size_t NetworkQualityEstimator::GetNetworkQualityCacheSizeForTests() const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  return cached_network_qualities_.size();
 }
 
 NetworkQuality NetworkQualityEstimator::GetPeakEstimate() const {
   DCHECK(thread_checker_.CalledOnValidThread());
 
   return NetworkQuality(fastest_rtt_since_last_connection_change_,
                         peak_kbps_since_last_connection_change_);
 }
 
-size_t NetworkQualityEstimator::GetMaximumObservationBufferSizeForTests()
-    const {
-  return kMaximumObservationsBufferSize;
+size_t NetworkQualityEstimator::GetKbpsObservationBufferSizeForTests() const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  return kbps_observations_.Size();
 }
 
-bool NetworkQualityEstimator::VerifyBufferSizeForTests(
-    size_t expected_size) const {
-  return kbps_observations_.Size() == expected_size &&
-         rtt_msec_observations_.Size() == expected_size;
+size_t NetworkQualityEstimator::GetRTTObservationBufferSizeForTests() const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  return rtt_msec_observations_.Size();
 }
 
 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(kMaximumObservationsBufferSize > 0U,
                 "Minimum size of observation buffer must be > 0");
 }
 
 NetworkQualityEstimator::ObservationBuffer::~ObservationBuffer() {
 }
 
 void NetworkQualityEstimator::ObservationBuffer::AddObservation(
     const Observation& observation) {
-  DCHECK_LE(observations_.size(), kMaximumObservationsBufferSize);
+  DCHECK_LE(observations_.size(),
+            NetworkQualityEstimator::kMaximumObservationsBufferSize);

[pauljensen, 2015/06/22 18:39:52]

Is NetworkQualityEstimator:: really necessary? Ditto for the other spots in this
file.

[tbansal1, 2015/06/22 20:28:25]

Its not really needed in this file but only in the unittest.cc. Removed.

   // Evict the oldest element if the buffer is already full.
-  if (observations_.size() == kMaximumObservationsBufferSize)
+  if (observations_.size() ==
+      NetworkQualityEstimator::kMaximumObservationsBufferSize)
     observations_.pop_front();
 
   observations_.push_back(observation);
-  DCHECK_LE(observations_.size(), kMaximumObservationsBufferSize);
+  DCHECK_LE(observations_.size(),
+            NetworkQualityEstimator::kMaximumObservationsBufferSize);
 }
 
 size_t NetworkQualityEstimator::ObservationBuffer::Size() const {
   return observations_.size();
 }
 
 void NetworkQualityEstimator::ObservationBuffer::Clear() {
   observations_.clear();
   DCHECK(observations_.empty());
 }
 
+NetworkQualityEstimator::NetworkID
+NetworkQualityEstimator::GetCurrentNetworkID() const {
+  // 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());
+
+    DCHECK(thread_checker_.CalledOnValidThread());
+
+    switch (network_id.type) {
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN:
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_NONE:
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_BLUETOOTH:
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_ETHERNET:
+        break;
+      case NetworkChangeNotifier::ConnectionType::CONNECTION_WIFI:
+#if defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS)
+        network_id.id = GetWifiSSID();

[pauljensen, 2015/06/22 18:39:52]

We should implement this for windows.  It should be quite easy.  Is there a bug
filed for this?

[tbansal1, 2015/06/22 20:28:25]

Filed crbug.com/503235

+        break;
+#else
+        break;
+#endif
+      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
+      default:
+        NOTREACHED() << "Unexpected connection type = " << network_id.type;
+    }
+
+    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()) {
+    // TOOD(tbansal): Populate these values back into the median computing
+    // algorithm.
+    // Add UMA to record how frequently matches happen.

[pauljensen, 2015/06/22 18:39:52]

Add a "TODO(tbansal):" here and the next line

[tbansal1, 2015/06/22 20:28:26]

Done.

+    // Ensure that the estimates read are non-zero before populating them into
+    // the median computing algorithm.
+    peak_kbps_since_last_connection_change_ =
+        it->second->network_quality().downstream_throughput_kbps();
+    fastest_rtt_since_last_connection_change_ =
+        it->second->network_quality().rtt();
+    return true;
+  }
+  return false;
+}
+
+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;
+
+  // TODO(tbansal): The following variables should be initialized using the
+  // median values reported by the NetworkQualityEstimator.
+  int median_kbps = peak_kbps_since_last_connection_change_;
+  base::TimeDelta median_rtt = fastest_rtt_since_last_connection_change_;
+
+  // If this network is already in the cache, overwrite that entry.
+  CachedNetworkQualities::iterator it =
+      cached_network_qualities_.find(current_network_id_);
+  if (it != cached_network_qualities_.end()) {
+    (it->second)->UpdateNetworkQuality(median_kbps, median_rtt);
+    return;
+  }
+
+  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_.insert(std::make_pair(
+      current_network_id_, make_scoped_ptr(new CachedNetworkQuality(
+                               NetworkQuality(median_rtt, median_kbps)))));
+  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_;
+}
+
+void NetworkQualityEstimator::CachedNetworkQuality::UpdateNetworkQuality(
+    int32_t median_kbps,
+    const base::TimeDelta& median_rtt) {
+  DCHECK_GE(median_kbps, 0);
+  DCHECK_GE(median_rtt, base::TimeDelta());
+  last_update_time_ = base::TimeTicks::Now();
+
+  network_quality_ = NetworkQuality(median_rtt, median_kbps);
+}
+
 }  // namespace net