Use |probe_cluster_id| to cluster packets.
Introduced new class DelayBasedProbingEstimator which is a copy of
RemoteBitrateEstimatorAbsSendTime with only minor changes. This makes probing
more reliable but is still not usable for mid-call probing.
BUG=
Review-Url: https://codereview.webrtc.org/2038023002
Cr-Original-Commit-Position: refs/heads/master@{#13195}
Cr-Mirrored-From: https://chromium.googlesource.com/external/webrtc
Cr-Mirrored-Commit: 863a8264cc0d8499fb7b666cb8be868ab95b1bff
diff --git a/modules/congestion_controller/BUILD.gn b/modules/congestion_controller/BUILD.gn
index 3835c19..2af1754 100644
--- a/modules/congestion_controller/BUILD.gn
+++ b/modules/congestion_controller/BUILD.gn
@@ -11,6 +11,8 @@
source_set("congestion_controller") {
sources = [
"congestion_controller.cc",
+ "delay_based_bwe.cc",
+ "delay_based_bwe.h",
"include/congestion_controller.h",
]
diff --git a/modules/congestion_controller/congestion_controller.cc b/modules/congestion_controller/congestion_controller.cc
index 38e488a..593f4a5 100644
--- a/modules/congestion_controller/congestion_controller.cc
+++ b/modules/congestion_controller/congestion_controller.cc
@@ -20,6 +20,7 @@
#include "webrtc/base/socket.h"
#include "webrtc/base/thread_annotations.h"
#include "webrtc/modules/bitrate_controller/include/bitrate_controller.h"
+#include "webrtc/modules/congestion_controller/delay_based_bwe.h"
#include "webrtc/modules/remote_bitrate_estimator/include/send_time_history.h"
#include "webrtc/modules/remote_bitrate_estimator/remote_bitrate_estimator_abs_send_time.h"
#include "webrtc/modules/remote_bitrate_estimator/remote_bitrate_estimator_single_stream.h"
@@ -207,7 +208,7 @@
void CongestionController::Init() {
transport_feedback_adapter_.SetBitrateEstimator(
- new RemoteBitrateEstimatorAbsSendTime(&transport_feedback_adapter_));
+ new DelayBasedBwe(&transport_feedback_adapter_));
transport_feedback_adapter_.GetBitrateEstimator()->SetMinBitrate(
min_bitrate_bps_);
}
diff --git a/modules/congestion_controller/congestion_controller.gypi b/modules/congestion_controller/congestion_controller.gypi
index c2531ab..5b23ae8 100644
--- a/modules/congestion_controller/congestion_controller.gypi
+++ b/modules/congestion_controller/congestion_controller.gypi
@@ -19,6 +19,8 @@
'sources': [
'congestion_controller.cc',
'include/congestion_controller.h',
+ 'delay_based_bwe.cc',
+ 'delay_based_bwe.h',
],
# TODO(jschuh): Bug 1348: fix size_t to int truncations.
'msvs_disabled_warnings': [ 4267, ],
diff --git a/modules/congestion_controller/delay_based_bwe.cc b/modules/congestion_controller/delay_based_bwe.cc
new file mode 100644
index 0000000..27cbf01
--- /dev/null
+++ b/modules/congestion_controller/delay_based_bwe.cc
@@ -0,0 +1,406 @@
+/*
+ * 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 "webrtc/modules/congestion_controller/delay_based_bwe.h"
+
+#include <math.h>
+
+#include <algorithm>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/constructormagic.h"
+#include "webrtc/base/logging.h"
+#include "webrtc/base/thread_annotations.h"
+#include "webrtc/modules/pacing/paced_sender.h"
+#include "webrtc/modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
+#include "webrtc/system_wrappers/include/critical_section_wrapper.h"
+#include "webrtc/typedefs.h"
+
+namespace {
+enum {
+ kTimestampGroupLengthMs = 5,
+ kAbsSendTimeFraction = 18,
+ kAbsSendTimeInterArrivalUpshift = 8,
+ kInterArrivalShift = kAbsSendTimeFraction + kAbsSendTimeInterArrivalUpshift,
+ kInitialProbingIntervalMs = 2000,
+ kMinClusterSize = 4,
+ kMaxProbePackets = 15,
+ kExpectedNumberOfProbes = 3
+};
+
+static const double kTimestampToMs =
+ 1000.0 / static_cast<double>(1 << kInterArrivalShift);
+
+template <typename K, typename V>
+std::vector<K> Keys(const std::map<K, V>& map) {
+ std::vector<K> keys;
+ keys.reserve(map.size());
+ for (typename std::map<K, V>::const_iterator it = map.begin();
+ it != map.end(); ++it) {
+ keys.push_back(it->first);
+ }
+ return keys;
+}
+
+uint32_t ConvertMsTo24Bits(int64_t time_ms) {
+ uint32_t time_24_bits =
+ static_cast<uint32_t>(
+ ((static_cast<uint64_t>(time_ms) << kAbsSendTimeFraction) + 500) /
+ 1000) &
+ 0x00FFFFFF;
+ return time_24_bits;
+}
+} // namespace
+
+namespace webrtc {
+
+void DelayBasedBwe::AddCluster(std::list<Cluster>* clusters, Cluster* cluster) {
+ cluster->send_mean_ms /= static_cast<float>(cluster->count);
+ cluster->recv_mean_ms /= static_cast<float>(cluster->count);
+ cluster->mean_size /= cluster->count;
+ clusters->push_back(*cluster);
+}
+
+DelayBasedBwe::DelayBasedBwe(RemoteBitrateObserver* observer)
+ : observer_(observer),
+ inter_arrival_(),
+ estimator_(),
+ detector_(OverUseDetectorOptions()),
+ incoming_bitrate_(kBitrateWindowMs, 8000),
+ total_probes_received_(0),
+ first_packet_time_ms_(-1),
+ last_update_ms_(-1),
+ ssrcs_() {
+ RTC_DCHECK(observer_);
+ // NOTE! The BitrateEstimatorTest relies on this EXACT log line.
+ LOG(LS_INFO) << "RemoteBitrateEstimatorAbsSendTime: Instantiating.";
+ network_thread_.DetachFromThread();
+}
+
+void DelayBasedBwe::ComputeClusters(std::list<Cluster>* clusters) const {
+ Cluster current;
+ int64_t prev_send_time = -1;
+ int64_t prev_recv_time = -1;
+ int last_probe_cluster_id = -1;
+ for (std::list<Probe>::const_iterator it = probes_.begin();
+ it != probes_.end(); ++it) {
+ if (last_probe_cluster_id == -1)
+ last_probe_cluster_id = it->cluster_id;
+ if (prev_send_time >= 0) {
+ int send_delta_ms = it->send_time_ms - prev_send_time;
+ int recv_delta_ms = it->recv_time_ms - prev_recv_time;
+ if (send_delta_ms >= 1 && recv_delta_ms >= 1) {
+ ++current.num_above_min_delta;
+ }
+ if (it->cluster_id != last_probe_cluster_id) {
+ if (current.count >= kMinClusterSize)
+ AddCluster(clusters, ¤t);
+ current = Cluster();
+ }
+ current.send_mean_ms += send_delta_ms;
+ current.recv_mean_ms += recv_delta_ms;
+ current.mean_size += it->payload_size;
+ ++current.count;
+ last_probe_cluster_id = it->cluster_id;
+ }
+ prev_send_time = it->send_time_ms;
+ prev_recv_time = it->recv_time_ms;
+ }
+ if (current.count >= kMinClusterSize)
+ AddCluster(clusters, ¤t);
+}
+
+std::list<DelayBasedBwe::Cluster>::const_iterator DelayBasedBwe::FindBestProbe(
+ const std::list<Cluster>& clusters) const {
+ int highest_probe_bitrate_bps = 0;
+ std::list<Cluster>::const_iterator best_it = clusters.end();
+ for (std::list<Cluster>::const_iterator it = clusters.begin();
+ it != clusters.end(); ++it) {
+ if (it->send_mean_ms == 0 || it->recv_mean_ms == 0)
+ continue;
+ int send_bitrate_bps = it->mean_size * 8 * 1000 / it->send_mean_ms;
+ int recv_bitrate_bps = it->mean_size * 8 * 1000 / it->recv_mean_ms;
+ if (it->num_above_min_delta > it->count / 2 &&
+ (it->recv_mean_ms - it->send_mean_ms <= 2.0f &&
+ it->send_mean_ms - it->recv_mean_ms <= 5.0f)) {
+ int probe_bitrate_bps =
+ std::min(it->GetSendBitrateBps(), it->GetRecvBitrateBps());
+ if (probe_bitrate_bps > highest_probe_bitrate_bps) {
+ highest_probe_bitrate_bps = probe_bitrate_bps;
+ best_it = it;
+ }
+ } else {
+ LOG(LS_INFO) << "Probe failed, sent at " << send_bitrate_bps
+ << " bps, received at " << recv_bitrate_bps
+ << " bps. Mean send delta: " << it->send_mean_ms
+ << " ms, mean recv delta: " << it->recv_mean_ms
+ << " ms, num probes: " << it->count;
+ break;
+ }
+ }
+ return best_it;
+}
+
+DelayBasedBwe::ProbeResult DelayBasedBwe::ProcessClusters(int64_t now_ms) {
+ std::list<Cluster> clusters;
+ ComputeClusters(&clusters);
+ if (clusters.empty()) {
+ // If we reach the max number of probe packets and still have no clusters,
+ // we will remove the oldest one.
+ if (probes_.size() >= kMaxProbePackets)
+ probes_.pop_front();
+ return ProbeResult::kNoUpdate;
+ }
+
+ std::list<Cluster>::const_iterator best_it = FindBestProbe(clusters);
+ if (best_it != clusters.end()) {
+ int probe_bitrate_bps =
+ std::min(best_it->GetSendBitrateBps(), best_it->GetRecvBitrateBps());
+ // Make sure that a probe sent on a lower bitrate than our estimate can't
+ // reduce the estimate.
+ if (IsBitrateImproving(probe_bitrate_bps)) {
+ LOG(LS_INFO) << "Probe successful, sent at "
+ << best_it->GetSendBitrateBps() << " bps, received at "
+ << best_it->GetRecvBitrateBps()
+ << " bps. Mean send delta: " << best_it->send_mean_ms
+ << " ms, mean recv delta: " << best_it->recv_mean_ms
+ << " ms, num probes: " << best_it->count;
+ remote_rate_.SetEstimate(probe_bitrate_bps, now_ms);
+ return ProbeResult::kBitrateUpdated;
+ }
+ }
+
+ // Not probing and received non-probe packet, or finished with current set
+ // of probes.
+ if (clusters.size() >= kExpectedNumberOfProbes)
+ probes_.clear();
+ return ProbeResult::kNoUpdate;
+}
+
+bool DelayBasedBwe::IsBitrateImproving(int new_bitrate_bps) const {
+ bool initial_probe = !remote_rate_.ValidEstimate() && new_bitrate_bps > 0;
+ bool bitrate_above_estimate =
+ remote_rate_.ValidEstimate() &&
+ new_bitrate_bps > static_cast<int>(remote_rate_.LatestEstimate());
+ return initial_probe || bitrate_above_estimate;
+}
+
+void DelayBasedBwe::IncomingPacketFeedbackVector(
+ const std::vector<PacketInfo>& packet_feedback_vector) {
+ RTC_DCHECK(network_thread_.CalledOnValidThread());
+ for (const auto& packet_info : packet_feedback_vector) {
+ IncomingPacketInfo(packet_info.arrival_time_ms,
+ ConvertMsTo24Bits(packet_info.send_time_ms),
+ packet_info.payload_size, 0, packet_info.was_paced,
+ packet_info.probe_cluster_id);
+ }
+}
+
+void DelayBasedBwe::IncomingPacket(int64_t arrival_time_ms,
+ size_t payload_size,
+ const RTPHeader& header,
+ bool was_paced) {
+ RTC_DCHECK(network_thread_.CalledOnValidThread());
+ if (!header.extension.hasAbsoluteSendTime) {
+ // NOTE! The BitrateEstimatorTest relies on this EXACT log line.
+ LOG(LS_WARNING) << "RemoteBitrateEstimatorAbsSendTime: Incoming packet "
+ "is missing absolute send time extension!";
+ return;
+ }
+ IncomingPacketInfo(arrival_time_ms, header.extension.absoluteSendTime,
+ payload_size, header.ssrc, was_paced,
+ PacketInfo::kNotAProbe);
+}
+
+void DelayBasedBwe::IncomingPacket(int64_t arrival_time_ms,
+ size_t payload_size,
+ const RTPHeader& header,
+ bool was_paced,
+ int probe_cluster_id) {
+ RTC_DCHECK(network_thread_.CalledOnValidThread());
+ if (!header.extension.hasAbsoluteSendTime) {
+ // NOTE! The BitrateEstimatorTest relies on this EXACT log line.
+ LOG(LS_WARNING) << "RemoteBitrateEstimatorAbsSendTime: Incoming packet "
+ "is missing absolute send time extension!";
+ return;
+ }
+ IncomingPacketInfo(arrival_time_ms, header.extension.absoluteSendTime,
+ payload_size, header.ssrc, was_paced, probe_cluster_id);
+}
+
+void DelayBasedBwe::IncomingPacketInfo(int64_t arrival_time_ms,
+ uint32_t send_time_24bits,
+ size_t payload_size,
+ uint32_t ssrc,
+ bool was_paced,
+ int probe_cluster_id) {
+ assert(send_time_24bits < (1ul << 24));
+ // Shift up send time to use the full 32 bits that inter_arrival works with,
+ // so wrapping works properly.
+ uint32_t timestamp = send_time_24bits << kAbsSendTimeInterArrivalUpshift;
+ int64_t send_time_ms = static_cast<int64_t>(timestamp) * kTimestampToMs;
+
+ int64_t now_ms = arrival_time_ms;
+ // TODO(holmer): SSRCs are only needed for REMB, should be broken out from
+ // here.
+ incoming_bitrate_.Update(payload_size, now_ms);
+
+ if (first_packet_time_ms_ == -1)
+ first_packet_time_ms_ = arrival_time_ms;
+
+ uint32_t ts_delta = 0;
+ int64_t t_delta = 0;
+ int size_delta = 0;
+
+ bool update_estimate = false;
+ uint32_t target_bitrate_bps = 0;
+ std::vector<uint32_t> ssrcs;
+ {
+ rtc::CritScope lock(&crit_);
+
+ TimeoutStreams(now_ms);
+ RTC_DCHECK(inter_arrival_.get());
+ RTC_DCHECK(estimator_.get());
+ ssrcs_[ssrc] = now_ms;
+
+ // For now only try to detect probes while we don't have a valid estimate,
+ // and make sure the packet was paced. We currently assume that only packets
+ // larger than 200 bytes are paced by the sender.
+ if (probe_cluster_id != PacketInfo::kNotAProbe &&
+ payload_size > PacedSender::kMinProbePacketSize &&
+ (!remote_rate_.ValidEstimate() ||
+ now_ms - first_packet_time_ms_ < kInitialProbingIntervalMs)) {
+ // TODO(holmer): Use a map instead to get correct order?
+ if (total_probes_received_ < kMaxProbePackets) {
+ int send_delta_ms = -1;
+ int recv_delta_ms = -1;
+ if (!probes_.empty()) {
+ send_delta_ms = send_time_ms - probes_.back().send_time_ms;
+ recv_delta_ms = arrival_time_ms - probes_.back().recv_time_ms;
+ }
+ LOG(LS_INFO) << "Probe packet received: send time=" << send_time_ms
+ << " ms, recv time=" << arrival_time_ms
+ << " ms, send delta=" << send_delta_ms
+ << " ms, recv delta=" << recv_delta_ms << " ms.";
+ }
+ probes_.push_back(
+ Probe(send_time_ms, arrival_time_ms, payload_size, probe_cluster_id));
+ ++total_probes_received_;
+ // Make sure that a probe which updated the bitrate immediately has an
+ // effect by calling the OnReceiveBitrateChanged callback.
+ if (ProcessClusters(now_ms) == ProbeResult::kBitrateUpdated)
+ update_estimate = true;
+ }
+ if (inter_arrival_->ComputeDeltas(timestamp, arrival_time_ms, payload_size,
+ &ts_delta, &t_delta, &size_delta)) {
+ double ts_delta_ms = (1000.0 * ts_delta) / (1 << kInterArrivalShift);
+ estimator_->Update(t_delta, ts_delta_ms, size_delta, detector_.State());
+ detector_.Detect(estimator_->offset(), ts_delta_ms,
+ estimator_->num_of_deltas(), arrival_time_ms);
+ }
+
+ if (!update_estimate) {
+ // Check if it's time for a periodic update or if we should update because
+ // of an over-use.
+ if (last_update_ms_ == -1 ||
+ now_ms - last_update_ms_ > remote_rate_.GetFeedbackInterval()) {
+ update_estimate = true;
+ } else if (detector_.State() == kBwOverusing) {
+ rtc::Optional<uint32_t> incoming_rate = incoming_bitrate_.Rate(now_ms);
+ if (incoming_rate &&
+ remote_rate_.TimeToReduceFurther(now_ms, *incoming_rate)) {
+ update_estimate = true;
+ }
+ }
+ }
+
+ if (update_estimate) {
+ // The first overuse should immediately trigger a new estimate.
+ // We also have to update the estimate immediately if we are overusing
+ // and the target bitrate is too high compared to what we are receiving.
+ const RateControlInput input(detector_.State(),
+ incoming_bitrate_.Rate(now_ms),
+ estimator_->var_noise());
+ remote_rate_.Update(&input, now_ms);
+ target_bitrate_bps = remote_rate_.UpdateBandwidthEstimate(now_ms);
+ update_estimate = remote_rate_.ValidEstimate();
+ ssrcs = Keys(ssrcs_);
+ }
+ }
+ if (update_estimate) {
+ last_update_ms_ = now_ms;
+ observer_->OnReceiveBitrateChanged(ssrcs, target_bitrate_bps);
+ }
+}
+
+void DelayBasedBwe::Process() {}
+
+int64_t DelayBasedBwe::TimeUntilNextProcess() {
+ const int64_t kDisabledModuleTime = 1000;
+ return kDisabledModuleTime;
+}
+
+void DelayBasedBwe::TimeoutStreams(int64_t now_ms) {
+ for (Ssrcs::iterator it = ssrcs_.begin(); it != ssrcs_.end();) {
+ if ((now_ms - it->second) > kStreamTimeOutMs) {
+ ssrcs_.erase(it++);
+ } else {
+ ++it;
+ }
+ }
+ if (ssrcs_.empty()) {
+ // We can't update the estimate if we don't have any active streams.
+ inter_arrival_.reset(
+ new InterArrival((kTimestampGroupLengthMs << kInterArrivalShift) / 1000,
+ kTimestampToMs, true));
+ estimator_.reset(new OveruseEstimator(OverUseDetectorOptions()));
+ // We deliberately don't reset the first_packet_time_ms_ here for now since
+ // we only probe for bandwidth in the beginning of a call right now.
+ }
+}
+
+void DelayBasedBwe::OnRttUpdate(int64_t avg_rtt_ms, int64_t max_rtt_ms) {
+ rtc::CritScope lock(&crit_);
+ remote_rate_.SetRtt(avg_rtt_ms);
+}
+
+void DelayBasedBwe::RemoveStream(uint32_t ssrc) {
+ rtc::CritScope lock(&crit_);
+ ssrcs_.erase(ssrc);
+}
+
+bool DelayBasedBwe::LatestEstimate(std::vector<uint32_t>* ssrcs,
+ uint32_t* bitrate_bps) const {
+ // Currently accessed from both the process thread (see
+ // ModuleRtpRtcpImpl::Process()) and the configuration thread (see
+ // Call::GetStats()). Should in the future only be accessed from a single
+ // thread.
+ RTC_DCHECK(ssrcs);
+ RTC_DCHECK(bitrate_bps);
+ rtc::CritScope lock(&crit_);
+ if (!remote_rate_.ValidEstimate()) {
+ return false;
+ }
+ *ssrcs = Keys(ssrcs_);
+ if (ssrcs_.empty()) {
+ *bitrate_bps = 0;
+ } else {
+ *bitrate_bps = remote_rate_.LatestEstimate();
+ }
+ return true;
+}
+
+void DelayBasedBwe::SetMinBitrate(int min_bitrate_bps) {
+ // Called from both the configuration thread and the network thread. Shouldn't
+ // be called from the network thread in the future.
+ rtc::CritScope lock(&crit_);
+ remote_rate_.SetMinBitrate(min_bitrate_bps);
+}
+} // namespace webrtc
diff --git a/modules/congestion_controller/delay_based_bwe.h b/modules/congestion_controller/delay_based_bwe.h
new file mode 100644
index 0000000..05fbbd8
--- /dev/null
+++ b/modules/congestion_controller/delay_based_bwe.h
@@ -0,0 +1,153 @@
+/*
+ * 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 WEBRTC_MODULES_CONGESTION_CONTROLLER_DELAY_BASED_BWE_H_
+#define WEBRTC_MODULES_CONGESTION_CONTROLLER_DELAY_BASED_BWE_H_
+
+#include <list>
+#include <map>
+#include <memory>
+#include <vector>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/constructormagic.h"
+#include "webrtc/base/criticalsection.h"
+#include "webrtc/base/rate_statistics.h"
+#include "webrtc/base/thread_checker.h"
+#include "webrtc/modules/remote_bitrate_estimator/aimd_rate_control.h"
+#include "webrtc/modules/remote_bitrate_estimator/include/remote_bitrate_estimator.h"
+#include "webrtc/modules/remote_bitrate_estimator/inter_arrival.h"
+#include "webrtc/modules/remote_bitrate_estimator/overuse_detector.h"
+#include "webrtc/modules/remote_bitrate_estimator/overuse_estimator.h"
+#include "webrtc/system_wrappers/include/critical_section_wrapper.h"
+
+namespace webrtc {
+
+class DelayBasedBwe : public RemoteBitrateEstimator {
+ public:
+ explicit DelayBasedBwe(RemoteBitrateObserver* observer);
+ virtual ~DelayBasedBwe() {}
+
+ void IncomingPacketFeedbackVector(
+ const std::vector<PacketInfo>& packet_feedback_vector) override;
+
+ void IncomingPacket(int64_t arrival_time_ms,
+ size_t payload_size,
+ const RTPHeader& header,
+ bool was_paced) override;
+
+ void IncomingPacket(int64_t arrival_time_ms,
+ size_t payload_size,
+ const RTPHeader& header,
+ bool was_paced,
+ int probe_cluster_id);
+
+ // This class relies on Process() being called periodically (at least once
+ // every other second) for streams to be timed out properly. Therefore it
+ // shouldn't be detached from the ProcessThread except if it's about to be
+ // deleted.
+ void Process() override;
+ int64_t TimeUntilNextProcess() override;
+ void OnRttUpdate(int64_t avg_rtt_ms, int64_t max_rtt_ms) override;
+ void RemoveStream(uint32_t ssrc) override;
+ bool LatestEstimate(std::vector<uint32_t>* ssrcs,
+ uint32_t* bitrate_bps) const override;
+ void SetMinBitrate(int min_bitrate_bps) override;
+
+ private:
+ struct Probe {
+ Probe(int64_t send_time_ms,
+ int64_t recv_time_ms,
+ size_t payload_size,
+ int cluster_id)
+ : send_time_ms(send_time_ms),
+ recv_time_ms(recv_time_ms),
+ payload_size(payload_size),
+ cluster_id(cluster_id) {}
+ int64_t send_time_ms;
+ int64_t recv_time_ms;
+ size_t payload_size;
+ int cluster_id;
+ };
+
+ struct Cluster {
+ Cluster()
+ : send_mean_ms(0.0f),
+ recv_mean_ms(0.0f),
+ mean_size(0),
+ count(0),
+ num_above_min_delta(0) {}
+
+ int GetSendBitrateBps() const {
+ RTC_CHECK_GT(send_mean_ms, 0.0f);
+ return mean_size * 8 * 1000 / send_mean_ms;
+ }
+
+ int GetRecvBitrateBps() const {
+ RTC_CHECK_GT(recv_mean_ms, 0.0f);
+ return mean_size * 8 * 1000 / recv_mean_ms;
+ }
+
+ float send_mean_ms;
+ float recv_mean_ms;
+ // TODO(holmer): Add some variance metric as well?
+ size_t mean_size;
+ int count;
+ int num_above_min_delta;
+ };
+
+ typedef std::map<uint32_t, int64_t> Ssrcs;
+ enum class ProbeResult { kBitrateUpdated, kNoUpdate };
+
+ static void AddCluster(std::list<Cluster>* clusters, Cluster* cluster);
+
+ void IncomingPacketInfo(int64_t arrival_time_ms,
+ uint32_t send_time_24bits,
+ size_t payload_size,
+ uint32_t ssrc,
+ bool was_paced,
+ int probe_cluster_id);
+
+ void ComputeClusters(std::list<Cluster>* clusters) const;
+
+ std::list<Cluster>::const_iterator FindBestProbe(
+ const std::list<Cluster>& clusters) const;
+
+ // Returns true if a probe which changed the estimate was detected.
+ ProbeResult ProcessClusters(int64_t now_ms) EXCLUSIVE_LOCKS_REQUIRED(&crit_);
+
+ bool IsBitrateImproving(int probe_bitrate_bps) const
+ EXCLUSIVE_LOCKS_REQUIRED(&crit_);
+
+ void TimeoutStreams(int64_t now_ms) EXCLUSIVE_LOCKS_REQUIRED(&crit_);
+
+ rtc::ThreadChecker network_thread_;
+ RemoteBitrateObserver* const observer_;
+ std::unique_ptr<InterArrival> inter_arrival_;
+ std::unique_ptr<OveruseEstimator> estimator_;
+ OveruseDetector detector_;
+ RateStatistics incoming_bitrate_;
+ std::vector<int> recent_propagation_delta_ms_;
+ std::vector<int64_t> recent_update_time_ms_;
+ std::list<Probe> probes_;
+ size_t total_probes_received_;
+ int64_t first_packet_time_ms_;
+ int64_t last_update_ms_;
+
+ rtc::CriticalSection crit_;
+ Ssrcs ssrcs_ GUARDED_BY(&crit_);
+ AimdRateControl remote_rate_ GUARDED_BY(&crit_);
+
+ RTC_DISALLOW_IMPLICIT_CONSTRUCTORS(DelayBasedBwe);
+};
+
+} // namespace webrtc
+
+#endif // WEBRTC_MODULES_CONGESTION_CONTROLLER_DELAY_BASED_BWE_H_
diff --git a/modules/congestion_controller/delay_based_bwe_unittest.cc b/modules/congestion_controller/delay_based_bwe_unittest.cc
new file mode 100644
index 0000000..7efd29f
--- /dev/null
+++ b/modules/congestion_controller/delay_based_bwe_unittest.cc
@@ -0,0 +1,236 @@
+/*
+ * 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 "webrtc/modules/congestion_controller/delay_based_bwe.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "webrtc/modules/pacing/paced_sender.h"
+#include "webrtc/system_wrappers/include/clock.h"
+
+namespace webrtc {
+
+class TestDelayBasedBwe : public ::testing::Test, public RemoteBitrateObserver {
+ public:
+ static constexpr int kArrivalTimeClockOffsetMs = 60000;
+ static constexpr int kNumProbes = 5;
+
+ TestDelayBasedBwe()
+ : bwe_(this), clock_(0), bitrate_updated_(false), latest_bitrate_(0) {}
+
+ uint32_t AbsSendTime(int64_t t, int64_t denom) {
+ return (((t << 18) + (denom >> 1)) / denom) & 0x00fffffful;
+ }
+
+ void IncomingPacket(uint32_t ssrc,
+ size_t payload_size,
+ int64_t arrival_time,
+ uint32_t rtp_timestamp,
+ uint32_t absolute_send_time,
+ bool was_paced,
+ int probe_cluster_id) {
+ RTPHeader header;
+ memset(&header, 0, sizeof(header));
+ header.ssrc = ssrc;
+ header.timestamp = rtp_timestamp;
+ header.extension.hasAbsoluteSendTime = true;
+ header.extension.absoluteSendTime = absolute_send_time;
+ bwe_.IncomingPacket(arrival_time + kArrivalTimeClockOffsetMs, payload_size,
+ header, was_paced, probe_cluster_id);
+ }
+
+ void OnReceiveBitrateChanged(const std::vector<uint32_t>& ssrcs,
+ uint32_t bitrate) {
+ bitrate_updated_ = true;
+ latest_bitrate_ = bitrate;
+ }
+
+ bool bitrate_updated() {
+ bool res = bitrate_updated_;
+ bitrate_updated_ = false;
+ return res;
+ }
+
+ int latest_bitrate() { return latest_bitrate_; }
+
+ DelayBasedBwe bwe_;
+ SimulatedClock clock_;
+
+ private:
+ bool bitrate_updated_;
+ int latest_bitrate_;
+};
+
+TEST_F(TestDelayBasedBwe, ProbeDetection) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+
+ // First burst sent at 8 * 1000 / 10 = 800 kbps.
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(10);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * now_ms, AbsSendTime(now_ms, 1000),
+ true, 0);
+ }
+ EXPECT_TRUE(bitrate_updated());
+
+ // Second burst sent at 8 * 1000 / 5 = 1600 kbps.
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(5);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * now_ms, AbsSendTime(now_ms, 1000),
+ true, 1);
+ }
+
+ EXPECT_TRUE(bitrate_updated());
+ EXPECT_GT(latest_bitrate(), 1500000);
+}
+
+TEST_F(TestDelayBasedBwe, ProbeDetectionNonPacedPackets) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ // First burst sent at 8 * 1000 / 10 = 800 kbps, but with every other packet
+ // not being paced which could mess things up.
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(5);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * now_ms, AbsSendTime(now_ms, 1000),
+ true, 0);
+ // Non-paced packet, arriving 5 ms after.
+ clock_.AdvanceTimeMilliseconds(5);
+ IncomingPacket(0, PacedSender::kMinProbePacketSize + 1, now_ms, 90 * now_ms,
+ AbsSendTime(now_ms, 1000), false, PacketInfo::kNotAProbe);
+ }
+
+ EXPECT_TRUE(bitrate_updated());
+ EXPECT_GT(latest_bitrate(), 800000);
+}
+
+// Packets will require 5 ms to be transmitted to the receiver, causing packets
+// of the second probe to be dispersed.
+TEST_F(TestDelayBasedBwe, ProbeDetectionTooHighBitrate) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ int64_t send_time_ms = 0;
+ // First burst sent at 8 * 1000 / 10 = 800 kbps.
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(10);
+ now_ms = clock_.TimeInMilliseconds();
+ send_time_ms += 10;
+ IncomingPacket(0, 1000, now_ms, 90 * send_time_ms,
+ AbsSendTime(send_time_ms, 1000), true, 0);
+ }
+
+ // Second burst sent at 8 * 1000 / 5 = 1600 kbps, arriving at 8 * 1000 / 8 =
+ // 1000 kbps.
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(8);
+ now_ms = clock_.TimeInMilliseconds();
+ send_time_ms += 5;
+ IncomingPacket(0, 1000, now_ms, send_time_ms,
+ AbsSendTime(send_time_ms, 1000), true, 1);
+ }
+
+ EXPECT_TRUE(bitrate_updated());
+ EXPECT_NEAR(latest_bitrate(), 800000, 10000);
+}
+
+TEST_F(TestDelayBasedBwe, ProbeDetectionSlightlyFasterArrival) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ // First burst sent at 8 * 1000 / 10 = 800 kbps.
+ // Arriving at 8 * 1000 / 5 = 1600 kbps.
+ int64_t send_time_ms = 0;
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(5);
+ send_time_ms += 10;
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * send_time_ms,
+ AbsSendTime(send_time_ms, 1000), true, 23);
+ }
+
+ EXPECT_TRUE(bitrate_updated());
+ EXPECT_GT(latest_bitrate(), 800000);
+}
+
+TEST_F(TestDelayBasedBwe, ProbeDetectionFasterArrival) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ // First burst sent at 8 * 1000 / 10 = 800 kbps.
+ // Arriving at 8 * 1000 / 5 = 1600 kbps.
+ int64_t send_time_ms = 0;
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(1);
+ send_time_ms += 10;
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * send_time_ms,
+ AbsSendTime(send_time_ms, 1000), true, 0);
+ }
+
+ EXPECT_FALSE(bitrate_updated());
+}
+
+TEST_F(TestDelayBasedBwe, ProbeDetectionSlowerArrival) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ // First burst sent at 8 * 1000 / 5 = 1600 kbps.
+ // Arriving at 8 * 1000 / 7 = 1142 kbps.
+ int64_t send_time_ms = 0;
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(7);
+ send_time_ms += 5;
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * send_time_ms,
+ AbsSendTime(send_time_ms, 1000), true, 1);
+ }
+
+ EXPECT_TRUE(bitrate_updated());
+ EXPECT_NEAR(latest_bitrate(), 1140000, 10000);
+}
+
+TEST_F(TestDelayBasedBwe, ProbeDetectionSlowerArrivalHighBitrate) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ // Burst sent at 8 * 1000 / 1 = 8000 kbps.
+ // Arriving at 8 * 1000 / 2 = 4000 kbps.
+ int64_t send_time_ms = 0;
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(2);
+ send_time_ms += 1;
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * send_time_ms,
+ AbsSendTime(send_time_ms, 1000), true, 1);
+ }
+
+ EXPECT_TRUE(bitrate_updated());
+ EXPECT_NEAR(latest_bitrate(), 4000000u, 10000);
+}
+
+TEST_F(TestDelayBasedBwe, ProbingIgnoresSmallPackets) {
+ int64_t now_ms = clock_.TimeInMilliseconds();
+ // Probing with 200 bytes every 10 ms, should be ignored by the probe
+ // detection.
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(10);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, PacedSender::kMinProbePacketSize, now_ms, 90 * now_ms,
+ AbsSendTime(now_ms, 1000), true, 1);
+ }
+
+ EXPECT_FALSE(bitrate_updated());
+
+ // Followed by a probe with 1000 bytes packets, should be detected as a
+ // probe.
+ for (int i = 0; i < kNumProbes; ++i) {
+ clock_.AdvanceTimeMilliseconds(10);
+ now_ms = clock_.TimeInMilliseconds();
+ IncomingPacket(0, 1000, now_ms, 90 * now_ms, AbsSendTime(now_ms, 1000),
+ true, 1);
+ }
+
+ // Wait long enough so that we can call Process again.
+ clock_.AdvanceTimeMilliseconds(1000);
+
+ EXPECT_TRUE(bitrate_updated());
+ EXPECT_NEAR(latest_bitrate(), 800000u, 10000);
+}
+} // namespace webrtc
diff --git a/modules/modules.gyp b/modules/modules.gyp
index f47cf2c..e9a250c 100644
--- a/modules/modules.gyp
+++ b/modules/modules.gyp
@@ -270,6 +270,7 @@
'bitrate_controller/bitrate_controller_unittest.cc',
'bitrate_controller/send_side_bandwidth_estimation_unittest.cc',
'congestion_controller/congestion_controller_unittest.cc',
+ 'congestion_controller/delay_based_bwe_unittest.cc',
'media_file/media_file_unittest.cc',
'module_common_types_unittest.cc',
'pacing/bitrate_prober_unittest.cc',
