OLD | NEW |
1 /* | 1 /* |
2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. | 2 * Copyright (c) 2015 The WebRTC project authors. All Rights Reserved. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license | 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 | 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 | 6 * tree. An additional intellectual property rights grant can be found |
7 * in the file PATENTS. All contributing project authors may | 7 * in the file PATENTS. All contributing project authors may |
8 * be found in the AUTHORS file in the root of the source tree. | 8 * be found in the AUTHORS file in the root of the source tree. |
9 * | 9 * |
10 */ | 10 */ |
11 | 11 |
12 // Implementation of Network-Assisted Dynamic Adaptation's (NADA's) proposal. | 12 // Implementation of Network-Assisted Dynamic Adaptation's (NADA's) proposal. |
13 // Version according to Draft Document (mentioned in references) | 13 // Version according to Draft Document (mentioned in references) |
14 // http://tools.ietf.org/html/draft-zhu-rmcat-nada-06 | 14 // http://tools.ietf.org/html/draft-zhu-rmcat-nada-06 |
15 // From March 26, 2015. | 15 // From March 26, 2015. |
16 | 16 |
17 #include <math.h> | 17 #include <math.h> |
18 #include <algorithm> | 18 #include <algorithm> |
19 #include <vector> | 19 #include <vector> |
20 #include <iostream> | |
21 | 20 |
22 #include "webrtc/base/common.h" | 21 #include "webrtc/base/common.h" |
23 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/nada.h" | 22 #include "webrtc/modules/remote_bitrate_estimator/test/estimators/nada.h" |
24 #include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h" | 23 #include "webrtc/modules/remote_bitrate_estimator/test/bwe_test_logging.h" |
25 #include "webrtc/modules/rtp_rtcp/interface/receive_statistics.h" | 24 #include "webrtc/modules/rtp_rtcp/interface/receive_statistics.h" |
26 | 25 |
27 namespace webrtc { | 26 namespace webrtc { |
28 namespace testing { | 27 namespace testing { |
29 namespace bwe { | 28 namespace bwe { |
30 | 29 |
31 const int NadaBweSender::kMinRefRateKbps = 150; | |
32 const int NadaBweSender::kMaxRefRateKbps = 1500; | |
33 const int64_t NadaBweReceiver::kReceivingRateTimeWindowMs = 500; | 30 const int64_t NadaBweReceiver::kReceivingRateTimeWindowMs = 500; |
34 | 31 |
35 NadaBweReceiver::NadaBweReceiver(int flow_id) | 32 NadaBweReceiver::NadaBweReceiver(int flow_id) |
36 : BweReceiver(flow_id), | 33 : BweReceiver(flow_id, kReceivingRateTimeWindowMs), |
37 clock_(0), | 34 clock_(0), |
38 last_feedback_ms_(0), | 35 last_feedback_ms_(0), |
39 recv_stats_(ReceiveStatistics::Create(&clock_)), | 36 recv_stats_(ReceiveStatistics::Create(&clock_)), |
40 baseline_delay_ms_(0), | 37 baseline_delay_ms_(10000), // Initialized as an upper bound. |
41 delay_signal_ms_(0), | 38 delay_signal_ms_(0), |
42 last_congestion_signal_ms_(0), | 39 last_congestion_signal_ms_(0), |
43 last_delays_index_(0), | 40 last_delays_index_(0), |
44 exp_smoothed_delay_ms_(-1), | 41 exp_smoothed_delay_ms_(-1), |
45 est_queuing_delay_signal_ms_(0) { | 42 est_queuing_delay_signal_ms_(0) { |
46 } | 43 } |
47 | 44 |
48 NadaBweReceiver::~NadaBweReceiver() { | 45 NadaBweReceiver::~NadaBweReceiver() { |
49 } | 46 } |
50 | 47 |
51 void NadaBweReceiver::ReceivePacket(int64_t arrival_time_ms, | 48 void NadaBweReceiver::ReceivePacket(int64_t arrival_time_ms, |
52 const MediaPacket& media_packet) { | 49 const MediaPacket& media_packet) { |
53 const float kAlpha = 0.1f; // Used for exponential smoothing. | 50 const float kAlpha = 0.1f; // Used for exponential smoothing. |
54 const int64_t kDelayLowThresholdMs = 50; // Referred as d_th. | 51 const int64_t kDelayLowThresholdMs = 50; // Referred as d_th. |
55 const int64_t kDelayMaxThresholdMs = 400; // Referred as d_max. | 52 const int64_t kDelayMaxThresholdMs = 400; // Referred as d_max. |
56 | 53 |
57 clock_.AdvanceTimeMilliseconds(arrival_time_ms - clock_.TimeInMilliseconds()); | 54 clock_.AdvanceTimeMilliseconds(arrival_time_ms - clock_.TimeInMilliseconds()); |
58 recv_stats_->IncomingPacket(media_packet.header(), | 55 recv_stats_->IncomingPacket(media_packet.header(), |
59 media_packet.payload_size(), false); | 56 media_packet.payload_size(), false); |
60 int64_t delay_ms = arrival_time_ms - | 57 // Refered as x_n. |
61 media_packet.creation_time_us() / 1000; // Refered as x_n. | 58 int64_t delay_ms = arrival_time_ms - media_packet.sender_timestamp_ms(); |
| 59 |
62 // The min should be updated within the first 10 minutes. | 60 // The min should be updated within the first 10 minutes. |
63 if (clock_.TimeInMilliseconds() < 10 * 60 * 1000) { | 61 if (clock_.TimeInMilliseconds() < 10 * 60 * 1000) { |
64 baseline_delay_ms_ = std::min(baseline_delay_ms_, delay_ms); | 62 baseline_delay_ms_ = std::min(baseline_delay_ms_, delay_ms); |
65 } | 63 } |
| 64 |
66 delay_signal_ms_ = delay_ms - baseline_delay_ms_; // Refered as d_n. | 65 delay_signal_ms_ = delay_ms - baseline_delay_ms_; // Refered as d_n. |
67 const int kMedian = ARRAY_SIZE(last_delays_ms_); | 66 const int kMedian = ARRAY_SIZE(last_delays_ms_); |
68 last_delays_ms_[(last_delays_index_++) % kMedian] = delay_signal_ms_; | 67 last_delays_ms_[(last_delays_index_++) % kMedian] = delay_signal_ms_; |
69 int size = std::min(last_delays_index_, kMedian); | 68 int size = std::min(last_delays_index_, kMedian); |
| 69 |
70 int64_t median_filtered_delay_ms_ = MedianFilter(last_delays_ms_, size); | 70 int64_t median_filtered_delay_ms_ = MedianFilter(last_delays_ms_, size); |
71 exp_smoothed_delay_ms_ = ExponentialSmoothingFilter( | 71 exp_smoothed_delay_ms_ = ExponentialSmoothingFilter( |
72 median_filtered_delay_ms_, exp_smoothed_delay_ms_, kAlpha); | 72 median_filtered_delay_ms_, exp_smoothed_delay_ms_, kAlpha); |
73 | 73 |
74 if (exp_smoothed_delay_ms_ < kDelayLowThresholdMs) { | 74 if (exp_smoothed_delay_ms_ < kDelayLowThresholdMs) { |
75 est_queuing_delay_signal_ms_ = exp_smoothed_delay_ms_; | 75 est_queuing_delay_signal_ms_ = exp_smoothed_delay_ms_; |
76 } else if (exp_smoothed_delay_ms_ < kDelayMaxThresholdMs) { | 76 } else if (exp_smoothed_delay_ms_ < kDelayMaxThresholdMs) { |
77 est_queuing_delay_signal_ms_ = static_cast<int64_t>( | 77 est_queuing_delay_signal_ms_ = static_cast<int64_t>( |
78 pow((static_cast<double>(kDelayMaxThresholdMs - | 78 pow((static_cast<double>(kDelayMaxThresholdMs - |
79 exp_smoothed_delay_ms_)) / | 79 exp_smoothed_delay_ms_)) / |
80 (kDelayMaxThresholdMs - kDelayLowThresholdMs), | 80 (kDelayMaxThresholdMs - kDelayLowThresholdMs), |
81 4.0) * | 81 4.0) * |
82 kDelayLowThresholdMs); | 82 kDelayLowThresholdMs); |
83 } else { | 83 } else { |
84 est_queuing_delay_signal_ms_ = 0; | 84 est_queuing_delay_signal_ms_ = 0; |
85 } | 85 } |
86 | 86 |
87 received_packets_.Insert(media_packet.sequence_number(), | 87 // Log received packet information. |
88 media_packet.send_time_ms(), arrival_time_ms, | 88 BweReceiver::ReceivePacket(arrival_time_ms, media_packet); |
89 media_packet.payload_size()); | |
90 } | 89 } |
91 | 90 |
92 FeedbackPacket* NadaBweReceiver::GetFeedback(int64_t now_ms) { | 91 FeedbackPacket* NadaBweReceiver::GetFeedback(int64_t now_ms) { |
93 const int64_t kPacketLossPenaltyMs = 1000; // Referred as d_L. | 92 const int64_t kPacketLossPenaltyMs = 1000; // Referred as d_L. |
94 | 93 |
95 if (now_ms - last_feedback_ms_ < 100) { | 94 if (now_ms - last_feedback_ms_ < 100) { |
96 return NULL; | 95 return NULL; |
97 } | 96 } |
98 | 97 |
99 float loss_fraction = RecentPacketLossRatio(); | 98 float loss_fraction = RecentPacketLossRatio(); |
100 | 99 |
101 int64_t loss_signal_ms = | 100 int64_t loss_signal_ms = |
102 static_cast<int64_t>(loss_fraction * kPacketLossPenaltyMs + 0.5f); | 101 static_cast<int64_t>(loss_fraction * kPacketLossPenaltyMs + 0.5f); |
103 int64_t congestion_signal_ms = est_queuing_delay_signal_ms_ + loss_signal_ms; | 102 int64_t congestion_signal_ms = est_queuing_delay_signal_ms_ + loss_signal_ms; |
104 | 103 |
105 float derivative = 0.0f; | 104 float derivative = 0.0f; |
106 if (last_feedback_ms_ > 0) { | 105 if (last_feedback_ms_ > 0) { |
107 derivative = (congestion_signal_ms - last_congestion_signal_ms_) / | 106 derivative = (congestion_signal_ms - last_congestion_signal_ms_) / |
108 static_cast<float>(now_ms - last_feedback_ms_); | 107 static_cast<float>(now_ms - last_feedback_ms_); |
109 } | 108 } |
110 last_feedback_ms_ = now_ms; | 109 last_feedback_ms_ = now_ms; |
111 last_congestion_signal_ms_ = congestion_signal_ms; | 110 last_congestion_signal_ms_ = congestion_signal_ms; |
112 | 111 |
113 PacketIdentifierNode* latest = *(received_packets_.begin()); | 112 int64_t corrected_send_time_ms = 0L; |
114 int64_t corrected_send_time_ms = | 113 |
115 latest->send_time_ms + now_ms - latest->arrival_time_ms; | 114 if (!received_packets_.empty()) { |
| 115 PacketIdentifierNode* latest = *(received_packets_.begin()); |
| 116 corrected_send_time_ms = |
| 117 latest->send_time_ms + now_ms - latest->arrival_time_ms; |
| 118 } |
116 | 119 |
117 // Sends a tuple containing latest values of <d_hat_n, d_tilde_n, x_n, x'_n, | 120 // Sends a tuple containing latest values of <d_hat_n, d_tilde_n, x_n, x'_n, |
118 // R_r> and additional information. | 121 // R_r> and additional information. |
119 return new NadaFeedback(flow_id_, now_ms, exp_smoothed_delay_ms_, | 122 return new NadaFeedback(flow_id_, now_ms * 1000, exp_smoothed_delay_ms_, |
120 est_queuing_delay_signal_ms_, congestion_signal_ms, | 123 est_queuing_delay_signal_ms_, congestion_signal_ms, |
121 derivative, RecentReceivingRate(), | 124 derivative, RecentKbps(), corrected_send_time_ms); |
122 corrected_send_time_ms); | |
123 } | |
124 | |
125 // For a given time window, compute the receiving speed rate in kbps. | |
126 // As described below, three cases are considered depending on the number of | |
127 // packets received. | |
128 size_t NadaBweReceiver::RecentReceivingRate() { | |
129 // If the receiver didn't receive any packet, return 0. | |
130 if (received_packets_.empty()) { | |
131 return 0.0f; | |
132 } | |
133 size_t total_size = 0; | |
134 int number_packets = 0; | |
135 | |
136 PacketNodeIt node_it = received_packets_.begin(); | |
137 | |
138 int64_t last_time_ms = (*node_it)->arrival_time_ms; | |
139 int64_t start_time_ms = last_time_ms; | |
140 PacketNodeIt end = received_packets_.end(); | |
141 | |
142 // Stops after including the first packet out of the timeWindow. | |
143 // Ameliorates results when there are wide gaps between packets. | |
144 // E.g. Large packets : p1(0ms), p2(3000ms). | |
145 while (node_it != end) { | |
146 total_size += (*node_it)->payload_size; | |
147 last_time_ms = (*node_it)->arrival_time_ms; | |
148 ++number_packets; | |
149 if ((*node_it)->arrival_time_ms < | |
150 start_time_ms - kReceivingRateTimeWindowMs) { | |
151 break; | |
152 } | |
153 ++node_it; | |
154 } | |
155 | |
156 int64_t corrected_time_ms; | |
157 // If the receiver received a single packet, return its size*8/timeWindow. | |
158 if (number_packets == 1) { | |
159 corrected_time_ms = kReceivingRateTimeWindowMs; | |
160 } | |
161 // If the receiver received multiple packets, use as time interval the gap | |
162 // between first and last packet falling in the timeWindow corrected by the | |
163 // factor number_packets/(number_packets-1). | |
164 // E.g: Let timeWindow = 500ms, payload_size = 500 bytes, number_packets = 2, | |
165 // packets received at t1(0ms) and t2(499 or 501ms). This prevent the function | |
166 // from returning ~2*8, sending instead a more likely ~1*8 kbps. | |
167 else { | |
168 corrected_time_ms = (number_packets * (start_time_ms - last_time_ms)) / | |
169 (number_packets - 1); | |
170 } | |
171 | |
172 // Converting from bytes/ms to kbits/s. | |
173 return static_cast<size_t>(8 * total_size / corrected_time_ms); | |
174 } | 125 } |
175 | 126 |
176 int64_t NadaBweReceiver::MedianFilter(int64_t* last_delays_ms, int size) { | 127 int64_t NadaBweReceiver::MedianFilter(int64_t* last_delays_ms, int size) { |
177 // Typically, size = 5. | 128 // Typically, size = 5. |
178 std::vector<int64_t> array_copy(last_delays_ms, last_delays_ms + size); | 129 std::vector<int64_t> array_copy(last_delays_ms, last_delays_ms + size); |
179 std::nth_element(array_copy.begin(), array_copy.begin() + size / 2, | 130 std::nth_element(array_copy.begin(), array_copy.begin() + size / 2, |
180 array_copy.end()); | 131 array_copy.end()); |
181 return array_copy.at(size / 2); | 132 return array_copy.at(size / 2); |
182 } | 133 } |
183 | 134 |
184 int64_t NadaBweReceiver::ExponentialSmoothingFilter(int64_t new_value, | 135 int64_t NadaBweReceiver::ExponentialSmoothingFilter(int64_t new_value, |
185 int64_t last_smoothed_value, | 136 int64_t last_smoothed_value, |
186 float alpha) { | 137 float alpha) { |
187 if (last_smoothed_value < 0) { | 138 if (last_smoothed_value < 0) { |
188 return new_value; // Handling initial case. | 139 return new_value; // Handling initial case. |
189 } | 140 } |
190 return static_cast<int64_t>(alpha * new_value + | 141 return static_cast<int64_t>(alpha * new_value + |
191 (1.0f - alpha) * last_smoothed_value + 0.5f); | 142 (1.0f - alpha) * last_smoothed_value + 0.5f); |
192 } | 143 } |
193 | 144 |
194 // Implementation according to Cisco's proposal by default. | 145 // Implementation according to Cisco's proposal by default. |
195 NadaBweSender::NadaBweSender(int kbps, BitrateObserver* observer, Clock* clock) | 146 NadaBweSender::NadaBweSender(int kbps, BitrateObserver* observer, Clock* clock) |
196 : clock_(clock), | 147 : BweSender(kbps), // Referred as "Reference Rate" = R_n., |
| 148 clock_(clock), |
197 observer_(observer), | 149 observer_(observer), |
198 bitrate_kbps_(kbps), | |
199 original_operating_mode_(true) { | 150 original_operating_mode_(true) { |
200 } | 151 } |
201 | 152 |
202 NadaBweSender::NadaBweSender(BitrateObserver* observer, Clock* clock) | 153 NadaBweSender::NadaBweSender(BitrateObserver* observer, Clock* clock) |
203 : clock_(clock), | 154 : BweSender(kMinBitrateKbps), // Referred as "Reference Rate" = R_n. |
| 155 clock_(clock), |
204 observer_(observer), | 156 observer_(observer), |
205 bitrate_kbps_(kMinRefRateKbps), | |
206 original_operating_mode_(true) { | 157 original_operating_mode_(true) { |
207 } | 158 } |
208 | 159 |
209 NadaBweSender::~NadaBweSender() { | 160 NadaBweSender::~NadaBweSender() { |
210 } | 161 } |
211 | 162 |
212 int NadaBweSender::GetFeedbackIntervalMs() const { | 163 int NadaBweSender::GetFeedbackIntervalMs() const { |
213 return 100; | 164 return 100; |
214 } | 165 } |
215 | 166 |
(...skipping 29 matching lines...) Expand all Loading... |
245 fb.derivative() < kDerivativeUpperBound) { | 196 fb.derivative() < kDerivativeUpperBound) { |
246 AcceleratedRampUp(fb); | 197 AcceleratedRampUp(fb); |
247 } else { | 198 } else { |
248 GradualRateUpdate(fb, delta_s, 1.0); | 199 GradualRateUpdate(fb, delta_s, 1.0); |
249 } | 200 } |
250 } else { | 201 } else { |
251 // Modified if conditions and rate update; new ramp down mode. | 202 // Modified if conditions and rate update; new ramp down mode. |
252 if (fb.congestion_signal() == fb.est_queuing_delay_signal_ms() && | 203 if (fb.congestion_signal() == fb.est_queuing_delay_signal_ms() && |
253 fb.est_queuing_delay_signal_ms() < kQueuingDelayUpperBoundMs && | 204 fb.est_queuing_delay_signal_ms() < kQueuingDelayUpperBoundMs && |
254 fb.exp_smoothed_delay_ms() < | 205 fb.exp_smoothed_delay_ms() < |
255 kMinRefRateKbps / kProportionalityDelayBits && | 206 kMinBitrateKbps / kProportionalityDelayBits && |
256 fb.derivative() < kDerivativeUpperBound && | 207 fb.derivative() < kDerivativeUpperBound && |
257 fb.receiving_rate() > kMinRefRateKbps) { | 208 fb.receiving_rate() > kMinBitrateKbps) { |
258 AcceleratedRampUp(fb); | 209 AcceleratedRampUp(fb); |
259 } else if (fb.congestion_signal() > kMaxCongestionSignalMs || | 210 } else if (fb.congestion_signal() > kMaxCongestionSignalMs || |
260 fb.exp_smoothed_delay_ms() > kMaxCongestionSignalMs) { | 211 fb.exp_smoothed_delay_ms() > kMaxCongestionSignalMs) { |
261 AcceleratedRampDown(fb); | 212 AcceleratedRampDown(fb); |
262 } else { | 213 } else { |
263 double bitrate_reference = | 214 double bitrate_reference = |
264 (2.0 * bitrate_kbps_) / (kMaxRefRateKbps + kMinRefRateKbps); | 215 (2.0 * bitrate_kbps_) / (kMaxBitrateKbps + kMinBitrateKbps); |
265 double smoothing_factor = pow(bitrate_reference, 0.75); | 216 double smoothing_factor = pow(bitrate_reference, 0.75); |
266 GradualRateUpdate(fb, delta_s, smoothing_factor); | 217 GradualRateUpdate(fb, delta_s, smoothing_factor); |
267 } | 218 } |
268 } | 219 } |
269 | 220 |
270 bitrate_kbps_ = std::min(bitrate_kbps_, kMaxRefRateKbps); | 221 bitrate_kbps_ = std::min(bitrate_kbps_, kMaxBitrateKbps); |
271 bitrate_kbps_ = std::max(bitrate_kbps_, kMinRefRateKbps); | 222 bitrate_kbps_ = std::max(bitrate_kbps_, kMinBitrateKbps); |
272 | 223 |
273 observer_->OnNetworkChanged(1000 * bitrate_kbps_, 0, rtt_ms); | 224 observer_->OnNetworkChanged(1000 * bitrate_kbps_, 0, rtt_ms); |
274 } | 225 } |
275 | 226 |
276 int64_t NadaBweSender::TimeUntilNextProcess() { | 227 int64_t NadaBweSender::TimeUntilNextProcess() { |
277 return 100; | 228 return 100; |
278 } | 229 } |
279 | 230 |
280 int NadaBweSender::Process() { | 231 int NadaBweSender::Process() { |
281 return 0; | 232 return 0; |
(...skipping 23 matching lines...) Expand all Loading... |
305 double smoothing_factor) { | 256 double smoothing_factor) { |
306 const float kTauOMs = 500.0f; // Referred as tau_o. | 257 const float kTauOMs = 500.0f; // Referred as tau_o. |
307 const float kEta = 2.0f; // Referred as eta. | 258 const float kEta = 2.0f; // Referred as eta. |
308 const float kKappa = 1.0f; // Referred as kappa. | 259 const float kKappa = 1.0f; // Referred as kappa. |
309 const float kReferenceDelayMs = 10.0f; // Referred as x_ref. | 260 const float kReferenceDelayMs = 10.0f; // Referred as x_ref. |
310 const float kPriorityWeight = 1.0f; // Referred as w. | 261 const float kPriorityWeight = 1.0f; // Referred as w. |
311 | 262 |
312 float x_hat = fb.congestion_signal() + kEta * kTauOMs * fb.derivative(); | 263 float x_hat = fb.congestion_signal() + kEta * kTauOMs * fb.derivative(); |
313 | 264 |
314 float kTheta = | 265 float kTheta = |
315 kPriorityWeight * (kMaxRefRateKbps - kMinRefRateKbps) * kReferenceDelayMs; | 266 kPriorityWeight * (kMaxBitrateKbps - kMinBitrateKbps) * kReferenceDelayMs; |
316 | 267 |
317 int original_increase = | 268 int original_increase = |
318 static_cast<int>((kKappa * delta_s * | 269 static_cast<int>((kKappa * delta_s * |
319 (kTheta - (bitrate_kbps_ - kMinRefRateKbps) * x_hat)) / | 270 (kTheta - (bitrate_kbps_ - kMinBitrateKbps) * x_hat)) / |
320 (kTauOMs * kTauOMs) + | 271 (kTauOMs * kTauOMs) + |
321 0.5f); | 272 0.5f); |
322 | 273 |
323 bitrate_kbps_ = bitrate_kbps_ + smoothing_factor * original_increase; | 274 bitrate_kbps_ = bitrate_kbps_ + smoothing_factor * original_increase; |
324 } | 275 } |
325 | 276 |
326 } // namespace bwe | 277 } // namespace bwe |
327 } // namespace testing | 278 } // namespace testing |
328 } // namespace webrtc | 279 } // namespace webrtc |
OLD | NEW |