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();
 }
 
 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) {

[minyue-webrtc, 2017/02/14 16:46:59]

The name should be OnSentPacket or something like that IMO

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

This is triggered from the pre-existing TransportFeedbackAdapter::AddPacket (see
subsequent CL), which is why I prefer this name.

[minyue-webrtc, 2017/02/16 09:51:44]

Should it hook to OnSentPacket instead: see

https://cs.chromium.org/chromium/src/third_party/webrtc/modules/congestion_co...

[elad.alon_webrtc.org, 2017/02/16 15:51:40]

That one seems to be called after the packet is sent, which creates a race with
the feedback from the other side. It's a race we're very unlikely to lose, but
it's still a race.

[minyue-webrtc, 2017/02/17 11:09:14]

I am not seeing this as a problem. Please refer to my corresponding comment in
the follow-up cl.

[elad.alon_webrtc.org, 2017/02/17 12:24:42]

(Replied there.)

[minyue-webrtc, 2017/02/20 12:49:06]

Per offline discussion, I think AddPacket is the right API to hook to now, then
it is fine to use OnPacketAdded here.

+  // The only way for these two to is when the stream lies dormant for long

[minyue-webrtc, 2017/02/14 16:46:59]

.. to ?? is ...

and looks like that this comment should be placed inside if

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

Missing "happen"; thanks for catching.

+  // enough for the sequence numbers to wrap. Everything in the window in
+  // such a case would be too old to use.
+  if (packet_status_window_.find(seq_num) != packet_status_window_.end()) {
+    Reset();
+  } else if (!packet_status_window_.empty() &&
+             ForwardDiff(seq_num, NewestSequenceNumber()) <= kSeqNumHalf) {

[minyue-webrtc, 2017/02/14 16:46:59]

how can this happen?

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

DTX, for instance. Or anything else that might cause the stream to not produce
packets for a long time, while other streams do.

+    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] !=
+    // 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())
+      continue;
+
+    const bool lost = fb_vector[i] ==
         webrtc::rtcp::TransportFeedback::StatusSymbol::kNotReceived;
-    InsertPacketStatus(seq_num, received);
+    const PacketStatus new_packet_status =
+        lost ? PacketStatus::Lost : PacketStatus::Received;
 
-    while (packet_status_window_.size() > max_window_size_) {
-      // Make sure that the window holds at most |max_window_size_| items.
-      RemoveOldestPacketStatus();
-    }
+    RecordPacketStatus(it, new_packet_status);
   }
 }
 
 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::RecordPacketStatus(
+    PacketStatusIterator it,

[minyue-webrtc, 2017/02/14 16:46:59]

if we make "it" into seq_num instead, we may avoid "PacketStatusIterator"

Then this function can do

1. find(seq_num)
2. if (new is any of the acks && was not found) { return }
3. what we have here already
  

[elad.alon_webrtc.org, 2017/02/15 16:47:36]

I feel that calling RecordPacketStatus() when it might have no effect is
confusing. I think it's clearer like this. Wdyt?

[minyue-webrtc, 2017/02/16 09:51:44]

I feel typedef a non-const iterator just for this function is not necessary. I'd
like avoiding iterator, since we cannot guarantee that iterator is always valid.

If you ask me about ConstPacketStatusIterator, yes, it is good to avoid it too,
but I did not find a way that is as efficient.

[elad.alon_webrtc.org, 2017/02/16 15:51:40]

I feel like RecordPacketStatus() makes the code clearer, so I've kept it. I did
get rid of the typedef for the non-const iterator. I'll keep the
ConstPacketStatusIterator's new name, because I feel that it's clearer. But
frankly, it only saves a couple of chars, so I'd like to get rid of it
completely, too. Wdyt?

[minyue-webrtc, 2017/02/17 11:09:14]

ConstPacketStatusIterator was introduced to avoid duplication, it does appear a
lot more often.

[elad.alon_webrtc.org, 2017/02/17 12:24:42]

Do you want the name to be reverted to PacketStatusIterator?

[minyue-webrtc, 2017/02/20 12:49:06]

No ConstPacketStatusIterator is fine

+    PacketStatus new_packet_status) {

[minyue-webrtc, 2017/02/17 11:09:14]

I see another issue. RecordPacketStatus sounds more generic than its name.
Because it is called only for feedback handling but it takes PacketStatus as
input, which can be UNACKED. Therefore one may think of either
1) change the scope by making it
   RecordFeedback(PacketStatusIterator it, bool received)

2) move it entirely to OnReceivedTransportFeedback() if it will not make
OnReceivedTransportFeedback() too lengthy

[elad.alon_webrtc.org, 2017/02/17 12:24:42]

I'll go with #1.

[elad.alon_webrtc.org, 2017/02/17 12:27:03]

By the way, I find the new code to be slightly less clear inside the function,
because we now have (A && B) where A is a comparison of PacketStatus and B is a
boolean. Before it was clearer, imho, that two successive packets were being
examined. I'd be happy to revert this one change if you also feel like that.

[minyue-webrtc, 2017/02/20 12:49:06]

I like the boolean ssince it is more important for the function signature to be
clearer.

+  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 &&
+        new_packet_status == PacketStatus::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 = new_packet_status;
+  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(
-    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:
+      RTC_NOTREACHED();
   }
 }
 
 void TransportFeedbackPacketLossTracker::UpdateRplr(
-    PacketStatusIterator it,
+    ConstPacketStatusIterator it,
     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!
-  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