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"
 
+#if defined(OS_ANDROID)
+#include "net/android/network_library.h"
+#endif  // OS_ANDROID
+
 namespace {
 
 // Maximum number of observations that can be held in the ObservationBuffer.
 const size_t kMaximumObservationsBufferSize = 500;
 
 }  // namespace
 
 namespace net {
 
+const size_t NetworkQualityEstimator::kMaximumNetworkQualityCacheSize = 10;
+
 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 {
+  DCHECK(thread_checker_.CalledOnValidThread());
   return kMaximumObservationsBufferSize;
 }
 
-bool NetworkQualityEstimator::VerifyBufferSizeForTests(
-    size_t expected_size) const {
-  return kbps_observations_.Size() == expected_size &&
-         rtt_msec_observations_.Size() == expected_size;
+size_t NetworkQualityEstimator::GetKbpsObservationBufferSizeForTests() const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  return kbps_observations_.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() {
@@ skipping 20 matching lines @@
 
 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.
+  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();
+      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;
+  }
+  // Due to race, it is possible that the connection type changed between when

[pauljensen, 2015/06/18 16:20:26]

Remove "Due to race, "

[tbansal1, 2015/06/18 20:57:40]

Done.

+  // GetCurrentConnectionType() was read and when network name was read.

[pauljensen, 2015/06/18 16:20:25]

network->the network

[pauljensen, 2015/06/18 16:20:26]

read->called

[tbansal1, 2015/06/18 20:57:40]

Done.

[tbansal1, 2015/06/18 20:57:40]

Done.

+  // Check if that happened and retry.

[pauljensen, 2015/06/18 16:20:26]

Mention that this isn't perfect but should catch the majority of cases, and this
is just an estimate anyhow.

[tbansal1, 2015/06/18 20:57:40]

Done.

+  if (network_id.type != NetworkChangeNotifier::GetConnectionType())
+    return GetCurrentNetworkID();

[pauljensen, 2015/06/18 16:20:26]

Please use a loop rather than recursion.  Waiting a long time is better than
crashing quickly from stack overflow.

[tbansal1, 2015/06/18 20:57:41]

Using while(true) now, which I found to be slightly cleaner -- I can define and
declare NetworkID inside the loop. Using do-while, I had to declare it before
the loop and update it inside the loop. WDYT?

[pauljensen, 2015/06/19 03:10:07]

SGTM

+  return network_id;
+}
+
+bool NetworkQualityEstimator::ReadCachedNetworkQualityEstimate() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  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.
+    // 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);
+
+  // 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);

[pauljensen, 2015/06/19 03:10:07]

This in-place update seems odd.  Why not just:
  cached_network_qualities_[current_network_id_] = CachedNetworkQuality(...)
and then you can remove UpdateNetworkQuality() and make the members of
CachedNetworkQuality const.

[tbansal1, 2015/06/19 23:34:40]

For this, I will need to overload = operator for CachedNetworkQuality. That
prevents me from making members of CachedNetworkQuality const.

Other option is to reset the scoped ptr in the map by creating a new
CachedNetworkQuality oject. This will call the constructor and not the
assignment operator. That way I can make members of CachedNetworkQuality as
const and not have to overload = operator. Please let me know if that SGTY? My
only concern was that we would be calling destructor and constructor but I am
not sure if that's a valid concern. Thanks. 

[pauljensen, 2015/06/20 01:30:45]

SGTM
Fine; they're already non-const.

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

You never implemented this change.

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

Took a slightly different approach which allowed me to make members of
CachedNetworkQuality const. Done. This simplified a lot. Thanks.

+    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