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