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 <string>
-
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
+#include "build/build_config.h"
 #include "net/base/net_util.h"
+#include "net/base/network_interfaces.h"
 #include "net/base/network_quality.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 size of the cache that holds network quality estimates.
+// Smaller size may reduce the cache hit rate due to frequent evictions.
+// Larger size may affect performance.
+const uint32_t kMaximumNetworkQualityCacheSize = 10;
+
+}  // namespace
+
 namespace net {
 
 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),
       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);
+  UpdateCurrentNetworkName();
 }
 
 NetworkQualityEstimator::~NetworkQualityEstimator() {
   DCHECK(thread_checker_.CalledOnValidThread());
   NetworkChangeNotifier::RemoveConnectionTypeObserver(this);
 }
 
 void NetworkQualityEstimator::NotifyDataReceived(const URLRequest& request,
                                                  int64_t prefilter_bytes_read) {
   DCHECK(thread_checker_.CalledOnValidThread());
@@ skipping 62 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_connection_type_;
         break;
     }
   }
 
   if (peak_kbps_since_last_connection_change_) {
     switch (current_connection_type_) {
       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Unknown",
                              peak_kbps_since_last_connection_change_);
         break;
@@ skipping 19 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_connection_type_;
         break;
     }
   }
 
+  // Write the estimates of the previous network to the cache.
+  CacheNetworkQualityEstimate();
+
   last_connection_change_ = base::TimeTicks::Now();
   bytes_read_since_last_connection_change_ = false;
   peak_kbps_since_last_connection_change_ = 0;
   current_connection_type_ = type;
+  UpdateCurrentNetworkName();
+
+  // Read any cached estimates for the new network.
+  ReadCachedNetworkQualityEstimate();
+}
+
+size_t NetworkQualityEstimator::GetCacheSizeForTests() const {
+  return cached_network_quality_.size();
+}
+
+void NetworkQualityEstimator::SetCurrentNetworkNameForTests(
+    const std::string& network_name) {

[mmenke, 2015/06/08 20:34:19]

Suggest making UpdateCurrentNetworkName call a virtual GetCurrentNetworkName
method instead, and override it in tests.  That allows you to also validate we
update the network internally on network changes, by simulating an NCN
notification.

[tbansal1, 2015/06/09 02:23:13]

Done.

+  current_network_name_ = network_name;
 }
 
 NetworkQuality NetworkQualityEstimator::GetEstimate() 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);
 }
 
+void NetworkQualityEstimator::UpdateCurrentNetworkName() {
+  // TODO(tbansal): Add NetworkQualityEstimatorAndroid class that overrides
+  // this method on Android platform.

[mmenke, 2015/06/08 20:34:20]

Is there a bug for this that we could link to, to give context?

[tbansal1, 2015/06/09 02:23:13]

Done.

+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  current_network_name_ = std::string();
+  switch (current_connection_type_) {
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_NONE:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_BLUETOOTH:
+      return;
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_ETHERNET:
+      current_network_name_ = "ethernet";

[mmenke, 2015/06/08 20:34:20]

I don't think this is needed - we're recording network type and name in the
cache, right?

[tbansal1, 2015/06/09 02:23:13]

Yes, it was not really needed.

+      return;
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_WIFI:
+#if defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS)
+      current_network_name_ = GetWifiSSID();
+#endif  // defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS)
+      return;
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_2G:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_3G:
+    case NetworkChangeNotifier::ConnectionType::CONNECTION_4G:
+#if defined(OS_ANDROID)
+      current_network_name_ = android::GetTelephonyNetworkOperator();

[mmenke, 2015/06/08 20:34:19]

Suggest a struct:

struct NetworkID {
  ConnectionType type;
  std::string id;
};

Having a string "id" as part of NetworkID is a little weird, but I think it's
clearer than saying the "name" of a network is "ethernet" or the network
operator name.

Alternatively, could use prefixed strings ("wifi/" + GetWifiSSID(), "cell/" +
GetTelephonyNetworkOperator()).  Makes for simpler data structures, though does
lose a bit in clarity.

[tbansal1, 2015/06/09 02:23:13]

Done.

+#endif  // OS_ANDROID
+      return;
+    default:
+      NOTREACHED() << "Unexpected connection type = "
+                   << current_connection_type_;
+  }
+}
+
+bool NetworkQualityEstimator::ReadCachedNetworkQualityEstimate() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  for (const auto& network_quality : cached_network_quality_) {
+    if (!network_quality->MatchesNetwork(current_connection_type_,
+                                         current_network_name_)) {
+      continue;
+    }
+
+    // TOOD(tbansal): Populate these values back into the median computing
+    // algorithm.
+    // Add UMA to record how frequently match happens.
+    // int64 median_kbps = network_quality.median_kbps;
+    // int64 median_rtt_msec = network_quality.median_rtt_milliseconds;
+    // Ensure that the estimates read are non-zero before populating them into
+    // the median computing algorithm.
+    return true;
+  }
+
+  return false;
+}
+
+void NetworkQualityEstimator::CacheNetworkQualityEstimate() {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  // TODO(tbansal): Following variables should be initialized using the median
+  /// values reported by NetworkQualityEstimator.
+  int median_kbps = 0;
+  base::TimeDelta median_rtt;
+
+  // If this network is already in the cache, overwrite that entry.
+  for (auto& network_quality : cached_network_quality_) {

[mmenke, 2015/06/08 20:34:20]

Why not just use an std::map?

[tbansal1, 2015/06/09 02:23:13]

Did not do it before because I was not using struct NetworkID.
Now, it makes more sense. Done.
Unfortunately, this caused a lot of churn in the code.

+    if (!network_quality->MatchesNetwork(current_connection_type_,
+                                         current_network_name_)) {
+      continue;
+    }
+
+    network_quality->UpdateNetworkQuality(median_kbps, median_rtt);
+    return;
+  }
+
+  if (cached_network_quality_.size() < kMaximumNetworkQualityCacheSize) {
+    cached_network_quality_.push_back(new CachedNetworkQuality(
+        current_connection_type_, current_network_name_, median_kbps,
+        median_rtt));

[mmenke, 2015/06/08 20:34:20]

Rather than duplicate this line, suggest you do:

if (cached_network_quality_.size() >= kMaximumNetworkQualityCacheSize) {
  // Remove oldest entry here.
}

// Add new entry here, unconditionally.

[tbansal1, 2015/06/09 02:23:13]

Done.

+    return;
+  }
+
+  DCHECK_EQ(kMaximumNetworkQualityCacheSize, cached_network_quality_.size());

[mmenke, 2015/06/08 20:34:19]

optional:  Suggest a DCHECK_LE(kMaximumNetworkQualityCacheSize,
cached_network_quality_.size()); at the start of this function instead.

[tbansal1, 2015/06/09 02:23:13]

Done.

+
+  // Overwrite the oldest entry.
+  ScopedVector<CachedNetworkQuality>::iterator oldest_entry_iterator =
+      cached_network_quality_.begin();
+
+  for (ScopedVector<CachedNetworkQuality>::iterator iterator =
+           cached_network_quality_.begin();
+       iterator != cached_network_quality_.end(); ++iterator) {
+    if ((*oldest_entry_iterator)->last_update_time() >
+        (*iterator)->last_update_time()) {
+      oldest_entry_iterator = iterator;
+    }
+  }
+
+  cached_network_quality_.erase(oldest_entry_iterator);
+  cached_network_quality_.push_back(
+      new CachedNetworkQuality(current_connection_type_, current_network_name_,
+                               median_kbps, median_rtt));
+
+  DCHECK_EQ(kMaximumNetworkQualityCacheSize, cached_network_quality_.size());
+}
+
+NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
+    NetworkChangeNotifier::ConnectionType connection_type,
+    const std::string& network_name,
+    uint64_t median_kbps,
+    const base::TimeDelta& median_rtt)
+    : median_kbps_(median_kbps),
+      median_rtt_(median_rtt),
+      last_update_time_(base::TimeTicks::Now()),
+      connection_type_(connection_type),
+      network_name_(network_name) {
+  DCHECK_GE(median_kbps_, 0U);
+  DCHECK_GE(median_rtt_, base::TimeDelta());
+}
+
+NetworkQualityEstimator::CachedNetworkQuality::~CachedNetworkQuality() {
+}
+
+void NetworkQualityEstimator::CachedNetworkQuality::UpdateNetworkQuality(
+    uint64_t median_kbps,
+    const base::TimeDelta& median_rtt) {
+  median_kbps_ = median_kbps;
+  median_rtt_ = median_rtt;
+  last_update_time_ = base::TimeTicks::Now();
+  DCHECK_GE(median_kbps_, 0U);
+  DCHECK_GE(median_rtt_, base::TimeDelta());

[mmenke, 2015/06/08 20:34:20]

nit:  DCHECKs to validate input are generally put at the start of methods.

[tbansal1, 2015/06/09 02:23:12]

Done.

+}
+
+bool NetworkQualityEstimator::CachedNetworkQuality::MatchesNetwork(
+    NetworkChangeNotifier::ConnectionType connection_type,
+    const std::string& network_name) const {
+  return connection_type == connection_type_ && network_name == network_name_;
+}
+
 }  // namespace net