1 /*
2 * Copyright (c) 2016 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/video_coding/deprecated/nack_module.h"
12
13 #include <algorithm>
14 #include <limits>
15
16 #include "api/units/timestamp.h"
17 #include "modules/utility/include/process_thread.h"
18 #include "rtc_base/checks.h"
19 #include "rtc_base/experiments/field_trial_parser.h"
20 #include "rtc_base/logging.h"
21 #include "system_wrappers/include/field_trial.h"
22
23 namespace webrtc {
24
25 namespace {
26 const int kMaxPacketAge = 10000;
27 const int kMaxNackPackets = 1000;
28 const int kDefaultRttMs = 100;
29 const int kMaxNackRetries = 10;
30 const int kProcessFrequency = 50;
31 const int kProcessIntervalMs = 1000 / kProcessFrequency;
32 const int kMaxReorderedPackets = 128;
33 const int kNumReorderingBuckets = 10;
34 const int kDefaultSendNackDelayMs = 0;
35
GetSendNackDelay()36 int64_t GetSendNackDelay() {
37 int64_t delay_ms = strtol(
38 webrtc::field_trial::FindFullName("WebRTC-SendNackDelayMs").c_str(),
39 nullptr, 10);
40 if (delay_ms > 0 && delay_ms <= 20) {
41 RTC_LOG(LS_INFO) << "SendNackDelay is set to " << delay_ms;
42 return delay_ms;
43 }
44 return kDefaultSendNackDelayMs;
45 }
46 } // namespace
47
NackInfo()48 DEPRECATED_NackModule::NackInfo::NackInfo()
49 : seq_num(0), send_at_seq_num(0), sent_at_time(-1), retries(0) {}
50
NackInfo(uint16_t seq_num,uint16_t send_at_seq_num,int64_t created_at_time)51 DEPRECATED_NackModule::NackInfo::NackInfo(uint16_t seq_num,
52 uint16_t send_at_seq_num,
53 int64_t created_at_time)
54 : seq_num(seq_num),
55 send_at_seq_num(send_at_seq_num),
56 created_at_time(created_at_time),
57 sent_at_time(-1),
58 retries(0) {}
59
BackoffSettings(TimeDelta min_retry,TimeDelta max_rtt,double base)60 DEPRECATED_NackModule::BackoffSettings::BackoffSettings(TimeDelta min_retry,
61 TimeDelta max_rtt,
62 double base)
63 : min_retry_interval(min_retry), max_rtt(max_rtt), base(base) {}
64
65 absl::optional<DEPRECATED_NackModule::BackoffSettings>
ParseFromFieldTrials()66 DEPRECATED_NackModule::BackoffSettings::ParseFromFieldTrials() {
67 // Matches magic number in RTPSender::OnReceivedNack().
68 const TimeDelta kDefaultMinRetryInterval = TimeDelta::Millis(5);
69 // Upper bound on link-delay considered for exponential backoff.
70 // Selected so that cumulative delay with 1.25 base and 10 retries ends up
71 // below 3s, since above that there will be a FIR generated instead.
72 const TimeDelta kDefaultMaxRtt = TimeDelta::Millis(160);
73 // Default base for exponential backoff, adds 25% RTT delay for each retry.
74 const double kDefaultBase = 1.25;
75
76 FieldTrialParameter<bool> enabled("enabled", false);
77 FieldTrialParameter<TimeDelta> min_retry("min_retry",
78 kDefaultMinRetryInterval);
79 FieldTrialParameter<TimeDelta> max_rtt("max_rtt", kDefaultMaxRtt);
80 FieldTrialParameter<double> base("base", kDefaultBase);
81 ParseFieldTrial({&enabled, &min_retry, &max_rtt, &base},
82 field_trial::FindFullName("WebRTC-ExponentialNackBackoff"));
83
84 if (enabled) {
85 return DEPRECATED_NackModule::BackoffSettings(min_retry.Get(),
86 max_rtt.Get(), base.Get());
87 }
88 return absl::nullopt;
89 }
90
DEPRECATED_NackModule(Clock * clock,NackSender * nack_sender,KeyFrameRequestSender * keyframe_request_sender)91 DEPRECATED_NackModule::DEPRECATED_NackModule(
92 Clock* clock,
93 NackSender* nack_sender,
94 KeyFrameRequestSender* keyframe_request_sender)
95 : clock_(clock),
96 nack_sender_(nack_sender),
97 keyframe_request_sender_(keyframe_request_sender),
98 reordering_histogram_(kNumReorderingBuckets, kMaxReorderedPackets),
99 initialized_(false),
100 rtt_ms_(kDefaultRttMs),
101 newest_seq_num_(0),
102 next_process_time_ms_(-1),
103 send_nack_delay_ms_(GetSendNackDelay()),
104 backoff_settings_(BackoffSettings::ParseFromFieldTrials()) {
105 RTC_DCHECK(clock_);
106 RTC_DCHECK(nack_sender_);
107 RTC_DCHECK(keyframe_request_sender_);
108 }
109
OnReceivedPacket(uint16_t seq_num,bool is_keyframe)110 int DEPRECATED_NackModule::OnReceivedPacket(uint16_t seq_num,
111 bool is_keyframe) {
112 return OnReceivedPacket(seq_num, is_keyframe, false);
113 }
114
OnReceivedPacket(uint16_t seq_num,bool is_keyframe,bool is_recovered)115 int DEPRECATED_NackModule::OnReceivedPacket(uint16_t seq_num,
116 bool is_keyframe,
117 bool is_recovered) {
118 MutexLock lock(&mutex_);
119 // TODO(philipel): When the packet includes information whether it is
120 // retransmitted or not, use that value instead. For
121 // now set it to true, which will cause the reordering
122 // statistics to never be updated.
123 bool is_retransmitted = true;
124
125 if (!initialized_) {
126 newest_seq_num_ = seq_num;
127 if (is_keyframe)
128 keyframe_list_.insert(seq_num);
129 initialized_ = true;
130 return 0;
131 }
132
133 // Since the |newest_seq_num_| is a packet we have actually received we know
134 // that packet has never been Nacked.
135 if (seq_num == newest_seq_num_)
136 return 0;
137
138 if (AheadOf(newest_seq_num_, seq_num)) {
139 // An out of order packet has been received.
140 auto nack_list_it = nack_list_.find(seq_num);
141 int nacks_sent_for_packet = 0;
142 if (nack_list_it != nack_list_.end()) {
143 nacks_sent_for_packet = nack_list_it->second.retries;
144 nack_list_.erase(nack_list_it);
145 }
146 if (!is_retransmitted)
147 UpdateReorderingStatistics(seq_num);
148 return nacks_sent_for_packet;
149 }
150
151 // Keep track of new keyframes.
152 if (is_keyframe)
153 keyframe_list_.insert(seq_num);
154
155 // And remove old ones so we don't accumulate keyframes.
156 auto it = keyframe_list_.lower_bound(seq_num - kMaxPacketAge);
157 if (it != keyframe_list_.begin())
158 keyframe_list_.erase(keyframe_list_.begin(), it);
159
160 if (is_recovered) {
161 recovered_list_.insert(seq_num);
162
163 // Remove old ones so we don't accumulate recovered packets.
164 auto it = recovered_list_.lower_bound(seq_num - kMaxPacketAge);
165 if (it != recovered_list_.begin())
166 recovered_list_.erase(recovered_list_.begin(), it);
167
168 // Do not send nack for packets recovered by FEC or RTX.
169 return 0;
170 }
171
172 AddPacketsToNack(newest_seq_num_ + 1, seq_num);
173 newest_seq_num_ = seq_num;
174
175 // Are there any nacks that are waiting for this seq_num.
176 std::vector<uint16_t> nack_batch = GetNackBatch(kSeqNumOnly);
177 if (!nack_batch.empty()) {
178 // This batch of NACKs is triggered externally; the initiator can
179 // batch them with other feedback messages.
180 nack_sender_->SendNack(nack_batch, /*buffering_allowed=*/true);
181 }
182
183 return 0;
184 }
185
ClearUpTo(uint16_t seq_num)186 void DEPRECATED_NackModule::ClearUpTo(uint16_t seq_num) {
187 MutexLock lock(&mutex_);
188 nack_list_.erase(nack_list_.begin(), nack_list_.lower_bound(seq_num));
189 keyframe_list_.erase(keyframe_list_.begin(),
190 keyframe_list_.lower_bound(seq_num));
191 recovered_list_.erase(recovered_list_.begin(),
192 recovered_list_.lower_bound(seq_num));
193 }
194
UpdateRtt(int64_t rtt_ms)195 void DEPRECATED_NackModule::UpdateRtt(int64_t rtt_ms) {
196 MutexLock lock(&mutex_);
197 rtt_ms_ = rtt_ms;
198 }
199
Clear()200 void DEPRECATED_NackModule::Clear() {
201 MutexLock lock(&mutex_);
202 nack_list_.clear();
203 keyframe_list_.clear();
204 recovered_list_.clear();
205 }
206
TimeUntilNextProcess()207 int64_t DEPRECATED_NackModule::TimeUntilNextProcess() {
208 return std::max<int64_t>(next_process_time_ms_ - clock_->TimeInMilliseconds(),
209 0);
210 }
211
Process()212 void DEPRECATED_NackModule::Process() {
213 if (nack_sender_) {
214 std::vector<uint16_t> nack_batch;
215 {
216 MutexLock lock(&mutex_);
217 nack_batch = GetNackBatch(kTimeOnly);
218 }
219
220 if (!nack_batch.empty()) {
221 // This batch of NACKs is triggered externally; there is no external
222 // initiator who can batch them with other feedback messages.
223 nack_sender_->SendNack(nack_batch, /*buffering_allowed=*/false);
224 }
225 }
226
227 // Update the next_process_time_ms_ in intervals to achieve
228 // the targeted frequency over time. Also add multiple intervals
229 // in case of a skip in time as to not make uneccessary
230 // calls to Process in order to catch up.
231 int64_t now_ms = clock_->TimeInMilliseconds();
232 if (next_process_time_ms_ == -1) {
233 next_process_time_ms_ = now_ms + kProcessIntervalMs;
234 } else {
235 next_process_time_ms_ = next_process_time_ms_ + kProcessIntervalMs +
236 (now_ms - next_process_time_ms_) /
237 kProcessIntervalMs * kProcessIntervalMs;
238 }
239 }
240
RemovePacketsUntilKeyFrame()241 bool DEPRECATED_NackModule::RemovePacketsUntilKeyFrame() {
242 while (!keyframe_list_.empty()) {
243 auto it = nack_list_.lower_bound(*keyframe_list_.begin());
244
245 if (it != nack_list_.begin()) {
246 // We have found a keyframe that actually is newer than at least one
247 // packet in the nack list.
248 nack_list_.erase(nack_list_.begin(), it);
249 return true;
250 }
251
252 // If this keyframe is so old it does not remove any packets from the list,
253 // remove it from the list of keyframes and try the next keyframe.
254 keyframe_list_.erase(keyframe_list_.begin());
255 }
256 return false;
257 }
258
AddPacketsToNack(uint16_t seq_num_start,uint16_t seq_num_end)259 void DEPRECATED_NackModule::AddPacketsToNack(uint16_t seq_num_start,
260 uint16_t seq_num_end) {
261 // Remove old packets.
262 auto it = nack_list_.lower_bound(seq_num_end - kMaxPacketAge);
263 nack_list_.erase(nack_list_.begin(), it);
264
265 // If the nack list is too large, remove packets from the nack list until
266 // the latest first packet of a keyframe. If the list is still too large,
267 // clear it and request a keyframe.
268 uint16_t num_new_nacks = ForwardDiff(seq_num_start, seq_num_end);
269 if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
270 while (RemovePacketsUntilKeyFrame() &&
271 nack_list_.size() + num_new_nacks > kMaxNackPackets) {
272 }
273
274 if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
275 nack_list_.clear();
276 RTC_LOG(LS_WARNING) << "NACK list full, clearing NACK"
277 " list and requesting keyframe.";
278 keyframe_request_sender_->RequestKeyFrame();
279 return;
280 }
281 }
282
283 for (uint16_t seq_num = seq_num_start; seq_num != seq_num_end; ++seq_num) {
284 // Do not send nack for packets that are already recovered by FEC or RTX
285 if (recovered_list_.find(seq_num) != recovered_list_.end())
286 continue;
287 NackInfo nack_info(seq_num, seq_num + WaitNumberOfPackets(0.5),
288 clock_->TimeInMilliseconds());
289 RTC_DCHECK(nack_list_.find(seq_num) == nack_list_.end());
290 nack_list_[seq_num] = nack_info;
291 }
292 }
293
GetNackBatch(NackFilterOptions options)294 std::vector<uint16_t> DEPRECATED_NackModule::GetNackBatch(
295 NackFilterOptions options) {
296 bool consider_seq_num = options != kTimeOnly;
297 bool consider_timestamp = options != kSeqNumOnly;
298 Timestamp now = clock_->CurrentTime();
299 std::vector<uint16_t> nack_batch;
300 auto it = nack_list_.begin();
301 while (it != nack_list_.end()) {
302 TimeDelta resend_delay = TimeDelta::Millis(rtt_ms_);
303 if (backoff_settings_) {
304 resend_delay =
305 std::max(resend_delay, backoff_settings_->min_retry_interval);
306 if (it->second.retries > 1) {
307 TimeDelta exponential_backoff =
308 std::min(TimeDelta::Millis(rtt_ms_), backoff_settings_->max_rtt) *
309 std::pow(backoff_settings_->base, it->second.retries - 1);
310 resend_delay = std::max(resend_delay, exponential_backoff);
311 }
312 }
313
314 bool delay_timed_out =
315 now.ms() - it->second.created_at_time >= send_nack_delay_ms_;
316 bool nack_on_rtt_passed =
317 now.ms() - it->second.sent_at_time >= resend_delay.ms();
318 bool nack_on_seq_num_passed =
319 it->second.sent_at_time == -1 &&
320 AheadOrAt(newest_seq_num_, it->second.send_at_seq_num);
321 if (delay_timed_out && ((consider_seq_num && nack_on_seq_num_passed) ||
322 (consider_timestamp && nack_on_rtt_passed))) {
323 nack_batch.emplace_back(it->second.seq_num);
324 ++it->second.retries;
325 it->second.sent_at_time = now.ms();
326 if (it->second.retries >= kMaxNackRetries) {
327 RTC_LOG(LS_WARNING) << "Sequence number " << it->second.seq_num
328 << " removed from NACK list due to max retries.";
329 it = nack_list_.erase(it);
330 } else {
331 ++it;
332 }
333 continue;
334 }
335 ++it;
336 }
337 return nack_batch;
338 }
339
UpdateReorderingStatistics(uint16_t seq_num)340 void DEPRECATED_NackModule::UpdateReorderingStatistics(uint16_t seq_num) {
341 RTC_DCHECK(AheadOf(newest_seq_num_, seq_num));
342 uint16_t diff = ReverseDiff(newest_seq_num_, seq_num);
343 reordering_histogram_.Add(diff);
344 }
345
WaitNumberOfPackets(float probability) const346 int DEPRECATED_NackModule::WaitNumberOfPackets(float probability) const {
347 if (reordering_histogram_.NumValues() == 0)
348 return 0;
349 return reordering_histogram_.InverseCdf(probability);
350 }
351
352 } // namespace webrtc
353