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/send_algorithm_simulator.h"
6
7#include <limits>
8
9#include "base/logging.h"
10#include "base/rand_util.h"
11#include "net/quic/crypto/quic_random.h"
12
13using std::list;
14using std::max;
15using std::min;
16
17namespace net {
18
19namespace {
20
21const QuicByteCount kPacketSize = 1200;
22
23}  // namespace
24
25SendAlgorithmSimulator::SendAlgorithmSimulator(
26    SendAlgorithmInterface* send_algorithm,
27    MockClock* clock,
28    RttStats* rtt_stats,
29    QuicBandwidth bandwidth,
30    QuicTime::Delta rtt)
31    : send_algorithm_(send_algorithm),
32      clock_(clock),
33      rtt_stats_(rtt_stats),
34      next_sent_(1),
35      last_acked_(0),
36      next_acked_(1),
37      lose_next_ack_(false),
38      bytes_in_flight_(0),
39      forward_loss_rate_(0),
40      reverse_loss_rate_(0),
41      loss_correlation_(0),
42      bandwidth_(bandwidth),
43      rtt_(rtt),
44      buffer_size_(1000000),
45      max_cwnd_(0),
46      min_cwnd_(100000),
47      max_cwnd_drop_(0),
48      last_cwnd_(0) {
49  uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max());
50  DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed;
51  simple_random_.set_seed(seed);
52}
53
54SendAlgorithmSimulator::~SendAlgorithmSimulator() {}
55
56// Sends the specified number of bytes as quickly as possible and returns the
57// average bandwidth in bytes per second.  The time elapsed is based on
58// waiting for all acks to arrive.
59QuicBandwidth SendAlgorithmSimulator::SendBytes(size_t num_bytes) {
60  const QuicTime start_time = clock_->Now();
61  size_t bytes_acked = 0;
62  while (bytes_acked < num_bytes) {
63    DVLOG(1) << "bytes_acked:" << bytes_acked << " bytes_in_flight_:"
64             << bytes_in_flight_ << " CWND(bytes):"
65             << send_algorithm_->GetCongestionWindow();
66    // Determine the times of next send and of the next ack arrival.
67    QuicTime::Delta send_delta = send_algorithm_->TimeUntilSend(
68        clock_->Now(), bytes_in_flight_, HAS_RETRANSMITTABLE_DATA);
69    // If we've already sent enough bytes, wait for them to be acked.
70    if (bytes_acked + bytes_in_flight_ >= num_bytes) {
71      send_delta = QuicTime::Delta::Infinite();
72    }
73    QuicTime::Delta ack_delta = NextAckDelta();
74    // If both times are infinite, fire a TLP.
75    if (ack_delta.IsInfinite() && send_delta.IsInfinite()) {
76      DVLOG(1) << "Both times are infinite, simulating a TLP.";
77      // TODO(ianswett): Use a more sophisticated TLP timer.
78      clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
79      SendDataNow();
80    } else if (ack_delta < send_delta) {
81      DVLOG(1) << "Handling ack, advancing time:"
82               << ack_delta.ToMicroseconds() << "us";
83      // Ack data all the data up to ack time and lose any missing sequence
84      // numbers.
85      clock_->AdvanceTime(ack_delta);
86      bytes_acked += HandlePendingAck();
87    } else {
88      DVLOG(1) << "Sending, advancing time:"
89               << send_delta.ToMicroseconds() << "us";
90      clock_->AdvanceTime(send_delta);
91      SendDataNow();
92    }
93    RecordStats();
94  }
95  return QuicBandwidth::FromBytesAndTimeDelta(
96      num_bytes, clock_->Now().Subtract(start_time));
97}
98
99// NextAck takes into account packet loss in both forward and reverse
100// direction, as well as correlated losses.  And it assumes the receiver acks
101// every other packet when there is no loss.
102QuicTime::Delta SendAlgorithmSimulator::NextAckDelta() {
103  if (sent_packets_.empty() || AllPacketsLost()) {
104    DVLOG(1) << "No outstanding packets to cause acks. sent_packets_.size():"
105             << sent_packets_.size();
106    return QuicTime::Delta::Infinite();
107  }
108
109  // If necessary, determine next_acked_.
110  // This is only done once to ensure multiple calls return the same time.
111  FindNextAcked();
112
113  // If only one packet is acked, simulate a delayed ack.
114  if (next_acked_ - last_acked_ == 1) {
115    return sent_packets_.front().ack_time.Add(
116        QuicTime::Delta::FromMilliseconds(100)).Subtract(clock_->Now());
117  }
118  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
119       it != sent_packets_.end(); ++it) {
120    if (next_acked_ == it->sequence_number) {
121      return it->ack_time.Subtract(clock_->Now());
122    }
123  }
124  LOG(DFATAL) << "Error, next_acked_: " << next_acked_
125              << " should have been found in sent_packets_";
126  return QuicTime::Delta::Infinite();
127}
128
129bool SendAlgorithmSimulator::AllPacketsLost() {
130  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
131       it != sent_packets_.end(); ++it) {
132    if (it->ack_time.IsInitialized()) {
133      return false;
134    }
135  }
136  return true;
137}
138
139void SendAlgorithmSimulator::FindNextAcked() {
140  // TODO(ianswett): Add a simpler mode which acks every packet.
141  bool packets_lost = false;
142  if (next_acked_ == last_acked_) {
143    // Determine if the next ack is lost only once, to ensure determinism.
144    lose_next_ack_ =
145        reverse_loss_rate_ * kuint64max > simple_random_.RandUint64();
146  }
147  bool two_acks_remaining = lose_next_ack_;
148  next_acked_ = last_acked_;
149  // Remove any packets that are simulated as lost.
150  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
151      it != sent_packets_.end(); ++it) {
152    // Lost packets don't trigger an ack.
153    if (it->ack_time  == QuicTime::Zero()) {
154      packets_lost = true;
155      continue;
156    }
157    // Buffer dropped packets are skipped automatically, but still end up
158    // being lost and cause acks to be sent immediately.
159    if (next_acked_ < it->sequence_number - 1) {
160      packets_lost = true;
161    }
162    next_acked_ = it->sequence_number;
163    if (packets_lost || (next_acked_ - last_acked_) % 2 == 0) {
164      if (two_acks_remaining) {
165        two_acks_remaining = false;
166      } else {
167        break;
168      }
169    }
170  }
171  DVLOG(1) << "FindNextAcked found next_acked_:" << next_acked_
172           << " last_acked:" << last_acked_;
173}
174
175int SendAlgorithmSimulator::HandlePendingAck() {
176  DCHECK_LT(last_acked_, next_acked_);
177  SendAlgorithmInterface::CongestionMap acked_packets;
178  SendAlgorithmInterface::CongestionMap lost_packets;
179  // Some entries may be missing from the sent_packets_ array, if they were
180  // dropped due to buffer overruns.
181  SentPacket largest_observed = sent_packets_.front();
182  while (last_acked_ < next_acked_) {
183    ++last_acked_;
184    TransmissionInfo info = TransmissionInfo();
185    info.bytes_sent = kPacketSize;
186    info.in_flight = true;
187    // If it's missing from the array, it's a loss.
188    if (sent_packets_.front().sequence_number > last_acked_) {
189      DVLOG(1) << "Lost packet:" << last_acked_
190               << " dropped by buffer overflow.";
191      lost_packets[last_acked_] = info;
192      continue;
193    }
194    if (sent_packets_.front().ack_time.IsInitialized()) {
195      acked_packets[last_acked_] = info;
196    } else {
197      lost_packets[last_acked_] = info;
198    }
199    // Remove all packets from the front to next_acked_.
200    largest_observed = sent_packets_.front();
201    sent_packets_.pop_front();
202  }
203
204  DCHECK(largest_observed.ack_time.IsInitialized());
205  rtt_stats_->UpdateRtt(
206      largest_observed.ack_time.Subtract(largest_observed.send_time),
207      QuicTime::Delta::Zero(),
208      clock_->Now());
209  send_algorithm_->OnCongestionEvent(
210      true, bytes_in_flight_, acked_packets, lost_packets);
211  DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()),
212            bytes_in_flight_);
213  bytes_in_flight_ -=
214      kPacketSize * (acked_packets.size() + lost_packets.size());
215  return acked_packets.size() * kPacketSize;
216}
217
218void SendAlgorithmSimulator::SendDataNow() {
219  DVLOG(1) << "Sending packet:" << next_sent_ << " bytes_in_flight:"
220           << bytes_in_flight_;
221  send_algorithm_->OnPacketSent(
222      clock_->Now(), bytes_in_flight_,
223      next_sent_, kPacketSize, HAS_RETRANSMITTABLE_DATA);
224  // Lose the packet immediately if the buffer is full.
225  if (sent_packets_.size() * kPacketSize < buffer_size_) {
226    // TODO(ianswett): This buffer simulation is an approximation.
227    // An ack time of zero means loss.
228    bool packet_lost =
229        forward_loss_rate_ * kuint64max > simple_random_.RandUint64();
230    // Handle correlated loss.
231    if (!sent_packets_.empty() &&
232        !sent_packets_.back().ack_time.IsInitialized() &&
233        loss_correlation_ * kuint64max > simple_random_.RandUint64()) {
234      packet_lost = true;
235    }
236
237    QuicTime ack_time = clock_->Now().Add(rtt_);
238    // If the number of bytes in flight are less than the bdp, there's
239    // no buffering delay.  Bytes lost from the buffer are not counted.
240    QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_);
241    if (sent_packets_.size() * kPacketSize > bdp) {
242      QuicByteCount qsize = sent_packets_.size() * kPacketSize - bdp;
243      ack_time = ack_time.Add(bandwidth_.TransferTime(qsize));
244    }
245    // If the packet is lost, give it an ack time of Zero.
246    sent_packets_.push_back(SentPacket(
247        next_sent_, clock_->Now(), packet_lost ? QuicTime::Zero() : ack_time));
248  }
249  ++next_sent_;
250  bytes_in_flight_ += kPacketSize;
251}
252
253void SendAlgorithmSimulator::RecordStats() {
254  QuicByteCount cwnd = send_algorithm_->GetCongestionWindow();
255  max_cwnd_ = max(max_cwnd_, cwnd);
256  min_cwnd_ = min(min_cwnd_, cwnd);
257  if (last_cwnd_ > cwnd) {
258    max_cwnd_drop_ = max(max_cwnd_drop_, last_cwnd_ - cwnd);
259  }
260  last_cwnd_ = cwnd;
261}
262
263// Advance the time by |delta| without sending anything.
264void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
265  clock_->AdvanceTime(delta);
266}
267
268// Elapsed time from the start of the connection.
269QuicTime SendAlgorithmSimulator::ElapsedTime() {
270  return clock_->Now();
271}
272
273}  // namespace net
274