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