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