src/net/quic/quic_sent_packet_manager.cc

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