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_sender.h" 6 7 namespace net { 8 9 namespace { 10 const int64 kProbeBitrateKBytesPerSecond = 1200; // 9.6 Mbit/s 11 const float kPacketLossBitrateReduction = 0.7f; 12 const float kUncertainSafetyMargin = 0.7f; 13 const float kMaxBitrateReduction = 0.9f; 14 const float kMinBitrateReduction = 0.05f; 15 const uint64 kMinBitrateKbit = 10; 16 const int kInitialRttMs = 60; // At a typical RTT 60 ms. 17 const float kAlpha = 0.125f; 18 const float kOneMinusAlpha = 1 - kAlpha; 19 20 static const int kBitrateSmoothingPeriodMs = 1000; 21 static const int kMinBitrateSmoothingPeriodMs = 500; 22 23 } // namespace 24 25 InterArrivalSender::InterArrivalSender(const QuicClock* clock) 26 : probing_(true), 27 current_bandwidth_(QuicBandwidth::Zero()), 28 smoothed_rtt_(QuicTime::Delta::Zero()), 29 channel_estimator_(new ChannelEstimator()), 30 bitrate_ramp_up_(new InterArrivalBitrateRampUp(clock)), 31 overuse_detector_(new InterArrivalOveruseDetector()), 32 probe_(new InterArrivalProbe()), 33 state_machine_(new InterArrivalStateMachine(clock)), 34 paced_sender_(new PacedSender(QuicBandwidth::FromKBytesPerSecond( 35 kProbeBitrateKBytesPerSecond))), 36 accumulated_number_of_lost_packets_(0), 37 bandwidth_usage_state_(kBandwidthSteady), 38 back_down_time_(QuicTime::Zero()), 39 back_down_bandwidth_(QuicBandwidth::Zero()), 40 back_down_congestion_delay_(QuicTime::Delta::Zero()) { 41 } 42 43 InterArrivalSender::~InterArrivalSender() { 44 } 45 46 // TODO(pwestin): this is really inefficient (4% CPU on the GFE loadtest). 47 // static 48 QuicBandwidth InterArrivalSender::CalculateSentBandwidth( 49 const SendAlgorithmInterface::SentPacketsMap& sent_packets_map, 50 QuicTime feedback_receive_time) { 51 const QuicTime::Delta kBitrateSmoothingPeriod = 52 QuicTime::Delta::FromMilliseconds(kBitrateSmoothingPeriodMs); 53 const QuicTime::Delta kMinBitrateSmoothingPeriod = 54 QuicTime::Delta::FromMilliseconds(kMinBitrateSmoothingPeriodMs); 55 56 QuicByteCount sum_bytes_sent = 0; 57 58 // Sum packet from new until they are kBitrateSmoothingPeriod old. 59 SendAlgorithmInterface::SentPacketsMap::const_reverse_iterator history_rit = 60 sent_packets_map.rbegin(); 61 62 QuicTime::Delta max_diff = QuicTime::Delta::Zero(); 63 for (; history_rit != sent_packets_map.rend(); ++history_rit) { 64 QuicTime::Delta diff = 65 feedback_receive_time.Subtract(history_rit->second->SendTimestamp()); 66 if (diff > kBitrateSmoothingPeriod) { 67 break; 68 } 69 sum_bytes_sent += history_rit->second->BytesSent(); 70 max_diff = diff; 71 } 72 if (max_diff < kMinBitrateSmoothingPeriod) { 73 // No estimate. 74 return QuicBandwidth::Zero(); 75 } 76 return QuicBandwidth::FromBytesAndTimeDelta(sum_bytes_sent, max_diff); 77 } 78 79 void InterArrivalSender::OnIncomingQuicCongestionFeedbackFrame( 80 const QuicCongestionFeedbackFrame& feedback, 81 QuicTime feedback_receive_time, 82 const SentPacketsMap& sent_packets) { 83 DCHECK(feedback.type == kInterArrival); 84 85 if (feedback.type != kInterArrival) { 86 return; 87 } 88 89 QuicBandwidth sent_bandwidth = CalculateSentBandwidth(sent_packets, 90 feedback_receive_time); 91 92 TimeMap::const_iterator received_it; 93 for (received_it = feedback.inter_arrival.received_packet_times.begin(); 94 received_it != feedback.inter_arrival.received_packet_times.end(); 95 ++received_it) { 96 QuicPacketSequenceNumber sequence_number = received_it->first; 97 98 SentPacketsMap::const_iterator sent_it = sent_packets.find(sequence_number); 99 if (sent_it == sent_packets.end()) { 100 // Too old data; ignore and move forward. 101 DLOG(INFO) << "Too old feedback move forward, sequence_number:" 102 << sequence_number; 103 continue; 104 } 105 QuicTime time_received = received_it->second; 106 QuicTime time_sent = sent_it->second->SendTimestamp(); 107 QuicByteCount bytes_sent = sent_it->second->BytesSent(); 108 109 channel_estimator_->OnAcknowledgedPacket( 110 sequence_number, bytes_sent, time_sent, time_received); 111 if (probing_) { 112 probe_->OnIncomingFeedback( 113 sequence_number, bytes_sent, time_sent, time_received); 114 } else { 115 bool last_of_send_time = false; 116 SentPacketsMap::const_iterator next_sent_it = ++sent_it; 117 if (next_sent_it == sent_packets.end()) { 118 // No more sent packets; hence this must be the last. 119 last_of_send_time = true; 120 } else { 121 if (time_sent != next_sent_it->second->SendTimestamp()) { 122 // Next sent packet have a different send time. 123 last_of_send_time = true; 124 } 125 } 126 overuse_detector_->OnAcknowledgedPacket( 127 sequence_number, time_sent, last_of_send_time, time_received); 128 } 129 } 130 if (probing_) { 131 probing_ = ProbingPhase(feedback_receive_time); 132 return; 133 } 134 135 bool packet_loss_event = false; 136 if (accumulated_number_of_lost_packets_ != 137 feedback.inter_arrival.accumulated_number_of_lost_packets) { 138 accumulated_number_of_lost_packets_ = 139 feedback.inter_arrival.accumulated_number_of_lost_packets; 140 packet_loss_event = true; 141 } 142 InterArrivalState state = state_machine_->GetInterArrivalState(); 143 144 if (state == kInterArrivalStatePacketLoss || 145 state == kInterArrivalStateCompetingTcpFLow) { 146 if (packet_loss_event) { 147 if (!state_machine_->PacketLossEvent()) { 148 // Less than one RTT since last PacketLossEvent. 149 return; 150 } 151 EstimateBandwidthAfterLossEvent(feedback_receive_time); 152 } else { 153 EstimateNewBandwidth(feedback_receive_time, sent_bandwidth); 154 } 155 return; 156 } 157 EstimateDelayBandwidth(feedback_receive_time, sent_bandwidth); 158 } 159 160 bool InterArrivalSender::ProbingPhase(QuicTime feedback_receive_time) { 161 QuicBandwidth available_channel_estimate = QuicBandwidth::Zero(); 162 if (!probe_->GetEstimate(&available_channel_estimate)) { 163 // Continue probing phase. 164 return true; 165 } 166 QuicBandwidth channel_estimate = QuicBandwidth::Zero(); 167 ChannelEstimateState channel_estimator_state = 168 channel_estimator_->GetChannelEstimate(&channel_estimate); 169 170 QuicBandwidth new_rate = 171 available_channel_estimate.Scale(kUncertainSafetyMargin); 172 173 switch (channel_estimator_state) { 174 case kChannelEstimateUnknown: 175 channel_estimate = available_channel_estimate; 176 break; 177 case kChannelEstimateUncertain: 178 channel_estimate = channel_estimate.Scale(kUncertainSafetyMargin); 179 break; 180 case kChannelEstimateGood: 181 // Do nothing. 182 break; 183 } 184 new_rate = std::max(new_rate, 185 QuicBandwidth::FromKBitsPerSecond(kMinBitrateKbit)); 186 187 bitrate_ramp_up_->Reset(new_rate, available_channel_estimate, 188 channel_estimate); 189 190 current_bandwidth_ = new_rate; 191 paced_sender_->UpdateBandwidthEstimate(feedback_receive_time, new_rate); 192 DLOG(INFO) << "Probe result; new rate:" 193 << new_rate.ToKBitsPerSecond() << " Kbits/s " 194 << " available estimate:" 195 << available_channel_estimate.ToKBitsPerSecond() << " Kbits/s " 196 << " channel estimate:" 197 << channel_estimate.ToKBitsPerSecond() << " Kbits/s "; 198 return false; 199 } 200 201 void InterArrivalSender::OnIncomingAck( 202 QuicPacketSequenceNumber /*acked_sequence_number*/, 203 QuicByteCount acked_bytes, 204 QuicTime::Delta rtt) { 205 // RTT can't be negative. 206 DCHECK_LE(0, rtt.ToMicroseconds()); 207 208 if (probing_) { 209 probe_->OnAcknowledgedPacket(acked_bytes); 210 } 211 212 if (rtt.IsInfinite()) { 213 return; 214 } 215 216 if (smoothed_rtt_.IsZero()) { 217 smoothed_rtt_ = rtt; 218 } else { 219 smoothed_rtt_ = QuicTime::Delta::FromMicroseconds( 220 kOneMinusAlpha * smoothed_rtt_.ToMicroseconds() + 221 kAlpha * rtt.ToMicroseconds()); 222 } 223 state_machine_->set_rtt(smoothed_rtt_); 224 } 225 226 void InterArrivalSender::OnIncomingLoss(QuicTime ack_receive_time) { 227 // Packet loss was reported. 228 if (!probing_) { 229 if (!state_machine_->PacketLossEvent()) { 230 // Less than one RTT since last PacketLossEvent. 231 return; 232 } 233 // Calculate new pace rate. 234 EstimateBandwidthAfterLossEvent(ack_receive_time); 235 } 236 } 237 238 void InterArrivalSender::SentPacket(QuicTime sent_time, 239 QuicPacketSequenceNumber sequence_number, 240 QuicByteCount bytes, 241 Retransmission /*retransmit*/) { 242 if (probing_) { 243 probe_->OnSentPacket(bytes); 244 } 245 paced_sender_->SentPacket(sent_time, bytes); 246 } 247 248 void InterArrivalSender::AbandoningPacket( 249 QuicPacketSequenceNumber /*sequence_number*/, 250 QuicByteCount abandoned_bytes) { 251 // TODO(pwestin): use for out outer_congestion_window_ logic. 252 if (probing_) { 253 probe_->OnAcknowledgedPacket(abandoned_bytes); 254 } 255 } 256 257 QuicTime::Delta InterArrivalSender::TimeUntilSend( 258 QuicTime now, 259 Retransmission /*retransmit*/, 260 HasRetransmittableData has_retransmittable_data, 261 IsHandshake /* handshake */) { 262 // TODO(pwestin): implement outer_congestion_window_ logic. 263 QuicTime::Delta outer_window = QuicTime::Delta::Zero(); 264 265 if (probing_) { 266 if (has_retransmittable_data == HAS_RETRANSMITTABLE_DATA && 267 probe_->GetAvailableCongestionWindow() == 0) { 268 outer_window = QuicTime::Delta::Infinite(); 269 } 270 } 271 return paced_sender_->TimeUntilSend(now, outer_window); 272 } 273 274 void InterArrivalSender::EstimateDelayBandwidth(QuicTime feedback_receive_time, 275 QuicBandwidth sent_bandwidth) { 276 QuicTime::Delta estimated_congestion_delay = QuicTime::Delta::Zero(); 277 BandwidthUsage new_bandwidth_usage_state = 278 overuse_detector_->GetState(&estimated_congestion_delay); 279 280 switch (new_bandwidth_usage_state) { 281 case kBandwidthDraining: 282 case kBandwidthUnderUsing: 283 // Hold our current bitrate. 284 break; 285 case kBandwidthOverUsing: 286 if (!state_machine_->IncreasingDelayEvent()) { 287 // Less than one RTT since last IncreasingDelayEvent. 288 return; 289 } 290 EstimateBandwidthAfterDelayEvent(feedback_receive_time, 291 estimated_congestion_delay); 292 break; 293 case kBandwidthSteady: 294 // Calculate new pace rate. 295 if (bandwidth_usage_state_ == kBandwidthDraining || 296 bandwidth_usage_state_ == kBandwidthOverUsing) { 297 EstimateNewBandwidthAfterDraining(feedback_receive_time, 298 estimated_congestion_delay); 299 } else { 300 EstimateNewBandwidth(feedback_receive_time, sent_bandwidth); 301 } 302 break; 303 } 304 bandwidth_usage_state_ = new_bandwidth_usage_state; 305 } 306 307 QuicBandwidth InterArrivalSender::BandwidthEstimate() { 308 return current_bandwidth_; 309 } 310 311 QuicTime::Delta InterArrivalSender::SmoothedRtt() { 312 if (smoothed_rtt_.IsZero()) { 313 return QuicTime::Delta::FromMilliseconds(kInitialRttMs); 314 } 315 return smoothed_rtt_; 316 } 317 318 QuicTime::Delta InterArrivalSender::RetransmissionDelay() { 319 // TODO(pwestin): Calculate and return retransmission delay. 320 // Use 2 * the smoothed RTT for now. 321 return smoothed_rtt_.Add(smoothed_rtt_); 322 } 323 324 void InterArrivalSender::EstimateNewBandwidth(QuicTime feedback_receive_time, 325 QuicBandwidth sent_bandwidth) { 326 QuicBandwidth new_bandwidth = bitrate_ramp_up_->GetNewBitrate(sent_bandwidth); 327 if (current_bandwidth_ == new_bandwidth) { 328 return; 329 } 330 current_bandwidth_ = new_bandwidth; 331 state_machine_->IncreaseBitrateDecision(); 332 333 QuicBandwidth channel_estimate = QuicBandwidth::Zero(); 334 ChannelEstimateState channel_estimator_state = 335 channel_estimator_->GetChannelEstimate(&channel_estimate); 336 337 if (channel_estimator_state == kChannelEstimateGood) { 338 bitrate_ramp_up_->UpdateChannelEstimate(channel_estimate); 339 } 340 paced_sender_->UpdateBandwidthEstimate(feedback_receive_time, 341 current_bandwidth_); 342 DLOG(INFO) << "New bandwidth estimate in steady state:" 343 << current_bandwidth_.ToKBitsPerSecond() 344 << " Kbits/s"; 345 } 346 347 // Did we drain the network buffers in our expected pace? 348 void InterArrivalSender::EstimateNewBandwidthAfterDraining( 349 QuicTime feedback_receive_time, 350 QuicTime::Delta estimated_congestion_delay) { 351 if (current_bandwidth_ > back_down_bandwidth_) { 352 // Do nothing, our current bandwidth is higher than our bandwidth at the 353 // previous back down. 354 DLOG(INFO) << "Current bandwidth estimate is higher than before draining"; 355 return; 356 } 357 if (estimated_congestion_delay >= back_down_congestion_delay_) { 358 // Do nothing, our estimated delay have increased. 359 DLOG(INFO) << "Current delay estimate is higher than before draining"; 360 return; 361 } 362 DCHECK(back_down_time_.IsInitialized()); 363 QuicTime::Delta buffer_reduction = 364 back_down_congestion_delay_.Subtract(estimated_congestion_delay); 365 QuicTime::Delta elapsed_time = 366 feedback_receive_time.Subtract(back_down_time_).Subtract(SmoothedRtt()); 367 368 QuicBandwidth new_estimate = QuicBandwidth::Zero(); 369 if (buffer_reduction >= elapsed_time) { 370 // We have drained more than the elapsed time... go back to our old rate. 371 new_estimate = back_down_bandwidth_; 372 } else { 373 float fraction_of_rate = 374 static_cast<float>(buffer_reduction.ToMicroseconds()) / 375 elapsed_time.ToMicroseconds(); // < 1.0 376 377 QuicBandwidth draining_rate = back_down_bandwidth_.Scale(fraction_of_rate); 378 QuicBandwidth max_estimated_draining_rate = 379 back_down_bandwidth_.Subtract(current_bandwidth_); 380 if (draining_rate > max_estimated_draining_rate) { 381 // We drained faster than our old send rate, go back to our old rate. 382 new_estimate = back_down_bandwidth_; 383 } else { 384 // Use our drain rate and our kMinBitrateReduction to go to our 385 // new estimate. 386 new_estimate = std::max(current_bandwidth_, 387 current_bandwidth_.Add(draining_rate).Scale( 388 1.0f - kMinBitrateReduction)); 389 DLOG(INFO) << "Draining calculation; current rate:" 390 << current_bandwidth_.ToKBitsPerSecond() << " Kbits/s " 391 << "draining rate:" 392 << draining_rate.ToKBitsPerSecond() << " Kbits/s " 393 << "new estimate:" 394 << new_estimate.ToKBitsPerSecond() << " Kbits/s " 395 << " buffer reduction:" 396 << buffer_reduction.ToMicroseconds() << " us " 397 << " elapsed time:" 398 << elapsed_time.ToMicroseconds() << " us "; 399 } 400 } 401 if (new_estimate == current_bandwidth_) { 402 return; 403 } 404 405 QuicBandwidth channel_estimate = QuicBandwidth::Zero(); 406 ChannelEstimateState channel_estimator_state = 407 channel_estimator_->GetChannelEstimate(&channel_estimate); 408 409 // TODO(pwestin): we need to analyze channel_estimate too. 410 switch (channel_estimator_state) { 411 case kChannelEstimateUnknown: 412 channel_estimate = current_bandwidth_; 413 break; 414 case kChannelEstimateUncertain: 415 channel_estimate = channel_estimate.Scale(kUncertainSafetyMargin); 416 break; 417 case kChannelEstimateGood: 418 // Do nothing, estimate is accurate. 419 break; 420 } 421 bitrate_ramp_up_->Reset(new_estimate, back_down_bandwidth_, channel_estimate); 422 state_machine_->IncreaseBitrateDecision(); 423 paced_sender_->UpdateBandwidthEstimate(feedback_receive_time, new_estimate); 424 current_bandwidth_ = new_estimate; 425 DLOG(INFO) << "New bandwidth estimate after draining:" 426 << new_estimate.ToKBitsPerSecond() << " Kbits/s"; 427 } 428 429 void InterArrivalSender::EstimateBandwidthAfterDelayEvent( 430 QuicTime feedback_receive_time, 431 QuicTime::Delta estimated_congestion_delay) { 432 QuicByteCount estimated_byte_buildup = 433 current_bandwidth_.ToBytesPerPeriod(estimated_congestion_delay); 434 435 // To drain all build up buffer within one RTT we need to reduce the 436 // bitrate with the following. 437 // TODO(pwestin): this is a crude first implementation. 438 int64 draining_rate_per_rtt = (estimated_byte_buildup * 439 kNumMicrosPerSecond) / SmoothedRtt().ToMicroseconds(); 440 441 float decrease_factor = 442 draining_rate_per_rtt / current_bandwidth_.ToBytesPerSecond(); 443 444 decrease_factor = std::max(decrease_factor, kMinBitrateReduction); 445 decrease_factor = std::min(decrease_factor, kMaxBitrateReduction); 446 back_down_congestion_delay_ = estimated_congestion_delay; 447 QuicBandwidth new_target_bitrate = 448 current_bandwidth_.Scale(1.0f - decrease_factor); 449 450 // While in delay sensing mode send at least one packet per RTT. 451 QuicBandwidth min_delay_bitrate = 452 QuicBandwidth::FromBytesAndTimeDelta(kMaxPacketSize, SmoothedRtt()); 453 new_target_bitrate = std::max(new_target_bitrate, min_delay_bitrate); 454 455 ResetCurrentBandwidth(feedback_receive_time, new_target_bitrate); 456 457 DLOG(INFO) << "New bandwidth estimate after delay event:" 458 << current_bandwidth_.ToKBitsPerSecond() 459 << " Kbits/s min delay bitrate:" 460 << min_delay_bitrate.ToKBitsPerSecond() 461 << " Kbits/s RTT:" 462 << SmoothedRtt().ToMicroseconds() 463 << " us"; 464 } 465 466 void InterArrivalSender::EstimateBandwidthAfterLossEvent( 467 QuicTime feedback_receive_time) { 468 ResetCurrentBandwidth(feedback_receive_time, 469 current_bandwidth_.Scale(kPacketLossBitrateReduction)); 470 DLOG(INFO) << "New bandwidth estimate after loss event:" 471 << current_bandwidth_.ToKBitsPerSecond() 472 << " Kbits/s"; 473 } 474 475 void InterArrivalSender::ResetCurrentBandwidth(QuicTime feedback_receive_time, 476 QuicBandwidth new_rate) { 477 new_rate = std::max(new_rate, 478 QuicBandwidth::FromKBitsPerSecond(kMinBitrateKbit)); 479 QuicBandwidth channel_estimate = QuicBandwidth::Zero(); 480 ChannelEstimateState channel_estimator_state = 481 channel_estimator_->GetChannelEstimate(&channel_estimate); 482 483 switch (channel_estimator_state) { 484 case kChannelEstimateUnknown: 485 channel_estimate = current_bandwidth_; 486 break; 487 case kChannelEstimateUncertain: 488 channel_estimate = channel_estimate.Scale(kUncertainSafetyMargin); 489 break; 490 case kChannelEstimateGood: 491 // Do nothing. 492 break; 493 } 494 back_down_time_ = feedback_receive_time; 495 back_down_bandwidth_ = current_bandwidth_; 496 bitrate_ramp_up_->Reset(new_rate, current_bandwidth_, channel_estimate); 497 if (new_rate != current_bandwidth_) { 498 current_bandwidth_ = new_rate; 499 paced_sender_->UpdateBandwidthEstimate(feedback_receive_time, 500 current_bandwidth_); 501 state_machine_->DecreaseBitrateDecision(); 502 } 503 } 504 505 } // namespace net 506