深入浅出WebRTC—DelayBasedBwe

WebRTC 中的带宽估计是其拥塞控制机制的核心组成部分,基于延迟的带宽估计是其中的一种策略,它主要基于延迟变化推断出可用的网络带宽。

1. 总体架构

1.1. 静态结构

1)DelayBasedBwe 受 GoogCcNetworkController 控制,接收其输入并返回带宽估计值。

2)DelayBasedBwe 内部使用 InterArrivalDelta、TrendlineEstimator 和 AimdRateControl 来完成带宽估计。

3)InterArrivalDelta 用来计算到达时间延迟。

4)TrendlineEstimator 根据到达时间延迟判断带宽使用是否过载。

5)AimdRateControl 内部运行一个状态机,根据状态机不断调整带宽估计值。

1.2. 调用流程

1)GoogCcNetworkController 收到 TransportFeedback,调用 DelayBasedBwe::IncomingPacketFeedbackVector 来计算基于延迟的带宽估计值。

2)DelaybasedBwe 调用 InterArralDelta::ComputeDeltas 计算延迟差值。

3)DelaybasedBwe 调用 TrendlineEstimator::Update 传入延迟差值计算得到带宽过载情况。

4)DelaybasedBwe 调用 AimdRateControl::Udpate 传入带宽过载情况计算得到延迟带宽估计值。

5)GoogCcNetworkController 调用 SendSideBandwidthEstimation::UpdateDelayBasedEstimate 传入延迟带宽估计值,融合基于丢包的带宽估计值,获得最终的带宽估计值。

1.3. 逻辑架构

1)DelayBaseBWE 接收一坨输入,经过计算输出DelayBasedBwe::Result(见 DelayBasedBwe 数据结构)。

2)InterArrivalDlata 基于 TransportFeedback 计算延迟差。

3)TrendLineEstimator 基于延迟差计算 BandwidthUsage。

4)LinkCapacityEstimator 基于过载状态下的 ACK 码率估算链路容量并计算 3sigma 上下界。当AIMD 升码率时,基于链路容量估计值来决定是采用加性增还是乘性增。当 AIMD 降码率时,下降之后的码率不能高于链路容量估计值。3sigma 上下界用来判断当前链路容量估计值的有效性,如果新的 ACK 码率超出 3sigma 范围,则链路容量估计值要重置并重新进行估算。

5)DelayBaseBWE 设置 ALR 状态到 AimdRateControl,当根据带宽使用情况决策应该要升码率时,如果此时进入了 ALR 状态,不允许升码率,和之前码率保持一致。

6)网络非过载状态下,DelayBaseBWE 设置 Probe bitrate 到 AimdRateControl,用探测带宽更新估计值。此时探测带宽很可能是链路的真实带宽,这样更新是合理的。

7)AimdRateControl 使用 TrendLineEstimator 输出的 BandwidthUsage 更来状态机状态,然后根据新的控制状态来更新带宽估计值,如果是 kRcHold 则保持估计值不变,如果是 kRcIncrease 则采用加性增或乘性增来增加带宽估计值,如果是 kRcDecrease 则降低估计值。

DelayBaseBWE 在调用 AimdRateControl 之前,会根据 BandwidthUsage 进行前处理:

1)如果链路处于 overusing 状态,且没有可用的 ACK 码率,则估计值砍半,这个频率(间隔)由 RTT 决定。

2)如果链路处于normal/underusing 状态,且有可用的探测带宽,则使用探测带宽更新估计值。

其他情况,才会更新 AimdRateControl 状态机,由 AimdRateControl 给出带宽估计值。

2. DelayBasedBwe

2.1. 重要属性

1)video_inter_arrival_

用来计算报文到达延迟差。

2)video_delay_detector_

TrendLineEstimator,用来检测链路过载状态。

3)rate_control_

根据链路过载状态及其变化来对带宽进行估计。

2.2. 重要方法

1)IncomingPacketFeedbackVector

传入 TransportFeedback 以计算报文到达延迟差,同时还会传入 ACK 码率、探测码率和 ALR 状态。

2)OnRttUpdate

更新链路 RTT,AimdRateControl 使用。

3)LatestEstimate

从 AimdRateControl 获取最近延迟带宽估计值。

4)SetStartBitrate

设置 AimdRateControl 的起始码率。

5)SetMinBitrate

设置 AimdRateControl 的最小码率。

2.3. 数据结构

带宽使用有正常、欠载和过载三种状态。

enum class BandwidthUsage {kBwNormal = 0,kBwUnderusing = 1,kBwOverusing = 2,kLast
};

延迟带宽估计器返回值。

struct DelayBasedBwe::Result {// 带宽估计值是否有更新bool updated = false;// 是否是使用探测值进行的更新bool probe = false;// 更新后的目标码率估计值DataRate target_bitrate = DataRate::Zero();// 是否是从过载恢复bool recovered_from_overuse = false;// 根据算法计算得到的带宽使用情况BandwidthUsage delay_detector_state = BandwidthUsage::kBwNormal;
};

2.4. 源码分析

2.4.1. IncomingPacketFeedbackVector

收到 TransportFeedback 后,使用延迟差值更新趋势线估计器,更新 ALR 状态,然后调用 MaybeUpdateEstimate 获取估计结果。

DelayBasedBwe::Result DelayBasedBwe::IncomingPacketFeedbackVector(const TransportPacketsFeedback& msg,absl::optional<DataRate> acked_bitrate,absl::optional<DataRate> probe_bitrate,absl::optional<NetworkStateEstimate> network_estimate,bool in_alr) {// 按时间进行排序auto packet_feedback_vector = msg.SortedByReceiveTime();...// 逐个处理feedbackfor (const auto& packet_feedback : packet_feedback_vector) {delayed_feedback = false;// 计算时延delta,并更新detector状态IncomingPacketFeedback(packet_feedback, msg.feedback_time);// 网络状态从欠载状态到正常状态,说明已经恢复if (prev_detector_state == BandwidthUsage::kBwUnderusing &&active_delay_detector_->State() == BandwidthUsage::kBwNormal) {recovered_from_overuse = true;}prev_detector_state = active_delay_detector_->State();}// 更新ALR状态rate_control_.SetInApplicationLimitedRegion(in_alr);// 从AIMD获取目标码率return MaybeUpdateEstimate(acked_bitrate, probe_bitrate,std::move(network_estimate),recovered_from_overuse, in_alr, msg.feedback_time);
}

2.4.2. MaybeUpdateEstimate

1)在没有获取到 ACK 码率的情况下,如果网络过载,算法简单粗暴,每 200ms 下降 50%。在未获得测量值的前提下,保守处理比较好。

2)在获得探测码率的情况下,如果网络不过载,则使用探测码率更新估计值。这是因为探测码率是通过主动探测获得的,它能更快、更真实地反映网络当前的实际承载能力。

DelayBasedBwe::Result DelayBasedBwe::MaybeUpdateEstimate(absl::optional<DataRate> acked_bitrate,absl::optional<DataRate> probe_bitrate,absl::optional<NetworkStateEstimate> state_estimate,bool recovered_from_overuse,bool in_alr,Timestamp at_time) {Result result;// 网络过载,需要降码率if (active_delay_detector_->State() == BandwidthUsage::kBwOverusing) {if (acked_bitrate && rate_control_.TimeToReduceFurther(at_time, *acked_bitrate)) {// 已经获取ACK码率,且符合调整频率限制,基于 ACK 码率更新估计码率result.updated = UpdateEstimate(at_time, acked_bitrate, &result.target_bitrate);} else if (!acked_bitrate && rate_control_.ValidEstimate() &&rate_control_.InitialTimeToReduceFurther(at_time)) {// 未获得 ACK 码率,码率下降 50%rate_control_.SetEstimate(rate_control_.LatestEstimate() / 2, at_time);result.updated = true;result.probe = false;result.target_bitrate = rate_control_.LatestEstimate();}// 网络欠载或正常} else {// 已经获得了探测码率,则使用探测码率更新AIMD的估计值if (probe_bitrate) {result.probe = true;result.updated = true;rate_control_.SetEstimate(*probe_bitrate, at_time);result.target_bitrate = rate_control_.LatestEstimate();} else {// 没有探测码率,则由AIMD基于ACK码率计算估计码率result.updated =UpdateEstimate(at_time, acked_bitrate, &result.target_bitrate);result.recovered_from_overuse = recovered_from_overuse;}}BandwidthUsage detector_state = active_delay_detector_->State();// 更新内部状态if ((result.updated && prev_bitrate_ != result.target_bitrate) ||detector_state != prev_state_) {DataRate bitrate = result.updated ? result.target_bitrate : prev_bitrate_;prev_bitrate_ = bitrate;prev_state_ = detector_state;}result.delay_detector_state = detector_state;return result;
}

3. InterArrivalDelta

3.1. 重要属性

1)send_time_group_length_

约束一个分组的长度不能 send_time_group_length_,用来协助划分时间戳分组。

2)current_timestamp_group_

当前时间戳分组。

3)prev_timestamp_group_

上一个时间戳分组。

4)num_consecutive_reordered_packets_

连续乱序报文数量,乱序定义为分组间的到达时间差为负数。

3.2. 重要方法

1)ComputeDeltas

返回 true 表示达到计算条件,返回发送时间差和接收时间差。返回false,继续更新当前分组数据。

3.3. 报文分组

计算相邻两个报文的到达时间差的噪声太大,计算两个报文分组的到达时间差会更可靠。这就涉及到如何对报文进行分组。

3.3.1. 数据结构

struct SendTimeGroup {// 第一个报文bool IsFirstPacket() const { return complete_time.IsInfinite(); }// 所有报文大小之和size_t size;// 第一个报文的发送时间Timestamp first_send_time;// 不断更新的发送时间,但须保持单调递增Timestamp send_time;// 第一个报文的接收时间Timestamp first_arrival;// 不断更新的接收时间Timestamp complete_time;// 每次更新时当前系统时间(发送端收到反馈时的本地系统时间)Timestamp last_system_time;
};

3.3.2. 分组规则

1)收到的报文是当前分组第一个报文,则表示分组开始。

2)收到的报文和当前分组属于同一个 burst,则报文归属于当前分组。

3)收到的报文的发送时间与当前分组中第一个报文的发送时间之差小于等于 5ms,则报文归属当前分组。

4)否则,报文属于新的分组。

bool InterArrivalDelta::NewTimestampGroup(Timestamp arrival_time, Timestamp send_time) {if (current_timestamp_group_.IsFirstPacket()) {// 当前Group还未收到报文return false;} else if (BelongsToBurst(arrival_time, send_time)) {// 与当前Group同属于一个burstreturn false;} else { // 根据发送时间跨度来划分分组// send_time_group_length_ = TimeDelta::Millis(5)return send_time - current_timestamp_group_.first_send_time >send_time_group_length_;}
}

3.3.3. Burst 规则

1)发送时间相同,肯定属于同一个 burst。

2)由于链路拥塞,导致不同发送时间的报文也可能形成一个 burst,具体规则见注释。

bool InterArrivalDelta::BelongsToBurst(Timestamp arrival_time,Timestamp send_time) {// 计算数据包到达时间和当前时间组完成时间(最近报文的 arrival_time)之间的时间差TimeDelta arrival_time_delta =arrival_time - current_timestamp_group_.complete_time;// 计算数据包发送时间和当前时间组发送时间(分组当前最大的 send_time)之间的时间差TimeDelta send_time_delta = send_time - current_timestamp_group_.send_time;// send_time一样,属于同一个burst发出来if (send_time_delta.IsZero())return true;// 计算传播时间差,即到达时间差减去发送时间差,表示在网络中的传播时间TimeDelta propagation_delta = arrival_time_delta - send_time_delta;// 即使send_time不一样,如果同时满足以下条件,也认为属于同一个burst:// 1)传播时间差为负,说明与当前分组最后一个报文是积压在链路然后一起发送过来// 2)到达时间差小于等于5ms// 3)报文到达时间与当前分组第一个包的到达时间之差小于100msif (propagation_delta < TimeDelta::Zero() &&arrival_time_delta <= kBurstDeltaThreshold &&arrival_time - current_timestamp_group_.first_arrival < kMaxBurstDuration)return true;return false;
}

3.4. Delta 计算

Delta 的计算方式比较简单,两组报文的 send_time 相减和 complete_time 相减分别得到 send_time_delta 和 arrival_time_delta。但还需要处理乱序、系统时间漂移等异常情况,以防异常数据污染,使得计算结果变得不可靠。

1)系统时间漂移

system_time 是收到反馈的本地系统时间,通过比较前后两次系统时间的差值,如果超出正常范围,则认为系统时间可以被人为修改,数据需要重置,重新进行统计。

2)乱序

连续出现 3 次 arrival_time_delta 为负,说明网络乱序情况非常严重,基于当前数据计算结果不可靠,需要进行重置。

bool InterArrivalDelta::ComputeDeltas(Timestamp send_time, Timestamp arrival_time,Timestamp system_time, size_t packet_size, TimeDelta* send_time_delta,TimeDelta* arrival_time_delta, int* packet_size_delta) {bool calculated_deltas = false;if (current_timestamp_group_.IsFirstPacket()) {// 如果是第一个数据包,则仅存储发送和到达时间,因为需要至少两帧数据来计算差异。current_timestamp_group_.send_time = send_time;current_timestamp_group_.first_send_time = send_time;current_timestamp_group_.first_arrival = arrival_time;} else if (current_timestamp_group_.first_send_time > send_time) {// 如果当前数据包的发送时间早于第一个发送时间,表明是乱序包,直接返回return false;} else if (NewTimestampGroup(arrival_time, send_time)) {// First packet of a later send burst, the previous packets sample is ready.if (prev_timestamp_group_.complete_time.IsFinite()) {// 两组报文的发送时间差*send_time_delta =current_timestamp_group_.send_time - prev_timestamp_group_.send_time;// 两组报文的接收时间差*arrival_time_delta = current_timestamp_group_.complete_time -prev_timestamp_group_.complete_time;TimeDelta system_time_delta = current_timestamp_group_.last_system_time -prev_timestamp_group_.last_system_time;// 发现系统时间偏移,重置if (*arrival_time_delta - system_time_delta >= kArrivalTimeOffsetThreshold) {Reset();return false;}// 两组报文乱序到达,超过3个乱序报文,重置if (*arrival_time_delta < TimeDelta::Zero()) {++num_consecutive_reordered_packets_;if (num_consecutive_reordered_packets_ >= kReorderedResetThreshold) {Reset();}return false;} else {num_consecutive_reordered_packets_ = 0;}// 两组报文大小差*packet_size_delta = static_cast<int>(current_timestamp_group_.size) -static_cast<int>(prev_timestamp_group_.size);// 完成差异计算calculated_deltas = true;}// current -> prevprev_timestamp_group_ = current_timestamp_group_;// The new timestamp is now the current frame.current_timestamp_group_.first_send_time = send_time;current_timestamp_group_.send_time = send_time;current_timestamp_group_.first_arrival = arrival_time;current_timestamp_group_.size = 0;} else {// 属于当前 group 的正常报文,更新 send_timecurrent_timestamp_group_.send_time =std::max(current_timestamp_group_.send_time, send_time);}// Accumulate the frame size.current_timestamp_group_.size += packet_size;current_timestamp_group_.complete_time = arrival_time;current_timestamp_group_.last_system_time = system_time;return calculated_deltas;
}

4. TrendLineEstimator

4.1. 重要属性

1)delay_hist_

保存用来计算延迟斜率的元素,元素定义如下:

struct PacketTiming {// 相对队列第一组报文到达的相对时间,即 X 坐标double arrival_time_ms;// 平滑后的累积延迟差,即 Y 坐标double smoothed_delay_ms;// 平滑前的累积延迟差double raw_delay_ms;
};

2)threshold_

计算的延迟斜率通过与 threshold_ 比较来判断网络使用状态。

4.2. 重要方法

1)Update

内部调用 UpdateTrendLine。

2)UdpateTrendline

传入新的时间差值,更新网络使用状态。

3)State

获取当前网络使用状态。

4.3. 源码分析

4.3.1. UpdateTrendline

这是 TrendLineEstimator 的主函数,延迟差值累积到一定数量后,计算一个拟合后的斜率,然后基于斜率判断带宽使用情况,逻辑比较清晰,处理流程如下图所示:

void TrendlineEstimator::UpdateTrendline(double recv_delta_ms,double send_delta_ms,int64_t send_time_ms,int64_t arrival_time_ms,size_t packet_size) {// 计算延迟差const double delta_ms = recv_delta_ms - send_delta_ms;// 累加次数++num_of_deltas_;// 最大值约束num_of_deltas_ = std::min(num_of_deltas_, kDeltaCounterMax);if (first_arrival_time_ms_ == -1)first_arrival_time_ms_ = arrival_time_ms;// 平滑前延迟累积accumulated_delay_ += delta_ms;// 平滑后延迟累积,使用指数加权平均算法:smoothing_coef_ = 0.9smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +(1 - smoothing_coef_) * accumulated_delay_;// 插入新元素delay_hist_.emplace_back(static_cast<double>(arrival_time_ms - first_arrival_time_ms_),smoothed_delay_, accumulated_delay_);// 确保按照 arrival_time_ms 升序排列if (settings_.enable_sort) {for (size_t i = delay_hist_.size() - 1;i > 0 &&delay_hist_[i].arrival_time_ms < delay_hist_[i - 1].arrival_time_ms;--i) {std::swap(delay_hist_[i], delay_hist_[i - 1]);}}// 维持窗口大小if (delay_hist_.size() > settings_.window_size)delay_hist_.pop_front();// Simple linear regression.double trend = prev_trend_;// 当累积的数据量达到这个大小时,触发趋势线的更新if (delay_hist_.size() == settings_.window_size) {trend = LinearFitSlope(delay_hist_).value_or(trend);if (settings_.enable_cap) {absl::optional<double> cap = ComputeSlopeCap(delay_hist_, settings_);if (trend >= 0 && cap.has_value() && trend > cap.value()) {trend = cap.value();}}}// 基于趋势线计算,检测网络使用状态Detect(trend, send_delta_ms, arrival_time_ms);
}

4.3.2. ComputeSlopeCap

考虑到最小二乘法对异常值比较敏感,需要对通过最小二乘法计算的斜率进行约束,约束值的计算方法是:取历史数据中前七个数据中最小原始延迟数据,取历史数据中后七个数据中最小延迟数据,一前一后两个数据计算一个斜率,用这个斜率来约束通过最小二乘法计算的斜率。

absl::optional<double> ComputeSlopeCap(const std::deque<TrendlineEstimator::PacketTiming>& packets,const TrendlineEstimatorSettings& settings) {// 从前数7个数据,寻找最小原始延迟数据点TrendlineEstimator::PacketTiming early = packets[0];for (size_t i = 1; i < settings.beginning_packets; ++i) {if (packets[i].raw_delay_ms < early.raw_delay_ms)early = packets[i];}// 从后数7个数据,寻找最小原始延迟数据点size_t late_start = packets.size() - settings.end_packets;TrendlineEstimator::PacketTiming late = packets[late_start];for (size_t i = late_start + 1; i < packets.size(); ++i) {if (packets[i].raw_delay_ms < late.raw_delay_ms)late = packets[i];}// 检查late和early两个数据点之间的时间跨度,如果小于1ms,// 则认为时间跨度太小,不足以进行有效计算if (late.arrival_time_ms - early.arrival_time_ms < 1) {return absl::nullopt;}// 使用找到的两个数据点计算斜率return (late.raw_delay_ms - early.raw_delay_ms) /(late.arrival_time_ms - early.arrival_time_ms) +settings.cap_uncertainty;
}

4.3.3. Detect

使用调整后斜率与 threshold_ 进行比较,判断网络使用情况,租后还需要更新阈值,以适应网络变化。

1)斜率小于 -threshold_,标识网络为 kBwUnderusing;

2)斜率处于 [-threshold, threshold] 范围内,标识网络为 kBwNormal;

3)斜率大于 threshold_ 且满足以下三个条件则标识网络为 kBwOverusing:

a)连续处于 overuse 状态超过 10ms

b)连续处于 overuse 状态两次及以上

c)最后一次计算的斜率比之前的斜率更大。

void TrendlineEstimator::Detect(double trend, double ts_delta, int64_t now_ms) {// 初始阶段,样本数不足,假设网络正常if (num_of_deltas_ < 2) {hypothesis_ = BandwidthUsage::kBwNormal;return;}// 调整原始trend,具体原理未知,kMinNumDeltas=60,threshold_gain_=4.0const double modified_trend =std::min(num_of_deltas_, kMinNumDeltas) * trend * threshold_gain_;// 更新上次调整后trendprev_modified_trend_ = modified_trend;if (modified_trend > threshold_) {if (time_over_using_ == -1) {// 初始化计时器。假设自上次采样以来,有一半时间处于过度使用网络的状态。time_over_using_ = ts_delta / 2;} else {// 累加 overusing 时长time_over_using_ += ts_delta;}overuse_counter_++; // 累加 overuse 次数// 处于 overuse 状态很长时间,且检测到 overuse 大于一次if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) {if (trend >= prev_trend_) { // trend 还在加强time_over_using_ = 0;overuse_counter_ = 0;hypothesis_ = BandwidthUsage::kBwOverusing;}}} else if (modified_trend < -threshold_) {time_over_using_ = -1;overuse_counter_ = 0;hypothesis_ = BandwidthUsage::kBwUnderusing;} else { // [-threshold, threshold]time_over_using_ = -1;overuse_counter_ = 0;hypothesis_ = BandwidthUsage::kBwNormal;}prev_trend_ = trend; // 更新trend// 动态更新阈值UpdateThreshold(modified_trend, now_ms);
}

4.3.4. UpdateThreshold

threshold_ 初始值为 12.5,在计算过程中会进行动态更新,以适应网络条件变化。

void TrendlineEstimator::UpdateThreshold(double modified_trend, int64_t now_ms) {if (last_update_ms_ == -1)last_update_ms_ = now_ms;// kMaxAdaptOffsetMs = 15.0// 调整后趋势与当前阈值的差值超过了kMaxAdaptOffsetMs,则不进行阈值调整。// 这可以防止因网络突发的大延迟(如路由变化或瞬时拥塞)导致阈值被错误地大幅提高或降低。if (fabs(modified_trend) > threshold_ + kMaxAdaptOffsetMs) {last_update_ms_ = now_ms;return;}// k_up_(0.0087), k_down_(0.039), threshold_(12.5)// 选择阈值调整系数const double k = fabs(modified_trend) < threshold_ ? k_down_ : k_up_;// 约束time_delta_ms最大值为100msconst int64_t kMaxTimeDeltaMs = 100;int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);// trend如果在normal区间内,则减小threshold_// trend如果在normal区间外,则增大threshold_threshold_ += k * (fabs(modified_trend) - threshold_) * time_delta_ms;// 约束threshold_在[6, 600]范围threshold_ = rtc::SafeClamp(threshold_, 6.f, 600.f);last_update_ms_ = now_ms;
}

5. LinkCapacityEstimator

5.1. 重要属性

1)estimate_kbps_

估计的链路容量。

2)deviation_kbps_

链路容量估计值的方差,用来量化估计值的不确定性或波动性,初始值为 0.4。

5.2. 重要方法

1)UpperBound

链路容量估计的上界,等于链路容量估计值加上 3 倍标准差。

2)LowerBound

链路容量估计的下界,等于链路容量估计值减去 3 倍标准差。

3)OnOveruseDetected

当 AIMD 检测到 overuse 时,调用此接口,传入 ACK 码率,LinkCapacityEstimator 对 ACK 码率使用 0.05 的权重来更新估计值。网络处于 overuse 状态时,ACK 码率能够真实反映链路容量。

void LinkCapacityEstimator::OnOveruseDetected(DataRate acknowledged_rate) {Update(acknowledged_rate, 0.05);
}

4)OnProbeRate

探测码率具有更好的实时性,LinkCapacityEstimator 对探测码率赋予更高的权重(0.5)来更新估计值。

void LinkCapacityEstimator::OnOveruseDetected(DataRate acknowledged_rate) {Update(acknowledged_rate, 0.05);
}

5)estimate

获取链路容量估计值。

5.3. 源码分析

5.3.1. UpperBound/LowerBound

可以认为链路容量估计值符合正态分布,正态分布中大约 99.7% 的数据位于均值的三倍标准差之内,可以提供一个相对宽松但合理的上限和下限估计。

UpperBound 取链路容量估计值加上 3 倍标准差,LowerBound 取链路容量估计值减去 3 倍标准差。

DataRate LinkCapacityEstimator::UpperBound() const {if (estimate_kbps_.has_value())return DataRate::KilobitsPerSec(estimate_kbps_.value() +3 * deviation_estimate_kbps());return DataRate::Infinity();
}DataRate LinkCapacityEstimator::LowerBound() const {if (estimate_kbps_.has_value())return DataRate::KilobitsPerSec(std::max(0.0, estimate_kbps_.value() - 3 * deviation_estimate_kbps()));return DataRate::Zero();
}double LinkCapacityEstimator::deviation_estimate_kbps() const {// 计算标准差之前先恢复归一化return sqrt(deviation_kbps_ * estimate_kbps_.value());
}

5.3.2. Update

AimdRateControl 在网络处于过载状态时,会调用此接口传入 ACK 码率,来更新链路容量估计值。只有处于网络过载状态的 ACK 码率才能真实反映当前链路容量。LinkCapacityEstimator 使用指数移动平均算法对链路容量值进行平滑,并计算归一化方差。

void LinkCapacityEstimator::Update(DataRate capacity_sample, double alpha) {double sample_kbps = capacity_sample.kbps();if (!estimate_kbps_.has_value()) {estimate_kbps_ = sample_kbps;} else {// 使用指数移动平均算法来平滑估计值estimate_kbps_ = (1 - alpha) * estimate_kbps_.value() + alpha * sample_kbps;}// 方差归一化参数const double norm = std::max(estimate_kbps_.value(), 1.0);// 计算估计值与当前样本值之间的差,相当于样本值与平均值的差double error_kbps = estimate_kbps_.value() - sample_kbps;// 计算归一化方差并进行平滑,注意这里的归一化并没有完全归一,单位是 kbps。// 如果要做完全归一化,分母应该是 norm 的平方。deviation_kbps_ =(1 - alpha) * deviation_kbps_ + alpha * error_kbps * error_kbps / norm;// 对归一化方差进行约束(这是个经验值)deviation_kbps_ = rtc::SafeClamp(deviation_kbps_, 0.4f, 2.5f);
}

限制 deviation_kbps_ 在 [0.4, 2.5] 范围,这应该是一个经验值。相当于 500Kbps 的估计值,归一化方差范围对应的估计误差大约在 14kbps 到 35kbps 之间。

(500-x)^2 / 500 = 0.4
|500-x| = sqrt(500 * 0.4)
|500-x| ~= 14kbps(500-x)^2 / 500 = 2.5
|500-x| = sqrt(500 * 2.5)
|500-x| ~= 35kbps

6. AimdRateControl

6.1. 重要属性

1)link_capacity_

链路容量估计器,用来辅助调整估计带宽,具体参考源码分析。

6.2. 重要方法

1)SetStartBitrate

设置起始估计值。

2)SetMinBitrate

设置估计值的下限。

3)LatestEstimate

获取最近的估计值。

4)SetRtt

更新 RTT,当进行加性提速时,需要使用 RTT 来计算增速。

5)Update

外部周期性调用,传入 ACK 码率,驱动 AimdRateControl 的状态机运转。

6)SetInApplicationLimitedRegion

设置 ALR 状态,ALR 状态不允许提速(如果有配置的话)。

6.3. 状态机

码率控制状态定义如下:

enum class RateControlState { kRcHold, kRcIncrease, kRcDecrease
};

码率控制状态在网络过载信号的刺激下会作出相应的响应和变化,形成一个状态机,如下图所示。

状态机状态变化规则说明:

1)状态机一开始进入 Incr 状态。

【注】Incr 状态码率每次增长系数见源码分析

2)检测到 overuse 信号,不管当前处于什么状态,都转换到 Decr 状态。

【注】Decr 状态码率每次下降系数为

3)检测到 underuse 信号,不管当前处于什么状态,都转换到 Hold 状态。

【注】即使之前处于 Incr 状态,也必须转换到 Hold 状态。因为 underuse 信号,说明网络正处于排空期,在排空完成前不要提升速率,否则可能会增加延迟。

4)在 Decr 状态,检测到 normal 信号,进入 Hold 状态,降速可以结束了。

5)在 Hold 状态,检测到 normal 信号,进入 Incr 状态,需要开始提速了。

【注】Hold 是一个暂态,会不停往上疯狂试探网络容量的上界。因此,Hold 的意思,更像是等待网络排空的Hold,而不是码率保持的 Hold。

6)在 Incr 状态,检测到 normal 信号,继续保持 Incr 状态,提速还不能停。

【注】说明这是一个相对激进的带宽评估状态机,不会停在刚刚好,而是一定会走到 underuse。

状态机运行相关代码如下:

void AimdRateControl::ChangeState(const RateControlInput& input, Timestamp at_time) {switch (input.bw_state) {case BandwidthUsage::kBwNormal:// 带宽使用状态正常// 如果之前是保持,现在可以提升估计值了// 如果之前是提升,现在继续提升// 如果之前是降低,现在继续降低if (rate_control_state_ == RateControlState::kRcHold) {time_last_bitrate_change_ = at_time;rate_control_state_ = RateControlState::kRcIncrease;}break;case BandwidthUsage::kBwOverusing:// 网络过载,不管之前是什么控制状态,现在都要降低估计值if (rate_control_state_ != RateControlState::kRcDecrease) {rate_control_state_ = RateControlState::kRcDecrease;}break;case BandwidthUsage::kBwUnderusing:// 网络欠载,不管之前是什么控制状态,现在都要保持估计值rate_control_state_ = RateControlState::kRcHold;break;default:RTC_DCHECK_NOTREACHED();}
}

6.4. 源码分析

6.4.1. ChangeBitrate

使用输入参数中的网络使用信号更新状态机,然后根据新的状态指示作出相应处理。有几个处理细节需要注意:

1)ACK 码率是提速和降速的基础,这是因为 ACK 码率是一个链路容量的一个观测值,也是当前链路容量的可靠估计值。

2)LinkCapacityEstimator 是基于 ACK 码率的估计,当收到新的 ACK 码率超出估计值的 3 倍标准差,有理由认为当前的估计值与真实值有较大偏差,需要重置。

void AimdRateControl::ChangeBitrate(const RateControlInput& input,Timestamp at_time) {absl::optional<DataRate> new_bitrate;// ACK 码率DataRate estimated_throughput =input.estimated_throughput.value_or(latest_estimated_throughput_);// 更新if (input.estimated_throughput)latest_estimated_throughput_ = *input.estimated_throughput;// 未设置或者未评估,if (!bitrate_is_initialized_ && input.bw_state != BandwidthUsage::kBwOverusing)return;// 状态机更新ChangeState(input, at_time);switch (rate_control_state_) {// 保持case RateControlState::kRcHold:break; // 码率不变// 提速case RateControlState::kRcIncrease: {// ACK 码率超过估计值的 3*sigma 范围,需要重置 LinkCapacityEstimatorif (estimated_throughput > link_capacity_.UpperBound())link_capacity_.Reset();// 以 ACK 码率的 1.5 倍作为提速上限DataRate increase_limit =1.5 * estimated_throughput + DataRate::KilobitsPerSec(10);// 发送端,设置了 ALR 状态不允许升速if (send_side_ && in_alr_ && no_bitrate_increase_in_alr_) {increase_limit = current_bitrate_;}if (current_bitrate_ < increase_limit) {DataRate increased_bitrate = DataRate::MinusInfinity();if (link_capacity_.has_estimate()) {// 链路容量估计值有效,认为目标码率与链路容量较为接近,采用加性增进行调整。DataRate additive_increase =AdditiveRateIncrease(at_time, time_last_bitrate_change_);increased_bitrate = current_bitrate_ + additive_increase;} else {// 链路容量估计值无效,则使用乘性增方式来探索新的链路容量。DataRate multiplicative_increase = MultiplicativeRateIncrease(at_time, time_last_bitrate_change_, current_bitrate_);increased_bitrate = current_bitrate_ + multiplicative_increase;}new_bitrate = std::min(increased_bitrate, increase_limit);}time_last_bitrate_change_ = at_time;break;}// 降速case RateControlState::kRcDecrease: {DataRate decreased_bitrate = DataRate::PlusInfinity();// 降速目标设置为 ACK 码率的 85%decreased_bitrate = estimated_throughput * beta_;if (decreased_bitrate > DataRate::KilobitsPerSec(5) &&subtract_additional_backoff_term_) {decreased_bitrate -= DataRate::KilobitsPerSec(5);}// 如果降速目标还是比当前码率高,则尝试使用链路容量估计值的 85%if (decreased_bitrate > current_bitrate_) {if (link_capacity_.has_estimate()) {decreased_bitrate = beta_ * link_capacity_.estimate();}}// 有可能降速目标还是比当前码率高if (decreased_bitrate < current_bitrate_) {new_bitrate = decreased_bitrate;}// 更新 last_decrease_if (bitrate_is_initialized_ && estimated_throughput < current_bitrate_) {if (!new_bitrate.has_value()) {last_decrease_ = DataRate::Zero();} else {last_decrease_ = current_bitrate_ - *new_bitrate;}}// ACK 码率超过估计值的 3*sigma 范围,需要重置 LinkCapacityEstimatorif (estimated_throughput < link_capacity_.LowerBound()) {link_capacity_.Reset();}bitrate_is_initialized_ = true;// 使用 overuse 信号下的 ACK 码率更新链路容量估计link_capacity_.OnOveruseDetected(estimated_throughput);// Stay on hold until the pipes are cleared.rate_control_state_ = RateControlState::kRcHold;time_last_bitrate_change_ = at_time;time_last_bitrate_decrease_ = at_time;break;}default:RTC_DCHECK_NOTREACHED();}// 更新当前估计值current_bitrate_ = ClampBitrate(new_bitrate.value_or(current_bitrate_));
}

6.4.2. AdditiveRateIncrease

加性提速根据 rtt_ 和 current_bitrate_ 来计算增速,相当于每个 rtt 多发送一个 packet,这样的增速看上去是比较温和的。

DataRate AimdRateControl::AdditiveRateIncrease(Timestamp at_time,Timestamp last_time) const {double time_period_seconds = (at_time - last_time).seconds<double>();double data_rate_increase_bps =GetNearMaxIncreaseRateBpsPerSecond() * time_period_seconds;return DataRate::BitsPerSec(data_rate_increase_bps);
}
double AimdRateControl::GetNearMaxIncreaseRateBpsPerSecond() const {RTC_DCHECK(!current_bitrate_.IsZero());// 假定视频帧率为30FPS,计算每帧的时间间隔 kFrameInterval 为大约33.3毫秒const TimeDelta kFrameInterval = TimeDelta::Seconds(1) / 30;// 根据当前比特率和帧间隔,计算单帧数据的大小,这代表了每帧数据传输所需的总比特数DataSize frame_size = current_bitrate_ * kFrameInterval;// 设定每数据包的大小为1200字节const DataSize kPacketSize = DataSize::Bytes(1200);//  计算每帧数据需要多少个这样的数据包,取上界值(因为即使最后一包不满,也按一整个包计算)double packets_per_frame = std::ceil(frame_size / kPacketSize);// 基于总帧大小和包的数量,计算平均每个包的大小DataSize avg_packet_size = frame_size / packets_per_frame;// 注:纯粹数学推导,avg_packet_size == kPacketSize// 在真实RTT的基础上加上100ms再乘以2,使得加性增速更加保守?TimeDelta response_time = rtt_ + TimeDelta::Millis(100);response_time = response_time * 2;// 按照ping-pong模式(收到ack后再发送下一个报文)一秒钟可以多发送多少数据。double increase_rate_bps_per_second =(avg_packet_size / response_time).bps<double>();double kMinIncreaseRateBpsPerSecond = 4000;return std::max(kMinIncreaseRateBpsPerSecond, increase_rate_bps_per_second);
}

6.4.3. MultiplicativeRateIncrease

乘性提速会计算一个增益值,初始化增益为 8%,会根据时间频率来调整增益系数。

DataRate AimdRateControl::MultiplicativeRateIncrease(Timestamp at_time,Timestamp last_time,DataRate current_bitrate) const {// 初始化增益系数double alpha = 1.08;// 如果之前调整过码率,距离上次调整码率时间过去越久,增益系数越大if (last_time.IsFinite()) {auto time_since_last_update = at_time - last_time;alpha = pow(alpha, std::min(time_since_last_update.seconds<double>(), 1.0));}// 根据增益系数计算增速,限制最低码率增速为 1KbpsDataRate multiplicative_increase =std::max(current_bitrate * (alpha - 1.0), DataRate::BitsPerSec(1000));return multiplicative_increase;
}

7. 总结

基于延迟的带宽估计,以处于非 ALR 状态的 ACK 码率为基础,基于延迟梯度估计链路真实带宽,实现对链路带宽的动态跟踪,算法的核心逻辑可以表述为:

1)网络过载,说明网络产生拥塞,当前发送码率过高,需要降低发送码率。

2)网络欠载,说明网络正在排空,不要急着提升发送码率,先保持当前发送码率一段时间。

3)网络正常,可以试着增加发送码率,探测下带宽的上限。

同时,在网络非过载状态下,使用探测带宽对估计值进行校正,使估计更加精准。算法在计算延迟梯度、判断网络使用状况都做了精心的设计,会尽量排除随机噪声的干扰。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/383096.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

贪心算法(算法篇)

算法之贪心算法 贪心算法 概念&#xff1a; 贪心算法是一种思想&#xff0c;并不是一种算法&#xff0c;贪心算法是分阶段地工作&#xff0c;在每一个阶段&#xff0c;可以认为所作决定是好的&#xff0c;而不考虑将来地后果。算法的每个阶段总是选择当前阶段最优&#xff0…

Kafka Producer之数据重复和乱序问题

文章目录 1. 数据重复2. 数据乱序 为了可靠性&#xff0c;Kafka有消息重试机制&#xff0c;但是同时也带来了2大问题 1. 数据重复 消息发送到broker后&#xff0c;broker记录消息数据到log中&#xff0c;但是由于网络问题&#xff0c;producer没有收到acks&#xff0c;于是再次…

Axure设计之轮播图(动态面板+中继器)

轮播图&#xff08;Carousel&#xff09;是一种网页或应用界面中常见的组件&#xff0c;用于展示一系列的图片或内容&#xff0c;通常通过自动播放或用户交互&#xff08;如点击箭头按钮&#xff09;来切换展示不同的内容。轮播图能够吸引用户的注意力&#xff0c;有效展示重要…

新手小白的pytorch学习第十一弹-----Computer Vision创建基础模型使用FashionMNIST

目录 PyTorch Computer Vision0 PyTorch 中 Computer vision 的库1 获得一个数据集1.1 查看数据的输入和输出形状1.2 可视化数据 2 准备 DataLoader3 Model 0: 创建一个 baseline model3.1 设置损失函数、优化器和评估指标3.2 创建一个函数来给我们的实验计时3.3 在批量数据集上…

萝卜快跑:自动驾驶的先锋与挑战

萝卜快跑&#xff1a;自动驾驶的先锋与挑战 近段时间&#xff0c;由萝卜快跑引发的自动驾驶事件如火如荼&#xff0c;成为科技领域的热门话题。萝卜快跑作为自动驾驶领域的重要参与者&#xff0c;其最新事件引发了广泛的关注和讨论。 萝卜快跑是百度推出的自动驾驶出行服务平台…

20240724-然后用idea创建一个Java项目/配置maven环境/本地仓储配置

1.创建一个java项目 &#xff08;1&#xff09;点击页面的create project&#xff0c;然后next &#xff08;2&#xff09;不勾选&#xff0c;继续next &#xff08;3&#xff09;选择新项目名称&#xff0c;新项目路径&#xff0c;然后Finsh&#xff0c;在新打开的页面选择…

Hadoop、Hive、HBase、数据集成、Scala阶段测试

姓名&#xff1a; 总分&#xff1a;Hadoop、Hive、HBase、数据集成、Scala阶段测试 一、选择题&#xff08;共20道&#xff0c;每道0.5分&#xff09; 1、下面哪个程序负责HDFS数据存储&#xff08; C &#xff09; A. NameNode B. Jobtracher C. DataNode D. Sec…

鸿蒙界面开发

界面开发 //构建 → 界面 build() {//行Row(){//列Column(){//文本 函数名(参数) 对象.方法名&#xff08;参数&#xff09; 枚举名.变量名Text(this.message).fontSize(40)//设置文本大小.fontWeight(FontWeight.Bold)//设置文本粗细.fontColor(#ff2152)//设置文本颜色}.widt…

3.JAVA-IDEA

IDEA介绍 下载安装 实际操作 免费试用&#xff0c;可以选第一个自己找到密匙开锁 首先新建project项目 建立空项目 起名并存储位置选择 确定创建项目 成功新建项目&#xff0c;开始新建模块 新建或导入模块 新建java模块 修改名称&#xff0c;位置保持默认 同样yes建立 ok即可 …

2 YOLO8的使用

1 介绍 YOLOv8是YOLO (You Only Look Once) 目标检测模型系列的最新版本&#xff0c;由Ultralytics公司开发和维护。YOLOv8是在先前版本的基础上进行的重大更新&#xff0c;不仅提升了性能&#xff0c;还增加了更多的功能&#xff0c;它不仅能够进行目标检测&#xff0c;还能完…

职业教育综合布线实验实训室建设应用案例

在信息技术迅猛发展的今天&#xff0c;综合布线技术已成为智能建筑、数据中心等基础设施不可或缺的一部分。唯众&#xff0c;作为职业教育领域的先行者&#xff0c;早在多年前便洞悉行业趋势&#xff0c;率先涉足综合布线实训室的建设&#xff0c;凭借丰富的经验和持续的创新&a…

phpstorm配置xdebug3

查看php路径相关信息 php --ini安装xdebug https://www.jetbrains.com/help/phpstorm/2024.1/configuring-xdebug.html?php.debugging.xdebug.configure php.ini 配置 在最后添加&#xff0c;以下是我的配置 [xdebug] zend_extension/opt/homebrew/Cellar/php8.1/8.1.29/p…

决策树 和 集成学习、随机森林

决策树是非参数学习算法&#xff0c;可以解决分类问题&#xff0c;天然可以解决多分类问题&#xff08;不同于逻辑回归或者SVM&#xff0c;需要通过OVR&#xff0c;OVO的方法&#xff09;&#xff0c;也可以解决回归问题&#xff0c;甚至是多输出任务&#xff0c;并且决策树有非…

【北京迅为】《i.MX8MM嵌入式Linux开发指南》-第三篇 嵌入式Linux驱动开发篇-第五十一章 添加设备树节点

i.MX8MM处理器采用了先进的14LPCFinFET工艺&#xff0c;提供更快的速度和更高的电源效率;四核Cortex-A53&#xff0c;单核Cortex-M4&#xff0c;多达五个内核 &#xff0c;主频高达1.8GHz&#xff0c;2G DDR4内存、8G EMMC存储。千兆工业级以太网、MIPI-DSI、USB HOST、WIFI/BT…

通过4G模块EC600N向阿里云物联网平台物模型上面发送字符串,现在发送int数据是成功的,发送字符串就是不成功

&#x1f3c6;本文收录于《CSDN问答解惑-专业版》专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收…

轻量化YOLOv7系列:结合G-GhostNet | 适配GPU,华为诺亚提出G-Ghost方案升级GhostNet

轻量化YOLOv7系列&#xff1a;结合G-GhostNet | 适配GPU&#xff0c;华为诺亚提出G-Ghost方案升级GhostNet 需要修改的代码models/GGhostRegNet.py代码 创建yaml文件测试是否创建成功 本文提供了改进 YOLOv7注意力系列包含不同的注意力机制以及多种加入方式&#xff0c;在本文…

【Python】Facebook开源时间序列数据预测模型Prophet

文章目录 一、简介二、项目的文件解读三、Prophet类主要方法和参数3.1 主要参数3.2 主要方法 四、用法示例 一、简介 Prophet 是由 Facebook 开发的一个开源工具&#xff0c;用于时间序列数据的预测。它特别适用于处理具有强季节性和趋势的时间序列数据&#xff0c;并且对节假…

大数据之Oracle同步Doris数据不一致问题

数据同步架构如下&#xff1a; 出现的问题&#xff1a; doris中的数据条数 源库中的数据条数 总数完全不一致。 出现问题的原因&#xff1a; 在Dinky中建立表结构时&#xff0c;缺少对主键属性的限制 primary key(ID) not enforced 加上如上语句&#xff0c;数据条数解决一致 …

App Instance 架构示例

前言 在Unity程序设计过程中&#xff0c;我们处理的第一个对象是Application Instance。 它的主要职责是启动流程管理、卸载流程管理&#xff0c;次要职责是管理在内部的子系统生命周期。其他职责&#xff0c;提供或桥接应用程序的配置信息、及其他第三方接口。 它通常以单例的…

51单片机嵌入式开发:18、STC89C52RC嵌入式DS1302实时时钟实验及数码管显示

STC89C52RC嵌入式DS1302实时时钟实验及数码管显示 STC89C52RC嵌入式DS1302实时时钟实验及数码管显示1 概述1.1 DS1302简介1.2 DS1302功能和特点1.3 DS1302工作原理1.4 DS1302应用领域 2 DS1302设计原理2.1 引脚说明2.2 寄存器说明及使用&#xff08;1&#xff09;命令cmd字节说…