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