Packet Loss Tracker - Stream Separation

webrtc/voice_engine/transport_feedback_packet_loss_tracker.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/voice_engine/transport_feedback_packet_loss_tracker.h"
 
 #include <limits>
 #include <utility>
 
 #include "webrtc/base/checks.h"
 #include "webrtc/base/mod_ops.h"
 #include "webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.h"
 
 namespace {
 constexpr uint16_t kSeqNumHalf = 0x8000u;
-constexpr uint16_t kSeqNumQuarter = kSeqNumHalf / 2;
-constexpr size_t kMaxConsecutiveOldReports = 4;
-
 void UpdateCounter(size_t* counter, bool increment) {
   if (increment) {
     RTC_DCHECK_LT(*counter, std::numeric_limits<std::size_t>::max());
     ++(*counter);
   } else {
     RTC_DCHECK_GT(*counter, 0);
     --(*counter);
   }
 }
 
 }  // namespace
 
 namespace webrtc {
 
 TransportFeedbackPacketLossTracker::TransportFeedbackPacketLossTracker(
-    size_t max_window_size,
-    size_t plr_min_num_packets,
-    size_t rplr_min_num_pairs)
-    : max_window_size_(max_window_size),
+    size_t max_acked_packets,
+    size_t plr_min_num_acked_packets,
+    size_t rplr_min_num_acked_pairs)
+    : max_acked_packets_(max_acked_packets),
       ref_packet_status_(packet_status_window_.begin()),
-      plr_state_(plr_min_num_packets),
-      rplr_state_(rplr_min_num_pairs) {
-  RTC_DCHECK_GT(plr_min_num_packets, 0);
-  RTC_DCHECK_GE(max_window_size, plr_min_num_packets);
-  RTC_DCHECK_LE(max_window_size, kSeqNumHalf);
-  RTC_DCHECK_GT(rplr_min_num_pairs, 0);
-  RTC_DCHECK_GT(max_window_size, rplr_min_num_pairs);
+      plr_state_(plr_min_num_acked_packets),
+      rplr_state_(rplr_min_num_acked_pairs) {
+  RTC_DCHECK_GT(plr_min_num_acked_packets, 0);
+  RTC_DCHECK_GE(max_acked_packets, plr_min_num_acked_packets);
+  RTC_DCHECK_LE(max_acked_packets, kSeqNumHalf);
+  RTC_DCHECK_GT(rplr_min_num_acked_pairs, 0);
+  RTC_DCHECK_GT(max_acked_packets, rplr_min_num_acked_pairs);
   Reset();

[michaelt, 2017/02/27 12:44:21]

Calling a function called "Reset" in the ctor sounds strange to me.
To which state will the class be set ?
So we may rename the function to "SetInitState" or "SetZeroState" .. or
something else :)

[elad.alon_webrtc.org, 2017/02/27 13:18:05]

You voice legitimate concerns which were discussed in preceding CLs. The
conclusion was to keep Reset() here, but get rid of it for plr_state_ and
rplr_state_ (which doesn't really work that well without a std::unique_ptr, so
we've let that go for now; I can refer you to the previous discussion of this if
you'd like).

Minyue, I assume this is still your preference? I don't mind changing otherwise,
but my two cents are that Reset() is clear enough. Please note that Reset() is
also used from places except the ctor, which is why it makes sense to have a
function for it.

[michaelt, 2017/02/27 15:46:18]

Hmm I think i would go for the std::unique_ptr solution here. 

[elad.alon_webrtc.org, 2017/02/27 15:53:32]

That would require the tracker informing its owner that it needs to be replaced
by a new instance, which I think would be bad design. Or is this comment
actually about |plr_state_| and |rplr_state_|, but not about the object for
which this is the ctor?

[michaelt, 2017/02/27 16:04:31]

:) no not for the tracker :) 
For plr and rplr states.
Then add acked_packets_ and ref_packet_status_ to the ctor of the tracker and
remove the reset form the ctor.

(sorry the last comment was quite misleading)

[elad.alon_webrtc.org, 2017/02/27 16:29:19]

It's possible for the plr_state_ and rplr_state_, but I think the associated
overhead makes it undesirable. It's only rarely that the objects are reset
anytime besides in the ctor (we expect this to never happen in ~99.9% of the
calls), and the pointer would mean lesser efficiency whenever accessed (100% of
calls). Let's see what other people think?

[minyue-webrtc, 2017/03/03 14:14:31]

Hi, I hoped to get rid of Reset() everywhere, but agreed that we could have it
everywhere like this. But I am fine if we try to remove all Reset() in any
separate CL.

 }
 
 void TransportFeedbackPacketLossTracker::Reset() {
+  acked_packets_ = 0;
   plr_state_.Reset();
   rplr_state_.Reset();
-  num_consecutive_old_reports_ = 0;
   packet_status_window_.clear();
   ref_packet_status_ = packet_status_window_.begin();
 }
 
 uint16_t TransportFeedbackPacketLossTracker::ReferenceSequenceNumber() const {
   RTC_DCHECK(!packet_status_window_.empty());
   return ref_packet_status_->first;
 }
 
-bool TransportFeedbackPacketLossTracker::IsOldSequenceNumber(
-    uint16_t seq_num) const {
-  if (packet_status_window_.empty()) {
-    return false;
+uint16_t TransportFeedbackPacketLossTracker::NewestSequenceNumber() const {
+  RTC_DCHECK(!packet_status_window_.empty());
+  return PreviousPacketStatus(packet_status_window_.end())->first;
+}
+
+void TransportFeedbackPacketLossTracker::OnPacketAdded(uint16_t seq_num) {
+  if (packet_status_window_.find(seq_num) != packet_status_window_.end() ||
+      (!packet_status_window_.empty() &&
+       ForwardDiff(seq_num, NewestSequenceNumber()) <= kSeqNumHalf)) {
+    // The only way for these two to happen is when the stream lies dormant for
+    // long enough for the sequence numbers to wrap. Everything in the window in
+    // such a case would be too old to use.
+    Reset();
   }
-  const uint16_t diff = ForwardDiff(ReferenceSequenceNumber(), seq_num);
-  return diff >= 3 * kSeqNumQuarter;
+
+  // Shift older packets out of window.
+  while (!packet_status_window_.empty() &&
+         ForwardDiff(ref_packet_status_->first, seq_num) >= kSeqNumHalf) {
+    RemoveOldestPacketStatus();
+  }
+
+  packet_status_window_.insert(packet_status_window_.end(),
+                               std::make_pair(seq_num, PacketStatus::Unacked));
+
+  if (packet_status_window_.size() == 1) {
+    ref_packet_status_ = packet_status_window_.cbegin();
+  }
 }
 
 void TransportFeedbackPacketLossTracker::OnReceivedTransportFeedback(
     const rtcp::TransportFeedback& feedback) {
   const auto& fb_vector = feedback.GetStatusVector();
   const uint16_t base_seq_num = feedback.GetBaseSequence();
 
-  if (IsOldSequenceNumber(base_seq_num)) {
-    ++num_consecutive_old_reports_;
-    if (num_consecutive_old_reports_ <= kMaxConsecutiveOldReports) {
-      // If the number consecutive old reports have not exceed a threshold, we
-      // consider this packet as a late arrival. We could consider adding it to
-      // |packet_status_window_|, but in current implementation, we simply
-      // ignore it.
-      return;
-    }
-    // If we see several consecutive older reports, we assume that we've not
-    // received reports for an exceedingly long time, and do a reset.
-    Reset();
-    RTC_DCHECK(!IsOldSequenceNumber(base_seq_num));
-  } else {
-    num_consecutive_old_reports_ = 0;
-  }
-
   uint16_t seq_num = base_seq_num;
   for (size_t i = 0; i < fb_vector.size(); ++i, ++seq_num) {
-    // Remove the oldest feedbacks so that the distance between the oldest and
-    // the packet to be added does not exceed or equal to half of total sequence
-    // numbers.
-    while (!packet_status_window_.empty() &&
-           ForwardDiff(ReferenceSequenceNumber(), seq_num) >= kSeqNumHalf) {
-      RemoveOldestPacketStatus();
-    }
+    const auto& it = packet_status_window_.find(seq_num);
 
-    const bool received =
-        fb_vector[i] !=
-        webrtc::rtcp::TransportFeedback::StatusSymbol::kNotReceived;
-    InsertPacketStatus(seq_num, received);
-
-    while (packet_status_window_.size() > max_window_size_) {
-      // Make sure that the window holds at most |max_window_size_| items.
-      RemoveOldestPacketStatus();
+    // Packets which aren't at least marked as unacked either do not belong to
+    // this media stream, or have been shifted out of window.
+    if (it != packet_status_window_.end()) {
+      const bool received = fb_vector[i] !=
+          webrtc::rtcp::TransportFeedback::StatusSymbol::kNotReceived;
+      RecordFeedback(it, received);
     }
   }
 }
 
 rtc::Optional<float>
 TransportFeedbackPacketLossTracker::GetPacketLossRate() const {
   return plr_state_.GetMetric();
 }
 
 rtc::Optional<float>
 TransportFeedbackPacketLossTracker::GetRecoverablePacketLossRate() const {
   return rplr_state_.GetMetric();
 }
 
-void TransportFeedbackPacketLossTracker::InsertPacketStatus(uint16_t seq_num,
-                                                            bool received) {
-  const auto& ret =
-      packet_status_window_.insert(std::make_pair(seq_num, received));
-  if (!ret.second) {
-    if (!ret.first->second && received) {
+void TransportFeedbackPacketLossTracker::RecordFeedback(
+    PacketStatusMap::iterator it,
+    bool received) {
+  if (it->second != PacketStatus::Unacked) {
+    // Normally, packets are sent (inserted into window as "unacked"), then we
+    // receive one feedback for them.
+    // But it is possible that a packet would receive two feedbacks. Then:
+    if (it->second == PacketStatus::Lost && received) {
       // If older status said that the packet was lost but newer one says it
       // is received, we take the newer one.
-      UpdateMetrics(ret.first, false);
-      ret.first->second = received;
+      UpdateMetrics(it, false);
+      it->second = PacketStatus::Unacked;  // For clarity; overwritten shortly.
     } else {
       // If the value is unchanged or if older status said that the packet was
       // received but the newer one says it is lost, we ignore it.
+      // The standard allows for previously-reported packets to carry
+      // no report when the reports overlap, which also looks like the
+      // packet is being reported as lost.
       return;
     }
   }
-  UpdateMetrics(ret.first, true);
-  if (packet_status_window_.size() == 1)
-    ref_packet_status_ = ret.first;
+
+  // Change from UNACKED to RECEIVED/LOST.
+  it->second = received ? PacketStatus::Received : PacketStatus::Lost;
+  UpdateMetrics(it, true);
+
+  // Remove packets from the beginning of the window until maximum-acked
+  // is observed again. Note that multiple sent-but-unacked packets might
+  // be removed before we reach the first acked (whether as received or as
+  // lost) packet.
+  while (acked_packets_ > max_acked_packets_)
+    RemoveOldestPacketStatus();
 }
 
 void TransportFeedbackPacketLossTracker::RemoveOldestPacketStatus() {
   UpdateMetrics(ref_packet_status_, false);
   const auto it = ref_packet_status_;
   ref_packet_status_ = NextPacketStatus(it);
   packet_status_window_.erase(it);
 }
 
 void TransportFeedbackPacketLossTracker::UpdateMetrics(
-    PacketStatusIterator it,
+    ConstPacketStatusIterator it,
     bool apply /* false = undo */) {
   RTC_DCHECK(it != packet_status_window_.end());
+  // Metrics are dependent on feedbacks from the other side. We don't want
+  // to update the metrics each time a packet is sent, except for the case
+  // when it shifts old sent-but-unacked-packets out of window.
+  RTC_DCHECK(!apply || it->second != PacketStatus::Unacked);
+
+  if (it->second != PacketStatus::Unacked) {
+    UpdateCounter(&acked_packets_, apply);
+  }
+
   UpdatePlr(it, apply);
   UpdateRplr(it, apply);
 }
 
 void TransportFeedbackPacketLossTracker::UpdatePlr(

[michaelt, 2017/02/27 12:44:21]

Would be nice to move this function to PlrState.

[elad.alon_webrtc.org, 2017/02/27 13:18:05]

I agree in principle. Let's keep the discussion around UpdateRplr(), which is
the problematic case, as you've noticed, and then stay symmetric - move either
both or neither.

-    PacketStatusIterator it,
+    ConstPacketStatusIterator it,
     bool apply /* false = undo */) {
-  // Record or undo reception status of currently handled packet.
-  if (it->second) {
-    UpdateCounter(&plr_state_.num_received_packets_, apply);
-  } else {
-    UpdateCounter(&plr_state_.num_lost_packets_, apply);
+  switch (it->second) {
+    case PacketStatus::Unacked:
+      return;
+    case PacketStatus::Received:
+      UpdateCounter(&plr_state_.num_received_packets_, apply);
+      break;
+    case PacketStatus::Lost:
+      UpdateCounter(&plr_state_.num_lost_packets_, apply);
+      break;
+    default:

[michaelt, 2017/02/27 12:44:21]

A question to all:
In my opinion its not necessary to check the default case of a enum class.
What do you think about this ?

[elad.alon_webrtc.org, 2017/02/27 13:18:05]

+1 question
(I think checking that is generally safer, but if the rest of the codebase
considers this overkill, there's no need for me to diverge from convention in
this case, which does not involve potential input from other modules, etc.,
which would have created a stronger need for extra checks.)

[minyue-webrtc, 2017/03/03 14:14:31]

Agree. compiling warnings should be enough. Please remove, unless someone knows
a reason to keep it.

[elad.alon_webrtc.org, 2017/03/03 14:54:22]

Discussed this with Minyue offline, and he'd like to keep the defensive
approach. There are two ways this could be triggered:
1. Receive an unsanitized value from outside (cast to enum of something from
network/file/user).
2. Memory corruption in another module ends up passing us a bad value, and we
fail to catch it.

+      RTC_NOTREACHED();
   }
 }
 
 void TransportFeedbackPacketLossTracker::UpdateRplr(
-    PacketStatusIterator it,
+    ConstPacketStatusIterator it,

[michaelt, 2017/02/27 12:44:21]

Would be nice to move this function to RplrState.
We could pass PreviousPacketStatus and NextPacketStatus to make to function not
dependent on TransportFeedbackPacketLossTracker.

[elad.alon_webrtc.org, 2017/02/27 13:18:05]

As you've noticed, this is the problematic case. We want to minimize the
struct's visibility into the data-structure which it is tracking
(SentPacketStatusMap). If a previous/next always existed, we could just give
both statuses to the function, and that would be it. Because the existence of
previous/next is not guaranteed, we need to give an iterator, and that exposes
too much, I feel. There are ways around - rtc::Optional, pointer, etc. To me
they seem overkill, but I'm open to discussion. Do you have a suggested
solution? Off the top of my head, rtc::Optional seems the cleanest, but it also
means relative inefficiency.

[michaelt, 2017/02/27 15:46:18]

I think i would go for the "rtc::Optional" solution. 

[elad.alon_webrtc.org, 2017/02/27 15:53:32]

Okay. I'll wait for feedback from Erik and/or Stefan before implementing.

[minyue-webrtc, 2017/03/03 14:14:31]

I would also like to make PlrState and RplrState expose fewer accessibility.
Putting these into them and make their data members private will be nice. But
then they should become class rather than struct.


https://engdoc.corp.google.com/eng/doc/devguide/cpp/styleguide.shtml?cl=head#...

May do it in a separate CL.

[minyue-webrtc, 2017/03/03 14:50:01]

That links is not publicly assessible, see this instead.
https://google.github.io/styleguide/cppguide.html#Structs_vs._Classes

[elad.alon_webrtc.org, 2017/03/03 14:54:22]

So no action for now?

     bool apply /* false = undo */) {
-  // Previous packet and current packet might compose a known pair.
-  // If so, the RPLR state needs to be updated accordingly.
+  if (it->second == PacketStatus::Unacked) {
+    // Unacked packets cannot compose a pair.
+    return;
+  }
+
+  // Previous packet and current packet might compose a pair.
   if (it != ref_packet_status_) {
     const auto& prev = PreviousPacketStatus(it);
-    if (prev->first == static_cast<uint16_t>(it->first - 1)) {
-      UpdateCounter(&rplr_state_.num_known_pairs_, apply);
-      if (!prev->second && it->second) {
+    if (prev->second != PacketStatus::Unacked) {
+      UpdateCounter(&rplr_state_.num_acked_pairs_, apply);
+      if (prev->second == PacketStatus::Lost &&
+          it->second == PacketStatus::Received) {
         UpdateCounter(
             &rplr_state_.num_recoverable_losses_, apply);
       }
     }
   }
 
   // Current packet and next packet might compose a pair.
-  // If so, the RPLR state needs to be updated accordingly.
   const auto& next = NextPacketStatus(it);
   if (next != packet_status_window_.end() &&
-      next->first == static_cast<uint16_t>(it->first + 1)) {
-    UpdateCounter(&rplr_state_.num_known_pairs_, apply);
-    if (!it->second && next->second) {
+      next->second != PacketStatus::Unacked) {
+    UpdateCounter(&rplr_state_.num_acked_pairs_, apply);
+    if (it->second == PacketStatus::Lost &&
+        next->second == PacketStatus::Received) {
       UpdateCounter(&rplr_state_.num_recoverable_losses_, apply);
     }
   }
 }
 
-TransportFeedbackPacketLossTracker::PacketStatusIterator
+TransportFeedbackPacketLossTracker::ConstPacketStatusIterator
 TransportFeedbackPacketLossTracker::PreviousPacketStatus(
-    PacketStatusIterator it) {
+    ConstPacketStatusIterator it) const {
   RTC_DCHECK(it != ref_packet_status_);
   if (it == packet_status_window_.end()) {
     // This is to make PreviousPacketStatus(packet_status_window_.end()) point
     // to the last element.
     it = ref_packet_status_;
   }
 
   if (it == packet_status_window_.begin()) {
     // Due to the circular nature of sequence numbers, we let the iterator
     // go to the end.
     it = packet_status_window_.end();
   }
   return --it;
 }
 
-TransportFeedbackPacketLossTracker::PacketStatusIterator
-TransportFeedbackPacketLossTracker::NextPacketStatus(PacketStatusIterator it) {
+TransportFeedbackPacketLossTracker::ConstPacketStatusIterator
+TransportFeedbackPacketLossTracker::NextPacketStatus(
+    ConstPacketStatusIterator it) const {
   RTC_DCHECK(it != packet_status_window_.end());
   ++it;
   if (it == packet_status_window_.end()) {
     // Due to the circular nature of sequence numbers, we let the iterator
     // goes back to the beginning.
     it = packet_status_window_.begin();
   }
   if (it == ref_packet_status_) {
     // This is to make the NextPacketStatus of the last element to return the
     // beyond-the-end iterator.
     it = packet_status_window_.end();
   }
   return it;
 }
 
 // TODO(minyue): This method checks the states of this class do not misbehave.
 // The method is used both in unit tests and a fuzzer test. The fuzzer test
 // is present to help finding potential errors. Once the fuzzer test shows no
 // error after long period, we can remove the fuzzer test, and move this method
 // to unit test.
 void TransportFeedbackPacketLossTracker::Validate() const {  // Testing only!

[michaelt, 2017/02/27 12:44:21]

Do we have any concrete conditions when we will remove this function ?

[elad.alon_webrtc.org, 2017/02/27 13:18:05]

The fuzzer relies heavily on this, so I don't see us removing this function
unless we remove the fuzzer. Also, the UTs make use of this. I'd be happy to
keep this in the code.

[michaelt, 2017/02/27 15:46:18]

I just asked because minyue wrote in the comment "Once the fuzzer test shows no
error after long period, we can remove the fuzzer test, and move this method to
unit test." which seams to be quite a open criteria :).
I may have to clarify this with him. 

[elad.alon_webrtc.org, 2017/02/27 15:53:32]

Ah. Well, if he wants to remove this, of course. :-) Personally, I'd vote for
keeping this, but I can see the merit of either decision.

[minyue-webrtc, 2017/03/03 14:14:31]

Let's keep it until the feature has been fully landed in products, and no
algorithmic changes are ahead of us.

-  RTC_CHECK_LE(packet_status_window_.size(), max_window_size_);
-  RTC_CHECK_EQ(packet_status_window_.size(),
-               plr_state_.num_lost_packets_ + plr_state_.num_received_packets_);
+  RTC_CHECK_EQ(plr_state_.num_received_packets_ + plr_state_.num_lost_packets_,
+               acked_packets_);
+  RTC_CHECK_LE(acked_packets_, packet_status_window_.size());
+  RTC_CHECK_LE(acked_packets_, max_acked_packets_);
   RTC_CHECK_LE(rplr_state_.num_recoverable_losses_,
-               rplr_state_.num_known_pairs_);
-  RTC_CHECK_LE(rplr_state_.num_known_pairs_,
-               packet_status_window_.size() - 1);
+               rplr_state_.num_acked_pairs_);
+  RTC_CHECK_LE(rplr_state_.num_acked_pairs_, acked_packets_ - 1);
 
+  size_t unacked_packets = 0;
   size_t received_packets = 0;
   size_t lost_packets = 0;
-  size_t known_status_pairs = 0;
+  size_t acked_pairs = 0;
   size_t recoverable_losses = 0;
 
   if (!packet_status_window_.empty()) {
-    PacketStatusIterator it = ref_packet_status_;
+    ConstPacketStatusIterator it = ref_packet_status_;
     do {
-      if (it->second) {
-        ++received_packets;
-      } else {
-        ++lost_packets;
+      switch (it->second) {
+        case PacketStatus::Unacked:
+          ++unacked_packets;
+          break;
+        case PacketStatus::Received:
+          ++received_packets;
+          break;
+        case PacketStatus::Lost:
+          ++lost_packets;
+          break;
+        default:
+          RTC_NOTREACHED();
       }
 
       auto next = std::next(it);
       if (next == packet_status_window_.end())
         next = packet_status_window_.begin();
 
       if (next != ref_packet_status_ &&
-          next->first == static_cast<uint16_t>(it->first + 1)) {
-        ++known_status_pairs;
-        if (!it->second && next->second)
+          it->second != PacketStatus::Unacked &&
+          next->second != PacketStatus::Unacked) {
+        ++acked_pairs;
+        if (it->second == PacketStatus::Lost &&
+            next->second == PacketStatus::Received)
           ++recoverable_losses;
       }
 
       RTC_CHECK_LT(ForwardDiff(ReferenceSequenceNumber(), it->first),
                    kSeqNumHalf);
 
       it = next;
     } while (it != ref_packet_status_);
   }
 
   RTC_CHECK_EQ(plr_state_.num_received_packets_, received_packets);
   RTC_CHECK_EQ(plr_state_.num_lost_packets_, lost_packets);
-  RTC_CHECK_EQ(rplr_state_.num_known_pairs_, known_status_pairs);
+  RTC_CHECK_EQ(packet_status_window_.size(),
+               unacked_packets + received_packets + lost_packets);
+  RTC_CHECK_EQ(rplr_state_.num_acked_pairs_, acked_pairs);
   RTC_CHECK_EQ(rplr_state_.num_recoverable_losses_, recoverable_losses);
 }
 
 rtc::Optional<float>
 TransportFeedbackPacketLossTracker::PlrState::GetMetric() const {
   const size_t total = num_lost_packets_ + num_received_packets_;
-  if (total < min_num_packets_) {
+  if (total < min_num_acked_packets_) {
     return rtc::Optional<float>();
   } else {
     return rtc::Optional<float>(
         static_cast<float>(num_lost_packets_) / total);
   }
 }
 
 rtc::Optional<float>
 TransportFeedbackPacketLossTracker::RplrState::GetMetric() const {
-  if (num_known_pairs_ < min_num_pairs_) {
+  if (num_acked_pairs_ < min_num_acked_pairs_) {
     return rtc::Optional<float>();
   } else {
     return rtc::Optional<float>(
-        static_cast<float>(num_recoverable_losses_) / num_known_pairs_);
+        static_cast<float>(num_recoverable_losses_) / num_acked_pairs_);
   }
 }
 
 }  // namespace webrtc