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) {
+  // The only way for these two to 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.
+  if (packet_status_window_.find(seq_num) != packet_status_window_.end()) {

[michaelt, 2017/02/09 10:52:02]

The "else if" seams to be obsolete. Would go for:

if (packet_status_window_.find(seq_num) != packet_status_window_.end() || 
              !packet_status_window_.empty() &&
              ForwardDiff(seq_num, NewestSequenceNumber()) <= kSeqNumHalf) {
 Reset();
}

[elad.alon_webrtc.org, 2017/02/09 12:27:53]

I think it's easier to read like this, but if the consensus ends up being that
it's better to combine the two cases, because they have the same behavior, I'll
do so. What do the rest of you think?

+    Reset();
+  } else if (!packet_status_window_.empty() &&
+             ForwardDiff(seq_num, NewestSequenceNumber()) <= kSeqNumHalf) {
+    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();
+  }
+
+  const auto& ret = packet_status_window_.insert(

[michaelt, 2017/02/09 10:52:02]

1. "packet_status" would make more sene to me for a name than "ret"  
2. Using a hint here should make this more efficient. 

[elad.alon_webrtc.org, 2017/02/09 12:35:55]

Good point about the hint.

+      std::make_pair(seq_num, PacketStatus::Unacked));
+  RTC_DCHECK(ret.second);

[michaelt, 2017/02/09 10:52:05]

Seams obsolete since you checked already if the seq_num si in the map.

[elad.alon_webrtc.org, 2017/02/09 12:27:53]

I think out-of-memory would be the only way for this to happen. A quick search
through the code-base seems to indicate that we don't usually D/CHECK that
insertion was successful, so I'll indeed remove this.

+
+  if (packet_status_window_.size() == 1) {
+    ref_packet_status_ = ret.first;
+  }
 }
 
 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,
+    PacketStatus new_packet_status) {
+  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);

[michaelt, 2017/02/09 10:52:04]

Why do we UpdateMetrics before we remove the packet ?

[elad.alon_webrtc.org, 2017/02/09 12:27:53]

The order is:
1. Update the statistics. This packet might have contributed to R/PLR; now that
it's being removed, this contribution needs to be forgotten.
2. Remove the packet.

Doing it the other way around would mean having to remember the removed packet's
properties in a temporary variable.

   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:

[michaelt, 2017/02/09 10:52:03]

The default case seams useless to me, since the compiler will warn us anyway if
we did not used all cases. 

[elad.alon_webrtc.org, 2017/02/09 12:27:53]

It protects against illegal enum values, such as 3, which I consider
good-practice. But I guess the coding convention is king. Minyue, what is the
standard here in Google for such cases?

+      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