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

webrtc/modules/congestion_controller/delay_based_bwe.cc

Index: webrtc/modules/congestion_controller/delay_based_bwe.cc
diff --git a/webrtc/modules/congestion_controller/delay_based_bwe.cc b/webrtc/modules/congestion_controller/delay_based_bwe.cc
index f550d44e3224f7b5b3fe9d2f7f421dc262bdd16f..f9ff194eceb1dd49a500b6a6621873d0c16eac1f 100644
--- a/webrtc/modules/congestion_controller/delay_based_bwe.cc
+++ b/webrtc/modules/congestion_controller/delay_based_bwe.cc
@@ -123,6 +123,18 @@ bool ReadMedianSlopeFilterExperimentParameters(size_t* window_size,
   *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 {
@@ -256,6 +268,11 @@ DelayBasedBwe::DelayBasedBwe(RtcEventLog* event_log, Clock* clock)
 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,
@@ -264,7 +281,7 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(
   }
   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;
@@ -278,8 +295,8 @@ DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(
     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;
@@ -423,6 +440,16 @@ bool DelayBasedBwe::UpdateEstimate(int64_t arrival_time_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);
 }