net/quic/congestion_control/send_algorithm_simulator.h

   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 // A test only class to enable simulations of send algorithms.
   6
   7 #ifndef NET_QUIC_CONGESTION_CONTROL_SEND_ALGORITHM_SIMULATOR_H_
   8 #define NET_QUIC_CONGESTION_CONTROL_SEND_ALGORITHM_SIMULATOR_H_
   9
  10 #include <algorithm>
  11 #include <string>
  12 #include <vector>
  13
  14 #include "base/basictypes.h"
  15 #include "base/format_macros.h"
  16 #include "base/strings/stringprintf.h"
  17 #include "net/quic/congestion_control/send_algorithm_interface.h"
  18 #include "net/quic/quic_protocol.h"
  19 #include "net/quic/quic_time.h"
  20 #include "net/quic/test_tools/mock_clock.h"
  21 #include "net/quic/test_tools/quic_test_utils.h"
  22
  23 using base::StringPrintf;
  24
  25 namespace net {
  26
  27 class SendAlgorithmSimulator {
  28  public:
  29   struct Sender {
  30     Sender(SendAlgorithmInterface* send_algorithm, RttStats* rtt_stats);
  31
  32     void RecordStats() {
  33       QuicByteCount cwnd = send_algorithm->GetCongestionWindow();
  34       max_cwnd = std::max(max_cwnd, cwnd);
  35       min_cwnd = std::min(min_cwnd, cwnd);
  36       if (last_cwnd > cwnd) {
  37         max_cwnd_drop = std::max(max_cwnd_drop, last_cwnd - cwnd);
  38       }
  39       last_cwnd = cwnd;
  40     }
  41
  42     std::string DebugString() {
  43       return StringPrintf("observed goodput(bytes/s):%" PRId64
  44                           " loss rate:%f"
  45                           " cwnd:%" PRIu64
  46                           " max_cwnd:%" PRIu64 " min_cwnd:%" PRIu64
  47                           " max_cwnd_drop:%" PRIu64,
  48                           last_transfer_bandwidth.ToBytesPerSecond(),
  49                           last_transfer_loss_rate,
  50                           send_algorithm->GetCongestionWindow(),
  51                           max_cwnd, min_cwnd, max_cwnd_drop);
  52     }
  53
  54     SendAlgorithmInterface* send_algorithm;
  55     RttStats* rtt_stats;
  56
  57     // Last sequence number the sender sent.
  58     QuicPacketSequenceNumber last_sent;
  59     // Last packet sequence number acked.
  60     QuicPacketSequenceNumber last_acked;
  61     // Packet sequence number to ack up to.
  62     QuicPacketSequenceNumber next_acked;
  63
  64     // Stats collected for understanding the congestion control.
  65     QuicByteCount max_cwnd;
  66     QuicByteCount min_cwnd;
  67     QuicByteCount max_cwnd_drop;
  68     QuicByteCount last_cwnd;
  69
  70     QuicBandwidth last_transfer_bandwidth;
  71     float last_transfer_loss_rate;
  72   };
  73
  74   struct Transfer {
  75     Transfer(Sender* sender, QuicByteCount num_bytes, QuicTime start_time)
  76         : sender(sender),
  77           num_bytes(num_bytes),
  78           bytes_acked(0),
  79           bytes_lost(0),
  80           bytes_in_flight(0),
  81           start_time(start_time) {}
  82
  83     Sender* sender;
  84     QuicByteCount num_bytes;
  85     QuicByteCount bytes_acked;
  86     QuicByteCount bytes_lost;
  87     QuicByteCount bytes_in_flight;
  88     QuicTime start_time;
  89   };
  90
  91   struct SentPacket {
  92     SentPacket()
  93         : sequence_number(0),
  94           send_time(QuicTime::Zero()),
  95           ack_time(QuicTime::Zero()),
  96           lost(false),
  97           transfer(NULL) {}
  98     SentPacket(QuicPacketSequenceNumber sequence_number,
  99                QuicTime send_time,
 100                QuicTime ack_time,
 101                bool lost,
 102                Transfer* transfer)
 103         : sequence_number(sequence_number),
 104           send_time(send_time),
 105           ack_time(ack_time),
 106           lost(lost),
 107           transfer(transfer) {}
 108
 109     QuicPacketSequenceNumber sequence_number;
 110     QuicTime send_time;
 111     QuicTime ack_time;
 112     bool lost;
 113     Transfer* transfer;
 114   };
 115
 116   // |rtt_stats| should be the same RttStats used by the |send_algorithm|.
 117   SendAlgorithmSimulator(MockClock* clock_,
 118                          QuicBandwidth bandwidth,
 119                          QuicTime::Delta rtt);
 120   ~SendAlgorithmSimulator();
 121
 122   void set_bandwidth(QuicBandwidth bandwidth) {
 123     bandwidth_ = bandwidth;
 124   }
 125
 126   void set_forward_loss_rate(float loss_rate) {
 127     DCHECK_LT(loss_rate, 1.0f);
 128     forward_loss_rate_ = loss_rate;
 129   }
 130
 131   void set_reverse_loss_rate(float loss_rate) {
 132     DCHECK_LT(loss_rate, 1.0f);
 133     reverse_loss_rate_ = loss_rate;
 134   }
 135
 136   void set_loss_correlation(float loss_correlation) {
 137     DCHECK_LT(loss_correlation, 1.0f);
 138     loss_correlation_ = loss_correlation;
 139   }
 140
 141   void set_buffer_size(size_t buffer_size_bytes) {
 142     buffer_size_ = buffer_size_bytes;
 143   }
 144
 145   void set_delayed_ack_timer(QuicTime::Delta delayed_ack_timer) {
 146     delayed_ack_timer_ = delayed_ack_timer;
 147   }
 148
 149   // Advance the time by |delta| without sending anything.
 150   void AdvanceTime(QuicTime::Delta delta);
 151
 152   // Adds a pending sender.  The send will run when TransferBytes is called.
 153   // Adding two transfers with the same sender is unsupported.
 154   void AddTransfer(Sender* sender, size_t num_bytes);
 155
 156   // Adds a pending sending to start at the specified time.
 157   void AddTransfer(Sender* sender, size_t num_bytes, QuicTime start_time);
 158
 159   // Convenience method to transfer all bytes.
 160   void TransferBytes();
 161
 162   // Transfers bytes through the connection until |max_bytes| are reached,
 163   // |max_time| is reached, or all senders have finished sending.  If max_bytes
 164   // is 0, it does not apply, and if |max_time| is Zero, no time limit applies.
 165   void TransferBytes(QuicByteCount max_bytes, QuicTime::Delta max_time);
 166
 167  private:
 168   // A pending packet event, either a send or an ack.
 169   struct PacketEvent {
 170     PacketEvent(QuicTime::Delta time_delta, Transfer* transfer)
 171         : time_delta(time_delta),
 172           transfer(transfer) {}
 173
 174     QuicTime::Delta time_delta;
 175     Transfer* transfer;
 176   };
 177
 178   // NextSendTime returns the next time any of the pending transfers send,
 179   // and populates transfer if the send time is not infinite.
 180   PacketEvent NextSendEvent();
 181
 182   // NextAckTime takes into account packet loss in both forward and reverse
 183   // direction, as well as delayed ack behavior.
 184   PacketEvent NextAckEvent();
 185
 186   // Sets the next acked.
 187   QuicTime::Delta FindNextAcked(Transfer* transfer);
 188
 189   // Sets the |next_acked| packet for the |transfer| starting at the specified
 190   // |last_acked|.  Returns QuicTime::Delta::Infinite and doesn't set
 191   // |next_acked| if there is no ack after |last_acked|.
 192   QuicTime::Delta FindNextAck(const Transfer* transfer,
 193                               QuicPacketSequenceNumber last_acked,
 194                               QuicPacketSequenceNumber* next_acked) const;
 195
 196   // Returns true if any of the packets |transfer| is waiting for less than
 197   // next_acked have been lost.
 198   bool HasRecentLostPackets(const Transfer* transfer,
 199                             QuicPacketSequenceNumber next_acked) const;
 200
 201   // Process all the acks that should have arrived by the current time, and
 202   // lose any packets that are missing.  Returns the number of bytes acked.
 203   void HandlePendingAck(Transfer* transfer);
 204
 205   void SendDataNow(Transfer* transfer);
 206
 207   // List of all pending transfers waiting to use the connection.
 208   std::vector<Transfer> pending_transfers_;
 209
 210   MockClock* clock_;
 211   // Whether the next ack should be lost.
 212   bool lose_next_ack_;
 213   // The times acks are expected, assuming acks are not lost and every packet
 214   // is acked.
 215   std::list<SentPacket> sent_packets_;
 216
 217   test::SimpleRandom simple_random_;
 218   float forward_loss_rate_;  // Loss rate on the forward path.
 219   float reverse_loss_rate_;  // Loss rate on the reverse path.
 220   float loss_correlation_;   // Likelihood the subsequent packet is lost.
 221   QuicBandwidth bandwidth_;
 222   QuicTime::Delta rtt_;
 223   size_t buffer_size_;       // In bytes.
 224   QuicTime::Delta delayed_ack_timer_;
 225
 226   DISALLOW_COPY_AND_ASSIGN(SendAlgorithmSimulator);
 227 };
 228
 229 }  // namespace net
 230
 231 #endif  // NET_QUIC_CONGESTION_CONTROL_SEND_ALGORITHM_SIMULATOR_H_