1 /*
2 * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 #include "modules/congestion_controller/goog_cc/robust_throughput_estimator.h"
12
13 #include <stddef.h>
14
15 #include <algorithm>
16 #include <utility>
17
18 #include "api/units/data_rate.h"
19 #include "api/units/data_size.h"
20 #include "api/units/time_delta.h"
21 #include "api/units/timestamp.h"
22 #include "rtc_base/checks.h"
23
24 namespace webrtc {
25
RobustThroughputEstimator(const RobustThroughputEstimatorSettings & settings)26 RobustThroughputEstimator::RobustThroughputEstimator(
27 const RobustThroughputEstimatorSettings& settings)
28 : settings_(settings),
29 latest_discarded_send_time_(Timestamp::MinusInfinity()) {
30 RTC_DCHECK(settings.enabled);
31 }
32
~RobustThroughputEstimator()33 RobustThroughputEstimator::~RobustThroughputEstimator() {}
34
FirstPacketOutsideWindow()35 bool RobustThroughputEstimator::FirstPacketOutsideWindow() {
36 if (window_.empty())
37 return false;
38 if (window_.size() > settings_.max_window_packets)
39 return true;
40 TimeDelta current_window_duration =
41 window_.back().receive_time - window_.front().receive_time;
42 if (current_window_duration > settings_.max_window_duration)
43 return true;
44 if (window_.size() > settings_.window_packets &&
45 current_window_duration > settings_.min_window_duration) {
46 return true;
47 }
48 return false;
49 }
50
IncomingPacketFeedbackVector(const std::vector<PacketResult> & packet_feedback_vector)51 void RobustThroughputEstimator::IncomingPacketFeedbackVector(
52 const std::vector<PacketResult>& packet_feedback_vector) {
53 RTC_DCHECK(std::is_sorted(packet_feedback_vector.begin(),
54 packet_feedback_vector.end(),
55 PacketResult::ReceiveTimeOrder()));
56 for (const auto& packet : packet_feedback_vector) {
57 // Ignore packets without valid send or receive times.
58 // (This should not happen in production since lost packets are filtered
59 // out before passing the feedback vector to the throughput estimator.
60 // However, explicitly handling this case makes the estimator more robust
61 // and avoids a hard-to-detect bad state.)
62 if (packet.receive_time.IsInfinite() ||
63 packet.sent_packet.send_time.IsInfinite()) {
64 continue;
65 }
66
67 // Insert the new packet.
68 window_.push_back(packet);
69 window_.back().sent_packet.prior_unacked_data =
70 window_.back().sent_packet.prior_unacked_data *
71 settings_.unacked_weight;
72 // In most cases, receive timestamps should already be in order, but in the
73 // rare case where feedback packets have been reordered, we do some swaps to
74 // ensure that the window is sorted.
75 for (size_t i = window_.size() - 1;
76 i > 0 && window_[i].receive_time < window_[i - 1].receive_time; i--) {
77 std::swap(window_[i], window_[i - 1]);
78 }
79 }
80
81 // Remove old packets.
82 while (FirstPacketOutsideWindow()) {
83 latest_discarded_send_time_ = std::max(
84 latest_discarded_send_time_, window_.front().sent_packet.send_time);
85 window_.pop_front();
86 }
87 }
88
bitrate() const89 absl::optional<DataRate> RobustThroughputEstimator::bitrate() const {
90 if (window_.empty() || window_.size() < settings_.required_packets)
91 return absl::nullopt;
92
93 TimeDelta largest_recv_gap(TimeDelta::Zero());
94 TimeDelta second_largest_recv_gap(TimeDelta::Zero());
95 for (size_t i = 1; i < window_.size(); i++) {
96 // Find receive time gaps.
97 TimeDelta gap = window_[i].receive_time - window_[i - 1].receive_time;
98 if (gap > largest_recv_gap) {
99 second_largest_recv_gap = largest_recv_gap;
100 largest_recv_gap = gap;
101 } else if (gap > second_largest_recv_gap) {
102 second_largest_recv_gap = gap;
103 }
104 }
105
106 Timestamp first_send_time = Timestamp::PlusInfinity();
107 Timestamp last_send_time = Timestamp::MinusInfinity();
108 Timestamp first_recv_time = Timestamp::PlusInfinity();
109 Timestamp last_recv_time = Timestamp::MinusInfinity();
110 DataSize recv_size = DataSize::Bytes(0);
111 DataSize send_size = DataSize::Bytes(0);
112 DataSize first_recv_size = DataSize::Bytes(0);
113 DataSize last_send_size = DataSize::Bytes(0);
114 size_t num_sent_packets_in_window = 0;
115 for (const auto& packet : window_) {
116 if (packet.receive_time < first_recv_time) {
117 first_recv_time = packet.receive_time;
118 first_recv_size =
119 packet.sent_packet.size + packet.sent_packet.prior_unacked_data;
120 }
121 last_recv_time = std::max(last_recv_time, packet.receive_time);
122 recv_size += packet.sent_packet.size;
123 recv_size += packet.sent_packet.prior_unacked_data;
124
125 if (packet.sent_packet.send_time < latest_discarded_send_time_) {
126 // If we have dropped packets from the window that were sent after
127 // this packet, then this packet was reordered. Ignore it from
128 // the send rate computation (since the send time may be very far
129 // in the past, leading to underestimation of the send rate.)
130 // However, ignoring packets creates a risk that we end up without
131 // any packets left to compute a send rate.
132 continue;
133 }
134 if (packet.sent_packet.send_time > last_send_time) {
135 last_send_time = packet.sent_packet.send_time;
136 last_send_size =
137 packet.sent_packet.size + packet.sent_packet.prior_unacked_data;
138 }
139 first_send_time = std::min(first_send_time, packet.sent_packet.send_time);
140
141 send_size += packet.sent_packet.size;
142 send_size += packet.sent_packet.prior_unacked_data;
143 ++num_sent_packets_in_window;
144 }
145
146 // Suppose a packet of size S is sent every T milliseconds.
147 // A window of N packets would contain N*S bytes, but the time difference
148 // between the first and the last packet would only be (N-1)*T. Thus, we
149 // need to remove the size of one packet to get the correct rate of S/T.
150 // Which packet to remove (if the packets have varying sizes),
151 // depends on the network model.
152 // Suppose that 2 packets with sizes s1 and s2, are received at times t1
153 // and t2, respectively. If the packets were transmitted back to back over
154 // a bottleneck with rate capacity r, then we'd expect t2 = t1 + r * s2.
155 // Thus, r = (t2-t1) / s2, so the size of the first packet doesn't affect
156 // the difference between t1 and t2.
157 // Analoguously, if the first packet is sent at time t1 and the sender
158 // paces the packets at rate r, then the second packet can be sent at time
159 // t2 = t1 + r * s1. Thus, the send rate estimate r = (t2-t1) / s1 doesn't
160 // depend on the size of the last packet.
161 recv_size -= first_recv_size;
162 send_size -= last_send_size;
163
164 // Remove the largest gap by replacing it by the second largest gap.
165 // This is to ensure that spurious "delay spikes" (i.e. when the
166 // network stops transmitting packets for a short period, followed
167 // by a burst of delayed packets), don't cause the estimate to drop.
168 // This could cause an overestimation, which we guard against by
169 // never returning an estimate above the send rate.
170 RTC_DCHECK(first_recv_time.IsFinite());
171 RTC_DCHECK(last_recv_time.IsFinite());
172 TimeDelta recv_duration = (last_recv_time - first_recv_time) -
173 largest_recv_gap + second_largest_recv_gap;
174 recv_duration = std::max(recv_duration, TimeDelta::Millis(1));
175
176 if (num_sent_packets_in_window < settings_.required_packets) {
177 // Too few send times to calculate a reliable send rate.
178 return recv_size / recv_duration;
179 }
180
181 RTC_DCHECK(first_send_time.IsFinite());
182 RTC_DCHECK(last_send_time.IsFinite());
183 TimeDelta send_duration = last_send_time - first_send_time;
184 send_duration = std::max(send_duration, TimeDelta::Millis(1));
185
186 return std::min(send_size / send_duration, recv_size / recv_duration);
187 }
188
189 } // namespace webrtc
190