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