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