Add a time based loss detection algorithm to QUIC that loses packets

net/quic/congestion_control/time_loss_algorithm.cc

Index: net/quic/congestion_control/time_loss_algorithm.cc
diff --git a/net/quic/congestion_control/tcp_loss_algorithm.cc b/net/quic/congestion_control/time_loss_algorithm.cc
similarity index 31%
copy from net/quic/congestion_control/tcp_loss_algorithm.cc
copy to net/quic/congestion_control/time_loss_algorithm.cc
index 57b7ffad0c66b5c1e6556e2770dc37fb7288275d..9fde9c318f840edaa45610c206e3189aac010623 100644
--- a/net/quic/congestion_control/tcp_loss_algorithm.cc
+++ b/net/quic/congestion_control/time_loss_algorithm.cc
@@ -2,54 +2,63 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "net/quic/congestion_control/tcp_loss_algorithm.h"
+#include "net/quic/congestion_control/time_loss_algorithm.h"
 
 #include "net/quic/quic_protocol.h"
 
 namespace net {
-
 namespace {
-// TCP retransmits after 3 nacks.
-static const size_t kNumberOfNacksBeforeRetransmission = 3;
-}
 
-TCPLossAlgorithm::TCPLossAlgorithm() { }
+// The minimum delay before a packet will be considered lost,
+// regardless of SRTT.  Half of the minimum TLP, since the loss algorithm only
+// triggers when a nack has been receieved for the packet.
+static const size_t kMinLossDelayMs = 5;
+
+// How many RTTs the algorithm waits before determining a packet is lost.
+static const double kLossDelayMultiplier = 1.25;
+
+}  // namespace
 
-// Uses nack counts to decide when packets are lost.
-SequenceNumberSet TCPLossAlgorithm::DetectLostPackets(
+TimeLossAlgorithm::TimeLossAlgorithm()
+    : loss_detection_timeout_(QuicTime::Zero()) { }
+
+SequenceNumberSet TimeLossAlgorithm::DetectLostPackets(
     const QuicUnackedPacketMap& unacked_packets,
     const QuicTime& time,
     QuicPacketSequenceNumber largest_observed,
-    QuicTime::Delta srtt) {
+    QuicTime::Delta srtt,
+    QuicTime::Delta latest_rtt) {
   SequenceNumberSet lost_packets;
+  loss_detection_timeout_ = QuicTime::Zero();
+  QuicTime::Delta loss_delay = QuicTime::Delta::Max(
+      QuicTime::Delta::FromMilliseconds(kMinLossDelayMs),
+      QuicTime::Delta::Max(srtt, latest_rtt).Multiply(kLossDelayMultiplier));
 
   for (QuicUnackedPacketMap::const_iterator it = unacked_packets.begin();
        it != unacked_packets.end() && it->first <= largest_observed; ++it) {
     if (!it->second.pending) {
       continue;
     }
-    size_t num_nacks_needed = kNumberOfNacksBeforeRetransmission;
-    // Check for early retransmit(RFC5827) when the last packet gets acked and
-    // the there are fewer than 4 pending packets.
-    // TODO(ianswett): Set a retransmission timer instead of losing the packet
-    // and retransmitting immediately.
-    if (it->second.retransmittable_frames &&
-        unacked_packets.largest_sent_packet() == largest_observed) {
-      num_nacks_needed = largest_observed - it->first;
-    }
+    LOG_IF(DFATAL, it->second.nack_count == 0)
+        << "All packets less than largest observed should have been nacked.";
 
-    if (it->second.nack_count < num_nacks_needed) {
-      continue;
+    // Packets are sent in order, so break when we haven't waited long enough
+    // to lose any more packets and leave the loss_time_ set for the timeout.
+    QuicTime when_lost = it->second.sent_time.Add(loss_delay);
+    if (time < when_lost) {
+      loss_detection_timeout_ = when_lost;
+      break;
     }
-
     lost_packets.insert(it->first);
   }
 
   return lost_packets;
 }
 
-QuicTime TCPLossAlgorithm::GetLossTimeout() const {
-  return QuicTime::Zero();
+// loss_time_ is updated in DetectLostPackets, which must be called every time
+// an ack is received or the timeout expires.
+QuicTime TimeLossAlgorithm::GetLossTimeout() const {
+  return loss_detection_timeout_;
 }
 
 }  // namespace net