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::make_pair;
15using std::max;
16using std::min;
17using std::vector;
18
19namespace net {
20
21namespace {
22
23const QuicByteCount kPacketSize = 1200;
24
25}  // namespace
26
27SendAlgorithmSimulator::Sender::Sender(SendAlgorithmInterface* send_algorithm,
28                                       RttStats* rtt_stats)
29    : send_algorithm(send_algorithm),
30      rtt_stats(rtt_stats),
31      last_sent(0),
32      last_acked(0),
33      next_acked(1),
34      max_cwnd(0),
35      min_cwnd(100000),
36      max_cwnd_drop(0),
37      last_cwnd(0),
38      last_transfer_bandwidth(QuicBandwidth::Zero()),
39      last_transfer_loss_rate(0) {}
40
41SendAlgorithmSimulator::SendAlgorithmSimulator(
42    MockClock* clock,
43    QuicBandwidth bandwidth,
44    QuicTime::Delta rtt)
45    : clock_(clock),
46      lose_next_ack_(false),
47      forward_loss_rate_(0),
48      reverse_loss_rate_(0),
49      loss_correlation_(0),
50      bandwidth_(bandwidth),
51      rtt_(rtt),
52      buffer_size_(1000000),
53      delayed_ack_timer_(QuicTime::Delta::FromMilliseconds(100)) {
54  uint32 seed = base::RandInt(0, std::numeric_limits<int32>::max());
55  DVLOG(1) << "Seeding SendAlgorithmSimulator with " << seed;
56  simple_random_.set_seed(seed);
57}
58
59SendAlgorithmSimulator::~SendAlgorithmSimulator() {}
60
61void SendAlgorithmSimulator::AddTransfer(Sender* sender, size_t num_bytes) {
62  AddTransfer(sender, num_bytes, clock_->Now());
63}
64
65void SendAlgorithmSimulator::AddTransfer(
66    Sender* sender, size_t num_bytes, QuicTime start_time) {
67  pending_transfers_.push_back(Transfer(sender, num_bytes, start_time));
68  // Record initial stats from when the transfer begins.
69  pending_transfers_.back().sender->RecordStats();
70}
71
72void SendAlgorithmSimulator::TransferBytes() {
73  TransferBytes(kuint64max, QuicTime::Delta::Infinite());
74}
75
76void SendAlgorithmSimulator::TransferBytes(QuicByteCount max_bytes,
77                                           QuicTime::Delta max_time) {
78  const QuicTime end_time = max_time.IsInfinite() ?
79      QuicTime::Zero().Add(QuicTime::Delta::Infinite()) :
80      clock_->Now().Add(max_time);
81  QuicByteCount bytes_sent = 0;
82  while (!pending_transfers_.empty() &&
83         clock_->Now() < end_time &&
84         bytes_sent < max_bytes) {
85    // Determine the times of next send and of the next ack arrival.
86    PacketEvent send_event = NextSendEvent();
87    PacketEvent ack_event = NextAckEvent();
88    // If both times are infinite, fire a TLP.
89    if (ack_event.time_delta.IsInfinite() &&
90        send_event.time_delta.IsInfinite()) {
91      DVLOG(1) << "Both times are infinite, simulating a TLP.";
92      // TODO(ianswett): Use a more sophisticated TLP timer or never lose
93      // the last ack?
94      clock_->AdvanceTime(QuicTime::Delta::FromMilliseconds(100));
95      SendDataNow(&pending_transfers_.front());
96    } else if (ack_event.time_delta < send_event.time_delta) {
97      DVLOG(1) << "Handling ack of largest observed:"
98               << ack_event.transfer->sender->next_acked << ", advancing time:"
99               << ack_event.time_delta.ToMicroseconds() << "us";
100      // Ack data all the data up to ack time and lose any missing sequence
101      // numbers.
102      clock_->AdvanceTime(ack_event.time_delta);
103      HandlePendingAck(ack_event.transfer);
104    } else {
105      DVLOG(1) << "Sending, advancing time:"
106               << send_event.time_delta.ToMicroseconds() << "us";
107      clock_->AdvanceTime(send_event.time_delta);
108      SendDataNow(send_event.transfer);
109      bytes_sent += kPacketSize;
110    }
111  }
112}
113
114SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextSendEvent() {
115  QuicTime::Delta next_send_time = QuicTime::Delta::Infinite();
116  Transfer* transfer = NULL;
117  for (vector<Transfer>::iterator it = pending_transfers_.begin();
118       it != pending_transfers_.end(); ++it) {
119    // If we've already sent enough bytes, wait for them to be acked.
120    if (it->bytes_acked + it->bytes_in_flight >= it->num_bytes) {
121      continue;
122    }
123    // If the flow hasn't started, use the start time.
124    QuicTime::Delta transfer_send_time = it->start_time.Subtract(clock_->Now());
125    if (clock_->Now() >= it->start_time) {
126      transfer_send_time =
127          it->sender->send_algorithm->TimeUntilSend(
128              clock_->Now(), it->bytes_in_flight, HAS_RETRANSMITTABLE_DATA);
129    }
130    if (transfer_send_time < next_send_time) {
131      next_send_time = transfer_send_time;
132      transfer = &(*it);
133    }
134  }
135  DVLOG(1) << "NextSendTime returning delta(ms):"
136           << next_send_time.ToMilliseconds();
137  return PacketEvent(next_send_time, transfer);
138}
139
140// NextAck takes into account packet loss in both forward and reverse
141// direction, as well as correlated losses.  And it assumes the receiver acks
142// every other packet when there is no loss.
143SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextAckEvent() {
144  if (sent_packets_.empty()) {
145    DVLOG(1) << "No outstanding packets to ack for any transfer.";
146    return PacketEvent(QuicTime::Delta::Infinite(), NULL);
147  }
148
149  // For each connection, find the next acked packet.
150  QuicTime::Delta ack_time = QuicTime::Delta::Infinite();
151  Transfer* transfer = NULL;
152  for (vector<Transfer>::iterator it = pending_transfers_.begin();
153       it != pending_transfers_.end(); ++it) {
154    QuicTime::Delta transfer_ack_time = FindNextAcked(&(*it));
155    if (transfer_ack_time < ack_time) {
156      ack_time = transfer_ack_time;
157      transfer = &(*it);
158    }
159  }
160
161  return PacketEvent(ack_time, transfer);
162}
163
164QuicTime::Delta SendAlgorithmSimulator::FindNextAcked(Transfer* transfer) {
165  Sender* sender = transfer->sender;
166  if (sender->next_acked == sender->last_acked) {
167    // Determine if the next ack is lost only once, to ensure determinism.
168    lose_next_ack_ =
169        reverse_loss_rate_ * kuint64max > simple_random_.RandUint64();
170  }
171
172  QuicPacketSequenceNumber next_acked = sender->last_acked;
173  QuicTime::Delta next_ack_delay =
174      FindNextAck(transfer, sender->last_acked, &next_acked);
175  if (lose_next_ack_) {
176    next_ack_delay = FindNextAck(transfer, next_acked, &next_acked);
177  }
178  sender->next_acked = next_acked;
179  return next_ack_delay;
180}
181
182QuicTime::Delta SendAlgorithmSimulator::FindNextAck(
183    const Transfer* transfer,
184    QuicPacketSequenceNumber last_acked,
185    QuicPacketSequenceNumber* next_acked) const {
186  *next_acked = last_acked;
187  QuicTime::Delta ack_delay = QuicTime::Delta::Infinite();
188  // Remove any packets that are simulated as lost.
189  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
190       it != sent_packets_.end(); ++it) {
191    if (transfer != it->transfer) {
192      continue;
193    }
194    // Skip over any packets less than or equal to last_acked.
195    if (it->sequence_number <= last_acked) {
196      continue;
197    }
198    // Lost packets don't trigger an ack.
199    if (it->lost) {
200      continue;
201    }
202    DCHECK_LT(*next_acked, it->sequence_number);
203    // Consider a delayed ack for the current next_acked.
204    if (ack_delay < it->ack_time.Subtract(clock_->Now())) {
205      break;
206    }
207    *next_acked = it->sequence_number;
208    ack_delay = it->ack_time.Subtract(clock_->Now());
209    if (HasRecentLostPackets(transfer, *next_acked) ||
210        (*next_acked - last_acked) >= 2) {
211      break;
212    }
213    ack_delay = ack_delay.Add(delayed_ack_timer_);
214  }
215
216  DVLOG(1) << "FindNextAcked found next_acked_:"
217           << transfer->sender->next_acked
218           << " last_acked:" << transfer->sender->last_acked
219           << " ack_delay(ms):" << ack_delay.ToMilliseconds();
220  return ack_delay;
221}
222
223bool SendAlgorithmSimulator::HasRecentLostPackets(
224    const Transfer* transfer, QuicPacketSequenceNumber next_acked) const {
225  QuicPacketSequenceNumber last_packet = transfer->sender->last_acked;
226  for (list<SentPacket>::const_iterator it = sent_packets_.begin();
227       it != sent_packets_.end() && it->sequence_number < next_acked; ++it) {
228    if (transfer != it->transfer) {
229      continue;
230    }
231    // Lost packets don't trigger an ack.
232    if (it->lost) {
233      return true;
234    }
235    // Buffer dropped packets are skipped automatically, but still end up
236    // being lost and cause acks to be sent immediately.
237    if (it->sequence_number > last_packet + 1) {
238      return true;
239    }
240    last_packet = it->sequence_number;
241  }
242  return false;
243}
244
245void SendAlgorithmSimulator::HandlePendingAck(Transfer* transfer) {
246  Sender* sender  = transfer->sender;
247  DCHECK_LT(sender->last_acked, sender->next_acked);
248  SendAlgorithmInterface::CongestionVector acked_packets;
249  SendAlgorithmInterface::CongestionVector lost_packets;
250  DVLOG(1) << "Acking packets from:" << sender->last_acked
251             << " to " << sender->next_acked
252             << " bytes_in_flight:" << transfer->bytes_in_flight
253             << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
254  // Some entries may be missing from the sent_packets_ array, if they were
255  // dropped due to buffer overruns.
256  SentPacket largest_observed;
257  list<SentPacket>::iterator it = sent_packets_.begin();
258  while (sender->last_acked < sender->next_acked) {
259    ++sender->last_acked;
260    TransmissionInfo info = TransmissionInfo();
261    info.bytes_sent = kPacketSize;
262    info.in_flight = true;
263    // Find the next SentPacket for this transfer.
264    while (it->transfer != transfer) {
265      DCHECK(it != sent_packets_.end());
266      ++it;
267    }
268    // If it's missing from the array, it's a loss.
269    if (it->sequence_number > sender->last_acked) {
270      DVLOG(1) << "Lost packet:" << sender->last_acked
271               << " dropped by buffer overflow.";
272      lost_packets.push_back(make_pair(sender->last_acked, info));
273      continue;
274    }
275    if (it->lost) {
276      lost_packets.push_back(make_pair(sender->last_acked, info));
277    } else {
278      acked_packets.push_back(make_pair(sender->last_acked, info));
279    }
280    // This packet has been acked or lost, remove it from sent_packets_.
281    largest_observed = *it;
282    sent_packets_.erase(it++);
283  }
284
285  DCHECK(largest_observed.ack_time.IsInitialized());
286  DVLOG(1) << "Updating RTT from send_time:"
287           << largest_observed.send_time.ToDebuggingValue() << " to ack_time:"
288           << largest_observed.ack_time.ToDebuggingValue();
289  QuicTime::Delta measured_rtt =
290      largest_observed.ack_time.Subtract(largest_observed.send_time);
291  DCHECK_GE(measured_rtt.ToMicroseconds(), rtt_.ToMicroseconds());
292  sender->rtt_stats->UpdateRtt(measured_rtt,
293                               QuicTime::Delta::Zero(),
294                               clock_->Now());
295  sender->send_algorithm->OnCongestionEvent(
296      true, transfer->bytes_in_flight, acked_packets, lost_packets);
297  DCHECK_LE(kPacketSize * (acked_packets.size() + lost_packets.size()),
298            transfer->bytes_in_flight);
299  transfer->bytes_in_flight -=
300      kPacketSize * (acked_packets.size() + lost_packets.size());
301
302  sender->RecordStats();
303  transfer->bytes_acked += acked_packets.size() * kPacketSize;
304  transfer->bytes_lost += lost_packets.size() * kPacketSize;
305  if (transfer->bytes_acked >= transfer->num_bytes) {
306    // Remove completed transfers and record transfer bandwidth.
307    QuicTime::Delta transfer_time =
308        clock_->Now().Subtract(transfer->start_time);
309    sender->last_transfer_loss_rate = static_cast<float>(transfer->bytes_lost) /
310        (transfer->bytes_lost + transfer->bytes_acked);
311    sender->last_transfer_bandwidth =
312        QuicBandwidth::FromBytesAndTimeDelta(transfer->num_bytes,
313                                             transfer_time);
314    DCHECK_GE(bandwidth_.ToBitsPerSecond(),
315              sender->last_transfer_bandwidth.ToBitsPerSecond());
316    for (vector<Transfer>::iterator it = pending_transfers_.begin();
317         it != pending_transfers_.end(); ++it) {
318      if (transfer == &(*it)) {
319        pending_transfers_.erase(it);
320        break;
321      }
322    }
323  }
324}
325
326void SendAlgorithmSimulator::SendDataNow(Transfer* transfer) {
327  Sender* sender  = transfer->sender;
328  ++sender->last_sent;
329  DVLOG(1) << "Sending packet:" << sender->last_sent
330           << " bytes_in_flight:" << transfer->bytes_in_flight
331           << " Now():" << (clock_->Now().ToDebuggingValue() / 1000) << "ms";
332  sender->send_algorithm->OnPacketSent(
333      clock_->Now(), transfer->bytes_in_flight,
334      sender->last_sent, kPacketSize, HAS_RETRANSMITTABLE_DATA);
335  // Lose the packet immediately if the buffer is full.
336  if (sent_packets_.size() * kPacketSize < buffer_size_) {
337    // TODO(ianswett): This buffer simulation is an approximation.
338    // An ack time of zero means loss.
339    bool packet_lost =
340        forward_loss_rate_ * kuint64max > simple_random_.RandUint64();
341    // Handle correlated loss.
342    if (!sent_packets_.empty() && sent_packets_.back().lost &&
343        loss_correlation_ * kuint64max > simple_random_.RandUint64()) {
344      packet_lost = true;
345    }
346    DVLOG(1) << "losing packet:" << sender->last_sent
347             << " due to random loss.";
348
349    // If the number of bytes in flight are less than the bdp, there's
350    // no buffering delay.  Bytes lost from the buffer are not counted.
351    QuicByteCount bdp = bandwidth_.ToBytesPerPeriod(rtt_);
352    QuicTime ack_time = clock_->Now().Add(rtt_);
353    if (kPacketSize > bdp) {
354      ack_time = ack_time.Add(bandwidth_.TransferTime(kPacketSize - bdp));
355    }
356    QuicTime queue_ack_time = sent_packets_.empty() ? QuicTime::Zero() :
357        sent_packets_.back().ack_time.Add(bandwidth_.TransferTime(kPacketSize));
358    ack_time = QuicTime::Max(ack_time, queue_ack_time);
359    sent_packets_.push_back(SentPacket(
360        sender->last_sent, clock_->Now(), ack_time, packet_lost, transfer));
361  } else {
362    DVLOG(1) << "losing packet:" << sender->last_sent
363             << " because the buffer was full.";
364  }
365  transfer->bytes_in_flight += kPacketSize;
366}
367
368// Advance the time by |delta| without sending anything.
369void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
370  clock_->AdvanceTime(delta);
371}
372
373}  // namespace net
374