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::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.
21 bool 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.
25 bool 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.
32 bool FLAGS_enable_quic_pacing = false;
33
34 namespace net {
35 namespace {
36 static const int kBitrateSmoothingPeriodMs = 1000;
37 static const int kHistoryPeriodMs = 5000;
38
39 static 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.
43 static const int kMinRetransmissionTimeMs = 200;
44 static const int kMaxRetransmissionTimeMs = 60000;
45 static const size_t kMaxRetransmissions = 10;
46
47 // We only retransmit 2 packets per ack.
48 static const size_t kMaxRetransmissionsPerAck = 2;
49
50 // TCP retransmits after 3 nacks.
51 static const size_t kNumberOfNacksBeforeRetransmission = 3;
52
53 COMPILE_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
~HelperInterface()59 QuicSentPacketManager::HelperInterface::~HelperInterface() {
60 }
61
QuicSentPacketManager(bool is_server,HelperInterface * helper,const QuicClock * clock,CongestionFeedbackType type)62 QuicSentPacketManager::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
~QuicSentPacketManager()75 QuicSentPacketManager::~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
SetFromConfig(const QuicConfig & config)88 void 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
SetMaxPacketSize(QuicByteCount max_packet_size)103 void QuicSentPacketManager::SetMaxPacketSize(QuicByteCount max_packet_size) {
104 send_algorithm_->SetMaxPacketSize(max_packet_size);
105 }
106
OnSerializedPacket(const SerializedPacket & serialized_packet)107 void 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
OnRetransmittedPacket(QuicPacketSequenceNumber old_sequence_number,QuicPacketSequenceNumber new_sequence_number)124 void 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
OnIncomingAck(const ReceivedPacketInfo & received_info,QuicTime ack_receive_time)167 bool 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
DiscardUnackedPacket(QuicPacketSequenceNumber sequence_number)193 void QuicSentPacketManager::DiscardUnackedPacket(
194 QuicPacketSequenceNumber sequence_number) {
195 MarkPacketReceivedByPeer(sequence_number);
196 }
197
HandleAckForSentPackets(const ReceivedPacketInfo & received_info)198 void 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
ClearPreviousRetransmissions(size_t num_to_clear)233 void 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
HasRetransmittableFrames(QuicPacketSequenceNumber sequence_number) const262 bool 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
RetransmitUnackedPackets(RetransmissionType retransmission_type)272 void 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
MarkForRetransmission(QuicPacketSequenceNumber sequence_number,TransmissionType transmission_type)298 bool 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
HasPendingRetransmissions() const315 bool QuicSentPacketManager::HasPendingRetransmissions() const {
316 return !pending_retransmissions_.empty();
317 }
318
319 QuicSentPacketManager::PendingRetransmission
NextPendingRetransmission()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
IsPreviousTransmission(QuicPacketSequenceNumber sequence_number) const335 bool 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
349 QuicSentPacketManager::UnackedPacketMap::iterator
MarkPacketReceivedByPeer(QuicPacketSequenceNumber sequence_number)350 QuicSentPacketManager::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
DiscardPacket(QuicPacketSequenceNumber sequence_number)401 void 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
IsUnacked(QuicPacketSequenceNumber sequence_number) const417 bool QuicSentPacketManager::IsUnacked(
418 QuicPacketSequenceNumber sequence_number) const {
419 return ContainsKey(unacked_packets_, sequence_number);
420 }
421
GetSequenceNumberLength(QuicPacketSequenceNumber sequence_number) const422 QuicSequenceNumberLength 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
HasUnackedPackets() const429 bool QuicSentPacketManager::HasUnackedPackets() const {
430 return !unacked_packets_.empty();
431 }
432
GetNumRetransmittablePackets() const433 size_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
445 QuicPacketSequenceNumber
GetLeastUnackedSentPacket() const446 QuicSentPacketManager::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
GetUnackedPackets() const456 SequenceNumberSet 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
OnPacketSent(QuicPacketSequenceNumber sequence_number,QuicTime sent_time,QuicByteCount bytes,TransmissionType transmission_type,HasRetransmittableData has_retransmittable_data)465 void 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
OnRetransmissionTimeout()489 void 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
OnPacketAbandoned(QuicPacketSequenceNumber sequence_number)536 void 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
OnIncomingQuicCongestionFeedbackFrame(const QuicCongestionFeedbackFrame & frame,const QuicTime & feedback_receive_time)547 void 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
OnIncomingAckFrame(const ReceivedPacketInfo & received_info,const QuicTime & ack_receive_time)554 SequenceNumberSet 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
MaybeUpdateRTT(const ReceivedPacketInfo & received_info,const QuicTime & ack_receive_time)639 void 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
TimeUntilSend(QuicTime now,TransmissionType transmission_type,HasRetransmittableData retransmittable,IsHandshake handshake)664 QuicTime::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
DelayedAckTime()686 const QuicTime::Delta QuicSentPacketManager::DelayedAckTime() {
687 return QuicTime::Delta::FromMilliseconds(kMinRetransmissionTimeMs/2);
688 }
689
GetRetransmissionDelay() const690 const 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
SmoothedRtt() const729 const QuicTime::Delta QuicSentPacketManager::SmoothedRtt() const {
730 return send_algorithm_->SmoothedRtt();
731 }
732
BandwidthEstimate() const733 QuicBandwidth QuicSentPacketManager::BandwidthEstimate() const {
734 return send_algorithm_->BandwidthEstimate();
735 }
736
GetCongestionWindow() const737 QuicByteCount QuicSentPacketManager::GetCongestionWindow() const {
738 return send_algorithm_->GetCongestionWindow();
739 }
740
CleanupPacketHistory()741 void 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
MaybeEnablePacing()762 void 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