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..b205517b7be93764c8780d05f524091763c8d64a 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,10 @@ 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. |
+// Number of rounds for bandwidth estimate to expire. |
+const size_t kBandwidthWindowFilterSize = kGainCycleLength + 2; |
+const int kMinimumCongestionWindow = 4000; |
philipel
2017/08/04 12:08:06
kMinimumCongestionWindow should not be defined in
gnish1
2017/08/07 10:34:28
Done.
|
+// Least amount 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; |
@@ -49,6 +53,20 @@ 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 +78,33 @@ 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), |
+ bytes_acked_(0), |
prior_in_flight_(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_(0), |
+ last_high_gain_send_time_(-1), |
+ first_high_gain_sent_before_(-1), |
+ last_high_gain_sent_before_(-1), |
+ first_high_gain_ack_time_(-1), |
+ last_high_gain_ack_time_(-1), |
+ first_high_gain_acked_before_(-1), |
+ last_high_gain_acked_before_(-1), |
+ first_high_gain_seq_num_(-1), |
+ last_high_gain_seq_num_(-1), |
+ high_gain_over_(false), |
+ packet_stats_(), |
+ past_rtts_() { |
// Initially enter Startup mode. |
EnterStartup(); |
} |
@@ -79,44 +115,130 @@ int BbrBweSender::GetFeedbackIntervalMs() const { |
return kFeedbackIntervalsMs; |
} |
+void BbrBweSender::CalculatePacingRate() { |
+ pacing_rate_ = |
+ max_bandwidth_filter_->max_bandwidth_estimate_bps() * pacing_gain_; |
+} |
+ |
+void BbrBweSender::HandleLoss(uint64_t last_acked_packet, |
philipel
2017/08/04 12:08:07
So, in the case of loss we immediately mark the lo
gnish1
2017/08/07 10:34:28
Done.
|
+ uint64_t recently_acked_packet) { |
+ // Logic specific to wrapping sequence numbers. |
+ if (!last_acked_packet) |
+ return; |
+ for (uint64_t i = last_acked_packet + 1; i < recently_acked_packet; i++) |
philipel
2017/08/04 12:08:06
Are |last_acked_packet| and |recently_acked_packet
gnish1
2017/08/07 10:34:28
Done.
|
+ congestion_window_->AckReceived(packet_stats_[i].payload_size); |
+} |
+ |
+void BbrBweSender::AddToPastRtts(int64_t rtt_sample_ms) { |
+ uint64_t last_round = 0; |
+ if (!past_rtts_.empty()) |
+ last_round = past_rtts_.rbegin()->round; |
philipel
2017/08/04 12:08:06
... = past_rtts_.back().round;
gnish1
2017/08/07 10:34:27
Done.
|
+ |
+ // Try to add the sample to the last round. |
+ if (last_round == round_count_ && !past_rtts_.empty()) { |
+ BbrBweSender::AverageRtt& last_round_sample = *(past_rtts_.rbegin()); |
philipel
2017/08/04 12:08:06
BbrBweSender::AverageRtt* = &past_rtts_.back();
W
gnish1
2017/08/07 10:34:28
Done.
|
+ last_round_sample.sum_of_rtts += rtt_sample_ms; |
+ last_round_sample.quantity++; |
+ } 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 = clock_->TimeInMilliseconds(); |
+ last_packet_ack_time_ = now; |
+ prior_in_flight_ = bytes_acked_; |
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 (const auto& f : feedback_vector) { |
philipel
2017/08/04 12:08:06
We use auto for situations where it is both obviou
gnish1
2017/08/07 10:34:28
Done.
|
+ // Completing packet information with a recently received ack. |
+ PacketStats& packet = packet_stats_[f]; |
philipel
2017/08/04 12:08:06
PacketStats*
gnish1
2017/08/07 10:34:28
Done.
|
+ bytes_acked_ += packet.payload_size; |
+ packet.data_sent = bytes_sent_; |
+ packet.send_time = last_packet_send_time_; |
+ packet.data_acked = bytes_acked_; |
+ packet.ack_time = now; |
+ // 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_high_gain_seq_num_) { |
+ first_high_gain_ack_time_ = now; |
+ first_high_gain_acked_before_ = bytes_acked_; |
+ } |
+ // If the last packet of high gain phase has been acked, high gain phase is |
+ // over. |
+ if (packet.sequence_number == last_high_gain_seq_num_) { |
+ last_high_gain_ack_time_ = now; |
+ last_high_gain_acked_before_ = bytes_acked_; |
+ 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); |
+ 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_; |
} |
} |
+ // Try to enter and exit recovery only after a round has ended. |
+ if (new_round_started && full_bandwidth_reached_) { |
+ TryEnteringRecovery(); // Comment this line to disable entering Recovery |
+ // mode. |
+ TryExitingRecovery(); |
philipel
2017/08/04 12:08:06
I think having |new_round_started| and |full_bandw
gnish1
2017/08/07 10:34:28
Done.
|
+ } |
+ bool min_rtt_expired = false; |
+ min_rtt_expired = |
+ UpdateBandwidthAndMinRtt(now, 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: |
TryExitingStartup(); |
break; |
case DRAIN: |
- TryExitingDrain(now_ms); |
+ TryExitingDrain(now); |
break; |
case PROBE_BW: |
- TryUpdatingCyclePhase(now_ms); |
+ TryUpdatingCyclePhase(now); |
break; |
case PROBE_RTT: |
- TryExitingProbeRtt(now_ms, 0); |
+ TryExitingProbeRtt(now, round_count_, min_rtt_expired); |
+ break; |
+ case RECOVERY: |
break; |
} |
- TryEnteringProbeRtt(now_ms); |
- // TODO(gnish): implement functions updating congestion window and pacing rate |
- // controllers. |
+ TryEnteringProbeRtt(now, min_rtt_expired); |
+ CalculatePacingRate(); |
+ // Make sure we don't get stuck when pacing_rate is 0, because of simulation |
+ // tool specifics. |
+ if (!pacing_rate_) |
+ pacing_rate_ = 100; |
+ BWE_TEST_LOGGING_PLOT(1, "SendRate", now, pacing_rate_ / 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 +249,78 @@ 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, |
+ int64_t time_elapsed_1, |
+ size_t data_acked, |
+ int64_t time_elapsed_2) { |
+ rtc::Optional<int64_t> bandwidth_sample; |
+ if (time_elapsed_1 > 0) |
+ *bandwidth_sample = data_sent * 8000 / time_elapsed_1; |
+ rtc::Optional<int64_t> ack_rate; |
+ if (time_elapsed_2 > 0) |
+ *ack_rate = data_acked * 8000 / time_elapsed_2; |
+ // 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 = last_high_gain_sent_before_ - first_high_gain_sent_before_; |
+ int64_t time_elapsed_1 = |
+ last_high_gain_send_time_ - *first_high_gain_send_time_; |
+ size_t data_acked = |
+ last_high_gain_acked_before_ - first_high_gain_acked_before_; |
+ int64_t time_elapsed_2 = last_high_gain_ack_time_ - first_high_gain_ack_time_; |
+ rtc::Optional<int64_t> bandwidth_sample = CalculateBandwidthSample( |
+ data_sent, time_elapsed_1, data_acked, time_elapsed_2); |
+ if (bandwidth_sample) |
+ max_bandwidth_filter_->AddBandwidthSample(*bandwidth_sample, round_count_, |
+ kBandwidthWindowFilterSize); |
+ first_high_gain_send_time_.reset(); |
+} |
+ |
+bool BbrBweSender::UpdateBandwidthAndMinRtt( |
+ int64_t now, |
philipel
2017/08/04 12:08:06
now_ms
gnish1
2017/08/07 10:34:28
Done.
|
+ const std::vector<uint64_t>& feedback_vector, |
+ int64_t bytes_acked) { |
+ rtc::Optional<int64_t> min_rtt_sample_ms; |
+ for (const auto& f : feedback_vector) { |
philipel
2017/08/04 12:08:06
for (uint64_t f: feedback_vector)
gnish1
2017/08/07 10:34:28
Done.
|
+ PacketStats packet = packet_stats_[f]; |
+ size_t data_sent = packet.data_sent - packet.data_sent_before; |
+ int64_t time_elapsed_1 = packet.send_time - packet.send_time_before; |
+ size_t data_acked = packet.data_acked - packet.data_acked_before; |
+ int64_t time_elapsed_2 = packet.ack_time - packet.ack_time_before; |
+ rtc::Optional<int64_t> bandwidth_sample = CalculateBandwidthSample( |
+ data_sent, time_elapsed_1, data_acked, time_elapsed_2); |
+ if (bandwidth_sample) |
+ max_bandwidth_filter_->AddBandwidthSample(*bandwidth_sample, round_count_, |
+ kBandwidthWindowFilterSize); |
+ AddSampleForHighGain(); // Comment to disable bucket for high gain. |
+ if (!min_rtt_sample_ms) |
+ *min_rtt_sample_ms = packet.ack_time - packet.send_time_before; |
+ else |
+ *min_rtt_sample_ms = std::min(*min_rtt_sample_ms, |
+ packet.ack_time - packet.send_time_before); |
+ AddToPastRtts(packet.ack_time - packet.send_time_before); |
+ BWE_TEST_LOGGING_PLOT(1, "MinRtt", now, |
+ packet.ack_time - packet.send_time_before); |
+ } |
+ if (!min_rtt_sample_ms) |
+ return false; |
+ bool min_rtt_expired = |
+ min_rtt_filter_->min_rtt_expired(now, kMinRttFilterSizeMs); |
+ min_rtt_filter_->add_rtt_sample(*min_rtt_sample_ms, now, min_rtt_expired); |
+ return min_rtt_expired; |
} |
void BbrBweSender::EnterStartup() { |
@@ -189,9 +381,8 @@ 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) { |
+void BbrBweSender::TryEnteringProbeRtt(int64_t now_ms, bool min_rtt_expired) { |
philipel
2017/08/04 12:08:06
This looks like a revert of the changes you made i
gnish1
2017/08/07 10:34:28
Done.
|
+ if (min_rtt_expired && mode_ != PROBE_RTT) { |
mode_ = PROBE_RTT; |
pacing_gain_ = 1; |
probe_rtt_start_time_ms_ = now_ms; |
@@ -199,13 +390,14 @@ 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 |
+// |minimum_congestion_window_start_time_|'s value is set to the first moment |
+// when data inflight was less then |kMinimumCongestionWindow|, 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) { |
+void BbrBweSender::TryExitingProbeRtt(int64_t now_ms, |
+ int64_t round, |
+ bool min_rtt_expired) { |
philipel
2017/08/04 12:08:06
Undo this change.
gnish1
2017/08/07 10:34:28
Done.
|
if (!minimum_congestion_window_start_time_ms_) { |
- if (congestion_window_->data_inflight() <= |
- CongestionWindow::kMinimumCongestionWindowBytes) { |
+ if (congestion_window_->data_inflight() <= kMinimumCongestionWindow) { |
philipel
2017/08/04 12:08:06
Undo.
gnish1
2017/08/07 10:34:28
Done.
|
*minimum_congestion_window_start_time_ms_ = now_ms; |
minimum_congestion_window_start_round_ = round; |
} |
@@ -218,13 +410,70 @@ void BbrBweSender::TryExitingProbeRtt(int64_t now_ms, int64_t round) { |
} |
} |
+void BbrBweSender::TryEnteringRecovery() { |
+ // If we are already in Recovery don't try to enter. |
+ if (mode_ == RECOVERY) |
+ 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 (const auto i : past_rtts_) { |
philipel
2017/08/04 12:08:06
Don't use auto.
gnish1
2017/08/07 10:34:28
Done.
|
+ if (i.sum_of_rtts / (int64_t)i.quantity >= |
+ *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() { |
+ if (mode_ != RECOVERY) |
+ return; |
+ // If average rtt for the past round has decreased sufficiently exit Recovery. |
+ if (!past_rtts_.empty()) { |
+ auto last_round_sample = past_rtts_.rbegin(); |
+ if (last_round_sample->sum_of_rtts / last_round_sample->quantity <= |
+ *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_high_gain_send_time_ && pacing_gain_ > 1) { |
+ *first_high_gain_send_time_ = last_packet_send_time_; |
+ first_high_gain_sent_before_ = bytes_sent_; |
+ first_high_gain_seq_num_ = media_packet->sequence_number(); |
+ } |
+ // This condition ensures that |last_high_gain_seq_num_| will contain a |
+ // sequence number of the last packet sent during high gain phase. |
+ if (pacing_gain_ > 1) { |
+ last_high_gain_send_time_ = last_packet_send_time_; |
+ last_high_gain_sent_before_ = bytes_sent_; |
+ last_high_gain_seq_num_ = media_packet->sequence_number(); |
+ } |
+ congestion_window_->PacketSent(media_packet->payload_size()); |
+ } |
+ } |
} |
void BbrBweSender::Process() {} |