src/net/quic/quic_sent_packet_manager.cc

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