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