Home | History | Annotate | Download | only in estimators 
      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