net/base/network_quality_estimator.cc

   1 // Copyright 2015 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/base/network_quality_estimator.h"
   6
   7 #include <float.h>
   8 #include <algorithm>
   9 #include <cmath>
  10 #include <limits>
  11 #include <vector>
  12
  13 #include "base/logging.h"
  14 #include "base/metrics/histogram.h"
  15 #include "base/metrics/histogram_base.h"
  16 #include "base/strings/string_number_conversions.h"
  17 #include "build/build_config.h"
  18 #include "net/base/load_flags.h"
  19 #include "net/base/load_timing_info.h"
  20 #include "net/base/net_util.h"
  21 #include "net/base/network_interfaces.h"
  22 #include "net/url_request/url_request.h"
  23 #include "url/gurl.h"
  24
  25 #if defined(OS_ANDROID)
  26 #include "net/android/network_library.h"
  27 #endif  // OS_ANDROID
  28
  29 namespace {
  30
  31 // Implements SocketPerformanceWatcher for TCP sockets.
  32 class SocketPerformanceWatcherTCP : public net::SocketPerformanceWatcher {
  33  public:
  34   SocketPerformanceWatcherTCP() {}
  35
  36   ~SocketPerformanceWatcherTCP() override {
  37     DCHECK(thread_checker_.CalledOnValidThread());
  38   }
  39
  40   // net::SocketPerformanceWatcher implementation:
  41   void OnUpdatedRTTAvailable(const base::TimeDelta& rtt) override {
  42     DCHECK(thread_checker_.CalledOnValidThread());
  43     // TODO(tbansal): Notify any relevant observers.
  44   }
  45
  46  private:
  47   base::ThreadChecker thread_checker_;
  48 };
  49
  50 // Implements SocketPerformanceWatcher for UDP sockets.
  51 class SocketPerformanceWatcherUDP : public net::SocketPerformanceWatcher {
  52  public:
  53   SocketPerformanceWatcherUDP() {}
  54
  55   ~SocketPerformanceWatcherUDP() override {
  56     DCHECK(thread_checker_.CalledOnValidThread());
  57   }
  58
  59   // net::SocketPerformanceWatcher implementation:
  60   void OnUpdatedRTTAvailable(const base::TimeDelta& rtt) override {
  61     DCHECK(thread_checker_.CalledOnValidThread());
  62     // TODO(tbansal): Notify any relevant observers.
  63   }
  64
  65  private:
  66   base::ThreadChecker thread_checker_;
  67 };
  68
  69 // Default value of the half life (in seconds) for computing time weighted
  70 // percentiles. Every half life, the weight of all observations reduces by
  71 // half. Lowering the half life would reduce the weight of older values faster.
  72 const int kDefaultHalfLifeSeconds = 60;
  73
  74 // Name of the variation parameter that holds the value of the half life (in
  75 // seconds) of the observations.
  76 const char kHalfLifeSecondsParamName[] = "HalfLifeSeconds";
  77
  78 // Returns a descriptive name corresponding to |connection_type|.
  79 const char* GetNameForConnectionType(
  80     net::NetworkChangeNotifier::ConnectionType connection_type) {
  81   switch (connection_type) {
  82     case net::NetworkChangeNotifier::CONNECTION_UNKNOWN:
  83       return "Unknown";
  84     case net::NetworkChangeNotifier::CONNECTION_ETHERNET:
  85       return "Ethernet";
  86     case net::NetworkChangeNotifier::CONNECTION_WIFI:
  87       return "WiFi";
  88     case net::NetworkChangeNotifier::CONNECTION_2G:
  89       return "2G";
  90     case net::NetworkChangeNotifier::CONNECTION_3G:
  91       return "3G";
  92     case net::NetworkChangeNotifier::CONNECTION_4G:
  93       return "4G";
  94     case net::NetworkChangeNotifier::CONNECTION_NONE:
  95       return "None";
  96     case net::NetworkChangeNotifier::CONNECTION_BLUETOOTH:
  97       return "Bluetooth";
  98     default:
  99       NOTREACHED();
 100       break;
 101   }
 102   return "";
 103 }
 104
 105 // Suffix of the name of the variation parameter that contains the default RTT
 106 // observation (in milliseconds). Complete name of the variation parameter
 107 // would be |ConnectionType|.|kDefaultRTTMsecObservationSuffix| where
 108 // |ConnectionType| is from |kConnectionTypeNames|. For example, variation
 109 // parameter for Wi-Fi would be "WiFi.DefaultMedianRTTMsec".
 110 const char kDefaultRTTMsecObservationSuffix[] = ".DefaultMedianRTTMsec";
 111
 112 // Suffix of the name of the variation parameter that contains the default
 113 // downstream throughput observation (in Kbps).  Complete name of the variation
 114 // parameter would be |ConnectionType|.|kDefaultKbpsObservationSuffix| where
 115 // |ConnectionType| is from |kConnectionTypeNames|. For example, variation
 116 // parameter for Wi-Fi would be "WiFi.DefaultMedianKbps".
 117 const char kDefaultKbpsObservationSuffix[] = ".DefaultMedianKbps";
 118
 119 // Computes and returns the weight multiplier per second.
 120 // |variation_params| is the map containing all field trial parameters
 121 // related to NetworkQualityEstimator field trial.
 122 double GetWeightMultiplierPerSecond(
 123     const std::map<std::string, std::string>& variation_params) {
 124   int half_life_seconds = kDefaultHalfLifeSeconds;
 125   int32_t variations_value = 0;
 126   auto it = variation_params.find(kHalfLifeSecondsParamName);
 127   if (it != variation_params.end() &&
 128       base::StringToInt(it->second, &variations_value) &&
 129       variations_value >= 1) {
 130     half_life_seconds = variations_value;
 131   }
 132   DCHECK_GT(half_life_seconds, 0);
 133   return exp(log(0.5) / half_life_seconds);
 134 }
 135
 136 // Returns the histogram that should be used to record the given statistic.
 137 // |max_limit| is the maximum value that can be stored in the histogram.
 138 base::HistogramBase* GetHistogram(
 139     const std::string& statistic_name,
 140     net::NetworkChangeNotifier::ConnectionType type,
 141     int32_t max_limit) {
 142   const base::LinearHistogram::Sample kLowerLimit = 1;
 143   DCHECK_GT(max_limit, kLowerLimit);
 144   const size_t kBucketCount = 50;
 145
 146   // Prefix of network quality estimator histograms.
 147   const char prefix[] = "NQE.";
 148   return base::Histogram::FactoryGet(
 149       prefix + statistic_name + GetNameForConnectionType(type), kLowerLimit,
 150       max_limit, kBucketCount, base::HistogramBase::kUmaTargetedHistogramFlag);
 151 }
 152
 153 }  // namespace
 154
 155 namespace net {
 156
 157 const int32_t NetworkQualityEstimator::kInvalidThroughput = 0;
 158
 159 NetworkQualityEstimator::NetworkQualityEstimator(
 160     scoped_ptr<ExternalEstimateProvider> external_estimates_provider,
 161     const std::map<std::string, std::string>& variation_params)
 162     : NetworkQualityEstimator(external_estimates_provider.Pass(),
 163                               variation_params,
 164                               false,
 165                               false) {}
 166
 167 NetworkQualityEstimator::NetworkQualityEstimator(
 168     scoped_ptr<ExternalEstimateProvider> external_estimates_provider,
 169     const std::map<std::string, std::string>& variation_params,
 170     bool allow_local_host_requests_for_tests,
 171     bool allow_smaller_responses_for_tests)
 172     : allow_localhost_requests_(allow_local_host_requests_for_tests),
 173       allow_small_responses_(allow_smaller_responses_for_tests),
 174       last_connection_change_(base::TimeTicks::Now()),
 175       current_network_id_(
 176           NetworkID(NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN,
 177                     std::string())),
 178       downstream_throughput_kbps_observations_(
 179           GetWeightMultiplierPerSecond(variation_params)),
 180       rtt_msec_observations_(GetWeightMultiplierPerSecond(variation_params)),
 181       external_estimates_provider_(external_estimates_provider.Pass()) {
 182   static_assert(kMinRequestDurationMicroseconds > 0,
 183                 "Minimum request duration must be > 0");
 184   static_assert(kDefaultHalfLifeSeconds > 0,
 185                 "Default half life duration must be > 0");
 186   static_assert(kMaximumNetworkQualityCacheSize > 0,
 187                 "Size of the network quality cache must be > 0");
 188   // This limit should not be increased unless the logic for removing the
 189   // oldest cache entry is rewritten to use a doubly-linked-list LRU queue.
 190   static_assert(kMaximumNetworkQualityCacheSize <= 10,
 191                 "Size of the network quality cache must <= 10");
 192
 193   ObtainOperatingParams(variation_params);
 194   NetworkChangeNotifier::AddConnectionTypeObserver(this);
 195   if (external_estimates_provider_)
 196     external_estimates_provider_->SetUpdatedEstimateDelegate(this);
 197   current_network_id_ = GetCurrentNetworkID();
 198   AddDefaultEstimates();
 199 }
 200
 201 // static
 202 const base::TimeDelta NetworkQualityEstimator::InvalidRTT() {
 203   return base::TimeDelta::Max();
 204 }
 205
 206 void NetworkQualityEstimator::ObtainOperatingParams(
 207     const std::map<std::string, std::string>& variation_params) {
 208   DCHECK(thread_checker_.CalledOnValidThread());
 209
 210   for (size_t i = 0; i <= NetworkChangeNotifier::CONNECTION_LAST; ++i) {
 211     NetworkChangeNotifier::ConnectionType type =
 212         static_cast<NetworkChangeNotifier::ConnectionType>(i);
 213     int32_t variations_value = kMinimumRTTVariationParameterMsec - 1;
 214     // Name of the parameter that holds the RTT value for this connection type.
 215     std::string rtt_parameter_name =
 216         std::string(GetNameForConnectionType(type))
 217             .append(kDefaultRTTMsecObservationSuffix);
 218     auto it = variation_params.find(rtt_parameter_name);
 219     if (it != variation_params.end() &&
 220         base::StringToInt(it->second, &variations_value) &&
 221         variations_value >= kMinimumRTTVariationParameterMsec) {
 222       default_observations_[i] =
 223           NetworkQuality(base::TimeDelta::FromMilliseconds(variations_value),
 224                          default_observations_[i].downstream_throughput_kbps());
 225     }
 226
 227     variations_value = kMinimumThroughputVariationParameterKbps - 1;
 228     // Name of the parameter that holds the Kbps value for this connection
 229     // type.
 230     std::string kbps_parameter_name =
 231         std::string(GetNameForConnectionType(type))
 232             .append(kDefaultKbpsObservationSuffix);
 233     it = variation_params.find(kbps_parameter_name);
 234     if (it != variation_params.end() &&
 235         base::StringToInt(it->second, &variations_value) &&
 236         variations_value >= kMinimumThroughputVariationParameterKbps) {
 237       default_observations_[i] =
 238           NetworkQuality(default_observations_[i].rtt(), variations_value);
 239     }
 240   }
 241 }
 242
 243 void NetworkQualityEstimator::AddDefaultEstimates() {
 244   DCHECK(thread_checker_.CalledOnValidThread());
 245   if (default_observations_[current_network_id_.type].rtt() != InvalidRTT()) {
 246     rtt_msec_observations_.AddObservation(Observation(
 247         default_observations_[current_network_id_.type].rtt().InMilliseconds(),
 248         base::TimeTicks::Now()));
 249   }
 250   if (default_observations_[current_network_id_.type]
 251           .downstream_throughput_kbps() != kInvalidThroughput) {
 252     downstream_throughput_kbps_observations_.AddObservation(
 253         Observation(default_observations_[current_network_id_.type]
 254                         .downstream_throughput_kbps(),
 255                     base::TimeTicks::Now()));
 256   }
 257 }
 258
 259 NetworkQualityEstimator::~NetworkQualityEstimator() {
 260   DCHECK(thread_checker_.CalledOnValidThread());
 261   NetworkChangeNotifier::RemoveConnectionTypeObserver(this);
 262 }
 263
 264 void NetworkQualityEstimator::NotifyHeadersReceived(const URLRequest& request) {
 265   DCHECK(thread_checker_.CalledOnValidThread());
 266
 267   if (!RequestProvidesUsefulObservations(request))
 268     return;
 269
 270   // Update |estimated_median_network_quality_| if this is a main frame request.
 271   if (request.load_flags() & LOAD_MAIN_FRAME) {
 272     estimated_median_network_quality_ = NetworkQuality(
 273         GetRTTEstimateInternal(base::TimeTicks(), 50),
 274         GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50));
 275   }
 276
 277   base::TimeTicks now = base::TimeTicks::Now();
 278   LoadTimingInfo load_timing_info;
 279   request.GetLoadTimingInfo(&load_timing_info);
 280
 281   // If the load timing info is unavailable, it probably means that the request
 282   // did not go over the network.
 283   if (load_timing_info.send_start.is_null() ||
 284       load_timing_info.receive_headers_end.is_null()) {
 285     return;
 286   }
 287
 288   // Time when the resource was requested.
 289   base::TimeTicks request_start_time = load_timing_info.send_start;
 290
 291   // Time when the headers were received.
 292   base::TimeTicks headers_received_time = load_timing_info.receive_headers_end;
 293
 294   // Duration between when the resource was requested and when response
 295   // headers were received.
 296     base::TimeDelta observed_rtt = headers_received_time - request_start_time;
 297     DCHECK_GE(observed_rtt, base::TimeDelta());
 298     if (observed_rtt < peak_network_quality_.rtt()) {
 299       peak_network_quality_ = NetworkQuality(
 300           observed_rtt, peak_network_quality_.downstream_throughput_kbps());
 301     }
 302
 303     rtt_msec_observations_.AddObservation(
 304         Observation(observed_rtt.InMilliseconds(), now));
 305
 306     // Compare the RTT observation with the estimated value and record it.
 307     if (estimated_median_network_quality_.rtt() != InvalidRTT()) {
 308       RecordRTTUMA(estimated_median_network_quality_.rtt().InMilliseconds(),
 309                    observed_rtt.InMilliseconds());
 310     }
 311 }
 312
 313 void NetworkQualityEstimator::NotifyRequestCompleted(
 314     const URLRequest& request) {
 315   DCHECK(thread_checker_.CalledOnValidThread());
 316
 317   if (!RequestProvidesUsefulObservations(request))
 318     return;
 319
 320   base::TimeTicks now = base::TimeTicks::Now();
 321   LoadTimingInfo load_timing_info;
 322   request.GetLoadTimingInfo(&load_timing_info);
 323
 324   // If the load timing info is unavailable, it probably means that the request
 325   // did not go over the network.
 326   if (load_timing_info.send_start.is_null() ||
 327       load_timing_info.receive_headers_end.is_null()) {
 328     return;
 329   }
 330
 331   // Time since the resource was requested.
 332   // TODO(tbansal): Change the start time to receive_headers_end, once we use
 333   // NetworkActivityMonitor.
 334   base::TimeDelta request_start_to_completed =
 335       now - load_timing_info.send_start;
 336   DCHECK_GE(request_start_to_completed, base::TimeDelta());
 337
 338   // Ignore tiny transfers which will not produce accurate rates.
 339   // Ignore short duration transfers.
 340   // Skip the checks if |allow_small_responses_| is true.
 341   if (!allow_small_responses_ &&
 342       (request.GetTotalReceivedBytes() < kMinTransferSizeInBytes ||
 343        request_start_to_completed < base::TimeDelta::FromMicroseconds(
 344                                         kMinRequestDurationMicroseconds))) {
 345     return;
 346   }
 347
 348   double downstream_kbps = request.GetTotalReceivedBytes() * 8.0 / 1000.0 /
 349                            request_start_to_completed.InSecondsF();
 350   DCHECK_GE(downstream_kbps, 0.0);
 351
 352   // Check overflow errors. This may happen if the downstream_kbps is more than
 353   // 2 * 10^9 (= 2000 Gbps).
 354   if (downstream_kbps >= std::numeric_limits<int32_t>::max())
 355     downstream_kbps = std::numeric_limits<int32_t>::max();
 356
 357   int32_t downstream_kbps_as_integer = static_cast<int32_t>(downstream_kbps);
 358
 359   // Round up |downstream_kbps_as_integer|. If the |downstream_kbps_as_integer|
 360   // is less than 1, it is set to 1 to differentiate from case when there is no
 361   // connection.
 362   if (downstream_kbps - downstream_kbps_as_integer > 0)
 363     downstream_kbps_as_integer++;
 364
 365   DCHECK_GT(downstream_kbps_as_integer, 0.0);
 366   if (downstream_kbps_as_integer >
 367       peak_network_quality_.downstream_throughput_kbps())
 368     peak_network_quality_ =
 369         NetworkQuality(peak_network_quality_.rtt(), downstream_kbps_as_integer);
 370
 371   downstream_throughput_kbps_observations_.AddObservation(
 372       Observation(downstream_kbps_as_integer, now));
 373 }
 374
 375 void NetworkQualityEstimator::RecordRTTUMA(int32_t estimated_value_msec,
 376                                            int32_t actual_value_msec) const {
 377   DCHECK(thread_checker_.CalledOnValidThread());
 378
 379   // Record the difference between the actual and the estimated value.
 380   if (estimated_value_msec >= actual_value_msec) {
 381     base::HistogramBase* difference_rtt =
 382         GetHistogram("DifferenceRTTEstimatedAndActual.",
 383                      current_network_id_.type, 10 * 1000);  // 10 seconds
 384     difference_rtt->Add(estimated_value_msec - actual_value_msec);
 385   } else {
 386     base::HistogramBase* difference_rtt =
 387         GetHistogram("DifferenceRTTActualAndEstimated.",
 388                      current_network_id_.type, 10 * 1000);  // 10 seconds
 389     difference_rtt->Add(actual_value_msec - estimated_value_msec);
 390   }
 391
 392   // Record all the RTT observations.
 393   base::HistogramBase* rtt_observations =
 394       GetHistogram("RTTObservations.", current_network_id_.type,
 395                    10 * 1000);  // 10 seconds upper bound
 396   rtt_observations->Add(actual_value_msec);
 397
 398   if (actual_value_msec == 0)
 399     return;
 400
 401   int32 ratio = (estimated_value_msec * 100) / actual_value_msec;
 402
 403   // Record the accuracy of estimation by recording the ratio of estimated
 404   // value to the actual value.
 405   base::HistogramBase* ratio_median_rtt = GetHistogram(
 406       "RatioEstimatedToActualRTT.", current_network_id_.type, 1000);
 407   ratio_median_rtt->Add(ratio);
 408 }
 409
 410 bool NetworkQualityEstimator::RequestProvidesUsefulObservations(
 411     const URLRequest& request) const {
 412   return request.url().is_valid() &&
 413          (allow_localhost_requests_ || !IsLocalhost(request.url().host())) &&
 414          request.url().SchemeIsHTTPOrHTTPS() &&
 415          // Verify that response headers are received, so it can be ensured that
 416          // response is not cached.
 417          !request.response_info().response_time.is_null() &&
 418          !request.was_cached() &&
 419          request.creation_time() >= last_connection_change_;
 420 }
 421
 422 void NetworkQualityEstimator::OnConnectionTypeChanged(
 423     NetworkChangeNotifier::ConnectionType type) {
 424   DCHECK(thread_checker_.CalledOnValidThread());
 425   if (peak_network_quality_.rtt() != InvalidRTT()) {
 426     switch (current_network_id_.type) {
 427       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 428         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
 429                             peak_network_quality_.rtt());
 430         break;
 431       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 432         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Ethernet",
 433                             peak_network_quality_.rtt());
 434         break;
 435       case NetworkChangeNotifier::CONNECTION_WIFI:
 436         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi", peak_network_quality_.rtt());
 437         break;
 438       case NetworkChangeNotifier::CONNECTION_2G:
 439         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.2G", peak_network_quality_.rtt());
 440         break;
 441       case NetworkChangeNotifier::CONNECTION_3G:
 442         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.3G", peak_network_quality_.rtt());
 443         break;
 444       case NetworkChangeNotifier::CONNECTION_4G:
 445         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.4G", peak_network_quality_.rtt());
 446         break;
 447       case NetworkChangeNotifier::CONNECTION_NONE:
 448         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None", peak_network_quality_.rtt());
 449         break;
 450       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 451         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Bluetooth",
 452                             peak_network_quality_.rtt());
 453         break;
 454       default:
 455         NOTREACHED() << "Unexpected connection type = "
 456                      << current_network_id_.type;
 457         break;
 458     }
 459   }
 460
 461   if (peak_network_quality_.downstream_throughput_kbps() !=
 462       kInvalidThroughput) {
 463     switch (current_network_id_.type) {
 464       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 465         UMA_HISTOGRAM_COUNTS(
 466             "NQE.PeakKbps.Unknown",
 467             peak_network_quality_.downstream_throughput_kbps());
 468         break;
 469       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 470         UMA_HISTOGRAM_COUNTS(
 471             "NQE.PeakKbps.Ethernet",
 472             peak_network_quality_.downstream_throughput_kbps());
 473         break;
 474       case NetworkChangeNotifier::CONNECTION_WIFI:
 475         UMA_HISTOGRAM_COUNTS(
 476             "NQE.PeakKbps.Wifi",
 477             peak_network_quality_.downstream_throughput_kbps());
 478         break;
 479       case NetworkChangeNotifier::CONNECTION_2G:
 480         UMA_HISTOGRAM_COUNTS(
 481             "NQE.PeakKbps.2G",
 482             peak_network_quality_.downstream_throughput_kbps());
 483         break;
 484       case NetworkChangeNotifier::CONNECTION_3G:
 485         UMA_HISTOGRAM_COUNTS(
 486             "NQE.PeakKbps.3G",
 487             peak_network_quality_.downstream_throughput_kbps());
 488         break;
 489       case NetworkChangeNotifier::CONNECTION_4G:
 490         UMA_HISTOGRAM_COUNTS(
 491             "NQE.PeakKbps.4G",
 492             peak_network_quality_.downstream_throughput_kbps());
 493         break;
 494       case NetworkChangeNotifier::CONNECTION_NONE:
 495         UMA_HISTOGRAM_COUNTS(
 496             "NQE.PeakKbps.None",
 497             peak_network_quality_.downstream_throughput_kbps());
 498         break;
 499       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 500         UMA_HISTOGRAM_COUNTS(
 501             "NQE.PeakKbps.Bluetooth",
 502             peak_network_quality_.downstream_throughput_kbps());
 503         break;
 504       default:
 505         NOTREACHED() << "Unexpected connection type = "
 506                      << current_network_id_.type;
 507         break;
 508     }
 509   }
 510
 511   base::TimeDelta rtt = GetRTTEstimateInternal(base::TimeTicks(), 50);
 512   if (rtt != InvalidRTT()) {
 513     // Add the 50th percentile value.
 514     base::HistogramBase* rtt_percentile =
 515         GetHistogram("RTT.Percentile50.", current_network_id_.type,
 516                      10 * 1000);  // 10 seconds
 517     rtt_percentile->Add(rtt.InMilliseconds());
 518
 519     // Add the remaining percentile values.
 520     static const int kPercentiles[] = {0, 10, 90, 100};
 521     for (size_t i = 0; i < arraysize(kPercentiles); ++i) {
 522       rtt = GetRTTEstimateInternal(base::TimeTicks(), kPercentiles[i]);
 523
 524       rtt_percentile = GetHistogram(
 525           "RTT.Percentile" + base::IntToString(kPercentiles[i]) + ".",
 526           current_network_id_.type, 10 * 1000);  // 10 seconds
 527       rtt_percentile->Add(rtt.InMilliseconds());
 528     }
 529   }
 530
 531   // Write the estimates of the previous network to the cache.
 532   CacheNetworkQualityEstimate();
 533
 534   // Clear the local state.
 535   last_connection_change_ = base::TimeTicks::Now();
 536   peak_network_quality_ = NetworkQuality();
 537   downstream_throughput_kbps_observations_.Clear();
 538   rtt_msec_observations_.Clear();
 539   current_network_id_ = GetCurrentNetworkID();
 540
 541   // Read any cached estimates for the new network. If cached estimates are
 542   // unavailable, add the default estimates.
 543   if (!ReadCachedNetworkQualityEstimate())
 544     AddDefaultEstimates();
 545   estimated_median_network_quality_ = NetworkQuality();
 546 }
 547
 548 bool NetworkQualityEstimator::GetRTTEstimate(base::TimeDelta* rtt) const {
 549   DCHECK(thread_checker_.CalledOnValidThread());
 550   DCHECK(rtt);
 551   if (rtt_msec_observations_.Size() == 0) {
 552     *rtt = InvalidRTT();
 553     return false;
 554   }
 555   *rtt = GetRTTEstimateInternal(base::TimeTicks(), 50);
 556   return (*rtt != InvalidRTT());
 557 }
 558
 559 bool NetworkQualityEstimator::GetDownlinkThroughputKbpsEstimate(
 560     int32_t* kbps) const {
 561   DCHECK(thread_checker_.CalledOnValidThread());
 562   DCHECK(kbps);
 563   if (downstream_throughput_kbps_observations_.Size() == 0) {
 564     *kbps = kInvalidThroughput;
 565     return false;
 566   }
 567   *kbps = GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50);
 568   return (*kbps != kInvalidThroughput);
 569 }
 570
 571 bool NetworkQualityEstimator::GetRecentMedianRTT(
 572     const base::TimeTicks& begin_timestamp,
 573     base::TimeDelta* rtt) const {
 574   DCHECK(thread_checker_.CalledOnValidThread());
 575   DCHECK(rtt);
 576   *rtt = GetRTTEstimateInternal(begin_timestamp, 50);
 577   return (*rtt != InvalidRTT());
 578 }
 579
 580 bool NetworkQualityEstimator::GetRecentMedianDownlinkThroughputKbps(
 581     const base::TimeTicks& begin_timestamp,
 582     int32_t* kbps) const {
 583   DCHECK(thread_checker_.CalledOnValidThread());
 584   DCHECK(kbps);
 585   *kbps = GetDownlinkThroughputKbpsEstimateInternal(begin_timestamp, 50);
 586   return (*kbps != kInvalidThroughput);
 587 }
 588
 589 NetworkQualityEstimator::Observation::Observation(int32_t value,
 590                                                   base::TimeTicks timestamp)
 591     : value(value), timestamp(timestamp) {
 592   DCHECK_GE(value, 0);
 593   DCHECK(!timestamp.is_null());
 594 }
 595
 596 NetworkQualityEstimator::Observation::~Observation() {
 597 }
 598
 599 NetworkQualityEstimator::ObservationBuffer::ObservationBuffer(
 600     double weight_multiplier_per_second)
 601     : weight_multiplier_per_second_(weight_multiplier_per_second) {
 602   static_assert(kMaximumObservationsBufferSize > 0U,
 603                 "Minimum size of observation buffer must be > 0");
 604   DCHECK_GE(weight_multiplier_per_second_, 0.0);
 605   DCHECK_LE(weight_multiplier_per_second_, 1.0);
 606 }
 607
 608 NetworkQualityEstimator::ObservationBuffer::~ObservationBuffer() {
 609 }
 610
 611 void NetworkQualityEstimator::ObservationBuffer::AddObservation(
 612     const Observation& observation) {
 613   DCHECK_LE(observations_.size(),
 614             static_cast<size_t>(kMaximumObservationsBufferSize));
 615   // Evict the oldest element if the buffer is already full.
 616   if (observations_.size() == kMaximumObservationsBufferSize)
 617     observations_.pop_front();
 618
 619   observations_.push_back(observation);
 620   DCHECK_LE(observations_.size(),
 621             static_cast<size_t>(kMaximumObservationsBufferSize));
 622 }
 623
 624 size_t NetworkQualityEstimator::ObservationBuffer::Size() const {
 625   return observations_.size();
 626 }
 627
 628 void NetworkQualityEstimator::ObservationBuffer::Clear() {
 629   observations_.clear();
 630   DCHECK(observations_.empty());
 631 }
 632
 633 base::TimeDelta NetworkQualityEstimator::GetRTTEstimateInternal(
 634     const base::TimeTicks& begin_timestamp,
 635     int percentile) const {
 636   DCHECK(thread_checker_.CalledOnValidThread());
 637   DCHECK_GE(percentile, 0);
 638   DCHECK_LE(percentile, 100);
 639   if (rtt_msec_observations_.Size() == 0)
 640     return InvalidRTT();
 641
 642   // RTT observations are sorted by duration from shortest to longest, thus
 643   // a higher percentile RTT will have a longer RTT than a lower percentile.
 644   base::TimeDelta rtt = InvalidRTT();
 645   int32_t rtt_result = -1;
 646   if (rtt_msec_observations_.GetPercentile(begin_timestamp, &rtt_result,
 647                                            percentile)) {
 648     rtt = base::TimeDelta::FromMilliseconds(rtt_result);
 649   }
 650   return rtt;
 651 }
 652
 653 int32_t NetworkQualityEstimator::GetDownlinkThroughputKbpsEstimateInternal(
 654     const base::TimeTicks& begin_timestamp,
 655     int percentile) const {
 656   DCHECK(thread_checker_.CalledOnValidThread());
 657   DCHECK_GE(percentile, 0);
 658   DCHECK_LE(percentile, 100);
 659   if (downstream_throughput_kbps_observations_.Size() == 0)
 660     return kInvalidThroughput;
 661
 662   // Throughput observations are sorted by kbps from slowest to fastest,
 663   // thus a higher percentile throughput will be faster than a lower one.
 664   int32_t kbps = kInvalidThroughput;
 665   downstream_throughput_kbps_observations_.GetPercentile(begin_timestamp, &kbps,
 666                                                          100 - percentile);
 667   return kbps;
 668 }
 669
 670 void NetworkQualityEstimator::ObservationBuffer::ComputeWeightedObservations(
 671     const base::TimeTicks& begin_timestamp,
 672     std::vector<WeightedObservation>& weighted_observations,
 673     double* total_weight) const {
 674   weighted_observations.clear();
 675   double total_weight_observations = 0.0;
 676   base::TimeTicks now = base::TimeTicks::Now();
 677
 678   for (const auto& observation : observations_) {
 679     if (observation.timestamp < begin_timestamp)
 680       continue;
 681     base::TimeDelta time_since_sample_taken = now - observation.timestamp;
 682     double weight =
 683         pow(weight_multiplier_per_second_, time_since_sample_taken.InSeconds());
 684     weight = std::max(DBL_MIN, std::min(1.0, weight));
 685
 686     weighted_observations.push_back(
 687         WeightedObservation(observation.value, weight));
 688     total_weight_observations += weight;
 689   }
 690
 691   // Sort the samples by value in ascending order.
 692   std::sort(weighted_observations.begin(), weighted_observations.end());
 693   *total_weight = total_weight_observations;
 694 }
 695
 696 bool NetworkQualityEstimator::ObservationBuffer::GetPercentile(
 697     const base::TimeTicks& begin_timestamp,
 698     int32_t* result,
 699     int percentile) const {
 700   DCHECK(result);
 701   // Stores WeightedObservation in increasing order of value.
 702   std::vector<WeightedObservation> weighted_observations;
 703
 704   // Total weight of all observations in |weighted_observations|.
 705   double total_weight = 0.0;
 706
 707   ComputeWeightedObservations(begin_timestamp, weighted_observations,
 708                               &total_weight);
 709   if (weighted_observations.empty())
 710     return false;
 711
 712   DCHECK(!weighted_observations.empty());
 713   DCHECK_GT(total_weight, 0.0);
 714
 715   // weighted_observations may have a smaller size than observations_ since the
 716   // former contains only the observations later than begin_timestamp.
 717   DCHECK_GE(observations_.size(), weighted_observations.size());
 718
 719   double desired_weight = percentile / 100.0 * total_weight;
 720
 721   double cumulative_weight_seen_so_far = 0.0;
 722   for (const auto& weighted_observation : weighted_observations) {
 723     cumulative_weight_seen_so_far += weighted_observation.weight;
 724
 725     // TODO(tbansal): Consider interpolating between observations.
 726     if (cumulative_weight_seen_so_far >= desired_weight) {
 727       *result = weighted_observation.value;
 728       return true;
 729     }
 730   }
 731
 732   // Computation may reach here due to floating point errors. This may happen
 733   // if |percentile| was 100 (or close to 100), and |desired_weight| was
 734   // slightly larger than |total_weight| (due to floating point errors).
 735   // In this case, we return the highest |value| among all observations.
 736   // This is same as value of the last observation in the sorted vector.
 737   *result = weighted_observations.at(weighted_observations.size() - 1).value;
 738   return true;
 739 }
 740
 741 NetworkQualityEstimator::NetworkID
 742 NetworkQualityEstimator::GetCurrentNetworkID() const {
 743   DCHECK(thread_checker_.CalledOnValidThread());
 744
 745   // TODO(tbansal): crbug.com/498068 Add NetworkQualityEstimatorAndroid class
 746   // that overrides this method on the Android platform.
 747
 748   // It is possible that the connection type changed between when
 749   // GetConnectionType() was called and when the API to determine the
 750   // network name was called. Check if that happened and retry until the
 751   // connection type stabilizes. This is an imperfect solution but should
 752   // capture majority of cases, and should not significantly affect estimates
 753   // (that are approximate to begin with).
 754   while (true) {
 755     NetworkQualityEstimator::NetworkID network_id(
 756         NetworkChangeNotifier::GetConnectionType(), std::string());
 757
 758     switch (network_id.type) {
 759       case NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN:
 760       case NetworkChangeNotifier::ConnectionType::CONNECTION_NONE:
 761       case NetworkChangeNotifier::ConnectionType::CONNECTION_BLUETOOTH:
 762       case NetworkChangeNotifier::ConnectionType::CONNECTION_ETHERNET:
 763         break;
 764       case NetworkChangeNotifier::ConnectionType::CONNECTION_WIFI:
 765 #if defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS) || \
 766     defined(OS_WIN)
 767         network_id.id = GetWifiSSID();
 768 #endif
 769         break;
 770       case NetworkChangeNotifier::ConnectionType::CONNECTION_2G:
 771       case NetworkChangeNotifier::ConnectionType::CONNECTION_3G:
 772       case NetworkChangeNotifier::ConnectionType::CONNECTION_4G:
 773 #if defined(OS_ANDROID)
 774         network_id.id = android::GetTelephonyNetworkOperator();
 775 #endif
 776         break;
 777       default:
 778         NOTREACHED() << "Unexpected connection type = " << network_id.type;
 779         break;
 780     }
 781
 782     if (network_id.type == NetworkChangeNotifier::GetConnectionType())
 783       return network_id;
 784   }
 785   NOTREACHED();
 786 }
 787
 788 bool NetworkQualityEstimator::ReadCachedNetworkQualityEstimate() {
 789   DCHECK(thread_checker_.CalledOnValidThread());
 790
 791   // If the network name is unavailable, caching should not be performed.
 792   if (current_network_id_.id.empty())
 793     return false;
 794
 795   CachedNetworkQualities::const_iterator it =
 796       cached_network_qualities_.find(current_network_id_);
 797
 798   if (it == cached_network_qualities_.end())
 799     return false;
 800
 801   NetworkQuality network_quality(it->second.network_quality());
 802
 803   DCHECK_NE(InvalidRTT(), network_quality.rtt());
 804   DCHECK_NE(kInvalidThroughput, network_quality.downstream_throughput_kbps());
 805
 806   downstream_throughput_kbps_observations_.AddObservation(Observation(
 807       network_quality.downstream_throughput_kbps(), base::TimeTicks::Now()));
 808   rtt_msec_observations_.AddObservation(Observation(
 809       network_quality.rtt().InMilliseconds(), base::TimeTicks::Now()));
 810   return true;
 811 }
 812
 813 void NetworkQualityEstimator::OnUpdatedEstimateAvailable() {
 814   DCHECK(thread_checker_.CalledOnValidThread());
 815   DCHECK(external_estimates_provider_);
 816   // TODO(tbansal): Query provider for the recent value.
 817 }
 818
 819 void NetworkQualityEstimator::CacheNetworkQualityEstimate() {
 820   DCHECK(thread_checker_.CalledOnValidThread());
 821   DCHECK_LE(cached_network_qualities_.size(),
 822             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 823
 824   // If the network name is unavailable, caching should not be performed.
 825   if (current_network_id_.id.empty())
 826     return;
 827
 828   NetworkQuality network_quality = NetworkQuality(
 829       GetRTTEstimateInternal(base::TimeTicks(), 50),
 830       GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50));
 831   if (network_quality.rtt() == InvalidRTT() ||
 832       network_quality.downstream_throughput_kbps() == kInvalidThroughput) {
 833     return;
 834   }
 835
 836   if (cached_network_qualities_.size() == kMaximumNetworkQualityCacheSize) {
 837     // Remove the oldest entry.
 838     CachedNetworkQualities::iterator oldest_entry_iterator =
 839         cached_network_qualities_.begin();
 840
 841     for (CachedNetworkQualities::iterator it =
 842              cached_network_qualities_.begin();
 843          it != cached_network_qualities_.end(); ++it) {
 844       if ((it->second).OlderThan(oldest_entry_iterator->second))
 845         oldest_entry_iterator = it;
 846     }
 847     cached_network_qualities_.erase(oldest_entry_iterator);
 848   }
 849   DCHECK_LT(cached_network_qualities_.size(),
 850             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 851
 852   cached_network_qualities_.insert(std::make_pair(
 853       current_network_id_, CachedNetworkQuality(network_quality)));
 854   DCHECK_LE(cached_network_qualities_.size(),
 855             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 856 }
 857
 858 scoped_ptr<SocketPerformanceWatcher>
 859 NetworkQualityEstimator::CreateTCPSocketPerformanceWatcher() const {
 860   DCHECK(thread_checker_.CalledOnValidThread());
 861   return scoped_ptr<SocketPerformanceWatcher>(
 862       new SocketPerformanceWatcherTCP());
 863 }
 864
 865 scoped_ptr<SocketPerformanceWatcher>
 866 NetworkQualityEstimator::CreateUDPSocketPerformanceWatcher() const {
 867   DCHECK(thread_checker_.CalledOnValidThread());
 868   return scoped_ptr<SocketPerformanceWatcher>(
 869       new SocketPerformanceWatcherUDP());
 870 }
 871
 872 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
 873     const NetworkQuality& network_quality)
 874     : last_update_time_(base::TimeTicks::Now()),
 875       network_quality_(network_quality) {
 876 }
 877
 878 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
 879     const CachedNetworkQuality& other)
 880     : last_update_time_(other.last_update_time_),
 881       network_quality_(other.network_quality_) {
 882 }
 883
 884 NetworkQualityEstimator::CachedNetworkQuality::~CachedNetworkQuality() {
 885 }
 886
 887 bool NetworkQualityEstimator::CachedNetworkQuality::OlderThan(
 888     const CachedNetworkQuality& cached_network_quality) const {
 889   return last_update_time_ < cached_network_quality.last_update_time_;
 890 }
 891
 892 NetworkQualityEstimator::NetworkQuality::NetworkQuality()
 893     : NetworkQuality(NetworkQualityEstimator::InvalidRTT(),
 894                      NetworkQualityEstimator::kInvalidThroughput) {}
 895
 896 NetworkQualityEstimator::NetworkQuality::NetworkQuality(
 897     const base::TimeDelta& rtt,
 898     int32_t downstream_throughput_kbps)
 899     : rtt_(rtt), downstream_throughput_kbps_(downstream_throughput_kbps) {
 900   DCHECK_GE(rtt_, base::TimeDelta());
 901   DCHECK_GE(downstream_throughput_kbps_, 0);
 902 }
 903
 904 NetworkQualityEstimator::NetworkQuality::NetworkQuality(
 905     const NetworkQuality& other)
 906     : NetworkQuality(other.rtt_, other.downstream_throughput_kbps_) {}
 907
 908 NetworkQualityEstimator::NetworkQuality::~NetworkQuality() {}
 909
 910 NetworkQualityEstimator::NetworkQuality&
 911     NetworkQualityEstimator::NetworkQuality::
 912     operator=(const NetworkQuality& other) {
 913   rtt_ = other.rtt_;
 914   downstream_throughput_kbps_ = other.downstream_throughput_kbps_;
 915   return *this;
 916 }
 917
 918 }  // namespace net