net/quic/congestion_control/send_algorithm_simulator.cc

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