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

net/base/network_quality_estimator.h

 // 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.
 
 #ifndef NET_BASE_NETWORK_QUALITY_ESTIMATOR_H_
 #define NET_BASE_NETWORK_QUALITY_ESTIMATOR_H_
 
 #include <stdint.h>
 
 #include <deque>
+#include <map>
+#include <string>
 
 #include "base/gtest_prod_util.h"
 #include "base/macros.h"
 #include "base/threading/thread_checker.h"
 #include "base/time/time.h"
 #include "net/base/net_export.h"
 #include "net/base/network_change_notifier.h"
+#include "net/base/network_quality.h"
 
 namespace net {
 
-class NetworkQuality;
-
 // NetworkQualityEstimator provides network quality estimates (quality of the
 // full paths to all origins that have been connected to).
 // The estimates are based on the observed organic traffic.
 // A NetworkQualityEstimator instance is attached to URLRequestContexts and
 // observes the traffic of URLRequests spawned from the URLRequestContexts.
 // A single instance of NQE can be attached to multiple URLRequestContexts,
 // thereby increasing the single NQE instance's accuracy by providing more
 // observed traffic characteristics.
 class NET_EXPORT_PRIVATE NetworkQualityEstimator
     : public NetworkChangeNotifier::ConnectionTypeObserver {
@@ skipping 11 matching lines @@
   // Notifies NetworkQualityEstimator that a response has been received.
   // |cumulative_prefilter_bytes_read| is the count of the bytes received prior
   // to applying filters (e.g. decompression, SDCH) from request creation time
   // until now.
   // |prefiltered_bytes_read| is the count of the bytes received prior
   // to applying filters in the most recent read.
   void NotifyDataReceived(const URLRequest& request,
                           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 NetworkID {
+    NetworkID(NetworkChangeNotifier::ConnectionType type, const std::string& id)
+        : type(type), id(id) {}
+

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

Remove new line

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

Aah, did not know about the new line style. I thought I saw these separated by a
newline somewhere (may be in data reduction proxy code). Done.

+    NetworkID(const NetworkID& other) : type(other.type), id(other.id) {}

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

does this need explicit?

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

don't think so. From:
http://google-styleguide.googlecode.com/svn/trunk/cppguide.html#Explicit_Cons...

"Copy and move constructors are exceptions: they should not be explicit"

[pauljensen, 2015/06/23 11:52:10]

Then please fix CachedNetworkQuality()'s copy constructor.

[tbansal1, 2015/07/13 21:21:26]

I may be looking it wrong but that's not a copy constructor.
CachedNetworkQuality has a constructor that takes NetworkQuality as an argument.

+

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

Remove new line

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

Done.

+    ~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
+    // - 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.
+  // |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(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.
+  // |type| is ignored.
+  void OnConnectionTypeChanged(
+      NetworkChangeNotifier::ConnectionType type) override;
+
+  // Returns the number of entries in the network quality cache.
+  // Used only for testing.
+  size_t GetNetworkQualityCacheSizeForTests() const;
+
  private:
   FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, StoreObservations);
   FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest,
                            TestPeakKbpsFastestRTTUpdates);
   FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, TestAddObservation);
+  FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, TestCaching);
+  FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest,
+                           TestLRUCacheMaximumSize);
   FRIEND_TEST_ALL_PREFIXES(URLRequestTestHTTP, NetworkQualityEstimator);
+  friend class ObservationBuffer;

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

What is this needed for?

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

Done.

+
+  // CachedNetworkQuality stores the quality of a previously seen network.
+  class CachedNetworkQuality {
+   public:
+    explicit CachedNetworkQuality(const NetworkQuality& network_quality);
+

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

Remove new line

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

Done.

+    ~CachedNetworkQuality();
+
+    // Returns the network quality associated with this cached entry.
+    const NetworkQuality network_quality() const { return network_quality_; }
+
+    // Updates the network quality to the specified |median_kbps| and
+    // |median_rtt|.
+    void UpdateNetworkQuality(int32_t median_kbps,
+                              const base::TimeDelta& median_rtt);
+
+    // Returns true if this cache entry was updated before
+    // |cached_network_quality|.
+    bool OlderThan(const CachedNetworkQuality& cached_network_quality) const;
+
+   private:
+    // Time when this cache entry was last updated.
+    base::TimeTicks last_update_time_;
+
+    // Quality of this cached network.
+    NetworkQuality network_quality_;
+
+    DISALLOW_COPY_AND_ASSIGN(CachedNetworkQuality);
+  };
 
   // Records the round trip time or throughput observation, along with the time
   // the observation was made.
   struct Observation {
     Observation(int32_t value, base::TimeTicks timestamp);
 

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

Remove new line

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

Done.

     ~Observation();
 
     // Value of the observation.
     const int32_t value;
 
     // Time when the observation was taken.
     const base::TimeTicks timestamp;
   };
 
   // Stores observations sorted by time.
   class ObservationBuffer {
    public:
     ObservationBuffer();
 

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

remove new line

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

Done.

     ~ObservationBuffer();
 
     // Adds |observation| to the buffer. The oldest observation in the buffer
     // will be evicted to make room if the buffer is already full.
     void AddObservation(const Observation& observation);
 
     // Returns the number of observations in this buffer.
     size_t Size() const;

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

I think this function is dead once the unneeded "ForTest" functions are removed,
so remove this function.

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

Please see the comment on the ForTest() functions.

 
     // Clears the observations stored in this buffer.
     void Clear();
 
    private:
     FRIEND_TEST_ALL_PREFIXES(NetworkQualityEstimatorTest, StoreObservations);
 
     // Holds observations sorted by time, with the oldest observation at the
     // front of the queue.
     std::deque<Observation> observations_;
 
     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, scoped_ptr<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;
 
   // Minimum duration (in microseconds) of the transfer over which the
   // throughput is computed.
   static const int kMinRequestDurationMicroseconds = 1000;
 
-  // Construct a NetworkQualityEstimator instance allowing for test
-  // configuration.
-  // Registers for network type change notifications so estimates can be kept
-  // network specific.
-  // |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(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;
 
-  // Returns the maximum size of the observation buffer.
-  // Used for testing.
-  size_t GetMaximumObservationBufferSizeForTests() const;
+  // Maximum number of observations that can be held in the ObservationBuffer.
+  static const size_t kMaximumObservationsBufferSize = 500;
 
-  // 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;
+  // Returns the current size of the Kbps observation buffer. Used for testing.
+  size_t GetKbpsObservationBufferSizeForTests() const;

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

Can you get rid of this too?

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

Can you please explain how I can get rid of them.
using estimator.kbps_observations_.Size() in nqe_unittest.cc does not work on
Windows.  It gives
linking error (it does work on all other platforms):
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...
I fixed the linking error by
https://codereview.chromium.org/1164713004/diff2/380001:400001/net/base/netwo...

[pauljensen, 2015/06/23 11:52:10]

I cannot see the build logs.  The build logs get wiped quickly.  Please just
copy and paste the error message here.

[tbansal1, 2015/07/13 21:21:26]

Fixed in a separate CL. Adding NET_EXPORT_PRIVATE macro fixed the linking.

 
-  // NetworkChangeNotifier::ConnectionTypeObserver implementation.
-  void OnConnectionTypeChanged(
-      NetworkChangeNotifier::ConnectionType type) override;
+  // Returns the current size of the RTT observation buffer. Used for testing.
+  size_t GetRTTObservationBufferSizeForTests() const;

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

ditto

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

Please see above.

+
+  // 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();
 
   // Determines if the requests to local host can be used in estimating the
   // network quality. Set to true only for tests.
   const bool allow_localhost_requests_;
 
   // Determines if the responses smaller than |kMinTransferSizeInBytes|
   // or shorter than |kMinTransferSizeInBytes| can be used in estimating the
   // network quality. Set to true only for tests.
   const bool allow_small_responses_;
 
   // 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_;
+  // ID of the current network.
+  NetworkID current_network_id_;
 
   // 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_;

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

Could we combine fastest_rtt_since_last_connection_change_ and
peak_kbps_since_last_connection_change_ into "NetworkQuality
peak_quality_metrics_"?  I think this might simplify UpdateNetworkQuality() and
GetPeakEstimate().  I think these variables are just copied from NCN.

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

Done.

 
+  // Cache that stores quality of previously seen networks.
+  CachedNetworkQualities cached_network_qualities_;
+
   // Rough measurement of downstream peak Kbps witnessed since last connectivity
   // change. 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_;
 
   // Buffer that holds Kbps observations.
   ObservationBuffer kbps_observations_;
 
   // Buffer that holds RTT (in milliseconds) observations.
   ObservationBuffer rtt_msec_observations_;
 
   base::ThreadChecker thread_checker_;
 
   DISALLOW_COPY_AND_ASSIGN(NetworkQualityEstimator);
 };
 
 }  // namespace net
 
 #endif  // NET_BASE_NETWORK_QUALITY_ESTIMATOR_H_