#define NET_QUIC_CONGESTION_CONTROL_SEND_ALGORITHM_SIMULATOR_H_
#include <algorithm>
+#include <string>
+#include <vector>
#include "base/basictypes.h"
+#include "base/format_macros.h"
+#include "base/strings/stringprintf.h"
#include "net/quic/congestion_control/send_algorithm_interface.h"
#include "net/quic/quic_protocol.h"
#include "net/quic/quic_time.h"
#include "net/quic/test_tools/mock_clock.h"
#include "net/quic/test_tools/quic_test_utils.h"
+using base::StringPrintf;
+
namespace net {
class SendAlgorithmSimulator {
public:
+ struct Sender {
+ Sender(SendAlgorithmInterface* send_algorithm, RttStats* rtt_stats);
+
+ void RecordStats() {
+ QuicByteCount cwnd = send_algorithm->GetCongestionWindow();
+ max_cwnd = std::max(max_cwnd, cwnd);
+ min_cwnd = std::min(min_cwnd, cwnd);
+ if (last_cwnd > cwnd) {
+ max_cwnd_drop = std::max(max_cwnd_drop, last_cwnd - cwnd);
+ }
+ last_cwnd = cwnd;
+ }
+
+ std::string DebugString() {
+ return StringPrintf("observed goodput(bytes/s):%" PRId64
+ " loss rate:%f"
+ " cwnd:%" PRIu64
+ " max_cwnd:%" PRIu64 " min_cwnd:%" PRIu64
+ " max_cwnd_drop:%" PRIu64,
+ last_transfer_bandwidth.ToBytesPerSecond(),
+ last_transfer_loss_rate,
+ send_algorithm->GetCongestionWindow(),
+ max_cwnd, min_cwnd, max_cwnd_drop);
+ }
+
+ SendAlgorithmInterface* send_algorithm;
+ RttStats* rtt_stats;
+
+ // Last sequence number the sender sent.
+ QuicPacketSequenceNumber last_sent;
+ // Last packet sequence number acked.
+ QuicPacketSequenceNumber last_acked;
+ // Packet sequence number to ack up to.
+ QuicPacketSequenceNumber next_acked;
+
+ // Stats collected for understanding the congestion control.
+ QuicByteCount max_cwnd;
+ QuicByteCount min_cwnd;
+ QuicByteCount max_cwnd_drop;
+ QuicByteCount last_cwnd;
+
+ QuicBandwidth last_transfer_bandwidth;
+ float last_transfer_loss_rate;
+ };
+
+ struct Transfer {
+ Transfer(Sender* sender, QuicByteCount num_bytes, QuicTime start_time)
+ : sender(sender),
+ num_bytes(num_bytes),
+ bytes_acked(0),
+ bytes_lost(0),
+ bytes_in_flight(0),
+ start_time(start_time) {}
+
+ Sender* sender;
+ QuicByteCount num_bytes;
+ QuicByteCount bytes_acked;
+ QuicByteCount bytes_lost;
+ QuicByteCount bytes_in_flight;
+ QuicTime start_time;
+ };
+
struct SentPacket {
+ SentPacket()
+ : sequence_number(0),
+ send_time(QuicTime::Zero()),
+ ack_time(QuicTime::Zero()),
+ lost(false),
+ transfer(NULL) {}
SentPacket(QuicPacketSequenceNumber sequence_number,
QuicTime send_time,
- QuicTime ack_time)
+ QuicTime ack_time,
+ bool lost,
+ Transfer* transfer)
: sequence_number(sequence_number),
send_time(send_time),
- ack_time(ack_time) {}
+ ack_time(ack_time),
+ lost(lost),
+ transfer(transfer) {}
+
QuicPacketSequenceNumber sequence_number;
QuicTime send_time;
QuicTime ack_time;
+ bool lost;
+ Transfer* transfer;
};
// |rtt_stats| should be the same RttStats used by the |send_algorithm|.
- SendAlgorithmSimulator(SendAlgorithmInterface* send_algorithm,
- MockClock* clock_,
- RttStats* rtt_stats,
+ SendAlgorithmSimulator(MockClock* clock_,
QuicBandwidth bandwidth,
QuicTime::Delta rtt);
~SendAlgorithmSimulator();
+ void set_bandwidth(QuicBandwidth bandwidth) {
+ bandwidth_ = bandwidth;
+ }
+
void set_forward_loss_rate(float loss_rate) {
DCHECK_LT(loss_rate, 1.0f);
forward_loss_rate_ = loss_rate;
buffer_size_ = buffer_size_bytes;
}
- // Sends the specified number of bytes as quickly as possible and returns the
- // average bandwidth in bytes per second. The time elapsed is based on
- // waiting for all acks to arrive.
- QuicBandwidth SendBytes(size_t num_bytes);
+ void set_delayed_ack_timer(QuicTime::Delta delayed_ack_timer) {
+ delayed_ack_timer_ = delayed_ack_timer;
+ }
+
+ // Advance the time by |delta| without sending anything.
+ void AdvanceTime(QuicTime::Delta delta);
+
+ // Adds a pending sender. The send will run when TransferBytes is called.
+ // Adding two transfers with the same sender is unsupported.
+ void AddTransfer(Sender* sender, size_t num_bytes);
+
+ // Adds a pending sending to start at the specified time.
+ void AddTransfer(Sender* sender, size_t num_bytes, QuicTime start_time);
- const RttStats* rtt_stats() const { return rtt_stats_; }
+ // Convenience method to transfer all bytes.
+ void TransferBytes();
- QuicByteCount max_cwnd() const { return max_cwnd_; }
- QuicByteCount min_cwnd() const { return min_cwnd_; }
- QuicByteCount max_cwnd_drop() const { return max_cwnd_drop_; }
- QuicByteCount last_cwnd() const { return last_cwnd_; }
+ // Transfers bytes through the connection until |max_bytes| are reached,
+ // |max_time| is reached, or all senders have finished sending. If max_bytes
+ // is 0, it does not apply, and if |max_time| is Zero, no time limit applies.
+ void TransferBytes(QuicByteCount max_bytes, QuicTime::Delta max_time);
private:
+ // A pending packet event, either a send or an ack.
+ struct PacketEvent {
+ PacketEvent(QuicTime::Delta time_delta, Transfer* transfer)
+ : time_delta(time_delta),
+ transfer(transfer) {}
+
+ QuicTime::Delta time_delta;
+ Transfer* transfer;
+ };
+
+ // NextSendTime returns the next time any of the pending transfers send,
+ // and populates transfer if the send time is not infinite.
+ PacketEvent NextSendEvent();
+
// NextAckTime takes into account packet loss in both forward and reverse
// direction, as well as delayed ack behavior.
- QuicTime::Delta NextAckDelta();
-
- // Whether all packets in sent_packets_ are lost.
- bool AllPacketsLost();
+ PacketEvent NextAckEvent();
// Sets the next acked.
- void FindNextAcked();
+ QuicTime::Delta FindNextAcked(Transfer* transfer);
+
+ // Sets the |next_acked| packet for the |transfer| starting at the specified
+ // |last_acked|. Returns QuicTime::Delta::Infinite and doesn't set
+ // |next_acked| if there is no ack after |last_acked|.
+ QuicTime::Delta FindNextAck(const Transfer* transfer,
+ QuicPacketSequenceNumber last_acked,
+ QuicPacketSequenceNumber* next_acked) const;
+
+ // Returns true if any of the packets |transfer| is waiting for less than
+ // next_acked have been lost.
+ bool HasRecentLostPackets(const Transfer* transfer,
+ QuicPacketSequenceNumber next_acked) const;
// Process all the acks that should have arrived by the current time, and
// lose any packets that are missing. Returns the number of bytes acked.
- int HandlePendingAck();
-
- void SendDataNow();
- void RecordStats();
+ void HandlePendingAck(Transfer* transfer);
- // Advance the time by |delta| without sending anything.
- void AdvanceTime(QuicTime::Delta delta);
+ void SendDataNow(Transfer* transfer);
- // Elapsed time from the start of the connection.
- QuicTime ElapsedTime();
+ // List of all pending transfers waiting to use the connection.
+ std::vector<Transfer> pending_transfers_;
- SendAlgorithmInterface* send_algorithm_;
MockClock* clock_;
- RttStats* rtt_stats_;
- // Next packet sequence number to send.
- QuicPacketSequenceNumber next_sent_;
- // Last packet sequence number acked.
- QuicPacketSequenceNumber last_acked_;
- // Packet sequence number to ack up to.
- QuicPacketSequenceNumber next_acked_;
// Whether the next ack should be lost.
bool lose_next_ack_;
- QuicByteCount bytes_in_flight_;
// The times acks are expected, assuming acks are not lost and every packet
// is acked.
std::list<SentPacket> sent_packets_;
QuicBandwidth bandwidth_;
QuicTime::Delta rtt_;
size_t buffer_size_; // In bytes.
-
- // Stats collected for understanding the congestion control.
- QuicByteCount max_cwnd_;
- QuicByteCount min_cwnd_;
- QuicByteCount max_cwnd_drop_;
- QuicByteCount last_cwnd_;
+ QuicTime::Delta delayed_ack_timer_;
DISALLOW_COPY_AND_ASSIGN(SendAlgorithmSimulator);
};