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 <string>
  12 #include <vector>
  13
  14 #include "base/logging.h"
  15 #include "base/metrics/histogram.h"
  16 #include "base/strings/string_number_conversions.h"
  17 #include "net/base/load_timing_info.h"
  18 #include "net/base/net_util.h"
  19 #include "net/url_request/url_request.h"
  20 #include "url/gurl.h"
  21
  22 namespace {
  23
  24 // Maximum number of observations that can be held in the ObservationBuffer.
  25 const size_t kMaximumObservationsBufferSize = 500;
  26
  27 // Default value of the half life (in seconds) for computing time weighted
  28 // percentiles. Every half life, the weight of all observations reduces by
  29 // half. Lowering the half life would reduce the weight of older values faster.
  30 const int kDefaultHalfLifeSeconds = 60;
  31
  32 // Name of the variation parameter that holds the value of the half life (in
  33 // seconds) of the observations.
  34 const char kHalfLifeSecondsParamName[] = "HalfLifeSeconds";
  35
  36 // Name of the different connection types. Used for matching the connection
  37 // type to the variation parameters. Names must be in the same order as
  38 // NetworkChangeNotifier::ConnectionType enum.
  39 const char* const kConnectionTypeNames[] =
  40     {"Unknown", "Ethernet", "WiFi", "2G", "3G", "4G", "None", "Bluetooth"};
  41
  42 // Suffix of the name of the variation parameter that contains the default RTT
  43 // observation (in milliseconds). Complete name of the variation parameter
  44 // would be |ConnectionType|.|kDefaultRTTMsecObservationSuffix| where
  45 // |ConnectionType| is from |kConnectionTypeNames|. For example, variation
  46 // parameter for Wi-Fi would be "WiFi.DefaultMedianRTTMsec".
  47 const char kDefaultRTTMsecObservationSuffix[] = ".DefaultMedianRTTMsec";
  48
  49 // Suffix of the name of the variation parameter that contains the default
  50 // downstream throughput observation (in Kbps).  Complete name of the variation
  51 // parameter would be |ConnectionType|.|kDefaultKbpsObservationSuffix| where
  52 // |ConnectionType| is from |kConnectionTypeNames|. For example, variation
  53 // parameter for Wi-Fi would be "WiFi.DefaultMedianKbps".
  54 const char kDefaultKbpsObservationSuffix[] = ".DefaultMedianKbps";
  55
  56 // Computes and returns the weight multiplier per second.
  57 // |variation_params| is the map containing all field trial parameters
  58 // related to NetworkQualityEstimator field trial.
  59 double GetWeightMultiplierPerSecond(
  60     const std::map<std::string, std::string>& variation_params) {
  61   int half_life_seconds = kDefaultHalfLifeSeconds;
  62   int32_t variations_value = 0;
  63   auto it = variation_params.find(kHalfLifeSecondsParamName);
  64   if (it != variation_params.end() &&
  65       base::StringToInt(it->second, &variations_value) &&
  66       variations_value >= 1) {
  67     half_life_seconds = variations_value;
  68   }
  69   DCHECK_GT(half_life_seconds, 0);
  70   return exp(log(0.5) / half_life_seconds);
  71 }
  72
  73 }  // namespace
  74
  75 namespace net {
  76
  77 NetworkQualityEstimator::NetworkQualityEstimator(
  78     const std::map<std::string, std::string>& variation_params)
  79     : NetworkQualityEstimator(variation_params, false, false) {
  80 }
  81
  82 NetworkQualityEstimator::NetworkQualityEstimator(
  83     const std::map<std::string, std::string>& variation_params,
  84     bool allow_local_host_requests_for_tests,
  85     bool allow_smaller_responses_for_tests)
  86     : allow_localhost_requests_(allow_local_host_requests_for_tests),
  87       allow_small_responses_(allow_smaller_responses_for_tests),
  88       last_connection_change_(base::TimeTicks::Now()),
  89       current_connection_type_(NetworkChangeNotifier::GetConnectionType()),
  90       fastest_rtt_since_last_connection_change_(NetworkQuality::InvalidRTT()),
  91       peak_kbps_since_last_connection_change_(
  92           NetworkQuality::kInvalidThroughput),
  93       kbps_observations_(GetWeightMultiplierPerSecond(variation_params)),
  94       rtt_msec_observations_(GetWeightMultiplierPerSecond(variation_params)) {
  95   static_assert(kMinRequestDurationMicroseconds > 0,
  96                 "Minimum request duration must be > 0");
  97   static_assert(kDefaultHalfLifeSeconds > 0,
  98                 "Default half life duration must be > 0");
  99   static_assert(arraysize(kConnectionTypeNames) ==
 100                     NetworkChangeNotifier::CONNECTION_LAST + 1,
 101                 "ConnectionType name count should match");
 102
 103   ObtainOperatingParams(variation_params);
 104   AddDefaultEstimates();
 105   NetworkChangeNotifier::AddConnectionTypeObserver(this);
 106 }
 107
 108 void NetworkQualityEstimator::ObtainOperatingParams(
 109     const std::map<std::string, std::string>& variation_params) {
 110   DCHECK(thread_checker_.CalledOnValidThread());
 111
 112   for (size_t i = 0; i < arraysize(kConnectionTypeNames); ++i) {
 113     int32_t variations_value = kMinimumRTTVariationParameterMsec - 1;
 114     // Name of the parameter that holds the RTT value for this connection type.
 115     std::string rtt_parameter_name =
 116         std::string(kConnectionTypeNames[i])
 117             .append(kDefaultRTTMsecObservationSuffix);
 118     auto it = variation_params.find(rtt_parameter_name);
 119     if (it != variation_params.end() &&
 120         base::StringToInt(it->second, &variations_value) &&
 121         variations_value >= kMinimumRTTVariationParameterMsec) {
 122       default_observations_[i] =
 123           NetworkQuality(base::TimeDelta::FromMilliseconds(variations_value),
 124                          default_observations_[i].downstream_throughput_kbps());
 125     }
 126
 127     variations_value = kMinimumThroughputVariationParameterKbps - 1;
 128     // Name of the parameter that holds the Kbps value for this connection
 129     // type.
 130     std::string kbps_parameter_name =
 131         std::string(kConnectionTypeNames[i])
 132             .append(kDefaultKbpsObservationSuffix);
 133     it = variation_params.find(kbps_parameter_name);
 134     if (it != variation_params.end() &&
 135         base::StringToInt(it->second, &variations_value) &&
 136         variations_value >= kMinimumThroughputVariationParameterKbps) {
 137       default_observations_[i] =
 138           NetworkQuality(default_observations_[i].rtt(), variations_value);
 139     }
 140   }
 141 }
 142
 143 void NetworkQualityEstimator::AddDefaultEstimates() {
 144   DCHECK(thread_checker_.CalledOnValidThread());
 145
 146   if (default_observations_[current_connection_type_].rtt() !=
 147       NetworkQuality::InvalidRTT()) {
 148     rtt_msec_observations_.AddObservation(Observation(
 149         default_observations_[current_connection_type_].rtt().InMilliseconds(),
 150         base::TimeTicks::Now()));
 151   }
 152
 153   if (default_observations_[current_connection_type_]
 154           .downstream_throughput_kbps() != NetworkQuality::kInvalidThroughput) {
 155     kbps_observations_.AddObservation(
 156         Observation(default_observations_[current_connection_type_]
 157                         .downstream_throughput_kbps(),
 158                     base::TimeTicks::Now()));
 159   }
 160 }
 161
 162 NetworkQualityEstimator::~NetworkQualityEstimator() {
 163   DCHECK(thread_checker_.CalledOnValidThread());
 164   NetworkChangeNotifier::RemoveConnectionTypeObserver(this);
 165 }
 166
 167 void NetworkQualityEstimator::NotifyDataReceived(
 168     const URLRequest& request,
 169     int64_t cumulative_prefilter_bytes_read,
 170     int64_t prefiltered_bytes_read) {
 171   DCHECK(thread_checker_.CalledOnValidThread());
 172   DCHECK_GT(cumulative_prefilter_bytes_read, 0);
 173   DCHECK_GT(prefiltered_bytes_read, 0);
 174
 175   if (!request.url().is_valid() ||
 176       (!allow_localhost_requests_ && IsLocalhost(request.url().host())) ||
 177       !request.url().SchemeIsHTTPOrHTTPS() ||
 178       // Verify that response headers are received, so it can be ensured that
 179       // response is not cached.
 180       request.response_info().response_time.is_null() || request.was_cached() ||
 181       request.creation_time() < last_connection_change_) {
 182     return;
 183   }
 184
 185   base::TimeTicks now = base::TimeTicks::Now();
 186   LoadTimingInfo load_timing_info;
 187   request.GetLoadTimingInfo(&load_timing_info);
 188
 189   // If the load timing info is unavailable, it probably means that the request
 190   // did not go over the network.
 191   if (load_timing_info.send_start.is_null() ||
 192       load_timing_info.receive_headers_end.is_null()) {
 193     return;
 194   }
 195
 196   // Time when the resource was requested.
 197   base::TimeTicks request_start_time = load_timing_info.send_start;
 198
 199   // Time when the headers were received.
 200   base::TimeTicks headers_received_time = load_timing_info.receive_headers_end;
 201
 202   // Only add RTT observation if this is the first read for this response.
 203   if (cumulative_prefilter_bytes_read == prefiltered_bytes_read) {
 204     // Duration between when the resource was requested and when response
 205     // headers were received.
 206     base::TimeDelta observed_rtt = headers_received_time - request_start_time;
 207     DCHECK_GE(observed_rtt, base::TimeDelta());
 208     if (observed_rtt < fastest_rtt_since_last_connection_change_)
 209       fastest_rtt_since_last_connection_change_ = observed_rtt;
 210
 211     rtt_msec_observations_.AddObservation(
 212         Observation(observed_rtt.InMilliseconds(), now));
 213   }
 214
 215   // Time since the resource was requested.
 216   base::TimeDelta since_request_start = now - request_start_time;
 217   DCHECK_GE(since_request_start, base::TimeDelta());
 218
 219   // Ignore tiny transfers which will not produce accurate rates.
 220   // Ignore short duration transfers.
 221   // Skip the checks if |allow_small_responses_| is true.
 222   if (allow_small_responses_ ||
 223       (cumulative_prefilter_bytes_read >= kMinTransferSizeInBytes &&
 224        since_request_start >= base::TimeDelta::FromMicroseconds(
 225                                   kMinRequestDurationMicroseconds))) {
 226     double kbps_f = cumulative_prefilter_bytes_read * 8.0 / 1000.0 /
 227                     since_request_start.InSecondsF();
 228     DCHECK_GE(kbps_f, 0.0);
 229
 230     // Check overflow errors. This may happen if the kbps_f is more than
 231     // 2 * 10^9 (= 2000 Gbps).
 232     if (kbps_f >= std::numeric_limits<int32_t>::max())
 233       kbps_f = std::numeric_limits<int32_t>::max() - 1;
 234
 235     int32_t kbps = static_cast<int32_t>(kbps_f);
 236
 237     // If the |kbps| is less than 1, we set it to 1 to differentiate from case
 238     // when there is no connection.
 239     if (kbps_f > 0.0 && kbps == 0)
 240       kbps = 1;
 241
 242     if (kbps > 0) {
 243       if (kbps > peak_kbps_since_last_connection_change_)
 244         peak_kbps_since_last_connection_change_ = kbps;
 245
 246       kbps_observations_.AddObservation(Observation(kbps, now));
 247     }
 248   }
 249 }
 250
 251 void NetworkQualityEstimator::OnConnectionTypeChanged(
 252     NetworkChangeNotifier::ConnectionType type) {
 253   DCHECK(thread_checker_.CalledOnValidThread());
 254   if (fastest_rtt_since_last_connection_change_ !=
 255       NetworkQuality::InvalidRTT()) {
 256     switch (current_connection_type_) {
 257       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 258         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
 259                             fastest_rtt_since_last_connection_change_);
 260         break;
 261       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 262         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Ethernet",
 263                             fastest_rtt_since_last_connection_change_);
 264         break;
 265       case NetworkChangeNotifier::CONNECTION_WIFI:
 266         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Wifi",
 267                             fastest_rtt_since_last_connection_change_);
 268         break;
 269       case NetworkChangeNotifier::CONNECTION_2G:
 270         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.2G",
 271                             fastest_rtt_since_last_connection_change_);
 272         break;
 273       case NetworkChangeNotifier::CONNECTION_3G:
 274         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.3G",
 275                             fastest_rtt_since_last_connection_change_);
 276         break;
 277       case NetworkChangeNotifier::CONNECTION_4G:
 278         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.4G",
 279                             fastest_rtt_since_last_connection_change_);
 280         break;
 281       case NetworkChangeNotifier::CONNECTION_NONE:
 282         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.None",
 283                             fastest_rtt_since_last_connection_change_);
 284         break;
 285       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 286         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Bluetooth",
 287                             fastest_rtt_since_last_connection_change_);
 288         break;
 289       default:
 290         NOTREACHED();
 291         break;
 292     }
 293   }
 294
 295   if (peak_kbps_since_last_connection_change_ !=
 296       NetworkQuality::kInvalidThroughput) {
 297     switch (current_connection_type_) {
 298       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
 299         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Unknown",
 300                              peak_kbps_since_last_connection_change_);
 301         break;
 302       case NetworkChangeNotifier::CONNECTION_ETHERNET:
 303         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Ethernet",
 304                              peak_kbps_since_last_connection_change_);
 305         break;
 306       case NetworkChangeNotifier::CONNECTION_WIFI:
 307         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Wifi",
 308                              peak_kbps_since_last_connection_change_);
 309         break;
 310       case NetworkChangeNotifier::CONNECTION_2G:
 311         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.2G",
 312                              peak_kbps_since_last_connection_change_);
 313         break;
 314       case NetworkChangeNotifier::CONNECTION_3G:
 315         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.3G",
 316                              peak_kbps_since_last_connection_change_);
 317         break;
 318       case NetworkChangeNotifier::CONNECTION_4G:
 319         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.4G",
 320                              peak_kbps_since_last_connection_change_);
 321         break;
 322       case NetworkChangeNotifier::CONNECTION_NONE:
 323         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.None",
 324                              peak_kbps_since_last_connection_change_);
 325         break;
 326       case NetworkChangeNotifier::CONNECTION_BLUETOOTH:
 327         UMA_HISTOGRAM_COUNTS("NQE.PeakKbps.Bluetooth",
 328                              peak_kbps_since_last_connection_change_);
 329         break;
 330       default:
 331         NOTREACHED();
 332         break;
 333     }
 334   }
 335
 336   last_connection_change_ = base::TimeTicks::Now();
 337   peak_kbps_since_last_connection_change_ = NetworkQuality::kInvalidThroughput;
 338   fastest_rtt_since_last_connection_change_ = NetworkQuality::InvalidRTT();
 339   kbps_observations_.Clear();
 340   rtt_msec_observations_.Clear();
 341   current_connection_type_ = type;
 342
 343   AddDefaultEstimates();
 344 }
 345
 346 NetworkQuality NetworkQualityEstimator::GetPeakEstimate() const {
 347   DCHECK(thread_checker_.CalledOnValidThread());
 348
 349   return NetworkQuality(fastest_rtt_since_last_connection_change_,
 350                         peak_kbps_since_last_connection_change_);
 351 }
 352
 353 bool NetworkQualityEstimator::GetEstimate(NetworkQuality* median) const {
 354   if (kbps_observations_.Size() == 0 || rtt_msec_observations_.Size() == 0) {
 355     *median = NetworkQuality();
 356     return false;
 357   }
 358   *median = GetEstimate(50);
 359   return true;
 360 }
 361
 362 size_t NetworkQualityEstimator::GetMaximumObservationBufferSizeForTests()
 363     const {
 364   return kMaximumObservationsBufferSize;
 365 }
 366
 367 bool NetworkQualityEstimator::VerifyBufferSizeForTests(
 368     size_t expected_size) const {
 369   return kbps_observations_.Size() == expected_size &&
 370          rtt_msec_observations_.Size() == expected_size;
 371 }
 372
 373 NetworkQualityEstimator::Observation::Observation(int32_t value,
 374                                                   base::TimeTicks timestamp)
 375     : value(value), timestamp(timestamp) {
 376   DCHECK_GE(value, 0);
 377   DCHECK(!timestamp.is_null());
 378 }
 379
 380 NetworkQualityEstimator::Observation::~Observation() {
 381 }
 382
 383 NetworkQualityEstimator::ObservationBuffer::ObservationBuffer(
 384     double weight_multiplier_per_second)
 385     : weight_multiplier_per_second_(weight_multiplier_per_second) {
 386   static_assert(kMaximumObservationsBufferSize > 0U,
 387                 "Minimum size of observation buffer must be > 0");
 388   DCHECK_GE(weight_multiplier_per_second_, 0.0);
 389   DCHECK_LE(weight_multiplier_per_second_, 1.0);
 390 }
 391
 392 NetworkQualityEstimator::ObservationBuffer::~ObservationBuffer() {
 393 }
 394
 395 void NetworkQualityEstimator::ObservationBuffer::AddObservation(
 396     const Observation& observation) {
 397   DCHECK_LE(observations_.size(), kMaximumObservationsBufferSize);
 398   // Evict the oldest element if the buffer is already full.
 399   if (observations_.size() == kMaximumObservationsBufferSize)
 400     observations_.pop_front();
 401
 402   observations_.push_back(observation);
 403   DCHECK_LE(observations_.size(), kMaximumObservationsBufferSize);
 404 }
 405
 406 size_t NetworkQualityEstimator::ObservationBuffer::Size() const {
 407   return observations_.size();
 408 }
 409
 410 void NetworkQualityEstimator::ObservationBuffer::Clear() {
 411   observations_.clear();
 412   DCHECK(observations_.empty());
 413 }
 414
 415 NetworkQuality NetworkQualityEstimator::GetEstimate(int percentile) const {
 416   DCHECK(thread_checker_.CalledOnValidThread());
 417   DCHECK_GE(percentile, 0);
 418   DCHECK_LE(percentile, 100);
 419   DCHECK_GT(kbps_observations_.Size(), 0U);
 420   DCHECK_GT(rtt_msec_observations_.Size(), 0U);
 421
 422   // RTT observations are sorted by duration from shortest to longest, thus
 423   // a higher percentile RTT will have a longer RTT than a lower percentile.
 424   // Throughput observations are sorted by kbps from slowest to fastest,
 425   // thus a higher percentile throughput will be faster than a lower one.
 426   return NetworkQuality(base::TimeDelta::FromMilliseconds(
 427                             rtt_msec_observations_.GetPercentile(percentile)),
 428                         kbps_observations_.GetPercentile(100 - percentile));
 429 }
 430
 431 void NetworkQualityEstimator::ObservationBuffer::ComputeWeightedObservations(
 432     std::vector<WeightedObservation>& weighted_observations,
 433     double* total_weight) const {
 434   weighted_observations.clear();
 435   double total_weight_observations = 0.0;
 436   base::TimeTicks now = base::TimeTicks::Now();
 437
 438   for (const auto& observation : observations_) {
 439     base::TimeDelta time_since_sample_taken = now - observation.timestamp;
 440     double weight =
 441         pow(weight_multiplier_per_second_, time_since_sample_taken.InSeconds());
 442     weight = std::max(DBL_MIN, std::min(1.0, weight));
 443
 444     weighted_observations.push_back(
 445         WeightedObservation(observation.value, weight));
 446     total_weight_observations += weight;
 447   }
 448
 449   // Sort the samples by value in ascending order.
 450   std::sort(weighted_observations.begin(), weighted_observations.end());
 451   *total_weight = total_weight_observations;
 452 }
 453
 454 int32_t NetworkQualityEstimator::ObservationBuffer::GetPercentile(
 455     int percentile) const {
 456   DCHECK(!observations_.empty());
 457
 458   // Stores WeightedObservation in increasing order of value.
 459   std::vector<WeightedObservation> weighted_observations;
 460
 461   // Total weight of all observations in |weighted_observations|.
 462   double total_weight = 0.0;
 463
 464   ComputeWeightedObservations(weighted_observations, &total_weight);
 465   DCHECK(!weighted_observations.empty());
 466   DCHECK_GT(total_weight, 0.0);
 467   DCHECK_EQ(observations_.size(), weighted_observations.size());
 468
 469   double desired_weight = percentile / 100.0 * total_weight;
 470
 471   double cumulative_weight_seen_so_far = 0.0;
 472   for (const auto& weighted_observation : weighted_observations) {
 473     cumulative_weight_seen_so_far += weighted_observation.weight;
 474
 475     // TODO(tbansal): Consider interpolating between observations.
 476     if (cumulative_weight_seen_so_far >= desired_weight)
 477       return weighted_observation.value;
 478   }
 479
 480   // Computation may reach here due to floating point errors. This may happen
 481   // if |percentile| was 100 (or close to 100), and |desired_weight| was
 482   // slightly larger than |total_weight| (due to floating point errors).
 483   // In this case, we return the highest |value| among all observations.
 484   // This is same as value of the last observation in the sorted vector.
 485   return weighted_observations.at(weighted_observations.size() - 1).value;
 486 }
 487
 488 }  // namespace net