net/quic/congestion_control/tcp_loss_algorithm.cc

   1 // Copyright 2014 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/congestion_control/tcp_loss_algorithm.h"
   6
   7 #include "net/quic/congestion_control/rtt_stats.h"
   8 #include "net/quic/quic_protocol.h"
   9
  10 namespace net {
  11
  12 namespace {
  13
  14 // The minimum delay before a packet will be considered lost,
  15 // regardless of SRTT.  Half of the minimum TLP, since the loss algorithm only
  16 // triggers when a nack has been receieved for the packet.
  17 static const size_t kMinLossDelayMs = 5;
  18
  19 // How many RTTs the algorithm waits before determining a packet is lost due
  20 // to early retransmission.
  21 static const double kEarlyRetransmitLossDelayMultiplier = 1.25;
  22
  23 }  // namespace
  24
  25 TCPLossAlgorithm::TCPLossAlgorithm()
  26     : loss_detection_timeout_(QuicTime::Zero()) { }
  27
  28 LossDetectionType TCPLossAlgorithm::GetLossDetectionType() const {
  29   return kNack;
  30 }
  31
  32 // Uses nack counts to decide when packets are lost.
  33 SequenceNumberSet TCPLossAlgorithm::DetectLostPackets(
  34     const QuicUnackedPacketMap& unacked_packets,
  35     const QuicTime& time,
  36     QuicPacketSequenceNumber largest_observed,
  37     const RttStats& rtt_stats) {
  38   SequenceNumberSet lost_packets;
  39   loss_detection_timeout_ = QuicTime::Zero();
  40   QuicTime::Delta early_retransmit_delay = QuicTime::Delta::Max(
  41       QuicTime::Delta::FromMilliseconds(kMinLossDelayMs),
  42       rtt_stats.smoothed_rtt().Multiply(kEarlyRetransmitLossDelayMultiplier));
  43
  44   QuicPacketSequenceNumber sequence_number = unacked_packets.GetLeastUnacked();
  45   for (QuicUnackedPacketMap::const_iterator it = unacked_packets.begin();
  46        it != unacked_packets.end() && sequence_number <= largest_observed;
  47        ++it, ++sequence_number) {
  48     if (!it->in_flight) {
  49       continue;
  50     }
  51
  52     LOG_IF(DFATAL, it->nack_count == 0 && it->sent_time.IsInitialized())
  53         << "All packets less than largest observed should have been nacked."
  54         << "sequence_number:" << sequence_number
  55         << " largest_observed:" << largest_observed;
  56     if (it->nack_count >= kNumberOfNacksBeforeRetransmission) {
  57       lost_packets.insert(sequence_number);
  58       continue;
  59     }
  60
  61     // Immediately lose the packet if it's been an srtt between the sent time
  62     // of it and the largest observed.  This speeds recovery from timer based
  63     // retransmissions, such as TLP and RTO, when there may be fewer than
  64     // kNumberOfNacksBeforeRetransmission nacks.
  65     if (it->sent_time.Add(rtt_stats.smoothed_rtt()) <
  66         unacked_packets.GetTransmissionInfo(largest_observed).sent_time) {
  67       lost_packets.insert(sequence_number);
  68       continue;
  69     }
  70
  71     // Only early retransmit(RFC5827) when the last packet gets acked and
  72     // there are retransmittable packets in flight.
  73     // This also implements a timer-protected variant of FACK.
  74     if (it->retransmittable_frames &&
  75         unacked_packets.largest_sent_packet() == largest_observed) {
  76       // Early retransmit marks the packet as lost once 1.25RTTs have passed
  77       // since the packet was sent and otherwise sets an alarm.
  78       if (time >= it->sent_time.Add(early_retransmit_delay)) {
  79         lost_packets.insert(sequence_number);
  80       } else {
  81         // Set the timeout for the earliest retransmittable packet where early
  82         // retransmit applies.
  83         loss_detection_timeout_ = it->sent_time.Add(early_retransmit_delay);
  84         break;
  85       }
  86     }
  87   }
  88
  89   return lost_packets;
  90 }
  91
  92 QuicTime TCPLossAlgorithm::GetLossTimeout() const {
  93   return loss_detection_timeout_;
  94 }
  95
  96 }  // namespace net