Home | History | Annotate | Download | only in congestion_control 
      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/time_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 namespace {
     12 
     13 // The minimum delay before a packet will be considered lost,
     14 // regardless of SRTT.  Half of the minimum TLP, since the loss algorithm only
     15 // triggers when a nack has been receieved for the packet.
     16 static const size_t kMinLossDelayMs = 5;
     17 
     18 // How many RTTs the algorithm waits before determining a packet is lost.
     19 static const double kLossDelayMultiplier = 1.25;
     20 
     21 }  // namespace
     22 
     23 TimeLossAlgorithm::TimeLossAlgorithm()
     24     : loss_detection_timeout_(QuicTime::Zero()) { }
     25 
     26 LossDetectionType TimeLossAlgorithm::GetLossDetectionType() const {
     27   return kTime;
     28 }
     29 
     30 SequenceNumberSet TimeLossAlgorithm::DetectLostPackets(
     31     const QuicUnackedPacketMap& unacked_packets,
     32     const QuicTime& time,
     33     QuicPacketSequenceNumber largest_observed,
     34     const RttStats& rtt_stats) {
     35   SequenceNumberSet lost_packets;
     36   loss_detection_timeout_ = QuicTime::Zero();
     37   QuicTime::Delta loss_delay = QuicTime::Delta::Max(
     38       QuicTime::Delta::FromMilliseconds(kMinLossDelayMs),
     39       QuicTime::Delta::Max(rtt_stats.SmoothedRtt(), rtt_stats.latest_rtt())
     40           .Multiply(kLossDelayMultiplier));
     41 
     42   QuicPacketSequenceNumber sequence_number = unacked_packets.GetLeastUnacked();
     43   for (QuicUnackedPacketMap::const_iterator it = unacked_packets.begin();
     44        it != unacked_packets.end() && sequence_number <= largest_observed;
     45        ++it, ++sequence_number) {
     46     if (!it->in_flight) {
     47       continue;
     48     }
     49     LOG_IF(DFATAL, it->nack_count == 0)
     50         << "All packets less than largest observed should have been nacked.";
     51 
     52     // Packets are sent in order, so break when we haven't waited long enough
     53     // to lose any more packets and leave the loss_time_ set for the timeout.
     54     QuicTime when_lost = it->sent_time.Add(loss_delay);
     55     if (time < when_lost) {
     56       loss_detection_timeout_ = when_lost;
     57       break;
     58     }
     59     lost_packets.insert(sequence_number);
     60   }
     61 
     62   return lost_packets;
     63 }
     64 
     65 // loss_time_ is updated in DetectLostPackets, which must be called every time
     66 // an ack is received or the timeout expires.
     67 QuicTime TimeLossAlgorithm::GetLossTimeout() const {
     68   return loss_detection_timeout_;
     69 }
     70 
     71 }  // namespace net
     72