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
23using base::StringPrintf;
24
25namespace net {
26
27class 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_
232