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:
+  // Returns true if the cached network quality estimate was successfully read.
+  bool ReadCachedNetworkQualityEstimate();
+
+  // NetworkChangeNotifier::ConnectionTypeObserver implementation.
+  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);
 
+  // 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).
+  struct 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 as returned by |GetCurrentNetworkName| function.
+    std::string id;
+  };
+
+  // CachedNetworkQuality stores the quality of a previously seen network.
+  class CachedNetworkQuality {
+   public:
+    explicit CachedNetworkQuality(const NetworkQuality& network_quality);
+
+    ~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 the time when this cached entry was last updated.
+    base::TimeTicks last_update_time() const { return last_update_time_; }

[pauljensen, 2015/06/17 14:23:26]

Slightly nicer encapsulation if we replaced this function with a "bool
older_than(const CachedNetworkQuality&)" function.

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

Done.

+
+   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);
 
     ~Observation();
 
     // Value of the observation.
     const int32_t value;
 
@@ skipping 21 matching lines @@
    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);
   };
 
+  typedef std::map<NetworkID, scoped_ptr<CachedNetworkQuality>>

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

I don't see an ordered traversal and assume we'll never need one, so please add
a comment or preferably use a hash table:

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.

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

Done.

+      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;
 
+  // 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;
+
   // 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 the maximum size of the observation buffer.
   // Used for testing.
   size_t GetMaximumObservationBufferSizeForTests() const;

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

Can we remove this and have the tests compare to the internal sizes?

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

Right now kMaximumObservationsBufferSize is defined in the cc file (because its
type is size_t which can't be defined in .h). There is no way for the tests to
access it without going through the function. So, still keeping this function.

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

I don't understand.  Why can't we replace this function declaration with "static
const size_t kMaximumObservationsBufferSize = 500;" that the friended test
classes can read?

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

For some reason, this gives the linking error both in nqe.cc and nqe_test.cc.
Typecasting it by size_t solves the linking error (this is what I am doing right
now) but I am not sure if that's the right approach. Seems that it is not
preferable to define static const size_t in header file. Another approach is to
simply use const size_t (e.g.,
https://code.google.com/p/chromium/codesearch#chromium/src/net/quic/quic_fram...).


So, there are 3 possible approaches
(1) Typecase size_t like what I am doing now
(2) Define the variables as const size_t (similar to quic code above)
(3) Declare and define in anonymous namespace in .cc file and have functions
that expose it to the tests.

Please let me know which approach you think is best.

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

What link error are you seeing?  There are plenty of places that define static
const size_t's in headers:
~/chrome/src$ git grep "  static const size_t" -- *.h | wc -l
181

[tbansal1, 2015/06/20 03:09:30]

Forgot to mention that the linking error comes only in DCHECK or other macro
statements. It does not show up in non-MACRO code. Weird.

Here is the linking error: https://goto.google.com/linkingerror

It works if the static const is not a class member but not as a class member.
e.g., if you search for 
static\ const\ size_t.*_\ .* f:h$ -f:test -f:third_party
in cs.chromium.org, there are only 3 results. (This regex "tries" to look only
for static const class members that are defined in the header)

[tbansal1, 2015/06/20 03:13:56]

My regex was incorrect. It does not capture variable names that start with k.
Here is another one that captures that but does not
guarantee that the variable is member of class:
static\ const\ size_t\ k.*=.* f:h$ -f:test -f:third_party

[tbansal1, 2015/06/20 03:21:17]

It seems like existing code also does typecast before putting it in  a macro
statement, see this e.g.:
https://code.google.com/p/chromium/codesearch#chromium/src/gpu/command_buffer...

Please let me know what you think is the best approach. I do not have much
Chromium experience but this typecasting approach does not look very great.
WDYT?

[tbansal1, 2015/06/22 17:51:22]

Done.

 
   // 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;

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

Can we remove this and have the tests compare to the internal sizes?

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

Removed this function but had to add 2 more functions. It seems that I can't
call estimator.kbps_observations_.Size() in the test code directly. It gives
linking error on windows (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....

 
-  // NetworkChangeNotifier::ConnectionTypeObserver implementation.
-  void OnConnectionTypeChanged(
-      NetworkChangeNotifier::ConnectionType type) override;
+  // Updates the current network name to:
+  // WiFi SSID (if the user is connected to a WiFi access point and the SSID

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

can you add " - " before "WiFi" on this line and before "the" on line 218 so
it's easier to read, and indent lines 217 and 219.

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

Done.

+  // name is available), or
+  // the MCC/MNC code of the cellular carrier if the device is connected to a
+  // cellular network.
+  // Updates the current network name to an empty string in all other cases or
+  // if the network name is not exposed by platform APIs.
+  // Virtualized for testing.
+  virtual std::string GetCurrentNetworkName() 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_;
 
+  // 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_