Improve QUIC's SendAlgorithmSimulator to allow setting the delayed ack

net/quic/congestion_control/send_algorithm_simulator.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // 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/send_algorithm_simulator.h"
 
 #include <limits>
 
 #include "base/logging.h"
 #include "base/rand_util.h"
@@ skipping 30 matching lines @@
     MockClock* clock,
     QuicBandwidth bandwidth,
     QuicTime::Delta rtt)
     : clock_(clock),
       lose_next_ack_(false),
       forward_loss_rate_(0),
       reverse_loss_rate_(0),
       loss_correlation_(0),
       bandwidth_(bandwidth),
       rtt_(rtt),
-      buffer_size_(1000000) {
+      buffer_size_(1000000),
+      delayed_ack_timer_(QuicTime::Delta::FromMilliseconds(100)) {
   uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max());
   DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed;
   simple_random_.set_seed(seed);
 }
 
 SendAlgorithmSimulator::~SendAlgorithmSimulator() {}
 
 void SendAlgorithmSimulator::AddTransfer(Sender* sender, size_t num_bytes) {
   AddTransfer(sender, num_bytes, clock_->Now());
 }
@@ skipping 23 matching lines @@
     PacketEvent ack_event = NextAckEvent();
     // If both times are infinite, fire a TLP.
     if (ack_event.time_delta.IsInfinite() &&
         send_event.time_delta.IsInfinite()) {
       DVLOG(1) << "Both times are infinite, simulating a TLP.";
       // TODO(ianswett): Use a more sophisticated TLP timer or never lose
       // the last ack?
       clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
       SendDataNow(&pending_transfers_.front());
     } else if (ack_event.time_delta < send_event.time_delta) {
-      DVLOG(1) << "Handling ack, advancing time:"
+      DVLOG(1) << "Handling ack of largest observed:"
+               << ack_event.transfer->sender->next_acked << ", advancing time:"
                << ack_event.time_delta.ToMicroseconds() << "us";
       // Ack data all the data up to ack time and lose any missing sequence
       // numbers.
       clock_->AdvanceTime(ack_event.time_delta);
       HandlePendingAck(ack_event.transfer);
     } else {
       DVLOG(1) << "Sending, advancing time:"
                << send_event.time_delta.ToMicroseconds() << "us";
       clock_->AdvanceTime(send_event.time_delta);
       SendDataNow(send_event.transfer);
@@ skipping 52 matching lines @@
   return PacketEvent(ack_time, transfer);
 }
 
 QuicTime::Delta SendAlgorithmSimulator::FindNextAcked(Transfer* transfer) {
   Sender* sender = transfer->sender;
   if (sender->next_acked == sender->last_acked) {
     // Determine if the next ack is lost only once, to ensure determinism.
     lose_next_ack_ =
         reverse_loss_rate_ * kuint64max > simple_random_.RandUint64();
   }
-  bool two_acks_remaining = lose_next_ack_;
-  sender->next_acked = sender->last_acked;
-  bool packets_lost = false;
+
+  QuicPacketSequenceNumber next_acked = sender->last_acked;
+  QuicTime::Delta next_ack_delay =
+      FindNextAck(transfer, sender->last_acked, &next_acked);
+  if (lose_next_ack_) {
+    next_ack_delay = FindNextAck(transfer, next_acked, &next_acked);
+  }
+  sender->next_acked = next_acked;
+  return next_ack_delay;
+}
+
+QuicTime::Delta SendAlgorithmSimulator::FindNextAck(
+    const Transfer* transfer,
+    QuicPacketSequenceNumber last_acked,
+    QuicPacketSequenceNumber* next_acked) const {
+  *next_acked = last_acked;
+  QuicTime::Delta ack_delay = QuicTime::Delta::Infinite();
   // Remove any packets that are simulated as lost.
   for (list<SentPacket>::const_iterator it = sent_packets_.begin();
        it != sent_packets_.end(); ++it) {
     if (transfer != it->transfer) {
       continue;
     }
-
+    // Skip over any packets less than or equal to last_acked.
+    if (it->sequence_number <= last_acked) {
+      continue;
+    }
     // Lost packets don't trigger an ack.
     if (it->ack_time == QuicTime::Zero()) {
-      packets_lost = true;
       continue;
     }
+    DCHECK_LT(*next_acked, it->sequence_number);
+    // Consider a delayed ack for the current next_acked.
+    if (ack_delay < it->ack_time.Subtract(clock_->Now())) {
+      break;
+    }
+    *next_acked = it->sequence_number;
+    ack_delay = it->ack_time.Subtract(clock_->Now());
+    if (HasRecentLostPackets(transfer, *next_acked) ||
+        (*next_acked - last_acked) >= 2) {
+      break;
+    }
+    ack_delay = ack_delay.Add(delayed_ack_timer_);
+  }
+
+  DVLOG(1) << "FindNextAcked found next_acked_:"
+           << transfer->sender->next_acked
+           << " last_acked:" << transfer->sender->last_acked
+           << " ack_delay(ms):" << ack_delay.ToMilliseconds();
+  return ack_delay;
+}
+
+bool SendAlgorithmSimulator::HasRecentLostPackets(
+    const Transfer* transfer, QuicPacketSequenceNumber next_acked) const {
+  QuicPacketSequenceNumber last_packet = transfer->sender->last_acked;
+  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
+       it != sent_packets_.end() && it->sequence_number < next_acked; ++it) {
+    if (transfer != it->transfer) {
+      continue;
+    }
+    // Lost packets don't trigger an ack.
+    if (it->ack_time == QuicTime::Zero()) {
+      return true;
+    }
     // Buffer dropped packets are skipped automatically, but still end up
     // being lost and cause acks to be sent immediately.
-    if (sender->next_acked < it->sequence_number - 1) {
-      packets_lost = true;
+    if (it->sequence_number > last_packet + 1) {
+      return true;
     }
-    DCHECK_LT(sender->next_acked, it->sequence_number);
-    sender->next_acked = it->sequence_number;
-    if (packets_lost || (sender->next_acked - sender->last_acked) % 2 == 0) {
-      if (two_acks_remaining) {
-        two_acks_remaining = false;
-      } else {
-        break;
-      }
-    }
+    last_packet = it->sequence_number;
   }
-  // If the connection has no packets to be acked, return Infinite.
-  if (sender->next_acked == sender->last_acked) {
-    return QuicTime::Delta::Infinite();
-  }
-
-  QuicTime::Delta ack_time = QuicTime::Delta::Infinite();
-  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
-       it != sent_packets_.end(); ++it) {
-    if (transfer == it->transfer && sender->next_acked == it->sequence_number) {
-      ack_time = it->ack_time.Subtract(clock_->Now());
-    }
-  }
-  // If only one packet is acked, simulate a delayed ack.
-  if (!ack_time.IsInfinite() && transfer->bytes_in_flight == kPacketSize) {
-    ack_time = ack_time.Add(QuicTime::Delta::FromMilliseconds(100));
-  }
-  DVLOG(1) << "FindNextAcked found next_acked_:"
-           << transfer->sender->next_acked
-           << " last_acked:" << transfer->sender->last_acked
-           << " ack_time(ms):" << ack_time.ToMilliseconds();
-  return ack_time;
+  return false;
 }
 
 void SendAlgorithmSimulator::HandlePendingAck(Transfer* transfer) {
   Sender* sender  = transfer->sender;
   DCHECK_LT(sender->last_acked, sender->next_acked);
   SendAlgorithmInterface::CongestionMap acked_packets;
   SendAlgorithmInterface::CongestionMap lost_packets;
+  DVLOG(1) << "Acking packets from:" << sender->last_acked
+             << " to " << sender->next_acked
+             << " bytes_in_flight:" << transfer->bytes_in_flight
+             << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
   // Some entries may be missing from the sent_packets_ array, if they were
   // dropped due to buffer overruns.
   SentPacket largest_observed(0, QuicTime::Zero(), QuicTime::Zero(), NULL);
   list<SentPacket>::iterator it = sent_packets_.begin();
   while (sender->last_acked < sender->next_acked) {
     ++sender->last_acked;
     TransmissionInfo info = TransmissionInfo();
     info.bytes_sent = kPacketSize;
     info.in_flight = true;
     // Find the next SentPacket for this transfer.
@@ skipping 15 matching lines @@
     }
     // This packet has been acked or lost, remove it from sent_packets_.
     largest_observed = *it;
     sent_packets_.erase(it++);
   }
 
   DCHECK(largest_observed.ack_time.IsInitialized());
   DVLOG(1) << "Updating RTT from send_time:"
            << largest_observed.send_time.ToDebuggingValue() << " to ack_time:"
            << largest_observed.ack_time.ToDebuggingValue();
-  sender->rtt_stats->UpdateRtt(
-      largest_observed.ack_time.Subtract(largest_observed.send_time),
-      QuicTime::Delta::Zero(),
-      clock_->Now());
+  QuicTime::Delta measured_rtt =
+      largest_observed.ack_time.Subtract(largest_observed.send_time);
+  DCHECK_GE(measured_rtt.ToMicroseconds(), rtt_.ToMicroseconds());
+  sender->rtt_stats->UpdateRtt(measured_rtt,
+                               QuicTime::Delta::Zero(),
+                               clock_->Now());
   sender->send_algorithm->OnCongestionEvent(
       true, transfer->bytes_in_flight, acked_packets, lost_packets);
   DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()),
             transfer->bytes_in_flight);
   transfer->bytes_in_flight -=
       kPacketSize * (acked_packets.size() + lost_packets.size());
 
   sender->RecordStats();
   transfer->bytes_acked += acked_packets.size() * kPacketSize;
   transfer->bytes_lost += lost_packets.size() * kPacketSize;
@@ skipping 13 matching lines @@
         break;
       }
     }
   }
 }
 
 void SendAlgorithmSimulator::SendDataNow(Transfer* transfer) {
   Sender* sender  = transfer->sender;
   ++sender->last_sent;
   DVLOG(1) << "Sending packet:" << sender->last_sent
-           << " bytes_in_flight:" << transfer->bytes_in_flight;
+           << " bytes_in_flight:" << transfer->bytes_in_flight
+           << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
   sender->send_algorithm->OnPacketSent(
       clock_->Now(), transfer->bytes_in_flight,
       sender->last_sent, kPacketSize, HAS_RETRANSMITTABLE_DATA);
   // Lose the packet immediately if the buffer is full.
   if (sent_packets_.size() * kPacketSize < buffer_size_) {
     // TODO(ianswett): This buffer simulation is an approximation.
     // An ack time of zero means loss.
     bool packet_lost =
         forward_loss_rate_ * kuint64max > simple_random_.RandUint64();
     // Handle correlated loss.
     if (!sent_packets_.empty() &&
         !sent_packets_.back().ack_time.IsInitialized() &&
         loss_correlation_ * kuint64max > simple_random_.RandUint64()) {
       packet_lost = true;
     }
     DVLOG(1) << "losing packet:" << sender->last_sent
              << " due to random loss.";
 
-    QuicTime ack_time = clock_->Now().Add(rtt_);
     // If the number of bytes in flight are less than the bdp, there's
     // no buffering delay.  Bytes lost from the buffer are not counted.
     QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_);
-    if ((sent_packets_.size() + 1) * kPacketSize > bdp) {
-      QuicByteCount qsize = (sent_packets_.size() + 1) * kPacketSize - bdp;
-      ack_time = ack_time.Add(bandwidth_.TransferTime(qsize));
-      DVLOG(1) << "Increasing transfer time:"
-               << bandwidth_.TransferTime(qsize).ToMilliseconds()
-               << "ms due to qsize:" << qsize;
+    QuicTime ack_time = clock_->Now().Add(rtt_);
+    if (kPacketSize > bdp) {
+      ack_time = ack_time.Add(bandwidth_.TransferTime(kPacketSize - bdp));
     }
+    QuicTime queue_ack_time = sent_packets_.empty() ? QuicTime::Zero() :
+        sent_packets_.back().ack_time.Add(bandwidth_.TransferTime(kPacketSize));
+    ack_time = QuicTime::Max(ack_time, queue_ack_time);
     // If the packet is lost, give it an ack time of Zero.
     sent_packets_.push_back(SentPacket(
         sender->last_sent, clock_->Now(),
         packet_lost ? QuicTime::Zero() : ack_time, transfer));
   } else {
     DVLOG(1) << "losing packet:" << sender->last_sent
              << " because the buffer was full.";
   }
   transfer->bytes_in_flight += kPacketSize;
 }
 
 // Advance the time by |delta| without sending anything.
 void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
   clock_->AdvanceTime(delta);
 }
 
 }  // namespace net