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
12using std::make_pair;
13using std::min;
14
15// TODO(rtenneti): Remove this.
16// Do not flip this flag until the flakiness of the
17// net/tools/quic/end_to_end_test is fixed.
18// If true, then QUIC connections will track the retransmission history of a
19// packet so that an ack of a previous transmission will ack the data of all
20// other transmissions.
21bool FLAGS_track_retransmission_history = false;
22
23// A test-only flag to prevent the RTO from backing off when multiple sequential
24// tail drops occur.
25bool FLAGS_limit_rto_increase_for_tests = false;
26
27// Do not remove this flag until the Finch-trials described in b/11706275
28// are complete.
29// If true, QUIC connections will support the use of a pacing algorithm when
30// sending packets, in an attempt to reduce packet loss.  The client must also
31// request pacing for the server to enable it.
32bool FLAGS_enable_quic_pacing = false;
33
34namespace net {
35namespace {
36static const int kBitrateSmoothingPeriodMs = 1000;
37static const int kHistoryPeriodMs = 5000;
38
39static const int kDefaultRetransmissionTimeMs = 500;
40// TCP RFC calls for 1 second RTO however Linux differs from this default and
41// define the minimum RTO to 200ms, we will use the same until we have data to
42// support a higher or lower value.
43static const int kMinRetransmissionTimeMs = 200;
44static const int kMaxRetransmissionTimeMs = 60000;
45static const size_t kMaxRetransmissions = 10;
46
47// We only retransmit 2 packets per ack.
48static const size_t kMaxRetransmissionsPerAck = 2;
49
50// TCP retransmits after 3 nacks.
51static const size_t kNumberOfNacksBeforeRetransmission = 3;
52
53COMPILE_ASSERT(kHistoryPeriodMs >= kBitrateSmoothingPeriodMs,
54               history_must_be_longer_or_equal_to_the_smoothing_period);
55}  // namespace
56
57#define ENDPOINT (is_server_ ? "Server: " : " Client: ")
58
59QuicSentPacketManager::HelperInterface::~HelperInterface() {
60}
61
62QuicSentPacketManager::QuicSentPacketManager(bool is_server,
63                                             HelperInterface* helper,
64                                             const QuicClock* clock,
65                                             CongestionFeedbackType type)
66    : is_server_(is_server),
67      helper_(helper),
68      clock_(clock),
69      send_algorithm_(SendAlgorithmInterface::Create(clock, type)),
70      rtt_sample_(QuicTime::Delta::Infinite()),
71      consecutive_rto_count_(0),
72      using_pacing_(false) {
73}
74
75QuicSentPacketManager::~QuicSentPacketManager() {
76  for (UnackedPacketMap::iterator it = unacked_packets_.begin();
77       it != unacked_packets_.end(); ++it) {
78    delete it->second.retransmittable_frames;
79    // Only delete previous_transmissions once, for the newest packet.
80    if (it->second.previous_transmissions != NULL &&
81        it->first == *it->second.previous_transmissions->rbegin()) {
82      delete it->second.previous_transmissions;
83    }
84  }
85  STLDeleteValues(&packet_history_map_);
86}
87
88void QuicSentPacketManager::SetFromConfig(const QuicConfig& config) {
89  if (config.initial_round_trip_time_us() > 0 &&
90      rtt_sample_.IsInfinite()) {
91    // The initial rtt should already be set on the client side.
92    DVLOG_IF(1, !is_server_)
93        << "Client did not set an initial RTT, but did negotiate one.";
94    rtt_sample_ =
95        QuicTime::Delta::FromMicroseconds(config.initial_round_trip_time_us());
96  }
97  if (config.congestion_control() == kPACE) {
98    MaybeEnablePacing();
99  }
100  send_algorithm_->SetFromConfig(config, is_server_);
101}
102
103void QuicSentPacketManager::SetMaxPacketSize(QuicByteCount max_packet_size) {
104  send_algorithm_->SetMaxPacketSize(max_packet_size);
105}
106
107void QuicSentPacketManager::OnSerializedPacket(
108    const SerializedPacket& serialized_packet) {
109  if (serialized_packet.retransmittable_frames == NULL &&
110      !serialized_packet.packet->is_fec_packet()) {
111    // Don't track ack/congestion feedback packets.
112    return;
113  }
114
115  ack_notifier_manager_.OnSerializedPacket(serialized_packet);
116
117  DCHECK(unacked_packets_.empty() ||
118         unacked_packets_.rbegin()->first < serialized_packet.sequence_number);
119  unacked_packets_[serialized_packet.sequence_number] =
120      TransmissionInfo(serialized_packet.retransmittable_frames,
121                       serialized_packet.sequence_number_length);
122}
123
124void QuicSentPacketManager::OnRetransmittedPacket(
125    QuicPacketSequenceNumber old_sequence_number,
126    QuicPacketSequenceNumber new_sequence_number) {
127  DCHECK(ContainsKey(unacked_packets_, old_sequence_number));
128  DCHECK(ContainsKey(pending_retransmissions_, old_sequence_number));
129  DCHECK(unacked_packets_.empty() ||
130         unacked_packets_.rbegin()->first < new_sequence_number);
131
132  pending_retransmissions_.erase(old_sequence_number);
133
134  UnackedPacketMap::iterator unacked_it =
135      unacked_packets_.find(old_sequence_number);
136  RetransmittableFrames* frames = unacked_it->second.retransmittable_frames;
137  DCHECK(frames);
138
139  // A notifier may be waiting to hear about ACKs for the original sequence
140  // number. Inform them that the sequence number has changed.
141  ack_notifier_manager_.UpdateSequenceNumber(old_sequence_number,
142                                             new_sequence_number);
143
144  // We keep the old packet in the unacked packet list until it, or one of
145  // the retransmissions of it are acked.
146  unacked_it->second.retransmittable_frames = NULL;
147  unacked_packets_[new_sequence_number] =
148      TransmissionInfo(frames, GetSequenceNumberLength(old_sequence_number));
149
150  // Keep track of all sequence numbers that this packet
151  // has been transmitted as.
152  SequenceNumberSet* previous_transmissions =
153      unacked_it->second.previous_transmissions;
154  if (previous_transmissions == NULL) {
155    // This is the first retransmission of this packet, so create a new entry.
156    previous_transmissions = new SequenceNumberSet;
157    unacked_it->second.previous_transmissions = previous_transmissions;
158    previous_transmissions->insert(old_sequence_number);
159  }
160  previous_transmissions->insert(new_sequence_number);
161  unacked_packets_[new_sequence_number].previous_transmissions =
162      previous_transmissions;
163
164  DCHECK(HasRetransmittableFrames(new_sequence_number));
165}
166
167bool QuicSentPacketManager::OnIncomingAck(
168    const ReceivedPacketInfo& received_info, QuicTime ack_receive_time) {
169  // Determine if the least unacked sequence number is being acked.
170  QuicPacketSequenceNumber least_unacked_sent_before =
171      GetLeastUnackedSentPacket();
172  bool new_least_unacked = !IsAwaitingPacket(received_info,
173                                             least_unacked_sent_before);
174
175  HandleAckForSentPackets(received_info);
176
177  SequenceNumberSet retransmission_packets =
178      OnIncomingAckFrame(received_info, ack_receive_time);
179
180  for (SequenceNumberSet::const_iterator it = retransmission_packets.begin();
181       it != retransmission_packets.end(); ++it) {
182    DCHECK(!ContainsKey(pending_packets_, *it));
183    MarkForRetransmission(*it, NACK_RETRANSMISSION);
184  }
185
186  if (new_least_unacked) {
187    consecutive_rto_count_ = 0;
188  }
189
190  return new_least_unacked;
191}
192
193void QuicSentPacketManager::DiscardUnackedPacket(
194    QuicPacketSequenceNumber sequence_number) {
195  MarkPacketReceivedByPeer(sequence_number);
196}
197
198void QuicSentPacketManager::HandleAckForSentPackets(
199    const ReceivedPacketInfo& received_info) {
200  // Go through the packets we have not received an ack for and see if this
201  // incoming_ack shows they've been seen by the peer.
202  UnackedPacketMap::iterator it = unacked_packets_.begin();
203  while (it != unacked_packets_.end()) {
204    QuicPacketSequenceNumber sequence_number = it->first;
205    if (sequence_number > received_info.largest_observed) {
206      // These are very new sequence_numbers.
207      break;
208    }
209
210    if (IsAwaitingPacket(received_info, sequence_number)) {
211      ++it;
212      continue;
213    }
214
215    // Packet was acked, so remove it from our unacked packet list.
216    DVLOG(1) << ENDPOINT <<"Got an ack for packet " << sequence_number;
217    // If data is associated with the most recent transmission of this
218    // packet, then inform the caller.
219    it = MarkPacketReceivedByPeer(sequence_number);
220
221    // The AckNotifierManager is informed of every ACKed sequence number.
222    ack_notifier_manager_.OnPacketAcked(sequence_number);
223  }
224
225  // If we have received a truncated ack, then we need to
226  // clear out some previous transmissions to allow the peer
227  // to actually ACK new packets.
228  if (received_info.is_truncated) {
229    ClearPreviousRetransmissions(received_info.missing_packets.size() / 2);
230  }
231}
232
233void QuicSentPacketManager::ClearPreviousRetransmissions(size_t num_to_clear) {
234  UnackedPacketMap::iterator it = unacked_packets_.begin();
235  while (it != unacked_packets_.end() && num_to_clear > 0) {
236    QuicPacketSequenceNumber sequence_number = it->first;
237    // If this is not a previous transmission then there is no point
238    // in clearing out any further packets, because it will not affect
239    // the high water mark.
240    SequenceNumberSet* previous_transmissions =
241        it->second.previous_transmissions;
242    if (previous_transmissions == NULL) {
243      break;
244    }
245    QuicPacketSequenceNumber newest_transmission =
246        *previous_transmissions->rbegin();
247    if (sequence_number == newest_transmission) {
248      break;
249    }
250
251    DCHECK(it->second.retransmittable_frames == NULL);
252    previous_transmissions->erase(sequence_number);
253    if (previous_transmissions->size() == 1) {
254      unacked_packets_[newest_transmission].previous_transmissions = NULL;
255      delete previous_transmissions;
256    }
257    unacked_packets_.erase(it++);
258    --num_to_clear;
259  }
260}
261
262bool QuicSentPacketManager::HasRetransmittableFrames(
263    QuicPacketSequenceNumber sequence_number) const {
264  if (!ContainsKey(unacked_packets_, sequence_number)) {
265    return false;
266  }
267
268  return unacked_packets_.find(
269      sequence_number)->second.retransmittable_frames != NULL;
270}
271
272void QuicSentPacketManager::RetransmitUnackedPackets(
273    RetransmissionType retransmission_type) {
274  if (unacked_packets_.empty()) {
275    return;
276  }
277
278  for (UnackedPacketMap::const_iterator unacked_it = unacked_packets_.begin();
279       unacked_it != unacked_packets_.end(); ++unacked_it) {
280    const RetransmittableFrames* frames =
281        unacked_it->second.retransmittable_frames;
282    if (frames == NULL) {
283      continue;
284    }
285    if (retransmission_type == ALL_PACKETS ||
286        frames->encryption_level() == ENCRYPTION_INITIAL) {
287      // TODO(satyamshekhar): Think about congestion control here.
288      // Specifically, about the retransmission count of packets being sent
289      // proactively to achieve 0 (minimal) RTT.
290      OnPacketAbandoned(unacked_it->first);
291      if (!MarkForRetransmission(unacked_it->first, NACK_RETRANSMISSION)) {
292        DiscardUnackedPacket(unacked_it->first);
293      }
294    }
295  }
296}
297
298bool QuicSentPacketManager::MarkForRetransmission(
299    QuicPacketSequenceNumber sequence_number,
300    TransmissionType transmission_type) {
301  DCHECK(ContainsKey(unacked_packets_, sequence_number));
302  if (!HasRetransmittableFrames(sequence_number)) {
303    return false;
304  }
305  // If it's already in the retransmission map, don't add it again, just let
306  // the prior retransmission request win out.
307  if (ContainsKey(pending_retransmissions_, sequence_number)) {
308    return true;
309  }
310
311  pending_retransmissions_[sequence_number] = transmission_type;
312  return true;
313}
314
315bool QuicSentPacketManager::HasPendingRetransmissions() const {
316  return !pending_retransmissions_.empty();
317}
318
319QuicSentPacketManager::PendingRetransmission
320    QuicSentPacketManager::NextPendingRetransmission() {
321  DCHECK(!pending_retransmissions_.empty());
322  QuicPacketSequenceNumber sequence_number =
323      pending_retransmissions_.begin()->first;
324  DCHECK(ContainsKey(unacked_packets_, sequence_number));
325  const RetransmittableFrames* retransmittable_frames =
326      unacked_packets_[sequence_number].retransmittable_frames;
327  DCHECK(retransmittable_frames);
328
329  return PendingRetransmission(sequence_number,
330                               pending_retransmissions_.begin()->second,
331                               *retransmittable_frames,
332                               GetSequenceNumberLength(sequence_number));
333}
334
335bool QuicSentPacketManager::IsPreviousTransmission(
336    QuicPacketSequenceNumber sequence_number) const {
337  DCHECK(ContainsKey(unacked_packets_, sequence_number));
338
339  UnackedPacketMap::const_iterator it = unacked_packets_.find(sequence_number);
340  if (it->second.previous_transmissions == NULL) {
341    return false;
342  }
343
344  SequenceNumberSet* previous_transmissions = it->second.previous_transmissions;
345  DCHECK(!previous_transmissions->empty());
346  return *previous_transmissions->rbegin() != sequence_number;
347}
348
349QuicSentPacketManager::UnackedPacketMap::iterator
350QuicSentPacketManager::MarkPacketReceivedByPeer(
351    QuicPacketSequenceNumber sequence_number) {
352  DCHECK(ContainsKey(unacked_packets_, sequence_number));
353
354  // If this packet has never been retransmitted, then simply drop it.
355  UnackedPacketMap::const_iterator previous_it =
356      unacked_packets_.find(sequence_number);
357  if (previous_it->second.previous_transmissions == NULL) {
358    UnackedPacketMap::iterator next_unacked =
359        unacked_packets_.find(sequence_number);
360    ++next_unacked;
361    DiscardPacket(sequence_number);
362    return next_unacked;
363  }
364
365  SequenceNumberSet* previous_transmissions =
366      previous_it->second.previous_transmissions;
367  DCHECK(!previous_transmissions->empty());
368  SequenceNumberSet::reverse_iterator previous_transmissions_it =
369      previous_transmissions->rbegin();
370  QuicPacketSequenceNumber newest_transmission = *previous_transmissions_it;
371  if (newest_transmission == sequence_number) {
372    DiscardPacket(newest_transmission);
373  } else {
374    // If we have received an ack for a previous transmission of a packet,
375    // we want to keep the "new" transmission of the packet unacked,
376    // but prevent the data from being retransmitted.
377    delete unacked_packets_[newest_transmission].retransmittable_frames;
378    unacked_packets_[newest_transmission].retransmittable_frames = NULL;
379    unacked_packets_[newest_transmission].previous_transmissions = NULL;
380    pending_retransmissions_.erase(newest_transmission);
381  }
382
383  // Clear out information all previous transmissions.
384  ++previous_transmissions_it;
385  while (previous_transmissions_it != previous_transmissions->rend()) {
386    QuicPacketSequenceNumber previous_transmission = *previous_transmissions_it;
387    ++previous_transmissions_it;
388    DiscardPacket(previous_transmission);
389  }
390
391  delete previous_transmissions;
392
393  UnackedPacketMap::iterator next_unacked = unacked_packets_.begin();
394  while (next_unacked != unacked_packets_.end() &&
395         next_unacked->first < sequence_number) {
396    ++next_unacked;
397  }
398  return next_unacked;
399}
400
401void QuicSentPacketManager::DiscardPacket(
402    QuicPacketSequenceNumber sequence_number) {
403  UnackedPacketMap::iterator unacked_it =
404      unacked_packets_.find(sequence_number);
405  // Packet was not meant to be retransmitted.
406  if (unacked_it == unacked_packets_.end()) {
407    return;
408  }
409
410  // Delete the retransmittable frames.
411  delete unacked_it->second.retransmittable_frames;
412  unacked_packets_.erase(unacked_it);
413  pending_retransmissions_.erase(sequence_number);
414  return;
415}
416
417bool QuicSentPacketManager::IsUnacked(
418    QuicPacketSequenceNumber sequence_number) const {
419  return ContainsKey(unacked_packets_, sequence_number);
420}
421
422QuicSequenceNumberLength QuicSentPacketManager::GetSequenceNumberLength(
423    QuicPacketSequenceNumber sequence_number) const {
424  DCHECK(ContainsKey(unacked_packets_, sequence_number));
425
426  return unacked_packets_.find(sequence_number)->second.sequence_number_length;
427}
428
429bool QuicSentPacketManager::HasUnackedPackets() const {
430  return !unacked_packets_.empty();
431}
432
433size_t QuicSentPacketManager::GetNumRetransmittablePackets() const {
434  size_t num_unacked_packets = 0;
435  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
436       it != unacked_packets_.end(); ++it) {
437    QuicPacketSequenceNumber sequence_number = it->first;
438    if (HasRetransmittableFrames(sequence_number)) {
439      ++num_unacked_packets;
440    }
441  }
442  return num_unacked_packets;
443}
444
445QuicPacketSequenceNumber
446QuicSentPacketManager::GetLeastUnackedSentPacket() const {
447  if (unacked_packets_.empty()) {
448    // If there are no unacked packets, set the least unacked packet to
449    // the sequence number of the next packet sent.
450    return helper_->GetNextPacketSequenceNumber();
451  }
452
453  return unacked_packets_.begin()->first;
454}
455
456SequenceNumberSet QuicSentPacketManager::GetUnackedPackets() const {
457  SequenceNumberSet unacked_packets;
458  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
459       it != unacked_packets_.end(); ++it) {
460    unacked_packets.insert(it->first);
461  }
462  return unacked_packets;
463}
464
465void QuicSentPacketManager::OnPacketSent(
466    QuicPacketSequenceNumber sequence_number,
467    QuicTime sent_time,
468    QuicByteCount bytes,
469    TransmissionType transmission_type,
470    HasRetransmittableData has_retransmittable_data) {
471  DCHECK_LT(0u, sequence_number);
472  DCHECK(!ContainsKey(pending_packets_, sequence_number));
473  if (ContainsKey(unacked_packets_, sequence_number)) {
474    unacked_packets_[sequence_number].sent_time = sent_time;
475  }
476
477  // Only track packets the send algorithm wants us to track.
478  if (!send_algorithm_->OnPacketSent(sent_time, sequence_number, bytes,
479                                     transmission_type,
480                                     has_retransmittable_data)) {
481    return;
482  }
483  packet_history_map_[sequence_number] = new SendAlgorithmInterface::SentPacket(
484      bytes, sent_time, has_retransmittable_data);
485  pending_packets_.insert(sequence_number);
486  CleanupPacketHistory();
487}
488
489void QuicSentPacketManager::OnRetransmissionTimeout() {
490  // Abandon all pending packets to ensure the congestion window
491  // opens up before we attempt to retransmit packets.
492  QuicTime::Delta retransmission_delay = GetRetransmissionDelay();
493  QuicTime max_send_time =
494      clock_->ApproximateNow().Subtract(retransmission_delay);
495  for (SequenceNumberSet::iterator it = pending_packets_.begin();
496       it != pending_packets_.end();) {
497    QuicPacketSequenceNumber sequence_number = *it;
498    DCHECK(ContainsKey(packet_history_map_, sequence_number));
499    DCHECK(ContainsKey(unacked_packets_, sequence_number));
500    const TransmissionInfo& transmission_info =
501        unacked_packets_.find(sequence_number)->second;
502    // Abandon retransmittable packet and old non-retransmittable packets.
503    if (transmission_info.retransmittable_frames ||
504        transmission_info.sent_time <= max_send_time) {
505      pending_packets_.erase(it++);
506      send_algorithm_->OnPacketAbandoned(
507          sequence_number, packet_history_map_[sequence_number]->bytes_sent());
508    } else {
509      ++it;
510    }
511  }
512
513  // Attempt to send all the unacked packets when the RTO fires, let the
514  // congestion manager decide how many to send immediately and the remaining
515  // packets will be queued for future sending.
516  DVLOG(1) << "OnRetransmissionTimeout() fired with "
517           << unacked_packets_.size() << " unacked packets.";
518
519  // Retransmit any packet with retransmittable frames.
520  bool packets_retransmitted = false;
521  for (UnackedPacketMap::const_iterator it = unacked_packets_.begin();
522       it != unacked_packets_.end(); ++it) {
523    if (it->second.retransmittable_frames != NULL) {
524      packets_retransmitted = true;
525      MarkForRetransmission(it->first, RTO_RETRANSMISSION);
526    }
527  }
528
529  // Only inform the sent packet manager of an RTO if data was retransmitted.
530  if (packets_retransmitted) {
531    ++consecutive_rto_count_;
532    send_algorithm_->OnRetransmissionTimeout();
533  }
534}
535
536void QuicSentPacketManager::OnPacketAbandoned(
537    QuicPacketSequenceNumber sequence_number) {
538  SequenceNumberSet::iterator it = pending_packets_.find(sequence_number);
539  if (it != pending_packets_.end()) {
540    DCHECK(ContainsKey(packet_history_map_, sequence_number));
541    send_algorithm_->OnPacketAbandoned(
542        sequence_number, packet_history_map_[sequence_number]->bytes_sent());
543    pending_packets_.erase(it);
544  }
545}
546
547void QuicSentPacketManager::OnIncomingQuicCongestionFeedbackFrame(
548    const QuicCongestionFeedbackFrame& frame,
549    const QuicTime& feedback_receive_time) {
550  send_algorithm_->OnIncomingQuicCongestionFeedbackFrame(
551      frame, feedback_receive_time, packet_history_map_);
552}
553
554SequenceNumberSet QuicSentPacketManager::OnIncomingAckFrame(
555    const ReceivedPacketInfo& received_info,
556    const QuicTime& ack_receive_time) {
557  MaybeUpdateRTT(received_info, ack_receive_time);
558
559  // We want to.
560  // * Get all packets lower(including) than largest_observed
561  //   from pending_packets_.
562  // * Remove all packets no longer being waited for(ie: acked).
563  // * Send each ACK in the list to send_algorithm_.
564  SequenceNumberSet::iterator it = pending_packets_.begin();
565  SequenceNumberSet::iterator it_upper =
566      pending_packets_.upper_bound(received_info.largest_observed);
567
568  SequenceNumberSet retransmission_packets;
569  SequenceNumberSet lost_packets;
570  while (it != it_upper) {
571    QuicPacketSequenceNumber sequence_number = *it;
572    const SendAlgorithmInterface::SentPacket* sent_packet =
573        packet_history_map_[sequence_number];
574    if (!IsAwaitingPacket(received_info, sequence_number)) {
575      // Not missing, hence implicitly acked.
576      size_t bytes_sent = sent_packet->bytes_sent();
577      send_algorithm_->OnPacketAcked(sequence_number, bytes_sent, rtt_sample_);
578      pending_packets_.erase(it++);  // Must be incremented post to work.
579      continue;
580    }
581
582    // The peer got packets after this sequence number.  This is an explicit
583    // nack.
584    DVLOG(1) << "still missing packet " << sequence_number;
585    DCHECK(ContainsKey(packet_history_map_, sequence_number));
586    // Consider it multiple nacks when there is a gap between the missing packet
587    // and the largest observed, since the purpose of a nack threshold is to
588    // tolerate re-ordering.  This handles both StretchAcks and Forward Acks.
589    // TODO(ianswett): This relies heavily on sequential reception of packets,
590    // and makes an assumption that the congestion control uses TCP style nacks.
591    size_t min_nacks = received_info.largest_observed - sequence_number;
592    packet_history_map_[sequence_number]->Nack(min_nacks);
593
594    size_t num_nacks_needed = kNumberOfNacksBeforeRetransmission;
595    // Check for early retransmit(RFC5827) when the last packet gets acked and
596    // the there are fewer than 4 pending packets.
597    if (pending_packets_.size() <= kNumberOfNacksBeforeRetransmission &&
598        sent_packet->has_retransmittable_data() == HAS_RETRANSMITTABLE_DATA &&
599        *pending_packets_.rbegin() == received_info.largest_observed) {
600      num_nacks_needed = received_info.largest_observed - sequence_number;
601    }
602
603    if (sent_packet->nack_count() < num_nacks_needed) {
604      ++it;
605      continue;
606    }
607
608    // If the number of retransmissions has maxed out, don't lose or retransmit
609    // any more packets.
610    if (retransmission_packets.size() >= kMaxRetransmissionsPerAck) {
611      ++it;
612      continue;
613    }
614
615    lost_packets.insert(sequence_number);
616    if (sent_packet->has_retransmittable_data() == HAS_RETRANSMITTABLE_DATA) {
617      retransmission_packets.insert(sequence_number);
618    }
619
620    ++it;
621  }
622  // Abandon packets after the loop over pending packets, because otherwise it
623  // changes the early retransmit logic and iteration.
624  for (SequenceNumberSet::const_iterator it = lost_packets.begin();
625       it != lost_packets.end(); ++it) {
626    // TODO(ianswett): OnPacketLost is also called from TCPCubicSender when
627    // an FEC packet is lost, but FEC loss information should be shared among
628    // congestion managers.  Additionally, if it's expected the FEC packet may
629    // repair the loss, it should be recorded as a loss to the congestion
630    // manager, but not retransmitted until it's known whether the FEC packet
631    // arrived.
632    send_algorithm_->OnPacketLost(*it, ack_receive_time);
633    OnPacketAbandoned(*it);
634  }
635
636  return retransmission_packets;
637}
638
639void QuicSentPacketManager::MaybeUpdateRTT(
640    const ReceivedPacketInfo& received_info,
641    const QuicTime& ack_receive_time) {
642  // We calculate the RTT based on the highest ACKed sequence number, the lower
643  // sequence numbers will include the ACK aggregation delay.
644  SendAlgorithmInterface::SentPacketsMap::iterator history_it =
645      packet_history_map_.find(received_info.largest_observed);
646  // TODO(satyamshekhar): largest_observed might be missing.
647  if (history_it == packet_history_map_.end()) {
648    return;
649  }
650
651  QuicTime::Delta send_delta = ack_receive_time.Subtract(
652      history_it->second->send_timestamp());
653  if (send_delta > received_info.delta_time_largest_observed) {
654    rtt_sample_ = send_delta.Subtract(
655        received_info.delta_time_largest_observed);
656  } else if (rtt_sample_.IsInfinite()) {
657    // Even though we received information from the peer suggesting
658    // an invalid (negative) RTT, we can use the send delta as an
659    // approximation until we get a better estimate.
660    rtt_sample_ = send_delta;
661  }
662}
663
664QuicTime::Delta QuicSentPacketManager::TimeUntilSend(
665    QuicTime now,
666    TransmissionType transmission_type,
667    HasRetransmittableData retransmittable,
668    IsHandshake handshake) {
669  return send_algorithm_->TimeUntilSend(now, transmission_type, retransmittable,
670                                        handshake);
671}
672
673// Ensures that the Delayed Ack timer is always set to a value lesser
674// than the retransmission timer's minimum value (MinRTO). We want the
675// delayed ack to get back to the QUIC peer before the sender's
676// retransmission timer triggers.  Since we do not know the
677// reverse-path one-way delay, we assume equal delays for forward and
678// reverse paths, and ensure that the timer is set to less than half
679// of the MinRTO.
680// There may be a value in making this delay adaptive with the help of
681// the sender and a signaling mechanism -- if the sender uses a
682// different MinRTO, we may get spurious retransmissions. May not have
683// any benefits, but if the delayed ack becomes a significant source
684// of (likely, tail) latency, then consider such a mechanism.
685
686const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() {
687  return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2);
688}
689
690const QuicTime::Delta QuicSentPacketManager::GetRetransmissionDelay() const {
691  size_t number_retransmissions = consecutive_rto_count_;
692  if (FLAGS_limit_rto_increase_for_tests) {
693    const size_t kTailDropWindowSize = 5;
694    const size_t kTailDropMaxRetransmissions = 4;
695    if (pending_packets_.size() <= kTailDropWindowSize) {
696      // Avoid exponential backoff of RTO when there are only a few packets
697      // outstanding.  This helps avoid the situation where fake packet loss
698      // causes a packet and it's retransmission to be dropped causing
699      // test timouts.
700      if (number_retransmissions <= kTailDropMaxRetransmissions) {
701        number_retransmissions = 0;
702      } else {
703        number_retransmissions -= kTailDropMaxRetransmissions;
704      }
705    }
706  }
707
708  QuicTime::Delta retransmission_delay = send_algorithm_->RetransmissionDelay();
709  if (retransmission_delay.IsZero()) {
710    // We are in the initial state, use default timeout values.
711    retransmission_delay =
712        QuicTime::Delta::FromMilliseconds(kDefaultRetransmissionTimeMs);
713  }
714  // Calculate exponential back off.
715  retransmission_delay = QuicTime::Delta::FromMilliseconds(
716      retransmission_delay.ToMilliseconds() * static_cast<size_t>(
717          (1 << min<size_t>(number_retransmissions, kMaxRetransmissions))));
718
719  // TODO(rch): This code should move to |send_algorithm_|.
720  if (retransmission_delay.ToMilliseconds() < kMinRetransmissionTimeMs) {
721    return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs);
722  }
723  if (retransmission_delay.ToMilliseconds() > kMaxRetransmissionTimeMs) {
724    return QuicTime::Delta::FromMilliseconds(kMaxRetransmissionTimeMs);
725  }
726  return retransmission_delay;
727}
728
729const QuicTime::Delta QuicSentPacketManager::SmoothedRtt() const {
730  return send_algorithm_->SmoothedRtt();
731}
732
733QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
734  return send_algorithm_->BandwidthEstimate();
735}
736
737QuicByteCount QuicSentPacketManager::GetCongestionWindow() const {
738  return send_algorithm_->GetCongestionWindow();
739}
740
741void QuicSentPacketManager::CleanupPacketHistory() {
742  const QuicTime::Delta kHistoryPeriod =
743      QuicTime::Delta::FromMilliseconds(kHistoryPeriodMs);
744  QuicTime now = clock_->ApproximateNow();
745
746  SendAlgorithmInterface::SentPacketsMap::iterator history_it =
747      packet_history_map_.begin();
748  for (; history_it != packet_history_map_.end(); ++history_it) {
749    if (now.Subtract(history_it->second->send_timestamp()) <= kHistoryPeriod) {
750      return;
751    }
752    // Don't remove packets which have not been acked.
753    if (ContainsKey(pending_packets_, history_it->first)) {
754      continue;
755    }
756    delete history_it->second;
757    packet_history_map_.erase(history_it);
758    history_it = packet_history_map_.begin();
759  }
760}
761
762void QuicSentPacketManager::MaybeEnablePacing() {
763  if (!FLAGS_enable_quic_pacing) {
764    return;
765  }
766
767  if (using_pacing_) {
768    return;
769  }
770
771  using_pacing_ = true;
772  send_algorithm_.reset(
773      new PacingSender(send_algorithm_.release(),
774                       QuicTime::Delta::FromMicroseconds(1)));
775}
776
777}  // namespace net
778