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

webrtc/p2p/base/packetlossestimator.h

Index: webrtc/p2p/base/packetlossestimator.h
diff --git a/webrtc/p2p/base/packetlossestimator.h b/webrtc/p2p/base/packetlossestimator.h
new file mode 100644
index 0000000000000000000000000000000000000000..a98050a441fa27b72d83cb115c7a11c5080c15c1
--- /dev/null
+++ b/webrtc/p2p/base/packetlossestimator.h
@@ -0,0 +1,76 @@
+/*
+ *  Copyright 2004 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.
+// Responses are considered lost if they are not received within
+// |consider_lost_after| ms. If a responses is received after

[Taylor Brandstetter, 2017/03/07 18:16:32]

"response", singular

[Zach Stein, 2017/03/08 06:21:15]

Done.

+// |consider_lost_after| ms, it is still considered to be a response.

[Taylor Brandstetter, 2017/03/07 18:16:32]

Maybe "counted as" instead of "considered to be"?

[Zach Stein, 2017/03/08 06:21:15]

Done.

+// 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

[Taylor Brandstetter, 2017/03/07 18:16:32]

Paragraph break before "If"?

[Zach Stein, 2017/03/08 06:21:14]

Done.

+// time is 7, |forget_after| is 6, and |consider_lost_after| is 2, the response

[Taylor Brandstetter, 2017/03/07 18:16:32]

Since "forget_after" now means "forget both sent requests and received
responses", maybe "window_size" would be a more clear name.

[Zach Stein, 2017/03/08 06:21:15]

I don't really like the name forget after, but I would think of window size as
forget_after - consider_lost_after (forget_after is relative to now, not the
right/near end of the window). Using window_size and window_offset does sound a
bit more formal though (forget_after = window_size + window_offset,
consider_lost_after = window_offset). Do you like that better?

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

I guess "window size" is still ambiguous since there are two windows (window of
responses being counted as received and window of responses being counted as
lost). Let's just stick with forget_after.

+// rate considers messages sent between times 1 and 5, so the window looks like
+// this:
+//
+// Time: 0 1 2 3 4 5 6 7
+// Wind:   <------->   |

[Taylor Brandstetter, 2017/03/07 18:16:32]

I'm not sure this is accurate; if a request is sent at time 6 and received at
time 7, won't it be counted?

[Zach Stein, 2017/03/08 06:21:15]

It will be. I was trying to show the window where responses count against the
response rate, but that is confusing. Maybe I should draw the window like this:

// Time: 0 1 2 3 4 5 6 7
// Wind:   <=======|--->

And say that responses expected in the = region are counted against the loss
rate but responses expected in the - region are not. Or we could just not count
responses received in the - region yet, but that seems like it might be a useful
signal.

I could also define things a bit more mathematically (I need to double check
inclusive/exclusive bounds):

// response_rate = received_full_window / (expected_left + received_right)
// received_full_window := #responses received for tracked IDs in [wind_left,
now]
// expected_left := #responses expected for tracked IDs sent in [wind_left,
wind_right)
// received_right := #responses received for tracked IDs from [wind_right, now]

Where wind_left is < and wind_right is > in the window from the diff. I'll try
to clarify this all and see where I end up.

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

That diagram looks good (or, even just the sentence you added in the latest
patchset is good). I wouldn't worry about it too much; someone can always just
look a the code or tests to confirm the expected behavior.

+class PacketLossEstimator {
+ public:
+  explicit PacketLossEstimator(int64_t consider_lost_after,
+                               int64_t forget_after);
+
+  // 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 UpdateResponseRateIfStale(int64_t now);
+
+  bool ConsiderLost(const PacketInfo&, int64_t now) const;
+  bool Forget(const PacketInfo&, int64_t now) const;
+
+  int64_t consider_lost_after_;  // In milliseconds.

[Taylor Brandstetter, 2017/03/07 18:16:32]

I forgot if I suggested this, but if these variables were named with "_ms_" at
the end, the "In milleseconds" comment wouldn't be necessary.

[Zach Stein, 2017/03/08 06:21:15]

Done.

+  int64_t forget_after_;         // In milliseconds.
+
+  int64_t last_update_time_ = 0;
+
+  std::unordered_map<std::string, PacketInfo> tracked_packets_;
+
+  double response_rate_ = 1.0;
+};
+
+}  // namespace cricket
+
+#endif  // WEBRTC_P2P_BASE_PACKETLOSSESTIMATOR_H_