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/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 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 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 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<NackModule::BackoffSettings>
ParseFromFieldTrials()66 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 NackModule::BackoffSettings(min_retry.Get(), max_rtt.Get(),
86 base.Get());
87 }
88 return absl::nullopt;
89 }
90
NackModule(Clock * clock,NackSender * nack_sender,KeyFrameRequestSender * keyframe_request_sender)91 NackModule::NackModule(Clock* clock,
92 NackSender* nack_sender,
93 KeyFrameRequestSender* keyframe_request_sender)
94 : clock_(clock),
95 nack_sender_(nack_sender),
96 keyframe_request_sender_(keyframe_request_sender),
97 reordering_histogram_(kNumReorderingBuckets, kMaxReorderedPackets),
98 initialized_(false),
99 rtt_ms_(kDefaultRttMs),
100 newest_seq_num_(0),
101 next_process_time_ms_(-1),
102 send_nack_delay_ms_(GetSendNackDelay()),
103 backoff_settings_(BackoffSettings::ParseFromFieldTrials()) {
104 RTC_DCHECK(clock_);
105 RTC_DCHECK(nack_sender_);
106 RTC_DCHECK(keyframe_request_sender_);
107 }
108
OnReceivedPacket(uint16_t seq_num,bool is_keyframe)109 int NackModule::OnReceivedPacket(uint16_t seq_num, bool is_keyframe) {
110 return OnReceivedPacket(seq_num, is_keyframe, false);
111 }
112
OnReceivedPacket(uint16_t seq_num,bool is_keyframe,bool is_recovered)113 int NackModule::OnReceivedPacket(uint16_t seq_num,
114 bool is_keyframe,
115 bool is_recovered) {
116 rtc::CritScope lock(&crit_);
117 // TODO(philipel): When the packet includes information whether it is
118 // retransmitted or not, use that value instead. For
119 // now set it to true, which will cause the reordering
120 // statistics to never be updated.
121 bool is_retransmitted = true;
122
123 if (!initialized_) {
124 newest_seq_num_ = seq_num;
125 if (is_keyframe)
126 keyframe_list_.insert(seq_num);
127 initialized_ = true;
128 return 0;
129 }
130
131 // Since the |newest_seq_num_| is a packet we have actually received we know
132 // that packet has never been Nacked.
133 if (seq_num == newest_seq_num_)
134 return 0;
135
136 if (AheadOf(newest_seq_num_, seq_num)) {
137 // An out of order packet has been received.
138 auto nack_list_it = nack_list_.find(seq_num);
139 int nacks_sent_for_packet = 0;
140 if (nack_list_it != nack_list_.end()) {
141 nacks_sent_for_packet = nack_list_it->second.retries;
142 nack_list_.erase(nack_list_it);
143 }
144 if (!is_retransmitted)
145 UpdateReorderingStatistics(seq_num);
146 return nacks_sent_for_packet;
147 }
148
149 // Keep track of new keyframes.
150 if (is_keyframe)
151 keyframe_list_.insert(seq_num);
152
153 // And remove old ones so we don't accumulate keyframes.
154 auto it = keyframe_list_.lower_bound(seq_num - kMaxPacketAge);
155 if (it != keyframe_list_.begin())
156 keyframe_list_.erase(keyframe_list_.begin(), it);
157
158 if (is_recovered) {
159 recovered_list_.insert(seq_num);
160
161 // Remove old ones so we don't accumulate recovered packets.
162 auto it = recovered_list_.lower_bound(seq_num - kMaxPacketAge);
163 if (it != recovered_list_.begin())
164 recovered_list_.erase(recovered_list_.begin(), it);
165
166 // Do not send nack for packets recovered by FEC or RTX.
167 return 0;
168 }
169
170 AddPacketsToNack(newest_seq_num_ + 1, seq_num);
171 newest_seq_num_ = seq_num;
172
173 // Are there any nacks that are waiting for this seq_num.
174 std::vector<uint16_t> nack_batch = GetNackBatch(kSeqNumOnly);
175 if (!nack_batch.empty()) {
176 // This batch of NACKs is triggered externally; the initiator can
177 // batch them with other feedback messages.
178 nack_sender_->SendNack(nack_batch, /*buffering_allowed=*/true);
179 }
180
181 return 0;
182 }
183
ClearUpTo(uint16_t seq_num)184 void NackModule::ClearUpTo(uint16_t seq_num) {
185 rtc::CritScope lock(&crit_);
186 nack_list_.erase(nack_list_.begin(), nack_list_.lower_bound(seq_num));
187 keyframe_list_.erase(keyframe_list_.begin(),
188 keyframe_list_.lower_bound(seq_num));
189 recovered_list_.erase(recovered_list_.begin(),
190 recovered_list_.lower_bound(seq_num));
191 }
192
UpdateRtt(int64_t rtt_ms)193 void NackModule::UpdateRtt(int64_t rtt_ms) {
194 rtc::CritScope lock(&crit_);
195 rtt_ms_ = rtt_ms;
196 }
197
Clear()198 void NackModule::Clear() {
199 rtc::CritScope lock(&crit_);
200 nack_list_.clear();
201 keyframe_list_.clear();
202 recovered_list_.clear();
203 }
204
TimeUntilNextProcess()205 int64_t NackModule::TimeUntilNextProcess() {
206 return std::max<int64_t>(next_process_time_ms_ - clock_->TimeInMilliseconds(),
207 0);
208 }
209
Process()210 void NackModule::Process() {
211 if (nack_sender_) {
212 std::vector<uint16_t> nack_batch;
213 {
214 rtc::CritScope lock(&crit_);
215 nack_batch = GetNackBatch(kTimeOnly);
216 }
217
218 if (!nack_batch.empty()) {
219 // This batch of NACKs is triggered externally; there is no external
220 // initiator who can batch them with other feedback messages.
221 nack_sender_->SendNack(nack_batch, /*buffering_allowed=*/false);
222 }
223 }
224
225 // Update the next_process_time_ms_ in intervals to achieve
226 // the targeted frequency over time. Also add multiple intervals
227 // in case of a skip in time as to not make uneccessary
228 // calls to Process in order to catch up.
229 int64_t now_ms = clock_->TimeInMilliseconds();
230 if (next_process_time_ms_ == -1) {
231 next_process_time_ms_ = now_ms + kProcessIntervalMs;
232 } else {
233 next_process_time_ms_ = next_process_time_ms_ + kProcessIntervalMs +
234 (now_ms - next_process_time_ms_) /
235 kProcessIntervalMs * kProcessIntervalMs;
236 }
237 }
238
RemovePacketsUntilKeyFrame()239 bool NackModule::RemovePacketsUntilKeyFrame() {
240 while (!keyframe_list_.empty()) {
241 auto it = nack_list_.lower_bound(*keyframe_list_.begin());
242
243 if (it != nack_list_.begin()) {
244 // We have found a keyframe that actually is newer than at least one
245 // packet in the nack list.
246 nack_list_.erase(nack_list_.begin(), it);
247 return true;
248 }
249
250 // If this keyframe is so old it does not remove any packets from the list,
251 // remove it from the list of keyframes and try the next keyframe.
252 keyframe_list_.erase(keyframe_list_.begin());
253 }
254 return false;
255 }
256
AddPacketsToNack(uint16_t seq_num_start,uint16_t seq_num_end)257 void NackModule::AddPacketsToNack(uint16_t seq_num_start,
258 uint16_t seq_num_end) {
259 // Remove old packets.
260 auto it = nack_list_.lower_bound(seq_num_end - kMaxPacketAge);
261 nack_list_.erase(nack_list_.begin(), it);
262
263 // If the nack list is too large, remove packets from the nack list until
264 // the latest first packet of a keyframe. If the list is still too large,
265 // clear it and request a keyframe.
266 uint16_t num_new_nacks = ForwardDiff(seq_num_start, seq_num_end);
267 if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
268 while (RemovePacketsUntilKeyFrame() &&
269 nack_list_.size() + num_new_nacks > kMaxNackPackets) {
270 }
271
272 if (nack_list_.size() + num_new_nacks > kMaxNackPackets) {
273 nack_list_.clear();
274 RTC_LOG(LS_WARNING) << "NACK list full, clearing NACK"
275 " list and requesting keyframe.";
276 keyframe_request_sender_->RequestKeyFrame();
277 return;
278 }
279 }
280
281 for (uint16_t seq_num = seq_num_start; seq_num != seq_num_end; ++seq_num) {
282 // Do not send nack for packets that are already recovered by FEC or RTX
283 if (recovered_list_.find(seq_num) != recovered_list_.end())
284 continue;
285 NackInfo nack_info(seq_num, seq_num + WaitNumberOfPackets(0.5),
286 clock_->TimeInMilliseconds());
287 RTC_DCHECK(nack_list_.find(seq_num) == nack_list_.end());
288 nack_list_[seq_num] = nack_info;
289 }
290 }
291
GetNackBatch(NackFilterOptions options)292 std::vector<uint16_t> NackModule::GetNackBatch(NackFilterOptions options) {
293 bool consider_seq_num = options != kTimeOnly;
294 bool consider_timestamp = options != kSeqNumOnly;
295 Timestamp now = clock_->CurrentTime();
296 std::vector<uint16_t> nack_batch;
297 auto it = nack_list_.begin();
298 while (it != nack_list_.end()) {
299 TimeDelta resend_delay = TimeDelta::Millis(rtt_ms_);
300 if (backoff_settings_) {
301 resend_delay =
302 std::max(resend_delay, backoff_settings_->min_retry_interval);
303 if (it->second.retries > 1) {
304 TimeDelta exponential_backoff =
305 std::min(TimeDelta::Millis(rtt_ms_), backoff_settings_->max_rtt) *
306 std::pow(backoff_settings_->base, it->second.retries - 1);
307 resend_delay = std::max(resend_delay, exponential_backoff);
308 }
309 }
310
311 bool delay_timed_out =
312 now.ms() - it->second.created_at_time >= send_nack_delay_ms_;
313 bool nack_on_rtt_passed =
314 now.ms() - it->second.sent_at_time >= resend_delay.ms();
315 bool nack_on_seq_num_passed =
316 it->second.sent_at_time == -1 &&
317 AheadOrAt(newest_seq_num_, it->second.send_at_seq_num);
318 if (delay_timed_out && ((consider_seq_num && nack_on_seq_num_passed) ||
319 (consider_timestamp && nack_on_rtt_passed))) {
320 nack_batch.emplace_back(it->second.seq_num);
321 ++it->second.retries;
322 it->second.sent_at_time = now.ms();
323 if (it->second.retries >= kMaxNackRetries) {
324 RTC_LOG(LS_WARNING) << "Sequence number " << it->second.seq_num
325 << " removed from NACK list due to max retries.";
326 it = nack_list_.erase(it);
327 } else {
328 ++it;
329 }
330 continue;
331 }
332 ++it;
333 }
334 return nack_batch;
335 }
336
UpdateReorderingStatistics(uint16_t seq_num)337 void NackModule::UpdateReorderingStatistics(uint16_t seq_num) {
338 RTC_DCHECK(AheadOf(newest_seq_num_, seq_num));
339 uint16_t diff = ReverseDiff(newest_seq_num_, seq_num);
340 reordering_histogram_.Add(diff);
341 }
342
WaitNumberOfPackets(float probability) const343 int NackModule::WaitNumberOfPackets(float probability) const {
344 if (reordering_histogram_.NumValues() == 0)
345 return 0;
346 return reordering_histogram_.InverseCdf(probability);
347 }
348
349 } // namespace webrtc
350