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 = false;
  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 // TCP retransmits after 3 nacks.
  45 static const size_t kNumberOfNacksBeforeRetransmission = 3;
  46
  47 // Only exponentially back off the handshake timer 5 times due to a timeout.
  48 static const size_t kMaxHandshakeRetransmissionBackoffs = 5;
  49 static const size_t kMinHandshakeTimeoutMs = 10;
  50
  51 // Sends up to two tail loss probes before firing an RTO,
  52 // per draft RFC draft-dukkipati-tcpm-tcp-loss-probe.
  53 static const size_t kDefaultMaxTailLossProbes = 2;
  54 static const int64 kMinTailLossProbeTimeoutMs = 10;
  55
  56 bool HasCryptoHandshake(
  57     const QuicUnackedPacketMap::TransmissionInfo& transmission_info) {
  58   if (transmission_info.retransmittable_frames == NULL) {
  59     return false;
  60   }
  61   return transmission_info.retransmittable_frames->HasCryptoHandshake() ==
  62       IS_HANDSHAKE;
  63 }
  64
  65 }  // namespace
  66
  67 #define ENDPOINT (is_server_ ? "Server: " : " Client: ")
  68
  69 QuicSentPacketManager::QuicSentPacketManager(bool is_server,
  70                                              const QuicClock* clock,
  71                                              QuicConnectionStats* stats,
  72                                              CongestionFeedbackType type)
  73     : unacked_packets_(is_server),
  74       is_server_(is_server),
  75       clock_(clock),
  76       stats_(stats),
  77       send_algorithm_(SendAlgorithmInterface::Create(clock, type)),
  78       rtt_sample_(QuicTime::Delta::Infinite()),
  79       pending_crypto_packet_count_(0),
  80       consecutive_rto_count_(0),
  81       consecutive_tlp_count_(0),
  82       consecutive_crypto_retransmission_count_(0),
  83       max_tail_loss_probes_(kDefaultMaxTailLossProbes),
  84       using_pacing_(false) {
  85 }
  86
  87 QuicSentPacketManager::~QuicSentPacketManager() {
  88 }
  89
  90 void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
  91   if (config.initial_round_trip_time_us() > 0 &&
  92       rtt_sample_.IsInfinite()) {
  93     // The initial rtt should already be set on the client side.
  94     DVLOG_IF(1, !is_server_)
  95         << "Client did not set an initial RTT, but did negotiate one.";
  96     rtt_sample_ =
  97         QuicTime::Delta::FromMicroseconds(config.initial_round_trip_time_us());
  98     send_algorithm_->UpdateRtt(rtt_sample_);
  99   }
 100   if (config.congestion_control() == kPACE) {
 101     MaybeEnablePacing();
 102   }
 103   send_algorithm_->SetFromConfig(config, is_server_);
 104 }
 105
 106 // TODO(ianswett): Combine this method with OnPacketSent once packets are always
 107 // sent in order and the connection tracks RetransmittableFrames for longer.
 108 void QuicSentPacketManager::OnSerializedPacket(
 109     const SerializedPacket& serialized_packet) {
 110   if (serialized_packet.retransmittable_frames) {
 111     ack_notifier_manager_.OnSerializedPacket(serialized_packet);
 112
 113     if (serialized_packet.retransmittable_frames->HasCryptoHandshake()
 114             == IS_HANDSHAKE) {
 115       ++pending_crypto_packet_count_;
 116     }
 117   }
 118
 119   unacked_packets_.AddPacket(serialized_packet);
 120 }
 121
 122 void QuicSentPacketManager::OnRetransmittedPacket(
 123     QuicPacketSequenceNumber old_sequence_number,
 124     QuicPacketSequenceNumber new_sequence_number) {
 125   DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number));
 126
 127   pending_retransmissions_.erase(old_sequence_number);
 128
 129   // A notifier may be waiting to hear about ACKs for the original sequence
 130   // number. Inform them that the sequence number has changed.
 131   ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number,
 132                                              new_sequence_number);
 133
 134   unacked_packets_.OnRetransmittedPacket(old_sequence_number,
 135                                          new_sequence_number);
 136 }
 137
 138 bool QuicSentPacketManager::OnIncomingAck(
 139     const ReceivedPacketInfo& received_info, QuicTime ack_receive_time) {
 140   // We rely on delta_time_largest_observed to compute an RTT estimate, so
 141   // we only update rtt when the largest observed gets acked.
 142   bool largest_observed_acked =
 143       unacked_packets_.IsUnacked(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
 309   SequenceNumberSet all_transmissions = *transmission_info.all_transmissions;
 310   SequenceNumberSet::reverse_iterator all_transmissions_it =
 311       all_transmissions.rbegin();
 312   QuicPacketSequenceNumber newest_transmission = *all_transmissions_it;
 313   if (newest_transmission != sequence_number) {
 314     ++stats_->packets_spuriously_retransmitted;
 315   }
 316
 317   bool has_cryto_handshake = HasCryptoHandshake(
 318       unacked_packets_.GetTransmissionInfo(newest_transmission));
 319   if (has_cryto_handshake) {
 320     --pending_crypto_packet_count_;
 321   }
 322   while (all_transmissions_it != all_transmissions.rend()) {
 323     QuicPacketSequenceNumber previous_transmission = *all_transmissions_it;
 324     const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 325         unacked_packets_.GetTransmissionInfo(previous_transmission);
 326     if (ContainsKey(pending_retransmissions_, previous_transmission)) {
 327       // Don't bother retransmitting this packet, if it has been
 328       // marked for retransmission.
 329       pending_retransmissions_.erase(previous_transmission);
 330     }
 331     if (has_cryto_handshake) {
 332       // If it's a crypto handshake packet, discard it and all retransmissions,
 333       // since they won't be acked now that one has been processed.
 334       if (transmission_info.pending) {
 335         OnPacketAbandoned(previous_transmission);
 336       }
 337       unacked_packets_.SetNotPending(previous_transmission);
 338     }
 339     if (!transmission_info.pending) {
 340       unacked_packets_.RemovePacket(previous_transmission);
 341     } else {
 342       unacked_packets_.NeuterPacket(previous_transmission);
 343     }
 344     ++all_transmissions_it;
 345   }
 346
 347   QuicUnackedPacketMap::const_iterator next_unacked = unacked_packets_.begin();
 348   while (next_unacked != unacked_packets_.end() &&
 349          next_unacked->first < sequence_number) {
 350     ++next_unacked;
 351   }
 352   return next_unacked;
 353 }
 354
 355 bool QuicSentPacketManager::IsUnacked(
 356     QuicPacketSequenceNumber sequence_number) const {
 357   return unacked_packets_.IsUnacked(sequence_number);
 358 }
 359
 360 bool QuicSentPacketManager::HasUnackedPackets() const {
 361   return unacked_packets_.HasUnackedPackets();
 362 }
 363
 364 QuicPacketSequenceNumber
 365 QuicSentPacketManager::GetLeastUnackedSentPacket() const {
 366   return unacked_packets_.GetLeastUnackedSentPacket();
 367 }
 368
 369 bool QuicSentPacketManager::OnPacketSent(
 370     QuicPacketSequenceNumber sequence_number,
 371     QuicTime sent_time,
 372     QuicByteCount bytes,
 373     TransmissionType transmission_type,
 374     HasRetransmittableData has_retransmittable_data) {
 375   DCHECK_LT(0u, sequence_number);
 376   LOG_IF(DFATAL, bytes == 0) << "Cannot send empty packets.";
 377   // In rare circumstances, the packet could be serialized, sent, and then acked
 378   // before OnPacketSent is called.
 379   if (!unacked_packets_.IsUnacked(sequence_number)) {
 380     return false;
 381   }
 382
 383   // Only track packets the send algorithm wants us to track.
 384   if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes,
 385                                      transmission_type,
 386                                      has_retransmittable_data)) {
 387     unacked_packets_.RemovePacket(sequence_number);
 388     // Do not reset the retransmission timer, since the packet isn't tracked.
 389     return false;
 390   }
 391
 392   const bool set_retransmission_timer = !unacked_packets_.HasPendingPackets();
 393
 394   unacked_packets_.SetPending(sequence_number, sent_time, bytes);
 395
 396   // Reset the retransmission timer anytime a packet is sent in tail loss probe
 397   // mode or before the crypto handshake has completed.
 398   return set_retransmission_timer || GetRetransmissionMode() != RTO_MODE;
 399 }
 400
 401 void QuicSentPacketManager::OnRetransmissionTimeout() {
 402   DCHECK(unacked_packets_.HasPendingPackets());
 403   // Handshake retransmission, TLP, and RTO are implemented with a single alarm.
 404   // The handshake alarm is set when the handshake has not completed, and the
 405   // TLP and RTO alarms are set after that.
 406   // The TLP alarm is always set to run for under an RTO.
 407   switch (GetRetransmissionMode()) {
 408     case HANDSHAKE_MODE:
 409       ++stats_->crypto_retransmit_count;
 410       RetransmitCryptoPackets();
 411       return;
 412     case TLP_MODE:
 413       // If no tail loss probe can be sent, because there are no retransmittable
 414       // packets, execute a conventional RTO to abandon old packets.
 415       ++stats_->tlp_count;
 416       RetransmitOldestPacket();
 417       return;
 418     case RTO_MODE:
 419       ++stats_->rto_count;
 420       RetransmitAllPackets();
 421       return;
 422   }
 423 }
 424
 425 void QuicSentPacketManager::RetransmitCryptoPackets() {
 426   DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode());
 427   // TODO(ianswett): Typical TCP implementations only retransmit 5 times.
 428   consecutive_crypto_retransmission_count_ =
 429       min(kMaxHandshakeRetransmissionBackoffs,
 430           consecutive_crypto_retransmission_count_ + 1);
 431   bool packet_retransmitted = false;
 432   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 433        it != unacked_packets_.end(); ++it) {
 434     QuicPacketSequenceNumber sequence_number = it->first;
 435     const RetransmittableFrames* frames = it->second.retransmittable_frames;
 436     // Only retransmit frames which are pending, and therefore have been sent.
 437     if (!it->second.pending || frames == NULL ||
 438         frames->HasCryptoHandshake() != IS_HANDSHAKE) {
 439       continue;
 440     }
 441     packet_retransmitted = true;
 442     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
 443     // Abandon all the crypto retransmissions now so they're not lost later.
 444     OnPacketAbandoned(sequence_number);
 445   }
 446   DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
 447 }
 448
 449 void QuicSentPacketManager::RetransmitOldestPacket() {
 450   DCHECK_EQ(TLP_MODE, GetRetransmissionMode());
 451   ++consecutive_tlp_count_;
 452   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 453        it != unacked_packets_.end(); ++it) {
 454     QuicPacketSequenceNumber sequence_number = it->first;
 455     const RetransmittableFrames* frames = it->second.retransmittable_frames;
 456     // Only retransmit frames which are pending, and therefore have been sent.
 457     if (!it->second.pending || frames == NULL) {
 458       continue;
 459     }
 460     DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake());
 461     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
 462     return;
 463   }
 464   DLOG(FATAL)
 465     << "No retransmittable packets, so RetransmitOldestPacket failed.";
 466 }
 467
 468 void QuicSentPacketManager::RetransmitAllPackets() {
 469   // Abandon all retransmittable packets and packets older than the
 470   // retransmission delay.
 471
 472   DVLOG(1) << "OnRetransmissionTimeout() fired with "
 473            << unacked_packets_.GetNumUnackedPackets() << " unacked packets.";
 474
 475   // Request retransmission of all retransmittable packets when the RTO
 476   // fires, and let the congestion manager decide how many to send
 477   // immediately and the remaining packets will be queued.
 478   // Abandon any non-retransmittable packets that are sufficiently old.
 479   bool packets_retransmitted = false;
 480   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 481        it != unacked_packets_.end(); ++it) {
 482     unacked_packets_.SetNotPending(it->first);
 483     if (it->second.retransmittable_frames != NULL) {
 484       packets_retransmitted = true;
 485       MarkForRetransmission(it->first, RTO_RETRANSMISSION);
 486     }
 487   }
 488
 489   send_algorithm_->OnRetransmissionTimeout(packets_retransmitted);
 490   if (packets_retransmitted) {
 491     ++consecutive_rto_count_;
 492   }
 493 }
 494
 495 QuicSentPacketManager::RetransmissionTimeoutMode
 496     QuicSentPacketManager::GetRetransmissionMode() const {
 497   DCHECK(unacked_packets_.HasPendingPackets());
 498   if (pending_crypto_packet_count_ > 0) {
 499     return HANDSHAKE_MODE;
 500   }
 501   if (consecutive_tlp_count_ < max_tail_loss_probes_) {
 502     if (unacked_packets_.HasUnackedRetransmittableFrames()) {
 503       return TLP_MODE;
 504     }
 505   }
 506   return RTO_MODE;
 507 }
 508
 509 void QuicSentPacketManager::OnPacketAbandoned(
 510     QuicPacketSequenceNumber sequence_number) {
 511   if (unacked_packets_.IsPending(sequence_number)) {
 512     LOG_IF(DFATAL, unacked_packets_.GetTransmissionInfo(
 513         sequence_number).bytes_sent == 0);
 514     send_algorithm_->OnPacketAbandoned(
 515         sequence_number,
 516         unacked_packets_.GetTransmissionInfo(sequence_number).bytes_sent);
 517     unacked_packets_.SetNotPending(sequence_number);
 518   }
 519 }
 520
 521 void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame(
 522     const QuicCongestionFeedbackFrame& frame,
 523     const QuicTime& feedback_receive_time) {
 524   send_algorithm_->OnIncomingQuicCongestionFeedbackFrame(
 525       frame, feedback_receive_time);
 526 }
 527
 528 void QuicSentPacketManager::MaybeRetransmitOnAckFrame(
 529     const ReceivedPacketInfo& received_info,
 530     const QuicTime& ack_receive_time) {
 531   // Go through all pending packets up to the largest observed and see if any
 532   // need to be retransmitted or lost.
 533   for (QuicUnackedPacketMap::const_iterator it = unacked_packets_.begin();
 534        it != unacked_packets_.end() &&
 535            it->first <= received_info.largest_observed; ++it) {
 536     if (!it->second.pending) {
 537       continue;
 538     }
 539     QuicPacketSequenceNumber sequence_number = it->first;
 540     DVLOG(1) << "still missing packet " << sequence_number;
 541     // Acks must be handled previously, so ensure it's missing and not acked.
 542     DCHECK(IsAwaitingPacket(received_info, sequence_number));
 543
 544     // Consider it multiple nacks when there is a gap between the missing packet
 545     // and the largest observed, since the purpose of a nack threshold is to
 546     // tolerate re-ordering.  This handles both StretchAcks and Forward Acks.
 547     // TODO(ianswett): This relies heavily on sequential reception of packets,
 548     // and makes an assumption that the congestion control uses TCP style nacks.
 549     size_t min_nacks = received_info.largest_observed - sequence_number;
 550     unacked_packets_.NackPacket(sequence_number, min_nacks);
 551   }
 552
 553   SequenceNumberSet lost_packets =
 554       DetectLostPackets(unacked_packets_,
 555                        ack_receive_time,
 556                        received_info.largest_observed);
 557   for (SequenceNumberSet::const_iterator it = lost_packets.begin();
 558        it != lost_packets.end(); ++it) {
 559     QuicPacketSequenceNumber sequence_number = *it;
 560     // TODO(ianswett): If it's expected the FEC packet may repair the loss, it
 561     // should be recorded as a loss to the send algorithm, but not retransmitted
 562     // until it's known whether the FEC packet arrived.
 563     ++stats_->packets_lost;
 564     send_algorithm_->OnPacketLost(sequence_number, ack_receive_time);
 565     OnPacketAbandoned(sequence_number);
 566
 567     if (unacked_packets_.HasRetransmittableFrames(sequence_number)) {
 568       MarkForRetransmission(sequence_number, NACK_RETRANSMISSION);
 569     } else {
 570       // Since we will not retransmit this, we need to remove it from
 571       // unacked_packets_.   This is either the current transmission of
 572       // a packet whose previous transmission has been acked, or it
 573       // is a packet that has been TLP retransmitted.
 574       unacked_packets_.RemovePacket(sequence_number);
 575     }
 576   }
 577 }
 578
 579 // static
 580 SequenceNumberSet QuicSentPacketManager::DetectLostPackets(
 581     const QuicUnackedPacketMap& unacked_packets,
 582     const QuicTime& time,
 583     QuicPacketSequenceNumber largest_observed) {
 584   SequenceNumberSet lost_packets;
 585
 586   for (QuicUnackedPacketMap::const_iterator it = unacked_packets.begin();
 587        it != unacked_packets.end() && it->first <= largest_observed; ++it) {
 588     if (!it->second.pending) {
 589       continue;
 590     }
 591     size_t num_nacks_needed = kNumberOfNacksBeforeRetransmission;
 592     // Check for early retransmit(RFC5827) when the last packet gets acked and
 593     // the there are fewer than 4 pending packets.
 594     // TODO(ianswett): Set a retransmission timer instead of losing the packet
 595     // and retransmitting immediately.  Also consider only invoking OnPacketLost
 596     // and OnPacketAbandoned when they're actually retransmitted in case they
 597     // arrive while queued for retransmission.
 598     if (it->second.retransmittable_frames &&
 599         unacked_packets.largest_sent_packet() == largest_observed) {
 600       num_nacks_needed = largest_observed - it->first;
 601     }
 602
 603     if (it->second.nack_count < num_nacks_needed) {
 604       continue;
 605     }
 606
 607     lost_packets.insert(it->first);
 608   }
 609
 610   return lost_packets;
 611 }
 612
 613 void QuicSentPacketManager::MaybeUpdateRTT(
 614     const ReceivedPacketInfo& received_info,
 615     const QuicTime& ack_receive_time) {
 616   if (!unacked_packets_.IsUnacked(received_info.largest_observed)) {
 617     return;
 618   }
 619   // We calculate the RTT based on the highest ACKed sequence number, the lower
 620   // sequence numbers will include the ACK aggregation delay.
 621   const QuicUnackedPacketMap::TransmissionInfo& transmission_info =
 622       unacked_packets_.GetTransmissionInfo(received_info.largest_observed);
 623   // Don't update the RTT if it hasn't been sent.
 624   if (transmission_info.sent_time == QuicTime::Zero()) {
 625     return;
 626   }
 627
 628   QuicTime::Delta send_delta =
 629       ack_receive_time.Subtract(transmission_info.sent_time);
 630   if (send_delta > received_info.delta_time_largest_observed) {
 631     rtt_sample_ = send_delta.Subtract(
 632         received_info.delta_time_largest_observed);
 633   } else if (rtt_sample_.IsInfinite()) {
 634     // Even though we received information from the peer suggesting
 635     // an invalid (negative) RTT, we can use the send delta as an
 636     // approximation until we get a better estimate.
 637     rtt_sample_ = send_delta;
 638   }
 639   send_algorithm_->UpdateRtt(rtt_sample_);
 640 }
 641
 642 QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
 643     QuicTime now,
 644     TransmissionType transmission_type,
 645     HasRetransmittableData retransmittable,
 646     IsHandshake handshake) {
 647   return send_algorithm_->TimeUntilSend(now, transmission_type, retransmittable,
 648                                         handshake);
 649 }
 650
 651 // Ensures that the Delayed Ack timer is always set to a value lesser
 652 // than the retransmission timer's minimum value (MinRTO). We want the
 653 // delayed ack to get back to the QUIC peer before the sender's
 654 // retransmission timer triggers.  Since we do not know the
 655 // reverse-path one-way delay, we assume equal delays for forward and
 656 // reverse paths, and ensure that the timer is set to less than half
 657 // of the MinRTO.
 658 // There may be a value in making this delay adaptive with the help of
 659 // the sender and a signaling mechanism -- if the sender uses a
 660 // different MinRTO, we may get spurious retransmissions. May not have
 661 // any benefits, but if the delayed ack becomes a significant source
 662 // of (likely, tail) latency, then consider such a mechanism.
 663 const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const {
 664   return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2);
 665 }
 666
 667 const QuicTime QuicSentPacketManager::GetRetransmissionTime() const {
 668   // Don't set the timer if there are no pending packets.
 669   if (!unacked_packets_.HasPendingPackets()) {
 670     return QuicTime::Zero();
 671   }
 672   switch (GetRetransmissionMode()) {
 673     case HANDSHAKE_MODE:
 674       return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
 675     case TLP_MODE: {
 676       // TODO(ianswett): When CWND is available, it would be preferable to
 677       // set the timer based on the earliest retransmittable packet.
 678       // Base the updated timer on the send time of the last packet.
 679       // TODO(ianswett): I believe this is a subtle mis-implementation of tail
 680       // loss probe, since GetLastPacketSentTime actually returns the sent time
 681       // of the last pending packet which still has retransmittable frames.
 682       const QuicTime sent_time = unacked_packets_.GetLastPacketSentTime();
 683       const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay());
 684       // Ensure the tlp timer never gets set to a time in the past.
 685       return QuicTime::Max(clock_->ApproximateNow(), tlp_time);
 686     }
 687     case RTO_MODE: {
 688       // The RTO is based on the first pending packet.
 689       const QuicTime sent_time =
 690           unacked_packets_.GetFirstPendingPacketSentTime();
 691       // Always wait at least 1.5 * RTT after the first sent packet.
 692       QuicTime min_timeout = clock_->ApproximateNow().Add(
 693           SmoothedRtt().Multiply(1.5));
 694       QuicTime rto_timeout = sent_time.Add(GetRetransmissionDelay());
 695
 696       return QuicTime::Max(min_timeout, rto_timeout);
 697     }
 698   }
 699   DCHECK(false);
 700   return QuicTime::Zero();
 701 }
 702
 703 const QuicTime::Delta QuicSentPacketManager::GetCryptoRetransmissionDelay()
 704     const {
 705   // This is equivalent to the TailLossProbeDelay, but slightly more aggressive
 706   // because crypto handshake messages don't incur a delayed ack time.
 707   int64 delay_ms = max<int64>(kMinHandshakeTimeoutMs,
 708                               1.5 * SmoothedRtt().ToMilliseconds());
 709   return QuicTime::Delta::FromMilliseconds(
 710       delay_ms << consecutive_crypto_retransmission_count_);
 711 }
 712
 713 const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const {
 714   QuicTime::Delta srtt = SmoothedRtt();
 715   if (!unacked_packets_.HasMultiplePendingPackets()) {
 716     return QuicTime::Delta::Max(
 717         srtt.Multiply(1.5).Add(DelayedAckTime()), srtt.Multiply(2));
 718   }
 719   return QuicTime::Delta::FromMilliseconds(
 720       max(kMinTailLossProbeTimeoutMs,
 721           static_cast<int64>(2 * srtt.ToMilliseconds())));
 722 }
 723
 724 const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
 725   QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
 726   // TODO(rch): This code should move to |send_algorithm_|.
 727   if (retransmission_delay.IsZero()) {
 728     // We are in the initial state, use default timeout values.
 729     retransmission_delay =
 730         QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
 731   } else if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
 732     retransmission_delay =
 733         QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
 734   }
 735
 736   // Calculate exponential back off.
 737   retransmission_delay = retransmission_delay.Multiply(
 738       1 << min<size_t>(consecutive_rto_count_, kMaxRetransmissions));
 739
 740   if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
 741     return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
 742   }
 743   return retransmission_delay;
 744 }
 745
 746 const QuicTime::Delta QuicSentPacketManager::SmoothedRtt() const {
 747   return send_algorithm_->SmoothedRtt();
 748 }
 749
 750 QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
 751   return send_algorithm_->BandwidthEstimate();
 752 }
 753
 754 QuicByteCount QuicSentPacketManager::GetCongestionWindow() const {
 755   return send_algorithm_->GetCongestionWindow();
 756 }
 757
 758 void QuicSentPacketManager::MaybeEnablePacing() {
 759   if (!FLAGS_enable_quic_pacing) {
 760     return;
 761   }
 762
 763   if (using_pacing_) {
 764     return;
 765   }
 766
 767   using_pacing_ = true;
 768   send_algorithm_.reset(
 769       new PacingSender(send_algorithm_.release(),
 770                        QuicTime::Delta::FromMicroseconds(1)));
 771 }
 772
 773 }  // namespace net