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