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