src/net/quic/congestion_control/inter_arrival_overuse_detector.cc

   1 // Copyright (c) 2013 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/quic/congestion_control/inter_arrival_overuse_detector.h"
   6
   7 #include <math.h>
   8 #include <stdlib.h>
   9
  10 #include <algorithm>
  11
  12 // Initial noise variance, equal to a standard deviation of 1 millisecond.
  13 static const float kInitialVarianceNoise = 1000000.0;
  14
  15 // Minimum variance of the time delta.
  16 static const int kMinVarianceDelta = 10000;
  17
  18 // Threshold for accumulated delta.
  19 static const int kThresholdAccumulatedDeltasUs = 1000;
  20
  21 // Same as above, described as numerator and denominator.
  22 static const int kBetaNumerator = 49;
  23 static const int kBetaDenominator = 50;
  24
  25 // Trigger a signal when the accumulated time drift is larger than
  26 // 5 x standard deviation.
  27 // A lower value triggers earlier with more false detect as a side effect.
  28 static const int kDetectDriftStandardDeviation = 5;
  29
  30 // Trigger an overuse when the time difference between send time and receive
  31 // is larger than 7 x standard deviation.
  32 // A lower value triggers earlier with more false detect as a side effect.
  33 static const float kDetectTimeDiffStandardDeviation = 7;
  34
  35 // Trigger an overuse when the mean of the time difference diverges too far
  36 // from 0.
  37 // A higher value trigger earlier with more false detect as a side effect.
  38 static const int kDetectSlopeFactor = 14;
  39
  40 // We need to get some initial statistics before the detection can start.
  41 static const int kMinSamplesBeforeDetect = 10;
  42
  43 namespace net {
  44
  45 InterArrivalOveruseDetector::InterArrivalOveruseDetector()
  46     : last_sequence_number_(0),
  47       num_of_deltas_(0),
  48       accumulated_deltas_(QuicTime::Delta::Zero()),
  49       delta_mean_(0.0),
  50       delta_variance_(kInitialVarianceNoise),
  51       delta_overuse_counter_(0),
  52       delta_estimate_(kBandwidthSteady),
  53       slope_overuse_counter_(0),
  54       slope_estimate_(kBandwidthSteady),
  55       send_receive_offset_(QuicTime::Delta::Infinite()),
  56       estimated_congestion_delay_(QuicTime::Delta::Zero()) {
  57 }
  58
  59 void InterArrivalOveruseDetector::OnAcknowledgedPacket(
  60     QuicPacketSequenceNumber sequence_number,
  61     QuicTime send_time,
  62     bool last_of_send_time,
  63     QuicTime receive_time) {
  64   if (last_sequence_number_ >= sequence_number) {
  65     // This is an old packet and should be ignored.  Note that we are called
  66     // with a full 64 bit sequence number, even if the wire format may only
  67     // convey some low-order bits of that number.
  68     DLOG(INFO) << "Skip old packet";
  69     return;
  70   }
  71
  72   last_sequence_number_ = sequence_number;
  73
  74   if (current_packet_group_.send_time != send_time) {
  75     // First value in this group. If the last packet of a group is lost we
  76     // overwrite the old value and start over with a new measurement.
  77     current_packet_group_.send_time = send_time;
  78     // The receive_time value might not be first in a packet burst if that
  79     // packet was lost, however we will still use it in this calculation.
  80     UpdateSendReceiveTimeOffset(receive_time.Subtract(send_time));
  81   }
  82   if (!last_of_send_time) {
  83     // We expect more packet with this send time.
  84     return;
  85   }
  86   // First packet of a later group, the previous group sample is ready.
  87   if (previous_packet_group_.send_time.IsInitialized()) {
  88     QuicTime::Delta sent_delta = send_time.Subtract(
  89         previous_packet_group_.send_time);
  90     QuicTime::Delta receive_delta = receive_time.Subtract(
  91         previous_packet_group_.last_receive_time);
  92     // We assume that groups of packets are sent together as bursts (tagged
  93     // with identical send times) because it is too computationally expensive
  94     // to pace them out individually.  The received_delta is then the total
  95     // delta between the receipt of the last packet of the previous group, and
  96     // the last packet of the current group.  Assuming we are transmitting
  97     // these bursts on average at the available bandwidth rate, there should be
  98     // no change in overall spread (both deltas should be the same).
  99     UpdateFilter(receive_delta, sent_delta);
 100   }
 101   // Save current as previous.
 102   previous_packet_group_ = current_packet_group_;
 103   previous_packet_group_.last_receive_time = receive_time;
 104 }
 105
 106 void InterArrivalOveruseDetector::UpdateSendReceiveTimeOffset(
 107     QuicTime::Delta offset) {
 108   // Note the send and receive time can have a randomly large offset, however
 109   // they are stable in relation to each other, hence no or extremely low clock
 110   // drift relative to the duration of our stream.
 111   if (offset.ToMicroseconds() < send_receive_offset_.ToMicroseconds()) {
 112     send_receive_offset_ = offset;
 113   }
 114   estimated_congestion_delay_ = offset.Subtract(send_receive_offset_);
 115 }
 116
 117 BandwidthUsage InterArrivalOveruseDetector::GetState(
 118     QuicTime::Delta* estimated_congestion_delay) {
 119   *estimated_congestion_delay = estimated_congestion_delay_;
 120   int64 sigma_delta = sqrt(static_cast<double>(delta_variance_));
 121   DetectSlope(sigma_delta);
 122   DetectDrift(sigma_delta);
 123   return std::max(slope_estimate_, delta_estimate_);
 124 }
 125
 126 void InterArrivalOveruseDetector::UpdateFilter(QuicTime::Delta received_delta,
 127                                                QuicTime::Delta sent_delta) {
 128   ++num_of_deltas_;
 129   QuicTime::Delta time_diff = received_delta.Subtract(sent_delta);
 130   UpdateDeltaEstimate(time_diff);
 131   accumulated_deltas_ = accumulated_deltas_.Add(time_diff);
 132 }
 133
 134 void InterArrivalOveruseDetector::UpdateDeltaEstimate(
 135     QuicTime::Delta residual) {
 136   DCHECK_EQ(1, kBetaDenominator - kBetaNumerator);
 137   int64 residual_us = residual.ToMicroseconds();
 138   delta_mean_ =
 139       (kBetaNumerator * delta_mean_ + residual_us) / kBetaDenominator;
 140   delta_variance_ =
 141       (kBetaNumerator * delta_variance_ +
 142       (delta_mean_ - residual_us) * (delta_mean_ - residual_us)) /
 143       kBetaDenominator;
 144
 145   if (delta_variance_ < kMinVarianceDelta) {
 146     delta_variance_ = kMinVarianceDelta;
 147   }
 148 }
 149
 150 void InterArrivalOveruseDetector::DetectDrift(int64 sigma_delta) {
 151   // We have 2 drift detectors. The accumulate of deltas and the absolute time
 152   // differences.
 153   if (num_of_deltas_ < kMinSamplesBeforeDetect) {
 154     return;
 155   }
 156   if (delta_overuse_counter_ > 0 &&
 157       accumulated_deltas_.ToMicroseconds() > kThresholdAccumulatedDeltasUs) {
 158     if (delta_estimate_ != kBandwidthDraining) {
 159       DLOG(INFO) << "Bandwidth estimate drift: Draining buffer(s) "
 160                  << accumulated_deltas_.ToMilliseconds() << " ms";
 161       delta_estimate_ = kBandwidthDraining;
 162     }
 163     return;
 164   }
 165   if ((sigma_delta * kDetectTimeDiffStandardDeviation >
 166           estimated_congestion_delay_.ToMicroseconds()) &&
 167       (sigma_delta * kDetectDriftStandardDeviation >
 168           abs(accumulated_deltas_.ToMicroseconds()))) {
 169     if (delta_estimate_ != kBandwidthSteady) {
 170       DLOG(INFO) << "Bandwidth estimate drift: Steady"
 171                  << " mean:" << delta_mean_
 172                  << " sigma:" << sigma_delta
 173                  << " offset:" << send_receive_offset_.ToMicroseconds()
 174                  << " delta:" << estimated_congestion_delay_.ToMicroseconds()
 175                  << " drift:" << accumulated_deltas_.ToMicroseconds();
 176       delta_estimate_ = kBandwidthSteady;
 177       // Reset drift counter.
 178       accumulated_deltas_ = QuicTime::Delta::Zero();
 179       delta_overuse_counter_ = 0;
 180     }
 181     return;
 182   }
 183   if (accumulated_deltas_.ToMicroseconds() > 0) {
 184     if (delta_estimate_ != kBandwidthOverUsing) {
 185       ++delta_overuse_counter_;
 186       DLOG(INFO) << "Bandwidth estimate drift: Over using"
 187                  << " mean:" << delta_mean_
 188                  << " sigma:" << sigma_delta
 189                  << " offset:" << send_receive_offset_.ToMicroseconds()
 190                  << " delta:" << estimated_congestion_delay_.ToMicroseconds()
 191                  << " drift:" << accumulated_deltas_.ToMicroseconds();
 192       delta_estimate_ = kBandwidthOverUsing;
 193     }
 194   } else {
 195     if (delta_estimate_ != kBandwidthUnderUsing) {
 196       --delta_overuse_counter_;
 197       DLOG(INFO) << "Bandwidth estimate drift: Under using"
 198                  << " mean:" << delta_mean_
 199                  << " sigma:" << sigma_delta
 200                  << " offset:" << send_receive_offset_.ToMicroseconds()
 201                  << " delta:" << estimated_congestion_delay_.ToMicroseconds()
 202                  << " drift:" << accumulated_deltas_.ToMicroseconds();
 203       delta_estimate_ = kBandwidthUnderUsing;
 204     }
 205     // Adding decay of negative accumulated_deltas_ since it could be caused by
 206     // a starting with full buffers. This way we will always converge to 0.
 207     accumulated_deltas_ = accumulated_deltas_.Add(
 208         QuicTime::Delta::FromMicroseconds(sigma_delta >> 3));
 209   }
 210 }
 211
 212 void InterArrivalOveruseDetector::DetectSlope(int64 sigma_delta) {
 213   // We use the mean change since it has a constant expected mean 0
 214   // regardless of number of packets and spread. It is also safe to use during
 215   // packet loss, since a lost packet only results in a missed filter update
 216   // not a drift.
 217   if (num_of_deltas_ < kMinSamplesBeforeDetect) {
 218     return;
 219   }
 220   if (slope_overuse_counter_ > 0 && delta_mean_ > 0) {
 221     if (slope_estimate_ != kBandwidthDraining) {
 222       DLOG(INFO) << "Bandwidth estimate slope: Draining buffer(s)";
 223     }
 224     slope_estimate_ = kBandwidthDraining;
 225     return;
 226   }
 227   if (sigma_delta > abs(delta_mean_) * kDetectSlopeFactor) {
 228     if (slope_estimate_ != kBandwidthSteady) {
 229       DLOG(INFO) << "Bandwidth estimate slope: Steady"
 230                  << " mean:" << delta_mean_
 231                  << " sigma:" << sigma_delta;
 232       slope_overuse_counter_ = 0;
 233       slope_estimate_ = kBandwidthSteady;
 234     }
 235     return;
 236   }
 237   if (delta_mean_ > 0) {
 238     if (slope_estimate_ != kBandwidthOverUsing) {
 239       ++slope_overuse_counter_;
 240       DLOG(INFO) << "Bandwidth estimate slope: Over using"
 241                  << " mean:" << delta_mean_
 242                  << " sigma:" << sigma_delta;
 243       slope_estimate_ = kBandwidthOverUsing;
 244     }
 245   } else {
 246     if (slope_estimate_ != kBandwidthUnderUsing) {
 247       --slope_overuse_counter_;
 248       DLOG(INFO) << "Bandwidth estimate slope: Under using"
 249                  << " mean:" << delta_mean_
 250                  << " sigma:" << sigma_delta;
 251       slope_estimate_ = kBandwidthUnderUsing;
 252     }
 253   }
 254 }
 255
 256 }  // namespace net