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::make_pair;
  15 using std::max;
  16 using std::min;
  17 using std::vector;
  18
  19 namespace net {
  20
  21 namespace {
  22
  23 const QuicByteCount kPacketSize = 1200;
  24
  25 }  // namespace
  26
  27 SendAlgorithmSimulator::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
  41 SendAlgorithmSimulator::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
  59 SendAlgorithmSimulator::~SendAlgorithmSimulator() {}
  60
  61 void SendAlgorithmSimulator::AddTransfer(Sender* sender, size_t num_bytes) {
  62   AddTransfer(sender, num_bytes, clock_->Now());
  63 }
  64
  65 void 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
  72 void SendAlgorithmSimulator::TransferBytes() {
  73   TransferBytes(kuint64max, QuicTime::Delta::Infinite());
  74 }
  75
  76 void 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
 114 SendAlgorithmSimulator::PacketEvent SendAlgorithmSimulator::NextSendEvent() {
 115   QuicTime::Delta next_send_time = QuicTime::Delta::Infinite();
 116   Transfer* transfer = nullptr;
 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.
 143 SendAlgorithmSimulator::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(), nullptr);
 147   }
 148
 149   // For each connection, find the next acked packet.
 150   QuicTime::Delta ack_time = QuicTime::Delta::Infinite();
 151   Transfer* transfer = nullptr;
 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
 164 QuicTime::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
 182 QuicTime::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
 223 bool 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
 245 void 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
 326 void 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.
 369 void SendAlgorithmSimulator::AdvanceTime(QuicTime::Delta delta) {
 370   clock_->AdvanceTime(delta);
 371 }
 372
 373 }  // namespace net