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_estimate_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_estimate_provider_) {
 196     RecordExternalEstimateProviderMetrics(
 197         EXTERNAL_ESTIMATE_PROVIDER_STATUS_AVAILABLE);
 198     external_estimate_provider_->SetUpdatedEstimateDelegate(this);
 199     QueryExternalEstimateProvider();
 200   } else {
 201     RecordExternalEstimateProviderMetrics(
 202         EXTERNAL_ESTIMATE_PROVIDER_STATUS_NOT_AVAILABLE);
 203   }
 204   current_network_id_ = GetCurrentNetworkID();
 205   AddDefaultEstimates();
 206 }
 207
 208 // static
 209 const base::TimeDelta NetworkQualityEstimator::InvalidRTT() {
 210   return base::TimeDelta::Max();
 211 }
 212
 213 void NetworkQualityEstimator::ObtainOperatingParams(
 214     const std::map<std::string, std::string>& variation_params) {
 215   DCHECK(thread_checker_.CalledOnValidThread());
 216
 217   for (size_t i = 0; i <= NetworkChangeNotifier::CONNECTION_LAST; ++i) {
 218     NetworkChangeNotifier::ConnectionType type =
 219         static_cast<NetworkChangeNotifier::ConnectionType>(i);
 220     DCHECK_EQ(InvalidRTT(), default_observations_[i].rtt());
 221     DCHECK_EQ(kInvalidThroughput,
 222               default_observations_[i].downstream_throughput_kbps());
 223     int32_t variations_value = kMinimumRTTVariationParameterMsec - 1;
 224     // Name of the parameter that holds the RTT value for this connection type.
 225     std::string rtt_parameter_name =
 226         std::string(GetNameForConnectionType(type))
 227             .append(kDefaultRTTMsecObservationSuffix);
 228     auto it = variation_params.find(rtt_parameter_name);
 229     if (it != variation_params.end() &&
 230         base::StringToInt(it->second, &variations_value) &&
 231         variations_value >= kMinimumRTTVariationParameterMsec) {
 232       default_observations_[i] =
 233           NetworkQuality(base::TimeDelta::FromMilliseconds(variations_value),
 234                          default_observations_[i].downstream_throughput_kbps());
 235     }
 236
 237     variations_value = kMinimumThroughputVariationParameterKbps - 1;
 238     // Name of the parameter that holds the Kbps value for this connection
 239     // type.
 240     std::string kbps_parameter_name =
 241         std::string(GetNameForConnectionType(type))
 242             .append(kDefaultKbpsObservationSuffix);
 243     it = variation_params.find(kbps_parameter_name);
 244     if (it != variation_params.end() &&
 245         base::StringToInt(it->second, &variations_value) &&
 246         variations_value >= kMinimumThroughputVariationParameterKbps) {
 247       default_observations_[i] =
 248           NetworkQuality(default_observations_[i].rtt(), variations_value);
 249     }
 250   }
 251 }
 252
 253 void NetworkQualityEstimator::AddDefaultEstimates() {
 254   DCHECK(thread_checker_.CalledOnValidThread());
 255   if (default_observations_[current_network_id_.type].rtt() != InvalidRTT()) {
 256     rtt_msec_observations_.AddObservation(Observation(
 257         default_observations_[current_network_id_.type].rtt().InMilliseconds(),
 258         base::TimeTicks::Now()));
 259   }
 260   if (default_observations_[current_network_id_.type]
 261           .downstream_throughput_kbps() != kInvalidThroughput) {
 262     downstream_throughput_kbps_observations_.AddObservation(
 263         Observation(default_observations_[current_network_id_.type]
 264                         .downstream_throughput_kbps(),
 265                     base::TimeTicks::Now()));
 266   }
 267 }
 268
 269 NetworkQualityEstimator::~NetworkQualityEstimator() {
 270   DCHECK(thread_checker_.CalledOnValidThread());
 271   NetworkChangeNotifier::RemoveConnectionTypeObserver(this);
 272 }
 273
 274 void NetworkQualityEstimator::NotifyHeadersReceived(const URLRequest& request) {
 275   DCHECK(thread_checker_.CalledOnValidThread());
 276
 277   if (!RequestProvidesUsefulObservations(request))
 278     return;
 279
 280   // Update |estimated_median_network_quality_| if this is a main frame request.
 281   if (request.load_flags() & LOAD_MAIN_FRAME) {
 282     estimated_median_network_quality_ = NetworkQuality(
 283         GetRTTEstimateInternal(base::TimeTicks(), 50),
 284         GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50));
 285   }
 286
 287   base::TimeTicks now = base::TimeTicks::Now();
 288   LoadTimingInfo load_timing_info;
 289   request.GetLoadTimingInfo(&load_timing_info);
 290
 291   // If the load timing info is unavailable, it probably means that the request
 292   // did not go over the network.
 293   if (load_timing_info.send_start.is_null() ||
 294       load_timing_info.receive_headers_end.is_null()) {
 295     return;
 296   }
 297
 298   // Time when the resource was requested.
 299   base::TimeTicks request_start_time = load_timing_info.send_start;
 300
 301   // Time when the headers were received.
 302   base::TimeTicks headers_received_time = load_timing_info.receive_headers_end;
 303
 304   // Duration between when the resource was requested and when response
 305   // headers were received.
 306     base::TimeDelta observed_rtt = headers_received_time - request_start_time;
 307     DCHECK_GE(observed_rtt, base::TimeDelta());
 308     if (observed_rtt < peak_network_quality_.rtt()) {
 309       peak_network_quality_ = NetworkQuality(
 310           observed_rtt, peak_network_quality_.downstream_throughput_kbps());
 311     }
 312
 313     rtt_msec_observations_.AddObservation(
 314         Observation(observed_rtt.InMilliseconds(), now));
 315
 316     // Compare the RTT observation with the estimated value and record it.
 317     if (estimated_median_network_quality_.rtt() != InvalidRTT()) {
 318       RecordRTTUMA(estimated_median_network_quality_.rtt().InMilliseconds(),
 319                    observed_rtt.InMilliseconds());
 320     }
 321 }
 322
 323 void NetworkQualityEstimator::NotifyRequestCompleted(
 324     const URLRequest& request) {
 325   DCHECK(thread_checker_.CalledOnValidThread());
 326
 327   if (!RequestProvidesUsefulObservations(request))
 328     return;
 329
 330   base::TimeTicks now = base::TimeTicks::Now();
 331   LoadTimingInfo load_timing_info;
 332   request.GetLoadTimingInfo(&load_timing_info);
 333
 334   // If the load timing info is unavailable, it probably means that the request
 335   // did not go over the network.
 336   if (load_timing_info.send_start.is_null() ||
 337       load_timing_info.receive_headers_end.is_null()) {
 338     return;
 339   }
 340
 341   // Time since the resource was requested.
 342   // TODO(tbansal): Change the start time to receive_headers_end, once we use
 343   // NetworkActivityMonitor.
 344   base::TimeDelta request_start_to_completed =
 345       now - load_timing_info.send_start;
 346   DCHECK_GE(request_start_to_completed, base::TimeDelta());
 347
 348   // Ignore tiny transfers which will not produce accurate rates.
 349   // Ignore short duration transfers.
 350   // Skip the checks if |allow_small_responses_| is true.
 351   if (!allow_small_responses_ &&
 352       (request.GetTotalReceivedBytes() < kMinTransferSizeInBytes ||
 353        request_start_to_completed < base::TimeDelta::FromMicroseconds(
 354                                         kMinRequestDurationMicroseconds))) {
 355     return;
 356   }
 357
 358   double downstream_kbps = request.GetTotalReceivedBytes() * 8.0 / 1000.0 /
 359                            request_start_to_completed.InSecondsF();
 360   DCHECK_GE(downstream_kbps, 0.0);
 361
 362   // Check overflow errors. This may happen if the downstream_kbps is more than
 363   // 2 * 10^9 (= 2000 Gbps).
 364   if (downstream_kbps >= std::numeric_limits<int32_t>::max())
 365     downstream_kbps = std::numeric_limits<int32_t>::max();
 366
 367   int32_t downstream_kbps_as_integer = static_cast<int32_t>(downstream_kbps);
 368
 369   // Round up |downstream_kbps_as_integer|. If the |downstream_kbps_as_integer|
 370   // is less than 1, it is set to 1 to differentiate from case when there is no
 371   // connection.
 372   if (downstream_kbps - downstream_kbps_as_integer > 0)
 373     downstream_kbps_as_integer++;
 374
 375   DCHECK_GT(downstream_kbps_as_integer, 0.0);
 376   if (downstream_kbps_as_integer >
 377       peak_network_quality_.downstream_throughput_kbps())
 378     peak_network_quality_ =
 379         NetworkQuality(peak_network_quality_.rtt(), downstream_kbps_as_integer);
 380
 381   downstream_throughput_kbps_observations_.AddObservation(
 382       Observation(downstream_kbps_as_integer, now));
 383 }
 384
 385 void NetworkQualityEstimator::RecordRTTUMA(int32_t estimated_value_msec,
 386                                            int32_t actual_value_msec) const {
 387   DCHECK(thread_checker_.CalledOnValidThread());
 388
 389   // Record the difference between the actual and the estimated value.
 390   if (estimated_value_msec >= actual_value_msec) {
 391     base::HistogramBase* difference_rtt =
 392         GetHistogram("DifferenceRTTEstimatedAndActual.",
 393                      current_network_id_.type, 10 * 1000);  // 10 seconds
 394     difference_rtt->Add(estimated_value_msec - actual_value_msec);
 395   } else {
 396     base::HistogramBase* difference_rtt =
 397         GetHistogram("DifferenceRTTActualAndEstimated.",
 398                      current_network_id_.type, 10 * 1000);  // 10 seconds
 399     difference_rtt->Add(actual_value_msec - estimated_value_msec);
 400   }
 401
 402   // Record all the RTT observations.
 403   base::HistogramBase* rtt_observations =
 404       GetHistogram("RTTObservations.", current_network_id_.type,
 405                    10 * 1000);  // 10 seconds upper bound
 406   rtt_observations->Add(actual_value_msec);
 407
 408   if (actual_value_msec == 0)
 409     return;
 410
 411   int32 ratio = (estimated_value_msec * 100) / actual_value_msec;
 412
 413   // Record the accuracy of estimation by recording the ratio of estimated
 414   // value to the actual value.
 415   base::HistogramBase* ratio_median_rtt = GetHistogram(
 416       "RatioEstimatedToActualRTT.", current_network_id_.type, 1000);
 417   ratio_median_rtt->Add(ratio);
 418 }
 419
 420 bool NetworkQualityEstimator::RequestProvidesUsefulObservations(
 421     const URLRequest& request) const {
 422   return request.url().is_valid() &&
 423          (allow_localhost_requests_ || !IsLocalhost(request.url().host())) &&
 424          request.url().SchemeIsHTTPOrHTTPS() &&
 425          // Verify that response headers are received, so it can be ensured that
 426          // response is not cached.
 427          !request.response_info().response_time.is_null() &&
 428          !request.was_cached() &&
 429          request.creation_time() >= last_connection_change_;
 430 }
 431
 432 void NetworkQualityEstimator::RecordExternalEstimateProviderMetrics(
 433     NQEExternalEstimateProviderStatus status) const {
 434   UMA_HISTOGRAM_ENUMERATION("NQE.ExternalEstimateProviderStatus", status,
 435                             EXTERNAL_ESTIMATE_PROVIDER_STATUS_BOUNDARY);
 436 }
 437
 438 void NetworkQualityEstimator::OnConnectionTypeChanged(
 439     NetworkChangeNotifier::ConnectionType type) {
 440   DCHECK(thread_checker_.CalledOnValidThread());
 441   if (peak_network_quality_.rtt() != InvalidRTT()) {
 442     switch (current_network_id_.type) {
 443       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 444         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
 445                             peak_network_quality_.rtt());
 446         break;
 447       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 448         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Ethernet",
 449                             peak_network_quality_.rtt());
 450         break;
 451       case NetworkChangeNotifier::CONNECTION_WIFI:
 452         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi", peak_network_quality_.rtt());
 453         break;
 454       case NetworkChangeNotifier::CONNECTION_2G:
 455         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.2G", peak_network_quality_.rtt());
 456         break;
 457       case NetworkChangeNotifier::CONNECTION_3G:
 458         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.3G", peak_network_quality_.rtt());
 459         break;
 460       case NetworkChangeNotifier::CONNECTION_4G:
 461         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.4G", peak_network_quality_.rtt());
 462         break;
 463       case NetworkChangeNotifier::CONNECTION_NONE:
 464         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None", peak_network_quality_.rtt());
 465         break;
 466       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 467         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Bluetooth",
 468                             peak_network_quality_.rtt());
 469         break;
 470       default:
 471         NOTREACHED() << "Unexpected connection type = "
 472                      << current_network_id_.type;
 473         break;
 474     }
 475   }
 476
 477   if (peak_network_quality_.downstream_throughput_kbps() !=
 478       kInvalidThroughput) {
 479     switch (current_network_id_.type) {
 480       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 481         UMA_HISTOGRAM_COUNTS(
 482             "NQE.PeakKbps.Unknown",
 483             peak_network_quality_.downstream_throughput_kbps());
 484         break;
 485       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 486         UMA_HISTOGRAM_COUNTS(
 487             "NQE.PeakKbps.Ethernet",
 488             peak_network_quality_.downstream_throughput_kbps());
 489         break;
 490       case NetworkChangeNotifier::CONNECTION_WIFI:
 491         UMA_HISTOGRAM_COUNTS(
 492             "NQE.PeakKbps.Wifi",
 493             peak_network_quality_.downstream_throughput_kbps());
 494         break;
 495       case NetworkChangeNotifier::CONNECTION_2G:
 496         UMA_HISTOGRAM_COUNTS(
 497             "NQE.PeakKbps.2G",
 498             peak_network_quality_.downstream_throughput_kbps());
 499         break;
 500       case NetworkChangeNotifier::CONNECTION_3G:
 501         UMA_HISTOGRAM_COUNTS(
 502             "NQE.PeakKbps.3G",
 503             peak_network_quality_.downstream_throughput_kbps());
 504         break;
 505       case NetworkChangeNotifier::CONNECTION_4G:
 506         UMA_HISTOGRAM_COUNTS(
 507             "NQE.PeakKbps.4G",
 508             peak_network_quality_.downstream_throughput_kbps());
 509         break;
 510       case NetworkChangeNotifier::CONNECTION_NONE:
 511         UMA_HISTOGRAM_COUNTS(
 512             "NQE.PeakKbps.None",
 513             peak_network_quality_.downstream_throughput_kbps());
 514         break;
 515       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 516         UMA_HISTOGRAM_COUNTS(
 517             "NQE.PeakKbps.Bluetooth",
 518             peak_network_quality_.downstream_throughput_kbps());
 519         break;
 520       default:
 521         NOTREACHED() << "Unexpected connection type = "
 522                      << current_network_id_.type;
 523         break;
 524     }
 525   }
 526
 527   base::TimeDelta rtt = GetRTTEstimateInternal(base::TimeTicks(), 50);
 528   if (rtt != InvalidRTT()) {
 529     // Add the 50th percentile value.
 530     base::HistogramBase* rtt_percentile =
 531         GetHistogram("RTT.Percentile50.", current_network_id_.type,
 532                      10 * 1000);  // 10 seconds
 533     rtt_percentile->Add(rtt.InMilliseconds());
 534
 535     // Add the remaining percentile values.
 536     static const int kPercentiles[] = {0, 10, 90, 100};
 537     for (size_t i = 0; i < arraysize(kPercentiles); ++i) {
 538       rtt = GetRTTEstimateInternal(base::TimeTicks(), kPercentiles[i]);
 539
 540       rtt_percentile = GetHistogram(
 541           "RTT.Percentile" + base::IntToString(kPercentiles[i]) + ".",
 542           current_network_id_.type, 10 * 1000);  // 10 seconds
 543       rtt_percentile->Add(rtt.InMilliseconds());
 544     }
 545   }
 546
 547   // Write the estimates of the previous network to the cache.
 548   CacheNetworkQualityEstimate();
 549
 550   // Clear the local state.
 551   last_connection_change_ = base::TimeTicks::Now();
 552   peak_network_quality_ = NetworkQuality();
 553   downstream_throughput_kbps_observations_.Clear();
 554   rtt_msec_observations_.Clear();
 555   current_network_id_ = GetCurrentNetworkID();
 556
 557   QueryExternalEstimateProvider();
 558
 559   // Read any cached estimates for the new network. If cached estimates are
 560   // unavailable, add the default estimates.
 561   if (!ReadCachedNetworkQualityEstimate())
 562     AddDefaultEstimates();
 563   estimated_median_network_quality_ = NetworkQuality();
 564 }
 565
 566 bool NetworkQualityEstimator::GetRTTEstimate(base::TimeDelta* rtt) const {
 567   DCHECK(thread_checker_.CalledOnValidThread());
 568   DCHECK(rtt);
 569   if (rtt_msec_observations_.Size() == 0) {
 570     *rtt = InvalidRTT();
 571     return false;
 572   }
 573   *rtt = GetRTTEstimateInternal(base::TimeTicks(), 50);
 574   return (*rtt != InvalidRTT());
 575 }
 576
 577 bool NetworkQualityEstimator::GetDownlinkThroughputKbpsEstimate(
 578     int32_t* kbps) const {
 579   DCHECK(thread_checker_.CalledOnValidThread());
 580   DCHECK(kbps);
 581   if (downstream_throughput_kbps_observations_.Size() == 0) {
 582     *kbps = kInvalidThroughput;
 583     return false;
 584   }
 585   *kbps = GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50);
 586   return (*kbps != kInvalidThroughput);
 587 }
 588
 589 bool NetworkQualityEstimator::GetRecentMedianRTT(
 590     const base::TimeTicks& begin_timestamp,
 591     base::TimeDelta* rtt) const {
 592   DCHECK(thread_checker_.CalledOnValidThread());
 593   DCHECK(rtt);
 594   *rtt = GetRTTEstimateInternal(begin_timestamp, 50);
 595   return (*rtt != InvalidRTT());
 596 }
 597
 598 bool NetworkQualityEstimator::GetRecentMedianDownlinkThroughputKbps(
 599     const base::TimeTicks& begin_timestamp,
 600     int32_t* kbps) const {
 601   DCHECK(thread_checker_.CalledOnValidThread());
 602   DCHECK(kbps);
 603   *kbps = GetDownlinkThroughputKbpsEstimateInternal(begin_timestamp, 50);
 604   return (*kbps != kInvalidThroughput);
 605 }
 606
 607 NetworkQualityEstimator::Observation::Observation(int32_t value,
 608                                                   base::TimeTicks timestamp)
 609     : value(value), timestamp(timestamp) {
 610   DCHECK_GE(value, 0);
 611   DCHECK(!timestamp.is_null());
 612 }
 613
 614 NetworkQualityEstimator::Observation::~Observation() {
 615 }
 616
 617 NetworkQualityEstimator::ObservationBuffer::ObservationBuffer(
 618     double weight_multiplier_per_second)
 619     : weight_multiplier_per_second_(weight_multiplier_per_second) {
 620   static_assert(kMaximumObservationsBufferSize > 0U,
 621                 "Minimum size of observation buffer must be > 0");
 622   DCHECK_GE(weight_multiplier_per_second_, 0.0);
 623   DCHECK_LE(weight_multiplier_per_second_, 1.0);
 624 }
 625
 626 NetworkQualityEstimator::ObservationBuffer::~ObservationBuffer() {
 627 }
 628
 629 void NetworkQualityEstimator::ObservationBuffer::AddObservation(
 630     const Observation& observation) {
 631   DCHECK_LE(observations_.size(),
 632             static_cast<size_t>(kMaximumObservationsBufferSize));
 633   // Evict the oldest element if the buffer is already full.
 634   if (observations_.size() == kMaximumObservationsBufferSize)
 635     observations_.pop_front();
 636
 637   observations_.push_back(observation);
 638   DCHECK_LE(observations_.size(),
 639             static_cast<size_t>(kMaximumObservationsBufferSize));
 640 }
 641
 642 size_t NetworkQualityEstimator::ObservationBuffer::Size() const {
 643   return observations_.size();
 644 }
 645
 646 void NetworkQualityEstimator::ObservationBuffer::Clear() {
 647   observations_.clear();
 648   DCHECK(observations_.empty());
 649 }
 650
 651 base::TimeDelta NetworkQualityEstimator::GetRTTEstimateInternal(
 652     const base::TimeTicks& begin_timestamp,
 653     int percentile) const {
 654   DCHECK(thread_checker_.CalledOnValidThread());
 655   DCHECK_GE(percentile, 0);
 656   DCHECK_LE(percentile, 100);
 657   if (rtt_msec_observations_.Size() == 0)
 658     return InvalidRTT();
 659
 660   // RTT observations are sorted by duration from shortest to longest, thus
 661   // a higher percentile RTT will have a longer RTT than a lower percentile.
 662   base::TimeDelta rtt = InvalidRTT();
 663   int32_t rtt_result = -1;
 664   if (rtt_msec_observations_.GetPercentile(begin_timestamp, &rtt_result,
 665                                            percentile)) {
 666     rtt = base::TimeDelta::FromMilliseconds(rtt_result);
 667   }
 668   return rtt;
 669 }
 670
 671 int32_t NetworkQualityEstimator::GetDownlinkThroughputKbpsEstimateInternal(
 672     const base::TimeTicks& begin_timestamp,
 673     int percentile) const {
 674   DCHECK(thread_checker_.CalledOnValidThread());
 675   DCHECK_GE(percentile, 0);
 676   DCHECK_LE(percentile, 100);
 677   if (downstream_throughput_kbps_observations_.Size() == 0)
 678     return kInvalidThroughput;
 679
 680   // Throughput observations are sorted by kbps from slowest to fastest,
 681   // thus a higher percentile throughput will be faster than a lower one.
 682   int32_t kbps = kInvalidThroughput;
 683   downstream_throughput_kbps_observations_.GetPercentile(begin_timestamp, &kbps,
 684                                                          100 - percentile);
 685   return kbps;
 686 }
 687
 688 void NetworkQualityEstimator::ObservationBuffer::ComputeWeightedObservations(
 689     const base::TimeTicks& begin_timestamp,
 690     std::vector<WeightedObservation>& weighted_observations,
 691     double* total_weight) const {
 692   weighted_observations.clear();
 693   double total_weight_observations = 0.0;
 694   base::TimeTicks now = base::TimeTicks::Now();
 695
 696   for (const auto& observation : observations_) {
 697     if (observation.timestamp < begin_timestamp)
 698       continue;
 699     base::TimeDelta time_since_sample_taken = now - observation.timestamp;
 700     double weight =
 701         pow(weight_multiplier_per_second_, time_since_sample_taken.InSeconds());
 702     weight = std::max(DBL_MIN, std::min(1.0, weight));
 703
 704     weighted_observations.push_back(
 705         WeightedObservation(observation.value, weight));
 706     total_weight_observations += weight;
 707   }
 708
 709   // Sort the samples by value in ascending order.
 710   std::sort(weighted_observations.begin(), weighted_observations.end());
 711   *total_weight = total_weight_observations;
 712 }
 713
 714 bool NetworkQualityEstimator::ObservationBuffer::GetPercentile(
 715     const base::TimeTicks& begin_timestamp,
 716     int32_t* result,
 717     int percentile) const {
 718   DCHECK(result);
 719   // Stores WeightedObservation in increasing order of value.
 720   std::vector<WeightedObservation> weighted_observations;
 721
 722   // Total weight of all observations in |weighted_observations|.
 723   double total_weight = 0.0;
 724
 725   ComputeWeightedObservations(begin_timestamp, weighted_observations,
 726                               &total_weight);
 727   if (weighted_observations.empty())
 728     return false;
 729
 730   DCHECK(!weighted_observations.empty());
 731   DCHECK_GT(total_weight, 0.0);
 732
 733   // weighted_observations may have a smaller size than observations_ since the
 734   // former contains only the observations later than begin_timestamp.
 735   DCHECK_GE(observations_.size(), weighted_observations.size());
 736
 737   double desired_weight = percentile / 100.0 * total_weight;
 738
 739   double cumulative_weight_seen_so_far = 0.0;
 740   for (const auto& weighted_observation : weighted_observations) {
 741     cumulative_weight_seen_so_far += weighted_observation.weight;
 742
 743     // TODO(tbansal): Consider interpolating between observations.
 744     if (cumulative_weight_seen_so_far >= desired_weight) {
 745       *result = weighted_observation.value;
 746       return true;
 747     }
 748   }
 749
 750   // Computation may reach here due to floating point errors. This may happen
 751   // if |percentile| was 100 (or close to 100), and |desired_weight| was
 752   // slightly larger than |total_weight| (due to floating point errors).
 753   // In this case, we return the highest |value| among all observations.
 754   // This is same as value of the last observation in the sorted vector.
 755   *result = weighted_observations.at(weighted_observations.size() - 1).value;
 756   return true;
 757 }
 758
 759 NetworkQualityEstimator::NetworkID
 760 NetworkQualityEstimator::GetCurrentNetworkID() const {
 761   DCHECK(thread_checker_.CalledOnValidThread());
 762
 763   // TODO(tbansal): crbug.com/498068 Add NetworkQualityEstimatorAndroid class
 764   // that overrides this method on the Android platform.
 765
 766   // It is possible that the connection type changed between when
 767   // GetConnectionType() was called and when the API to determine the
 768   // network name was called. Check if that happened and retry until the
 769   // connection type stabilizes. This is an imperfect solution but should
 770   // capture majority of cases, and should not significantly affect estimates
 771   // (that are approximate to begin with).
 772   while (true) {
 773     NetworkQualityEstimator::NetworkID network_id(
 774         NetworkChangeNotifier::GetConnectionType(), std::string());
 775
 776     switch (network_id.type) {
 777       case NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN:
 778       case NetworkChangeNotifier::ConnectionType::CONNECTION_NONE:
 779       case NetworkChangeNotifier::ConnectionType::CONNECTION_BLUETOOTH:
 780       case NetworkChangeNotifier::ConnectionType::CONNECTION_ETHERNET:
 781         break;
 782       case NetworkChangeNotifier::ConnectionType::CONNECTION_WIFI:
 783 #if defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS) || \
 784     defined(OS_WIN)
 785         network_id.id = GetWifiSSID();
 786 #endif
 787         break;
 788       case NetworkChangeNotifier::ConnectionType::CONNECTION_2G:
 789       case NetworkChangeNotifier::ConnectionType::CONNECTION_3G:
 790       case NetworkChangeNotifier::ConnectionType::CONNECTION_4G:
 791 #if defined(OS_ANDROID)
 792         network_id.id = android::GetTelephonyNetworkOperator();
 793 #endif
 794         break;
 795       default:
 796         NOTREACHED() << "Unexpected connection type = " << network_id.type;
 797         break;
 798     }
 799
 800     if (network_id.type == NetworkChangeNotifier::GetConnectionType())
 801       return network_id;
 802   }
 803   NOTREACHED();
 804 }
 805
 806 bool NetworkQualityEstimator::ReadCachedNetworkQualityEstimate() {
 807   DCHECK(thread_checker_.CalledOnValidThread());
 808
 809   // If the network name is unavailable, caching should not be performed.
 810   if (current_network_id_.id.empty())
 811     return false;
 812
 813   CachedNetworkQualities::const_iterator it =
 814       cached_network_qualities_.find(current_network_id_);
 815
 816   if (it == cached_network_qualities_.end())
 817     return false;
 818
 819   NetworkQuality network_quality(it->second.network_quality());
 820
 821   DCHECK_NE(InvalidRTT(), network_quality.rtt());
 822   DCHECK_NE(kInvalidThroughput, network_quality.downstream_throughput_kbps());
 823
 824   downstream_throughput_kbps_observations_.AddObservation(Observation(
 825       network_quality.downstream_throughput_kbps(), base::TimeTicks::Now()));
 826   rtt_msec_observations_.AddObservation(Observation(
 827       network_quality.rtt().InMilliseconds(), base::TimeTicks::Now()));
 828   return true;
 829 }
 830
 831 void NetworkQualityEstimator::OnUpdatedEstimateAvailable() {
 832   DCHECK(thread_checker_.CalledOnValidThread());
 833   DCHECK(external_estimate_provider_);
 834
 835   RecordExternalEstimateProviderMetrics(
 836       EXTERNAL_ESTIMATE_PROVIDER_STATUS_CALLBACK);
 837   QueryExternalEstimateProvider();
 838 }
 839
 840 void NetworkQualityEstimator::QueryExternalEstimateProvider() {
 841   DCHECK(thread_checker_.CalledOnValidThread());
 842
 843   if (!external_estimate_provider_)
 844     return;
 845   RecordExternalEstimateProviderMetrics(
 846       EXTERNAL_ESTIMATE_PROVIDER_STATUS_QUERIED);
 847
 848   base::TimeDelta time_since_last_update;
 849
 850   // Request a new estimate if estimate is not available, or if the available
 851   // estimate is not fresh.
 852   if (!external_estimate_provider_->GetTimeSinceLastUpdate(
 853           &time_since_last_update) ||
 854       time_since_last_update >
 855           base::TimeDelta::FromMilliseconds(
 856               kExternalEstimateProviderFreshnessDurationMsec)) {
 857     // Request the external estimate provider for updated estimates. When the
 858     // updates estimates are available, OnUpdatedEstimateAvailable() will be
 859     // called.
 860     external_estimate_provider_->Update();
 861     return;
 862   }
 863
 864   RecordExternalEstimateProviderMetrics(
 865       EXTERNAL_ESTIMATE_PROVIDER_STATUS_QUERY_SUCCESSFUL);
 866   base::TimeDelta rtt;
 867   if (external_estimate_provider_->GetRTT(&rtt)) {
 868     rtt_msec_observations_.AddObservation(
 869         Observation(rtt.InMilliseconds(), base::TimeTicks::Now()));
 870   }
 871
 872   int32_t downstream_throughput_kbps;
 873   if (external_estimate_provider_->GetDownstreamThroughputKbps(
 874           &downstream_throughput_kbps)) {
 875     downstream_throughput_kbps_observations_.AddObservation(
 876         Observation(downstream_throughput_kbps, base::TimeTicks::Now()));
 877   }
 878 }
 879
 880 void NetworkQualityEstimator::CacheNetworkQualityEstimate() {
 881   DCHECK(thread_checker_.CalledOnValidThread());
 882   DCHECK_LE(cached_network_qualities_.size(),
 883             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 884
 885   // If the network name is unavailable, caching should not be performed.
 886   if (current_network_id_.id.empty())
 887     return;
 888
 889   NetworkQuality network_quality = NetworkQuality(
 890       GetRTTEstimateInternal(base::TimeTicks(), 50),
 891       GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50));
 892   if (network_quality.rtt() == InvalidRTT() ||
 893       network_quality.downstream_throughput_kbps() == kInvalidThroughput) {
 894     return;
 895   }
 896
 897   if (cached_network_qualities_.size() == kMaximumNetworkQualityCacheSize) {
 898     // Remove the oldest entry.
 899     CachedNetworkQualities::iterator oldest_entry_iterator =
 900         cached_network_qualities_.begin();
 901
 902     for (CachedNetworkQualities::iterator it =
 903              cached_network_qualities_.begin();
 904          it != cached_network_qualities_.end(); ++it) {
 905       if ((it->second).OlderThan(oldest_entry_iterator->second))
 906         oldest_entry_iterator = it;
 907     }
 908     cached_network_qualities_.erase(oldest_entry_iterator);
 909   }
 910   DCHECK_LT(cached_network_qualities_.size(),
 911             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 912
 913   cached_network_qualities_.insert(std::make_pair(
 914       current_network_id_, CachedNetworkQuality(network_quality)));
 915   DCHECK_LE(cached_network_qualities_.size(),
 916             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 917 }
 918
 919 scoped_ptr<SocketPerformanceWatcher>
 920 NetworkQualityEstimator::CreateTCPSocketPerformanceWatcher() const {
 921   DCHECK(thread_checker_.CalledOnValidThread());
 922   return scoped_ptr<SocketPerformanceWatcher>(
 923       new SocketPerformanceWatcherTCP());
 924 }
 925
 926 scoped_ptr<SocketPerformanceWatcher>
 927 NetworkQualityEstimator::CreateUDPSocketPerformanceWatcher() const {
 928   DCHECK(thread_checker_.CalledOnValidThread());
 929   return scoped_ptr<SocketPerformanceWatcher>(
 930       new SocketPerformanceWatcherUDP());
 931 }
 932
 933 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
 934     const NetworkQuality& network_quality)
 935     : last_update_time_(base::TimeTicks::Now()),
 936       network_quality_(network_quality) {
 937 }
 938
 939 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
 940     const CachedNetworkQuality& other)
 941     : last_update_time_(other.last_update_time_),
 942       network_quality_(other.network_quality_) {
 943 }
 944
 945 NetworkQualityEstimator::CachedNetworkQuality::~CachedNetworkQuality() {
 946 }
 947
 948 bool NetworkQualityEstimator::CachedNetworkQuality::OlderThan(
 949     const CachedNetworkQuality& cached_network_quality) const {
 950   return last_update_time_ < cached_network_quality.last_update_time_;
 951 }
 952
 953 NetworkQualityEstimator::NetworkQuality::NetworkQuality()
 954     : NetworkQuality(NetworkQualityEstimator::InvalidRTT(),
 955                      NetworkQualityEstimator::kInvalidThroughput) {}
 956
 957 NetworkQualityEstimator::NetworkQuality::NetworkQuality(
 958     const base::TimeDelta& rtt,
 959     int32_t downstream_throughput_kbps)
 960     : rtt_(rtt), downstream_throughput_kbps_(downstream_throughput_kbps) {
 961   DCHECK_GE(rtt_, base::TimeDelta());
 962   DCHECK_GE(downstream_throughput_kbps_, 0);
 963 }
 964
 965 NetworkQualityEstimator::NetworkQuality::NetworkQuality(
 966     const NetworkQuality& other)
 967     : NetworkQuality(other.rtt_, other.downstream_throughput_kbps_) {}
 968
 969 NetworkQualityEstimator::NetworkQuality::~NetworkQuality() {}
 970
 971 NetworkQualityEstimator::NetworkQuality&
 972     NetworkQualityEstimator::NetworkQuality::
 973     operator=(const NetworkQuality& other) {
 974   rtt_ = other.rtt_;
 975   downstream_throughput_kbps_ = other.downstream_throughput_kbps_;
 976   return *this;
 977 }
 978
 979 }  // namespace net