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_utils_chromium.h"
  16
  17 using std::make_pair;
  18 using std::max;
  19 using std::min;
  20
  21 // TODO(rtenneti): Remove this.
  22 // Do not flip this flag until the flakiness of the
  23 // net/tools/quic/end_to_end_test is fixed.
  24 // If true, then QUIC connections will track the retransmission history of a
  25 // packet so that an ack of a previous transmission will ack the data of all
  26 // other transmissions.
  27 bool FLAGS_track_retransmission_history = false;
  28
  29 // Do not remove this flag until the Finch-trials described in b/11706275
  30 // are complete.
  31 // If true, QUIC connections will support the use of a pacing algorithm when
  32 // sending packets, in an attempt to reduce packet loss.  The client must also
  33 // request pacing for the server to enable it.
  34 bool FLAGS_enable_quic_pacing = true;
  35
  36 namespace net {
  37 namespace {
  38 static const int kDefaultRetransmissionTimeMs = 500;
  39 // TCP RFC calls for 1 second RTO however Linux differs from this default and
  40 // define the minimum RTO to 200ms, we will use the same until we have data to
  41 // support a higher or lower value.
  42 static const int kMinRetransmissionTimeMs = 200;
  43 static const int kMaxRetransmissionTimeMs = 60000;
  44 static const size_t kMaxRetransmissions = 10;
  45
  46 // Only exponentially back off the handshake timer 5 times due to a timeout.
  47 static const size_t kMaxHandshakeRetransmissionBackoffs = 5;
  48 static const size_t kMinHandshakeTimeoutMs = 10;
  49
  50 // Sends up to two tail loss probes before firing an RTO,
  51 // per draft RFC draft-dukkipati-tcpm-tcp-loss-probe.
  52 static const size_t kDefaultMaxTailLossProbes = 2;
  53 static const int64 kMinTailLossProbeTimeoutMs = 10;
  54
  55 bool HasCryptoHandshake(
  56     const QuicUnackedPacketMap::TransmissionInfo& transmission_info) {
  57   if (transmission_info.retransmittable_frames == NULL) {
  58     return false;
  59   }
  60   return transmission_info.retransmittable_frames->HasCryptoHandshake() ==
  61       IS_HANDSHAKE;
  62 }
  63
  64 }  // namespace
  65
  66 #define ENDPOINT (is_server_ ? "Server: " : " Client: ")
  67
  68 QuicSentPacketManager::QuicSentPacketManager(bool is_server,
  69                                              const QuicClock* clock,
  70                                              QuicConnectionStats* stats,
  71                                              CongestionFeedbackType type)
  72     : unacked_packets_(),
  73       is_server_(is_server),
  74       clock_(clock),
  75       stats_(stats),
  76       send_algorithm_(
  77           SendAlgorithmInterface::Create(clock, &rtt_stats_, type, stats)),
  78       loss_algorithm_(LossDetectionInterface::Create()),
  79       largest_observed_(0),
  80       consecutive_rto_count_(0),
  81       consecutive_tlp_count_(0),
  82       consecutive_crypto_retransmission_count_(0),
  83       max_tail_loss_probes_(kDefaultMaxTailLossProbes),
  84       using_pacing_(false) {
  85 }
  86
  87 QuicSentPacketManager::~QuicSentPacketManager() {
  88 }
  89
  90 void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
  91   if (config.initial_round_trip_time_us() > 0) {
  92     // The initial rtt should already be set on the client side.
  93     DVLOG_IF(1, !is_server_)
  94         << "Client did not set an initial RTT, but did negotiate one.";
  95     rtt_stats_.set_initial_rtt_us(config.initial_round_trip_time_us());
  96   }
  97   if (config.congestion_control() == kPACE) {
  98     MaybeEnablePacing();
  99   }
 100   send_algorithm_->SetFromConfig(config, is_server_);
 101 }
 102
 103 // TODO(ianswett): Combine this method with OnPacketSent once packets are always
 104 // sent in order and the connection tracks RetransmittableFrames for longer.
 105 void QuicSentPacketManager::OnSerializedPacket(
 106     const SerializedPacket& serialized_packet) {
 107   if (serialized_packet.retransmittable_frames) {
 108     ack_notifier_manager_.OnSerializedPacket(serialized_packet);
 109   }
 110
 111   unacked_packets_.AddPacket(serialized_packet);
 112 }
 113
 114 void QuicSentPacketManager::OnRetransmittedPacket(
 115     QuicPacketSequenceNumber old_sequence_number,
 116     QuicPacketSequenceNumber new_sequence_number) {
 117   DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number));
 118
 119   pending_retransmissions_.erase(old_sequence_number);
 120
 121   // A notifier may be waiting to hear about ACKs for the original sequence
 122   // number. Inform them that the sequence number has changed.
 123   ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number,
 124                                              new_sequence_number);
 125
 126   unacked_packets_.OnRetransmittedPacket(old_sequence_number,
 127                                          new_sequence_number);
 128 }
 129
 130 bool QuicSentPacketManager::OnIncomingAck(
 131     const ReceivedPacketInfo& received_info, QuicTime ack_receive_time) {
 132   // We rely on delta_time_largest_observed to compute an RTT estimate, so
 133   // we only update rtt when the largest observed gets acked.
 134   bool largest_observed_acked =
 135       unacked_packets_.IsUnacked(received_info.largest_observed);
 136   largest_observed_ = received_info.largest_observed;
 137   MaybeUpdateRTT(received_info, ack_receive_time);
 138   HandleAckForSentPackets(received_info);
 139   MaybeRetransmitOnAckFrame(received_info, ack_receive_time);
 140
 141   // Anytime we are making forward progress and have a new RTT estimate, reset
 142   // the backoff counters.
 143   if (largest_observed_acked) {
 144     // Reset all retransmit counters any time a new packet is acked.
 145     consecutive_rto_count_ = 0;
 146     consecutive_tlp_count_ = 0;
 147     consecutive_crypto_retransmission_count_ = 0;
 148   }
 149
 150   // Always reset the retransmission alarm when an ack comes in, since we now
 151   // have a better estimate of the current rtt than when it was set.
 152   return true;
 153 }
 154
 155 void QuicSentPacketManager::DiscardUnackedPacket(
 156     QuicPacketSequenceNumber sequence_number) {
 157   MarkPacketHandled(sequence_number, NOT_RECEIVED_BY_PEER);
 158 }
 159
 160 void QuicSentPacketManager::HandleAckForSentPackets(
 161     const ReceivedPacketInfo& received_info) {
 162   // Go through the packets we have not received an ack for and see if this
 163   // incoming_ack shows they've been seen by the peer.
 164   QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 165   while (it != unacked_packets_.end()) {
 166     QuicPacketSequenceNumber sequence_number = it->first;
 167     if (sequence_number > received_info.largest_observed) {
 168       // These are very new sequence_numbers.
 169       break;
 170     }
 171
 172     if (IsAwaitingPacket(received_info, sequence_number)) {
 173       ++it;
 174       continue;
 175     }
 176
 177     // Packet was acked, so remove it from our unacked packet list.
 178     DVLOG(1) << ENDPOINT <<"Got an ack for packet " << sequence_number;
 179     // If data is associated with the most recent transmission of this
 180     // packet, then inform the caller.
 181     it = MarkPacketHandled(sequence_number, RECEIVED_BY_PEER);
 182   }
 183
 184   // Discard any retransmittable frames associated with revived packets.
 185   for (SequenceNumberSet::const_iterator revived_it =
 186            received_info.revived_packets.begin();
 187        revived_it != received_info.revived_packets.end(); ++revived_it) {
 188     if (unacked_packets_.IsUnacked(*revived_it)) {
 189       if (!unacked_packets_.IsPending(*revived_it)) {
 190         unacked_packets_.RemovePacket(*revived_it);
 191       } else {
 192         unacked_packets_.NeuterPacket(*revived_it);
 193       }
 194     }
 195   }
 196
 197   // If we have received a truncated ack, then we need to
 198   // clear out some previous transmissions to allow the peer
 199   // to actually ACK new packets.
 200   if (received_info.is_truncated) {
 201     unacked_packets_.ClearPreviousRetransmissions(
 202         received_info.missing_packets.size() / 2);
 203   }
 204 }
 205
 206 bool QuicSentPacketManager::HasRetransmittableFrames(
 207     QuicPacketSequenceNumber sequence_number) const {
 208   return unacked_packets_.HasRetransmittableFrames(sequence_number);
 209 }
 210
 211 void QuicSentPacketManager::RetransmitUnackedPackets(
 212     RetransmissionType retransmission_type) {
 213   QuicUnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
 214   while (unacked_it != unacked_packets_.end()) {
 215     const RetransmittableFrames* frames =
 216         unacked_it->second.retransmittable_frames;
 217     // Only mark it as handled if it can't be retransmitted and there are no
 218     // pending retransmissions which would be cleared.
 219     if (frames == NULL && unacked_it->second.all_transmissions->size() == 1 &&
 220         retransmission_type == ALL_PACKETS) {
 221       unacked_it = MarkPacketHandled(unacked_it->first, NOT_RECEIVED_BY_PEER);
 222       continue;
 223     }
 224     // If it had no other transmissions, we handle it above.  If it has
 225     // other transmissions, one of them must have retransmittable frames,
 226     // so that gets resolved the same way as other retransmissions.
 227     // TODO(ianswett): Consider adding a new retransmission type which removes
 228     // all these old packets from unacked and retransmits them as new sequence
 229     // numbers with no connection to the previous ones.
 230     if (frames != NULL && (retransmission_type == ALL_PACKETS ||
 231                            frames->encryption_level() == ENCRYPTION_INITIAL)) {
 232       OnPacketAbandoned(unacked_it->first);
 233       MarkForRetransmission(unacked_it->first, ALL_UNACKED_RETRANSMISSION);
 234     }
 235     ++unacked_it;
 236   }
 237 }
 238
 239 void QuicSentPacketManager::MarkForRetransmission(
 240     QuicPacketSequenceNumber sequence_number,
 241     TransmissionType transmission_type) {
 242   const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 243       unacked_packets_.GetTransmissionInfo(sequence_number);
 244   LOG_IF(DFATAL, transmission_info.retransmittable_frames == NULL);
 245   LOG_IF(DFATAL, transmission_info.sent_time == QuicTime::Zero());
 246   // TODO(ianswett): Currently the RTO can fire while there are pending NACK
 247   // retransmissions for the same data, which is not ideal.
 248   if (ContainsKey(pending_retransmissions_, sequence_number)) {
 249     return;
 250   }
 251
 252   pending_retransmissions_[sequence_number] = transmission_type;
 253 }
 254
 255 bool QuicSentPacketManager::HasPendingRetransmissions() const {
 256   return !pending_retransmissions_.empty();
 257 }
 258
 259 QuicSentPacketManager::PendingRetransmission
 260     QuicSentPacketManager::NextPendingRetransmission() {
 261   DCHECK(!pending_retransmissions_.empty());
 262   QuicPacketSequenceNumber sequence_number =
 263       pending_retransmissions_.begin()->first;
 264   DCHECK(unacked_packets_.IsUnacked(sequence_number));
 265   const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 266       unacked_packets_.GetTransmissionInfo(sequence_number);
 267   DCHECK(transmission_info.retransmittable_frames);
 268
 269   return PendingRetransmission(sequence_number,
 270                                pending_retransmissions_.begin()->second,
 271                                *transmission_info.retransmittable_frames,
 272                                transmission_info.sequence_number_length);
 273 }
 274
 275 QuicUnackedPacketMap::const_iterator
 276 QuicSentPacketManager::MarkPacketHandled(
 277     QuicPacketSequenceNumber sequence_number,
 278     ReceivedByPeer received_by_peer) {
 279   if (!unacked_packets_.IsUnacked(sequence_number)) {
 280     LOG(DFATAL) << "Packet is not unacked: " << sequence_number;
 281     return unacked_packets_.end();
 282   }
 283   const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 284       unacked_packets_.GetTransmissionInfo(sequence_number);
 285   // If this packet is pending, remove it and inform the send algorithm.
 286   if (transmission_info.pending) {
 287     if (received_by_peer == RECEIVED_BY_PEER) {
 288       send_algorithm_->OnPacketAcked(sequence_number,
 289                                      transmission_info.bytes_sent);
 290     } else {
 291       // It's been abandoned.
 292       send_algorithm_->OnPacketAbandoned(sequence_number,
 293                                          transmission_info.bytes_sent);
 294     }
 295     unacked_packets_.SetNotPending(sequence_number);
 296   }
 297
 298   SequenceNumberSet all_transmissions = *transmission_info.all_transmissions;
 299   SequenceNumberSet::reverse_iterator all_transmissions_it =
 300       all_transmissions.rbegin();
 301   QuicPacketSequenceNumber newest_transmission = *all_transmissions_it;
 302   if (newest_transmission != sequence_number) {
 303     ++stats_->packets_spuriously_retransmitted;
 304   }
 305
 306   // The AckNotifierManager needs to be notified about the most recent
 307   // transmission, since that's the one only one it tracks.
 308   ack_notifier_manager_.OnPacketAcked(newest_transmission);
 309
 310   bool has_crypto_handshake = HasCryptoHandshake(
 311       unacked_packets_.GetTransmissionInfo(newest_transmission));
 312   while (all_transmissions_it != all_transmissions.rend()) {
 313     QuicPacketSequenceNumber previous_transmission = *all_transmissions_it;
 314     const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 315         unacked_packets_.GetTransmissionInfo(previous_transmission);
 316     if (ContainsKey(pending_retransmissions_, previous_transmission)) {
 317       // Don't bother retransmitting this packet, if it has been
 318       // marked for retransmission.
 319       pending_retransmissions_.erase(previous_transmission);
 320     }
 321     if (has_crypto_handshake) {
 322       // If it's a crypto handshake packet, discard it and all retransmissions,
 323       // since they won't be acked now that one has been processed.
 324       if (transmission_info.pending) {
 325         OnPacketAbandoned(previous_transmission);
 326       }
 327       unacked_packets_.SetNotPending(previous_transmission);
 328     }
 329     if (!transmission_info.pending) {
 330       unacked_packets_.RemovePacket(previous_transmission);
 331     } else {
 332       unacked_packets_.NeuterPacket(previous_transmission);
 333     }
 334     ++all_transmissions_it;
 335   }
 336
 337   QuicUnackedPacketMap::const_iterator next_unacked = unacked_packets_.begin();
 338   while (next_unacked != unacked_packets_.end() &&
 339          next_unacked->first < sequence_number) {
 340     ++next_unacked;
 341   }
 342   return next_unacked;
 343 }
 344
 345 bool QuicSentPacketManager::IsUnacked(
 346     QuicPacketSequenceNumber sequence_number) const {
 347   return unacked_packets_.IsUnacked(sequence_number);
 348 }
 349
 350 bool QuicSentPacketManager::HasUnackedPackets() const {
 351   return unacked_packets_.HasUnackedPackets();
 352 }
 353
 354 QuicPacketSequenceNumber
 355 QuicSentPacketManager::GetLeastUnackedSentPacket() const {
 356   return unacked_packets_.GetLeastUnackedSentPacket();
 357 }
 358
 359 bool QuicSentPacketManager::OnPacketSent(
 360     QuicPacketSequenceNumber sequence_number,
 361     QuicTime sent_time,
 362     QuicByteCount bytes,
 363     TransmissionType transmission_type,
 364     HasRetransmittableData has_retransmittable_data) {
 365   DCHECK_LT(0u, sequence_number);
 366   LOG_IF(DFATAL, bytes == 0) << "Cannot send empty packets.";
 367   // In rare circumstances, the packet could be serialized, sent, and then acked
 368   // before OnPacketSent is called.
 369   if (!unacked_packets_.IsUnacked(sequence_number)) {
 370     return false;
 371   }
 372
 373   // Only track packets the send algorithm wants us to track.
 374   if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes,
 375                                      transmission_type,
 376                                      has_retransmittable_data)) {
 377     unacked_packets_.RemovePacket(sequence_number);
 378     // Do not reset the retransmission timer, since the packet isn't tracked.
 379     return false;
 380   }
 381
 382   const bool set_retransmission_timer = !unacked_packets_.HasPendingPackets();
 383
 384   unacked_packets_.SetPending(sequence_number, sent_time, bytes);
 385
 386   // Reset the retransmission timer anytime a packet is sent in tail loss probe
 387   // mode or before the crypto handshake has completed.
 388   return set_retransmission_timer || GetRetransmissionMode() != RTO_MODE;
 389 }
 390
 391 void QuicSentPacketManager::OnRetransmissionTimeout() {
 392   DCHECK(unacked_packets_.HasPendingPackets());
 393   // Handshake retransmission, timer based loss detection, TLP, and RTO are
 394   // implemented with a single alarm. The handshake alarm is set when the
 395   // handshake has not completed, the loss alarm is set when the loss detection
 396   // algorithm says to, and the TLP and  RTO alarms are set after that.
 397   // The TLP alarm is always set to run for under an RTO.
 398   switch (GetRetransmissionMode()) {
 399     case HANDSHAKE_MODE:
 400       ++stats_->crypto_retransmit_count;
 401       RetransmitCryptoPackets();
 402       return;
 403     case LOSS_MODE:
 404       ++stats_->loss_timeout_count;
 405       InvokeLossDetection(clock_->Now());
 406       return;
 407     case TLP_MODE:
 408       // If no tail loss probe can be sent, because there are no retransmittable
 409       // packets, execute a conventional RTO to abandon old packets.
 410       ++stats_->tlp_count;
 411       RetransmitOldestPacket();
 412       return;
 413     case RTO_MODE:
 414       ++stats_->rto_count;
 415       RetransmitAllPackets();
 416       return;
 417   }
 418 }
 419
 420 void QuicSentPacketManager::RetransmitCryptoPackets() {
 421   DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode());
 422   // TODO(ianswett): Typical TCP implementations only retransmit 5 times.
 423   consecutive_crypto_retransmission_count_ =
 424       min(kMaxHandshakeRetransmissionBackoffs,
 425           consecutive_crypto_retransmission_count_ + 1);
 426   bool packet_retransmitted = false;
 427   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 428        it != unacked_packets_.end(); ++it) {
 429     QuicPacketSequenceNumber sequence_number = it->first;
 430     const RetransmittableFrames* frames = it->second.retransmittable_frames;
 431     // Only retransmit frames which are pending, and therefore have been sent.
 432     if (!it->second.pending || frames == NULL ||
 433         frames->HasCryptoHandshake() != IS_HANDSHAKE) {
 434       continue;
 435     }
 436     packet_retransmitted = true;
 437     MarkForRetransmission(sequence_number, HANDSHAKE_RETRANSMISSION);
 438     // Abandon all the crypto retransmissions now so they're not lost later.
 439     OnPacketAbandoned(sequence_number);
 440   }
 441   DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
 442 }
 443
 444 void QuicSentPacketManager::RetransmitOldestPacket() {
 445   DCHECK_EQ(TLP_MODE, GetRetransmissionMode());
 446   ++consecutive_tlp_count_;
 447   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 448        it != unacked_packets_.end(); ++it) {
 449     QuicPacketSequenceNumber sequence_number = it->first;
 450     const RetransmittableFrames* frames = it->second.retransmittable_frames;
 451     // Only retransmit frames which are pending, and therefore have been sent.
 452     if (!it->second.pending || frames == NULL) {
 453       continue;
 454     }
 455     DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake());
 456     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
 457     return;
 458   }
 459   DLOG(FATAL)
 460     << "No retransmittable packets, so RetransmitOldestPacket failed.";
 461 }
 462
 463 void QuicSentPacketManager::RetransmitAllPackets() {
 464   // Abandon all retransmittable packets and packets older than the
 465   // retransmission delay.
 466
 467   DVLOG(1) << "OnRetransmissionTimeout() fired with "
 468            << unacked_packets_.GetNumUnackedPackets() << " unacked packets.";
 469
 470   // Request retransmission of all retransmittable packets when the RTO
 471   // fires, and let the congestion manager decide how many to send
 472   // immediately and the remaining packets will be queued.
 473   // Abandon any non-retransmittable packets that are sufficiently old.
 474   bool packets_retransmitted = false;
 475   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 476        it != unacked_packets_.end(); ++it) {
 477     unacked_packets_.SetNotPending(it->first);
 478     if (it->second.retransmittable_frames != NULL) {
 479       packets_retransmitted = true;
 480       MarkForRetransmission(it->first, RTO_RETRANSMISSION);
 481     }
 482   }
 483
 484   send_algorithm_->OnRetransmissionTimeout(packets_retransmitted);
 485   if (packets_retransmitted) {
 486     ++consecutive_rto_count_;
 487   }
 488 }
 489
 490 QuicSentPacketManager::RetransmissionTimeoutMode
 491     QuicSentPacketManager::GetRetransmissionMode() const {
 492   DCHECK(unacked_packets_.HasPendingPackets());
 493   if (unacked_packets_.HasPendingCryptoPackets()) {
 494     return HANDSHAKE_MODE;
 495   }
 496   if (loss_algorithm_->GetLossTimeout() != QuicTime::Zero()) {
 497     return LOSS_MODE;
 498   }
 499   if (consecutive_tlp_count_ < max_tail_loss_probes_) {
 500     if (unacked_packets_.HasUnackedRetransmittableFrames()) {
 501       return TLP_MODE;
 502     }
 503   }
 504   return RTO_MODE;
 505 }
 506
 507 void QuicSentPacketManager::OnPacketAbandoned(
 508     QuicPacketSequenceNumber sequence_number) {
 509   const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 510       unacked_packets_.GetTransmissionInfo(sequence_number);
 511   if (transmission_info.pending) {
 512     LOG_IF(DFATAL, transmission_info.bytes_sent == 0);
 513     send_algorithm_->OnPacketAbandoned(sequence_number,
 514                                        transmission_info.bytes_sent);
 515     unacked_packets_.SetNotPending(sequence_number);
 516   }
 517 }
 518
 519 void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame(
 520     const QuicCongestionFeedbackFrame& frame,
 521     const QuicTime& feedback_receive_time) {
 522   send_algorithm_->OnIncomingQuicCongestionFeedbackFrame(
 523       frame, feedback_receive_time);
 524 }
 525
 526 void QuicSentPacketManager::MaybeRetransmitOnAckFrame(
 527     const ReceivedPacketInfo& received_info,
 528     const QuicTime& ack_receive_time) {
 529   // Go through all pending packets up to the largest observed and count nacks.
 530   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 531        it != unacked_packets_.end() &&
 532            it->first <= received_info.largest_observed; ++it) {
 533     if (!it->second.pending) {
 534       continue;
 535     }
 536     QuicPacketSequenceNumber sequence_number = it->first;
 537     DVLOG(1) << "still missing packet " << sequence_number;
 538     // Acks must be handled previously, so ensure it's missing and not acked.
 539     DCHECK(IsAwaitingPacket(received_info, sequence_number));
 540
 541     // Consider it multiple nacks when there is a gap between the missing packet
 542     // and the largest observed, since the purpose of a nack threshold is to
 543     // tolerate re-ordering.  This handles both StretchAcks and Forward Acks.
 544     // The nack count only increases when the largest observed increases.
 545     size_t min_nacks = received_info.largest_observed - sequence_number;
 546     // Truncated acks can nack the largest observed, so set the nack count to 1.
 547     if (min_nacks == 0) {
 548       min_nacks = 1;
 549     }
 550     unacked_packets_.NackPacket(sequence_number, min_nacks);
 551   }
 552
 553   InvokeLossDetection(ack_receive_time);
 554 }
 555
 556 void QuicSentPacketManager::InvokeLossDetection(QuicTime time) {
 557   SequenceNumberSet lost_packets =
 558       loss_algorithm_->DetectLostPackets(unacked_packets_,
 559                                          time,
 560                                          largest_observed_,
 561                                          rtt_stats_);
 562   for (SequenceNumberSet::const_iterator it = lost_packets.begin();
 563        it != lost_packets.end(); ++it) {
 564     QuicPacketSequenceNumber sequence_number = *it;
 565     // TODO(ianswett): If it's expected the FEC packet may repair the loss, it
 566     // should be recorded as a loss to the send algorithm, but not retransmitted
 567     // until it's known whether the FEC packet arrived.
 568     ++stats_->packets_lost;
 569     send_algorithm_->OnPacketLost(sequence_number, time);
 570     OnPacketAbandoned(sequence_number);
 571
 572     if (unacked_packets_.HasRetransmittableFrames(sequence_number)) {
 573       MarkForRetransmission(sequence_number, LOSS_RETRANSMISSION);
 574     } else {
 575       // Since we will not retransmit this, we need to remove it from
 576       // unacked_packets_.   This is either the current transmission of
 577       // a packet whose previous transmission has been acked, or it
 578       // is a packet that has been TLP retransmitted.
 579       unacked_packets_.RemovePacket(sequence_number);
 580     }
 581   }
 582 }
 583
 584 void QuicSentPacketManager::MaybeUpdateRTT(
 585     const ReceivedPacketInfo& received_info,
 586     const QuicTime& ack_receive_time) {
 587   if (!unacked_packets_.IsUnacked(received_info.largest_observed)) {
 588     return;
 589   }
 590   // We calculate the RTT based on the highest ACKed sequence number, the lower
 591   // sequence numbers will include the ACK aggregation delay.
 592   const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 593       unacked_packets_.GetTransmissionInfo(received_info.largest_observed);
 594   // Don't update the RTT if it hasn't been sent.
 595   if (transmission_info.sent_time == QuicTime::Zero()) {
 596     return;
 597   }
 598
 599   QuicTime::Delta send_delta =
 600       ack_receive_time.Subtract(transmission_info.sent_time);
 601   rtt_stats_.UpdateRtt(send_delta, received_info.delta_time_largest_observed);
 602   send_algorithm_->UpdateRtt(rtt_stats_.latest_rtt());
 603 }
 604
 605 QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
 606     QuicTime now,
 607     TransmissionType transmission_type,
 608     HasRetransmittableData retransmittable,
 609     IsHandshake handshake) {
 610   return send_algorithm_->TimeUntilSend(now, transmission_type, retransmittable,
 611                                         handshake);
 612 }
 613
 614 // Ensures that the Delayed Ack timer is always set to a value lesser
 615 // than the retransmission timer's minimum value (MinRTO). We want the
 616 // delayed ack to get back to the QUIC peer before the sender's
 617 // retransmission timer triggers.  Since we do not know the
 618 // reverse-path one-way delay, we assume equal delays for forward and
 619 // reverse paths, and ensure that the timer is set to less than half
 620 // of the MinRTO.
 621 // There may be a value in making this delay adaptive with the help of
 622 // the sender and a signaling mechanism -- if the sender uses a
 623 // different MinRTO, we may get spurious retransmissions. May not have
 624 // any benefits, but if the delayed ack becomes a significant source
 625 // of (likely, tail) latency, then consider such a mechanism.
 626 const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const {
 627   return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2);
 628 }
 629
 630 const QuicTime QuicSentPacketManager::GetRetransmissionTime() const {
 631   // Don't set the timer if there are no pending packets.
 632   if (!unacked_packets_.HasPendingPackets()) {
 633     return QuicTime::Zero();
 634   }
 635   switch (GetRetransmissionMode()) {
 636     case HANDSHAKE_MODE:
 637       return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
 638     case LOSS_MODE:
 639       return loss_algorithm_->GetLossTimeout();
 640     case TLP_MODE: {
 641       // TODO(ianswett): When CWND is available, it would be preferable to
 642       // set the timer based on the earliest retransmittable packet.
 643       // Base the updated timer on the send time of the last packet.
 644       // TODO(ianswett): I believe this is a subtle mis-implementation of tail
 645       // loss probe, since GetLastPacketSentTime actually returns the sent time
 646       // of the last pending packet which still has retransmittable frames.
 647       const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
 648       const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay());
 649       // Ensure the tlp timer never gets set to a time in the past.
 650       return QuicTime::Max(clock_->ApproximateNow(), tlp_time);
 651     }
 652     case RTO_MODE: {
 653       // The RTO is based on the first pending packet.
 654       const QuicTime sent_time =
 655           unacked_packets_.GetFirstPendingPacketSentTime();
 656       QuicTime rto_timeout = sent_time.Add(GetRetransmissionDelay());
 657       // Always wait at least 1.5 * RTT from now.
 658       QuicTime min_timeout = clock_->ApproximateNow().Add(
 659           SmoothedRtt().Multiply(1.5));
 660
 661       return QuicTime::Max(min_timeout, rto_timeout);
 662     }
 663   }
 664   DCHECK(false);
 665   return QuicTime::Zero();
 666 }
 667
 668 const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay()
 669     const {
 670   // This is equivalent to the TailLossProbeDelay, but slightly more aggressive
 671   // because crypto handshake messages don't incur a delayed ack time.
 672   int64 delay_ms = max<int64>(kMinHandshakeTimeoutMs,
 673                               1.5 * SmoothedRtt().ToMilliseconds());
 674   return QuicTime::Delta::FromMilliseconds(
 675       delay_ms << consecutive_crypto_retransmission_count_);
 676 }
 677
 678 const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const {
 679   QuicTime::Delta srtt = SmoothedRtt();
 680   if (!unacked_packets_.HasMultiplePendingPackets()) {
 681     return QuicTime::Delta::Max(
 682         srtt.Multiply(1.5).Add(DelayedAckTime()), srtt.Multiply(2));
 683   }
 684   return QuicTime::Delta::FromMilliseconds(
 685       max(kMinTailLossProbeTimeoutMs,
 686           static_cast<int64>(2 * srtt.ToMilliseconds())));
 687 }
 688
 689 const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
 690   QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
 691   // TODO(rch): This code should move to |send_algorithm_|.
 692   if (retransmission_delay.IsZero()) {
 693     // We are in the initial state, use default timeout values.
 694     retransmission_delay =
 695         QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
 696   } else if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
 697     retransmission_delay =
 698         QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
 699   }
 700
 701   // Calculate exponential back off.
 702   retransmission_delay = retransmission_delay.Multiply(
 703       1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions));
 704
 705   if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
 706     return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
 707   }
 708   return retransmission_delay;
 709 }
 710
 711 const QuicTime::Delta QuicSentPacketManager::SmoothedRtt() const {
 712   return rtt_stats_.SmoothedRtt();
 713 }
 714
 715 QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
 716   return send_algorithm_->BandwidthEstimate();
 717 }
 718
 719 QuicByteCount QuicSentPacketManager::GetCongestionWindow() const {
 720   return send_algorithm_->GetCongestionWindow();
 721 }
 722
 723 void QuicSentPacketManager::MaybeEnablePacing() {
 724   if (!FLAGS_enable_quic_pacing) {
 725     return;
 726   }
 727
 728   if (using_pacing_) {
 729     return;
 730   }
 731
 732   using_pacing_ = true;
 733   send_algorithm_.reset(
 734       new PacingSender(send_algorithm_.release(),
 735                        QuicTime::Delta::FromMicroseconds(1)));
 736 }
 737
 738 }  // namespace net