Measure packet loss so we can use it to select ICE candidate pairs.

webrtc/p2p/base/packetlossestimator.h

+/*
+ *  Copyright 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.
+ */
+
+#ifndef WEBRTC_P2P_BASE_PACKETLOSSESTIMATOR_H_
+#define WEBRTC_P2P_BASE_PACKETLOSSESTIMATOR_H_
+
+#include <stdint.h>
+#include <string>
+#include <unordered_map>
+
+namespace cricket {
+
+// Estimates the response rate for a series of messages expecting responses.
+// Messages and their corresponding responses are identified by a string id.
+//
+// TODO(zstein): The above comment describes a PacketLossEstimatorInterface.

[Taylor Brandstetter, 2017/03/08 17:48:21]

I don't think an interface is necessary until we have multiple implementations.
Generally our policy is "only add something once you need it". If you add things
you think you *might* need, half the time you don't end up needing them (or at
least, that's my experience).

[Zach Stein, 2017/03/08 23:00:08]

That's why I just put this in a comment :)

I don't feel super strongly about this case, but in general I think there can be
a lot of value in introducing interfaces early. One advantage in this case would
be the separation of the intended client API and the implementation details.
This is the whole interface:

class IPacketLossEstimator {
 public:
  ExpectResponse(string id, int64_t sent_time);
  ReceivedResponse(string id, int64_t received_time);
  void UpdateResponseRate(int64_t now);
  double response_rate() const;
}

The details of what is considered lost, the private helpers and members, and
methods for testing/debugging make it harder to understand the class and easier
to depend more heavily on the class' internals.

If I had made an interface from the beginning, I also might not have overwritten
my previous implementation that used a vector (it could be a separate subclass
instead). I could also have added a simpler version that just tracked the
response rate without a window (which was my original plan). Having that would
have allowed me to start getting the infrastructure in place to track this data
somewhere real.

Anyway, I'll just get rid of this TODO for now and decide what to do next later
:)

+// Everything below is specific to this implementation, which counts the number
+// of responses received in a trailing window, stores its state in an
+// unordered_map, and computes the response_rate on demand. Another
+// implementation could store state in counts and a sorted vector, or use a
+// different policy to decide if a message should be considered lost.
+//
+// Responses are considered lost if they are not received within
+// |consider_lost_after_ms|. If a response is received after
+// |consider_lost_after_ms|, it is still considered as a response.
+// Messages sent more than |forget_after_ms| ago are not considered
+// anymore. The response rate is initially assumed to be 1.0.
+//
+// If the current time is 7, |forget_after_ms| is 6, and
+// |consider_lost_after_ms| is 2, the response rate considers messages sent
+// between times 1 and 5, so only messages in the following window can be
+// considered lost:
+//
+// Time: 0 1 2 3 4 5 6 7
+// Wind:   <------->   |
+//
+// Responses received to the right of the window are still counted.
+class PacketLossEstimator {
+ public:
+  explicit PacketLossEstimator(int64_t consider_lost_after_ms,
+                               int64_t forget_after_ms);
+
+  // Registers that a message with the given |id| was sent at |sent_time|.
+  void ExpectResponse(std::string id, int64_t sent_time);
+
+  // Registers a response with the given |id| was received at |received_time|.
+  void ReceivedResponse(std::string id, int64_t received_time);
+
+  // Calculates the current response rate based on the expected and received
+  // messages. Messages sent more than |forget_after| ms ago will be erased.
+  // This method is called periodically by ExpectResponse and ReceivedResponse
+  // to bound memory usage.
+  void UpdateResponseRate(int64_t now);
+
+  // Gets the current response rate as updated by UpdateResponseRate.
+  double get_response_rate() const { return response_rate_; }
+
+ private:
+  struct PacketInfo {
+    int64_t sent_time;
+    bool response_received;
+  };
+
+  void MaybeForgetOldRequests(int64_t now);
+
+  bool ConsiderLost(const PacketInfo&, int64_t now) const;
+  bool Forget(const PacketInfo&, int64_t now) const;
+
+  int64_t consider_lost_after_ms_;
+  int64_t forget_after_ms_;
+
+  int64_t last_forgot_at_ = 0;
+
+  std::unordered_map<std::string, PacketInfo> tracked_packets_;
+
+  double response_rate_ = 1.0;
+};
+
+}  // namespace cricket
+
+#endif  // WEBRTC_P2P_BASE_PACKETLOSSESTIMATOR_H_