• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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