Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1026)

Unified Diff: webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.cc

Issue 2990163002: Almost full implementation of BBR's core. (Closed)
Patch Set: fixed patch failure Created 3 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.cc
diff --git a/webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.cc b/webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.cc
index 11979bf4468d1b2291fe92233dcd6573fdfad3f8..a45700b19e9528d15303960928e244e3f29dfdde 100644
--- a/webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.cc
+++ b/webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.cc
@@ -12,6 +12,7 @@
#include "webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.h"
#include <stdlib.h>
+#include <algorithm>
#include "webrtc/modules/remote_bitrate_estimator/test/estimators/congestion_window.h"
#include "webrtc/modules/remote_bitrate_estimator/test/estimators/max_bandwidth_filter.h"
@@ -21,7 +22,7 @@ namespace webrtc {
namespace testing {
namespace bwe {
namespace {
-const int kFeedbackIntervalsMs = 3;
+const int kFeedbackIntervalsMs = 5;
// BBR uses this value to double sending rate each round trip. Design document
// suggests using this value.
const float kHighGain = 2.885f;
@@ -35,7 +36,7 @@ const int kMaxRoundsWithoutGrowth = 3;
// Pacing gain values for Probe Bandwidth mode.
const float kPacingGain[] = {1.25, 0.75, 1, 1, 1, 1, 1, 1};
const size_t kGainCycleLength = sizeof(kPacingGain) / sizeof(kPacingGain[0]);
-// The least amount of rounds PROBE_RTT mode should last.
+// Least number of rounds PROBE_RTT should last.
const int kProbeRttDurationRounds = 1;
// The least amount of milliseconds PROBE_RTT mode should last.
const int kProbeRttDurationMs = 200;
@@ -46,9 +47,20 @@ const float kTargetCongestionWindowGain = 1;
// work, it is nice to have some extra room in congestion window for full link
// utilization. Value chosen by observations on different tests.
const float kCruisingCongestionWindowGain = 1.5f;
-// Expiration time for min_rtt sample, which is set to 10 seconds according to
-// BBR design doc.
-const int64_t kMinRttFilterSizeMs = 10000;
+// Pacing gain specific for Recovery mode. Chosen by experiments in simulation
+// tool.
+const float kRecoveryPacingGain = 0.5f;
+// Congestion window gain specific for Recovery mode. Chosen by experiments in
+// simulation tool.
+const float kRecoveryCongestionWindowGain = 1.5f;
+// Number of rounds over which average RTT is stored for Recovery mode.
+const size_t kPastRttsFilterSize = 1;
+// Threshold to assume average RTT has increased for a round. Chosen by
+// experiments in simulation tool.
+const float kRttIncreaseThreshold = 3;
+// Threshold to assume average RTT has decreased for a round. Chosen by
+// experiments in simulation tool.
+const float kRttDecreaseThreshold = 1.5f;
} // namespace
BbrBweSender::BbrBweSender(Clock* clock)
@@ -60,15 +72,32 @@ BbrBweSender::BbrBweSender(Clock* clock)
congestion_window_(new CongestionWindow()),
rand_(new Random(time(NULL))),
round_count_(0),
- last_packet_sent_(0),
round_trip_end_(0),
full_bandwidth_reached_(false),
cycle_start_time_ms_(0),
cycle_index_(0),
- prior_in_flight_(0),
+ bytes_acked_(0),
probe_rtt_start_time_ms_(0),
- minimum_congestion_window_start_time_ms_(),
- minimum_congestion_window_start_round_(0) {
+ minimum_congestion_window_start_time_ms_(0),
+ minimum_congestion_window_start_round_(0),
+ bytes_sent_(0),
+ last_packet_sent_sequence_number_(0),
+ last_packet_acked_sequence_number_(0),
+ last_packet_ack_time_(0),
+ last_packet_send_time_(0),
+ pacing_rate_bps_(0),
+ last_packet_send_time_during_high_gain_ms_(-1),
+ data_sent_before_high_gain_started_bytes_(-1),
+ data_sent_before_high_gain_ended_bytes_(-1),
+ first_packet_ack_time_during_high_gain_ms_(-1),
+ last_packet_ack_time_during_high_gain_ms_(-1),
+ data_acked_before_high_gain_started_bytes_(-1),
+ data_acked_before_high_gain_ended_bytes_(-1),
+ first_packet_seq_num_during_high_gain_(-1),
+ last_packet_seq_num_during_high_gain_(-1),
+ high_gain_over_(false),
+ packet_stats_(),
+ past_rtts_() {
// Initially enter Startup mode.
EnterStartup();
}
@@ -79,26 +108,101 @@ int BbrBweSender::GetFeedbackIntervalMs() const {
return kFeedbackIntervalsMs;
}
+void BbrBweSender::CalculatePacingRate() {
+ pacing_rate_bps_ =
+ max_bandwidth_filter_->max_bandwidth_estimate_bps() * pacing_gain_;
+}
+
+void BbrBweSender::HandleLoss(uint64_t last_acked_packet,
+ uint64_t recently_acked_packet) {
+ // Logic specific to wrapping sequence numbers.
+ if (!last_acked_packet)
+ return;
+ for (uint16_t i = last_acked_packet + 1;
+ AheadOrAt<uint16_t>(recently_acked_packet - 1, i); i++) {
+ congestion_window_->AckReceived(packet_stats_[i].payload_size_bytes);
+ }
+}
+
+void BbrBweSender::AddToPastRtts(int64_t rtt_sample_ms) {
+ uint64_t last_round = 0;
+ if (!past_rtts_.empty())
+ last_round = past_rtts_.back().round;
+
+ // Try to add the sample to the last round.
+ if (last_round == round_count_ && !past_rtts_.empty()) {
+ past_rtts_.back().sum_of_rtts_ms += rtt_sample_ms;
+ past_rtts_.back().num_samples++;
+ } else {
+ // If the sample belongs to a new round, keep number of rounds in the window
+ // equal to |kPastRttsFilterSize|.
+ if (past_rtts_.size() == kPastRttsFilterSize)
+ past_rtts_.pop_front();
+ past_rtts_.push_back(
+ BbrBweSender::AverageRtt(rtt_sample_ms, 1, round_count_));
+ }
+}
+
void BbrBweSender::GiveFeedback(const FeedbackPacket& feedback) {
+ int64_t now_ms = clock_->TimeInMilliseconds();
+ last_packet_ack_time_ = now_ms;
const BbrBweFeedback& fb = static_cast<const BbrBweFeedback&>(feedback);
// feedback_vector holds values of acknowledged packets' sequence numbers.
const std::vector<uint64_t>& feedback_vector = fb.packet_feedback_vector();
- // Check if new round started for the connection. Round is the period of time
- // from sending packet to its acknowledgement.
+ // Go through all the packets acked, update variables/containers accordingly.
+ for (uint16_t sequence_number : feedback_vector) {
+ // Completing packet information with a recently received ack.
+ PacketStats* packet = &packet_stats_[sequence_number];
+ bytes_acked_ += packet->payload_size_bytes;
+ packet->data_sent_bytes = bytes_sent_;
+ packet->last_sent_packet_send_time_ms = last_packet_send_time_;
+ packet->data_acked_bytes = bytes_acked_;
+ packet->ack_time_ms = now_ms;
+ // Logic specific to applying "bucket" to high gain, in order to have
+ // quicker ramp-up. We check if we started receiving acks for the packets
+ // sent during high gain phase.
+ if (packet->sequence_number == first_packet_seq_num_during_high_gain_) {
+ first_packet_ack_time_during_high_gain_ms_ = now_ms;
+ // Substracting half of the packet's size to avoid overestimation.
+ data_acked_before_high_gain_started_bytes_ =
+ bytes_acked_ - packet->payload_size_bytes / 2;
+ }
+ // If the last packet of high gain phase has been acked, high gain phase is
+ // over.
+ if (packet->sequence_number == last_packet_seq_num_during_high_gain_) {
+ last_packet_ack_time_during_high_gain_ms_ = now_ms;
+ data_acked_before_high_gain_ended_bytes_ =
+ bytes_acked_ - packet->payload_size_bytes / 2;
+ high_gain_over_ = true;
+ }
+ // Notify pacer that an ack was received, to adjust data inflight.
+ // TODO(gnish): Add implementation for BitrateObserver class, to notify
+ // pacer about incoming acks.
+ congestion_window_->AckReceived(packet->payload_size_bytes);
+ HandleLoss(last_packet_acked_sequence_number_, packet->sequence_number);
+ last_packet_acked_sequence_number_ = packet->sequence_number;
+ // Logic for wrapping sequence numbers. If round started with packet number
+ // x, it can never end on y, if x > y. That could happen when sequence
+ // numbers are wrapped after some point.
+ if (packet->sequence_number == 0)
+ round_trip_end_ = 0;
+ }
+ // Check if new round started for the connection.
bool new_round_started = false;
if (!feedback_vector.empty()) {
- uint64_t last_acked_packet = *feedback_vector.rbegin();
- if (last_acked_packet > round_trip_end_) {
+ if (last_packet_acked_sequence_number_ > round_trip_end_) {
new_round_started = true;
round_count_++;
- round_trip_end_ = last_packet_sent_;
+ round_trip_end_ = last_packet_sent_sequence_number_;
}
}
+ bool min_rtt_expired = false;
+ min_rtt_expired =
+ UpdateBandwidthAndMinRtt(now_ms, feedback_vector, bytes_acked_);
if (new_round_started && !full_bandwidth_reached_) {
full_bandwidth_reached_ = max_bandwidth_filter_->FullBandwidthReached(
kStartupGrowthTarget, kMaxRoundsWithoutGrowth);
}
- int now_ms = clock_->TimeInMilliseconds();
switch (mode_) {
break;
case STARTUP:
@@ -111,12 +215,25 @@ void BbrBweSender::GiveFeedback(const FeedbackPacket& feedback) {
TryUpdatingCyclePhase(now_ms);
break;
case PROBE_RTT:
- TryExitingProbeRtt(now_ms, 0);
+ TryExitingProbeRtt(now_ms, round_count_);
+ break;
+ case RECOVERY:
+ TryExitingRecovery(new_round_started);
break;
}
TryEnteringProbeRtt(now_ms);
- // TODO(gnish): implement functions updating congestion window and pacing rate
- // controllers.
+ TryEnteringRecovery(new_round_started); // Comment this line to disable
+ // entering Recovery mode.
+ for (uint64_t f : feedback_vector)
+ AddToPastRtts(packet_stats_[f].ack_time_ms - packet_stats_[f].send_time_ms);
+ CalculatePacingRate();
+ // Make sure we don't get stuck when pacing_rate is 0, because of simulation
+ // tool specifics.
+ if (!pacing_rate_bps_)
+ pacing_rate_bps_ = 100;
+ BWE_TEST_LOGGING_PLOT(1, "SendRate", now_ms, pacing_rate_bps_ / 1000);
+ // TODO(gnish): Add implementation for BitrateObserver class to update pacing
+ // rate for the pacer and the encoder.
}
size_t BbrBweSender::TargetCongestionWindow(float gain) {
@@ -127,8 +244,82 @@ size_t BbrBweSender::TargetCongestionWindow(float gain) {
return target_congestion_window;
}
-bool BbrBweSender::UpdateBandwidthAndMinRtt() {
- return false;
+rtc::Optional<int64_t> BbrBweSender::CalculateBandwidthSample(
+ size_t data_sent_bytes,
+ int64_t send_time_delta_ms,
+ size_t data_acked_bytes,
+ int64_t ack_time_delta_ms) {
+ rtc::Optional<int64_t> bandwidth_sample;
+ if (send_time_delta_ms > 0)
+ *bandwidth_sample = data_sent_bytes * 8000 / send_time_delta_ms;
+ rtc::Optional<int64_t> ack_rate;
+ if (ack_time_delta_ms > 0)
+ *ack_rate = data_acked_bytes * 8000 / ack_time_delta_ms;
+ // If send rate couldn't be calculated automaticaly set |bandwidth_sample| to
+ // ack_rate.
+ if (!bandwidth_sample)
+ bandwidth_sample = ack_rate;
+ if (bandwidth_sample && ack_rate)
+ *bandwidth_sample = std::min(*bandwidth_sample, *ack_rate);
+ return bandwidth_sample;
+}
+
+void BbrBweSender::AddSampleForHighGain() {
+ if (!high_gain_over_)
+ return;
+ high_gain_over_ = false;
+ // Calculate data sent/acked and time elapsed only for packets sent during
+ // high gain phase.
+ size_t data_sent_bytes = data_sent_before_high_gain_ended_bytes_ -
+ data_sent_before_high_gain_started_bytes_;
+ int64_t send_time_delta_ms = last_packet_send_time_during_high_gain_ms_ -
+ *first_packet_send_time_during_high_gain_ms_;
+ size_t data_acked_bytes = data_acked_before_high_gain_ended_bytes_ -
+ data_acked_before_high_gain_started_bytes_;
+ int64_t ack_time_delta_ms = last_packet_ack_time_during_high_gain_ms_ -
+ first_packet_ack_time_during_high_gain_ms_;
+ rtc::Optional<int64_t> bandwidth_sample = CalculateBandwidthSample(
+ data_sent_bytes, send_time_delta_ms, data_acked_bytes, ack_time_delta_ms);
+ if (bandwidth_sample)
+ max_bandwidth_filter_->AddBandwidthSample(*bandwidth_sample, round_count_);
+ first_packet_send_time_during_high_gain_ms_.reset();
+}
+
+bool BbrBweSender::UpdateBandwidthAndMinRtt(
+ int64_t now_ms,
+ const std::vector<uint64_t>& feedback_vector,
+ int64_t bytes_acked) {
+ rtc::Optional<int64_t> min_rtt_sample_ms;
+ for (uint64_t f : feedback_vector) {
+ PacketStats packet = packet_stats_[f];
+ size_t data_sent_bytes =
+ packet.data_sent_bytes - packet.data_sent_before_last_sent_packet_bytes;
+ int64_t send_time_delta_ms =
+ packet.last_sent_packet_send_time_ms - packet.send_time_ms;
+ size_t data_acked_bytes = packet.data_acked_bytes -
+ packet.data_acked_before_last_acked_packet_bytes;
+ int64_t ack_time_delta_ms =
+ packet.ack_time_ms - packet.last_acked_packet_ack_time_ms;
+ rtc::Optional<int64_t> bandwidth_sample =
+ CalculateBandwidthSample(data_sent_bytes, send_time_delta_ms,
+ data_acked_bytes, ack_time_delta_ms);
+ if (bandwidth_sample)
+ max_bandwidth_filter_->AddBandwidthSample(*bandwidth_sample,
+ round_count_);
+ AddSampleForHighGain(); // Comment to disable bucket for high gain.
+ if (!min_rtt_sample_ms)
+ *min_rtt_sample_ms = packet.ack_time_ms - packet.send_time_ms;
+ else
+ *min_rtt_sample_ms = std::min(*min_rtt_sample_ms,
+ packet.ack_time_ms - packet.send_time_ms);
+ BWE_TEST_LOGGING_PLOT(1, "MinRtt", now_ms,
+ packet.ack_time_ms - packet.send_time_ms);
+ }
+ if (!min_rtt_sample_ms)
+ return false;
+ min_rtt_filter_->AddRttSample(*min_rtt_sample_ms, now_ms);
+ bool min_rtt_expired = min_rtt_filter_->MinRttExpired(now_ms);
+ return min_rtt_expired;
}
void BbrBweSender::EnterStartup() {
@@ -174,12 +365,13 @@ void BbrBweSender::TryUpdatingCyclePhase(int64_t now_ms) {
// If BBR was probing and it couldn't increase data inflight sufficiently in
// one min_rtt time, continue probing. BBR design doc isn't clear about this,
// but condition helps in quicker ramp-up and performs better.
- if (pacing_gain_ > 1.0 &&
- prior_in_flight_ < TargetCongestionWindow(pacing_gain_))
+ if (pacing_gain_ > 1.0 && congestion_window_->data_inflight() <
+ TargetCongestionWindow(pacing_gain_))
advance_cycle_phase = false;
// If BBR has already drained queues there is no point in continuing draining
// phase.
- if (pacing_gain_ < 1.0 && prior_in_flight_ <= TargetCongestionWindow(1))
+ if (pacing_gain_ < 1.0 &&
+ congestion_window_->data_inflight() <= TargetCongestionWindow(1))
advance_cycle_phase = true;
if (advance_cycle_phase) {
cycle_index_++;
@@ -190,8 +382,7 @@ void BbrBweSender::TryUpdatingCyclePhase(int64_t now_ms) {
}
void BbrBweSender::TryEnteringProbeRtt(int64_t now_ms) {
- if (min_rtt_filter_->min_rtt_expired(now_ms, kMinRttFilterSizeMs) &&
- mode_ != PROBE_RTT) {
+ if (min_rtt_filter_->MinRttExpired(now_ms) && mode_ != PROBE_RTT) {
mode_ = PROBE_RTT;
pacing_gain_ = 1;
probe_rtt_start_time_ms_ = now_ms;
@@ -199,9 +390,10 @@ void BbrBweSender::TryEnteringProbeRtt(int64_t now_ms) {
}
}
-// minimum_congestion_window_start_time_'s value is set to the first moment when
-// data inflight was less then kMinimumCongestionWindowBytes, we should make
-// sure that BBR has been in PROBE_RTT mode for at least one round or 200ms.
+// |minimum_congestion_window_start_time_|'s value is set to the first moment
+// when data inflight was less then
+// |CongestionWindow::kMinimumCongestionWindowBytes|, we should make sure that
+// BBR has been in PROBE_RTT mode for at least one round or 200ms.
void BbrBweSender::TryExitingProbeRtt(int64_t now_ms, int64_t round) {
if (!minimum_congestion_window_start_time_ms_) {
if (congestion_window_->data_inflight() <=
@@ -218,13 +410,74 @@ void BbrBweSender::TryExitingProbeRtt(int64_t now_ms, int64_t round) {
}
}
+void BbrBweSender::TryEnteringRecovery(bool new_round_started) {
+ // If we are already in Recovery don't try to enter.
+ if (mode_ == RECOVERY || !new_round_started || !full_bandwidth_reached_)
+ return;
+ uint64_t increased_rtt_round_counter = 0;
+ // If average RTT for past |kPastRttsFilterSize| rounds has been more than
+ // some multiplier of min_rtt_ms enter Recovery.
+ for (BbrBweSender::AverageRtt i : past_rtts_) {
+ if (i.sum_of_rtts_ms / (int64_t)i.num_samples >=
+ *min_rtt_filter_->min_rtt_ms() * kRttIncreaseThreshold)
+ increased_rtt_round_counter++;
+ }
+ if (increased_rtt_round_counter < kPastRttsFilterSize)
+ return;
+ mode_ = RECOVERY;
+ pacing_gain_ = kRecoveryPacingGain;
+ congestion_window_gain_ = kRecoveryCongestionWindowGain;
+}
+
+void BbrBweSender::TryExitingRecovery(bool new_round_started) {
+ if (mode_ != RECOVERY || !new_round_started || !full_bandwidth_reached_)
+ return;
+ // If average RTT for the past round has decreased sufficiently exit Recovery.
+ if (!past_rtts_.empty()) {
+ BbrBweSender::AverageRtt last_round_sample = past_rtts_.back();
+ if (last_round_sample.sum_of_rtts_ms / last_round_sample.num_samples <=
+ *min_rtt_filter_->min_rtt_ms() * kRttDecreaseThreshold) {
+ EnterProbeBw(clock_->TimeInMilliseconds());
+ }
+ }
+}
+
int64_t BbrBweSender::TimeUntilNextProcess() {
- return 100;
+ return 50;
}
void BbrBweSender::OnPacketsSent(const Packets& packets) {
- last_packet_sent_ =
- static_cast<const MediaPacket*>(packets.back())->sequence_number();
+ for (Packet* packet : packets) {
+ if (packet->GetPacketType() == Packet::kMedia) {
+ MediaPacket* media_packet = static_cast<MediaPacket*>(packet);
+ bytes_sent_ += media_packet->payload_size();
+ PacketStats packet_stats = PacketStats(
+ media_packet->sequence_number(), 0,
+ media_packet->sender_timestamp_ms(), 0, last_packet_ack_time_,
+ media_packet->payload_size(), 0, bytes_sent_, 0, bytes_acked_);
+ packet_stats_[media_packet->sequence_number()] = packet_stats;
+ last_packet_send_time_ = media_packet->sender_timestamp_ms();
+ last_packet_sent_sequence_number_ = media_packet->sequence_number();
+ // If this is the first packet sent for high gain phase, save data for it.
+ if (!first_packet_send_time_during_high_gain_ms_ && pacing_gain_ > 1) {
+ *first_packet_send_time_during_high_gain_ms_ = last_packet_send_time_;
+ data_sent_before_high_gain_started_bytes_ =
+ bytes_sent_ - media_packet->payload_size() / 2;
+ first_packet_seq_num_during_high_gain_ =
+ media_packet->sequence_number();
+ }
+ // This condition ensures that |last_packet_seq_num_during_high_gain_|
+ // will contain a sequence number of the last packet sent during high gain
+ // phase.
+ if (pacing_gain_ > 1) {
+ last_packet_send_time_during_high_gain_ms_ = last_packet_send_time_;
+ data_sent_before_high_gain_ended_bytes_ =
+ bytes_sent_ - media_packet->payload_size() / 2;
+ last_packet_seq_num_during_high_gain_ = media_packet->sequence_number();
+ }
+ congestion_window_->PacketSent(media_packet->payload_size());
+ }
+ }
}
void BbrBweSender::Process() {}

Powered by Google App Engine
This is Rietveld 408576698