Expose packet loss counts from QUIC to NetworkQualityEstimator

net/base/network_quality_estimator.cc

 // Copyright 2015 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/base/network_quality_estimator.h"
 
 #include <float.h>
 #include <algorithm>
 #include <cmath>
 #include <limits>
@@ skipping 123 matching lines @@
     bool allow_smaller_responses_for_tests)
     : allow_localhost_requests_(allow_local_host_requests_for_tests),
       allow_small_responses_(allow_smaller_responses_for_tests),
       last_connection_change_(base::TimeTicks::Now()),
       current_network_id_(
           NetworkID(NetworkChangeNotifier::ConnectionType::CONNECTION_UNKNOWN,
                     std::string())),
       downstream_throughput_kbps_observations_(
           GetWeightMultiplierPerSecond(variation_params)),
       rtt_msec_observations_(GetWeightMultiplierPerSecond(variation_params)),
+      packet_loss_rate_observations_(
+          GetWeightMultiplierPerSecond(variation_params)),
       external_estimate_provider_(std::move(external_estimates_provider)) {
   static_assert(kMinRequestDurationMicroseconds > 0,
                 "Minimum request duration must be > 0");
   static_assert(kDefaultHalfLifeSeconds > 0,
                 "Default half life duration must be > 0");
   static_assert(kMaximumNetworkQualityCacheSize > 0,
                 "Size of the network quality cache must be > 0");
   // This limit should not be increased unless the logic for removing the
   // oldest cache entry is rewritten to use a doubly-linked-list LRU queue.
   static_assert(kMaximumNetworkQualityCacheSize <= 10,
@@ skipping 89 matching lines @@
   DCHECK(thread_checker_.CalledOnValidThread());
 
   if (!RequestProvidesUsefulObservations(request))
     return;
 
   // Update |estimated_median_network_quality_| if this is a main frame request.
   if (request.load_flags() & LOAD_MAIN_FRAME) {
     estimated_median_network_quality_ = NetworkQuality(
         GetRTTEstimateInternal(base::TimeTicks(), 50),
         GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50));
+
+    float packet_loss_rate;
+    if (GetPacketLossRateEstimate(&packet_loss_rate)) {
+      DCHECK_LE(0.0f, packet_loss_rate);
+      DCHECK_GE(1.0f, packet_loss_rate);
+
+      // Largest bucket is 101.
+      base::HistogramBase* packet_loss_histogram =
+          GetHistogram("PacketLossRate.", current_network_id_.type, 101);
+      packet_loss_histogram->Add(packet_loss_rate * 100.0f);
+    }
   }
 
   base::TimeTicks now = base::TimeTicks::Now();
   LoadTimingInfo load_timing_info;
   request.GetLoadTimingInfo(&load_timing_info);
 
   // If the load timing info is unavailable, it probably means that the request
   // did not go over the network.
   if (load_timing_info.send_start.is_null() ||
       load_timing_info.receive_headers_end.is_null()) {
@@ skipping 106 matching lines @@
   DCHECK(thread_checker_.CalledOnValidThread());
   throughput_observer_list_.AddObserver(throughput_observer);
 }
 
 void NetworkQualityEstimator::RemoveThroughputObserver(
     ThroughputObserver* throughput_observer) {
   DCHECK(thread_checker_.CalledOnValidThread());
   throughput_observer_list_.RemoveObserver(throughput_observer);
 }
 
+void NetworkQualityEstimator::AddPacketLossObserver(
+    PacketLossObserver* packet_loss_observer) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  packet_loss_observer_list_.AddObserver(packet_loss_observer);
+}
+
+void NetworkQualityEstimator::RemovePacketLossObserver(
+    PacketLossObserver* packet_loss_observer) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  packet_loss_observer_list_.RemoveObserver(packet_loss_observer);
+}
+
 void NetworkQualityEstimator::RecordRTTUMA(int32_t estimated_value_msec,
                                            int32_t actual_value_msec) const {
   DCHECK(thread_checker_.CalledOnValidThread());
 
   // Record the difference between the actual and the estimated value.
   if (estimated_value_msec >= actual_value_msec) {
     base::HistogramBase* difference_rtt =
         GetHistogram("DifferenceRTTEstimatedAndActual.",
                      current_network_id_.type, 10 * 1000);  // 10 seconds
     difference_rtt->Add(estimated_value_msec - actual_value_msec);
@@ skipping 33 matching lines @@
          !request.was_cached() &&
          request.creation_time() >= last_connection_change_;
 }
 
 void NetworkQualityEstimator::RecordExternalEstimateProviderMetrics(
     NQEExternalEstimateProviderStatus status) const {
   UMA_HISTOGRAM_ENUMERATION("NQE.ExternalEstimateProviderStatus", status,
                             EXTERNAL_ESTIMATE_PROVIDER_STATUS_BOUNDARY);
 }
 
+bool NetworkQualityEstimator::GetObservationSourceForProtocol(
+    Protocol protocol,
+    NetworkQualityEstimator::ObservationSource* observation_source) const {
+  switch (protocol) {
+    case PROTOCOL_TCP:
+      *observation_source = TCP;
+      return true;
+    case PROTOCOL_QUIC:
+      *observation_source = QUIC;
+      return true;
+    default:
+      NOTREACHED();
+      return false;
+  }
+}
+
 void NetworkQualityEstimator::OnConnectionTypeChanged(
     NetworkChangeNotifier::ConnectionType type) {
   DCHECK(thread_checker_.CalledOnValidThread());
   if (peak_network_quality_.rtt() != InvalidRTT()) {
     switch (current_network_id_.type) {
       case NetworkChangeNotifier::CONNECTION_UNKNOWN:
         UMA_HISTOGRAM_TIMES("NQE.FastestRTT.Unknown",
                             peak_network_quality_.rtt());
         break;
       case NetworkChangeNotifier::CONNECTION_ETHERNET:
@@ skipping 97 matching lines @@
   }
 
   // Write the estimates of the previous network to the cache.
   CacheNetworkQualityEstimate();
 
   // Clear the local state.
   last_connection_change_ = base::TimeTicks::Now();
   peak_network_quality_ = NetworkQuality();
   downstream_throughput_kbps_observations_.Clear();
   rtt_msec_observations_.Clear();
+  packet_loss_rate_observations_.Clear();
   current_network_id_ = GetCurrentNetworkID();
 
   QueryExternalEstimateProvider();
 
   // Read any cached estimates for the new network. If cached estimates are
   // unavailable, add the default estimates.
   if (!ReadCachedNetworkQualityEstimate())
     AddDefaultEstimates();
   estimated_median_network_quality_ = NetworkQuality();
 }
@@ skipping 14 matching lines @@
   DCHECK(thread_checker_.CalledOnValidThread());
   DCHECK(kbps);
   if (downstream_throughput_kbps_observations_.Size() == 0) {
     *kbps = kInvalidThroughput;
     return false;
   }
   *kbps = GetDownlinkThroughputKbpsEstimateInternal(base::TimeTicks(), 50);
   return (*kbps != kInvalidThroughput);
 }
 
+bool NetworkQualityEstimator::GetPacketLossRateEstimate(
+    float* packet_loss_rate_estimate) const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  float estimate = GetPacketLossRateEstimateInternal(base::TimeTicks());
+  if (estimate < 0.0f || estimate > 1.0f)
+    return false;
+  *packet_loss_rate_estimate = estimate;
+  return true;
+}
+
 bool NetworkQualityEstimator::GetRecentMedianRTT(
     const base::TimeTicks& begin_timestamp,
     base::TimeDelta* rtt) const {
   DCHECK(thread_checker_.CalledOnValidThread());
   DCHECK(rtt);
   *rtt = GetRTTEstimateInternal(begin_timestamp, 50);
   return (*rtt != InvalidRTT());
 }
 
 bool NetworkQualityEstimator::GetRecentMedianDownlinkThroughputKbps(
@@ skipping 44 matching lines @@
     return kInvalidThroughput;
 
   // Throughput observations are sorted by kbps from slowest to fastest,
   // thus a higher percentile throughput will be faster than a lower one.
   int32_t kbps = kInvalidThroughput;
   downstream_throughput_kbps_observations_.GetPercentile(begin_timestamp, &kbps,
                                                          100 - percentile);
   return kbps;
 }
 
+float NetworkQualityEstimator::GetPacketLossRateEstimateInternal(
+    const base::TimeTicks& begin_timestamp) const {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  if (packet_loss_rate_observations_.Size() == 0)
+    return -1.0f;
+
+  float packet_loss_rate;
+  if (!packet_loss_rate_observations_.GetWeightedAverage(begin_timestamp,
+                                                         &packet_loss_rate)) {
+    return -1.0f;
+  }
+  DCHECK_LE(0.0f, packet_loss_rate);
+  DCHECK_GE(1.0f, packet_loss_rate);
+  return packet_loss_rate;
+}
+
 template <typename ValueType>
 void NetworkQualityEstimator::ObservationBuffer<ValueType>::
     ComputeWeightedObservations(
         const base::TimeTicks& begin_timestamp,
         std::vector<WeightedObservation<ValueType>>& weighted_observations,
         double* total_weight) const {
   weighted_observations.clear();
   double total_weight_observations = 0.0;
   base::TimeTicks now = base::TimeTicks::Now();
 
@@ skipping 53 matching lines @@
 
   // Computation may reach here due to floating point errors. This may happen
   // if |percentile| was 100 (or close to 100), and |desired_weight| was
   // slightly larger than |total_weight| (due to floating point errors).
   // In this case, we return the highest |value| among all observations.
   // This is same as value of the last observation in the sorted vector.
   *result = weighted_observations.at(weighted_observations.size() - 1).value;
   return true;
 }
 
+template <typename ValueType>
+bool NetworkQualityEstimator::ObservationBuffer<ValueType>::GetWeightedAverage(
+    const base::TimeTicks& begin_timestamp,
+    ValueType* result) const {
+  DCHECK(result);
+
+  // Stores |weighted_observations| in the increasing order of value with lower
+  // values at the front of the vector.
+  std::vector<WeightedObservation<ValueType>> weighted_observations;
+
+  // The sum of the weights of all observations in |weighted_observations|.
+  double total_weight = 0.0;
+
+  ComputeWeightedObservations(begin_timestamp, weighted_observations,
+                              &total_weight);
+  if (weighted_observations.empty())
+    return false;
+
+  DCHECK_GT(total_weight, 0.0);
+
+  // |weighted_observations| may have a smaller size than |observations_| since
+  // the former only contains the observations later than |begin_timestamp|.
+  DCHECK_GE(observations_.size(), weighted_observations.size());
+
+  double total_weight_times_value = 0.0;
+  for (const auto& weighted_observation : weighted_observations) {
+    total_weight_times_value +=
+        (weighted_observation.weight * weighted_observation.value);
+  }
+  *result = total_weight_times_value / total_weight;
+  return true;
+}
+
 NetworkQualityEstimator::NetworkID
 NetworkQualityEstimator::GetCurrentNetworkID() const {
   DCHECK(thread_checker_.CalledOnValidThread());
 
   // TODO(tbansal): crbug.com/498068 Add NetworkQualityEstimatorAndroid class
   // that overrides this method on the Android platform.
 
   // It is possible that the connection type changed between when
   // GetConnectionType() was called and when the API to determine the
   // network name was called. Check if that happened and retry until the
@@ skipping 163 matching lines @@
 
   return scoped_ptr<SocketPerformanceWatcher>(
       new SocketPerformanceWatcher(protocol, this));
 }
 
 void NetworkQualityEstimator::OnUpdatedRTTAvailable(
     const Protocol protocol,
     const base::TimeDelta& rtt) {
   DCHECK(thread_checker_.CalledOnValidThread());
 
-  switch (protocol) {
-    case PROTOCOL_TCP:
-      NotifyObserversOfRTT(RttObservation(rtt, base::TimeTicks::Now(), TCP));
-      return;
-    case PROTOCOL_QUIC:
-      NotifyObserversOfRTT(RttObservation(rtt, base::TimeTicks::Now(), QUIC));
-      return;
-    default:
-      NOTREACHED();
+  ObservationSource observation_source;
+  if (!GetObservationSourceForProtocol(protocol, &observation_source))
+    return;
+
+  NotifyObserversOfRTT(
+      RttObservation(rtt, base::TimeTicks::Now(), observation_source));
+}
+
+void NetworkQualityEstimator::OnUpdatedPacketCountAvailable(
+    Protocol protocol,
+    size_t packets_missing,
+    size_t packets_received_in_order,
+    size_t packets_received_out_of_order) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+
+  const base::TimeTicks now = base::TimeTicks::Now();
+
+  ObservationSource observation_source;
+  if (!GetObservationSourceForProtocol(protocol, &observation_source))
+    return;
+
+  // Consider it as a packet loss only if at least 3 packets are received after
+  // the missing packets.
+  // TODO(tbansal): Maintain a watcher specific state to accurately compute if
+  // more than 3 packets were received after the missing packet.
+  if (packets_received_in_order >= 3) {

[Ryan Hamilton, 2016/03/07 20:02:10]

But this argument is really only going to ever be 0 or 1, right?

[tbansal1, 2016/03/08 02:59:58]

Obsolete.

+    for (size_t i = 0; i < packets_missing; ++i) {
+      packet_loss_rate_observations_.AddObservation(
+          PacketLossRateObservation(1.0, now, observation_source));
+    }
   }
+  for (size_t i = 0; i < packets_received_in_order; ++i) {
+    packet_loss_rate_observations_.AddObservation(
+        PacketLossRateObservation(0.0, now, observation_source));

[Ryan Hamilton, 2016/03/07 20:02:10]

You're computing packet loss rate per-packet? That seems unusual.

[tbansal1, 2016/03/08 02:59:58]

Obsolete.

+  }
+  // For packet loss estimation, we neglect the packets that were previously
+  // marked as lost but are later received out-of-order.
+  NotifyObserversOfPacketCount(packets_missing, packets_received_in_order,
+                               packets_received_out_of_order, now,
+                               observation_source);
 }
 
 void NetworkQualityEstimator::NotifyObserversOfRTT(
     const RttObservation& observation) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK_NE(EXTERNAL_ESTIMATE, observation.source);
+
   FOR_EACH_OBSERVER(
       RTTObserver, rtt_observer_list_,
       OnRTTObservation(observation.value.InMilliseconds(),
                        observation.timestamp, observation.source));
 }
 
 void NetworkQualityEstimator::NotifyObserversOfThroughput(
     const ThroughputObservation& observation) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK_NE(EXTERNAL_ESTIMATE, observation.source);
+
   FOR_EACH_OBSERVER(
       ThroughputObserver, throughput_observer_list_,
       OnThroughputObservation(observation.value, observation.timestamp,
                               observation.source));
 }
 
+void NetworkQualityEstimator::NotifyObserversOfPacketCount(
+    size_t packets_missing,
+    size_t packets_received_in_order,
+    size_t packets_received_out_of_order,
+    const base::TimeTicks& timestamp,
+    ObservationSource source) {
+  DCHECK(thread_checker_.CalledOnValidThread());
+  DCHECK_NE(EXTERNAL_ESTIMATE, source);
+
+  FOR_EACH_OBSERVER(PacketLossObserver, packet_loss_observer_list_,
+                    OnPacketLossObservation(
+                        packets_missing, packets_received_in_order,
+                        packets_received_out_of_order, timestamp, source));
+}
+
 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
     const NetworkQuality& network_quality)
     : last_update_time_(base::TimeTicks::Now()),
       network_quality_(network_quality) {
 }
 
 NetworkQualityEstimator::CachedNetworkQuality::CachedNetworkQuality(
     const CachedNetworkQuality& other)
     : last_update_time_(other.last_update_time_),
       network_quality_(other.network_quality_) {
@@ skipping 27 matching lines @@
 
 NetworkQualityEstimator::NetworkQuality&
     NetworkQualityEstimator::NetworkQuality::
     operator=(const NetworkQuality& other) {
   rtt_ = other.rtt_;
   downstream_throughput_kbps_ = other.downstream_throughput_kbps_;
   return *this;
 }
 
 }  // namespace net