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