Compute packet loss for event log visualization similar to how it is defined in RFC 3550.

webrtc/tools/event_log_visualizer/analyzer.cc

 /*
  *  Copyright (c) 2016 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/tools/event_log_visualizer/analyzer.h"
 
 #include <algorithm>
 #include <limits>
 #include <map>
 #include <sstream>
 #include <string>
 #include <utility>
 
 #include "webrtc/base/checks.h"
 #include "webrtc/base/logging.h"
 #include "webrtc/base/rate_statistics.h"
 #include "webrtc/call/audio_receive_stream.h"
 #include "webrtc/call/audio_send_stream.h"
 #include "webrtc/call/call.h"
 #include "webrtc/common_types.h"
 #include "webrtc/modules/bitrate_controller/include/bitrate_controller.h"
 #include "webrtc/modules/congestion_controller/include/congestion_controller.h"
+#include "webrtc/modules/include/module_common_types.h"
 #include "webrtc/modules/rtp_rtcp/include/rtp_rtcp.h"
 #include "webrtc/modules/rtp_rtcp/include/rtp_rtcp_defines.h"
 #include "webrtc/modules/rtp_rtcp/source/rtcp_packet/common_header.h"
 #include "webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.h"
 #include "webrtc/modules/rtp_rtcp/source/rtp_header_extensions.h"
 #include "webrtc/modules/rtp_rtcp/source/rtp_utility.h"
 #include "webrtc/video_receive_stream.h"
 #include "webrtc/video_send_stream.h"
 
 namespace webrtc {
@@ skipping 647 matching lines @@
     // Filter on direction and SSRC.
     if (stream_id.GetDirection() != kIncomingPacket ||
         !MatchingSsrc(stream_id.GetSsrc(), desired_ssrc_)) {
       continue;
     }
 
     TimeSeries time_series;
     time_series.label = GetStreamName(stream_id);
     time_series.style = LINE_DOT_GRAPH;
     const uint64_t kWindowUs = 1000000;
-    const LoggedRtpPacket* first_in_window = &packet_stream.front();
-    const LoggedRtpPacket* last_in_window = &packet_stream.front();
-    int packets_in_window = 0;
-    for (const LoggedRtpPacket& packet : packet_stream) {
-      if (packet.timestamp > first_in_window->timestamp + kWindowUs) {
-        uint16_t expected_num_packets = last_in_window->header.sequenceNumber -
-            first_in_window->header.sequenceNumber + 1;
-        float fraction_lost = (expected_num_packets - packets_in_window) /
-            static_cast<float>(expected_num_packets);
-        float y = fraction_lost * 100;
-        float x =
-            static_cast<float>(last_in_window->timestamp - begin_time_) /
-            1000000;
+    const uint64_t kStep = 1000000;
+    SequenceNumberUnwrapper unwrapper_;
+    SequenceNumberUnwrapper prior_unwrapper_;
+    size_t window_index_begin = 0;
+    size_t window_index_end = 0;
+    int64_t highest_seq_number = 0;
+    int64_t highest_prior_seq_number = 0;
+    if (packet_stream.size() > 0) {
+      unwrapper_.Unwrap(packet_stream[0].header.sequenceNumber);
+      prior_unwrapper_.Unwrap(packet_stream[0].header.sequenceNumber);
+    }
+
+    for (uint64_t t = begin_time_; t < end_time_ + kStep; t += kStep) {
+      while (window_index_end < packet_stream.size() &&
+             packet_stream[window_index_end].timestamp < t) {
+        int64_t sequence_number = unwrapper_.Unwrap(
+            packet_stream[window_index_end].header.sequenceNumber);
+        highest_seq_number = std::max(highest_seq_number, sequence_number);
+        ++window_index_end;
+      }
+      while (window_index_begin < packet_stream.size() &&
+             packet_stream[window_index_begin].timestamp < t - kWindowUs) {
+        int64_t sequence_number = prior_unwrapper_.Unwrap(
+            packet_stream[window_index_begin].header.sequenceNumber);
+        highest_prior_seq_number =
+            std::max(highest_prior_seq_number, sequence_number);
+        ++window_index_begin;
+      }
+      float x = static_cast<float>(t - begin_time_) / 1000000;
+      int64_t expected_packets = highest_seq_number - highest_prior_seq_number;
+      if (expected_packets > 0) {
+        int64_t received_packets = window_index_end - window_index_begin;

[stefan-webrtc, 2017/01/27 13:02:11]

Is there any chance that this diff becomes zero even though we have received one
packet in the window?

[terelius, 2017/01/27 14:03:11]

The loop on line 700 advances the window_index_end to the first packet past the
window. The loop on line 717 advances window_index_begin to the first packet in
the window (assuming there is a packet in the window). Thus, if there are
packets in the window, window_index_end > window_index_begin.

+        int64_t lost_packets = expected_packets - received_packets;

[terelius, 2017/01/27 14:03:11]

Note, reordering or duplication can cause expected_packets to be lower than the
number of received packets in the window. This would still cause the fraction
loss to be negative.

[minyue-webrtc, 2017/01/30 08:22:34]

Is this a flaw in RFC 3550?

[terelius, 2017/01/30 10:03:05]

They are aware that the computation can give negative results. In the spec, they
use clipping to replace all negative fractions by zero. Clipping helps them save
bits in the RTCP but also reduces the amount of information contained in the
signal.

For our purposes, I think allowing negative fraction losses is the right thing
to do. For example, if you've previously seen packet number 4 and now receive
packets 5, 6, 6, 7 and 8, I think it is reasonable say that the packet loss is
-25% since you have received 25% more packets than you expected. Or do you think
that is too confusing?

+        float y = static_cast<float>(lost_packets) / expected_packets * 100;
         time_series.points.emplace_back(x, y);
-        first_in_window = &packet;
-        last_in_window = &packet;
-        packets_in_window = 1;
-        continue;
       }
-      ++packets_in_window;
-      last_in_window = &packet;
     }
     plot->series_list_.push_back(std::move(time_series));
   }
 
   plot->SetXAxis(0, call_duration_s_, "Time (s)", kLeftMargin, kRightMargin);
   plot->SetSuggestedYAxis(0, 1, "Estimated loss rate (%)", kBottomMargin,
                           kTopMargin);
   plot->SetTitle("Estimated incoming loss rate");
 }
 
@@ skipping 463 matching lines @@
         int64_t capture_ms = packet.header.timestamp / 90.0;
         int64_t arrival_ms = packet.timestamp / 1000.0;
         timestamps.push_back(std::make_pair(capture_ms, arrival_ms));
       }
     }
   }
   return timestamps;
 }
 }  // namespace plotting
 }  // namespace webrtc