Fork NackModule and RtpVideoStreamReceiver
Bug: webrtc:11595
Change-Id: I4d14c0bf9c32e09d1624099a256f2778afebd4df
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/175901
Commit-Queue: Tommi <tommi@webrtc.org>
Reviewed-by: Mirko Bonadei <mbonadei@webrtc.org>
Cr-Commit-Position: refs/heads/master@{#31337}
diff --git a/modules/video_coding/BUILD.gn b/modules/video_coding/BUILD.gn
index 028b0d5..b084577 100644
--- a/modules/video_coding/BUILD.gn
+++ b/modules/video_coding/BUILD.gn
@@ -74,6 +74,8 @@
"histogram.h",
"nack_module.cc",
"nack_module.h",
+ "nack_module2.cc",
+ "nack_module2.h",
]
deps = [
@@ -876,6 +878,7 @@
"jitter_buffer_unittest.cc",
"jitter_estimator_tests.cc",
"loss_notification_controller_unittest.cc",
+ "nack_module2_unittest.cc",
"nack_module_unittest.cc",
"packet_buffer_unittest.cc",
"receiver_unittest.cc",
diff --git a/modules/video_coding/nack_module2.cc b/modules/video_coding/nack_module2.cc
new file mode 100644
index 0000000..267eaeb
--- /dev/null
+++ b/modules/video_coding/nack_module2.cc
@@ -0,0 +1,349 @@
+/*
+ * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/video_coding/nack_module2.h"
+
+#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"
+
+namespace webrtc {
+
+namespace {
+const int kMaxPacketAge = 10000;
+const int kMaxNackPackets = 1000;
+const int kDefaultRttMs = 100;
+const int kMaxNackRetries = 10;
+const int kProcessFrequency = 50;
+const int kProcessIntervalMs = 1000 / kProcessFrequency;
+const int kMaxReorderedPackets = 128;
+const int kNumReorderingBuckets = 10;
+const int kDefaultSendNackDelayMs = 0;
+
+int64_t GetSendNackDelay() {
+ int64_t delay_ms = strtol(
+ webrtc::field_trial::FindFullName("WebRTC-SendNackDelayMs").c_str(),
+ nullptr, 10);
+ if (delay_ms > 0 && delay_ms <= 20) {
+ RTC_LOG(LS_INFO) << "SendNackDelay is set to " << delay_ms;
+ return delay_ms;
+ }
+ return kDefaultSendNackDelayMs;
+}
+} // namespace
+
+NackModule2::NackInfo::NackInfo()
+ : seq_num(0), send_at_seq_num(0), sent_at_time(-1), retries(0) {}
+
+NackModule2::NackInfo::NackInfo(uint16_t seq_num,
+ uint16_t send_at_seq_num,
+ int64_t created_at_time)
+ : seq_num(seq_num),
+ send_at_seq_num(send_at_seq_num),
+ created_at_time(created_at_time),
+ sent_at_time(-1),
+ retries(0) {}
+
+NackModule2::BackoffSettings::BackoffSettings(TimeDelta min_retry,
+ TimeDelta max_rtt,
+ double base)
+ : min_retry_interval(min_retry), max_rtt(max_rtt), base(base) {}
+
+absl::optional<NackModule2::BackoffSettings>
+NackModule2::BackoffSettings::ParseFromFieldTrials() {
+ // Matches magic number in RTPSender::OnReceivedNack().
+ const TimeDelta kDefaultMinRetryInterval = TimeDelta::Millis(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::Millis(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 NackModule2::BackoffSettings(min_retry.Get(), max_rtt.Get(),
+ base.Get());
+ }
+ return absl::nullopt;
+}
+
+NackModule2::NackModule2(Clock* clock,
+ NackSender* nack_sender,
+ KeyFrameRequestSender* keyframe_request_sender)
+ : clock_(clock),
+ nack_sender_(nack_sender),
+ keyframe_request_sender_(keyframe_request_sender),
+ reordering_histogram_(kNumReorderingBuckets, kMaxReorderedPackets),
+ initialized_(false),
+ rtt_ms_(kDefaultRttMs),
+ newest_seq_num_(0),
+ next_process_time_ms_(-1),
+ send_nack_delay_ms_(GetSendNackDelay()),
+ backoff_settings_(BackoffSettings::ParseFromFieldTrials()) {
+ RTC_DCHECK(clock_);
+ RTC_DCHECK(nack_sender_);
+ RTC_DCHECK(keyframe_request_sender_);
+}
+
+int NackModule2::OnReceivedPacket(uint16_t seq_num, bool is_keyframe) {
+ return OnReceivedPacket(seq_num, is_keyframe, false);
+}
+
+int NackModule2::OnReceivedPacket(uint16_t seq_num,
+ bool is_keyframe,
+ bool is_recovered) {
+ rtc::CritScope lock(&crit_);
+ // TODO(philipel): When the packet includes information whether it is
+ // retransmitted or not, use that value instead. For
+ // now set it to true, which will cause the reordering
+ // statistics to never be updated.
+ bool is_retransmitted = true;
+
+ if (!initialized_) {
+ newest_seq_num_ = seq_num;
+ if (is_keyframe)
+ keyframe_list_.insert(seq_num);
+ initialized_ = true;
+ return 0;
+ }
+
+ // Since the |newest_seq_num_| is a packet we have actually received we know
+ // that packet has never been Nacked.
+ if (seq_num == newest_seq_num_)
+ return 0;
+
+ if (AheadOf(newest_seq_num_, seq_num)) {
+ // An out of order packet has been received.
+ auto nack_list_it = nack_list_.find(seq_num);
+ int nacks_sent_for_packet = 0;
+ if (nack_list_it != nack_list_.end()) {
+ nacks_sent_for_packet = nack_list_it->second.retries;
+ nack_list_.erase(nack_list_it);
+ }
+ if (!is_retransmitted)
+ UpdateReorderingStatistics(seq_num);
+ return nacks_sent_for_packet;
+ }
+
+ // Keep track of new keyframes.
+ if (is_keyframe)
+ keyframe_list_.insert(seq_num);
+
+ // And remove old ones so we don't accumulate keyframes.
+ auto it = keyframe_list_.lower_bound(seq_num - kMaxPacketAge);
+ if (it != keyframe_list_.begin())
+ keyframe_list_.erase(keyframe_list_.begin(), it);
+
+ if (is_recovered) {
+ recovered_list_.insert(seq_num);
+
+ // Remove old ones so we don't accumulate recovered packets.
+ auto it = recovered_list_.lower_bound(seq_num - kMaxPacketAge);
+ if (it != recovered_list_.begin())
+ recovered_list_.erase(recovered_list_.begin(), it);
+
+ // Do not send nack for packets recovered by FEC or RTX.
+ return 0;
+ }
+
+ AddPacketsToNack(newest_seq_num_ + 1, seq_num);
+ newest_seq_num_ = seq_num;
+
+ // Are there any nacks that are waiting for this seq_num.
+ std::vector<uint16_t> nack_batch = GetNackBatch(kSeqNumOnly);
+ if (!nack_batch.empty()) {
+ // This batch of NACKs is triggered externally; the initiator can
+ // batch them with other feedback messages.
+ nack_sender_->SendNack(nack_batch, /*buffering_allowed=*/true);
+ }
+
+ return 0;
+}
+
+void NackModule2::ClearUpTo(uint16_t seq_num) {
+ rtc::CritScope lock(&crit_);
+ nack_list_.erase(nack_list_.begin(), nack_list_.lower_bound(seq_num));
+ keyframe_list_.erase(keyframe_list_.begin(),
+ keyframe_list_.lower_bound(seq_num));
+ recovered_list_.erase(recovered_list_.begin(),
+ recovered_list_.lower_bound(seq_num));
+}
+
+void NackModule2::UpdateRtt(int64_t rtt_ms) {
+ rtc::CritScope lock(&crit_);
+ rtt_ms_ = rtt_ms;
+}
+
+void NackModule2::Clear() {
+ rtc::CritScope lock(&crit_);
+ nack_list_.clear();
+ keyframe_list_.clear();
+ recovered_list_.clear();
+}
+
+int64_t NackModule2::TimeUntilNextProcess() {
+ return std::max<int64_t>(next_process_time_ms_ - clock_->TimeInMilliseconds(),
+ 0);
+}
+
+void NackModule2::Process() {
+ if (nack_sender_) {
+ std::vector<uint16_t> nack_batch;
+ {
+ rtc::CritScope lock(&crit_);
+ nack_batch = GetNackBatch(kTimeOnly);
+ }
+
+ if (!nack_batch.empty()) {
+ // This batch of NACKs is triggered externally; there is no external
+ // initiator who can batch them with other feedback messages.
+ nack_sender_->SendNack(nack_batch, /*buffering_allowed=*/false);
+ }
+ }
+
+ // Update the next_process_time_ms_ in intervals to achieve
+ // the targeted frequency over time. Also add multiple intervals
+ // in case of a skip in time as to not make uneccessary
+ // calls to Process in order to catch up.
+ int64_t now_ms = clock_->TimeInMilliseconds();
+ if (next_process_time_ms_ == -1) {
+ next_process_time_ms_ = now_ms + kProcessIntervalMs;
+ } else {
+ next_process_time_ms_ = next_process_time_ms_ + kProcessIntervalMs +
+ (now_ms - next_process_time_ms_) /
+ kProcessIntervalMs * kProcessIntervalMs;
+ }
+}
+
+bool NackModule2::RemovePacketsUntilKeyFrame() {
+ while (!keyframe_list_.empty()) {
+ auto it = nack_list_.lower_bound(*keyframe_list_.begin());
+
+ if (it != nack_list_.begin()) {
+ // We have found a keyframe that actually is newer than at least one
+ // packet in the nack list.
+ nack_list_.erase(nack_list_.begin(), it);
+ return true;
+ }
+
+ // If this keyframe is so old it does not remove any packets from the list,
+ // remove it from the list of keyframes and try the next keyframe.
+ keyframe_list_.erase(keyframe_list_.begin());
+ }
+ return false;
+}
+
+void NackModule2::AddPacketsToNack(uint16_t seq_num_start,
+ uint16_t seq_num_end) {
+ // Remove old packets.
+ auto it = nack_list_.lower_bound(seq_num_end - kMaxPacketAge);
+ nack_list_.erase(nack_list_.begin(), it);
+
+ // If the nack list is too large, remove packets from the nack list until
+ // the latest first packet of a keyframe. If the list is still too large,
+ // clear it and request a keyframe.
+ uint16_t num_new_nacks = ForwardDiff(seq_num_start, seq_num_end);
+ if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
+ while (RemovePacketsUntilKeyFrame() &&
+ nack_list_.size() + num_new_nacks > kMaxNackPackets) {
+ }
+
+ if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
+ nack_list_.clear();
+ RTC_LOG(LS_WARNING) << "NACK list full, clearing NACK"
+ " list and requesting keyframe.";
+ keyframe_request_sender_->RequestKeyFrame();
+ return;
+ }
+ }
+
+ for (uint16_t seq_num = seq_num_start; seq_num != seq_num_end; ++seq_num) {
+ // Do not send nack for packets that are already recovered by FEC or RTX
+ if (recovered_list_.find(seq_num) != recovered_list_.end())
+ continue;
+ NackInfo nack_info(seq_num, seq_num + WaitNumberOfPackets(0.5),
+ clock_->TimeInMilliseconds());
+ RTC_DCHECK(nack_list_.find(seq_num) == nack_list_.end());
+ nack_list_[seq_num] = nack_info;
+ }
+}
+
+std::vector<uint16_t> NackModule2::GetNackBatch(NackFilterOptions options) {
+ bool consider_seq_num = options != kTimeOnly;
+ bool consider_timestamp = options != kSeqNumOnly;
+ Timestamp now = clock_->CurrentTime();
+ std::vector<uint16_t> nack_batch;
+ auto it = nack_list_.begin();
+ while (it != nack_list_.end()) {
+ TimeDelta resend_delay = TimeDelta::Millis(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::Millis(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 >= 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);
+ if (delay_timed_out && ((consider_seq_num && nack_on_seq_num_passed) ||
+ (consider_timestamp && nack_on_rtt_passed))) {
+ nack_batch.emplace_back(it->second.seq_num);
+ ++it->second.retries;
+ 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.";
+ it = nack_list_.erase(it);
+ } else {
+ ++it;
+ }
+ continue;
+ }
+ ++it;
+ }
+ return nack_batch;
+}
+
+void NackModule2::UpdateReorderingStatistics(uint16_t seq_num) {
+ RTC_DCHECK(AheadOf(newest_seq_num_, seq_num));
+ uint16_t diff = ReverseDiff(newest_seq_num_, seq_num);
+ reordering_histogram_.Add(diff);
+}
+
+int NackModule2::WaitNumberOfPackets(float probability) const {
+ if (reordering_histogram_.NumValues() == 0)
+ return 0;
+ return reordering_histogram_.InverseCdf(probability);
+}
+
+} // namespace webrtc
diff --git a/modules/video_coding/nack_module2.h b/modules/video_coding/nack_module2.h
new file mode 100644
index 0000000..6518f32
--- /dev/null
+++ b/modules/video_coding/nack_module2.h
@@ -0,0 +1,129 @@
+/*
+ * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef MODULES_VIDEO_CODING_NACK_MODULE2_H_
+#define MODULES_VIDEO_CODING_NACK_MODULE2_H_
+
+#include <stdint.h>
+
+#include <map>
+#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"
+#include "rtc_base/critical_section.h"
+#include "rtc_base/numerics/sequence_number_util.h"
+#include "rtc_base/thread_annotations.h"
+#include "system_wrappers/include/clock.h"
+
+namespace webrtc {
+
+class NackModule2 final : public Module {
+ public:
+ NackModule2(Clock* clock,
+ NackSender* nack_sender,
+ KeyFrameRequestSender* keyframe_request_sender);
+
+ int OnReceivedPacket(uint16_t seq_num, bool is_keyframe);
+ int OnReceivedPacket(uint16_t seq_num, bool is_keyframe, bool is_recovered);
+
+ void ClearUpTo(uint16_t seq_num);
+ void UpdateRtt(int64_t rtt_ms);
+ void Clear();
+
+ // Module implementation
+ int64_t TimeUntilNextProcess() override;
+ void Process() override;
+
+ private:
+ // Which fields to consider when deciding which packet to nack in
+ // GetNackBatch.
+ enum NackFilterOptions { kSeqNumOnly, kTimeOnly, kSeqNumAndTime };
+
+ // This class holds the sequence number of the packet that is in the nack list
+ // as well as the meta data about when it should be nacked and how many times
+ // we have tried to nack this packet.
+ struct NackInfo {
+ NackInfo();
+ NackInfo(uint16_t seq_num,
+ uint16_t send_at_seq_num,
+ int64_t created_at_time);
+
+ uint16_t seq_num;
+ uint16_t send_at_seq_num;
+ int64_t created_at_time;
+ 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_);
+
+ // Removes packets from the nack list until the next keyframe. Returns true
+ // if packets were removed.
+ bool RemovePacketsUntilKeyFrame() RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
+ std::vector<uint16_t> GetNackBatch(NackFilterOptions options)
+ RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
+
+ // Update the reordering distribution.
+ void UpdateReorderingStatistics(uint16_t seq_num)
+ RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
+
+ // Returns how many packets we have to wait in order to receive the packet
+ // with probability |probabilty| or higher.
+ int WaitNumberOfPackets(float probability) const
+ RTC_EXCLUSIVE_LOCKS_REQUIRED(crit_);
+
+ rtc::CriticalSection crit_;
+ Clock* const clock_;
+ NackSender* const nack_sender_;
+ KeyFrameRequestSender* const keyframe_request_sender_;
+
+ // TODO(philipel): Some of the variables below are consistently used on a
+ // known thread (e.g. see |initialized_|). Those probably do not need
+ // synchronized access.
+ std::map<uint16_t, NackInfo, DescendingSeqNumComp<uint16_t>> nack_list_
+ RTC_GUARDED_BY(crit_);
+ std::set<uint16_t, DescendingSeqNumComp<uint16_t>> keyframe_list_
+ RTC_GUARDED_BY(crit_);
+ std::set<uint16_t, DescendingSeqNumComp<uint16_t>> recovered_list_
+ RTC_GUARDED_BY(crit_);
+ video_coding::Histogram reordering_histogram_ RTC_GUARDED_BY(crit_);
+ bool initialized_ RTC_GUARDED_BY(crit_);
+ int64_t rtt_ms_ RTC_GUARDED_BY(crit_);
+ uint16_t newest_seq_num_ RTC_GUARDED_BY(crit_);
+
+ // Only touched on the process thread.
+ int64_t next_process_time_ms_;
+
+ // Adds a delay before send nack on packet received.
+ const int64_t send_nack_delay_ms_;
+
+ const absl::optional<BackoffSettings> backoff_settings_;
+};
+
+} // namespace webrtc
+
+#endif // MODULES_VIDEO_CODING_NACK_MODULE2_H_
diff --git a/modules/video_coding/nack_module2_unittest.cc b/modules/video_coding/nack_module2_unittest.cc
new file mode 100644
index 0000000..ebc28ec
--- /dev/null
+++ b/modules/video_coding/nack_module2_unittest.cc
@@ -0,0 +1,371 @@
+/*
+ * Copyright (c) 2016 The WebRTC project authors. All Rights Reserved.
+ *
+ * Use of this source code is governed by a BSD-style license
+ * that can be found in the LICENSE file in the root of the source
+ * tree. An additional intellectual property rights grant can be found
+ * in the file PATENTS. All contributing project authors may
+ * be found in the AUTHORS file in the root of the source tree.
+ */
+
+#include "modules/video_coding/nack_module2.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <cstring>
+#include <memory>
+
+#include "system_wrappers/include/clock.h"
+#include "test/field_trial.h"
+#include "test/gtest.h"
+
+namespace webrtc {
+class TestNackModule2 : public ::testing::TestWithParam<bool>,
+ public NackSender,
+ public KeyFrameRequestSender {
+ protected:
+ TestNackModule2()
+ : 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(),
+ sequence_numbers.end());
+ }
+
+ void RequestKeyFrame() override { ++keyframes_requested_; }
+
+ static constexpr int64_t kDefaultRttMs = 20;
+ std::unique_ptr<SimulatedClock> clock_;
+ test::ScopedFieldTrials field_trial_;
+ NackModule2 nack_module_;
+ std::vector<uint16_t> sent_nacks_;
+ int keyframes_requested_;
+};
+
+TEST_P(TestNackModule2, 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_P(TestNackModule2, WrappingSeqNum) {
+ nack_module_.OnReceivedPacket(0xfffe, false, false);
+ nack_module_.OnReceivedPacket(1, false, false);
+ EXPECT_EQ(2u, sent_nacks_.size());
+ EXPECT_EQ(0xffff, sent_nacks_[0]);
+ EXPECT_EQ(0, sent_nacks_[1]);
+}
+
+TEST_P(TestNackModule2, WrappingSeqNumClearToKeyframe) {
+ nack_module_.OnReceivedPacket(0xfffe, false, false);
+ nack_module_.OnReceivedPacket(1, false, false);
+ EXPECT_EQ(2u, sent_nacks_.size());
+ EXPECT_EQ(0xffff, sent_nacks_[0]);
+ EXPECT_EQ(0, sent_nacks_[1]);
+
+ sent_nacks_.clear();
+ nack_module_.OnReceivedPacket(2, true, false);
+ EXPECT_EQ(0u, sent_nacks_.size());
+
+ nack_module_.OnReceivedPacket(501, true, false);
+ EXPECT_EQ(498u, sent_nacks_.size());
+ for (int seq_num = 3; seq_num < 501; ++seq_num)
+ EXPECT_EQ(seq_num, sent_nacks_[seq_num - 3]);
+
+ sent_nacks_.clear();
+ nack_module_.OnReceivedPacket(1001, false, false);
+ EXPECT_EQ(499u, sent_nacks_.size());
+ for (int seq_num = 502; seq_num < 1001; ++seq_num)
+ EXPECT_EQ(seq_num, sent_nacks_[seq_num - 502]);
+
+ sent_nacks_.clear();
+ clock_->AdvanceTimeMilliseconds(100);
+ nack_module_.Process();
+ EXPECT_EQ(999u, sent_nacks_.size());
+ EXPECT_EQ(0xffff, sent_nacks_[0]);
+ EXPECT_EQ(0, sent_nacks_[1]);
+ for (int seq_num = 3; seq_num < 501; ++seq_num)
+ EXPECT_EQ(seq_num, sent_nacks_[seq_num - 1]);
+ for (int seq_num = 502; seq_num < 1001; ++seq_num)
+ EXPECT_EQ(seq_num, sent_nacks_[seq_num - 2]);
+
+ // Adding packet 1004 will cause the nack list to reach it's max limit.
+ // It will then clear all nacks up to the next keyframe (seq num 2),
+ // thus removing 0xffff and 0 from the nack list.
+ sent_nacks_.clear();
+ nack_module_.OnReceivedPacket(1004, false, false);
+ EXPECT_EQ(2u, sent_nacks_.size());
+ EXPECT_EQ(1002, sent_nacks_[0]);
+ EXPECT_EQ(1003, sent_nacks_[1]);
+
+ sent_nacks_.clear();
+ clock_->AdvanceTimeMilliseconds(100);
+ nack_module_.Process();
+ EXPECT_EQ(999u, sent_nacks_.size());
+ for (int seq_num = 3; seq_num < 501; ++seq_num)
+ EXPECT_EQ(seq_num, sent_nacks_[seq_num - 3]);
+ for (int seq_num = 502; seq_num < 1001; ++seq_num)
+ EXPECT_EQ(seq_num, sent_nacks_[seq_num - 4]);
+
+ // Adding packet 1007 will cause the nack module to overflow again, thus
+ // clearing everything up to 501 which is the next keyframe.
+ nack_module_.OnReceivedPacket(1007, false, false);
+ sent_nacks_.clear();
+ clock_->AdvanceTimeMilliseconds(100);
+ nack_module_.Process();
+ EXPECT_EQ(503u, sent_nacks_.size());
+ for (int seq_num = 502; seq_num < 1001; ++seq_num)
+ EXPECT_EQ(seq_num, sent_nacks_[seq_num - 502]);
+ EXPECT_EQ(1005, sent_nacks_[501]);
+ EXPECT_EQ(1006, sent_nacks_[502]);
+}
+
+TEST_P(TestNackModule2, DontBurstOnTimeSkip) {
+ nack_module_.Process();
+ clock_->AdvanceTimeMilliseconds(20);
+ EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
+ nack_module_.Process();
+
+ clock_->AdvanceTimeMilliseconds(100);
+ EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
+ nack_module_.Process();
+ EXPECT_EQ(20, nack_module_.TimeUntilNextProcess());
+
+ clock_->AdvanceTimeMilliseconds(19);
+ EXPECT_EQ(1, nack_module_.TimeUntilNextProcess());
+ clock_->AdvanceTimeMilliseconds(2);
+ nack_module_.Process();
+ EXPECT_EQ(19, nack_module_.TimeUntilNextProcess());
+
+ clock_->AdvanceTimeMilliseconds(19);
+ EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
+ nack_module_.Process();
+
+ clock_->AdvanceTimeMilliseconds(21);
+ EXPECT_EQ(0, nack_module_.TimeUntilNextProcess());
+ nack_module_.Process();
+ EXPECT_EQ(19, nack_module_.TimeUntilNextProcess());
+}
+
+TEST_P(TestNackModule2, ResendNack) {
+ nack_module_.OnReceivedPacket(1, false, false);
+ nack_module_.OnReceivedPacket(3, false, false);
+ size_t expected_nacks_sent = 1;
+ EXPECT_EQ(expected_nacks_sent, sent_nacks_.size());
+ EXPECT_EQ(2, sent_nacks_[0]);
+
+ 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(); // 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());
+ }
+
+ // 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::Millis(160); // + (i * 10 - 40)
+ nack_module_.UpdateRtt(rtt.ms());
+
+ // RTT gets capped at 160ms in backoff calculations.
+ TimeDelta expected_backoff_delay =
+ std::pow(b, i - 1) * std::min(rtt, TimeDelta::Millis(160));
+
+ // 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(expected_nacks_sent, sent_nacks_.size());
+}
+
+TEST_P(TestNackModule2, 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) {
+ // 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(backoff_factor * kDefaultRttMs);
+ nack_module_.Process();
+ EXPECT_EQ(10u, sent_nacks_.size());
+}
+
+TEST_P(TestNackModule2, TooLargeNackList) {
+ nack_module_.OnReceivedPacket(0, false, false);
+ nack_module_.OnReceivedPacket(1001, false, false);
+ EXPECT_EQ(1000u, sent_nacks_.size());
+ EXPECT_EQ(0, keyframes_requested_);
+ nack_module_.OnReceivedPacket(1003, false, false);
+ EXPECT_EQ(1000u, sent_nacks_.size());
+ EXPECT_EQ(1, keyframes_requested_);
+ nack_module_.OnReceivedPacket(1004, false, false);
+ EXPECT_EQ(1000u, sent_nacks_.size());
+ EXPECT_EQ(1, keyframes_requested_);
+}
+
+TEST_P(TestNackModule2, TooLargeNackListWithKeyFrame) {
+ nack_module_.OnReceivedPacket(0, false, false);
+ nack_module_.OnReceivedPacket(1, true, false);
+ nack_module_.OnReceivedPacket(1001, false, false);
+ EXPECT_EQ(999u, sent_nacks_.size());
+ EXPECT_EQ(0, keyframes_requested_);
+ nack_module_.OnReceivedPacket(1003, false, false);
+ EXPECT_EQ(1000u, sent_nacks_.size());
+ EXPECT_EQ(0, keyframes_requested_);
+ nack_module_.OnReceivedPacket(1005, false, false);
+ EXPECT_EQ(1000u, sent_nacks_.size());
+ EXPECT_EQ(1, keyframes_requested_);
+}
+
+TEST_P(TestNackModule2, ClearUpTo) {
+ nack_module_.OnReceivedPacket(0, false, false);
+ nack_module_.OnReceivedPacket(100, false, false);
+ EXPECT_EQ(99u, sent_nacks_.size());
+
+ sent_nacks_.clear();
+ clock_->AdvanceTimeMilliseconds(100);
+ nack_module_.ClearUpTo(50);
+ nack_module_.Process();
+ EXPECT_EQ(50u, sent_nacks_.size());
+ EXPECT_EQ(50, sent_nacks_[0]);
+}
+
+TEST_P(TestNackModule2, ClearUpToWrap) {
+ nack_module_.OnReceivedPacket(0xfff0, false, false);
+ nack_module_.OnReceivedPacket(0xf, false, false);
+ EXPECT_EQ(30u, sent_nacks_.size());
+
+ sent_nacks_.clear();
+ clock_->AdvanceTimeMilliseconds(100);
+ nack_module_.ClearUpTo(0);
+ nack_module_.Process();
+ EXPECT_EQ(15u, sent_nacks_.size());
+ EXPECT_EQ(0, sent_nacks_[0]);
+}
+
+TEST_P(TestNackModule2, 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));
+
+ sent_nacks_.clear();
+ nack_module_.UpdateRtt(100);
+ EXPECT_EQ(0, nack_module_.OnReceivedPacket(5, false, false));
+ clock_->AdvanceTimeMilliseconds(100);
+ nack_module_.Process();
+ 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_P(TestNackModule2, NackListFullAndNoOverlapWithKeyframes) {
+ const int kMaxNackPackets = 1000;
+ const unsigned int kFirstGap = kMaxNackPackets - 20;
+ const unsigned int kSecondGap = 200;
+ uint16_t seq_num = 0;
+ nack_module_.OnReceivedPacket(seq_num++, true, false);
+ seq_num += kFirstGap;
+ nack_module_.OnReceivedPacket(seq_num++, true, false);
+ EXPECT_EQ(kFirstGap, sent_nacks_.size());
+ sent_nacks_.clear();
+ seq_num += kSecondGap;
+ nack_module_.OnReceivedPacket(seq_num, true, false);
+ EXPECT_EQ(kSecondGap, sent_nacks_.size());
+}
+
+TEST_P(TestNackModule2, HandleFecRecoveredPacket) {
+ nack_module_.OnReceivedPacket(1, false, false);
+ nack_module_.OnReceivedPacket(4, false, true);
+ EXPECT_EQ(0u, sent_nacks_.size());
+ nack_module_.OnReceivedPacket(5, false, false);
+ EXPECT_EQ(2u, sent_nacks_.size());
+}
+
+TEST_P(TestNackModule2, SendNackWithoutDelay) {
+ nack_module_.OnReceivedPacket(0, false, false);
+ nack_module_.OnReceivedPacket(100, false, false);
+ EXPECT_EQ(99u, sent_nacks_.size());
+}
+
+INSTANTIATE_TEST_SUITE_P(WithAndWithoutBackoff,
+ TestNackModule2,
+ ::testing::Values(true, false));
+
+class TestNackModule2WithFieldTrial : public ::testing::Test,
+ public NackSender,
+ public KeyFrameRequestSender {
+ protected:
+ TestNackModule2WithFieldTrial()
+ : nack_delay_field_trial_("WebRTC-SendNackDelayMs/10/"),
+ clock_(new SimulatedClock(0)),
+ nack_module_(clock_.get(), this, this),
+ keyframes_requested_(0) {}
+
+ void SendNack(const std::vector<uint16_t>& sequence_numbers,
+ bool buffering_allowed) override {
+ sent_nacks_.insert(sent_nacks_.end(), sequence_numbers.begin(),
+ sequence_numbers.end());
+ }
+
+ void RequestKeyFrame() override { ++keyframes_requested_; }
+
+ test::ScopedFieldTrials nack_delay_field_trial_;
+ std::unique_ptr<SimulatedClock> clock_;
+ NackModule2 nack_module_;
+ std::vector<uint16_t> sent_nacks_;
+ int keyframes_requested_;
+};
+
+TEST_F(TestNackModule2WithFieldTrial, SendNackWithDelay) {
+ nack_module_.OnReceivedPacket(0, false, false);
+ nack_module_.OnReceivedPacket(100, false, false);
+ EXPECT_EQ(0u, sent_nacks_.size());
+ clock_->AdvanceTimeMilliseconds(10);
+ nack_module_.OnReceivedPacket(106, false, false);
+ EXPECT_EQ(99u, sent_nacks_.size());
+ clock_->AdvanceTimeMilliseconds(10);
+ nack_module_.OnReceivedPacket(109, false, false);
+ EXPECT_EQ(104u, sent_nacks_.size());
+}
+} // namespace webrtc