Home | History | Annotate | Download | only in congestion_control 
      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 = 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.
    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(), 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 
    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
    374