Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 204 insertions, 0 deletions

diff --git a/third_party/libwebrtc/modules/congestion_controller/goog_cc/robust_throughput_estimator.cc b/third_party/libwebrtc/modules/congestion_controller/goog_cc/robust_throughput_estimator.cc
new file mode 100644
index 0000000000..5a22910fe3
--- /dev/null
+++ b/third_party/libwebrtc/modules/congestion_controller/goog_cc/robust_throughput_estimator.cc
@@ -0,0 +1,204 @@
+/*
+ *  Copyright (c) 2019 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/congestion_controller/goog_cc/robust_throughput_estimator.h"
+
+#include <stddef.h>
+
+#include <algorithm>
+#include <utility>
+#include <vector>
+
+#include "absl/types/optional.h"
+#include "api/transport/network_types.h"
+#include "api/units/data_rate.h"
+#include "api/units/data_size.h"
+#include "api/units/time_delta.h"
+#include "api/units/timestamp.h"
+#include "modules/congestion_controller/goog_cc/acknowledged_bitrate_estimator_interface.h"
+#include "rtc_base/checks.h"
+#include "rtc_base/logging.h"
+
+namespace webrtc {
+
+RobustThroughputEstimator::RobustThroughputEstimator(
+    const RobustThroughputEstimatorSettings& settings)
+    : settings_(settings),
+      latest_discarded_send_time_(Timestamp::MinusInfinity()) {
+  RTC_DCHECK(settings.enabled);
+}
+
+RobustThroughputEstimator::~RobustThroughputEstimator() {}
+
+bool RobustThroughputEstimator::FirstPacketOutsideWindow() {
+  if (window_.empty())
+    return false;
+  if (window_.size() > settings_.max_window_packets)
+    return true;
+  TimeDelta current_window_duration =
+      window_.back().receive_time - window_.front().receive_time;
+  if (current_window_duration > settings_.max_window_duration)
+    return true;
+  if (window_.size() > settings_.window_packets &&
+      current_window_duration > settings_.min_window_duration) {
+    return true;
+  }
+  return false;
+}
+
+void RobustThroughputEstimator::IncomingPacketFeedbackVector(
+    const std::vector<PacketResult>& packet_feedback_vector) {
+  RTC_DCHECK(std::is_sorted(packet_feedback_vector.begin(),
+                            packet_feedback_vector.end(),
+                            PacketResult::ReceiveTimeOrder()));
+  for (const auto& packet : packet_feedback_vector) {
+    // Ignore packets without valid send or receive times.
+    // (This should not happen in production since lost packets are filtered
+    // out before passing the feedback vector to the throughput estimator.
+    // However, explicitly handling this case makes the estimator more robust
+    // and avoids a hard-to-detect bad state.)
+    if (packet.receive_time.IsInfinite() ||
+        packet.sent_packet.send_time.IsInfinite()) {
+      continue;
+    }
+
+    // Insert the new packet.
+    window_.push_back(packet);
+    window_.back().sent_packet.prior_unacked_data =
+        window_.back().sent_packet.prior_unacked_data *
+        settings_.unacked_weight;
+    // In most cases, receive timestamps should already be in order, but in the
+    // rare case where feedback packets have been reordered, we do some swaps to
+    // ensure that the window is sorted.
+    for (size_t i = window_.size() - 1;
+         i > 0 && window_[i].receive_time < window_[i - 1].receive_time; i--) {
+      std::swap(window_[i], window_[i - 1]);
+    }
+    constexpr TimeDelta kMaxReorderingTime = TimeDelta::Seconds(1);
+    const TimeDelta receive_delta =
+        (window_.back().receive_time - packet.receive_time);
+    if (receive_delta > kMaxReorderingTime) {
+      RTC_LOG(LS_WARNING)
+          << "Severe packet re-ordering or timestamps offset changed: "
+          << receive_delta;
+      window_.clear();
+      latest_discarded_send_time_ = Timestamp::MinusInfinity();
+    }
+  }
+
+  // Remove old packets.
+  while (FirstPacketOutsideWindow()) {
+    latest_discarded_send_time_ = std::max(
+        latest_discarded_send_time_, window_.front().sent_packet.send_time);
+    window_.pop_front();
+  }
+}
+
+absl::optional<DataRate> RobustThroughputEstimator::bitrate() const {
+  if (window_.empty() || window_.size() < settings_.required_packets)
+    return absl::nullopt;
+
+  TimeDelta largest_recv_gap(TimeDelta::Zero());
+  TimeDelta second_largest_recv_gap(TimeDelta::Zero());
+  for (size_t i = 1; i < window_.size(); i++) {
+    // Find receive time gaps.
+    TimeDelta gap = window_[i].receive_time - window_[i - 1].receive_time;
+    if (gap > largest_recv_gap) {
+      second_largest_recv_gap = largest_recv_gap;
+      largest_recv_gap = gap;
+    } else if (gap > second_largest_recv_gap) {
+      second_largest_recv_gap = gap;
+    }
+  }
+
+  Timestamp first_send_time = Timestamp::PlusInfinity();
+  Timestamp last_send_time = Timestamp::MinusInfinity();
+  Timestamp first_recv_time = Timestamp::PlusInfinity();
+  Timestamp last_recv_time = Timestamp::MinusInfinity();
+  DataSize recv_size = DataSize::Bytes(0);
+  DataSize send_size = DataSize::Bytes(0);
+  DataSize first_recv_size = DataSize::Bytes(0);
+  DataSize last_send_size = DataSize::Bytes(0);
+  size_t num_sent_packets_in_window = 0;
+  for (const auto& packet : window_) {
+    if (packet.receive_time < first_recv_time) {
+      first_recv_time = packet.receive_time;
+      first_recv_size =
+          packet.sent_packet.size + packet.sent_packet.prior_unacked_data;
+    }
+    last_recv_time = std::max(last_recv_time, packet.receive_time);
+    recv_size += packet.sent_packet.size;
+    recv_size += packet.sent_packet.prior_unacked_data;
+
+    if (packet.sent_packet.send_time < latest_discarded_send_time_) {
+      // If we have dropped packets from the window that were sent after
+      // this packet, then this packet was reordered. Ignore it from
+      // the send rate computation (since the send time may be very far
+      // in the past, leading to underestimation of the send rate.)
+      // However, ignoring packets creates a risk that we end up without
+      // any packets left to compute a send rate.
+      continue;
+    }
+    if (packet.sent_packet.send_time > last_send_time) {
+      last_send_time = packet.sent_packet.send_time;
+      last_send_size =
+          packet.sent_packet.size + packet.sent_packet.prior_unacked_data;
+    }
+    first_send_time = std::min(first_send_time, packet.sent_packet.send_time);
+
+    send_size += packet.sent_packet.size;
+    send_size += packet.sent_packet.prior_unacked_data;
+    ++num_sent_packets_in_window;
+  }
+
+  // Suppose a packet of size S is sent every T milliseconds.
+  // A window of N packets would contain N*S bytes, but the time difference
+  // between the first and the last packet would only be (N-1)*T. Thus, we
+  // need to remove the size of one packet to get the correct rate of S/T.
+  // Which packet to remove (if the packets have varying sizes),
+  // depends on the network model.
+  // Suppose that 2 packets with sizes s1 and s2, are received at times t1
+  // and t2, respectively. If the packets were transmitted back to back over
+  // a bottleneck with rate capacity r, then we'd expect t2 = t1 + r * s2.
+  // Thus, r = (t2-t1) / s2, so the size of the first packet doesn't affect
+  // the difference between t1 and t2.
+  // Analoguously, if the first packet is sent at time t1 and the sender
+  // paces the packets at rate r, then the second packet can be sent at time
+  // t2 = t1 + r * s1. Thus, the send rate estimate r = (t2-t1) / s1 doesn't
+  // depend on the size of the last packet.
+  recv_size -= first_recv_size;
+  send_size -= last_send_size;
+
+  // Remove the largest gap by replacing it by the second largest gap.
+  // This is to ensure that spurious "delay spikes" (i.e. when the
+  // network stops transmitting packets for a short period, followed
+  // by a burst of delayed packets), don't cause the estimate to drop.
+  // This could cause an overestimation, which we guard against by
+  // never returning an estimate above the send rate.
+  RTC_DCHECK(first_recv_time.IsFinite());
+  RTC_DCHECK(last_recv_time.IsFinite());
+  TimeDelta recv_duration = (last_recv_time - first_recv_time) -
+                            largest_recv_gap + second_largest_recv_gap;
+  recv_duration = std::max(recv_duration, TimeDelta::Millis(1));
+
+  if (num_sent_packets_in_window < settings_.required_packets) {
+    // Too few send times to calculate a reliable send rate.
+    return recv_size / recv_duration;
+  }
+
+  RTC_DCHECK(first_send_time.IsFinite());
+  RTC_DCHECK(last_send_time.IsFinite());
+  TimeDelta send_duration = last_send_time - first_send_time;
+  send_duration = std::max(send_duration, TimeDelta::Millis(1));
+
+  return std::min(send_size / send_duration, recv_size / recv_duration);
+}
+
+}  // namespace webrtc