Almost full implementation of BBR's core.

webrtc/modules/remote_bitrate_estimator/test/estimators/bbr.cc

 /*
  *  Copyright (c) 2017 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/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"
 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/min_rtt_filter.h"
 
 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;
 // BBR uses this value to drain queues created during STARTUP in one round trip
 // time.
 const float kDrainGain = 1 / kHighGain;
 // kStartupGrowthTarget and kMaxRoundsWithoutGrowth are chosen from
 // experiments, according to the design document.
 const float kStartupGrowthTarget = 1.25f;
 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 this file.

[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;
 // Gain value for congestion window for assuming that network has no queues.
 const float kTargetCongestionWindowGain = 1;
 // Gain value for congestion window in PROBE_BW mode. In theory it should be
 // equal to 1, but in practice because of delayed acks and the way networks
 // 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)
     : BweSender(0),
       clock_(clock),
       mode_(STARTUP),
       max_bandwidth_filter_(new MaxBandwidthFilter()),
       min_rtt_filter_(new MinRttFilter()),
       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();
 }
 
 BbrBweSender::~BbrBweSender() {}
 
 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 lost packet as acked? Please add
a comment about that.

[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| wrapping numbers, in that
case this won't work (if last is 65530 and recently is 0 for example).

You should use webrtc/modules/sequence_numer_util.h to handle wrapping numbers.

[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();

We only use const references, if you need to change the value make it a pointer.

[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 obvious which type it is and the
type is long to type, in this case I think it should be:
for (uint64_t f : feedback_vector) {

[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_bandwidth_reached| as parameters to
TryExitRecovery would be cleaner since you can move this to the switch statement
below.

[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) {
   size_t target_congestion_window =
       congestion_window_->GetTargetCongestionWindow(
           max_bandwidth_filter_->max_bandwidth_estimate_bps(),
           min_rtt_filter_->min_rtt_ms(), 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() {
   mode_ = STARTUP;
   pacing_gain_ = kHighGain;
   congestion_window_gain_ = kHighGain;
 }
 
 void BbrBweSender::TryExitingStartup() {
   if (full_bandwidth_reached_) {
@@ skipping 40 matching lines @@
   if (pacing_gain_ < 1.0 && prior_in_flight_ <= TargetCongestionWindow(1))
     advance_cycle_phase = true;
   if (advance_cycle_phase) {
     cycle_index_++;
     cycle_index_ %= kGainCycleLength;
     pacing_gain_ = kPacingGain[cycle_index_];
     cycle_start_time_ms_ = 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 in your last CL. Undo this
change.

[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;
     minimum_congestion_window_start_time_ms_.reset();
   }
 }
 
-// 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;
     }
   } else {
     if (now_ms - *minimum_congestion_window_start_time_ms_ >=
             kProbeRttDurationMs &&
         round - minimum_congestion_window_start_round_ >=
             kProbeRttDurationRounds)
       EnterProbeBw(now_ms);
   }
 }
 
+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() {}
 
 BbrBweReceiver::BbrBweReceiver(int flow_id)
     : BweReceiver(flow_id, kReceivingRateTimeWindowMs), clock_(0) {}
 
 BbrBweReceiver::~BbrBweReceiver() {}
 
 void BbrBweReceiver::ReceivePacket(int64_t arrival_time_ms,
                                    const MediaPacket& media_packet) {}
 
 FeedbackPacket* BbrBweReceiver::GetFeedback(int64_t now_ms) {
   return nullptr;
 }
 }  // namespace bwe
 }  // namespace testing
 }  // namespace webrtc