First version of a QUIC SendAlgorithmSimulator which is designed to

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"
+#include "net/quic/crypto/quic_random.h"
+
+using std::list;
+using std::max;
+using std::min;
+
+namespace net {
+
+SendAlgorithmSimulator::SendAlgorithmSimulator(
+    SendAlgorithmInterface* send_algorithm,
+    MockClock* clock,
+    RttStats* rtt_stats,
+    QuicBandwidth bandwidth,
+    QuicTime::Delta rtt)
+    : send_algorithm_(send_algorithm),
+      clock_(clock),
+      rtt_stats_(rtt_stats),
+      next_sent_(1),
+      last_acked_(0),
+      next_acked_(1),
+      lose_next_ack_(false),
+      bytes_in_flight_(0),
+      forward_loss_rate_(0),
+      reverse_loss_rate_(0),
+      loss_correlation_(0),
+      bandwidth_(bandwidth),
+      rtt_(rtt),
+      buffer_size_(1000000),
+      max_cwnd_(0),
+      min_cwnd_(100000),
+      max_cwnd_drop_(0),
+      last_cwnd_(0) {
+  uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max());
+  DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed;
+  simple_random_.set_seed(seed);
+}
+
+SendAlgorithmSimulator::~SendAlgorithmSimulator() {}
+
+// Sends the specified number of bytes as quickly as possible and returns the
+// average bandwidth in bytes per second.  The time elapsed is based on
+// waiting for all acks to arrive.
+QuicBandwidth SendAlgorithmSimulator::SendBytes(size_t num_bytes) {
+  const QuicTime start_time = clock_->Now();
+  size_t bytes_acked = 0;
+  while (bytes_acked < num_bytes) {
+    DVLOG(1) << "bytes_acked:" << bytes_acked << " bytes_in_flight_:"
+             << bytes_in_flight_ << " CWND(bytes):"
+             << send_algorithm_->GetCongestionWindow();
+    // Determine the times of next send and of the next ack arrival.
+    QuicTime::Delta send_delta = send_algorithm_->TimeUntilSend(
+        clock_->Now(), bytes_in_flight_, HAS_RETRANSMITTABLE_DATA);
+    // If we've already sent enough bytes, wait for them to be acked.
+    if (bytes_acked + bytes_in_flight_ >= num_bytes) {
+      send_delta = QuicTime::Delta::Infinite();
+    }
+    QuicTime::Delta ack_delta = NextAckDelta();
+    // If both times are infinite, fire a TLP.
+    if (ack_delta.IsInfinite() && send_delta.IsInfinite()) {
+      DVLOG(1) << "Both times are infinite, simulating a TLP.";
+      // TODO(ianswett): Use a more sophisticated TLP timer.
+      clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
+      SendDataNow();
+    } else if (ack_delta < send_delta) {
+      DVLOG(1) << "Handling ack, advancing time:"
+               << ack_delta.ToMicroseconds() << "us";
+      // Ack data all the data up to ack time and lose any missing sequence
+      // numbers.
+      clock_->AdvanceTime(ack_delta);
+      bytes_acked += HandlePendingAck();
+    } else {
+      DVLOG(1) << "Sending, advancing time:"
+               << send_delta.ToMicroseconds() << "us";
+      clock_->AdvanceTime(send_delta);
+      SendDataNow();
+    }
+    RecordStats();
+  }
+  return QuicBandwidth::FromBytesAndTimeDelta(
+      num_bytes, clock_->Now().Subtract(start_time));
+}
+
+// NextAck takes into account packet loss in both forward and reverse
+// direction, as well as correlated losses.  And it assumes the receiver acks
+// every other packet when there is no loss.
+QuicTime::Delta SendAlgorithmSimulator::NextAckDelta() {
+  if (sent_packets_.empty() || AllPacketsLost()) {
+    DVLOG(1) << "No outstanding packets to cause acks. sent_packets_.size():"
+             << sent_packets_.size();
+    return QuicTime::Delta::Infinite();
+  }
+
+  // If necessary, determine next_acked_.
+  // This is only done once to ensure multiple calls return the same time.
+  FindNextAcked();
+
+  // If only one packet is acked, simulate a delayed ack.
+  if (next_acked_ - last_acked_ == 1) {
+    return sent_packets_.front().ack_time.Add(
+        QuicTime::Delta::FromMilliseconds(100)).Subtract(clock_->Now());
+  }
+  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
+       it != sent_packets_.end(); ++it) {
+    if (next_acked_ == it->sequence_number) {
+      return it->ack_time.Subtract(clock_->Now());
+    }
+  }
+  LOG(DFATAL) << "Error, next_acked_: " << next_acked_
+              << " should have been found in sent_packets_";
+  return QuicTime::Delta::Infinite();
+}
+
+bool SendAlgorithmSimulator::AllPacketsLost() {
+  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
+       it != sent_packets_.end(); ++it) {
+    if (it->ack_time.IsInitialized()) {
+      return false;
+    }
+  }
+  return true;
+}
+
+void SendAlgorithmSimulator::FindNextAcked() {
+  // TODO(ianswett): Add a simpler mode which acks every packet.
+  bool packets_lost = false;
+  if (next_acked_ == 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_;
+  next_acked_ = last_acked_;
+  // Remove any packets that are simulated as lost.
+  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
+      it != sent_packets_.end(); ++it) {
+    // Lost packets don't trigger an ack.
+    if (it->ack_time  == QuicTime::Zero()) {
+      packets_lost = true;
+      continue;
+    }
+    // Buffer dropped packets are skipped automatically, but still end up
+    // being lost and cause acks to be sent immediately.
+    if (next_acked_ < it->sequence_number - 1) {
+      packets_lost = true;
+    }
+    next_acked_ = it->sequence_number;
+    if (packets_lost || (next_acked_ - last_acked_) % 2 == 0) {
+      if (two_acks_remaining) {
+        two_acks_remaining = false;
+      } else {
+        break;
+      }
+    }
+  }
+  DVLOG(1) << "FindNextAcked found next_acked_:" << next_acked_
+           << " last_acked:" << last_acked_;
+}
+
+int SendAlgorithmSimulator::HandlePendingAck() {
+  DCHECK_LT(last_acked_, next_acked_);
+  SendAlgorithmInterface::CongestionMap acked_packets;
+  SendAlgorithmInterface::CongestionMap lost_packets;
+  // Some entries may be missing from the sent_packets_ array, if they were
+  // dropped due to buffer overruns.
+  SentPacket largest_observed = sent_packets_.front();
+  while (last_acked_ < next_acked_) {
+    ++last_acked_;
+    TransmissionInfo info = TransmissionInfo();
+    info.bytes_sent = kPacketSize;
+    info.in_flight = true;
+    // If it's missing from the array, it's a loss.
+    if (sent_packets_.front().sequence_number > last_acked_) {
+      DVLOG(1) << "Lost packet:" << last_acked_
+               << " dropped by buffer overflow.";
+      lost_packets[last_acked_] = info;
+      continue;
+    }
+    if (sent_packets_.front().ack_time.IsInitialized()) {
+      acked_packets[last_acked_] = info;
+    } else {
+      lost_packets[last_acked_] = info;
+    }
+    // Remove all packets from the front to next_acked_.
+    largest_observed = sent_packets_.front();
+    sent_packets_.pop_front();
+  }
+
+  DCHECK(largest_observed.ack_time.IsInitialized());
+  rtt_stats_->UpdateRtt(
+      largest_observed.ack_time.Subtract(largest_observed.send_time),
+      QuicTime::Delta::Zero(),
+      clock_->Now());
+  send_algorithm_->OnCongestionEvent(
+      true, bytes_in_flight_, acked_packets, lost_packets);
+  DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()),
+            bytes_in_flight_);
+  bytes_in_flight_ -=
+      kPacketSize * (acked_packets.size() + lost_packets.size());
+  return acked_packets.size() * kPacketSize;
+}
+
+void SendAlgorithmSimulator::SendDataNow() {
+  DVLOG(1) << "Sending packet:" << next_sent_ << " bytes_in_flight:"
+           << bytes_in_flight_;
+  send_algorithm_->OnPacketSent(
+      clock_->Now(), bytes_in_flight_,
+      next_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;
+    }
+
+    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() * kPacketSize > bdp) {
+      QuicByteCount qsize = sent_packets_.size() * kPacketSize - bdp;
+      ack_time = ack_time.Add(bandwidth_.TransferTime(qsize));
+    }
+    // If the packet is lost, give it an ack time of Zero.
+    sent_packets_.push_back(SentPacket(
+        next_sent_, clock_->Now(), packet_lost ? QuicTime::Zero() : ack_time));
+  }
+  ++next_sent_;
+  bytes_in_flight_ += kPacketSize;
+}
+
+void SendAlgorithmSimulator::RecordStats() {
+  QuicByteCount cwnd = send_algorithm_->GetCongestionWindow();
+  max_cwnd_ = max(max_cwnd_, cwnd);
+  min_cwnd_ = min(min_cwnd_, cwnd);
+  if (last_cwnd_ > cwnd) {
+    max_cwnd_drop_ = max(max_cwnd_drop_, last_cwnd_ - cwnd);
+  }
+  last_cwnd_ = cwnd;
+}
+
+// Advance the time by |delta| without sending anything.
+void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
+  clock_->AdvanceTime(delta);
+}
+
+// Elapsed time from the start of the connection.
+QuicTime SendAlgorithmSimulator::ElapsedTime() {
+  return clock_->Now();
+}
+
+}  // namespace net