1 /*
2 * Copyright (c) 2015 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
12 // Implementation of Network-Assisted Dynamic Adaptation's (NADA's) proposal.
13 // Version according to Draft Document (mentioned in references)
14 // http://tools.ietf.org/html/draft-zhu-rmcat-nada-06
15 // From March 26, 2015.
16
17 #include <math.h>
18 #include <algorithm>
19 #include <vector>
20
21 #include "webrtc/base/arraysize.h"
22 #include "webrtc/base/common.h"
23 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/nada.h"
24 #include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h"
25 #include "webrtc/modules/rtp_rtcp/include/receive_statistics.h"
26
27 namespace webrtc {
28 namespace testing {
29 namespace bwe {
30
31 namespace {
32 // Used as an upper bound for calling AcceleratedRampDown.
33 const float kMaxCongestionSignalMs =
34 40.0f + NadaBweSender::kMinNadaBitrateKbps / 15;
35 } // namespace
36
37 const int NadaBweSender::kMinNadaBitrateKbps = 50;
38 const int64_t NadaBweReceiver::kReceivingRateTimeWindowMs = 500;
39
NadaBweReceiver(int flow_id)40 NadaBweReceiver::NadaBweReceiver(int flow_id)
41 : BweReceiver(flow_id, kReceivingRateTimeWindowMs),
42 clock_(0),
43 last_feedback_ms_(0),
44 recv_stats_(ReceiveStatistics::Create(&clock_)),
45 baseline_delay_ms_(10000), // Initialized as an upper bound.
46 delay_signal_ms_(0),
47 last_congestion_signal_ms_(0),
48 last_delays_index_(0),
49 exp_smoothed_delay_ms_(-1),
50 est_queuing_delay_signal_ms_(0) {
51 }
52
~NadaBweReceiver()53 NadaBweReceiver::~NadaBweReceiver() {
54 }
55
ReceivePacket(int64_t arrival_time_ms,const MediaPacket & media_packet)56 void NadaBweReceiver::ReceivePacket(int64_t arrival_time_ms,
57 const MediaPacket& media_packet) {
58 const float kAlpha = 0.1f; // Used for exponential smoothing.
59 const int64_t kDelayLowThresholdMs = 50; // Referred as d_th.
60 const int64_t kDelayMaxThresholdMs = 400; // Referred as d_max.
61
62 clock_.AdvanceTimeMilliseconds(arrival_time_ms - clock_.TimeInMilliseconds());
63 recv_stats_->IncomingPacket(media_packet.header(),
64 media_packet.payload_size(), false);
65 // Refered as x_n.
66 int64_t delay_ms = arrival_time_ms - media_packet.sender_timestamp_ms();
67
68 // The min should be updated within the first 10 minutes.
69 if (clock_.TimeInMilliseconds() < 10 * 60 * 1000) {
70 baseline_delay_ms_ = std::min(baseline_delay_ms_, delay_ms);
71 }
72
73 delay_signal_ms_ = delay_ms - baseline_delay_ms_; // Refered as d_n.
74 const int kMedian = arraysize(last_delays_ms_);
75 last_delays_ms_[(last_delays_index_++) % kMedian] = delay_signal_ms_;
76 int size = std::min(last_delays_index_, kMedian);
77
78 int64_t median_filtered_delay_ms_ = MedianFilter(last_delays_ms_, size);
79 exp_smoothed_delay_ms_ = ExponentialSmoothingFilter(
80 median_filtered_delay_ms_, exp_smoothed_delay_ms_, kAlpha);
81
82 if (exp_smoothed_delay_ms_ < kDelayLowThresholdMs) {
83 est_queuing_delay_signal_ms_ = exp_smoothed_delay_ms_;
84 } else if (exp_smoothed_delay_ms_ < kDelayMaxThresholdMs) {
85 est_queuing_delay_signal_ms_ = static_cast<int64_t>(
86 pow((static_cast<double>(kDelayMaxThresholdMs -
87 exp_smoothed_delay_ms_)) /
88 (kDelayMaxThresholdMs - kDelayLowThresholdMs),
89 4.0) *
90 kDelayLowThresholdMs);
91 } else {
92 est_queuing_delay_signal_ms_ = 0;
93 }
94
95 // Log received packet information.
96 BweReceiver::ReceivePacket(arrival_time_ms, media_packet);
97 }
98
GetFeedback(int64_t now_ms)99 FeedbackPacket* NadaBweReceiver::GetFeedback(int64_t now_ms) {
100 const int64_t kPacketLossPenaltyMs = 1000; // Referred as d_L.
101
102 if (now_ms - last_feedback_ms_ < 100) {
103 return NULL;
104 }
105
106 float loss_fraction = RecentPacketLossRatio();
107
108 int64_t loss_signal_ms =
109 static_cast<int64_t>(loss_fraction * kPacketLossPenaltyMs + 0.5f);
110 int64_t congestion_signal_ms = est_queuing_delay_signal_ms_ + loss_signal_ms;
111
112 float derivative = 0.0f;
113 if (last_feedback_ms_ > 0) {
114 derivative = (congestion_signal_ms - last_congestion_signal_ms_) /
115 static_cast<float>(now_ms - last_feedback_ms_);
116 }
117 last_feedback_ms_ = now_ms;
118 last_congestion_signal_ms_ = congestion_signal_ms;
119
120 int64_t corrected_send_time_ms = 0L;
121
122 if (!received_packets_.empty()) {
123 PacketIdentifierNode* latest = *(received_packets_.begin());
124 corrected_send_time_ms =
125 latest->send_time_ms + now_ms - latest->arrival_time_ms;
126 }
127
128 // Sends a tuple containing latest values of <d_hat_n, d_tilde_n, x_n, x'_n,
129 // R_r> and additional information.
130 return new NadaFeedback(flow_id_, now_ms * 1000, exp_smoothed_delay_ms_,
131 est_queuing_delay_signal_ms_, congestion_signal_ms,
132 derivative, RecentKbps(), corrected_send_time_ms);
133 }
134
135 // If size is even, the median is the average of the two middlemost numbers.
MedianFilter(int64_t * last_delays_ms,int size)136 int64_t NadaBweReceiver::MedianFilter(int64_t* last_delays_ms, int size) {
137 std::vector<int64_t> array_copy(last_delays_ms, last_delays_ms + size);
138 std::nth_element(array_copy.begin(), array_copy.begin() + size / 2,
139 array_copy.end());
140 if (size % 2 == 1) {
141 // Typically, size = 5. For odd size values, right and left are equal.
142 return array_copy.at(size / 2);
143 }
144 int64_t right = array_copy.at(size / 2);
145 std::nth_element(array_copy.begin(), array_copy.begin() + (size - 1) / 2,
146 array_copy.end());
147 int64_t left = array_copy.at((size - 1) / 2);
148 return (left + right + 1) / 2;
149 }
150
ExponentialSmoothingFilter(int64_t new_value,int64_t last_smoothed_value,float alpha)151 int64_t NadaBweReceiver::ExponentialSmoothingFilter(int64_t new_value,
152 int64_t last_smoothed_value,
153 float alpha) {
154 if (last_smoothed_value < 0) {
155 return new_value; // Handling initial case.
156 }
157 return static_cast<int64_t>(alpha * new_value +
158 (1.0f - alpha) * last_smoothed_value + 0.5f);
159 }
160
161 // Implementation according to Cisco's proposal by default.
NadaBweSender(int kbps,BitrateObserver * observer,Clock * clock)162 NadaBweSender::NadaBweSender(int kbps, BitrateObserver* observer, Clock* clock)
163 : BweSender(kbps), // Referred as "Reference Rate" = R_n.,
164 clock_(clock),
165 observer_(observer),
166 original_operating_mode_(true) {
167 }
168
NadaBweSender(BitrateObserver * observer,Clock * clock)169 NadaBweSender::NadaBweSender(BitrateObserver* observer, Clock* clock)
170 : BweSender(kMinNadaBitrateKbps), // Referred as "Reference Rate" = R_n.
171 clock_(clock),
172 observer_(observer),
173 original_operating_mode_(true) {}
174
~NadaBweSender()175 NadaBweSender::~NadaBweSender() {
176 }
177
GetFeedbackIntervalMs() const178 int NadaBweSender::GetFeedbackIntervalMs() const {
179 return 100;
180 }
181
GiveFeedback(const FeedbackPacket & feedback)182 void NadaBweSender::GiveFeedback(const FeedbackPacket& feedback) {
183 const NadaFeedback& fb = static_cast<const NadaFeedback&>(feedback);
184
185 // Following parameters might be optimized.
186 const int64_t kQueuingDelayUpperBoundMs = 10;
187 const float kDerivativeUpperBound =
188 10.0f / std::max<int64_t>(1, min_feedback_delay_ms_);
189 // In the modified version, a higher kMinUpperBound allows a higher d_hat
190 // upper bound for calling AcceleratedRampUp.
191 const float kProportionalityDelayBits = 20.0f;
192
193 int64_t now_ms = clock_->TimeInMilliseconds();
194 float delta_s = now_ms - last_feedback_ms_;
195 last_feedback_ms_ = now_ms;
196 // Update delta_0.
197 min_feedback_delay_ms_ =
198 std::min(min_feedback_delay_ms_, static_cast<int64_t>(delta_s));
199
200 // Update RTT_0.
201 int64_t rtt_ms = now_ms - fb.latest_send_time_ms();
202 min_round_trip_time_ms_ = std::min(min_round_trip_time_ms_, rtt_ms);
203
204 // Independent limits for AcceleratedRampUp conditions variables:
205 // x_n, d_tilde and x'_n in the original implementation, plus
206 // d_hat and receiving_rate in the modified one.
207 // There should be no packet losses/marking, hence x_n == d_tilde.
208 if (original_operating_mode_) {
209 // Original if conditions and rate update.
210 if (fb.congestion_signal() == fb.est_queuing_delay_signal_ms() &&
211 fb.est_queuing_delay_signal_ms() < kQueuingDelayUpperBoundMs &&
212 fb.derivative() < kDerivativeUpperBound) {
213 AcceleratedRampUp(fb);
214 } else {
215 GradualRateUpdate(fb, delta_s, 1.0);
216 }
217 } else {
218 // Modified if conditions and rate update; new ramp down mode.
219 if (fb.congestion_signal() == fb.est_queuing_delay_signal_ms() &&
220 fb.est_queuing_delay_signal_ms() < kQueuingDelayUpperBoundMs &&
221 fb.exp_smoothed_delay_ms() <
222 kMinNadaBitrateKbps / kProportionalityDelayBits &&
223 fb.derivative() < kDerivativeUpperBound &&
224 fb.receiving_rate() > kMinNadaBitrateKbps) {
225 AcceleratedRampUp(fb);
226 } else if (fb.congestion_signal() > kMaxCongestionSignalMs ||
227 fb.exp_smoothed_delay_ms() > kMaxCongestionSignalMs) {
228 AcceleratedRampDown(fb);
229 } else {
230 double bitrate_reference =
231 (2.0 * bitrate_kbps_) / (kMaxBitrateKbps + kMinNadaBitrateKbps);
232 double smoothing_factor = pow(bitrate_reference, 0.75);
233 GradualRateUpdate(fb, delta_s, smoothing_factor);
234 }
235 }
236
237 bitrate_kbps_ = std::min(bitrate_kbps_, kMaxBitrateKbps);
238 bitrate_kbps_ = std::max(bitrate_kbps_, kMinNadaBitrateKbps);
239
240 observer_->OnNetworkChanged(1000 * bitrate_kbps_, 0, rtt_ms);
241 }
242
TimeUntilNextProcess()243 int64_t NadaBweSender::TimeUntilNextProcess() {
244 return 100;
245 }
246
Process()247 void NadaBweSender::Process() {
248 }
249
AcceleratedRampUp(const NadaFeedback & fb)250 void NadaBweSender::AcceleratedRampUp(const NadaFeedback& fb) {
251 const int kMaxRampUpQueuingDelayMs = 50; // Referred as T_th.
252 const float kGamma0 = 0.5f; // Referred as gamma_0.
253
254 float gamma =
255 std::min(kGamma0, static_cast<float>(kMaxRampUpQueuingDelayMs) /
256 (min_round_trip_time_ms_ + min_feedback_delay_ms_));
257
258 bitrate_kbps_ = static_cast<int>((1.0f + gamma) * fb.receiving_rate() + 0.5f);
259 }
260
AcceleratedRampDown(const NadaFeedback & fb)261 void NadaBweSender::AcceleratedRampDown(const NadaFeedback& fb) {
262 const float kGamma0 = 0.9f;
263 float gamma = 3.0f * kMaxCongestionSignalMs /
264 (fb.congestion_signal() + fb.exp_smoothed_delay_ms());
265 gamma = std::min(gamma, kGamma0);
266 bitrate_kbps_ = gamma * fb.receiving_rate() + 0.5f;
267 }
268
GradualRateUpdate(const NadaFeedback & fb,float delta_s,double smoothing_factor)269 void NadaBweSender::GradualRateUpdate(const NadaFeedback& fb,
270 float delta_s,
271 double smoothing_factor) {
272 const float kTauOMs = 500.0f; // Referred as tau_o.
273 const float kEta = 2.0f; // Referred as eta.
274 const float kKappa = 1.0f; // Referred as kappa.
275 const float kReferenceDelayMs = 10.0f; // Referred as x_ref.
276 const float kPriorityWeight = 1.0f; // Referred as w.
277
278 float x_hat = fb.congestion_signal() + kEta * kTauOMs * fb.derivative();
279
280 float kTheta = kPriorityWeight * (kMaxBitrateKbps - kMinNadaBitrateKbps) *
281 kReferenceDelayMs;
282
283 int original_increase = static_cast<int>(
284 (kKappa * delta_s *
285 (kTheta - (bitrate_kbps_ - kMinNadaBitrateKbps) * x_hat)) /
286 (kTauOMs * kTauOMs) +
287 0.5f);
288
289 bitrate_kbps_ = bitrate_kbps_ + smoothing_factor * original_increase;
290 }
291
292 } // namespace bwe
293 } // namespace testing
294 } // namespace webrtc
295