diff options
Diffstat (limited to 'chromium/net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_test.cc')
| -rw-r--r-- | chromium/net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_test.cc | 371 |
1 files changed, 371 insertions, 0 deletions
diff --git a/chromium/net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_test.cc b/chromium/net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_test.cc new file mode 100644 index 00000000000..c07508c41bf --- /dev/null +++ b/chromium/net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_test.cc @@ -0,0 +1,371 @@ +// 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 "net/third_party/quiche/src/quic/core/congestion_control/rtt_stats.h" +#include "net/third_party/quiche/src/quic/core/congestion_control/send_algorithm_interface.h" +#include "net/third_party/quiche/src/quic/core/quic_types.h" +#include "net/third_party/quiche/src/quic/core/quic_utils.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_logging.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_ptr_util.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_str_cat.h" +#include "net/third_party/quiche/src/quic/platform/api/quic_test.h" +#include "net/third_party/quiche/src/quic/test_tools/mock_clock.h" +#include "net/third_party/quiche/src/quic/test_tools/quic_config_peer.h" +#include "net/third_party/quiche/src/quic/test_tools/quic_connection_peer.h" +#include "net/third_party/quiche/src/quic/test_tools/quic_sent_packet_manager_peer.h" +#include "net/third_party/quiche/src/quic/test_tools/quic_test_utils.h" +#include "net/third_party/quiche/src/quic/test_tools/simulator/quic_endpoint.h" +#include "net/third_party/quiche/src/quic/test_tools/simulator/simulator.h" +#include "net/third_party/quiche/src/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); + +const char* CongestionControlTypeToString(CongestionControlType cc_type) { + switch (cc_type) { + case kCubicBytes: + return "CUBIC_BYTES"; + case kRenoBytes: + return "RENO_BYTES"; + case kBBR: + return "BBR"; + case kPCC: + return "PCC"; + default: + QUIC_DLOG(FATAL) << "Unexpected CongestionControlType"; + return nullptr; + } +} + +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 QuicStrCat( + 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); + quic_sender_.RecordTrace(); + + QuicConnectionPeer::SetSendAlgorithm(quic_sender_.connection(), sender_); + 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_ = QuicMakeUnique<simulator::Switch>(&simulator_, "Switch", 8, + bottleneck_queue_length); + quic_sender_link_ = QuicMakeUnique<simulator::SymmetricLink>( + &quic_sender_, switch_->port(1), kLocalLinkBandwidth, + kLocalPropagationDelay); + receiver_link_ = QuicMakeUnique<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 |