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 DVLOG(1) << "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 DVLOG(1) << "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 DVLOG(1) << "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 DVLOG(1) << "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 DVLOG(1) << "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 DVLOG(1) << "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 DVLOG(1) << "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 DVLOG(1) << "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 DVLOG(1) << "Bandwidth estimate slope: Under using" 249 << " mean:" << delta_mean_ 250 << " sigma:" << sigma_delta; 251 slope_estimate_ = kBandwidthUnderUsing; 252 } 253 } 254 } 255 256 } // namespace net 257
