net/quic/quic_sent_packet_manager.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "net/quic/quic_sent_packet_manager.h"
   6
   7 #include "base/logging.h"
   8 #include "base/stl_util.h"
   9 #include "net/quic/congestion_control/pacing_sender.h"
  10 #include "net/quic/quic_ack_notifier_manager.h"
  11
  12 using std::make_pair;
  13 using std::max;
  14 using std::min;
  15
  16 // TODO(rtenneti): Remove this.
  17 // Do not flip this flag until the flakiness of the
  18 // net/tools/quic/end_to_end_test is fixed.
  19 // If true, then QUIC connections will track the retransmission history of a
  20 // packet so that an ack of a previous transmission will ack the data of all
  21 // other transmissions.
  22 bool FLAGS_track_retransmission_history = false;
  23
  24 // A test-only flag to prevent the RTO from backing off when multiple sequential
  25 // tail drops occur.
  26 bool FLAGS_limit_rto_increase_for_tests = false;
  27
  28 // Do not remove this flag until the Finch-trials described in b/11706275
  29 // are complete.
  30 // If true, QUIC connections will support the use of a pacing algorithm when
  31 // sending packets, in an attempt to reduce packet loss.  The client must also
  32 // request pacing for the server to enable it.
  33 bool FLAGS_enable_quic_pacing = false;
  34
  35 namespace net {
  36 namespace {
  37 static const int kBitrateSmoothingPeriodMs = 1000;
  38 static const int kHistoryPeriodMs = 5000;
  39
  40 static const int kDefaultRetransmissionTimeMs = 500;
  41 // TCP RFC calls for 1 second RTO however Linux differs from this default and
  42 // define the minimum RTO to 200ms, we will use the same until we have data to
  43 // support a higher or lower value.
  44 static const int kMinRetransmissionTimeMs = 200;
  45 static const int kMaxRetransmissionTimeMs = 60000;
  46 static const size_t kMaxRetransmissions = 10;
  47
  48 // We retransmit at most 2 packets per ack.
  49 static const size_t kMaxRetransmissionsPerAck = 2;
  50
  51 // TCP retransmits after 3 nacks.
  52 static const size_t kNumberOfNacksBeforeRetransmission = 3;
  53
  54 // Only exponentially back off the handshake timer 5 times due to a timeout.
  55 static const size_t kMaxHandshakeRetransmissionBackoffs = 5;
  56 static const size_t kMinHandshakeTimeoutMs = 10;
  57
  58 // Sends up to two tail loss probes before firing an RTO,
  59 // per draft RFC draft-dukkipati-tcpm-tcp-loss-probe.
  60 static const size_t kDefaultMaxTailLossProbes = 2;
  61 static const int64 kMinTailLossProbeTimeoutMs = 10;
  62
  63 COMPILE_ASSERT(kHistoryPeriodMs >= kBitrateSmoothingPeriodMs,
  64                history_must_be_longer_or_equal_to_the_smoothing_period);
  65
  66 }  // namespace
  67
  68 #define ENDPOINT (is_server_ ? "Server: " : " Client: ")
  69
  70 QuicSentPacketManager::HelperInterface::~HelperInterface() {
  71 }
  72
  73 QuicSentPacketManager::QuicSentPacketManager(bool is_server,
  74                                              HelperInterface* helper,
  75                                              const QuicClock* clock,
  76                                              CongestionFeedbackType type)
  77     : is_server_(is_server),
  78       helper_(helper),
  79       clock_(clock),
  80       send_algorithm_(SendAlgorithmInterface::Create(clock, type)),
  81       rtt_sample_(QuicTime::Delta::Infinite()),
  82       pending_crypto_packet_count_(0),
  83       consecutive_rto_count_(0),
  84       consecutive_tlp_count_(0),
  85       consecutive_crypto_retransmission_count_(0),
  86       max_tail_loss_probes_(kDefaultMaxTailLossProbes),
  87       using_pacing_(false) {
  88 }
  89
  90 QuicSentPacketManager::~QuicSentPacketManager() {
  91   for (UnackedPacketMap::iterator it = unacked_packets_.begin();
  92        it != unacked_packets_.end(); ++it) {
  93     delete it->second.retransmittable_frames;
  94     // Only delete previous_transmissions once, for the newest packet.
  95     if (it->second.previous_transmissions != NULL &&
  96         it->first == *it->second.previous_transmissions->rbegin()) {
  97       delete it->second.previous_transmissions;
  98     }
  99   }
 100   STLDeleteValues(&packet_history_map_);
 101 }
 102
 103 void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
 104   if (config.initial_round_trip_time_us() > 0 &&
 105       rtt_sample_.IsInfinite()) {
 106     // The initial rtt should already be set on the client side.
 107     DVLOG_IF(1, !is_server_)
 108         << "Client did not set an initial RTT, but did negotiate one.";
 109     rtt_sample_ =
 110         QuicTime::Delta::FromMicroseconds(config.initial_round_trip_time_us());
 111   }
 112   if (config.congestion_control() == kPACE) {
 113     MaybeEnablePacing();
 114   }
 115   send_algorithm_->SetFromConfig(config, is_server_);
 116 }
 117
 118 void QuicSentPacketManager::SetMaxPacketSize(QuicByteCount max_packet_size) {
 119   send_algorithm_->SetMaxPacketSize(max_packet_size);
 120 }
 121
 122 // TODO(ianswett): Combine this method with OnPacketSent once packets are always
 123 // sent in order and the connection tracks RetransmittableFrames for longer.
 124 void QuicSentPacketManager::OnSerializedPacket(
 125     const SerializedPacket& serialized_packet) {
 126   if (serialized_packet.retransmittable_frames) {
 127     ack_notifier_manager_.OnSerializedPacket(serialized_packet);
 128
 129     if (serialized_packet.retransmittable_frames->HasCryptoHandshake()
 130             == IS_HANDSHAKE) {
 131       ++pending_crypto_packet_count_;
 132     }
 133   }
 134
 135   DCHECK(unacked_packets_.empty() ||
 136          unacked_packets_.rbegin()->first < serialized_packet.sequence_number);
 137   unacked_packets_[serialized_packet.sequence_number] =
 138       TransmissionInfo(serialized_packet.retransmittable_frames,
 139                        serialized_packet.sequence_number_length);
 140 }
 141
 142 void QuicSentPacketManager::OnRetransmittedPacket(
 143     QuicPacketSequenceNumber old_sequence_number,
 144     QuicPacketSequenceNumber new_sequence_number) {
 145   DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
 146   DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number));
 147   DCHECK(unacked_packets_.empty() ||
 148          unacked_packets_.rbegin()->first < new_sequence_number);
 149
 150   pending_retransmissions_.erase(old_sequence_number);
 151   // TODO(ianswett): Discard and lose the packet lazily instead of immediately.
 152
 153   UnackedPacketMap::iterator unacked_it =
 154       unacked_packets_.find(old_sequence_number);
 155   RetransmittableFrames* frames = unacked_it->second.retransmittable_frames;
 156   DCHECK(frames);
 157
 158   // A notifier may be waiting to hear about ACKs for the original sequence
 159   // number. Inform them that the sequence number has changed.
 160   ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number,
 161                                              new_sequence_number);
 162
 163   // We keep the old packet in the unacked packet list until it, or one of
 164   // the retransmissions of it are acked.
 165   unacked_it->second.retransmittable_frames = NULL;
 166   unacked_packets_[new_sequence_number] =
 167       TransmissionInfo(frames, GetSequenceNumberLength(old_sequence_number));
 168
 169   // Keep track of all sequence numbers that this packet
 170   // has been transmitted as.
 171   SequenceNumberSet* previous_transmissions =
 172       unacked_it->second.previous_transmissions;
 173   if (previous_transmissions == NULL) {
 174     // This is the first retransmission of this packet, so create a new entry.
 175     previous_transmissions = new SequenceNumberSet;
 176     unacked_it->second.previous_transmissions = previous_transmissions;
 177     previous_transmissions->insert(old_sequence_number);
 178   }
 179   previous_transmissions->insert(new_sequence_number);
 180   unacked_packets_[new_sequence_number].previous_transmissions =
 181       previous_transmissions;
 182
 183   DCHECK(HasRetransmittableFrames(new_sequence_number));
 184 }
 185
 186 bool QuicSentPacketManager::OnIncomingAck(
 187     const ReceivedPacketInfo& received_info, QuicTime ack_receive_time) {
 188   // Determine if the least unacked sequence number is being acked.
 189   QuicPacketSequenceNumber least_unacked_sent_before =
 190       GetLeastUnackedSentPacket();
 191   // TODO(ianswett): Consider a non-TCP metric for determining the connection
 192   // is making progress, since QUIC has out of order delivery.
 193   bool new_least_unacked = !IsAwaitingPacket(received_info,
 194                                              least_unacked_sent_before);
 195
 196   MaybeUpdateRTT(received_info, ack_receive_time);
 197   HandleAckForSentPackets(received_info);
 198   MaybeRetransmitOnAckFrame(received_info, ack_receive_time);
 199
 200   if (new_least_unacked) {
 201     // Reset all retransmit counters any time a new packet is acked.
 202     consecutive_rto_count_ = 0;
 203     consecutive_tlp_count_ = 0;
 204     consecutive_crypto_retransmission_count_ = 0;
 205   }
 206
 207   // Always reset the retransmission alarm when an ack comes in, since we now
 208   // have a better estimate of the current rtt than when it was set.
 209   return true;
 210 }
 211
 212 void QuicSentPacketManager::DiscardUnackedPacket(
 213     QuicPacketSequenceNumber sequence_number) {
 214   MarkPacketHandled(sequence_number, NOT_RECEIVED_BY_PEER);
 215 }
 216
 217 void QuicSentPacketManager::HandleAckForSentPackets(
 218     const ReceivedPacketInfo& received_info) {
 219   // Go through the packets we have not received an ack for and see if this
 220   // incoming_ack shows they've been seen by the peer.
 221   UnackedPacketMap::iterator it = unacked_packets_.begin();
 222   while (it != unacked_packets_.end()) {
 223     QuicPacketSequenceNumber sequence_number = it->first;
 224     if (sequence_number > received_info.largest_observed) {
 225       // These are very new sequence_numbers.
 226       break;
 227     }
 228
 229     if (IsAwaitingPacket(received_info, sequence_number)) {
 230       ++it;
 231       continue;
 232     }
 233
 234     // Packet was acked, so remove it from our unacked packet list.
 235     DVLOG(1) << ENDPOINT <<"Got an ack for packet " << sequence_number;
 236     // If data is associated with the most recent transmission of this
 237     // packet, then inform the caller.
 238     it = MarkPacketHandled(sequence_number, RECEIVED_BY_PEER);
 239
 240     // The AckNotifierManager is informed of every ACKed sequence number.
 241     ack_notifier_manager_.OnPacketAcked(sequence_number);
 242   }
 243
 244   // If we have received a truncated ack, then we need to
 245   // clear out some previous transmissions to allow the peer
 246   // to actually ACK new packets.
 247   if (received_info.is_truncated) {
 248     ClearPreviousRetransmissions(received_info.missing_packets.size() / 2);
 249   }
 250 }
 251
 252 void QuicSentPacketManager::ClearPreviousRetransmissions(size_t num_to_clear) {
 253   UnackedPacketMap::iterator it = unacked_packets_.begin();
 254   while (it != unacked_packets_.end() && num_to_clear > 0) {
 255     QuicPacketSequenceNumber sequence_number = it->first;
 256     // If this is not a previous transmission then there is no point
 257     // in clearing out any further packets, because it will not affect
 258     // the high water mark.
 259     SequenceNumberSet* previous_transmissions =
 260         it->second.previous_transmissions;
 261     if (previous_transmissions == NULL) {
 262       break;
 263     }
 264     QuicPacketSequenceNumber newest_transmission =
 265         *previous_transmissions->rbegin();
 266     if (sequence_number == newest_transmission) {
 267       break;
 268     }
 269
 270     DCHECK(it->second.retransmittable_frames == NULL);
 271     previous_transmissions->erase(sequence_number);
 272     if (previous_transmissions->size() == 1) {
 273       unacked_packets_[newest_transmission].previous_transmissions = NULL;
 274       delete previous_transmissions;
 275     }
 276     DCHECK(!ContainsKey(pending_packets_, it->first));
 277     unacked_packets_.erase(it++);
 278     --num_to_clear;
 279   }
 280 }
 281
 282 bool QuicSentPacketManager::HasRetransmittableFrames(
 283     QuicPacketSequenceNumber sequence_number) const {
 284   UnackedPacketMap::const_iterator it = unacked_packets_.find(sequence_number);
 285   if (it == unacked_packets_.end()) {
 286     return false;
 287   }
 288   const TransmissionInfo* transmission_info = &it->second;
 289   DCHECK(transmission_info);
 290
 291   return transmission_info->retransmittable_frames != NULL;
 292 }
 293
 294 void QuicSentPacketManager::RetransmitUnackedPackets(
 295     RetransmissionType retransmission_type) {
 296   if (unacked_packets_.empty()) {
 297     return;
 298   }
 299
 300   for (UnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
 301        unacked_it != unacked_packets_.end(); ++unacked_it) {
 302     const RetransmittableFrames* frames =
 303         unacked_it->second.retransmittable_frames;
 304     if (frames == NULL) {
 305       continue;
 306     }
 307     if (retransmission_type == ALL_PACKETS ||
 308         frames->encryption_level() == ENCRYPTION_INITIAL) {
 309       // TODO(satyamshekhar): Think about congestion control here.
 310       // Specifically, about the retransmission count of packets being sent
 311       // proactively to achieve 0 (minimal) RTT.
 312       if (unacked_it->second.retransmittable_frames) {
 313         OnPacketAbandoned(unacked_it->first);
 314         MarkForRetransmission(unacked_it->first, NACK_RETRANSMISSION);
 315       } else {
 316         DiscardUnackedPacket(unacked_it->first);
 317       }
 318     }
 319   }
 320 }
 321
 322 void QuicSentPacketManager::MarkForRetransmission(
 323     QuicPacketSequenceNumber sequence_number,
 324     TransmissionType transmission_type) {
 325   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 326   DCHECK(HasRetransmittableFrames(sequence_number));
 327   // TODO(ianswett): Currently the RTO can fire while there are pending NACK
 328   // retransmissions for the same data, which is not ideal.
 329   if (ContainsKey(pending_retransmissions_, sequence_number)) {
 330     return;
 331   }
 332
 333   pending_retransmissions_[sequence_number] = transmission_type;
 334 }
 335
 336 bool QuicSentPacketManager::HasPendingRetransmissions() const {
 337   return !pending_retransmissions_.empty();
 338 }
 339
 340 QuicSentPacketManager::PendingRetransmission
 341     QuicSentPacketManager::NextPendingRetransmission() {
 342   DCHECK(!pending_retransmissions_.empty());
 343   QuicPacketSequenceNumber sequence_number =
 344       pending_retransmissions_.begin()->first;
 345   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 346   const RetransmittableFrames* retransmittable_frames =
 347       unacked_packets_[sequence_number].retransmittable_frames;
 348   DCHECK(retransmittable_frames);
 349
 350   return PendingRetransmission(sequence_number,
 351                                pending_retransmissions_.begin()->second,
 352                                *retransmittable_frames,
 353                                GetSequenceNumberLength(sequence_number));
 354 }
 355
 356 bool QuicSentPacketManager::IsPreviousTransmission(
 357     QuicPacketSequenceNumber sequence_number) const {
 358   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 359
 360   UnackedPacketMap::const_iterator it = unacked_packets_.find(sequence_number);
 361   if (it->second.previous_transmissions == NULL) {
 362     return false;
 363   }
 364
 365   SequenceNumberSet* previous_transmissions = it->second.previous_transmissions;
 366   DCHECK(!previous_transmissions->empty());
 367   return *previous_transmissions->rbegin() != sequence_number;
 368 }
 369
 370 // static
 371 bool QuicSentPacketManager::HasCryptoHandshake(
 372     const TransmissionInfo& transmission_info) {
 373   if (transmission_info.retransmittable_frames == NULL) {
 374     return false;
 375   }
 376   return transmission_info.retransmittable_frames->HasCryptoHandshake() ==
 377       IS_HANDSHAKE;
 378 }
 379
 380 QuicSentPacketManager::UnackedPacketMap::iterator
 381 QuicSentPacketManager::MarkPacketHandled(
 382     QuicPacketSequenceNumber sequence_number, ReceivedByPeer received_by_peer) {
 383   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 384
 385   // If this packet is pending, remove it and inform the send algorithm.
 386   if (pending_packets_.erase(sequence_number)) {
 387     size_t bytes_sent = packet_history_map_[sequence_number]->bytes_sent();
 388     if (received_by_peer == RECEIVED_BY_PEER) {
 389       send_algorithm_->OnPacketAcked(sequence_number, bytes_sent, rtt_sample_);
 390     } else {
 391       // It's been abandoned.
 392       send_algorithm_->OnPacketAbandoned(sequence_number, bytes_sent);
 393     }
 394   }
 395
 396   // If this packet has never been retransmitted, then simply drop it.
 397   UnackedPacketMap::iterator previous_it =
 398       unacked_packets_.find(sequence_number);
 399   if (previous_it->second.previous_transmissions == NULL) {
 400     ++previous_it;
 401     DiscardPacket(sequence_number);
 402     return previous_it;
 403   }
 404
 405   SequenceNumberSet* previous_transmissions =
 406       previous_it->second.previous_transmissions;
 407   DCHECK(!previous_transmissions->empty());
 408   SequenceNumberSet::reverse_iterator previous_transmissions_it =
 409       previous_transmissions->rbegin();
 410   QuicPacketSequenceNumber newest_transmission = *previous_transmissions_it;
 411   if (newest_transmission == sequence_number) {
 412     DiscardPacket(newest_transmission);
 413   } else {
 414     UnackedPacketMap::iterator newest_it =
 415         unacked_packets_.find(newest_transmission);
 416     if (HasCryptoHandshake(newest_it->second)) {
 417       --pending_crypto_packet_count_;
 418     }
 419     // If we have received an ack for a previous transmission of a packet,
 420     // we want to keep the "new" transmission of the packet unacked,
 421     // but prevent the data from being retransmitted.
 422     delete newest_it->second.retransmittable_frames;
 423     newest_it->second.retransmittable_frames = NULL;
 424     newest_it->second.previous_transmissions = NULL;
 425     pending_retransmissions_.erase(newest_transmission);
 426   }
 427
 428   // Clear out information all previous transmissions.
 429   ++previous_transmissions_it;
 430   while (previous_transmissions_it != previous_transmissions->rend()) {
 431     QuicPacketSequenceNumber previous_transmission = *previous_transmissions_it;
 432     ++previous_transmissions_it;
 433     // If the packet was TLP retransmitted, the old copy was not yet considered
 434     // lost or abandoned, so do that now.
 435     if (ContainsKey(pending_packets_, previous_transmission)) {
 436       send_algorithm_->OnPacketLost(previous_transmission, clock_->Now());
 437       OnPacketAbandoned(previous_transmission);
 438     }
 439     DiscardPacket(previous_transmission);
 440   }
 441
 442   delete previous_transmissions;
 443
 444   UnackedPacketMap::iterator next_unacked = unacked_packets_.begin();
 445   while (next_unacked != unacked_packets_.end() &&
 446          next_unacked->first < sequence_number) {
 447     ++next_unacked;
 448   }
 449   return next_unacked;
 450 }
 451
 452 void QuicSentPacketManager::DiscardPacket(
 453     QuicPacketSequenceNumber sequence_number) {
 454   UnackedPacketMap::iterator unacked_it =
 455       unacked_packets_.find(sequence_number);
 456   DCHECK(unacked_it != unacked_packets_.end());
 457   // Ensure the packet is no longer pending when it's discarded.
 458   DCHECK(!ContainsKey(pending_packets_, sequence_number));
 459
 460   RetransmittableFrames* retransmittable_frames =
 461       unacked_it->second.retransmittable_frames;
 462   if (HasCryptoHandshake(unacked_it->second)) {
 463     --pending_crypto_packet_count_;
 464   }
 465
 466   // Delete the retransmittable frames.
 467   delete retransmittable_frames;
 468   unacked_packets_.erase(unacked_it);
 469   pending_retransmissions_.erase(sequence_number);
 470   return;
 471 }
 472
 473 bool QuicSentPacketManager::IsUnacked(
 474     QuicPacketSequenceNumber sequence_number) const {
 475   return ContainsKey(unacked_packets_, sequence_number);
 476 }
 477
 478 QuicSequenceNumberLength QuicSentPacketManager::GetSequenceNumberLength(
 479     QuicPacketSequenceNumber sequence_number) const {
 480   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 481
 482   return unacked_packets_.find(sequence_number)->second.sequence_number_length;
 483 }
 484
 485 bool QuicSentPacketManager::HasUnackedPackets() const {
 486   return !unacked_packets_.empty();
 487 }
 488
 489 size_t QuicSentPacketManager::GetNumRetransmittablePackets() const {
 490   size_t num_unacked_packets = 0;
 491   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 492        it != unacked_packets_.end(); ++it) {
 493     QuicPacketSequenceNumber sequence_number = it->first;
 494     if (HasRetransmittableFrames(sequence_number)) {
 495       ++num_unacked_packets;
 496     }
 497   }
 498   return num_unacked_packets;
 499 }
 500
 501 QuicPacketSequenceNumber
 502 QuicSentPacketManager::GetLeastUnackedSentPacket() const {
 503   if (unacked_packets_.empty()) {
 504     // If there are no unacked packets, set the least unacked packet to
 505     // the sequence number of the next packet sent.
 506     return helper_->GetNextPacketSequenceNumber();
 507   }
 508
 509   return unacked_packets_.begin()->first;
 510 }
 511
 512 SequenceNumberSet QuicSentPacketManager::GetUnackedPackets() const {
 513   SequenceNumberSet unacked_packets;
 514   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 515        it != unacked_packets_.end(); ++it) {
 516     unacked_packets.insert(it->first);
 517   }
 518   return unacked_packets;
 519 }
 520
 521 bool QuicSentPacketManager::OnPacketSent(
 522     QuicPacketSequenceNumber sequence_number,
 523     QuicTime sent_time,
 524     QuicByteCount bytes,
 525     TransmissionType transmission_type,
 526     HasRetransmittableData has_retransmittable_data) {
 527   DCHECK_LT(0u, sequence_number);
 528   DCHECK(!ContainsKey(pending_packets_, sequence_number));
 529   DCHECK(ContainsKey(unacked_packets_, sequence_number));
 530   if (has_retransmittable_data == HAS_RETRANSMITTABLE_DATA) {
 531     DCHECK(unacked_packets_[sequence_number].retransmittable_frames);
 532   }
 533
 534   // Only track packets the send algorithm wants us to track.
 535   if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes,
 536                                      transmission_type,
 537                                      has_retransmittable_data)) {
 538     DCHECK(unacked_packets_[sequence_number].retransmittable_frames == NULL);
 539     unacked_packets_.erase(sequence_number);
 540     // Do not reset the retransmission timer, since the packet isn't tracked.
 541     return false;
 542   }
 543
 544   // Set the retransmission timer for the first pending packet.
 545   const bool set_retransmission_timer = pending_packets_.empty();
 546   unacked_packets_[sequence_number].sent_time = sent_time;
 547   packet_history_map_[sequence_number] =
 548       new SendAlgorithmInterface::SentPacket(bytes, sent_time);
 549   pending_packets_.insert(sequence_number);
 550   CleanupPacketHistory();
 551
 552   // Reset the retransmission timer anytime a packet is sent in tail loss probe
 553   // mode or before the crypto handshake has completed.
 554   return GetRetransmissionMode() != RTO_MODE || set_retransmission_timer;
 555 }
 556
 557 void QuicSentPacketManager::OnRetransmissionTimeout() {
 558   DCHECK(!pending_packets_.empty());
 559   // Handshake retransmission, TLP, and RTO are implemented with a single alarm.
 560   // The handshake alarm is set when the handshake has not completed, and the
 561   // TLP and RTO alarms are set after that.
 562   // The TLP alarm is always set to run for under an RTO.
 563   switch (GetRetransmissionMode()) {
 564     case HANDSHAKE_MODE:
 565       RetransmitCryptoPackets();
 566       return;
 567     case TLP_MODE:
 568       // If no tail loss probe can be sent, because there are no retransmittable
 569       // packets, execute a conventional RTO to abandon old packets.
 570       RetransmitOldestPacket();
 571       return;
 572     case RTO_MODE:
 573       RetransmitAllPackets();
 574       return;
 575   }
 576 }
 577
 578 void QuicSentPacketManager::RetransmitCryptoPackets() {
 579   DCHECK_EQ(HANDSHAKE_MODE, GetRetransmissionMode());
 580   // TODO(ianswett): Typical TCP implementations only retransmit 5 times.
 581   consecutive_crypto_retransmission_count_ =
 582       min(kMaxHandshakeRetransmissionBackoffs,
 583           consecutive_crypto_retransmission_count_ + 1);
 584   bool packet_retransmitted = false;
 585   for (SequenceNumberSet::iterator it = pending_packets_.begin();
 586        it != pending_packets_.end(); ) {
 587     QuicPacketSequenceNumber sequence_number = *it;
 588     DCHECK(ContainsKey(packet_history_map_, sequence_number));
 589     DCHECK(ContainsKey(unacked_packets_, sequence_number));
 590     const RetransmittableFrames* frames =
 591         unacked_packets_[sequence_number].retransmittable_frames;
 592     if (frames == NULL || frames->HasCryptoHandshake() != IS_HANDSHAKE) {
 593       ++it;
 594       continue;
 595     }
 596     packet_retransmitted = true;
 597     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
 598     // Abandon all the crypto retransmissions now so they're not lost later.
 599     send_algorithm_->OnPacketAbandoned(
 600         sequence_number, packet_history_map_[sequence_number]->bytes_sent());
 601     pending_packets_.erase(it++);
 602   }
 603   DCHECK(packet_retransmitted) << "No crypto packets found to retransmit.";
 604 }
 605
 606 void QuicSentPacketManager::RetransmitOldestPacket() {
 607   DCHECK_EQ(TLP_MODE, GetRetransmissionMode());
 608   ++consecutive_tlp_count_;
 609   for (SequenceNumberSet::const_iterator it = pending_packets_.begin();
 610        it != pending_packets_.end(); ++it) {
 611     QuicPacketSequenceNumber sequence_number = *it;
 612     DCHECK(ContainsKey(unacked_packets_, sequence_number));
 613     const RetransmittableFrames* frames =
 614         unacked_packets_[sequence_number].retransmittable_frames;
 615     if (frames == NULL) {
 616       continue;
 617     }
 618     DCHECK_NE(IS_HANDSHAKE, frames->HasCryptoHandshake());
 619     MarkForRetransmission(sequence_number, TLP_RETRANSMISSION);
 620     return;
 621   }
 622   DLOG(FATAL)
 623     << "No retransmittable packets, so RetransmitOldestPacket failed.";
 624 }
 625
 626 void QuicSentPacketManager::RetransmitAllPackets() {
 627   // Abandon all retransmittable packets and packets older than the
 628   // retransmission delay.
 629   QuicTime::Delta retransmission_delay = GetRetransmissionDelay();
 630   QuicTime max_send_time =
 631       clock_->ApproximateNow().Subtract(retransmission_delay);
 632
 633   DVLOG(1) << "OnRetransmissionTimeout() fired with "
 634            << unacked_packets_.size() << " unacked packets.";
 635
 636   // Request retransmission of all retransmittable packets when the RTO
 637   // fires, and let the congestion manager decide how many to send
 638   // immediately and the remaining packets will be queued.
 639   // Abandon any non-retransmittable packets that are sufficiently old.
 640   bool packets_retransmitted = false;
 641   for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
 642        it != unacked_packets_.end(); ++it) {
 643     if (it->second.retransmittable_frames != NULL) {
 644       OnPacketAbandoned(it->first);
 645       packets_retransmitted = true;
 646       MarkForRetransmission(it->first, RTO_RETRANSMISSION);
 647     } else if (it->second.sent_time <= max_send_time) {
 648       OnPacketAbandoned(it->first);
 649     }
 650   }
 651
 652   // Only inform the send algorithm of an RTO if data was retransmitted.
 653   if (packets_retransmitted) {
 654     ++consecutive_rto_count_;
 655     send_algorithm_->OnRetransmissionTimeout();
 656   }
 657 }
 658
 659 QuicSentPacketManager::RetransmissionTimeoutMode
 660     QuicSentPacketManager::GetRetransmissionMode() const {
 661   DCHECK(!pending_packets_.empty());
 662   if (pending_crypto_packet_count_ > 0) {
 663     return HANDSHAKE_MODE;
 664   }
 665   if (consecutive_tlp_count_ < max_tail_loss_probes_) {
 666     // Ensure there are retransmittable frames.
 667     for (SequenceNumberSet::const_iterator it = pending_packets_.begin();
 668          it != pending_packets_.end(); ++it) {
 669       if (HasRetransmittableFrames(*it)) {
 670         return TLP_MODE;
 671       }
 672     }
 673   }
 674   return RTO_MODE;
 675 }
 676
 677 void QuicSentPacketManager::OnPacketAbandoned(
 678     QuicPacketSequenceNumber sequence_number) {
 679   SequenceNumberSet::iterator it = pending_packets_.find(sequence_number);
 680   if (it != pending_packets_.end()) {
 681     DCHECK(ContainsKey(packet_history_map_, sequence_number));
 682     send_algorithm_->OnPacketAbandoned(
 683         sequence_number, packet_history_map_[sequence_number]->bytes_sent());
 684     pending_packets_.erase(it);
 685   }
 686 }
 687
 688 void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame(
 689     const QuicCongestionFeedbackFrame& frame,
 690     const QuicTime& feedback_receive_time) {
 691   send_algorithm_->OnIncomingQuicCongestionFeedbackFrame(
 692       frame, feedback_receive_time, packet_history_map_);
 693 }
 694
 695 void QuicSentPacketManager::MaybeRetransmitOnAckFrame(
 696     const ReceivedPacketInfo& received_info,
 697     const QuicTime& ack_receive_time) {
 698   // Go through all pending packets up to the largest observed and see if any
 699   // need to be retransmitted or lost.
 700   SequenceNumberSet::iterator it = pending_packets_.begin();
 701   SequenceNumberSet::iterator it_upper =
 702       pending_packets_.upper_bound(received_info.largest_observed);
 703
 704   size_t num_retransmitted = 0;
 705   SequenceNumberSet lost_packets;
 706   while (it != it_upper) {
 707     QuicPacketSequenceNumber sequence_number = *it;
 708     DVLOG(1) << "still missing packet " << sequence_number;
 709     // Acks must be handled previously, so ensure it's missing and not acked.
 710     DCHECK(IsAwaitingPacket(received_info, sequence_number));
 711     DCHECK(ContainsKey(packet_history_map_, sequence_number));
 712     const SendAlgorithmInterface::SentPacket* sent_packet =
 713         packet_history_map_[sequence_number];
 714     const TransmissionInfo& transmission_info =
 715         unacked_packets_[sequence_number];
 716
 717     // Consider it multiple nacks when there is a gap between the missing packet
 718     // and the largest observed, since the purpose of a nack threshold is to
 719     // tolerate re-ordering.  This handles both StretchAcks and Forward Acks.
 720     // TODO(ianswett): This relies heavily on sequential reception of packets,
 721     // and makes an assumption that the congestion control uses TCP style nacks.
 722     size_t min_nacks = received_info.largest_observed - sequence_number;
 723     packet_history_map_[sequence_number]->Nack(min_nacks);
 724
 725     size_t num_nacks_needed = kNumberOfNacksBeforeRetransmission;
 726     // Check for early retransmit(RFC5827) when the last packet gets acked and
 727     // the there are fewer than 4 pending packets.
 728     // TODO(ianswett): Consider setting a retransmission timer instead of
 729     // losing the packet and retransmitting immediately.  Also consider only
 730     // invoking OnPacketLost and OnPacketAbandoned when they're actually
 731     // retransmitted in case they arrive while queued.
 732     if (pending_packets_.size() <= kNumberOfNacksBeforeRetransmission &&
 733         transmission_info.retransmittable_frames &&
 734         packet_history_map_.rbegin()->first == received_info.largest_observed) {
 735       num_nacks_needed = received_info.largest_observed - sequence_number;
 736     }
 737
 738     if (sent_packet->nack_count() < num_nacks_needed) {
 739       ++it;
 740       continue;
 741     }
 742
 743     // If the number of retransmissions has maxed out, don't lose or retransmit
 744     // any more packets.
 745     if (num_retransmitted >= kMaxRetransmissionsPerAck) {
 746       ++it;
 747       continue;
 748     }
 749
 750     lost_packets.insert(sequence_number);
 751     if (transmission_info.retransmittable_frames) {
 752       ++num_retransmitted;
 753       MarkForRetransmission(*it, NACK_RETRANSMISSION);
 754     }
 755
 756     ++it;
 757   }
 758   // Abandon packets after the loop over pending packets, because otherwise it
 759   // changes the early retransmit logic and iteration.
 760   for (SequenceNumberSet::const_iterator it = lost_packets.begin();
 761        it != lost_packets.end(); ++it) {
 762     // TODO(ianswett): OnPacketLost is also called from TCPCubicSender when
 763     // an FEC packet is lost, but FEC loss information should be shared among
 764     // congestion managers.  Additionally, if it's expected the FEC packet may
 765     // repair the loss, it should be recorded as a loss to the congestion
 766     // manager, but not retransmitted until it's known whether the FEC packet
 767     // arrived.
 768     send_algorithm_->OnPacketLost(*it, ack_receive_time);
 769     OnPacketAbandoned(*it);
 770   }
 771 }
 772
 773 void QuicSentPacketManager::MaybeUpdateRTT(
 774     const ReceivedPacketInfo& received_info,
 775     const QuicTime& ack_receive_time) {
 776   // We calculate the RTT based on the highest ACKed sequence number, the lower
 777   // sequence numbers will include the ACK aggregation delay.
 778   SendAlgorithmInterface::SentPacketsMap::iterator history_it =
 779       packet_history_map_.find(received_info.largest_observed);
 780   // TODO(satyamshekhar): largest_observed might be missing.
 781   if (history_it == packet_history_map_.end()) {
 782     return;
 783   }
 784
 785   QuicTime::Delta send_delta = ack_receive_time.Subtract(
 786       history_it->second->send_timestamp());
 787   if (send_delta > received_info.delta_time_largest_observed) {
 788     rtt_sample_ = send_delta.Subtract(
 789         received_info.delta_time_largest_observed);
 790   } else if (rtt_sample_.IsInfinite()) {
 791     // Even though we received information from the peer suggesting
 792     // an invalid (negative) RTT, we can use the send delta as an
 793     // approximation until we get a better estimate.
 794     rtt_sample_ = send_delta;
 795   }
 796 }
 797
 798 QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
 799     QuicTime now,
 800     TransmissionType transmission_type,
 801     HasRetransmittableData retransmittable,
 802     IsHandshake handshake) {
 803   return send_algorithm_->TimeUntilSend(now, transmission_type, retransmittable,
 804                                         handshake);
 805 }
 806
 807 // Ensures that the Delayed Ack timer is always set to a value lesser
 808 // than the retransmission timer's minimum value (MinRTO). We want the
 809 // delayed ack to get back to the QUIC peer before the sender's
 810 // retransmission timer triggers.  Since we do not know the
 811 // reverse-path one-way delay, we assume equal delays for forward and
 812 // reverse paths, and ensure that the timer is set to less than half
 813 // of the MinRTO.
 814 // There may be a value in making this delay adaptive with the help of
 815 // the sender and a signaling mechanism -- if the sender uses a
 816 // different MinRTO, we may get spurious retransmissions. May not have
 817 // any benefits, but if the delayed ack becomes a significant source
 818 // of (likely, tail) latency, then consider such a mechanism.
 819
 820 const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() const {
 821   return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2);
 822 }
 823
 824 const QuicTime QuicSentPacketManager::GetRetransmissionTime() const {
 825   // There can't be any retransmittable packets if there are none pending.
 826   if (pending_packets_.empty()) {
 827     return QuicTime::Zero();
 828   }
 829   switch (GetRetransmissionMode()) {
 830     case HANDSHAKE_MODE:
 831       return clock_->ApproximateNow().Add(GetCryptoRetransmissionDelay());
 832     case TLP_MODE: {
 833       // TODO(ianswett): When CWND is available, it would be preferable to
 834       // set the timer based on the earliest retransmittable packet.
 835       // Base the updated timer on the send time of the last packet.
 836       QuicPacketSequenceNumber last_pending_packet = *pending_packets_.rbegin();
 837       const QuicTime& sent_time = packet_history_map_.find(
 838           last_pending_packet)->second->send_timestamp();
 839       const QuicTime tlp_time = sent_time.Add(GetTailLossProbeDelay());
 840       // Ensure the tlp timer never gets set to a time in the past.
 841       return QuicTime::Max(clock_->ApproximateNow(), tlp_time);
 842     }
 843     case RTO_MODE: {
 844       QuicPacketSequenceNumber first_pending_packet = *pending_packets_.begin();
 845       const QuicTime& sent_time = packet_history_map_.find(
 846           first_pending_packet)->second->send_timestamp();
 847       // Always wait at least 1.5 * RTT after the first sent packet.
 848       QuicTime min_timeout = clock_->ApproximateNow().Add(
 849           SmoothedRtt().Multiply(1.5));
 850       QuicTime rto_timeout = sent_time.Add(GetRetransmissionDelay());
 851
 852       return QuicTime::Max(min_timeout, rto_timeout);
 853     }
 854     default:
 855       DCHECK(false);
 856   }
 857   return QuicTime::Zero();
 858 }
 859
 860 const QuicTime::Delta
 861 QuicSentPacketManager::GetCryptoRetransmissionDelay() const {
 862   // This is equivalent to the TailLossProbeDelay, but slightly more aggressive
 863   // because crypto handshake messages don't incur a delayed ack time.
 864   int64 delay_ms = max<int64>(kMinHandshakeTimeoutMs,
 865                               1.5 * SmoothedRtt().ToMilliseconds());
 866   return QuicTime::Delta::FromMilliseconds(
 867       delay_ms << consecutive_crypto_retransmission_count_);
 868 }
 869
 870 const QuicTime::Delta QuicSentPacketManager::GetTailLossProbeDelay() const {
 871   QuicTime::Delta srtt = SmoothedRtt();
 872   if (pending_packets_.size() == 1) {
 873     return QuicTime::Delta::Max(
 874         srtt.Multiply(1.5).Add(DelayedAckTime()), srtt.Multiply(2));
 875   }
 876   return QuicTime::Delta::FromMilliseconds(
 877       max(kMinTailLossProbeTimeoutMs,
 878           static_cast<int64>(2 * srtt.ToMilliseconds())));
 879 }
 880
 881 const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
 882   size_t number_retransmissions = consecutive_rto_count_;
 883   // TODO(ianswett): Remove this flag now that EndToEndTest is no longer flaky.
 884   if (FLAGS_limit_rto_increase_for_tests) {
 885     const size_t kTailDropWindowSize = 5;
 886     const size_t kTailDropMaxRetransmissions = 4;
 887     if (pending_packets_.size() <= kTailDropWindowSize) {
 888       // Avoid exponential backoff of RTO when there are only a few packets
 889       // outstanding.  This helps avoid the situation where fake packet loss
 890       // causes a packet and it's retransmission to be dropped causing
 891       // test timouts.
 892       if (number_retransmissions <= kTailDropMaxRetransmissions) {
 893         number_retransmissions = 0;
 894       } else {
 895         number_retransmissions -= kTailDropMaxRetransmissions;
 896       }
 897     }
 898   }
 899
 900   QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
 901   if (retransmission_delay.IsZero()) {
 902     // We are in the initial state, use default timeout values.
 903     retransmission_delay =
 904         QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
 905   }
 906   // Calculate exponential back off.
 907   retransmission_delay = retransmission_delay.Multiply(
 908       1 << min<size_t>(number_retransmissions, kMaxRetransmissions));
 909
 910   // TODO(rch): This code should move to |send_algorithm_|.
 911   if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
 912     return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
 913   }
 914   if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
 915     return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
 916   }
 917   return retransmission_delay;
 918 }
 919
 920 const QuicTime::Delta QuicSentPacketManager::SmoothedRtt() const {
 921   return send_algorithm_->SmoothedRtt();
 922 }
 923
 924 QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
 925   return send_algorithm_->BandwidthEstimate();
 926 }
 927
 928 QuicByteCount QuicSentPacketManager::GetCongestionWindow() const {
 929   return send_algorithm_->GetCongestionWindow();
 930 }
 931
 932 void QuicSentPacketManager::CleanupPacketHistory() {
 933   const QuicTime::Delta kHistoryPeriod =
 934       QuicTime::Delta::FromMilliseconds(kHistoryPeriodMs);
 935   QuicTime now = clock_->ApproximateNow();
 936
 937   SendAlgorithmInterface::SentPacketsMap::iterator history_it =
 938       packet_history_map_.begin();
 939   for (; history_it != packet_history_map_.end(); ++history_it) {
 940     if (now.Subtract(history_it->second->send_timestamp()) <= kHistoryPeriod) {
 941       return;
 942     }
 943     // Don't remove packets which have not been acked.
 944     if (ContainsKey(pending_packets_, history_it->first)) {
 945       continue;
 946     }
 947     delete history_it->second;
 948     packet_history_map_.erase(history_it);
 949     history_it = packet_history_map_.begin();
 950   }
 951 }
 952
 953 void QuicSentPacketManager::MaybeEnablePacing() {
 954   if (!FLAGS_enable_quic_pacing) {
 955     return;
 956   }
 957
 958   if (using_pacing_) {
 959     return;
 960   }
 961
 962   using_pacing_ = true;
 963   send_algorithm_.reset(
 964       new PacingSender(send_algorithm_.release(),
 965                        QuicTime::Delta::FromMicroseconds(1)));
 966 }
 967
 968 }  // namespace net