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