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