// Copyright (c) 2013 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/quic/congestion_control/inter_arrival_overuse_detector.h" #include #include // Initial noise variance, equal to a standard deviation of 1 millisecond. static const float kInitialVarianceNoise = 1000000.0; // Minimum variance of the time delta. static const int kMinVarianceDelta = 10000; // Threshold for accumulated delta. static const int kThresholdAccumulatedDeltasUs = 1000; // Same as above, described as numerator and denominator. static const int kBetaNumerator = 49; static const int kBetaDenominator = 50; // Trigger a signal when the accumulated time drift is larger than // 5 x standard deviation. // A lower value triggers earlier with more false detect as a side effect. static const int kDetectDriftStandardDeviation = 5; // Trigger an overuse when the time difference between send time and receive // is larger than 7 x standard deviation. // A lower value triggers earlier with more false detect as a side effect. static const float kDetectTimeDiffStandardDeviation = 7; // Trigger an overuse when the mean of the time difference diverges too far // from 0. // A higher value trigger earlier with more false detect as a side effect. static const int kDetectSlopeFactor = 14; // We need to get some initial statistics before the detection can start. static const int kMinSamplesBeforeDetect = 10; namespace net { InterArrivalOveruseDetector::InterArrivalOveruseDetector() : last_sequence_number_(0), num_of_deltas_(0), accumulated_deltas_(QuicTime::Delta::Zero()), delta_mean_(0.0), delta_variance_(kInitialVarianceNoise), delta_overuse_counter_(0), delta_estimate_(kBandwidthSteady), slope_overuse_counter_(0), slope_estimate_(kBandwidthSteady), send_receive_offset_(QuicTime::Delta::Infinite()), estimated_congestion_delay_(QuicTime::Delta::Zero()) { } void InterArrivalOveruseDetector::OnAcknowledgedPacket( QuicPacketSequenceNumber sequence_number, QuicTime send_time, bool last_of_send_time, QuicTime receive_time) { if (last_sequence_number_ >= sequence_number) { // This is an old packet and should be ignored. Note that we are called // with a full 64 bit sequence number, even if the wire format may only // convey some low-order bits of that number. DLOG(INFO) << "Skip old packet"; return; } last_sequence_number_ = sequence_number; if (current_packet_group_.send_time != send_time) { // First value in this group. If the last packet of a group is lost we // overwrite the old value and start over with a new measurement. current_packet_group_.send_time = send_time; // The receive_time value might not be first in a packet burst if that // packet was lost, however we will still use it in this calculation. UpdateSendReceiveTimeOffset(receive_time.Subtract(send_time)); } if (!last_of_send_time) { // We expect more packet with this send time. return; } // First packet of a later group, the previous group sample is ready. if (previous_packet_group_.send_time.IsInitialized()) { QuicTime::Delta sent_delta = send_time.Subtract( previous_packet_group_.send_time); QuicTime::Delta receive_delta = receive_time.Subtract( previous_packet_group_.last_receive_time); // We assume that groups of packets are sent together as bursts (tagged // with identical send times) because it is too computationally expensive // to pace them out individually. The received_delta is then the total // delta between the receipt of the last packet of the previous group, and // the last packet of the current group. Assuming we are transmitting // these bursts on average at the available bandwidth rate, there should be // no change in overall spread (both deltas should be the same). UpdateFilter(receive_delta, sent_delta); } // Save current as previous. previous_packet_group_ = current_packet_group_; previous_packet_group_.last_receive_time = receive_time; } void InterArrivalOveruseDetector::UpdateSendReceiveTimeOffset( QuicTime::Delta offset) { // Note the send and receive time can have a randomly large offset, however // they are stable in relation to each other, hence no or extremely low clock // drift relative to the duration of our stream. if (offset.ToMicroseconds() < send_receive_offset_.ToMicroseconds()) { send_receive_offset_ = offset; } estimated_congestion_delay_ = offset.Subtract(send_receive_offset_); } BandwidthUsage InterArrivalOveruseDetector::GetState( QuicTime::Delta* estimated_congestion_delay) { *estimated_congestion_delay = estimated_congestion_delay_; int64 sigma_delta = sqrt(static_cast(delta_variance_)); DetectSlope(sigma_delta); DetectDrift(sigma_delta); return std::max(slope_estimate_, delta_estimate_); } void InterArrivalOveruseDetector::UpdateFilter(QuicTime::Delta received_delta, QuicTime::Delta sent_delta) { ++num_of_deltas_; QuicTime::Delta time_diff = received_delta.Subtract(sent_delta); UpdateDeltaEstimate(time_diff); accumulated_deltas_ = accumulated_deltas_.Add(time_diff); } void InterArrivalOveruseDetector::UpdateDeltaEstimate( QuicTime::Delta residual) { DCHECK_EQ(1, kBetaDenominator - kBetaNumerator); int64 residual_us = residual.ToMicroseconds(); delta_mean_ = (kBetaNumerator * delta_mean_ + residual_us) / kBetaDenominator; delta_variance_ = (kBetaNumerator * delta_variance_ + (delta_mean_ - residual_us) * (delta_mean_ - residual_us)) / kBetaDenominator; if (delta_variance_ < kMinVarianceDelta) { delta_variance_ = kMinVarianceDelta; } } void InterArrivalOveruseDetector::DetectDrift(int64 sigma_delta) { // We have 2 drift detectors. The accumulate of deltas and the absolute time // differences. if (num_of_deltas_ < kMinSamplesBeforeDetect) { return; } if (delta_overuse_counter_ > 0 && accumulated_deltas_.ToMicroseconds() > kThresholdAccumulatedDeltasUs) { if (delta_estimate_ != kBandwidthDraining) { DLOG(INFO) << "Bandwidth estimate drift: Draining buffer(s) " << accumulated_deltas_.ToMilliseconds() << " ms"; delta_estimate_ = kBandwidthDraining; } return; } if ((sigma_delta * kDetectTimeDiffStandardDeviation > estimated_congestion_delay_.ToMicroseconds()) && (sigma_delta * kDetectDriftStandardDeviation > abs(accumulated_deltas_.ToMicroseconds()))) { if (delta_estimate_ != kBandwidthSteady) { DLOG(INFO) << "Bandwidth estimate drift: Steady" << " mean:" << delta_mean_ << " sigma:" << sigma_delta << " offset:" << send_receive_offset_.ToMicroseconds() << " delta:" << estimated_congestion_delay_.ToMicroseconds() << " drift:" << accumulated_deltas_.ToMicroseconds(); delta_estimate_ = kBandwidthSteady; // Reset drift counter. accumulated_deltas_ = QuicTime::Delta::Zero(); delta_overuse_counter_ = 0; } return; } if (accumulated_deltas_.ToMicroseconds() > 0) { if (delta_estimate_ != kBandwidthOverUsing) { ++delta_overuse_counter_; DLOG(INFO) << "Bandwidth estimate drift: Over using" << " mean:" << delta_mean_ << " sigma:" << sigma_delta << " offset:" << send_receive_offset_.ToMicroseconds() << " delta:" << estimated_congestion_delay_.ToMicroseconds() << " drift:" << accumulated_deltas_.ToMicroseconds(); delta_estimate_ = kBandwidthOverUsing; } } else { if (delta_estimate_ != kBandwidthUnderUsing) { --delta_overuse_counter_; DLOG(INFO) << "Bandwidth estimate drift: Under using" << " mean:" << delta_mean_ << " sigma:" << sigma_delta << " offset:" << send_receive_offset_.ToMicroseconds() << " delta:" << estimated_congestion_delay_.ToMicroseconds() << " drift:" << accumulated_deltas_.ToMicroseconds(); delta_estimate_ = kBandwidthUnderUsing; } // Adding decay of negative accumulated_deltas_ since it could be caused by // a starting with full buffers. This way we will always converge to 0. accumulated_deltas_ = accumulated_deltas_.Add( QuicTime::Delta::FromMicroseconds(sigma_delta >> 3)); } } void InterArrivalOveruseDetector::DetectSlope(int64 sigma_delta) { // We use the mean change since it has a constant expected mean 0 // regardless of number of packets and spread. It is also safe to use during // packet loss, since a lost packet only results in a missed filter update // not a drift. if (num_of_deltas_ < kMinSamplesBeforeDetect) { return; } if (slope_overuse_counter_ > 0 && delta_mean_ > 0) { if (slope_estimate_ != kBandwidthDraining) { DLOG(INFO) << "Bandwidth estimate slope: Draining buffer(s)"; } slope_estimate_ = kBandwidthDraining; return; } if (sigma_delta > abs(delta_mean_) * kDetectSlopeFactor) { if (slope_estimate_ != kBandwidthSteady) { DLOG(INFO) << "Bandwidth estimate slope: Steady" << " mean:" << delta_mean_ << " sigma:" << sigma_delta; slope_overuse_counter_ = 0; slope_estimate_ = kBandwidthSteady; } return; } if (delta_mean_ > 0) { if (slope_estimate_ != kBandwidthOverUsing) { ++slope_overuse_counter_; DLOG(INFO) << "Bandwidth estimate slope: Over using" << " mean:" << delta_mean_ << " sigma:" << sigma_delta; slope_estimate_ = kBandwidthOverUsing; } } else { if (slope_estimate_ != kBandwidthUnderUsing) { --slope_overuse_counter_; DLOG(INFO) << "Bandwidth estimate slope: Under using" << " mean:" << delta_mean_ << " sigma:" << sigma_delta; slope_estimate_ = kBandwidthUnderUsing; } } } } // namespace net