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