Improve adaptation to reordered packets in delay manager.
This is done by adding a reorder optimizer that estimates the probability of receiving reordered packets.
The optimal delay is decided by balancing the cost of increasing the delay against the probability of missing a reordered packet, resulting in a loss. This balance is decided using the `ms_per_loss_percent` parameter.
The usage and parameters can be controlled via field trial.
Bug: webrtc:10178
Change-Id: Ic484df0412af35610e74b3a6070f2bac7a926a63
Reviewed-on: https://webrtc-review.googlesource.com/c/src/+/231541
Reviewed-by: Ivo Creusen <ivoc@webrtc.org>
Commit-Queue: Jakob Ivarsson <jakobi@webrtc.org>
Cr-Commit-Position: refs/heads/main@{#34954}
diff --git a/modules/audio_coding/BUILD.gn b/modules/audio_coding/BUILD.gn
index d5fb1a4..e67a05d 100644
--- a/modules/audio_coding/BUILD.gn
+++ b/modules/audio_coding/BUILD.gn
@@ -976,6 +976,8 @@
"neteq/red_payload_splitter.h",
"neteq/relative_arrival_delay_tracker.cc",
"neteq/relative_arrival_delay_tracker.h",
+ "neteq/reorder_optimizer.cc",
+ "neteq/reorder_optimizer.h",
"neteq/statistics_calculator.cc",
"neteq/statistics_calculator.h",
"neteq/sync_buffer.cc",
@@ -2016,6 +2018,7 @@
"neteq/random_vector_unittest.cc",
"neteq/red_payload_splitter_unittest.cc",
"neteq/relative_arrival_delay_tracker_unittest.cc",
+ "neteq/reorder_optimizer_unittest.cc",
"neteq/statistics_calculator_unittest.cc",
"neteq/sync_buffer_unittest.cc",
"neteq/time_stretch_unittest.cc",
diff --git a/modules/audio_coding/neteq/delay_manager.cc b/modules/audio_coding/neteq/delay_manager.cc
index 9f7eebd..97d1d2e 100644
--- a/modules/audio_coding/neteq/delay_manager.cc
+++ b/modules/audio_coding/neteq/delay_manager.cc
@@ -32,6 +32,16 @@
constexpr int kMaxBaseMinimumDelayMs = 10000;
constexpr int kStartDelayMs = 80;
+std::unique_ptr<ReorderOptimizer> MaybeCreateReorderOptimizer(
+ const DelayManager::Config& config) {
+ if (!config.use_reorder_optimizer) {
+ return nullptr;
+ }
+ return std::make_unique<ReorderOptimizer>(
+ (1 << 15) * config.reorder_forget_factor, config.ms_per_loss_percent,
+ config.start_forget_weight);
+}
+
} // namespace
DelayManager::Config::Config() {
@@ -47,16 +57,22 @@
<< " start_forget_weight=" << start_forget_weight.value_or(0)
<< " resample_interval_ms="
<< resample_interval_ms.value_or(0)
- << " max_history_ms=" << max_history_ms;
+ << " max_history_ms=" << max_history_ms
+ << " use_reorder_optimizer=" << use_reorder_optimizer
+ << " reorder_forget_factor=" << reorder_forget_factor
+ << " ms_per_loss_percent=" << ms_per_loss_percent;
}
std::unique_ptr<StructParametersParser> DelayManager::Config::Parser() {
- return StructParametersParser::Create( //
- "quantile", &quantile, //
- "forget_factor", &forget_factor, //
- "start_forget_weight", &start_forget_weight, //
- "resample_interval_ms", &resample_interval_ms, //
- "max_history_ms", &max_history_ms);
+ return StructParametersParser::Create( //
+ "quantile", &quantile, //
+ "forget_factor", &forget_factor, //
+ "start_forget_weight", &start_forget_weight, //
+ "resample_interval_ms", &resample_interval_ms, //
+ "max_history_ms", &max_history_ms, //
+ "use_reorder_optimizer", &use_reorder_optimizer, //
+ "reorder_forget_factor", &reorder_forget_factor, //
+ "ms_per_loss_percent", &ms_per_loss_percent);
}
// TODO(jakobi): remove legacy field trial.
@@ -90,6 +106,7 @@
(1 << 15) * config.forget_factor,
config.start_forget_weight,
config.resample_interval_ms),
+ reorder_optimizer_(MaybeCreateReorderOptimizer(config)),
relative_arrival_delay_tracker_(tick_timer, config.max_history_ms),
base_minimum_delay_ms_(config.base_minimum_delay_ms),
effective_minimum_delay_ms_(config.base_minimum_delay_ms),
@@ -115,9 +132,18 @@
return absl::nullopt;
}
- underrun_optimizer_.Update(*relative_delay);
+ bool reordered =
+ relative_arrival_delay_tracker_.newest_timestamp() != timestamp;
+ if (!reorder_optimizer_ || !reordered) {
+ underrun_optimizer_.Update(*relative_delay);
+ }
target_level_ms_ =
underrun_optimizer_.GetOptimalDelayMs().value_or(kStartDelayMs);
+ if (reorder_optimizer_) {
+ reorder_optimizer_->Update(*relative_delay, reordered, target_level_ms_);
+ target_level_ms_ = std::max(
+ target_level_ms_, reorder_optimizer_->GetOptimalDelayMs().value_or(0));
+ }
target_level_ms_ = std::max(target_level_ms_, effective_minimum_delay_ms_);
if (maximum_delay_ms_ > 0) {
target_level_ms_ = std::min(target_level_ms_, maximum_delay_ms_);
@@ -148,6 +174,9 @@
underrun_optimizer_.Reset();
relative_arrival_delay_tracker_.Reset();
target_level_ms_ = kStartDelayMs;
+ if (reorder_optimizer_) {
+ reorder_optimizer_->Reset();
+ }
}
int DelayManager::TargetDelayMs() const {
diff --git a/modules/audio_coding/neteq/delay_manager.h b/modules/audio_coding/neteq/delay_manager.h
index c751836..277b80d 100644
--- a/modules/audio_coding/neteq/delay_manager.h
+++ b/modules/audio_coding/neteq/delay_manager.h
@@ -20,6 +20,7 @@
#include "api/neteq/tick_timer.h"
#include "modules/audio_coding/neteq/histogram.h"
#include "modules/audio_coding/neteq/relative_arrival_delay_tracker.h"
+#include "modules/audio_coding/neteq/reorder_optimizer.h"
#include "modules/audio_coding/neteq/underrun_optimizer.h"
#include "rtc_base/constructor_magic.h"
#include "rtc_base/experiments/struct_parameters_parser.h"
@@ -39,6 +40,10 @@
absl::optional<int> resample_interval_ms;
int max_history_ms = 2000;
+ bool use_reorder_optimizer = true;
+ double reorder_forget_factor = 0.9993;
+ int ms_per_loss_percent = 20;
+
// Options that are externally populated.
int max_packets_in_buffer = 200;
int base_minimum_delay_ms = 0;
@@ -104,6 +109,7 @@
// TODO(jakobi): set maximum buffer delay instead of number of packets.
const int max_packets_in_buffer_;
UnderrunOptimizer underrun_optimizer_;
+ std::unique_ptr<ReorderOptimizer> reorder_optimizer_;
RelativeArrivalDelayTracker relative_arrival_delay_tracker_;
int base_minimum_delay_ms_;
diff --git a/modules/audio_coding/neteq/histogram.h b/modules/audio_coding/neteq/histogram.h
index 5b2f2b1..265a10e 100644
--- a/modules/audio_coding/neteq/histogram.h
+++ b/modules/audio_coding/neteq/histogram.h
@@ -42,7 +42,7 @@
virtual int NumBuckets() const;
// Returns the probability for each bucket in Q30.
- std::vector<int> buckets() const { return buckets_; }
+ const std::vector<int>& buckets() const { return buckets_; }
// Accessors only intended for testing purposes.
int base_forget_factor_for_testing() const { return base_forget_factor_; }
diff --git a/modules/audio_coding/neteq/relative_arrival_delay_tracker.cc b/modules/audio_coding/neteq/relative_arrival_delay_tracker.cc
index 5b9580c..02c5a43 100644
--- a/modules/audio_coding/neteq/relative_arrival_delay_tracker.cc
+++ b/modules/audio_coding/neteq/relative_arrival_delay_tracker.cc
@@ -12,6 +12,8 @@
#include <algorithm>
+#include "modules/include/module_common_types_public.h"
+
namespace webrtc {
absl::optional<int> RelativeArrivalDelayTracker::Update(uint32_t timestamp,
@@ -23,6 +25,7 @@
// Restart relative delay esimation from this packet.
delay_history_.clear();
packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
+ newest_timestamp_ = timestamp;
last_timestamp_ = timestamp;
return absl::nullopt;
}
@@ -37,6 +40,9 @@
packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
last_timestamp_ = timestamp;
+ if (IsNewerTimestamp(timestamp, *newest_timestamp_)) {
+ newest_timestamp_ = timestamp;
+ }
return relative_delay;
}
@@ -44,6 +50,7 @@
void RelativeArrivalDelayTracker::Reset() {
delay_history_.clear();
packet_iat_stopwatch_ = tick_timer_->GetNewStopwatch();
+ newest_timestamp_ = absl::nullopt;
last_timestamp_ = absl::nullopt;
}
diff --git a/modules/audio_coding/neteq/relative_arrival_delay_tracker.h b/modules/audio_coding/neteq/relative_arrival_delay_tracker.h
index da7f121..fed56be 100644
--- a/modules/audio_coding/neteq/relative_arrival_delay_tracker.h
+++ b/modules/audio_coding/neteq/relative_arrival_delay_tracker.h
@@ -28,6 +28,10 @@
void Reset();
+ absl::optional<uint32_t> newest_timestamp() const {
+ return newest_timestamp_;
+ }
+
private:
// Updates `delay_history_`.
void UpdateDelayHistory(int iat_delay_ms,
@@ -46,8 +50,8 @@
};
std::deque<PacketDelay> delay_history_;
- absl::optional<uint32_t>
- last_timestamp_; // Timestamp for the last received packet.
+ absl::optional<uint32_t> newest_timestamp_;
+ absl::optional<uint32_t> last_timestamp_;
std::unique_ptr<TickTimer::Stopwatch>
packet_iat_stopwatch_; // Time elapsed since last packet.
diff --git a/modules/audio_coding/neteq/relative_arrival_delay_tracker_unittest.cc b/modules/audio_coding/neteq/relative_arrival_delay_tracker_unittest.cc
index f764b85..b4e9456 100644
--- a/modules/audio_coding/neteq/relative_arrival_delay_tracker_unittest.cc
+++ b/modules/audio_coding/neteq/relative_arrival_delay_tracker_unittest.cc
@@ -49,14 +49,17 @@
// Insert reordered packet.
EXPECT_EQ(tracker.Update(kTs - 4 * kTsIncrement, kFs), 80);
+ EXPECT_EQ(tracker.newest_timestamp(), kTs);
// Insert another reordered packet.
EXPECT_EQ(tracker.Update(kTs - kTsIncrement, kFs), 20);
+ EXPECT_EQ(tracker.newest_timestamp(), kTs);
// Insert the next packet in order and verify that the relative delay is
// estimated based on the first inserted packet.
tick_timer.Increment(4 * kFrameSizeMs / tick_timer.ms_per_tick());
EXPECT_EQ(tracker.Update(kTs + kTsIncrement, kFs), 60);
+ EXPECT_EQ(tracker.newest_timestamp(), kTs + kTsIncrement);
}
TEST(RelativeArrivalDelayTrackerTest, MaxDelayHistory) {
diff --git a/modules/audio_coding/neteq/reorder_optimizer.cc b/modules/audio_coding/neteq/reorder_optimizer.cc
new file mode 100644
index 0000000..f6e073f
--- /dev/null
+++ b/modules/audio_coding/neteq/reorder_optimizer.cc
@@ -0,0 +1,75 @@
+/*
+ * Copyright (c) 2021 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/audio_coding/neteq/reorder_optimizer.h"
+
+#include <algorithm>
+#include <limits>
+#include <vector>
+
+namespace webrtc {
+
+namespace {
+
+constexpr int kDelayBuckets = 100;
+constexpr int kBucketSizeMs = 20;
+
+} // namespace
+
+ReorderOptimizer::ReorderOptimizer(int forget_factor,
+ int ms_per_loss_percent,
+ absl::optional<int> start_forget_weight)
+ : histogram_(kDelayBuckets, forget_factor, start_forget_weight),
+ ms_per_loss_percent_(ms_per_loss_percent) {}
+
+void ReorderOptimizer::Update(int relative_delay_ms,
+ bool reordered,
+ int base_delay_ms) {
+ const int index = reordered ? relative_delay_ms / kBucketSizeMs : 0;
+ if (index < histogram_.NumBuckets()) {
+ // Maximum delay to register is 2000 ms.
+ histogram_.Add(index);
+ }
+ int bucket_index = MinimizeCostFunction(base_delay_ms);
+ optimal_delay_ms_ = (1 + bucket_index) * kBucketSizeMs;
+}
+
+void ReorderOptimizer::Reset() {
+ histogram_.Reset();
+ optimal_delay_ms_.reset();
+}
+
+int ReorderOptimizer::MinimizeCostFunction(int base_delay_ms) const {
+ const std::vector<int>& buckets = histogram_.buckets();
+
+ // Values are calculated in Q30.
+ int64_t loss_probability = 1 << 30;
+ int64_t min_cost = std::numeric_limits<int64_t>::max();
+ int min_bucket = 0;
+ for (int i = 0; i < static_cast<int>(buckets.size()); ++i) {
+ loss_probability -= buckets[i];
+ int64_t delay_ms =
+ static_cast<int64_t>(std::max(0, i * kBucketSizeMs - base_delay_ms))
+ << 30;
+ int64_t cost = delay_ms + 100 * ms_per_loss_percent_ * loss_probability;
+
+ if (cost < min_cost) {
+ min_cost = cost;
+ min_bucket = i;
+ }
+ if (loss_probability == 0) {
+ break;
+ }
+ }
+
+ return min_bucket;
+}
+
+} // namespace webrtc
diff --git a/modules/audio_coding/neteq/reorder_optimizer.h b/modules/audio_coding/neteq/reorder_optimizer.h
new file mode 100644
index 0000000..06f6bc7
--- /dev/null
+++ b/modules/audio_coding/neteq/reorder_optimizer.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (c) 2021 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_AUDIO_CODING_NETEQ_REORDER_OPTIMIZER_H_
+#define MODULES_AUDIO_CODING_NETEQ_REORDER_OPTIMIZER_H_
+
+#include "absl/types/optional.h"
+#include "modules/audio_coding/neteq/histogram.h"
+
+namespace webrtc {
+
+// Calculates an optimal delay to reduce the chance of missing reordered
+// packets. The delay/loss trade-off can be tune using the `ms_per_loss_percent`
+// parameter.
+class ReorderOptimizer {
+ public:
+ ReorderOptimizer(int forget_factor,
+ int ms_per_loss_percent,
+ absl::optional<int> start_forget_weight);
+
+ void Update(int relative_delay_ms, bool reordered, int base_delay_ms);
+
+ absl::optional<int> GetOptimalDelayMs() const { return optimal_delay_ms_; }
+
+ void Reset();
+
+ private:
+ int MinimizeCostFunction(int base_delay_ms) const;
+
+ Histogram histogram_;
+ const int ms_per_loss_percent_;
+ absl::optional<int> optimal_delay_ms_;
+};
+
+} // namespace webrtc
+#endif // MODULES_AUDIO_CODING_NETEQ_REORDER_OPTIMIZER_H_
diff --git a/modules/audio_coding/neteq/reorder_optimizer_unittest.cc b/modules/audio_coding/neteq/reorder_optimizer_unittest.cc
new file mode 100644
index 0000000..aaa1062
--- /dev/null
+++ b/modules/audio_coding/neteq/reorder_optimizer_unittest.cc
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2021 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/audio_coding/neteq/reorder_optimizer.h"
+
+#include "test/gtest.h"
+
+namespace webrtc {
+
+namespace {
+
+constexpr int kForgetFactor = 32745; // 0.9993 in Q15.
+constexpr int kMsPerLossPercent = 20;
+constexpr int kStartForgetWeight = 1;
+
+} // namespace
+
+TEST(ReorderOptimizerTest, OnlyIncreaseDelayForReorderedPackets) {
+ ReorderOptimizer reorder_optimizer(kForgetFactor, kMsPerLossPercent,
+ kStartForgetWeight);
+ EXPECT_FALSE(reorder_optimizer.GetOptimalDelayMs());
+
+ // Delay should not increase for in-order packets.
+ reorder_optimizer.Update(60, /*reordered=*/false, 0);
+ EXPECT_EQ(reorder_optimizer.GetOptimalDelayMs(), 20);
+
+ reorder_optimizer.Update(100, /*reordered=*/false, 0);
+ EXPECT_EQ(reorder_optimizer.GetOptimalDelayMs(), 20);
+
+ reorder_optimizer.Update(80, /*reordered=*/true, 0);
+ EXPECT_EQ(reorder_optimizer.GetOptimalDelayMs(), 100);
+}
+
+TEST(ReorderOptimizerTest, AvoidIncreasingDelayWhenProbabilityIsLow) {
+ ReorderOptimizer reorder_optimizer(kForgetFactor, kMsPerLossPercent,
+ kStartForgetWeight);
+
+ reorder_optimizer.Update(40, /*reordered=*/true, 0);
+ reorder_optimizer.Update(40, /*reordered=*/true, 0);
+ reorder_optimizer.Update(40, /*reordered=*/true, 0);
+ EXPECT_EQ(reorder_optimizer.GetOptimalDelayMs(), 60);
+
+ // The cost of the delay is too high relative the probability.
+ reorder_optimizer.Update(600, /*reordered=*/true, 0);
+ EXPECT_EQ(reorder_optimizer.GetOptimalDelayMs(), 60);
+}
+
+TEST(ReorderOptimizerTest, BaseDelayIsSubtractedFromCost) {
+ constexpr int kBaseDelayMs = 200;
+ ReorderOptimizer reorder_optimizer(kForgetFactor, kMsPerLossPercent,
+ kStartForgetWeight);
+
+ reorder_optimizer.Update(40, /*reordered=*/true, kBaseDelayMs);
+ reorder_optimizer.Update(40, /*reordered=*/true, kBaseDelayMs);
+ reorder_optimizer.Update(40, /*reordered=*/true, kBaseDelayMs);
+ EXPECT_EQ(reorder_optimizer.GetOptimalDelayMs(), 60);
+
+ // The cost of the delay is too high relative the probability.
+ reorder_optimizer.Update(600, /*reordered=*/true, kBaseDelayMs);
+ EXPECT_EQ(reorder_optimizer.GetOptimalDelayMs(), 620);
+}
+
+} // namespace webrtc
