Measure packet loss so we can use it to select ICE candidate pairs.
BUG=webrtc:7028
Review-Url: https://codereview.webrtc.org/2722933002
Cr-Commit-Position: refs/heads/master@{#17313}
diff --git a/webrtc/p2p/BUILD.gn b/webrtc/p2p/BUILD.gn
index 07fcdf4..b458653 100644
--- a/webrtc/p2p/BUILD.gn
+++ b/webrtc/p2p/BUILD.gn
@@ -37,6 +37,8 @@
"base/p2pconstants.h",
"base/p2ptransportchannel.cc",
"base/p2ptransportchannel.h",
+ "base/packetlossestimator.cc",
+ "base/packetlossestimator.h",
"base/packetsocketfactory.h",
"base/packettransportinterface.h",
"base/packettransportinternal.h",
@@ -153,6 +155,7 @@
"base/jseptransport_unittest.cc",
"base/mockicetransport.h",
"base/p2ptransportchannel_unittest.cc",
+ "base/packetlossestimator_unittest.cc",
"base/port_unittest.cc",
"base/portallocator_unittest.cc",
"base/pseudotcp_unittest.cc",
diff --git a/webrtc/p2p/base/packetlossestimator.cc b/webrtc/p2p/base/packetlossestimator.cc
new file mode 100644
index 0000000..7dcd5b9
--- /dev/null
+++ b/webrtc/p2p/base/packetlossestimator.cc
@@ -0,0 +1,126 @@
+/*
+ * 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.
+ */
+
+#include <sstream>
+
+#include "webrtc/p2p/base/packetlossestimator.h"
+
+#include "webrtc/base/checks.h"
+
+namespace cricket {
+
+PacketLossEstimator::PacketLossEstimator(int64_t consider_lost_after_ms,
+ int64_t forget_after_ms)
+ : consider_lost_after_ms_(consider_lost_after_ms),
+ forget_after_ms_(forget_after_ms) {
+ RTC_DCHECK_LT(consider_lost_after_ms, forget_after_ms);
+}
+
+void PacketLossEstimator::ExpectResponse(std::string id, int64_t sent_time) {
+ tracked_packets_[id] = PacketInfo{sent_time, false};
+
+ // Called to free memory in case the client hasn't called UpdateResponseRate
+ // in a while.
+ MaybeForgetOldRequests(sent_time);
+}
+
+void PacketLossEstimator::ReceivedResponse(std::string id,
+ int64_t received_time) {
+ auto iter = tracked_packets_.find(id);
+ if (iter != tracked_packets_.end()) {
+ auto& packet_info = iter->second;
+ packet_info.response_received = true;
+ }
+
+ // Called to free memory in case the client hasn't called UpdateResponseRate
+ // in a while.
+ MaybeForgetOldRequests(received_time);
+}
+
+void PacketLossEstimator::UpdateResponseRate(int64_t now) {
+ int responses_expected = 0;
+ int responses_received = 0;
+
+ for (auto iter = tracked_packets_.begin(); iter != tracked_packets_.end();) {
+ const auto& packet_info = iter->second;
+ if (Forget(packet_info, now)) {
+ iter = tracked_packets_.erase(iter);
+ continue;
+ }
+ if (packet_info.response_received) {
+ responses_expected += 1;
+ responses_received += 1;
+ } else if (ConsiderLost(packet_info, now)) {
+ responses_expected += 1;
+ }
+ ++iter;
+ }
+
+ if (responses_expected > 0) {
+ response_rate_ =
+ static_cast<double>(responses_received) / responses_expected;
+ } else {
+ response_rate_ = 1.0;
+ }
+
+ last_forgot_at_ = now;
+}
+
+void PacketLossEstimator::MaybeForgetOldRequests(int64_t now) {
+ if (now - last_forgot_at_ <= forget_after_ms_) {
+ return;
+ }
+
+ for (auto iter = tracked_packets_.begin(); iter != tracked_packets_.end();) {
+ const auto& packet_info = iter->second;
+ if (Forget(packet_info, now)) {
+ iter = tracked_packets_.erase(iter);
+ } else {
+ ++iter;
+ }
+ }
+
+ last_forgot_at_ = now;
+}
+
+bool PacketLossEstimator::ConsiderLost(const PacketInfo& packet_info,
+ int64_t now) const {
+ return packet_info.sent_time < now - consider_lost_after_ms_;
+}
+
+bool PacketLossEstimator::Forget(const PacketInfo& packet_info,
+ int64_t now) const {
+ return now - packet_info.sent_time > forget_after_ms_;
+}
+
+std::size_t PacketLossEstimator::tracked_packet_count_for_testing() const {
+ return tracked_packets_.size();
+}
+
+std::string PacketLossEstimator::TrackedPacketsStringForTesting(
+ std::size_t max) const {
+ std::ostringstream oss;
+
+ size_t count = 0;
+ for (const auto& p : tracked_packets_) {
+ const auto& id = p.first;
+ const auto& packet_info = p.second;
+ oss << "{ " << id << ", " << packet_info.sent_time << "}, ";
+ count += 1;
+ if (count == max) {
+ oss << "...";
+ break;
+ }
+ }
+
+ return oss.str();
+}
+
+} // namespace cricket
diff --git a/webrtc/p2p/base/packetlossestimator.h b/webrtc/p2p/base/packetlossestimator.h
new file mode 100644
index 0000000..dfc5fe5
--- /dev/null
+++ b/webrtc/p2p/base/packetlossestimator.h
@@ -0,0 +1,86 @@
+/*
+ * 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.
+//
+// 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 forgotten.
+ void UpdateResponseRate(int64_t now);
+
+ // Gets the current response rate as updated by UpdateResponseRate.
+ double get_response_rate() const { return response_rate_; }
+
+ std::size_t tracked_packet_count_for_testing() const;
+
+ // Output tracked packet state as a string.
+ std::string TrackedPacketsStringForTesting(std::size_t max) const;
+
+ private:
+ struct PacketInfo {
+ int64_t sent_time;
+ bool response_received;
+ };
+
+ // Called periodically by ExpectResponse and ReceivedResponse to manage memory
+ // usage.
+ 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_
diff --git a/webrtc/p2p/base/packetlossestimator_unittest.cc b/webrtc/p2p/base/packetlossestimator_unittest.cc
new file mode 100644
index 0000000..44cfdbf
--- /dev/null
+++ b/webrtc/p2p/base/packetlossestimator_unittest.cc
@@ -0,0 +1,172 @@
+/*
+ * 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.
+ */
+
+#include <utility>
+
+#include "webrtc/base/gunit.h"
+#include "webrtc/p2p/base/packetlossestimator.h"
+
+using cricket::PacketLossEstimator;
+
+class PacketLossEstimatorTest : public testing::Test {};
+
+TEST_F(PacketLossEstimatorTest, InitialResponseRate) {
+ PacketLossEstimator ple(5, 100);
+ EXPECT_EQ(1.0, ple.get_response_rate());
+}
+
+TEST_F(PacketLossEstimatorTest, InitialUpdateResponseRate) {
+ PacketLossEstimator ple(5, 100);
+ ple.UpdateResponseRate(10);
+ EXPECT_EQ(1.0, ple.get_response_rate());
+}
+
+TEST_F(PacketLossEstimatorTest, ResponseReceived) {
+ PacketLossEstimator ple(5, 100);
+
+ ple.ExpectResponse("a", 0);
+ ple.ReceivedResponse("a", 1);
+ ple.UpdateResponseRate(2);
+
+ EXPECT_EQ(1.0, ple.get_response_rate());
+}
+
+TEST_F(PacketLossEstimatorTest, ResponseNotConsideredLostYet) {
+ PacketLossEstimator ple(5, 100);
+
+ ple.ExpectResponse("a", 0);
+ ple.UpdateResponseRate(2);
+
+ EXPECT_EQ(1.0, ple.get_response_rate());
+}
+
+TEST_F(PacketLossEstimatorTest, ResponseConsideredLost) {
+ PacketLossEstimator ple(5, 100);
+
+ ple.ExpectResponse("a", 0);
+ ple.UpdateResponseRate(10);
+
+ EXPECT_EQ(0.0, ple.get_response_rate());
+}
+
+TEST_F(PacketLossEstimatorTest, ResponseLate) {
+ PacketLossEstimator ple(5, 100);
+
+ ple.ExpectResponse("a", 0);
+ ple.ReceivedResponse("a", 6);
+ ple.UpdateResponseRate(10);
+
+ EXPECT_EQ(1.0, ple.get_response_rate());
+}
+
+TEST_F(PacketLossEstimatorTest, ResponseForgotten) {
+ PacketLossEstimator ple(5, 100);
+ ple.ExpectResponse("a", 0);
+ ple.UpdateResponseRate(101);
+
+ EXPECT_EQ(1.0, ple.get_response_rate());
+}
+
+TEST_F(PacketLossEstimatorTest, Lost1_Received1) {
+ PacketLossEstimator ple(5, 100);
+
+ ple.ExpectResponse("a", 0);
+ ple.ExpectResponse("b", 2);
+ ple.ReceivedResponse("b", 6);
+ ple.UpdateResponseRate(7);
+
+ EXPECT_EQ(0.5, ple.get_response_rate());
+}
+
+static const std::pair<std::string, int64_t> kFivePackets[5] = {{"a", 0},
+ {"b", 2},
+ {"c", 4},
+ {"d", 6},
+ {"e", 8}};
+
+// Time: 0 1 2 3 4 5 6 7 8 9 10
+// Sent: a b c d e |
+// Recv: b |
+// Wind: --------------> |
+TEST_F(PacketLossEstimatorTest, Lost3_Received1_Waiting1) {
+ PacketLossEstimator ple(3, 100);
+
+ for (const auto& p : kFivePackets) {
+ ple.ExpectResponse(p.first, p.second);
+ }
+ ple.ReceivedResponse("b", 3);
+ ple.UpdateResponseRate(10);
+ EXPECT_EQ(0.25, ple.get_response_rate());
+}
+
+// Time: 0 1 2 3 4 5 6 7 8 9 10
+// Sent: a b c d e |
+// Recv: e |
+// Wind: --------------> |
+TEST_F(PacketLossEstimatorTest, Lost4_Early1) {
+ PacketLossEstimator ple(3, 100);
+
+ for (const auto& p : kFivePackets) {
+ ple.ExpectResponse(p.first, p.second);
+ }
+ ple.ReceivedResponse("e", 9);
+ ple.UpdateResponseRate(10);
+ // e should be considered, even though its response was received less than
+ // |consider_lost_after_ms| ago.
+ EXPECT_EQ(0.2, ple.get_response_rate());
+}
+
+// Time: 0 1 2 3 4 5 6 7 8 9 10
+// Sent: a b c d e |
+// Recv: c |
+// Wind: <-------> |
+TEST_F(PacketLossEstimatorTest, Forgot2_Received1_Lost1_Waiting1) {
+ PacketLossEstimator ple(3, 7);
+
+ for (const auto& p : kFivePackets) {
+ ple.ExpectResponse(p.first, p.second);
+ }
+ ple.ReceivedResponse("c", 5);
+ ple.UpdateResponseRate(10);
+ EXPECT_EQ(0.5, ple.get_response_rate());
+}
+
+// Tests that old messages are forgotten if ExpectResponse is called
+// |forget_after_ms| after |last_forgot_at|. It is important that ExpectResponse
+// and ReceivedResponse forget old messages to avoid |tracked_packets_| growing
+// without bound if UpdateResponseRate is never called (or rarely called).
+//
+// Time: 0 1 2 3 4 5 6
+// Sent: a b
+// Wind: <------->
+TEST_F(PacketLossEstimatorTest, ExpectResponseForgetsOldPackets) {
+ PacketLossEstimator ple(1, 5);
+ ple.ExpectResponse("a", 0); // This message will be forgotten.
+ ple.ExpectResponse("b", 6); // This call should trigger clean up.
+ // a should be forgotten, b should be tracked.
+ EXPECT_EQ(1u, ple.tracked_packet_count_for_testing());
+}
+
+// Tests that old messages are forgotten if ExpectResponse is called
+// |forget_after_ms| after |last_forgot_at|. It is important that ExpectResponse
+// and ReceivedResponse forget old messages to avoid |tracked_packets_| growing
+// without bound if UpdateResponseRate is never called (or rarely called).
+//
+// Time: 0 1 2 3 4 5 6
+// Sent: a
+// Recv: b
+// Wind: <------->
+TEST_F(PacketLossEstimatorTest, ReceivedResponseForgetsOldPackets) {
+ PacketLossEstimator ple(1, 5);
+ ple.ExpectResponse("a", 0); // This message will be forgotten.
+ ple.ReceivedResponse("b", 6); // This call should trigger clean up.
+ // a should be forgoten, b should not be tracked (received but not sent).
+ EXPECT_EQ(0u, ple.tracked_packet_count_for_testing());
+}
diff --git a/webrtc/p2p/base/port.cc b/webrtc/p2p/base/port.cc
index 7410b20..675d39a 100644
--- a/webrtc/p2p/base/port.cc
+++ b/webrtc/p2p/base/port.cc
@@ -77,6 +77,13 @@
// The delay before we begin checking if this port is useless. We set
// it to a little higher than a total STUN timeout.
const int kPortTimeoutDelay = cricket::STUN_TOTAL_TIMEOUT + 5000;
+
+// For packet loss estimation.
+const int64_t kConsiderPacketLostAfter = 3000; // 3 seconds
+
+// For packet loss estimation.
+const int64_t kForgetPacketAfter = 30000; // 30 seconds
+
} // namespace
namespace cricket {
@@ -885,6 +892,7 @@
last_ping_received_(0),
last_data_received_(0),
last_ping_response_received_(0),
+ packet_loss_estimator_(kConsiderPacketLostAfter, kForgetPacketAfter),
reported_(false),
state_(IceCandidatePairState::WAITING),
receiving_timeout_(WEAK_CONNECTION_RECEIVE_TIMEOUT),
@@ -1237,6 +1245,7 @@
last_ping_sent_ = now;
ConnectionRequest *req = new ConnectionRequest(this);
pings_since_last_response_.push_back(SentPing(req->id(), now, nomination_));
+ packet_loss_estimator_.ExpectResponse(req->id(), now);
LOG_J(LS_VERBOSE, this) << "Sending STUN ping "
<< ", id=" << rtc::hex_encode(req->id())
<< ", nomination=" << nomination_;
@@ -1391,6 +1400,9 @@
}
ReceivedPingResponse(rtt, request->id());
+ int64_t time_received = rtc::TimeMillis();
+ packet_loss_estimator_.ReceivedResponse(request->id(), time_received);
+
stats_.recv_ping_responses++;
MaybeUpdateLocalCandidate(request, response);
diff --git a/webrtc/p2p/base/port.h b/webrtc/p2p/base/port.h
index 4d15656..fd6d182 100644
--- a/webrtc/p2p/base/port.h
+++ b/webrtc/p2p/base/port.h
@@ -17,13 +17,6 @@
#include <string>
#include <vector>
-#include "webrtc/p2p/base/candidate.h"
-#include "webrtc/p2p/base/candidatepairinterface.h"
-#include "webrtc/p2p/base/jseptransport.h"
-#include "webrtc/p2p/base/packetsocketfactory.h"
-#include "webrtc/p2p/base/portinterface.h"
-#include "webrtc/p2p/base/stun.h"
-#include "webrtc/p2p/base/stunrequest.h"
#include "webrtc/base/asyncpacketsocket.h"
#include "webrtc/base/checks.h"
#include "webrtc/base/network.h"
@@ -33,6 +26,14 @@
#include "webrtc/base/sigslot.h"
#include "webrtc/base/socketaddress.h"
#include "webrtc/base/thread.h"
+#include "webrtc/p2p/base/candidate.h"
+#include "webrtc/p2p/base/candidatepairinterface.h"
+#include "webrtc/p2p/base/jseptransport.h"
+#include "webrtc/p2p/base/packetlossestimator.h"
+#include "webrtc/p2p/base/packetsocketfactory.h"
+#include "webrtc/p2p/base/portinterface.h"
+#include "webrtc/p2p/base/stun.h"
+#include "webrtc/p2p/base/stunrequest.h"
namespace cricket {
@@ -719,6 +720,8 @@
int64_t receiving_unchanged_since_ = 0;
std::vector<SentPing> pings_since_last_response_;
+ PacketLossEstimator packet_loss_estimator_;
+
bool reported_;
IceCandidatePairState state_;
// Time duration to switch from receiving to not receiving.
