1 // Copyright 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/quic_sent_packet_manager.h" 6 7 #include <algorithm> 8 9 #include "base/logging.h" 10 #include "base/stl_util.h" 11 #include "net/quic/congestion_control/pacing_sender.h" 12 #include "net/quic/crypto/crypto_protocol.h" 13 #include "net/quic/quic_ack_notifier_manager.h" 14 #include "net/quic/quic_connection_stats.h" 15 #include "net/quic/quic_flags.h" 16 #include "net/quic/quic_utils_chromium.h" 17 18 using std::make_pair; 19 using std::max; 20 using std::min; 21 22 namespace net { 23 24 // The length of the recent min rtt window in seconds. Windowing is disabled for 25 // values less than or equal to 0. 26 int32 FLAGS_quic_recent_min_rtt_window_s = 60; 27 28 namespace { 29 static const int kDefaultRetransmissionTimeMs = 500; 30 // TCP RFC calls for 1 second RTO however Linux differs from this default and 31 // define the minimum RTO to 200ms, we will use the same until we have data to 32 // support a higher or lower value. 33 static const int kMinRetransmissionTimeMs = 200; 34 static const int kMaxRetransmissionTimeMs = 60000; 35 static const size_t kMaxRetransmissions = 10; 36 37 // Only exponentially back off the handshake timer 5 times due to a timeout. 38 static const size_t kMaxHandshakeRetransmissionBackoffs = 5; 39 static const size_t kMinHandshakeTimeoutMs = 10; 40 41 // Sends up to two tail loss probes before firing an RTO, 42 // per draft RFC draft-dukkipati-tcpm-tcp-loss-probe. 43 static const size_t kDefaultMaxTailLossProbes = 2; 44 static const int64 kMinTailLossProbeTimeoutMs = 10; 45 46 // Number of samples before we force a new recent min rtt to be captured. 47 static const size_t kNumMinRttSamplesAfterQuiescence = 2; 48 49 // Number of unpaced packets to send after quiescence. 50 static const size_t kInitialUnpacedBurst = 10; 51 52 bool HasCryptoHandshake(const TransmissionInfo& transmission_info) { 53 if (transmission_info.retransmittable_frames == NULL) { 54 return false; 55 } 56 return transmission_info.retransmittable_frames->HasCryptoHandshake() == 57 IS_HANDSHAKE; 58 } 59 60 } // namespace 61 62 #define ENDPOINT (is_server_ ? "Server: " : " Client: ") 63 64 QuicSentPacketManager::QuicSentPacketManager( 65 bool is_server, 66 const QuicClock* clock, 67 QuicConnectionStats* stats, 68 CongestionControlType congestion_control_type, 69 LossDetectionType loss_type) 70 : unacked_packets_(), 71 is_server_(is_server), 72 clock_(clock), 73 stats_(stats), 74 debug_delegate_(NULL), 75 network_change_visitor_(NULL), 76 send_algorithm_(SendAlgorithmInterface::Create(clock, 77 &rtt_stats_, 78 congestion_control_type, 79 stats)), 80 loss_algorithm_(LossDetectionInterface::Create(loss_type)), 81 least_packet_awaited_by_peer_(1), 82 first_rto_transmission_(0), 83 consecutive_rto_count_(0), 84 consecutive_tlp_count_(0), 85 consecutive_crypto_retransmission_count_(0), 86 pending_timer_transmission_count_(0), 87 max_tail_loss_probes_(kDefaultMaxTailLossProbes), 88 using_pacing_(false), 89 handshake_confirmed_(false) { 90 } 91 92 QuicSentPacketManager::~QuicSentPacketManager() { 93 } 94 95 void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) { 96 if (config.HasReceivedInitialRoundTripTimeUs() && 97 config.ReceivedInitialRoundTripTimeUs() > 0) { 98 rtt_stats_.set_initial_rtt_us(min(kMaxInitialRoundTripTimeUs, 99 config.ReceivedInitialRoundTripTimeUs())); 100 } else if (config.HasInitialRoundTripTimeUsToSend()) { 101 rtt_stats_.set_initial_rtt_us( 102 min(kMaxInitialRoundTripTimeUs, 103 config.GetInitialRoundTripTimeUsToSend())); 104 } 105 // TODO(ianswett): BBR is currently a server only feature. 106 if (config.HasReceivedConnectionOptions() && 107 ContainsQuicTag(config.ReceivedConnectionOptions(), kTBBR)) { 108 if (FLAGS_quic_recent_min_rtt_window_s > 0) { 109 rtt_stats_.set_recent_min_rtt_window( 110 QuicTime::Delta::FromSeconds(FLAGS_quic_recent_min_rtt_window_s)); 111 } 112 send_algorithm_.reset( 113 SendAlgorithmInterface::Create(clock_, &rtt_stats_, kBBR, stats_)); 114 } 115 if (config.HasReceivedConnectionOptions() && 116 ContainsQuicTag(config.ReceivedConnectionOptions(), kRENO)) { 117 send_algorithm_.reset( 118 SendAlgorithmInterface::Create(clock_, &rtt_stats_, kReno, stats_)); 119 } 120 if (is_server_) { 121 if (config.HasReceivedConnectionOptions() && 122 ContainsQuicTag(config.ReceivedConnectionOptions(), kPACE)) { 123 EnablePacing(); 124 } 125 } else if (config.HasSendConnectionOptions() && 126 ContainsQuicTag(config.SendConnectionOptions(), kPACE)) { 127 EnablePacing(); 128 } 129 // TODO(ianswett): Remove the "HasReceivedLossDetection" branch once 130 // the ConnectionOptions code is live everywhere. 131 if ((config.HasReceivedLossDetection() && 132 config.ReceivedLossDetection() == kTIME) || 133 (config.HasReceivedConnectionOptions() && 134 ContainsQuicTag(config.ReceivedConnectionOptions(), kTIME))) { 135 loss_algorithm_.reset(LossDetectionInterface::Create(kTime)); 136 } 137 send_algorithm_->SetFromConfig(config, is_server_); 138 139 if (network_change_visitor_ != NULL) { 140 network_change_visitor_->OnCongestionWindowChange(GetCongestionWindow()); 141 } 142 } 143 144 // TODO(ianswett): Combine this method with OnPacketSent once packets are always 145 // sent in order and the connection tracks RetransmittableFrames for longer. 146 void QuicSentPacketManager::OnSerializedPacket( 147 const SerializedPacket& serialized_packet) { 148 if (serialized_packet.retransmittable_frames) { 149 ack_notifier_manager_.OnSerializedPacket(serialized_packet); 150 } 151 unacked_packets_.AddPacket(serialized_packet); 152 153 if (debug_delegate_ != NULL) { 154 debug_delegate_->OnSerializedPacket(serialized_packet); 155 } 156 } 157 158 void QuicSentPacketManager::OnRetransmittedPacket( 159 QuicPacketSequenceNumber old_sequence_number, 160 QuicPacketSequenceNumber new_sequence_number) { 161 TransmissionType transmission_type; 162 PendingRetransmissionMap::iterator it = 163 pending_retransmissions_.find(old_sequence_number); 164 if (it != pending_retransmissions_.end()) { 165 transmission_type = it->second; 166 pending_retransmissions_.erase(it); 167 } else { 168 DLOG(DFATAL) << "Expected sequence number to be in " 169 "pending_retransmissions_. sequence_number: " << old_sequence_number; 170 transmission_type = NOT_RETRANSMISSION; 171 } 172 173 // A notifier may be waiting to hear about ACKs for the original sequence 174 // number. Inform them that the sequence number has changed. 175 ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number, 176 new_sequence_number); 177 178 unacked_packets_.OnRetransmittedPacket(old_sequence_number, 179 new_sequence_number, 180 transmission_type); 181 182 if (debug_delegate_ != NULL) { 183 debug_delegate_->OnRetransmittedPacket(old_sequence_number, 184 new_sequence_number, 185 transmission_type, 186 clock_->ApproximateNow()); 187 } 188 } 189 190 void QuicSentPacketManager::OnIncomingAck(const QuicAckFrame& ack_frame, 191 QuicTime ack_receive_time) { 192 QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight(); 193 194 UpdatePacketInformationReceivedByPeer(ack_frame); 195 // We rely on delta_time_largest_observed to compute an RTT estimate, so 196 // we only update rtt when the largest observed gets acked. 197 bool largest_observed_acked = MaybeUpdateRTT(ack_frame, ack_receive_time); 198 DCHECK_GE(ack_frame.largest_observed, unacked_packets_.largest_observed()); 199 unacked_packets_.IncreaseLargestObserved(ack_frame.largest_observed); 200 201 HandleAckForSentPackets(ack_frame); 202 InvokeLossDetection(ack_receive_time); 203 MaybeInvokeCongestionEvent(largest_observed_acked, bytes_in_flight); 204 unacked_packets_.RemoveObsoletePackets(); 205 206 sustained_bandwidth_recorder_.RecordEstimate( 207 send_algorithm_->InRecovery(), 208 send_algorithm_->InSlowStart(), 209 send_algorithm_->BandwidthEstimate(), 210 ack_receive_time, 211 clock_->WallNow(), 212 rtt_stats_.SmoothedRtt()); 213 214 // If we have received a truncated ack, then we need to clear out some 215 // previous transmissions to allow the peer to actually ACK new packets. 216 if (ack_frame.is_truncated) { 217 unacked_packets_.ClearAllPreviousRetransmissions(); 218 } 219 220 // Anytime we are making forward progress and have a new RTT estimate, reset 221 // the backoff counters. 222 if (largest_observed_acked) { 223 // Reset all retransmit counters any time a new packet is acked. 224 consecutive_rto_count_ = 0; 225 consecutive_tlp_count_ = 0; 226 consecutive_crypto_retransmission_count_ = 0; 227 } 228 229 if (debug_delegate_ != NULL) { 230 debug_delegate_->OnIncomingAck(ack_frame, 231 ack_receive_time, 232 unacked_packets_.largest_observed(), 233 largest_observed_acked, 234 GetLeastUnacked()); 235 } 236 } 237 238 void QuicSentPacketManager::UpdatePacketInformationReceivedByPeer( 239 const QuicAckFrame& ack_frame) { 240 if (ack_frame.missing_packets.empty()) { 241 least_packet_awaited_by_peer_ = ack_frame.largest_observed + 1; 242 } else { 243 least_packet_awaited_by_peer_ = *(ack_frame.missing_packets.begin()); 244 } 245 } 246 247 void QuicSentPacketManager::MaybeInvokeCongestionEvent( 248 bool rtt_updated, QuicByteCount bytes_in_flight) { 249 if (!rtt_updated && packets_acked_.empty() && packets_lost_.empty()) { 250 return; 251 } 252 send_algorithm_->OnCongestionEvent(rtt_updated, bytes_in_flight, 253 packets_acked_, packets_lost_); 254 packets_acked_.clear(); 255 packets_lost_.clear(); 256 if (network_change_visitor_ != NULL) { 257 network_change_visitor_->OnCongestionWindowChange(GetCongestionWindow()); 258 } 259 } 260 261 void QuicSentPacketManager::HandleAckForSentPackets( 262 const QuicAckFrame& ack_frame) { 263 // Go through the packets we have not received an ack for and see if this 264 // incoming_ack shows they've been seen by the peer. 265 QuicTime::Delta delta_largest_observed = 266 ack_frame.delta_time_largest_observed; 267 QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); 268 for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); 269 it != unacked_packets_.end(); ++it, ++sequence_number) { 270 if (sequence_number > ack_frame.largest_observed) { 271 // These packets are still in flight. 272 break; 273 } 274 275 if (ContainsKey(ack_frame.missing_packets, sequence_number)) { 276 // Don't continue to increase the nack count for packets not in flight. 277 if (!it->in_flight) { 278 continue; 279 } 280 // Consider it multiple nacks when there is a gap between the missing 281 // packet and the largest observed, since the purpose of a nack 282 // threshold is to tolerate re-ordering. This handles both StretchAcks 283 // and Forward Acks. 284 // The nack count only increases when the largest observed increases. 285 size_t min_nacks = ack_frame.largest_observed - sequence_number; 286 // Truncated acks can nack the largest observed, so use a min of 1. 287 if (min_nacks == 0) { 288 min_nacks = 1; 289 } 290 unacked_packets_.NackPacket(sequence_number, min_nacks); 291 continue; 292 } 293 // Packet was acked, so remove it from our unacked packet list. 294 DVLOG(1) << ENDPOINT << "Got an ack for packet " << sequence_number; 295 // If data is associated with the most recent transmission of this 296 // packet, then inform the caller. 297 if (it->in_flight) { 298 packets_acked_.push_back(make_pair(sequence_number, *it)); 299 } 300 MarkPacketHandled(sequence_number, *it, delta_largest_observed); 301 } 302 303 // Discard any retransmittable frames associated with revived packets. 304 for (SequenceNumberSet::const_iterator revived_it = 305 ack_frame.revived_packets.begin(); 306 revived_it != ack_frame.revived_packets.end(); ++revived_it) { 307 MarkPacketRevived(*revived_it, delta_largest_observed); 308 } 309 } 310 311 bool QuicSentPacketManager::HasRetransmittableFrames( 312 QuicPacketSequenceNumber sequence_number) const { 313 return unacked_packets_.HasRetransmittableFrames(sequence_number); 314 } 315 316 void QuicSentPacketManager::RetransmitUnackedPackets( 317 TransmissionType retransmission_type) { 318 DCHECK(retransmission_type == ALL_UNACKED_RETRANSMISSION || 319 retransmission_type == ALL_INITIAL_RETRANSMISSION); 320 QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); 321 for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); 322 it != unacked_packets_.end(); ++it, ++sequence_number) { 323 const RetransmittableFrames* frames = it->retransmittable_frames; 324 if (frames != NULL && (retransmission_type == ALL_UNACKED_RETRANSMISSION || 325 frames->encryption_level() == ENCRYPTION_INITIAL)) { 326 MarkForRetransmission(sequence_number, retransmission_type); 327 } 328 } 329 } 330 331 void QuicSentPacketManager::NeuterUnencryptedPackets() { 332 QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); 333 for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); 334 it != unacked_packets_.end(); ++it, ++sequence_number) { 335 const RetransmittableFrames* frames = it->retransmittable_frames; 336 if (frames != NULL && frames->encryption_level() == ENCRYPTION_NONE) { 337 // Once you're forward secure, no unencrypted packets will be sent, crypto 338 // or otherwise. Unencrypted packets are neutered and abandoned, to ensure 339 // they are not retransmitted or considered lost from a congestion control 340 // perspective. 341 pending_retransmissions_.erase(sequence_number); 342 unacked_packets_.RemoveFromInFlight(sequence_number); 343 unacked_packets_.RemoveRetransmittability(sequence_number); 344 } 345 } 346 } 347 348 void QuicSentPacketManager::MarkForRetransmission( 349 QuicPacketSequenceNumber sequence_number, 350 TransmissionType transmission_type) { 351 const TransmissionInfo& transmission_info = 352 unacked_packets_.GetTransmissionInfo(sequence_number); 353 LOG_IF(DFATAL, transmission_info.retransmittable_frames == NULL); 354 if (transmission_type != TLP_RETRANSMISSION) { 355 unacked_packets_.RemoveFromInFlight(sequence_number); 356 } 357 // TODO(ianswett): Currently the RTO can fire while there are pending NACK 358 // retransmissions for the same data, which is not ideal. 359 if (ContainsKey(pending_retransmissions_, sequence_number)) { 360 return; 361 } 362 363 pending_retransmissions_[sequence_number] = transmission_type; 364 } 365 366 void QuicSentPacketManager::RecordSpuriousRetransmissions( 367 const SequenceNumberList& all_transmissions, 368 QuicPacketSequenceNumber acked_sequence_number) { 369 if (acked_sequence_number < first_rto_transmission_) { 370 // Cancel all pending RTO transmissions and restore their in flight status. 371 // Replace SRTT with latest_rtt and increase the variance to prevent 372 // a spurious RTO from happening again. 373 rtt_stats_.ExpireSmoothedMetrics(); 374 for (PendingRetransmissionMap::const_iterator it = 375 pending_retransmissions_.begin(); 376 it != pending_retransmissions_.end(); ++it) { 377 DCHECK_EQ(it->second, RTO_RETRANSMISSION); 378 unacked_packets_.RestoreInFlight(it->first); 379 } 380 pending_retransmissions_.clear(); 381 send_algorithm_->RevertRetransmissionTimeout(); 382 first_rto_transmission_ = 0; 383 ++stats_->spurious_rto_count; 384 } 385 for (SequenceNumberList::const_reverse_iterator it = 386 all_transmissions.rbegin(); 387 it != all_transmissions.rend() && *it > acked_sequence_number; ++it) { 388 const TransmissionInfo& retransmit_info = 389 unacked_packets_.GetTransmissionInfo(*it); 390 391 stats_->bytes_spuriously_retransmitted += retransmit_info.bytes_sent; 392 ++stats_->packets_spuriously_retransmitted; 393 if (debug_delegate_ != NULL) { 394 debug_delegate_->OnSpuriousPacketRetransmition( 395 retransmit_info.transmission_type, 396 retransmit_info.bytes_sent); 397 } 398 } 399 } 400 401 bool QuicSentPacketManager::HasPendingRetransmissions() const { 402 return !pending_retransmissions_.empty(); 403 } 404 405 QuicSentPacketManager::PendingRetransmission 406 QuicSentPacketManager::NextPendingRetransmission() { 407 DCHECK(!pending_retransmissions_.empty()); 408 QuicPacketSequenceNumber sequence_number = 409 pending_retransmissions_.begin()->first; 410 TransmissionType transmission_type = pending_retransmissions_.begin()->second; 411 if (unacked_packets_.HasPendingCryptoPackets()) { 412 // Ensure crypto packets are retransmitted before other packets. 413 PendingRetransmissionMap::const_iterator it = 414 pending_retransmissions_.begin(); 415 do { 416 if (HasCryptoHandshake(unacked_packets_.GetTransmissionInfo(it->first))) { 417 sequence_number = it->first; 418 transmission_type = it->second; 419 break; 420 } 421 ++it; 422 } while (it != pending_retransmissions_.end()); 423 } 424 DCHECK(unacked_packets_.IsUnacked(sequence_number)) << sequence_number; 425 const TransmissionInfo& transmission_info = 426 unacked_packets_.GetTransmissionInfo(sequence_number); 427 DCHECK(transmission_info.retransmittable_frames); 428 429 return PendingRetransmission(sequence_number, 430 transmission_type, 431 *transmission_info.retransmittable_frames, 432 transmission_info.sequence_number_length); 433 } 434 435 void QuicSentPacketManager::MarkPacketRevived( 436 QuicPacketSequenceNumber sequence_number, 437 QuicTime::Delta delta_largest_observed) { 438 if (!unacked_packets_.IsUnacked(sequence_number)) { 439 return; 440 } 441 442 const TransmissionInfo& transmission_info = 443 unacked_packets_.GetTransmissionInfo(sequence_number); 444 QuicPacketSequenceNumber newest_transmission = 445 transmission_info.all_transmissions == NULL ? 446 sequence_number : *transmission_info.all_transmissions->rbegin(); 447 // This packet has been revived at the receiver. If we were going to 448 // retransmit it, do not retransmit it anymore. 449 pending_retransmissions_.erase(newest_transmission); 450 451 // The AckNotifierManager needs to be notified for revived packets, 452 // since it indicates the packet arrived from the appliction's perspective. 453 if (transmission_info.retransmittable_frames) { 454 ack_notifier_manager_.OnPacketAcked( 455 newest_transmission, delta_largest_observed); 456 } 457 458 unacked_packets_.RemoveRetransmittability(sequence_number); 459 } 460 461 void QuicSentPacketManager::MarkPacketHandled( 462 QuicPacketSequenceNumber sequence_number, 463 const TransmissionInfo& info, 464 QuicTime::Delta delta_largest_observed) { 465 QuicPacketSequenceNumber newest_transmission = 466 info.all_transmissions == NULL ? 467 sequence_number : *info.all_transmissions->rbegin(); 468 // Remove the most recent packet, if it is pending retransmission. 469 pending_retransmissions_.erase(newest_transmission); 470 471 // The AckNotifierManager needs to be notified about the most recent 472 // transmission, since that's the one only one it tracks. 473 ack_notifier_manager_.OnPacketAcked(newest_transmission, 474 delta_largest_observed); 475 if (newest_transmission != sequence_number) { 476 RecordSpuriousRetransmissions(*info.all_transmissions, sequence_number); 477 // Remove the most recent packet from flight if it's a crypto handshake 478 // packet, since they won't be acked now that one has been processed. 479 // Other crypto handshake packets won't be in flight, only the newest 480 // transmission of a crypto packet is in flight at once. 481 // TODO(ianswett): Instead of handling all crypto packets special, 482 // only handle NULL encrypted packets in a special way. 483 if (HasCryptoHandshake( 484 unacked_packets_.GetTransmissionInfo(newest_transmission))) { 485 unacked_packets_.RemoveFromInFlight(newest_transmission); 486 } 487 } 488 489 unacked_packets_.RemoveFromInFlight(sequence_number); 490 unacked_packets_.RemoveRetransmittability(sequence_number); 491 } 492 493 bool QuicSentPacketManager::IsUnacked( 494 QuicPacketSequenceNumber sequence_number) const { 495 return unacked_packets_.IsUnacked(sequence_number); 496 } 497 498 bool QuicSentPacketManager::HasUnackedPackets() const { 499 return unacked_packets_.HasUnackedPackets(); 500 } 501 502 QuicPacketSequenceNumber 503 QuicSentPacketManager::GetLeastUnacked() const { 504 return unacked_packets_.GetLeastUnacked(); 505 } 506 507 bool QuicSentPacketManager::OnPacketSent( 508 QuicPacketSequenceNumber sequence_number, 509 QuicTime sent_time, 510 QuicByteCount bytes, 511 TransmissionType transmission_type, 512 HasRetransmittableData has_retransmittable_data) { 513 DCHECK_LT(0u, sequence_number); 514 DCHECK(unacked_packets_.IsUnacked(sequence_number)); 515 LOG_IF(DFATAL, bytes == 0) << "Cannot send empty packets."; 516 if (pending_timer_transmission_count_ > 0) { 517 --pending_timer_transmission_count_; 518 } 519 520 if (unacked_packets_.bytes_in_flight() == 0) { 521 // TODO(ianswett): Consider being less aggressive to force a new 522 // recent_min_rtt, likely by not discarding a relatively new sample. 523 DVLOG(1) << "Sampling a new recent min rtt within 2 samples. currently:" 524 << rtt_stats_.recent_min_rtt().ToMilliseconds() << "ms"; 525 rtt_stats_.SampleNewRecentMinRtt(kNumMinRttSamplesAfterQuiescence); 526 } 527 528 // Only track packets as in flight that the send algorithm wants us to track. 529 const bool in_flight = 530 send_algorithm_->OnPacketSent(sent_time, 531 unacked_packets_.bytes_in_flight(), 532 sequence_number, 533 bytes, 534 has_retransmittable_data); 535 unacked_packets_.SetSent(sequence_number, sent_time, bytes, in_flight); 536 537 if (debug_delegate_ != NULL) { 538 debug_delegate_->OnSentPacket( 539 sequence_number, sent_time, bytes, transmission_type); 540 } 541 542 // Reset the retransmission timer anytime a pending packet is sent. 543 return in_flight; 544 } 545 546 void QuicSentPacketManager::OnRetransmissionTimeout() { 547 DCHECK(unacked_packets_.HasInFlightPackets()); 548 DCHECK_EQ(0u, pending_timer_transmission_count_); 549 // Handshake retransmission, timer based loss detection, TLP, and RTO are 550 // implemented with a single alarm. The handshake alarm is set when the 551 // handshake has not completed, the loss alarm is set when the loss detection 552 // algorithm says to, and the TLP and RTO alarms are set after that. 553 // The TLP alarm is always set to run for under an RTO. 554 switch (GetRetransmissionMode()) { 555 case HANDSHAKE_MODE: 556 ++stats_->crypto_retransmit_count; 557 RetransmitCryptoPackets(); 558 return; 559 case LOSS_MODE: { 560 ++stats_->loss_timeout_count; 561 QuicByteCount bytes_in_flight = unacked_packets_.bytes_in_flight(); 562 InvokeLossDetection(clock_->Now()); 563 MaybeInvokeCongestionEvent(false, bytes_in_flight); 564 return; 565 } 566 case TLP_MODE: 567 // If no tail loss probe can be sent, because there are no retransmittable 568 // packets, execute a conventional RTO to abandon old packets. 569 ++stats_->tlp_count; 570 ++consecutive_tlp_count_; 571 pending_timer_transmission_count_ = 1; 572 // TLPs prefer sending new data instead of retransmitting data, so 573 // give the connection a chance to write before completing the TLP. 574 return; 575 case RTO_MODE: 576 ++stats_->rto_count; 577 RetransmitAllPackets(); 578 return; 579 } 580 } 581 582 void QuicSentPacketManager::RetransmitCryptoPackets() { 583 DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode()); 584 // TODO(ianswett): Typical TCP implementations only retransmit 5 times. 585 consecutive_crypto_retransmission_count_ = 586 min(kMaxHandshakeRetransmissionBackoffs, 587 consecutive_crypto_retransmission_count_ + 1); 588 bool packet_retransmitted = false; 589 QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); 590 for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); 591 it != unacked_packets_.end(); ++it, ++sequence_number) { 592 // Only retransmit frames which are in flight, and therefore have been sent. 593 if (!it->in_flight || it->retransmittable_frames == NULL || 594 it->retransmittable_frames->HasCryptoHandshake() != IS_HANDSHAKE) { 595 continue; 596 } 597 packet_retransmitted = true; 598 MarkForRetransmission(sequence_number, HANDSHAKE_RETRANSMISSION); 599 ++pending_timer_transmission_count_; 600 } 601 DCHECK(packet_retransmitted) << "No crypto packets found to retransmit."; 602 } 603 604 bool QuicSentPacketManager::MaybeRetransmitTailLossProbe() { 605 if (pending_timer_transmission_count_ == 0) { 606 return false; 607 } 608 QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); 609 for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); 610 it != unacked_packets_.end(); ++it, ++sequence_number) { 611 // Only retransmit frames which are in flight, and therefore have been sent. 612 if (!it->in_flight || it->retransmittable_frames == NULL) { 613 continue; 614 } 615 if (!handshake_confirmed_) { 616 DCHECK_NE(IS_HANDSHAKE, it->retransmittable_frames->HasCryptoHandshake()); 617 } 618 MarkForRetransmission(sequence_number, TLP_RETRANSMISSION); 619 return true; 620 } 621 DLOG(FATAL) 622 << "No retransmittable packets, so RetransmitOldestPacket failed."; 623 return false; 624 } 625 626 void QuicSentPacketManager::RetransmitAllPackets() { 627 DVLOG(1) << "RetransmitAllPackets() called with " 628 << unacked_packets_.GetNumUnackedPacketsDebugOnly() 629 << " unacked packets."; 630 // Request retransmission of all retransmittable packets when the RTO 631 // fires, and let the congestion manager decide how many to send 632 // immediately and the remaining packets will be queued. 633 // Abandon any non-retransmittable packets that are sufficiently old. 634 bool packets_retransmitted = false; 635 QuicPacketSequenceNumber sequence_number = unacked_packets_.GetLeastUnacked(); 636 for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin(); 637 it != unacked_packets_.end(); ++it, ++sequence_number) { 638 if (it->retransmittable_frames != NULL) { 639 packets_retransmitted = true; 640 MarkForRetransmission(sequence_number, RTO_RETRANSMISSION); 641 } else { 642 unacked_packets_.RemoveFromInFlight(sequence_number); 643 } 644 } 645 646 send_algorithm_->OnRetransmissionTimeout(packets_retransmitted); 647 if (packets_retransmitted) { 648 if (consecutive_rto_count_ == 0) { 649 first_rto_transmission_ = unacked_packets_.largest_sent_packet() + 1; 650 } 651 ++consecutive_rto_count_; 652 } 653 654 if (network_change_visitor_ != NULL) { 655 network_change_visitor_->OnCongestionWindowChange(GetCongestionWindow()); 656 } 657 } 658 659 QuicSentPacketManager::RetransmissionTimeoutMode 660 QuicSentPacketManager::GetRetransmissionMode() const { 661 DCHECK(unacked_packets_.HasInFlightPackets()); 662 if (!handshake_confirmed_ && unacked_packets_.HasPendingCryptoPackets()) { 663 return HANDSHAKE_MODE; 664 } 665 if (loss_algorithm_->GetLossTimeout() != QuicTime::Zero()) { 666 return LOSS_MODE; 667 } 668 if (consecutive_tlp_count_ < max_tail_loss_probes_) { 669 if (unacked_packets_.HasUnackedRetransmittableFrames()) { 670 return TLP_MODE; 671 } 672 } 673 return RTO_MODE; 674 } 675 676 void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame( 677 const QuicCongestionFeedbackFrame& frame, 678 const QuicTime& feedback_receive_time) { 679 send_algorithm_->OnIncomingQuicCongestionFeedbackFrame( 680 frame, feedback_receive_time); 681 } 682 683 void QuicSentPacketManager::InvokeLossDetection(QuicTime time) { 684 SequenceNumberSet lost_packets = 685 loss_algorithm_->DetectLostPackets(unacked_packets_, 686 time, 687 unacked_packets_.largest_observed(), 688 rtt_stats_); 689 for (SequenceNumberSet::const_iterator it = lost_packets.begin(); 690 it != lost_packets.end(); ++it) { 691 QuicPacketSequenceNumber sequence_number = *it; 692 const TransmissionInfo& transmission_info = 693 unacked_packets_.GetTransmissionInfo(sequence_number); 694 // TODO(ianswett): If it's expected the FEC packet may repair the loss, it 695 // should be recorded as a loss to the send algorithm, but not retransmitted 696 // until it's known whether the FEC packet arrived. 697 ++stats_->packets_lost; 698 packets_lost_.push_back(make_pair(sequence_number, transmission_info)); 699 DVLOG(1) << ENDPOINT << "Lost packet " << sequence_number; 700 701 if (transmission_info.retransmittable_frames != NULL) { 702 MarkForRetransmission(sequence_number, LOSS_RETRANSMISSION); 703 } else { 704 // Since we will not retransmit this, we need to remove it from 705 // unacked_packets_. This is either the current transmission of 706 // a packet whose previous transmission has been acked, a packet that has 707 // been TLP retransmitted, or an FEC packet. 708 unacked_packets_.RemoveFromInFlight(sequence_number); 709 } 710 } 711 } 712 713 bool QuicSentPacketManager::MaybeUpdateRTT( 714 const QuicAckFrame& ack_frame, 715 const QuicTime& ack_receive_time) { 716 if (!unacked_packets_.IsUnacked(ack_frame.largest_observed)) { 717 return false; 718 } 719 // We calculate the RTT based on the highest ACKed sequence number, the lower 720 // sequence numbers will include the ACK aggregation delay. 721 const TransmissionInfo& transmission_info = 722 unacked_packets_.GetTransmissionInfo(ack_frame.largest_observed); 723 // Ensure the packet has a valid sent time. 724 if (transmission_info.sent_time == QuicTime::Zero()) { 725 LOG(DFATAL) << "Acked packet has zero sent time, largest_observed:" 726 << ack_frame.largest_observed; 727 return false; 728 } 729 730 QuicTime::Delta send_delta = 731 ack_receive_time.Subtract(transmission_info.sent_time); 732 rtt_stats_.UpdateRtt( 733 send_delta, ack_frame.delta_time_largest_observed, ack_receive_time); 734 return true; 735 } 736 737 QuicTime::Delta QuicSentPacketManager::TimeUntilSend( 738 QuicTime now, 739 HasRetransmittableData retransmittable) { 740 // The TLP logic is entirely contained within QuicSentPacketManager, so the 741 // send algorithm does not need to be consulted. 742 if (pending_timer_transmission_count_ > 0) { 743 return QuicTime::Delta::Zero(); 744 } 745 return send_algorithm_->TimeUntilSend( 746 now, unacked_packets_.bytes_in_flight(), retransmittable); 747 } 748 749 // Uses a 25ms delayed ack timer. Also helps with better signaling 750 // in low-bandwidth (< ~384 kbps), where an ack is sent per packet. 751 // Ensures that the Delayed Ack timer is always set to a value lesser 752 // than the retransmission timer's minimum value (MinRTO). We want the 753 // delayed ack to get back to the QUIC peer before the sender's 754 // retransmission timer triggers. Since we do not know the 755 // reverse-path one-way delay, we assume equal delays for forward and 756 // reverse paths, and ensure that the timer is set to less than half 757 // of the MinRTO. 758 // There may be a value in making this delay adaptive with the help of 759 // the sender and a signaling mechanism -- if the sender uses a 760 // different MinRTO, we may get spurious retransmissions. May not have 761 // any benefits, but if the delayed ack becomes a significant source 762 // of (likely, tail) latency, then consider such a mechanism. 763 const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const { 764 return QuicTime::Delta::FromMilliseconds(min(kMaxDelayedAckTimeMs, 765 kMinRetransmissionTimeMs/2)); 766 } 767 768 const QuicTime QuicSentPacketManager::GetRetransmissionTime() const { 769 // Don't set the timer if there are no packets in flight or we've already 770 // queued a tlp transmission and it hasn't been sent yet. 771 if (!unacked_packets_.HasInFlightPackets() || 772 pending_timer_transmission_count_ > 0) { 773 return QuicTime::Zero(); 774 } 775 switch (GetRetransmissionMode()) { 776 case HANDSHAKE_MODE: 777 return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay()); 778 case LOSS_MODE: 779 return loss_algorithm_->GetLossTimeout(); 780 case TLP_MODE: { 781 // TODO(ianswett): When CWND is available, it would be preferable to 782 // set the timer based on the earliest retransmittable packet. 783 // Base the updated timer on the send time of the last packet. 784 const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime(); 785 const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay()); 786 // Ensure the TLP timer never gets set to a time in the past. 787 return QuicTime::Max(clock_->ApproximateNow(), tlp_time); 788 } 789 case RTO_MODE: { 790 // The RTO is based on the first outstanding packet. 791 const QuicTime sent_time = 792 unacked_packets_.GetFirstInFlightPacketSentTime(); 793 QuicTime rto_time = sent_time.Add(GetRetransmissionDelay()); 794 // Wait for TLP packets to be acked before an RTO fires. 795 QuicTime tlp_time = 796 unacked_packets_.GetLastPacketSentTime().Add(GetTailLossProbeDelay()); 797 return QuicTime::Max(tlp_time, rto_time); 798 } 799 } 800 DCHECK(false); 801 return QuicTime::Zero(); 802 } 803 804 const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay() 805 const { 806 // This is equivalent to the TailLossProbeDelay, but slightly more aggressive 807 // because crypto handshake messages don't incur a delayed ack time. 808 int64 delay_ms = max<int64>(kMinHandshakeTimeoutMs, 809 1.5 * rtt_stats_.SmoothedRtt().ToMilliseconds()); 810 return QuicTime::Delta::FromMilliseconds( 811 delay_ms << consecutive_crypto_retransmission_count_); 812 } 813 814 const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const { 815 QuicTime::Delta srtt = rtt_stats_.SmoothedRtt(); 816 if (!unacked_packets_.HasMultipleInFlightPackets()) { 817 return QuicTime::Delta::Max( 818 srtt.Multiply(2), srtt.Multiply(1.5) 819 .Add(QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2))); 820 } 821 return QuicTime::Delta::FromMilliseconds( 822 max(kMinTailLossProbeTimeoutMs, 823 static_cast<int64>(2 * srtt.ToMilliseconds()))); 824 } 825 826 const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const { 827 QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay(); 828 // TODO(rch): This code should move to |send_algorithm_|. 829 if (retransmission_delay.IsZero()) { 830 // We are in the initial state, use default timeout values. 831 retransmission_delay = 832 QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs); 833 } else if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) { 834 retransmission_delay = 835 QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs); 836 } 837 838 // Calculate exponential back off. 839 retransmission_delay = retransmission_delay.Multiply( 840 1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions)); 841 842 if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) { 843 return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs); 844 } 845 return retransmission_delay; 846 } 847 848 const RttStats* QuicSentPacketManager::GetRttStats() const { 849 return &rtt_stats_; 850 } 851 852 QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const { 853 return send_algorithm_->BandwidthEstimate(); 854 } 855 856 bool QuicSentPacketManager::HasReliableBandwidthEstimate() const { 857 return send_algorithm_->HasReliableBandwidthEstimate(); 858 } 859 860 const QuicSustainedBandwidthRecorder& 861 QuicSentPacketManager::SustainedBandwidthRecorder() const { 862 return sustained_bandwidth_recorder_; 863 } 864 865 QuicByteCount QuicSentPacketManager::GetCongestionWindow() const { 866 return send_algorithm_->GetCongestionWindow(); 867 } 868 869 QuicByteCount QuicSentPacketManager::GetSlowStartThreshold() const { 870 return send_algorithm_->GetSlowStartThreshold(); 871 } 872 873 void QuicSentPacketManager::EnablePacing() { 874 if (using_pacing_) { 875 return; 876 } 877 878 // Set up a pacing sender with a 5 millisecond alarm granularity. 879 using_pacing_ = true; 880 send_algorithm_.reset( 881 new PacingSender(send_algorithm_.release(), 882 QuicTime::Delta::FromMilliseconds(5), 883 kInitialUnpacedBurst)); 884 } 885 886 } // namespace net 887
