GetTransportFeedbackVector() includes unreceived packets, sorted by seq-num

webrtc/modules/congestion_controller/delay_based_bwe.cc

 /*
  *  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.
  */
 
@@ skipping 105 matching lines @@
     RTC_CHECK_GT(*window_size, 1) << "Need at least 2 points to fit a line.";
     RTC_CHECK_GT(*threshold_gain, 0) << "Threshold gain needs to be positive.";
     return true;
   }
   LOG(LS_WARNING) << "Failed to parse parameters for BweMedianSlopeFilter "
                      "experiment from field trial string. Using default.";
   *window_size = kDefaultMedianSlopeWindowSize;
   *threshold_gain = kDefaultMedianSlopeThresholdGain;
   return false;
 }
+
+class PacketFeedbackComparator {
+ public:
+  inline bool operator()(const webrtc::PacketFeedback& lhs,
+                         const webrtc::PacketFeedback& rhs) {
+    if (lhs.arrival_time_ms != rhs.arrival_time_ms)
+      return lhs.arrival_time_ms < rhs.arrival_time_ms;
+    if (lhs.send_time_ms != rhs.send_time_ms)
+      return lhs.send_time_ms < rhs.send_time_ms;
+    return lhs.sequence_number < rhs.sequence_number;
+  }
+};
 }  // namespace
 
 namespace webrtc {
 
 DelayBasedBwe::BitrateEstimator::BitrateEstimator()
     : sum_(0),
       current_win_ms_(0),
       prev_time_ms_(-1),
       bitrate_estimate_(-1.0f),
       bitrate_estimate_var_(50.0f),
@@ skipping 113 matching lines @@
   if (!in_trendline_experiment_ && !in_median_slope_experiment_) {
     LOG(LS_INFO) << "No overuse experiment enabled. Using Kalman filter.";
   }
 
   network_thread_.DetachFromThread();
 }
 
 DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(
     const std::vector<PacketFeedback>& packet_feedback_vector) {
   RTC_DCHECK(network_thread_.CalledOnValidThread());
+
+  std::vector<PacketFeedback> sorted_packet_feedback_vector;
+  SortPacketFeedbackVector(packet_feedback_vector,
+                           &sorted_packet_feedback_vector);
+
   if (!uma_recorded_) {
     RTC_HISTOGRAM_ENUMERATION(kBweTypeHistogram,
                               BweNames::kSendSideTransportSeqNum,
                               BweNames::kBweNamesMax);
     uma_recorded_ = true;
   }
   Result aggregated_result;
   bool delayed_feedback = true;
-  for (const auto& packet_feedback : packet_feedback_vector) {
+  for (const auto& packet_feedback : sorted_packet_feedback_vector) {
     if (packet_feedback.send_time_ms < 0)
       continue;
     delayed_feedback = false;
     Result result = IncomingPacketFeedback(packet_feedback);
     if (result.updated)
       aggregated_result = result;
   }
   if (delayed_feedback) {
     ++consecutive_delayed_feedbacks_;
   } else {
     consecutive_delayed_feedbacks_ = 0;
   }
   if (consecutive_delayed_feedbacks_ >= kMaxConsecutiveFailedLookups) {
-    aggregated_result =
-        OnLongFeedbackDelay(packet_feedback_vector.back().arrival_time_ms);
+    aggregated_result = OnLongFeedbackDelay(
+        sorted_packet_feedback_vector.back().arrival_time_ms);
     consecutive_delayed_feedbacks_ = 0;
   }
   return aggregated_result;
 }
 
 DelayBasedBwe::Result DelayBasedBwe::OnLongFeedbackDelay(
     int64_t arrival_time_ms) {
   // Estimate should always be valid since a start bitrate always is set in the
   // Call constructor. An alternative would be to return an empty Result here,
   // or to estimate the throughput based on the feedback we received.
@@ skipping 123 matching lines @@
                                    rtc::Optional<uint32_t> acked_bitrate_bps,
                                    uint32_t* target_bitrate_bps) {
   // TODO(terelius): RateControlInput::noise_var is deprecated and will be
   // removed. In the meantime, we set it to zero.
   const RateControlInput input(detector_.State(), acked_bitrate_bps, 0);
   rate_control_.Update(&input, now_ms);
   *target_bitrate_bps = rate_control_.UpdateBandwidthEstimate(now_ms);
   return rate_control_.ValidEstimate();
 }
 
+void DelayBasedBwe::SortPacketFeedbackVector(
+    const std::vector<PacketFeedback>& input,
+    std::vector<PacketFeedback>* output) {
+  auto pred = [](const PacketFeedback& packet_feedback) {
+    return packet_feedback.arrival_time_ms != PacketFeedback::kLost;
+  };
+  std::copy_if(input.begin(), input.end(), std::back_inserter(*output), pred);
+  std::sort(output->begin(), output->end(), PacketFeedbackComparator());

[stefan-webrtc, 2017/02/24 09:28:57]

Should we do this in-place instead and just ignore kLost packets in the loop on
line 284?

[elad.alon_webrtc.org, 2017/02/27 09:43:48]

The way I see it, we have to duplicate the input to make sure we can define it
as const, which seems like a design requirement to me (but I am open for
discussion, of course). And if we copy, we might as well not copy elements we'll
not really need, thereby also making the sort quicker. Wdyt?

[stefan-webrtc, 2017/02/28 14:54:31]

True the constness is a good point.

+}
+
 void DelayBasedBwe::OnRttUpdate(int64_t avg_rtt_ms, int64_t max_rtt_ms) {
   rate_control_.SetRtt(avg_rtt_ms);
 }
 
 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.
@@ skipping 15 matching lines @@
 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.
   rate_control_.SetMinBitrate(min_bitrate_bps);
 }
 
 int64_t DelayBasedBwe::GetProbingIntervalMs() const {
   return probing_interval_estimator_.GetIntervalMs();
 }
 }  // namespace webrtc