blob: d04833bec48c84b1c2d4e2cbcb8387205870ebeb [file] [log] [blame]
// Copyright 2019 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 "net/nqe/network_congestion_analyzer.h"
#include <map>
#include <unordered_map>
#include "base/macros.h"
#include "base/optional.h"
#include "base/test/simple_test_tick_clock.h"
#include "base/time/time.h"
#include "net/nqe/network_quality.h"
#include "net/nqe/network_quality_estimator_test_util.h"
#include "net/nqe/observation_buffer.h"
#include "net/test/test_with_task_environment.h"
#include "testing/gtest/include/gtest/gtest.h"
namespace net {
namespace nqe {
namespace internal {
using NetworkCongestionAnalyzerTest = TestWithTaskEnvironment;
namespace {
constexpr float kEpsilon = 0.001f;
// These values should remain synchronized with the values in
// net/nqe/network_congestion_analyzer.cc.
constexpr int64_t kHighQueueingDelayMsec = 5000;
constexpr int64_t kMinEmptyQueueObservingTimeMsec = 1500;
constexpr base::TimeDelta
kLowQueueingDelayThresholds[EFFECTIVE_CONNECTION_TYPE_LAST] = {
base::TimeDelta::FromMilliseconds(400),
base::TimeDelta::FromMilliseconds(400),
base::TimeDelta::FromMilliseconds(400),
base::TimeDelta::FromMilliseconds(400),
base::TimeDelta::FromMilliseconds(40),
base::TimeDelta::FromMilliseconds(15)};
static constexpr size_t kMinScoreForValidSamples = 50;
// Verifies that the network queueing delay is computed correctly based on RTT
// and downlink throughput observations.
TEST_F(NetworkCongestionAnalyzerTest, TestComputingQueueingDelay) {
TestNetworkQualityEstimator network_quality_estimator;
base::SimpleTestTickClock tick_clock;
NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
std::map<uint64_t, CanonicalStats> recent_rtt_stats;
std::map<uint64_t, CanonicalStats> historical_rtt_stats;
int32_t downlink_kbps = nqe::internal::INVALID_RTT_THROUGHPUT;
// Checks that no result is updated when providing empty RTT observations and
// an invalid downlink throughput observation.
analyzer.ComputeRecentQueueingDelay(recent_rtt_stats, historical_rtt_stats,
downlink_kbps);
EXPECT_TRUE(analyzer.recent_queueing_delay().is_zero());
const uint64_t host_1 = 0x101010UL;
const uint64_t host_2 = 0x202020UL;
// Checks that the queueing delay is updated based on hosts with valid RTT
// observations. For example, the computation should be done by using data
// from host 1 only because host 2 does not provide a valid min RTT value.
std::map<int32_t, int32_t> recent_stat_host_1 = {{kStatVal0p, 1100}};
std::map<int32_t, int32_t> historical_stat_host_1 = {{kStatVal0p, 600}};
CanonicalStats recent_rtt_host_1 =
CanonicalStats(recent_stat_host_1, 1400, 5);
CanonicalStats historical_rtt_host_1 =
CanonicalStats(historical_stat_host_1, 1400, 15);
std::map<int32_t, int32_t> recent_stat_host_2 = {{kStatVal0p, 1200}};
std::map<int32_t, int32_t> historical_stat_host_2 = {{kStatVal50p, 1200}};
CanonicalStats recent_rtt_host_2 =
CanonicalStats(recent_stat_host_2, 1600, 3);
CanonicalStats historical_rtt_host_2 =
CanonicalStats(historical_stat_host_2, 1600, 8);
recent_rtt_stats.emplace(host_1, recent_rtt_host_1);
recent_rtt_stats.emplace(host_2, recent_rtt_host_2);
historical_rtt_stats.emplace(host_1, historical_rtt_host_1);
historical_rtt_stats.emplace(host_2, historical_rtt_host_2);
analyzer.ComputeRecentQueueingDelay(recent_rtt_stats, historical_rtt_stats,
downlink_kbps);
EXPECT_EQ(800, analyzer.recent_queueing_delay().InMilliseconds());
// Checks that the queueing delay is updated correctly based on all hosts when
// RTT observations and the throughput observation are valid.
historical_rtt_stats[host_2].canonical_pcts[kStatVal0p] = 1000;
downlink_kbps = 120;
analyzer.ComputeRecentQueueingDelay(recent_rtt_stats, historical_rtt_stats,
downlink_kbps);
EXPECT_EQ(700, analyzer.recent_queueing_delay().InMilliseconds());
EXPECT_NEAR(7.0, analyzer.recent_queue_length().value_or(0), kEpsilon);
}
} // namespace
// Verifies that a measurement period starts correctly when an empty queue
// observation shows up. An empty queue observation is made when the queueing
// delay is low and the number of in-flight requests is also low.
TEST_F(NetworkCongestionAnalyzerTest, TestStartingNewMeasurementPeriod) {
TestNetworkQualityEstimator network_quality_estimator;
base::SimpleTestTickClock tick_clock;
network_quality_estimator.set_effective_connection_type(
EFFECTIVE_CONNECTION_TYPE_2G);
NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
base::TimeDelta low_queueing_delay_sample =
kLowQueueingDelayThresholds[EFFECTIVE_CONNECTION_TYPE_2G];
// Checks that a new measurement period starts immediately if the queueing
// delay is low and the number of in-flight requests are equal or less than 1.
EXPECT_FALSE(
analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
EXPECT_TRUE(analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 1));
EXPECT_TRUE(analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 0));
// Checks that a new measurement period starts after waiting for a sufficient
// time interval when the number of in-flight requests is 2.
EXPECT_FALSE(
analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
tick_clock.Advance(
base::TimeDelta::FromMilliseconds(kMinEmptyQueueObservingTimeMsec / 2));
EXPECT_FALSE(
analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
tick_clock.Advance(
base::TimeDelta::FromMilliseconds(kMinEmptyQueueObservingTimeMsec / 2));
EXPECT_TRUE(analyzer.ShouldStartNewMeasurement(low_queueing_delay_sample, 2));
}
// Verifies that the peak queueing delay is correctly mapped to the count of
// in-flight requests that are responsible for that delay.
TEST_F(NetworkCongestionAnalyzerTest, TestUpdatePeakDelayMapping) {
TestNetworkQualityEstimator network_quality_estimator;
base::SimpleTestTickClock tick_clock;
network_quality_estimator.set_effective_connection_type(
EFFECTIVE_CONNECTION_TYPE_2G);
NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
EXPECT_EQ(base::nullopt,
analyzer.count_inflight_requests_causing_high_delay());
// Checks that the count of in-flight requests for peak queueing delay is
// correctly recorded.
// Case #1: the peak queueing delay was observed after the max count (7) of
// in-flight requests was observed.
const size_t expected_count_requests_1 = 7;
std::vector<std::pair<base::TimeDelta, size_t>> queueing_delay_samples_1 = {
std::make_pair(base::TimeDelta::FromMilliseconds(10), 1),
std::make_pair(base::TimeDelta::FromMilliseconds(10), 3),
std::make_pair(base::TimeDelta::FromMilliseconds(400), 5),
std::make_pair(base::TimeDelta::FromMilliseconds(800),
expected_count_requests_1),
std::make_pair(base::TimeDelta::FromMilliseconds(kHighQueueingDelayMsec),
5),
std::make_pair(base::TimeDelta::FromMilliseconds(1000), 3),
std::make_pair(base::TimeDelta::FromMilliseconds(700), 3),
std::make_pair(base::TimeDelta::FromMilliseconds(600), 1),
std::make_pair(base::TimeDelta::FromMilliseconds(300), 0),
};
for (const auto& sample : queueing_delay_samples_1) {
analyzer.UpdatePeakDelayMapping(sample.first, sample.second);
}
EXPECT_EQ(expected_count_requests_1,
analyzer.count_inflight_requests_causing_high_delay().value_or(0));
// Case #2: the peak queueing delay is observed before the max count (11) of
// in-flight requests was observed. The 8 requests should be responsible for
// the peak queueing delay.
const size_t expected_count_requests_2 = 10;
std::vector<std::pair<base::TimeDelta, size_t>> queueing_delay_samples_2 = {
std::make_pair(base::TimeDelta::FromMilliseconds(10), 1),
std::make_pair(base::TimeDelta::FromMilliseconds(10), 3),
std::make_pair(base::TimeDelta::FromMilliseconds(400), 5),
std::make_pair(base::TimeDelta::FromMilliseconds(800), 5),
std::make_pair(base::TimeDelta::FromMilliseconds(kHighQueueingDelayMsec),
expected_count_requests_2),
std::make_pair(base::TimeDelta::FromMilliseconds(3000), 11),
std::make_pair(base::TimeDelta::FromMilliseconds(700), 3),
std::make_pair(base::TimeDelta::FromMilliseconds(600), 1),
std::make_pair(base::TimeDelta::FromMilliseconds(300), 0),
};
for (const auto& sample : queueing_delay_samples_2) {
analyzer.UpdatePeakDelayMapping(sample.first, sample.second);
}
EXPECT_EQ(expected_count_requests_2,
analyzer.count_inflight_requests_causing_high_delay().value_or(0));
}
// Verifies that the network congestion analyzer can correctly determine whether
// a queueing delay sample is low or not under different effective connection
// types (ECTs).
TEST_F(NetworkCongestionAnalyzerTest, TestDetectLowQueueingDelay) {
TestNetworkQualityEstimator network_quality_estimator;
base::SimpleTestTickClock tick_clock;
NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
// Checks that computations are done correctly under all different ECTs.
for (int i = 0; i != net::EFFECTIVE_CONNECTION_TYPE_LAST; ++i) {
auto type = static_cast<net::EffectiveConnectionType>(i);
network_quality_estimator.set_effective_connection_type(type);
base::TimeDelta low_queueing_delay = kLowQueueingDelayThresholds[type];
EXPECT_TRUE(analyzer.IsQueueingDelayLow(low_queueing_delay));
EXPECT_FALSE(analyzer.IsQueueingDelayLow(
low_queueing_delay + base::TimeDelta::FromMilliseconds(1)));
}
}
// Verifies that the network congestion analyzer can correctly bucketize the
// peak queueing delay samples, and map the peak queueing delay samples to their
// corresponding queueing delay levels from Level1 to Level10.
TEST_F(NetworkCongestionAnalyzerTest, TestComputeQueueingDelayLevel) {
TestNetworkQualityEstimator network_quality_estimator;
base::SimpleTestTickClock tick_clock;
NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
std::vector<std::pair<base::TimeDelta, size_t>> queueing_delay_level_samples =
{std::make_pair(base::TimeDelta::FromMilliseconds(0), 1),
std::make_pair(base::TimeDelta::FromMilliseconds(25), 1),
std::make_pair(base::TimeDelta::FromMilliseconds(35), 2),
std::make_pair(base::TimeDelta::FromMilliseconds(55), 2),
std::make_pair(base::TimeDelta::FromMilliseconds(65), 3),
std::make_pair(base::TimeDelta::FromMilliseconds(115), 3),
std::make_pair(base::TimeDelta::FromMilliseconds(125), 4),
std::make_pair(base::TimeDelta::FromMilliseconds(245), 4),
std::make_pair(base::TimeDelta::FromMilliseconds(255), 5),
std::make_pair(base::TimeDelta::FromMilliseconds(495), 5),
std::make_pair(base::TimeDelta::FromMilliseconds(505), 6),
std::make_pair(base::TimeDelta::FromMilliseconds(995), 6),
std::make_pair(base::TimeDelta::FromMilliseconds(1005), 7),
std::make_pair(base::TimeDelta::FromMilliseconds(1995), 7),
std::make_pair(base::TimeDelta::FromMilliseconds(2005), 8),
std::make_pair(base::TimeDelta::FromMilliseconds(3995), 8),
std::make_pair(base::TimeDelta::FromMilliseconds(4005), 9),
std::make_pair(base::TimeDelta::FromMilliseconds(7995), 9),
std::make_pair(base::TimeDelta::FromMilliseconds(8005), 10),
std::make_pair(base::TimeDelta::FromMilliseconds(20000), 10)};
// Checks that all queueing delay samples are correctly mapped to
// their corresponding levels.
for (const auto& sample : queueing_delay_level_samples) {
EXPECT_EQ(sample.second,
analyzer.ComputePeakQueueingDelayLevel(sample.first));
}
}
// Verifies that the mapping sample is correctly evaluated with the computation
// of the count-delay mapping score. Also, verifies that samples are inserted
// into the cache when their mapping scores exceed the threshold.
TEST_F(NetworkCongestionAnalyzerTest, TestComputePeakDelayMappingSampleScore) {
TestNetworkQualityEstimator network_quality_estimator;
base::SimpleTestTickClock tick_clock;
NetworkCongestionAnalyzer analyzer(&network_quality_estimator, &tick_clock);
// Insert these samples into the cache. They are used to evaluate whether a
// new sample is valid or not.
std::map<size_t, base::TimeDelta> cached_requests_count_peak_delay_sample = {
{1, base::TimeDelta::FromMilliseconds(100)},
{2, base::TimeDelta::FromMilliseconds(200)},
{3, base::TimeDelta::FromMilliseconds(300)},
{4, base::TimeDelta::FromMilliseconds(400)},
{5, base::TimeDelta::FromMilliseconds(500)},
{6, base::TimeDelta::FromMilliseconds(600)},
{7, base::TimeDelta::FromMilliseconds(700)},
{8, base::TimeDelta::FromMilliseconds(800)},
{9, base::TimeDelta::FromMilliseconds(900)},
{10, base::TimeDelta::FromMilliseconds(1000)}};
for (const auto& sample : cached_requests_count_peak_delay_sample) {
analyzer.count_inflight_requests_for_peak_queueing_delay_ = sample.first;
analyzer.peak_queueing_delay_ = sample.second;
analyzer.UpdateRequestsCountAndPeakQueueingDelayMapping();
}
// Checks that the scores are correctly computed.
std::vector<std::pair<size_t, base::TimeDelta>> mapping_sample = {
std::make_pair(1, base::TimeDelta::FromMilliseconds(100)),
std::make_pair(2, base::TimeDelta::FromMilliseconds(200)),
std::make_pair(3, base::TimeDelta::FromMilliseconds(400)),
std::make_pair(4, base::TimeDelta::FromMilliseconds(800)),
std::make_pair(5, base::TimeDelta::FromMilliseconds(400)),
std::make_pair(6, base::TimeDelta::FromMilliseconds(200)),
std::make_pair(7, base::TimeDelta::FromMilliseconds(200)),
std::make_pair(8, base::TimeDelta::FromMilliseconds(200)),
std::make_pair(9, base::TimeDelta::FromMilliseconds(200)),
std::make_pair(10, base::TimeDelta::FromMilliseconds(900)),
std::make_pair(11, base::TimeDelta::FromMilliseconds(500))};
std::vector<size_t> ground_truth_mapping_score = {100, 100, 90, 60, 90, 60,
50, 40, 30, 90, 40};
EXPECT_EQ(mapping_sample.size(), ground_truth_mapping_score.size());
EXPECT_EQ(10u, analyzer.count_peak_queueing_delay_mapping_sample_);
for (size_t i = 0; i < mapping_sample.size(); ++i) {
EXPECT_EQ(analyzer.ComputePeakDelayMappingSampleScore(
mapping_sample[i].first, mapping_sample[i].second),
ground_truth_mapping_score[i]);
}
// Checks that only samples with a score higher than a threshold would be
// inserted into the cache.
size_t inserted_samples_count = 0;
size_t samples_count_before = 0;
bool is_inserted = false;
for (const auto& sample : mapping_sample) {
samples_count_before =
analyzer.count_inflight_requests_to_queueing_delay_[sample.first]
.size();
is_inserted =
analyzer.ComputePeakDelayMappingSampleScore(sample.first, sample.second)
.value_or(0) >= kMinScoreForValidSamples;
// Inserts the new sample.
analyzer.count_inflight_requests_for_peak_queueing_delay_ = sample.first;
analyzer.peak_queueing_delay_ = sample.second;
analyzer.UpdateRequestsCountAndPeakQueueingDelayMapping();
if (is_inserted) {
++inserted_samples_count;
EXPECT_EQ(
samples_count_before + 1,
analyzer.count_inflight_requests_to_queueing_delay_[sample.first]
.size());
} else {
EXPECT_EQ(
samples_count_before,
analyzer.count_inflight_requests_to_queueing_delay_[sample.first]
.size());
}
}
EXPECT_EQ(10u + inserted_samples_count,
analyzer.count_peak_queueing_delay_mapping_sample_);
}
} // namespace internal
} // namespace nqe
} // namespace net