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