R/PLR calculation - time-based window

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.
  */
 
@@ skipping 10 matching lines @@
 constexpr uint16_t kSeqNumHalf = 0x8000u;
 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_acked_packets,
+    int64_t max_window_size_ms,
     size_t plr_min_num_acked_packets,
     size_t rplr_min_num_acked_pairs)
-    : max_acked_packets_(max_acked_packets),
+    : max_window_size_ms_(max_window_size_ms),
       ref_packet_status_(packet_status_window_.begin()),
       plr_state_(plr_min_num_acked_packets),
       rplr_state_(rplr_min_num_acked_pairs) {
+  RTC_DCHECK_GT(max_window_size_ms, 0);
   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();
   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;
 }
 
 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) {
+void TransportFeedbackPacketLossTracker::OnPacketAdded(uint16_t seq_num,
+                                                       int64_t send_time_ms) {
+  // Sanity - time can't flow backwards.
+  if (packet_status_window_.size() > 0) {

[michaelt, 2017/03/07 09:15:26]

Can you move the if into the RTC_DCHECK so we will not have a empty if in
release mode ?

[elad.alon_webrtc.org, 2017/03/07 11:55:18]

That would require RTC_DCHECK(x || y), which I hope the other reviewers would be
fine with. Me, I'm also for it.

[minyue-webrtc, 2017/03/07 16:47:05]

yes

+    RTC_DCHECK_GE(send_time_ms,
+                  PreviousPacketStatus(
+                      packet_status_window_.end())->second.send_time_ms);
+  }
+
   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();
   }
 
-  // Shift older packets out of window.
+  // Maintain a window where the newest sequence number is at most 0x7fff away
+  // from the oldest, so that would could still distinguish old/new.
   while (!packet_status_window_.empty() &&
          ForwardDiff(ref_packet_status_->first, seq_num) >= kSeqNumHalf) {
     RemoveOldestPacketStatus();
   }
 
+  SentPacket sent_packet(send_time_ms, PacketStatus::Unacked);
   packet_status_window_.insert(packet_status_window_.end(),
-                               std::make_pair(seq_num, PacketStatus::Unacked));
+                               std::make_pair(seq_num, sent_packet));

[michaelt, 2017/03/07 09:15:26]

Use:
"packet_status_window_.emplace_hint(packet_status_window_.end(),std::make_pair(seq_num,
SentPacket(send_time_ms, PacketStatus::Unacked)));"

To construct SentPacket direct in the map. So we can save a copy.

[elad.alon_webrtc.org, 2017/03/07 11:55:19]

Done.

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

[michaelt, 2017/03/07 09:15:26]

Unrelated to this CL. But can you rename
"fb_vector" to "feedback_statuses" or something like that.
 

[elad.alon_webrtc.org, 2017/03/07 11:55:19]

Done.

   const uint16_t base_seq_num = feedback.GetBaseSequence();
 
   uint16_t seq_num = base_seq_num;
   for (size_t i = 0; i < fb_vector.size(); ++i, ++seq_num) {
     const auto& it = packet_status_window_.find(seq_num);
 
     // 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);
-    }
+    if (it == packet_status_window_.end())
+      continue;

[michaelt, 2017/03/07 09:15:26]

Can we RTC_DCHECK this ?

[elad.alon_webrtc.org, 2017/03/07 11:55:19]

We can't; it's not an erroneous case.

+
+    const bool lost = fb_vector[i] ==
+        webrtc::rtcp::TransportFeedback::StatusSymbol::kNotReceived;
+    const PacketStatus new_packet_status =

[michaelt, 2017/03/07 09:15:26]

I think "acked_packet_status" would be more clear than "new_packet_status" 

[elad.alon_webrtc.org, 2017/03/07 11:55:19]

I might as well just call it "packet_status" then. Let's go with that.

+        lost ? PacketStatus::Lost : PacketStatus::Received;
+
+    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::RecordFeedback(
-    PacketStatusMap::iterator it,
-    bool received) {
-  if (it->second != PacketStatus::Unacked) {
+void TransportFeedbackPacketLossTracker::RecordPacketStatus(

[michaelt, 2017/03/07 09:15:26]

How about rename this function to "UpdatedPacketStatus" and "new_packet_status"
to "packet_status" ?

[elad.alon_webrtc.org, 2017/03/07 11:55:19]

Thinking out loud:
Pro - we really sometimes overwrite an already recorded (acked) status.
Con - this is for recording the acked status, which normally happens only once.
Updating from Lost to Received is an edge case.

I'll go with UpdatePacketStatus(it, new_status). It makes it clearer down the
line that the variable new_packet_status refers to the status which we write in,
rather than some intermediate variable.

+    SentPacketStatusMap::iterator it,
+    PacketStatus new_packet_status) {
+  if (it->second.status != 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 (it->second.status == 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(it, false);
-      it->second = PacketStatus::Unacked;  // For clarity; overwritten shortly.
+      it->second.status =
+          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;
     }
   }
 
   // Change from UNACKED to RECEIVED/LOST.
-  it->second = received ? PacketStatus::Received : PacketStatus::Lost;
+  it->second.status = 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_)
+  // Remove packets from the beginning of the window until we only hold packets,
+  // be they acked or unacked, which are not more than |max_window_size_ms|
+  // older from the newest packet. (If the packet we're now inserting into the
+  // window isn't the newest, it would not trigger any removals; the newest
+  // already removed all relevant.)
+  while (ref_packet_status_ != packet_status_window_.end() &&
+         it->second.send_time_ms - ref_packet_status_->second.send_time_ms >
+             max_window_size_ms_) {
     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(
     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);
+  RTC_DCHECK(!apply || it->second.status != PacketStatus::Unacked);
 
-  if (it->second != PacketStatus::Unacked) {
+  if (it->second.status != PacketStatus::Unacked) {
     UpdateCounter(&acked_packets_, apply);
   }
 
   UpdatePlr(it, apply);
   UpdateRplr(it, apply);
 }
 
 void TransportFeedbackPacketLossTracker::UpdatePlr(
     ConstPacketStatusIterator it,
     bool apply /* false = undo */) {
-  switch (it->second) {
+  switch (it->second.status) {
     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(
     ConstPacketStatusIterator it,
     bool apply /* false = undo */) {
-  if (it->second == PacketStatus::Unacked) {
+  if (it->second.status == 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->second != PacketStatus::Unacked) {
+    if (prev->second.status != PacketStatus::Unacked) {
       UpdateCounter(&rplr_state_.num_acked_pairs_, apply);
-      if (prev->second == PacketStatus::Lost &&
-          it->second == PacketStatus::Received) {
+      if (prev->second.status == PacketStatus::Lost &&
+          it->second.status == PacketStatus::Received) {
         UpdateCounter(
             &rplr_state_.num_recoverable_losses_, apply);
       }
     }
   }
 
   // Current packet and next packet might compose a pair.
   const auto& next = NextPacketStatus(it);
   if (next != packet_status_window_.end() &&
-      next->second != PacketStatus::Unacked) {
+      next->second.status != PacketStatus::Unacked) {
     UpdateCounter(&rplr_state_.num_acked_pairs_, apply);
-    if (it->second == PacketStatus::Lost &&
-        next->second == PacketStatus::Received) {
+    if (it->second.status == PacketStatus::Lost &&
+        next->second.status == PacketStatus::Received) {
       UpdateCounter(&rplr_state_.num_recoverable_losses_, apply);
     }
   }
 }
 
 TransportFeedbackPacketLossTracker::ConstPacketStatusIterator
 TransportFeedbackPacketLossTracker::PreviousPacketStatus(
     ConstPacketStatusIterator it) const {
   RTC_DCHECK(it != ref_packet_status_);
   if (it == packet_status_window_.end()) {
@@ skipping 30 matching lines @@
 
 // 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_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_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 acked_pairs = 0;
   size_t recoverable_losses = 0;
 
   if (!packet_status_window_.empty()) {
     ConstPacketStatusIterator it = ref_packet_status_;
     do {
-      switch (it->second) {
+      switch (it->second.status) {
         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_ &&
-          it->second != PacketStatus::Unacked &&
-          next->second != PacketStatus::Unacked) {
-        ++acked_pairs;
-        if (it->second == PacketStatus::Lost &&
-            next->second == PacketStatus::Received)
-          ++recoverable_losses;
+      if (next != ref_packet_status_) {  // If we have a next packet...
+        RTC_CHECK_GE(next->second.send_time_ms, it->second.send_time_ms);
+
+        if (it->second.status != PacketStatus::Unacked &&
+            next->second.status != PacketStatus::Unacked) {
+          ++acked_pairs;
+          if (it->second.status == PacketStatus::Lost &&
+              next->second.status == 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);
@@ skipping 19 matching lines @@
 TransportFeedbackPacketLossTracker::RplrState::GetMetric() const {
   if (num_acked_pairs_ < min_num_acked_pairs_) {
     return rtc::Optional<float>();
   } else {
     return rtc::Optional<float>(
         static_cast<float>(num_recoverable_losses_) / num_acked_pairs_);
   }
 }
 
 }  // namespace webrtc