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 NetworkQualityEstimator::NetworkQualityEstimator(
 120     const std::map<std::string, std::string>& variation_params)
 121     : NetworkQualityEstimator(variation_params, false, false) {
 122 }
 123
 124 NetworkQualityEstimator::NetworkQualityEstimator(
 125     const std::map<std::string, std::string>& variation_params,
 126     bool allow_local_host_requests_for_tests,
 127     bool allow_smaller_responses_for_tests)
 128     : allow_localhost_requests_(allow_local_host_requests_for_tests),
 129       allow_small_responses_(allow_smaller_responses_for_tests),
 130       last_connection_change_(base::TimeTicks::Now()),
 131       current_network_id_(
 132           NetworkID(NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN,
 133                     std::string())),
 134       kbps_observations_(GetWeightMultiplierPerSecond(variation_params)),
 135       rtt_msec_observations_(GetWeightMultiplierPerSecond(variation_params)) {
 136   static_assert(kMinRequestDurationMicroseconds > 0,
 137                 "Minimum request duration must be > 0");
 138   static_assert(kDefaultHalfLifeSeconds > 0,
 139                 "Default half life duration must be > 0");
 140   static_assert(kMaximumNetworkQualityCacheSize > 0,
 141                 "Size of the network quality cache must be > 0");
 142   // This limit should not be increased unless the logic for removing the
 143   // oldest cache entry is rewritten to use a doubly-linked-list LRU queue.
 144   static_assert(kMaximumNetworkQualityCacheSize <= 10,
 145                 "Size of the network quality cache must <= 10");
 146
 147   ObtainOperatingParams(variation_params);
 148   NetworkChangeNotifier::AddConnectionTypeObserver(this);
 149   current_network_id_ = GetCurrentNetworkID();
 150   AddDefaultEstimates();
 151 }
 152
 153 void NetworkQualityEstimator::ObtainOperatingParams(
 154     const std::map<std::string, std::string>& variation_params) {
 155   DCHECK(thread_checker_.CalledOnValidThread());
 156
 157   for (size_t i = 0; i <= NetworkChangeNotifier::CONNECTION_LAST; ++i) {
 158     NetworkChangeNotifier::ConnectionType type =
 159         static_cast<NetworkChangeNotifier::ConnectionType>(i);
 160     int32_t variations_value = kMinimumRTTVariationParameterMsec - 1;
 161     // Name of the parameter that holds the RTT value for this connection type.
 162     std::string rtt_parameter_name =
 163         std::string(GetNameForConnectionType(type))
 164             .append(kDefaultRTTMsecObservationSuffix);
 165     auto it = variation_params.find(rtt_parameter_name);
 166     if (it != variation_params.end() &&
 167         base::StringToInt(it->second, &variations_value) &&
 168         variations_value >= kMinimumRTTVariationParameterMsec) {
 169       default_observations_[i] =
 170           NetworkQuality(base::TimeDelta::FromMilliseconds(variations_value),
 171                          default_observations_[i].downstream_throughput_kbps());
 172     }
 173
 174     variations_value = kMinimumThroughputVariationParameterKbps - 1;
 175     // Name of the parameter that holds the Kbps value for this connection
 176     // type.
 177     std::string kbps_parameter_name =
 178         std::string(GetNameForConnectionType(type))
 179             .append(kDefaultKbpsObservationSuffix);
 180     it = variation_params.find(kbps_parameter_name);
 181     if (it != variation_params.end() &&
 182         base::StringToInt(it->second, &variations_value) &&
 183         variations_value >= kMinimumThroughputVariationParameterKbps) {
 184       default_observations_[i] =
 185           NetworkQuality(default_observations_[i].rtt(), variations_value);
 186     }
 187   }
 188 }
 189
 190 void NetworkQualityEstimator::AddDefaultEstimates() {
 191   DCHECK(thread_checker_.CalledOnValidThread());
 192   if (default_observations_[current_network_id_.type].rtt() !=
 193       NetworkQuality::InvalidRTT()) {
 194     rtt_msec_observations_.AddObservation(Observation(
 195         default_observations_[current_network_id_.type].rtt().InMilliseconds(),
 196         base::TimeTicks::Now()));
 197   }
 198   if (default_observations_[current_network_id_.type]
 199           .downstream_throughput_kbps() != NetworkQuality::kInvalidThroughput) {
 200     kbps_observations_.AddObservation(
 201         Observation(default_observations_[current_network_id_.type]
 202                         .downstream_throughput_kbps(),
 203                     base::TimeTicks::Now()));
 204   }
 205 }
 206
 207 NetworkQualityEstimator::~NetworkQualityEstimator() {
 208   DCHECK(thread_checker_.CalledOnValidThread());
 209   NetworkChangeNotifier::RemoveConnectionTypeObserver(this);
 210 }
 211
 212 void NetworkQualityEstimator::NotifyDataReceived(
 213     const URLRequest& request,
 214     int64_t cumulative_prefilter_bytes_read,
 215     int64_t prefiltered_bytes_read) {
 216   DCHECK(thread_checker_.CalledOnValidThread());
 217   DCHECK_GT(cumulative_prefilter_bytes_read, 0);
 218   DCHECK_GT(prefiltered_bytes_read, 0);
 219
 220   if (!request.url().is_valid() ||
 221       (!allow_localhost_requests_ && IsLocalhost(request.url().host())) ||
 222       !request.url().SchemeIsHTTPOrHTTPS() ||
 223       // Verify that response headers are received, so it can be ensured that
 224       // response is not cached.
 225       request.response_info().response_time.is_null() || request.was_cached() ||
 226       request.creation_time() < last_connection_change_) {
 227     return;
 228   }
 229
 230   // Update |estimated_median_network_quality_| if this is a main frame
 231   // request.
 232   if (request.load_flags() & LOAD_MAIN_FRAME)
 233     GetEstimate(&estimated_median_network_quality_);
 234
 235   base::TimeTicks now = base::TimeTicks::Now();
 236   LoadTimingInfo load_timing_info;
 237   request.GetLoadTimingInfo(&load_timing_info);
 238
 239   // If the load timing info is unavailable, it probably means that the request
 240   // did not go over the network.
 241   if (load_timing_info.send_start.is_null() ||
 242       load_timing_info.receive_headers_end.is_null()) {
 243     return;
 244   }
 245
 246   // Time when the resource was requested.
 247   base::TimeTicks request_start_time = load_timing_info.send_start;
 248
 249   // Time when the headers were received.
 250   base::TimeTicks headers_received_time = load_timing_info.receive_headers_end;
 251
 252   // Only add RTT observation if this is the first read for this response.
 253   if (cumulative_prefilter_bytes_read == prefiltered_bytes_read) {
 254     // Duration between when the resource was requested and when response
 255     // headers were received.
 256     base::TimeDelta observed_rtt = headers_received_time - request_start_time;
 257     DCHECK_GE(observed_rtt, base::TimeDelta());
 258     if (observed_rtt < peak_network_quality_.rtt()) {
 259       peak_network_quality_ = NetworkQuality(
 260           observed_rtt, peak_network_quality_.downstream_throughput_kbps());
 261     }
 262
 263     rtt_msec_observations_.AddObservation(
 264         Observation(observed_rtt.InMilliseconds(), now));
 265
 266     // Compare the RTT observation with the estimated value and record it.
 267     if (estimated_median_network_quality_.rtt() !=
 268         NetworkQuality::InvalidRTT()) {
 269       RecordRTTUMA(estimated_median_network_quality_.rtt().InMilliseconds(),
 270                    observed_rtt.InMilliseconds());
 271     }
 272   }
 273
 274   // Time since the resource was requested.
 275   base::TimeDelta since_request_start = now - request_start_time;
 276   DCHECK_GE(since_request_start, base::TimeDelta());
 277
 278   // Ignore tiny transfers which will not produce accurate rates.
 279   // Ignore short duration transfers.
 280   // Skip the checks if |allow_small_responses_| is true.
 281   if (allow_small_responses_ ||
 282       (cumulative_prefilter_bytes_read >= kMinTransferSizeInBytes &&
 283        since_request_start >= base::TimeDelta::FromMicroseconds(
 284                                   kMinRequestDurationMicroseconds))) {
 285     double kbps_f = cumulative_prefilter_bytes_read * 8.0 / 1000.0 /
 286                     since_request_start.InSecondsF();
 287     DCHECK_GE(kbps_f, 0.0);
 288
 289     // Check overflow errors. This may happen if the kbps_f is more than
 290     // 2 * 10^9 (= 2000 Gbps).
 291     if (kbps_f >= std::numeric_limits<int32_t>::max())
 292       kbps_f = std::numeric_limits<int32_t>::max() - 1;
 293
 294     int32_t kbps = static_cast<int32_t>(kbps_f);
 295
 296     // If the |kbps| is less than 1, we set it to 1 to differentiate from case
 297     // when there is no connection.
 298     if (kbps_f > 0.0 && kbps == 0)
 299       kbps = 1;
 300
 301     if (kbps > 0) {
 302       if (kbps > peak_network_quality_.downstream_throughput_kbps()) {
 303         peak_network_quality_ =
 304             NetworkQuality(peak_network_quality_.rtt(), kbps);
 305       }
 306
 307       kbps_observations_.AddObservation(Observation(kbps, now));
 308     }
 309   }
 310 }
 311
 312 void NetworkQualityEstimator::RecordRTTUMA(int32_t estimated_value_msec,
 313                                            int32_t actual_value_msec) const {
 314   DCHECK(thread_checker_.CalledOnValidThread());
 315
 316   // Record the difference between the actual and the estimated value.
 317   if (estimated_value_msec >= actual_value_msec) {
 318     base::HistogramBase* difference_rtt =
 319         GetHistogram("DifferenceRTTEstimatedAndActual.",
 320                      current_network_id_.type, 10 * 1000);  // 10 seconds
 321     difference_rtt->Add(estimated_value_msec - actual_value_msec);
 322   } else {
 323     base::HistogramBase* difference_rtt =
 324         GetHistogram("DifferenceRTTActualAndEstimated.",
 325                      current_network_id_.type, 10 * 1000);  // 10 seconds
 326     difference_rtt->Add(actual_value_msec - estimated_value_msec);
 327   }
 328
 329   // Record all the RTT observations.
 330   base::HistogramBase* rtt_observations =
 331       GetHistogram("RTTObservations.", current_network_id_.type,
 332                    10 * 1000);  // 10 seconds upper bound
 333   rtt_observations->Add(actual_value_msec);
 334
 335   if (actual_value_msec == 0)
 336     return;
 337
 338   int32 ratio = (estimated_value_msec * 100) / actual_value_msec;
 339
 340   // Record the accuracy of estimation by recording the ratio of estimated
 341   // value to the actual value.
 342   base::HistogramBase* ratio_median_rtt = GetHistogram(
 343       "RatioEstimatedToActualRTT.", current_network_id_.type, 1000);
 344   ratio_median_rtt->Add(ratio);
 345 }
 346
 347 void NetworkQualityEstimator::OnConnectionTypeChanged(
 348     NetworkChangeNotifier::ConnectionType type) {
 349   DCHECK(thread_checker_.CalledOnValidThread());
 350   if (peak_network_quality_.rtt() != NetworkQuality::InvalidRTT()) {
 351     switch (current_network_id_.type) {
 352       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 353         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
 354                             peak_network_quality_.rtt());
 355         break;
 356       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 357         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Ethernet",
 358                             peak_network_quality_.rtt());
 359         break;
 360       case NetworkChangeNotifier::CONNECTION_WIFI:
 361         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi", peak_network_quality_.rtt());
 362         break;
 363       case NetworkChangeNotifier::CONNECTION_2G:
 364         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.2G", peak_network_quality_.rtt());
 365         break;
 366       case NetworkChangeNotifier::CONNECTION_3G:
 367         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.3G", peak_network_quality_.rtt());
 368         break;
 369       case NetworkChangeNotifier::CONNECTION_4G:
 370         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.4G", peak_network_quality_.rtt());
 371         break;
 372       case NetworkChangeNotifier::CONNECTION_NONE:
 373         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None", peak_network_quality_.rtt());
 374         break;
 375       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 376         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Bluetooth",
 377                             peak_network_quality_.rtt());
 378         break;
 379       default:
 380         NOTREACHED() << "Unexpected connection type = "
 381                      << current_network_id_.type;
 382         break;
 383     }
 384   }
 385
 386   if (peak_network_quality_.downstream_throughput_kbps() !=
 387       NetworkQuality::kInvalidThroughput) {
 388     switch (current_network_id_.type) {
 389       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 390         UMA_HISTOGRAM_COUNTS(
 391             "NQE.PeakKbps.Unknown",
 392             peak_network_quality_.downstream_throughput_kbps());
 393         break;
 394       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 395         UMA_HISTOGRAM_COUNTS(
 396             "NQE.PeakKbps.Ethernet",
 397             peak_network_quality_.downstream_throughput_kbps());
 398         break;
 399       case NetworkChangeNotifier::CONNECTION_WIFI:
 400         UMA_HISTOGRAM_COUNTS(
 401             "NQE.PeakKbps.Wifi",
 402             peak_network_quality_.downstream_throughput_kbps());
 403         break;
 404       case NetworkChangeNotifier::CONNECTION_2G:
 405         UMA_HISTOGRAM_COUNTS(
 406             "NQE.PeakKbps.2G",
 407             peak_network_quality_.downstream_throughput_kbps());
 408         break;
 409       case NetworkChangeNotifier::CONNECTION_3G:
 410         UMA_HISTOGRAM_COUNTS(
 411             "NQE.PeakKbps.3G",
 412             peak_network_quality_.downstream_throughput_kbps());
 413         break;
 414       case NetworkChangeNotifier::CONNECTION_4G:
 415         UMA_HISTOGRAM_COUNTS(
 416             "NQE.PeakKbps.4G",
 417             peak_network_quality_.downstream_throughput_kbps());
 418         break;
 419       case NetworkChangeNotifier::CONNECTION_NONE:
 420         UMA_HISTOGRAM_COUNTS(
 421             "NQE.PeakKbps.None",
 422             peak_network_quality_.downstream_throughput_kbps());
 423         break;
 424       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 425         UMA_HISTOGRAM_COUNTS(
 426             "NQE.PeakKbps.Bluetooth",
 427             peak_network_quality_.downstream_throughput_kbps());
 428         break;
 429       default:
 430         NOTREACHED() << "Unexpected connection type = "
 431                      << current_network_id_.type;
 432         break;
 433     }
 434   }
 435
 436   NetworkQuality network_quality;
 437   if (GetEstimate(&network_quality)) {
 438     // Add the 50th percentile value.
 439     base::HistogramBase* rtt_percentile =
 440         GetHistogram("RTT.Percentile50.", current_network_id_.type,
 441                      10 * 1000);  // 10 seconds
 442     rtt_percentile->Add(network_quality.rtt().InMilliseconds());
 443
 444     // Add the remaining percentile values.
 445     static const int kPercentiles[] = {0, 10, 90, 100};
 446     for (size_t i = 0; i < arraysize(kPercentiles); ++i) {
 447       network_quality = GetEstimate(kPercentiles[i]);
 448
 449       rtt_percentile = GetHistogram(
 450           "RTT.Percentile" + base::IntToString(kPercentiles[i]) + ".",
 451           current_network_id_.type, 10 * 1000);  // 10 seconds
 452       rtt_percentile->Add(network_quality.rtt().InMilliseconds());
 453     }
 454   }
 455
 456   // Write the estimates of the previous network to the cache.
 457   CacheNetworkQualityEstimate();
 458
 459   // Clear the local state.
 460   last_connection_change_ = base::TimeTicks::Now();
 461   peak_network_quality_ = NetworkQuality();
 462   kbps_observations_.Clear();
 463   rtt_msec_observations_.Clear();
 464   current_network_id_ = GetCurrentNetworkID();
 465
 466   // Read any cached estimates for the new network. If cached estimates are
 467   // unavailable, add the default estimates.
 468   if (!ReadCachedNetworkQualityEstimate())
 469     AddDefaultEstimates();
 470   estimated_median_network_quality_ = NetworkQuality();
 471 }
 472
 473 NetworkQuality NetworkQualityEstimator::GetPeakEstimate() const {
 474   DCHECK(thread_checker_.CalledOnValidThread());
 475
 476   return peak_network_quality_;
 477 }
 478
 479 bool NetworkQualityEstimator::GetEstimate(NetworkQuality* median) const {
 480   if (kbps_observations_.Size() == 0 || rtt_msec_observations_.Size() == 0) {
 481     *median = NetworkQuality();
 482     return false;
 483   }
 484   *median = GetEstimate(50);
 485   return true;
 486 }
 487
 488 NetworkQualityEstimator::Observation::Observation(int32_t value,
 489                                                   base::TimeTicks timestamp)
 490     : value(value), timestamp(timestamp) {
 491   DCHECK_GE(value, 0);
 492   DCHECK(!timestamp.is_null());
 493 }
 494
 495 NetworkQualityEstimator::Observation::~Observation() {
 496 }
 497
 498 NetworkQualityEstimator::ObservationBuffer::ObservationBuffer(
 499     double weight_multiplier_per_second)
 500     : weight_multiplier_per_second_(weight_multiplier_per_second) {
 501   static_assert(kMaximumObservationsBufferSize > 0U,
 502                 "Minimum size of observation buffer must be > 0");
 503   DCHECK_GE(weight_multiplier_per_second_, 0.0);
 504   DCHECK_LE(weight_multiplier_per_second_, 1.0);
 505 }
 506
 507 NetworkQualityEstimator::ObservationBuffer::~ObservationBuffer() {
 508 }
 509
 510 void NetworkQualityEstimator::ObservationBuffer::AddObservation(
 511     const Observation& observation) {
 512   DCHECK_LE(observations_.size(),
 513             static_cast<size_t>(kMaximumObservationsBufferSize));
 514   // Evict the oldest element if the buffer is already full.
 515   if (observations_.size() == kMaximumObservationsBufferSize)
 516     observations_.pop_front();
 517
 518   observations_.push_back(observation);
 519   DCHECK_LE(observations_.size(),
 520             static_cast<size_t>(kMaximumObservationsBufferSize));
 521 }
 522
 523 size_t NetworkQualityEstimator::ObservationBuffer::Size() const {
 524   return observations_.size();
 525 }
 526
 527 void NetworkQualityEstimator::ObservationBuffer::Clear() {
 528   observations_.clear();
 529   DCHECK(observations_.empty());
 530 }
 531
 532 NetworkQuality NetworkQualityEstimator::GetEstimate(int percentile) const {
 533   DCHECK(thread_checker_.CalledOnValidThread());
 534   DCHECK_GE(percentile, 0);
 535   DCHECK_LE(percentile, 100);
 536   DCHECK_GT(kbps_observations_.Size(), 0U);
 537   DCHECK_GT(rtt_msec_observations_.Size(), 0U);
 538
 539   // RTT observations are sorted by duration from shortest to longest, thus
 540   // a higher percentile RTT will have a longer RTT than a lower percentile.
 541   // Throughput observations are sorted by kbps from slowest to fastest,
 542   // thus a higher percentile throughput will be faster than a lower one.
 543   return NetworkQuality(base::TimeDelta::FromMilliseconds(
 544                             rtt_msec_observations_.GetPercentile(percentile)),
 545                         kbps_observations_.GetPercentile(100 - percentile));
 546 }
 547
 548 void NetworkQualityEstimator::ObservationBuffer::ComputeWeightedObservations(
 549     std::vector<WeightedObservation>& weighted_observations,
 550     double* total_weight) const {
 551   weighted_observations.clear();
 552   double total_weight_observations = 0.0;
 553   base::TimeTicks now = base::TimeTicks::Now();
 554
 555   for (const auto& observation : observations_) {
 556     base::TimeDelta time_since_sample_taken = now - observation.timestamp;
 557     double weight =
 558         pow(weight_multiplier_per_second_, time_since_sample_taken.InSeconds());
 559     weight = std::max(DBL_MIN, std::min(1.0, weight));
 560
 561     weighted_observations.push_back(
 562         WeightedObservation(observation.value, weight));
 563     total_weight_observations += weight;
 564   }
 565
 566   // Sort the samples by value in ascending order.
 567   std::sort(weighted_observations.begin(), weighted_observations.end());
 568   *total_weight = total_weight_observations;
 569 }
 570
 571 int32_t NetworkQualityEstimator::ObservationBuffer::GetPercentile(
 572     int percentile) const {
 573   DCHECK(!observations_.empty());
 574
 575   // Stores WeightedObservation in increasing order of value.
 576   std::vector<WeightedObservation> weighted_observations;
 577
 578   // Total weight of all observations in |weighted_observations|.
 579   double total_weight = 0.0;
 580
 581   ComputeWeightedObservations(weighted_observations, &total_weight);
 582   DCHECK(!weighted_observations.empty());
 583   DCHECK_GT(total_weight, 0.0);
 584   DCHECK_EQ(observations_.size(), weighted_observations.size());
 585
 586   double desired_weight = percentile / 100.0 * total_weight;
 587
 588   double cumulative_weight_seen_so_far = 0.0;
 589   for (const auto& weighted_observation : weighted_observations) {
 590     cumulative_weight_seen_so_far += weighted_observation.weight;
 591
 592     // TODO(tbansal): Consider interpolating between observations.
 593     if (cumulative_weight_seen_so_far >= desired_weight)
 594       return weighted_observation.value;
 595   }
 596
 597   // Computation may reach here due to floating point errors. This may happen
 598   // if |percentile| was 100 (or close to 100), and |desired_weight| was
 599   // slightly larger than |total_weight| (due to floating point errors).
 600   // In this case, we return the highest |value| among all observations.
 601   // This is same as value of the last observation in the sorted vector.
 602   return weighted_observations.at(weighted_observations.size() - 1).value;
 603 }
 604
 605 NetworkQualityEstimator::NetworkID
 606 NetworkQualityEstimator::GetCurrentNetworkID() const {
 607   DCHECK(thread_checker_.CalledOnValidThread());
 608
 609   // TODO(tbansal): crbug.com/498068 Add NetworkQualityEstimatorAndroid class
 610   // that overrides this method on the Android platform.
 611
 612   // It is possible that the connection type changed between when
 613   // GetConnectionType() was called and when the API to determine the
 614   // network name was called. Check if that happened and retry until the
 615   // connection type stabilizes. This is an imperfect solution but should
 616   // capture majority of cases, and should not significantly affect estimates
 617   // (that are approximate to begin with).
 618   while (true) {
 619     NetworkQualityEstimator::NetworkID network_id(
 620         NetworkChangeNotifier::GetConnectionType(), std::string());
 621
 622     switch (network_id.type) {
 623       case NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN:
 624       case NetworkChangeNotifier::ConnectionType::CONNECTION_NONE:
 625       case NetworkChangeNotifier::ConnectionType::CONNECTION_BLUETOOTH:
 626       case NetworkChangeNotifier::ConnectionType::CONNECTION_ETHERNET:
 627         break;
 628       case NetworkChangeNotifier::ConnectionType::CONNECTION_WIFI:
 629 #if defined(OS_ANDROID) || defined(OS_LINUX) || defined(OS_CHROMEOS) || \
 630     defined(OS_WIN)
 631         network_id.id = GetWifiSSID();
 632 #endif
 633         break;
 634       case NetworkChangeNotifier::ConnectionType::CONNECTION_2G:
 635       case NetworkChangeNotifier::ConnectionType::CONNECTION_3G:
 636       case NetworkChangeNotifier::ConnectionType::CONNECTION_4G:
 637 #if defined(OS_ANDROID)
 638         network_id.id = android::GetTelephonyNetworkOperator();
 639 #endif
 640         break;
 641       default:
 642         NOTREACHED() << "Unexpected connection type = " << network_id.type;
 643         break;
 644     }
 645
 646     if (network_id.type == NetworkChangeNotifier::GetConnectionType())
 647       return network_id;
 648   }
 649   NOTREACHED();
 650 }
 651
 652 bool NetworkQualityEstimator::ReadCachedNetworkQualityEstimate() {
 653   DCHECK(thread_checker_.CalledOnValidThread());
 654
 655   // If the network name is unavailable, caching should not be performed.
 656   if (current_network_id_.id.empty())
 657     return false;
 658
 659   CachedNetworkQualities::const_iterator it =
 660       cached_network_qualities_.find(current_network_id_);
 661
 662   if (it == cached_network_qualities_.end())
 663     return false;
 664
 665   NetworkQuality network_quality(it->second.network_quality());
 666
 667   DCHECK_NE(NetworkQuality::InvalidRTT(), network_quality.rtt());
 668   DCHECK_NE(NetworkQuality::kInvalidThroughput,
 669             network_quality.downstream_throughput_kbps());
 670
 671   kbps_observations_.AddObservation(Observation(
 672       network_quality.downstream_throughput_kbps(), base::TimeTicks::Now()));
 673   rtt_msec_observations_.AddObservation(Observation(
 674       network_quality.rtt().InMilliseconds(), base::TimeTicks::Now()));
 675   return true;
 676 }
 677
 678 void NetworkQualityEstimator::CacheNetworkQualityEstimate() {
 679   DCHECK(thread_checker_.CalledOnValidThread());
 680   DCHECK_LE(cached_network_qualities_.size(),
 681             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 682
 683   // If the network name is unavailable, caching should not be performed.
 684   if (current_network_id_.id.empty())
 685     return;
 686
 687   NetworkQuality network_quality;
 688   if (!GetEstimate(&network_quality))
 689     return;
 690
 691   DCHECK_NE(NetworkQuality::InvalidRTT(), network_quality.rtt());
 692   DCHECK_NE(NetworkQuality::kInvalidThroughput,
 693             network_quality.downstream_throughput_kbps());
 694
 695   if (cached_network_qualities_.size() == kMaximumNetworkQualityCacheSize) {
 696     // Remove the oldest entry.
 697     CachedNetworkQualities::iterator oldest_entry_iterator =
 698         cached_network_qualities_.begin();
 699
 700     for (CachedNetworkQualities::iterator it =
 701              cached_network_qualities_.begin();
 702          it != cached_network_qualities_.end(); ++it) {
 703       if ((it->second).OlderThan(oldest_entry_iterator->second))
 704         oldest_entry_iterator = it;
 705     }
 706     cached_network_qualities_.erase(oldest_entry_iterator);
 707   }
 708   DCHECK_LT(cached_network_qualities_.size(),
 709             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 710
 711   cached_network_qualities_.insert(std::make_pair(
 712       current_network_id_, CachedNetworkQuality(network_quality)));
 713   DCHECK_LE(cached_network_qualities_.size(),
 714             static_cast<size_t>(kMaximumNetworkQualityCacheSize));
 715 }
 716
 717 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
 718     const NetworkQuality& network_quality)
 719     : last_update_time_(base::TimeTicks::Now()),
 720       network_quality_(network_quality) {
 721 }
 722
 723 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
 724     const CachedNetworkQuality& other)
 725     : last_update_time_(other.last_update_time_),
 726       network_quality_(other.network_quality_) {
 727 }
 728
 729 NetworkQualityEstimator::CachedNetworkQuality::~CachedNetworkQuality() {
 730 }
 731
 732 bool NetworkQualityEstimator::CachedNetworkQuality::OlderThan(
 733     const CachedNetworkQuality& cached_network_quality) const {
 734   return last_update_time_ < cached_network_quality.last_update_time_;
 735 }
 736
 737 }  // namespace net