Add exponential backoff of retransmissions for a given packet
Bug: webrtc:8624
Change-Id: I8900c54935bf1da11ac74665426b0d198bd6d814
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/30900
Reviewed-by: Sergey Silkin <ssilkin@webrtc.org>
Commit-Queue: Erik Språng <sprang@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#29625}
diff --git a/modules/video_coding/BUILD.gn b/modules/video_coding/BUILD.gn
index c14186b..e5e80d1 100644
--- a/modules/video_coding/BUILD.gn
+++ b/modules/video_coding/BUILD.gn
@@ -46,9 +46,12 @@
deps = [
":packet",
"..:module_api",
+ "../../api/units:time_delta",
+ "../../api/units:timestamp",
"../../rtc_base:checks",
"../../rtc_base:rtc_base_approved",
"../../rtc_base:rtc_numerics",
+ "../../rtc_base/experiments:field_trial_parser",
"../../system_wrappers",
"../../system_wrappers:field_trial",
"../utility",
diff --git a/modules/video_coding/nack_module.cc b/modules/video_coding/nack_module.cc
index 45f0563..e6fd9f3 100644
--- a/modules/video_coding/nack_module.cc
+++ b/modules/video_coding/nack_module.cc
@@ -13,8 +13,10 @@
#include <algorithm>
#include <limits>
+#include "api/units/timestamp.h"
#include "modules/utility/include/process_thread.h"
#include "rtc_base/checks.h"
+#include "rtc_base/experiments/field_trial_parser.h"
#include "rtc_base/logging.h"
#include "system_wrappers/include/field_trial.h"
@@ -55,6 +57,37 @@
sent_at_time(-1),
retries(0) {}
+NackModule::BackoffSettings::BackoffSettings(TimeDelta min_retry,
+ TimeDelta max_rtt,
+ double base)
+ : min_retry_interval(min_retry), max_rtt(max_rtt), base(base) {}
+
+absl::optional<NackModule::BackoffSettings>
+NackModule::BackoffSettings::ParseFromFieldTrials() {
+ // Matches magic number in RTPSender::OnReceivedNack().
+ const TimeDelta kDefaultMinRetryInterval = TimeDelta::ms(5);
+ // Upper bound on link-delay considered for exponential backoff.
+ // Selected so that cumulative delay with 1.25 base and 10 retries ends up
+ // below 3s, since above that there will be a FIR generated instead.
+ const TimeDelta kDefaultMaxRtt = TimeDelta::ms(160);
+ // Default base for exponential backoff, adds 25% RTT delay for each retry.
+ const double kDefaultBase = 1.25;
+
+ FieldTrialParameter<bool> enabled("enabled", false);
+ FieldTrialParameter<TimeDelta> min_retry("min_retry",
+ kDefaultMinRetryInterval);
+ FieldTrialParameter<TimeDelta> max_rtt("max_rtt", kDefaultMaxRtt);
+ FieldTrialParameter<double> base("base", kDefaultBase);
+ ParseFieldTrial({&enabled, &min_retry, &max_rtt, &base},
+ field_trial::FindFullName("WebRTC-ExponentialNackBackoff"));
+
+ if (enabled) {
+ return NackModule::BackoffSettings(min_retry.Get(), max_rtt.Get(),
+ base.Get());
+ }
+ return absl::nullopt;
+}
+
NackModule::NackModule(Clock* clock,
NackSender* nack_sender,
KeyFrameRequestSender* keyframe_request_sender)
@@ -66,7 +99,8 @@
rtt_ms_(kDefaultRttMs),
newest_seq_num_(0),
next_process_time_ms_(-1),
- send_nack_delay_ms_(GetSendNackDelay()) {
+ send_nack_delay_ms_(GetSendNackDelay()),
+ backoff_settings_(BackoffSettings::ParseFromFieldTrials()) {
RTC_DCHECK(clock_);
RTC_DCHECK(nack_sender_);
RTC_DCHECK(keyframe_request_sender_);
@@ -258,13 +292,26 @@
std::vector<uint16_t> NackModule::GetNackBatch(NackFilterOptions options) {
bool consider_seq_num = options != kTimeOnly;
bool consider_timestamp = options != kSeqNumOnly;
- int64_t now_ms = clock_->TimeInMilliseconds();
+ Timestamp now = clock_->CurrentTime();
std::vector<uint16_t> nack_batch;
auto it = nack_list_.begin();
while (it != nack_list_.end()) {
+ TimeDelta resend_delay = TimeDelta::ms(rtt_ms_);
+ if (backoff_settings_) {
+ resend_delay =
+ std::max(resend_delay, backoff_settings_->min_retry_interval);
+ if (it->second.retries > 1) {
+ TimeDelta exponential_backoff =
+ std::min(TimeDelta::ms(rtt_ms_), backoff_settings_->max_rtt) *
+ std::pow(backoff_settings_->base, it->second.retries - 1);
+ resend_delay = std::max(resend_delay, exponential_backoff);
+ }
+ }
+
bool delay_timed_out =
- now_ms - it->second.created_at_time >= send_nack_delay_ms_;
- bool nack_on_rtt_passed = now_ms - it->second.sent_at_time >= rtt_ms_;
+ now.ms() - it->second.created_at_time >= send_nack_delay_ms_;
+ bool nack_on_rtt_passed =
+ now.ms() - it->second.sent_at_time >= resend_delay.ms();
bool nack_on_seq_num_passed =
it->second.sent_at_time == -1 &&
AheadOrAt(newest_seq_num_, it->second.send_at_seq_num);
@@ -272,7 +319,7 @@
(consider_timestamp && nack_on_rtt_passed))) {
nack_batch.emplace_back(it->second.seq_num);
++it->second.retries;
- it->second.sent_at_time = now_ms;
+ it->second.sent_at_time = now.ms();
if (it->second.retries >= kMaxNackRetries) {
RTC_LOG(LS_WARNING) << "Sequence number " << it->second.seq_num
<< " removed from NACK list due to max retries.";
diff --git a/modules/video_coding/nack_module.h b/modules/video_coding/nack_module.h
index fba55b1..d4f705b 100644
--- a/modules/video_coding/nack_module.h
+++ b/modules/video_coding/nack_module.h
@@ -17,6 +17,7 @@
#include <set>
#include <vector>
+#include "api/units/time_delta.h"
#include "modules/include/module.h"
#include "modules/include/module_common_types.h"
#include "modules/video_coding/histogram.h"
@@ -64,6 +65,19 @@
int64_t sent_at_time;
int retries;
};
+
+ struct BackoffSettings {
+ BackoffSettings(TimeDelta min_retry, TimeDelta max_rtt, double base);
+ static absl::optional<BackoffSettings> ParseFromFieldTrials();
+
+ // Min time between nacks.
+ const TimeDelta min_retry_interval;
+ // Upper bound on link-delay considered for exponential backoff.
+ const TimeDelta max_rtt;
+ // Base for the exponential backoff.
+ const double base;
+ };
+
void AddPacketsToNack(uint16_t seq_num_start, uint16_t seq_num_end)
RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
@@ -106,6 +120,8 @@
// Adds a delay before send nack on packet received.
const int64_t send_nack_delay_ms_;
+
+ const absl::optional<BackoffSettings> backoff_settings_;
};
} // namespace webrtc
diff --git a/modules/video_coding/nack_module_unittest.cc b/modules/video_coding/nack_module_unittest.cc
index 2028092..c9a2023 100644
--- a/modules/video_coding/nack_module_unittest.cc
+++ b/modules/video_coding/nack_module_unittest.cc
@@ -10,6 +10,7 @@
#include "modules/video_coding/nack_module.h"
+#include <algorithm>
#include <cstdint>
#include <cstring>
#include <memory>
@@ -19,15 +20,20 @@
#include "test/gtest.h"
namespace webrtc {
-class TestNackModule : public ::testing::Test,
+class TestNackModule : public ::testing::TestWithParam<bool>,
public NackSender,
public KeyFrameRequestSender {
protected:
TestNackModule()
: clock_(new SimulatedClock(0)),
+ field_trial_(GetParam()
+ ? "WebRTC-ExponentialNackBackoff/enabled:true/"
+ : "WebRTC-ExponentialNackBackoff/enabled:false/"),
nack_module_(clock_.get(), this, this),
keyframes_requested_(0) {}
+ void SetUp() override { nack_module_.UpdateRtt(kDefaultRttMs); }
+
void SendNack(const std::vector<uint16_t>& sequence_numbers,
bool buffering_allowed) override {
sent_nacks_.insert(sent_nacks_.end(), sequence_numbers.begin(),
@@ -36,20 +42,22 @@
void RequestKeyFrame() override { ++keyframes_requested_; }
+ static constexpr int64_t kDefaultRttMs = 20;
std::unique_ptr<SimulatedClock> clock_;
+ test::ScopedFieldTrials field_trial_;
NackModule nack_module_;
std::vector<uint16_t> sent_nacks_;
int keyframes_requested_;
};
-TEST_F(TestNackModule, NackOnePacket) {
+TEST_P(TestNackModule, NackOnePacket) {
nack_module_.OnReceivedPacket(1, false, false);
nack_module_.OnReceivedPacket(3, false, false);
EXPECT_EQ(1u, sent_nacks_.size());
EXPECT_EQ(2, sent_nacks_[0]);
}
-TEST_F(TestNackModule, WrappingSeqNum) {
+TEST_P(TestNackModule, WrappingSeqNum) {
nack_module_.OnReceivedPacket(0xfffe, false, false);
nack_module_.OnReceivedPacket(1, false, false);
EXPECT_EQ(2u, sent_nacks_.size());
@@ -57,7 +65,7 @@
EXPECT_EQ(0, sent_nacks_[1]);
}
-TEST_F(TestNackModule, WrappingSeqNumClearToKeyframe) {
+TEST_P(TestNackModule, WrappingSeqNumClearToKeyframe) {
nack_module_.OnReceivedPacket(0xfffe, false, false);
nack_module_.OnReceivedPacket(1, false, false);
EXPECT_EQ(2u, sent_nacks_.size());
@@ -121,7 +129,7 @@
EXPECT_EQ(1006, sent_nacks_[502]);
}
-TEST_F(TestNackModule, DontBurstOnTimeSkip) {
+TEST_P(TestNackModule, DontBurstOnTimeSkip) {
nack_module_.Process();
clock_->AdvanceTimeMilliseconds(20);
EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
@@ -148,54 +156,80 @@
EXPECT_EQ(19, nack_module_.TimeUntilNextProcess());
}
-TEST_F(TestNackModule, ResendNack) {
+TEST_P(TestNackModule, ResendNack) {
nack_module_.OnReceivedPacket(1, false, false);
nack_module_.OnReceivedPacket(3, false, false);
- EXPECT_EQ(1u, sent_nacks_.size());
+ size_t expected_nacks_sent = 1;
+ EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
EXPECT_EQ(2, sent_nacks_[0]);
- // Default RTT is 100
- clock_->AdvanceTimeMilliseconds(99);
- nack_module_.Process();
- EXPECT_EQ(1u, sent_nacks_.size());
+ if (GetParam()) {
+ // Retry has to wait at least 5ms by default.
+ nack_module_.UpdateRtt(1);
+ clock_->AdvanceTimeMilliseconds(4);
+ nack_module_.Process(); // Too early.
+ EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
- clock_->AdvanceTimeMilliseconds(1);
- nack_module_.Process();
- EXPECT_EQ(2u, sent_nacks_.size());
+ clock_->AdvanceTimeMilliseconds(1);
+ nack_module_.Process(); // Now allowed.
+ EXPECT_EQ(++expected_nacks_sent, sent_nacks_.size());
+ } else {
+ nack_module_.UpdateRtt(1);
+ clock_->AdvanceTimeMilliseconds(1);
+ nack_module_.Process(); // Fast retransmit allowed.
+ EXPECT_EQ(++expected_nacks_sent, sent_nacks_.size());
+ }
- nack_module_.UpdateRtt(50);
- clock_->AdvanceTimeMilliseconds(100);
- nack_module_.Process();
- EXPECT_EQ(3u, sent_nacks_.size());
+ // N:th try has to wait b^(N-1) * rtt by default.
+ const double b = GetParam() ? 1.25 : 1.0;
+ for (int i = 2; i < 10; ++i) {
+ // Change RTT, above the 40ms max for exponential backoff.
+ TimeDelta rtt = TimeDelta::ms(160); // + (i * 10 - 40)
+ nack_module_.UpdateRtt(rtt.ms());
- clock_->AdvanceTimeMilliseconds(50);
- nack_module_.Process();
- EXPECT_EQ(4u, sent_nacks_.size());
+ // RTT gets capped at 160ms in backoff calculations.
+ TimeDelta expected_backoff_delay =
+ std::pow(b, i - 1) * std::min(rtt, TimeDelta::ms(160));
- nack_module_.OnReceivedPacket(2, false, false);
- clock_->AdvanceTimeMilliseconds(50);
+ // Move to one millisecond before next allowed NACK.
+ clock_->AdvanceTimeMilliseconds(expected_backoff_delay.ms() - 1);
+ nack_module_.Process();
+ EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
+
+ // Move to one millisecond after next allowed NACK.
+ // After rather than on to avoid rounding errors.
+ clock_->AdvanceTimeMilliseconds(2);
+ nack_module_.Process(); // Now allowed.
+ EXPECT_EQ(++expected_nacks_sent, sent_nacks_.size());
+ }
+
+ // Giving up after 10 tries.
+ clock_->AdvanceTimeMilliseconds(3000);
nack_module_.Process();
- EXPECT_EQ(4u, sent_nacks_.size());
+ EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
}
-TEST_F(TestNackModule, ResendPacketMaxRetries) {
+TEST_P(TestNackModule, ResendPacketMaxRetries) {
nack_module_.OnReceivedPacket(1, false, false);
nack_module_.OnReceivedPacket(3, false, false);
EXPECT_EQ(1u, sent_nacks_.size());
EXPECT_EQ(2, sent_nacks_[0]);
+ int backoff_factor = 1;
for (size_t retries = 1; retries < 10; ++retries) {
- clock_->AdvanceTimeMilliseconds(100);
+ // Exponential backoff, so that we don't reject NACK because of time.
+ clock_->AdvanceTimeMilliseconds(backoff_factor * kDefaultRttMs);
+ backoff_factor *= 2;
nack_module_.Process();
EXPECT_EQ(retries + 1, sent_nacks_.size());
}
- clock_->AdvanceTimeMilliseconds(100);
+ clock_->AdvanceTimeMilliseconds(backoff_factor * kDefaultRttMs);
nack_module_.Process();
EXPECT_EQ(10u, sent_nacks_.size());
}
-TEST_F(TestNackModule, TooLargeNackList) {
+TEST_P(TestNackModule, TooLargeNackList) {
nack_module_.OnReceivedPacket(0, false, false);
nack_module_.OnReceivedPacket(1001, false, false);
EXPECT_EQ(1000u, sent_nacks_.size());
@@ -208,7 +242,7 @@
EXPECT_EQ(1, keyframes_requested_);
}
-TEST_F(TestNackModule, TooLargeNackListWithKeyFrame) {
+TEST_P(TestNackModule, TooLargeNackListWithKeyFrame) {
nack_module_.OnReceivedPacket(0, false, false);
nack_module_.OnReceivedPacket(1, true, false);
nack_module_.OnReceivedPacket(1001, false, false);
@@ -222,7 +256,7 @@
EXPECT_EQ(1, keyframes_requested_);
}
-TEST_F(TestNackModule, ClearUpTo) {
+TEST_P(TestNackModule, ClearUpTo) {
nack_module_.OnReceivedPacket(0, false, false);
nack_module_.OnReceivedPacket(100, false, false);
EXPECT_EQ(99u, sent_nacks_.size());
@@ -235,7 +269,7 @@
EXPECT_EQ(50, sent_nacks_[0]);
}
-TEST_F(TestNackModule, ClearUpToWrap) {
+TEST_P(TestNackModule, ClearUpToWrap) {
nack_module_.OnReceivedPacket(0xfff0, false, false);
nack_module_.OnReceivedPacket(0xf, false, false);
EXPECT_EQ(30u, sent_nacks_.size());
@@ -248,7 +282,7 @@
EXPECT_EQ(0, sent_nacks_[0]);
}
-TEST_F(TestNackModule, PacketNackCount) {
+TEST_P(TestNackModule, PacketNackCount) {
EXPECT_EQ(0, nack_module_.OnReceivedPacket(0, false, false));
EXPECT_EQ(0, nack_module_.OnReceivedPacket(2, false, false));
EXPECT_EQ(1, nack_module_.OnReceivedPacket(1, false, false));
@@ -258,14 +292,14 @@
EXPECT_EQ(0, nack_module_.OnReceivedPacket(5, false, false));
clock_->AdvanceTimeMilliseconds(100);
nack_module_.Process();
- clock_->AdvanceTimeMilliseconds(100);
+ clock_->AdvanceTimeMilliseconds(125);
nack_module_.Process();
EXPECT_EQ(3, nack_module_.OnReceivedPacket(3, false, false));
EXPECT_EQ(3, nack_module_.OnReceivedPacket(4, false, false));
EXPECT_EQ(0, nack_module_.OnReceivedPacket(4, false, false));
}
-TEST_F(TestNackModule, NackListFullAndNoOverlapWithKeyframes) {
+TEST_P(TestNackModule, NackListFullAndNoOverlapWithKeyframes) {
const int kMaxNackPackets = 1000;
const unsigned int kFirstGap = kMaxNackPackets - 20;
const unsigned int kSecondGap = 200;
@@ -280,7 +314,7 @@
EXPECT_EQ(kSecondGap, sent_nacks_.size());
}
-TEST_F(TestNackModule, HandleFecRecoveredPacket) {
+TEST_P(TestNackModule, HandleFecRecoveredPacket) {
nack_module_.OnReceivedPacket(1, false, false);
nack_module_.OnReceivedPacket(4, false, true);
EXPECT_EQ(0u, sent_nacks_.size());
@@ -288,12 +322,16 @@
EXPECT_EQ(2u, sent_nacks_.size());
}
-TEST_F(TestNackModule, SendNackWithoutDelay) {
+TEST_P(TestNackModule, SendNackWithoutDelay) {
nack_module_.OnReceivedPacket(0, false, false);
nack_module_.OnReceivedPacket(100, false, false);
EXPECT_EQ(99u, sent_nacks_.size());
}
+INSTANTIATE_TEST_SUITE_P(WithAndWithoutBackoff,
+ TestNackModule,
+ ::testing::Values(true, false));
+
class TestNackModuleWithFieldTrial : public ::testing::Test,
public NackSender,
public KeyFrameRequestSender {