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 "rtc_base/checks.h"
19
20 namespace webrtc {
21
RobustThroughputEstimator(const RobustThroughputEstimatorSettings & settings)22 RobustThroughputEstimator::RobustThroughputEstimator(
23 const RobustThroughputEstimatorSettings& settings)
24 : settings_(settings) {
25 RTC_DCHECK(settings.enabled);
26 }
27
~RobustThroughputEstimator()28 RobustThroughputEstimator::~RobustThroughputEstimator() {}
29
IncomingPacketFeedbackVector(const std::vector<PacketResult> & packet_feedback_vector)30 void RobustThroughputEstimator::IncomingPacketFeedbackVector(
31 const std::vector<PacketResult>& packet_feedback_vector) {
32 RTC_DCHECK(std::is_sorted(packet_feedback_vector.begin(),
33 packet_feedback_vector.end(),
34 PacketResult::ReceiveTimeOrder()));
35 for (const auto& packet : packet_feedback_vector) {
36 // Insert the new packet.
37 window_.push_back(packet);
38 window_.back().sent_packet.prior_unacked_data =
39 window_.back().sent_packet.prior_unacked_data *
40 settings_.unacked_weight;
41 // In most cases, receive timestamps should already be in order, but in the
42 // rare case where feedback packets have been reordered, we do some swaps to
43 // ensure that the window is sorted.
44 for (size_t i = window_.size() - 1;
45 i > 0 && window_[i].receive_time < window_[i - 1].receive_time; i--) {
46 std::swap(window_[i], window_[i - 1]);
47 }
48 // Remove old packets.
49 while (window_.size() > settings_.kMaxPackets ||
50 (window_.size() > settings_.min_packets &&
51 packet.receive_time - window_.front().receive_time >
52 settings_.window_duration)) {
53 window_.pop_front();
54 }
55 }
56 }
57
bitrate() const58 absl::optional<DataRate> RobustThroughputEstimator::bitrate() const {
59 if (window_.size() < settings_.initial_packets)
60 return absl::nullopt;
61
62 TimeDelta largest_recv_gap(TimeDelta::Millis(0));
63 TimeDelta second_largest_recv_gap(TimeDelta::Millis(0));
64 for (size_t i = 1; i < window_.size(); i++) {
65 // Find receive time gaps
66 TimeDelta gap = window_[i].receive_time - window_[i - 1].receive_time;
67 if (gap > largest_recv_gap) {
68 second_largest_recv_gap = largest_recv_gap;
69 largest_recv_gap = gap;
70 } else if (gap > second_largest_recv_gap) {
71 second_largest_recv_gap = gap;
72 }
73 }
74
75 Timestamp min_send_time = window_[0].sent_packet.send_time;
76 Timestamp max_send_time = window_[0].sent_packet.send_time;
77 Timestamp min_recv_time = window_[0].receive_time;
78 Timestamp max_recv_time = window_[0].receive_time;
79 DataSize data_size = DataSize::Bytes(0);
80 for (const auto& packet : window_) {
81 min_send_time = std::min(min_send_time, packet.sent_packet.send_time);
82 max_send_time = std::max(max_send_time, packet.sent_packet.send_time);
83 min_recv_time = std::min(min_recv_time, packet.receive_time);
84 max_recv_time = std::max(max_recv_time, packet.receive_time);
85 data_size += packet.sent_packet.size;
86 data_size += packet.sent_packet.prior_unacked_data;
87 }
88
89 // Suppose a packet of size S is sent every T milliseconds.
90 // A window of N packets would contain N*S bytes, but the time difference
91 // between the first and the last packet would only be (N-1)*T. Thus, we
92 // need to remove one packet.
93 DataSize recv_size = data_size;
94 DataSize send_size = data_size;
95 if (settings_.assume_shared_link) {
96 // Depending on how the bottleneck queue is implemented, a large packet
97 // may delay sending of sebsequent packets, so the delay between packets
98 // i and i+1 depends on the size of both packets. In this case we minimize
99 // the maximum error by removing half of both the first and last packet
100 // size.
101 DataSize first_last_average_size =
102 (window_.front().sent_packet.size +
103 window_.front().sent_packet.prior_unacked_data +
104 window_.back().sent_packet.size +
105 window_.back().sent_packet.prior_unacked_data) /
106 2;
107 recv_size -= first_last_average_size;
108 send_size -= first_last_average_size;
109 } else {
110 // In the simpler case where the delay between packets i and i+1 only
111 // depends on the size of packet i+1, the first packet doesn't give us
112 // any information. Analogously, we assume that the start send time
113 // for the last packet doesn't depend on the size of the packet.
114 recv_size -= (window_.front().sent_packet.size +
115 window_.front().sent_packet.prior_unacked_data);
116 send_size -= (window_.back().sent_packet.size +
117 window_.back().sent_packet.prior_unacked_data);
118 }
119
120 // Remove the largest gap by replacing it by the second largest gap
121 // or the average gap.
122 TimeDelta send_duration = max_send_time - min_send_time;
123 TimeDelta recv_duration = (max_recv_time - min_recv_time) - largest_recv_gap;
124 if (settings_.reduce_bias) {
125 recv_duration += second_largest_recv_gap;
126 } else {
127 recv_duration += recv_duration / (window_.size() - 2);
128 }
129
130 send_duration = std::max(send_duration, TimeDelta::Millis(1));
131 recv_duration = std::max(recv_duration, TimeDelta::Millis(1));
132 return std::min(send_size / send_duration, recv_size / recv_duration);
133 }
134
135 } // namespace webrtc
136