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;

[pauljensen, 2015/06/17 14:19:15]

Please add a comment like this or preferably address the issue:

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.

As it stands now, your logic to purge the oldest entry makes adding one entry to
the cache O(n) where n is kMaximumNetworkQualityCacheSize, and filling the cache
is O(n^2).
Here's a little example of a doubly-linked-list LRU queue and map:
http://stackoverflow.com/questions/2057424/lru-implementation-in-production-code
If you're going to add the comment, maybe adding a static_assert that checks
kMaximumNetworkQualityCacheSize <= 10 is appropriate next to the other
static_assert for kMaximumNetworkQualityCacheSize and putting the comment there
is a good idea.

[pauljensen, 2015/06/17 14:32:45]

Another benefit to switching to an LRU queue is that we can remove the reliance
on comparing TimeTicks::Now() values.  Matt mentioned horror stories about
different processor cores exhibiting Now() values significantly out of skew from
other cores.  Probably doesn't come in to play for your code (single threaded,
hopefully large Now() separation) but good future-proofing.

[tbansal1, 2015/06/17 21:18:45]

Thats a valid point but I think here for some reason, if a recent entry is
evicted (instead of the oldest one), it would still be okay. This cache is
already best effort and probably code simplicity trumps slightly more accuracy
that we can achieve by using double linked list + map. WDYT? I remember Ben once
suggesting that I should just randomly remove some entry and don't even keep
timestamps.

[tbansal1, 2015/06/17 21:18:46]

Done.
Yes, I thought of using map + deque, but I suspected that code complexity is not
worth it (unless the combined data structure is already available somewhere in
Chromium). Further, this happens only on network change, which is rare and
already too slow (just something to note when considering trade-offs). Also,
IIUC, complexity of filling cache is not really important because it happens
over a long period of time (e.g, on average, device may take at least a few
hours to switch over 10 different networks).
Done

+
 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::GetConnectionType(), 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");
   NetworkChangeNotifier::AddConnectionTypeObserver(this);
+  current_network_id_.id = GetCurrentNetworkName();
 }
 
 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_.type = type;
+  current_network_id_.id = GetCurrentNetworkName();
+
+  // 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 {
+  DCHECK(thread_checker_.CalledOnValidThread());
   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) {
   DCHECK_GE(value, 0);
   DCHECK(!timestamp.is_null());
 }
@@ skipping 22 matching lines @@
 
 size_t NetworkQualityEstimator::ObservationBuffer::Size() const {
   return observations_.size();
 }
 
 void NetworkQualityEstimator::ObservationBuffer::Clear() {
   observations_.clear();
   DCHECK(observations_.empty());
 }
 
+std::string NetworkQualityEstimator::GetCurrentNetworkName() const {
+  // TODO(tbansal): crbug.com/498068 Add NetworkQualityEstimatorAndroid class
+  // that overrides this method on the Android platform.
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  switch (current_network_id_.type) {

[pauljensen, 2015/06/17 14:19:15]

This is racy.  You're using a potentially old value (current_network_id_.type)
and assuming it's current.  A similar race caused crashes in the
NetworkChangeNotifierAutoDetect, see crrev.com/844146e.
I don't know of a great solution that doesn't require a fair bit of work.
I'd prefer we changed GetCurrentNetworkName to GetCurrentNetworkID.  This will
avoid the split initialization on lines 45 and 54, and at least reduce the race
to one function making it easier to fix later.
You could do something really ugly like:
do {
  type = getCurrentType()
  if (type == wifi) id = GetWifiSSID();
} while (type != getCurrentType())

[tbansal1, 2015/06/17 21:18:46]

Thanks for catching this. I made the change but this required making changes at
several other places. Done.

+    case NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_NONE:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_BLUETOOTH:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_ETHERNET:
+      return std::string();
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_WIFI:
+#if defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS)
+      return GetWifiSSID();
+#else
+      return std::string();

[pauljensen, 2015/06/17 14:19:15]

Does this mean every WiFi network will match every other WiFi network in the
cache?  Please fix this.

[tbansal1, 2015/06/17 21:18:46]

Yes, it does mean that on unsupported OSes. My previous logic was to not cache
if the SSID is unavailable. However, we had a discussion where we weighed the
pros/cons: Argument was that the slightly inaccurate value is better than no
value at all. Slightly inaccurate because of the hypothesis that it is likely
that users are always on slow Wi-Fi networks or always on fast Wi-Fi networks.

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

I don't think I agree with that.  We already have logic to indicate when there
is no estimate available, I think we should use it in this case.  I don't think
one Wi-Fi's quality gives much information about another Wi-Fi's quality.  When
someone changes Wi-Fi networks, they generally do so because one is
significantly better than the other, the O/S's Wi-Fi logic generally has high
hysteresis for changing APs.
If this becomes a big problem, it shouldn't be too hard to implement
GetWifiSSID() for windows.

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

I don't think I feel strongly either way (especially since I do not have any
data to backup either approach). Removed read/write to cache if the network name
is unavailable. Also, added test.

+#endif
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_2G:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_3G:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_4G:
+#if defined(OS_ANDROID)
+      return android::GetTelephonyNetworkOperator();
+#else
+      return std::string();
+#endif
+    default:
+      NOTREACHED() << "Unexpected connection type = "
+                   << current_network_id_.type;
+      return std::string();
+  }
+}
+
+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);
+    return;
+  }
+
+  if (cached_network_qualities_.size() == kMaximumNetworkQualityCacheSize) {
+    // Remove the oldest entry.
+    CachedNetworkQualities::iterator oldest_entry_iterator =
+        cached_network_qualities_.begin();
+
+    for (CachedNetworkQualities::iterator iterator =
+             cached_network_qualities_.begin();
+         iterator != cached_network_qualities_.end(); ++iterator) {
+      if ((oldest_entry_iterator->second)->last_update_time() >
+          (iterator->second)->last_update_time()) {
+        oldest_entry_iterator = iterator;
+      }
+    }
+    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() {
+}
+
+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