blob: 76e61a344bd21a06e48089b9413d3ac8e7475dfe [file] [log] [blame]
// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <algorithm>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include "absl/strings/str_cat.h"
#include "quiche/quic/core/congestion_control/rtt_stats.h"
#include "quiche/quic/core/congestion_control/send_algorithm_interface.h"
#include "quiche/quic/core/quic_types.h"
#include "quiche/quic/core/quic_utils.h"
#include "quiche/quic/platform/api/quic_logging.h"
#include "quiche/quic/platform/api/quic_test.h"
#include "quiche/quic/test_tools/mock_clock.h"
#include "quiche/quic/test_tools/quic_config_peer.h"
#include "quiche/quic/test_tools/quic_connection_peer.h"
#include "quiche/quic/test_tools/quic_sent_packet_manager_peer.h"
#include "quiche/quic/test_tools/quic_test_utils.h"
#include "quiche/quic/test_tools/simulator/quic_endpoint.h"
#include "quiche/quic/test_tools/simulator/simulator.h"
#include "quiche/quic/test_tools/simulator/switch.h"
namespace quic {
namespace test {
namespace {
// Use the initial CWND of 10, as 32 is too much for the test network.
const uint32_t kInitialCongestionWindowPackets = 10;
// Test network parameters. Here, the topology of the network is:
//
// QUIC Sender
// |
// | <-- local link
// |
// Network switch
// * <-- the bottleneck queue in the direction
// | of the receiver
// |
// | <-- test link
// |
// |
// Receiver
//
// When setting the bandwidth of the local link and test link, choose
// a bandwidth lower than 20Mbps, as the clock-granularity of the
// simulator can only handle a granularity of 1us.
// Default settings between the switch and the sender.
const QuicBandwidth kLocalLinkBandwidth =
QuicBandwidth::FromKBitsPerSecond(10000);
const QuicTime::Delta kLocalPropagationDelay =
QuicTime::Delta::FromMilliseconds(2);
// Wired network settings. A typical desktop network setup, a
// high-bandwidth, 30ms test link to the receiver.
const QuicBandwidth kTestLinkWiredBandwidth =
QuicBandwidth::FromKBitsPerSecond(4000);
const QuicTime::Delta kTestLinkWiredPropagationDelay =
QuicTime::Delta::FromMilliseconds(50);
const QuicTime::Delta kTestWiredTransferTime =
kTestLinkWiredBandwidth.TransferTime(kMaxOutgoingPacketSize) +
kLocalLinkBandwidth.TransferTime(kMaxOutgoingPacketSize);
const QuicTime::Delta kTestWiredRtt =
(kTestLinkWiredPropagationDelay + kLocalPropagationDelay +
kTestWiredTransferTime) *
2;
const QuicByteCount kTestWiredBdp = kTestWiredRtt * kTestLinkWiredBandwidth;
// Small BDP, Bandwidth-policed network settings. In this scenario,
// the receiver has a low-bandwidth, short propagation-delay link,
// resulting in a small BDP. We model the policer by setting the
// queue size to only one packet.
const QuicBandwidth kTestLinkLowBdpBandwidth =
QuicBandwidth::FromKBitsPerSecond(200);
const QuicTime::Delta kTestLinkLowBdpPropagationDelay =
QuicTime::Delta::FromMilliseconds(50);
const QuicByteCount kTestPolicerQueue = kMaxOutgoingPacketSize;
// Satellite network settings. In a satellite network, the bottleneck
// buffer is typically sized for non-satellite links , but the
// propagation delay of the test link to the receiver is as much as a
// quarter second.
const QuicTime::Delta kTestSatellitePropagationDelay =
QuicTime::Delta::FromMilliseconds(250);
// Cellular scenarios. In a cellular network, the bottleneck queue at
// the edge of the network can be as great as 3MB.
const QuicBandwidth kTestLink2GBandwidth =
QuicBandwidth::FromKBitsPerSecond(100);
const QuicBandwidth kTestLink3GBandwidth =
QuicBandwidth::FromKBitsPerSecond(1500);
const QuicByteCount kCellularQueue = 3 * 1024 * 1024;
const QuicTime::Delta kTestCellularPropagationDelay =
QuicTime::Delta::FromMilliseconds(40);
// Small RTT scenario, below the per-ack-update threshold of 30ms.
const QuicTime::Delta kTestLinkSmallRTTDelay =
QuicTime::Delta::FromMilliseconds(10);
struct TestParams {
explicit TestParams(CongestionControlType congestion_control_type)
: congestion_control_type(congestion_control_type) {}
friend std::ostream& operator<<(std::ostream& os, const TestParams& p) {
os << "{ congestion_control_type: "
<< CongestionControlTypeToString(p.congestion_control_type);
os << " }";
return os;
}
const CongestionControlType congestion_control_type;
};
std::string TestParamToString(
const testing::TestParamInfo<TestParams>& params) {
return absl::StrCat(
CongestionControlTypeToString(params.param.congestion_control_type), "_");
}
// Constructs various test permutations.
std::vector<TestParams> GetTestParams() {
std::vector<TestParams> params;
for (const CongestionControlType congestion_control_type :
{kBBR, kCubicBytes, kRenoBytes, kPCC}) {
params.push_back(TestParams(congestion_control_type));
}
return params;
}
} // namespace
class SendAlgorithmTest : public QuicTestWithParam<TestParams> {
protected:
SendAlgorithmTest()
: simulator_(),
quic_sender_(&simulator_, "QUIC sender", "Receiver",
Perspective::IS_CLIENT, TestConnectionId()),
receiver_(&simulator_, "Receiver", "QUIC sender",
Perspective::IS_SERVER, TestConnectionId()) {
rtt_stats_ = quic_sender_.connection()->sent_packet_manager().GetRttStats();
sender_ = SendAlgorithmInterface::Create(
simulator_.GetClock(), rtt_stats_,
QuicSentPacketManagerPeer::GetUnackedPacketMap(
QuicConnectionPeer::GetSentPacketManager(
quic_sender_.connection())),
GetParam().congestion_control_type, &random_, &stats_,
kInitialCongestionWindowPackets, nullptr);
quic_sender_.RecordTrace();
QuicConnectionPeer::SetSendAlgorithm(quic_sender_.connection(), sender_);
const int kTestMaxPacketSize = 1350;
quic_sender_.connection()->SetMaxPacketLength(kTestMaxPacketSize);
clock_ = simulator_.GetClock();
simulator_.set_random_generator(&random_);
uint64_t seed = QuicRandom::GetInstance()->RandUint64();
random_.set_seed(seed);
QUIC_LOG(INFO) << "SendAlgorithmTest simulator set up. Seed: " << seed;
}
// Creates a simulated network, with default settings between the
// sender and the switch and the given settings from the switch to
// the receiver.
void CreateSetup(const QuicBandwidth& test_bandwidth,
const QuicTime::Delta& test_link_delay,
QuicByteCount bottleneck_queue_length) {
switch_ = std::make_unique<simulator::Switch>(&simulator_, "Switch", 8,
bottleneck_queue_length);
quic_sender_link_ = std::make_unique<simulator::SymmetricLink>(
&quic_sender_, switch_->port(1), kLocalLinkBandwidth,
kLocalPropagationDelay);
receiver_link_ = std::make_unique<simulator::SymmetricLink>(
&receiver_, switch_->port(2), test_bandwidth, test_link_delay);
}
void DoSimpleTransfer(QuicByteCount transfer_size, QuicTime::Delta deadline) {
quic_sender_.AddBytesToTransfer(transfer_size);
bool simulator_result = simulator_.RunUntilOrTimeout(
[this]() { return quic_sender_.bytes_to_transfer() == 0; }, deadline);
EXPECT_TRUE(simulator_result)
<< "Simple transfer failed. Bytes remaining: "
<< quic_sender_.bytes_to_transfer();
}
void SendBursts(size_t number_of_bursts, QuicByteCount bytes,
QuicTime::Delta rtt, QuicTime::Delta wait_time) {
ASSERT_EQ(0u, quic_sender_.bytes_to_transfer());
for (size_t i = 0; i < number_of_bursts; i++) {
quic_sender_.AddBytesToTransfer(bytes);
// Transfer data and wait for three seconds between each transfer.
simulator_.RunFor(wait_time);
// Ensure the connection did not time out.
ASSERT_TRUE(quic_sender_.connection()->connected());
ASSERT_TRUE(receiver_.connection()->connected());
}
simulator_.RunFor(wait_time + rtt);
EXPECT_EQ(0u, quic_sender_.bytes_to_transfer());
}
// Estimates the elapsed time for a given transfer size, given the
// bottleneck bandwidth and link propagation delay.
QuicTime::Delta EstimatedElapsedTime(
QuicByteCount transfer_size_bytes, QuicBandwidth test_link_bandwidth,
const QuicTime::Delta& test_link_delay) const {
return test_link_bandwidth.TransferTime(transfer_size_bytes) +
2 * test_link_delay;
}
QuicTime QuicSenderStartTime() {
return quic_sender_.connection()->GetStats().connection_creation_time;
}
void PrintTransferStats() {
const QuicConnectionStats& stats = quic_sender_.connection()->GetStats();
QUIC_LOG(INFO) << "Summary for scenario " << GetParam();
QUIC_LOG(INFO) << "Sender stats is " << stats;
const double rtx_rate =
static_cast<double>(stats.bytes_retransmitted) / stats.bytes_sent;
QUIC_LOG(INFO) << "Retransmit rate (num_rtx/num_total_sent): " << rtx_rate;
QUIC_LOG(INFO) << "Connection elapsed time: "
<< (clock_->Now() - QuicSenderStartTime()).ToMilliseconds()
<< " (ms)";
}
simulator::Simulator simulator_;
simulator::QuicEndpoint quic_sender_;
simulator::QuicEndpoint receiver_;
std::unique_ptr<simulator::Switch> switch_;
std::unique_ptr<simulator::SymmetricLink> quic_sender_link_;
std::unique_ptr<simulator::SymmetricLink> receiver_link_;
QuicConnectionStats stats_;
SimpleRandom random_;
// Owned by different components of the connection.
const QuicClock* clock_;
const RttStats* rtt_stats_;
SendAlgorithmInterface* sender_;
};
INSTANTIATE_TEST_SUITE_P(SendAlgorithmTests, SendAlgorithmTest,
::testing::ValuesIn(GetTestParams()),
TestParamToString);
// Test a simple long data transfer in the default setup.
TEST_P(SendAlgorithmTest, SimpleWiredNetworkTransfer) {
CreateSetup(kTestLinkWiredBandwidth, kTestLinkWiredPropagationDelay,
kTestWiredBdp);
const QuicByteCount kTransferSizeBytes = 12 * 1024 * 1024;
const QuicTime::Delta maximum_elapsed_time =
EstimatedElapsedTime(kTransferSizeBytes, kTestLinkWiredBandwidth,
kTestLinkWiredPropagationDelay) *
1.2;
DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
PrintTransferStats();
}
TEST_P(SendAlgorithmTest, LowBdpPolicedNetworkTransfer) {
CreateSetup(kTestLinkLowBdpBandwidth, kTestLinkLowBdpPropagationDelay,
kTestPolicerQueue);
const QuicByteCount kTransferSizeBytes = 5 * 1024 * 1024;
const QuicTime::Delta maximum_elapsed_time =
EstimatedElapsedTime(kTransferSizeBytes, kTestLinkLowBdpBandwidth,
kTestLinkLowBdpPropagationDelay) *
1.2;
DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
PrintTransferStats();
}
TEST_P(SendAlgorithmTest, AppLimitedBurstsOverWiredNetwork) {
CreateSetup(kTestLinkWiredBandwidth, kTestLinkWiredPropagationDelay,
kTestWiredBdp);
const QuicByteCount kBurstSizeBytes = 512;
const int kNumBursts = 20;
const QuicTime::Delta kWaitTime = QuicTime::Delta::FromSeconds(3);
SendBursts(kNumBursts, kBurstSizeBytes, kTestWiredRtt, kWaitTime);
PrintTransferStats();
const QuicTime::Delta estimated_burst_time =
EstimatedElapsedTime(kBurstSizeBytes, kTestLinkWiredBandwidth,
kTestLinkWiredPropagationDelay) +
kWaitTime;
const QuicTime::Delta max_elapsed_time =
kNumBursts * estimated_burst_time + kWaitTime;
const QuicTime::Delta actual_elapsed_time =
clock_->Now() - QuicSenderStartTime();
EXPECT_GE(max_elapsed_time, actual_elapsed_time);
}
TEST_P(SendAlgorithmTest, SatelliteNetworkTransfer) {
CreateSetup(kTestLinkWiredBandwidth, kTestSatellitePropagationDelay,
kTestWiredBdp);
const QuicByteCount kTransferSizeBytes = 12 * 1024 * 1024;
const QuicTime::Delta maximum_elapsed_time =
EstimatedElapsedTime(kTransferSizeBytes, kTestLinkWiredBandwidth,
kTestSatellitePropagationDelay) *
1.25;
DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
PrintTransferStats();
}
TEST_P(SendAlgorithmTest, 2GNetworkTransfer) {
CreateSetup(kTestLink2GBandwidth, kTestCellularPropagationDelay,
kCellularQueue);
const QuicByteCount kTransferSizeBytes = 1024 * 1024;
const QuicTime::Delta maximum_elapsed_time =
EstimatedElapsedTime(kTransferSizeBytes, kTestLink2GBandwidth,
kTestCellularPropagationDelay) *
1.2;
DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
PrintTransferStats();
}
TEST_P(SendAlgorithmTest, 3GNetworkTransfer) {
CreateSetup(kTestLink3GBandwidth, kTestCellularPropagationDelay,
kCellularQueue);
const QuicByteCount kTransferSizeBytes = 5 * 1024 * 1024;
const QuicTime::Delta maximum_elapsed_time =
EstimatedElapsedTime(kTransferSizeBytes, kTestLink3GBandwidth,
kTestCellularPropagationDelay) *
1.2;
DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
PrintTransferStats();
}
TEST_P(SendAlgorithmTest, LowRTTTransfer) {
CreateSetup(kTestLinkWiredBandwidth, kTestLinkSmallRTTDelay, kCellularQueue);
const QuicByteCount kTransferSizeBytes = 12 * 1024 * 1024;
const QuicTime::Delta maximum_elapsed_time =
EstimatedElapsedTime(kTransferSizeBytes, kTestLinkWiredBandwidth,
kTestLinkSmallRTTDelay) *
1.2;
DoSimpleTransfer(kTransferSizeBytes, maximum_elapsed_time);
PrintTransferStats();
}
} // namespace test
} // namespace quic