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

net/base/network_quality_estimator.h

Index: net/base/network_quality_estimator.h
diff --git a/net/base/network_quality_estimator.h b/net/base/network_quality_estimator.h
index 5fc3a55f24e56157356b181db31be75e4ab62e90..dadce886e93624982efc1af620701e04912fc3c1 100644
--- a/net/base/network_quality_estimator.h
+++ b/net/base/network_quality_estimator.h
@@ -9,9 +9,11 @@
 
 #include <deque>
 #include <map>
+#include <string>
 
 #include "base/gtest_prod_util.h"
 #include "base/macros.h"
+#include "base/memory/scoped_ptr.h"
 #include "base/threading/thread_checker.h"
 #include "base/time/time.h"
 #include "net/base/net_export.h"
@@ -63,6 +65,68 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
                           int64_t cumulative_prefilter_bytes_read,
                           int64_t prefiltered_bytes_read);
 
+ protected:
+  // NetworkID is used to uniquely identify a network.
+  // For the purpose of network quality estimation and caching, a network is
+  // uniquely identified by a combination of |type| and
+  // |id|. This approach is unable to distinguish networks with
+  // same name (e.g., different Wi-Fi networks with same SSID).
+  // This is a protected member to expose it to tests.
+  struct NET_EXPORT_PRIVATE NetworkID {
+    NetworkID(NetworkChangeNotifier::ConnectionType type, const std::string& id)
+        : type(type), id(id) {}
+    NetworkID(const NetworkID& other) : type(other.type), id(other.id) {}
+    ~NetworkID() {}
+
+    NetworkID& operator=(const NetworkID& other) {
+      type = other.type;
+      id = other.id;
+      return *this;
+    }
+
+    // Overloaded because NetworkID is used as key in a map.
+    bool operator<(const NetworkID& other) const {
+      return type < other.type || (type == other.type && id < other.id);
+    }
+
+    // Connection type of the network.
+    NetworkChangeNotifier::ConnectionType type;
+
+    // Name of this network. This is set to:
+    // - Wi-Fi SSID if the device is connected to a Wi-Fi access point and the
+    //   SSID name is available, or
+    // - MCC/MNC code of the cellular carrier if the device is connected to a
+    //   cellular network, or
+    // - "Ethernet" in case the device is connected to ethernet.
+    // - An empty string in all other cases or if the network name is not
+    //   exposed by platform APIs.
+    std::string id;
+  };
+
+  // Construct a NetworkQualityEstimator instance allowing for test
+  // configuration. Registers for network type change notifications so estimates
+  // can be kept network specific.
+  // |variation_params| is the map containing all field trial parameters for the
+  // network quality estimator field trial.
+  // |allow_local_host_requests_for_tests| should only be true when testing
+  // against local HTTP server and allows the requests to local host to be
+  // used for network quality estimation.
+  // |allow_smaller_responses_for_tests| should only be true when testing.
+  // Allows the responses smaller than |kMinTransferSizeInBytes| or shorter than
+  // |kMinRequestDurationMicroseconds| to be used for network quality
+  // estimation.
+  NetworkQualityEstimator(
+      const std::map<std::string, std::string>& variation_params,
+      bool allow_local_host_requests_for_tests,
+      bool allow_smaller_responses_for_tests);
+
+  // Returns true if the cached network quality estimate was successfully read.
+  bool ReadCachedNetworkQualityEstimate();
+
+  // NetworkChangeNotifier::ConnectionTypeObserver implementation.
+  void OnConnectionTypeChanged(
+      NetworkChangeNotifier::ConnectionType type) override;
+
  private:
   FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, StoreObservations);
   FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, TestKbpsRTTUpdates);
@@ -75,12 +139,38 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
   FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest,
                            PercentileDifferentTimestamps);
   FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, ComputedPercentiles);
+  FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, TestCaching);
+  FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest,
+                           TestLRUCacheMaximumSize);
+
+  // CachedNetworkQuality stores the quality of a previously seen network.
+  class NET_EXPORT_PRIVATE CachedNetworkQuality {
+   public:
+    explicit CachedNetworkQuality(const NetworkQuality& network_quality);
+    CachedNetworkQuality(const CachedNetworkQuality& other);
+    ~CachedNetworkQuality();
+
+    // Returns the network quality associated with this cached entry.
+    const NetworkQuality network_quality() const { return network_quality_; }
+
+    // Returns true if this cache entry was updated before
+    // |cached_network_quality|.
+    bool OlderThan(const CachedNetworkQuality& cached_network_quality) const;
+
+    // Time when this cache entry was last updated.
+    const base::TimeTicks last_update_time_;
+
+    // Quality of this cached network.
+    const NetworkQuality network_quality_;
+
+   private:
+    DISALLOW_ASSIGN(CachedNetworkQuality);
+  };
 
   // Records the round trip time or throughput observation, along with the time
   // the observation was made.
   struct NET_EXPORT_PRIVATE Observation {
     Observation(int32_t value, base::TimeTicks timestamp);
-
     ~Observation();
 
     // Value of the observation.
@@ -91,7 +181,7 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
   };
 
   // Holds an observation and its weight.
-  struct WeightedObservation {
+  struct NET_EXPORT_PRIVATE WeightedObservation {
     WeightedObservation(int32_t value, double weight)
         : value(value), weight(weight) {}
     WeightedObservation(const WeightedObservation& other)
@@ -120,7 +210,6 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
   class NET_EXPORT_PRIVATE ObservationBuffer {
    public:
     explicit ObservationBuffer(double weight_multiplier_per_second);
-
     ~ObservationBuffer();
 
     // Adds |observation| to the buffer. The oldest observation in the buffer
@@ -164,6 +253,11 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
     DISALLOW_COPY_AND_ASSIGN(ObservationBuffer);
   };
 
+  // This does not use a unordered_map or hash_map for code simplicity (key just
+  // implements operator<, rather than hash and equality) and because the map is
+  // tiny.
+  typedef std::map<NetworkID, CachedNetworkQuality> CachedNetworkQualities;
+
   // Tiny transfer sizes may give inaccurate throughput results.
   // Minimum size of the transfer over which the throughput is computed.
   static const int kMinTransferSizeInBytes = 10000;
@@ -180,22 +274,13 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
   // kbps) values.
   static const int kMinimumThroughputVariationParameterKbps = 1;
 
-  // Construct a NetworkQualityEstimator instance allowing for test
-  // configuration. Registers for network type change notifications so estimates
-  // can be kept network specific.
-  // |variation_params| is the map containing all field trial parameters for the
-  // network quality estimator field trial.
-  // |allow_local_host_requests_for_tests| should only be true when testing
-  // against local HTTP server and allows the requests to local host to be
-  // used for network quality estimation.
-  // |allow_smaller_responses_for_tests| should only be true when testing
-  // against local HTTP server and allows the responses smaller than
-  // |kMinTransferSizeInBytes| or shorter than |kMinRequestDurationMicroseconds|
-  // to be used for network quality estimation.
-  NetworkQualityEstimator(
-      const std::map<std::string, std::string>& variation_params,
-      bool allow_local_host_requests_for_tests,
-      bool allow_smaller_responses_for_tests);
+  // 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.
+  static const size_t kMaximumNetworkQualityCacheSize = 10;
+
+  // Maximum number of observations that can be held in the ObservationBuffer.
+  static const size_t kMaximumObservationsBufferSize = 300;
 
   // Obtains operating parameters from the field trial parameters.
   void ObtainOperatingParams(
@@ -205,18 +290,6 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
   // current connection type to the observation buffer.
   void AddDefaultEstimates();
 
-  // Returns the maximum size of the observation buffer.
-  // Used for testing.
-  size_t GetMaximumObservationBufferSizeForTests() const;
-
-  // Returns true if the size of all observation buffers is equal to the
-  // |expected_size|. Used for testing.
-  bool VerifyBufferSizeForTests(size_t expected_size) const;
-
-  // NetworkChangeNotifier::ConnectionTypeObserver implementation.
-  void OnConnectionTypeChanged(
-      NetworkChangeNotifier::ConnectionType type) override;
-
   // Returns an estimate of network quality at the specified |percentile|.
   // |percentile| must be between 0 and 100 (both inclusive) with higher
   // percentiles indicating less performant networks. For example, if
@@ -225,6 +298,13 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
   // be slower than the returned estimate with 0.1 probability.
   NetworkQuality GetEstimate(int percentile) const;
 
+  // Returns the current network ID checking by calling the platform APIs.
+  // Virtualized for testing.
+  virtual NetworkID GetCurrentNetworkID() const;
+
+  // Writes the estimated quality of the current network to the cache.
+  void CacheNetworkQualityEstimate();
+
   // Records the UMA related to RTT.
   void RecordRTTUMA(int32_t estimated_value_msec,
                     int32_t actual_value_msec) const;
@@ -241,19 +321,19 @@ class NET_EXPORT_PRIVATE NetworkQualityEstimator
   // Time when last connection change was observed.
   base::TimeTicks last_connection_change_;
 
-  // Last value passed to |OnConnectionTypeChanged|. This indicates the
-  // current connection type.
-  NetworkChangeNotifier::ConnectionType current_connection_type_;
-
-  // Fastest round-trip-time (RTT) since last connectivity change. RTT measured
-  // from URLRequest creation until first byte received.
-  base::TimeDelta fastest_rtt_since_last_connection_change_;
+  // ID of the current network.
+  NetworkID current_network_id_;
 
-  // Rough measurement of downstream peak Kbps witnessed since last connectivity
-  // change. The accuracy is decreased by ignoring these factors:
+  // Peak network quality (fastest round-trip-time (RTT) and highest
+  // downstream throughput) measured since last connectivity change. RTT is
+  // measured from time the request is sent until the first byte received.
+  // The accuracy is decreased by ignoring these factors:
   // 1) Multiple URLRequests can occur concurrently.
-  // 2) The transfer time includes at least one RTT while no bytes are read.
-  int32_t peak_kbps_since_last_connection_change_;
+  // 2) Includes server processing time.
+  NetworkQuality peak_network_quality_;
+
+  // Cache that stores quality of previously seen networks.
+  CachedNetworkQualities cached_network_qualities_;
 
   // Buffer that holds Kbps observations sorted by timestamp.
   ObservationBuffer kbps_observations_;