background
Network congestion is based on the IP datagram exchange network in a common network transmission problem, it has serious impact on the quality of the network, network congestion is reduce the network throughput and network packet loss and so on, one of the main reasons for these problems make the upper application unable to use the network bandwidth effectively obtain the high quality network transmission. Especially in the field of communication, network congestion caused by packet loss, delay, jitter and other problems, seriously affect the quality of communication, if not a good solution to these problems, a communication product can not be used in the real environment.
Packet loss bandwidth estimation
Packet loss – based congestion control is relatively simple, and its basic idea is to judge the degree of network congestion according to the number of packet loss. The more packets are lost, the more congested the network is. Therefore, we need to reduce the sending rate to ease the network congestion. If there is no packet loss, this indicates that the network is in good condition, so you can increase the transmitting bit rate and probe upward to see if there is more bandwidth available. There are two points to realize the algorithm: one is to get the packet loss rate of the receiving end, the other is to determine the threshold of decreasing bit rate and increasing bit rate.
As_hat (I) = As_hat (I – 1), 2% < = packet loss rate < = 10%, unchanged As_hat (I) = As_hat (I – 1) (1-0.5 p), packet loss rate > 10%, falling, p is As_hat packet loss rate (I) = 1.05 * As_hat (I – 1), Packet loss rate <2%, increasing
After receiving the RTCP RR packet and resolving the packet loss rate, the weBRTC calculates the bit rate of the sender according to the following formula: When the packet loss rate is greater than 0.1, the network is congested and the bit rate of the sender is reduced. When the packet loss rate is less than 0.02, it indicates that the network is in good condition. In this case, the bit rate of the sending end increases. In other cases, the transmitting bit rate remains unchanged.
Delay bandwidth estimation
Goog-REMB
Based on the delay algorithm at the receiving end, the network bandwidth trend at the next moment is estimated by kalman filter with the delay value, which is not as accurate and fair as transport-CC and has been eliminated by the new version of WEBRTC
Transport-CC
The delay algorithm based on the sender also uses interval delay value and TrendLine filter (least square filter) to judge the current network congestion condition by increasing or decreasing slope
Delay gradient calculation
First, let’s take a look at the calculation of delay gradient through a graph:
In WebRTC, the delay gradient is calculated not packet by packet, but by grouping packets and then calculating the delay between these packet groups, which reduces the number of calculations and also reduces the error. Packet groups are divided according to the principle that a series of packets within a burst_time interval form a group. You are advised to set burst_time to 5ms.
TrendLine filter (least square filter)
The method of linear regression is used to predict the delay trend, and the slope of the fitting line is obtained by the least square method
For a bunch of sample points (x,y), the slope A of the fitting line equation y= Ax +b is calculated by the following formula
Is the minimum distance sum of squares of specific way, according to the value of the derivative launched a specific can refer to www.cnblogs.com/paiandlu/p/…
The code implementation path, goog_cc/trendline_estimator.cc, is consistent with the above derivation formula
absl::optional<double> LinearFitSlope(
const std: :deque<TrendlineEstimator::PacketTiming>& packets) {
RTC_DCHECK(packets.size() >= 2);
// Compute the "center of mass".
double sum_x = 0;
double sum_y = 0;
for (const auto& packet : packets) {
// Calculate the total value of x and y
sum_x += packet.arrival_time_ms;
sum_y += packet.smoothed_delay_ms;
}
// Calculate the average value of x and y
double x_avg = sum_x / packets.size();
double y_avg = sum_y / packets.size();
// Compute the slope k = sum (x_i-x_avg)(y_i-y_avg) / sum (x_i-x_avg)^2
double numerator = 0;
double denominator = 0;
for (const auto& packet : packets) {
double x = packet.arrival_time_ms;
double y = packet.smoothed_delay_ms;
numerator += (x - x_avg) * (y - y_avg);
denominator += (x - x_avg) * (x - x_avg);
}
if (denominator == 0)
return absl::nullopt;
return numerator / denominator;
}
Copy the codeThe overall call flow is
LinearFitSlope UpdateTrendline left LinearFitSlope LinearFitSlope left TrendlineEstimator: : Detect left TrendlineEstimator::UpdateThresholdCopy the codeUpdateTrendline
This method is basically to do some statistical calculations of the data, and then call LinearFitSlope to calculate the slope
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) {
// Delay change: receive time difference - send time difference
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;
// Exponential backoff filter.
accumulated_delay_ += delta_ms;
BWE_TEST_LOGGING_PLOT(1."accumulated_delay_ms", arrival_time_ms,
accumulated_delay_);
// Calculate the smoothed delay according to the cumulative delay value in 1) : Smoothing_COef_ is 0.9
smoothed_delay_ = smoothing_coef_ * smoothed_delay_ +
(1 - smoothing_coef_) * accumulated_delay_;
BWE_TEST_LOGGING_PLOT(1."smoothed_delay_ms", arrival_time_ms,
smoothed_delay_);
if (delay_hist_.size() > settings_.window_size)
delay_hist_.pop_front();
// Simple linear regression.
double trend = prev_trend_;
// When queue delay_HIST_ is equal to the set window size, the delay trend is calculated and the straight slope is obtained
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_);
// We only use the cap to filter out overuse detections, not
// to detect additional underuses.
if (trend >= 0 && cap.has_value() && trend > cap.value()) {
trend = cap.value();
}
}
}
BWE_TEST_LOGGING_PLOT(1."trendline_slope", arrival_time_ms, trend);
// Pass in trend to calculate the current network state
Detect(trend, send_delta_ms, arrival_time_ms);
}
Copy the codeDetect
This function mainly calculates the current network status according to the trend of delay change. Within the Detect function, an adjusted slope value based on the previously calculated slope is obtained: modified_trend:
void TrendlineEstimator::Detect(double trend, double ts_delta, int64_t now_ms) {
if (num_of_deltas_ < 2) {
hypothesis_ = BandwidthUsage::kBwNormal;
return;
}
const double modified_trend =
std::min(num_of_deltas_, kMinNumDeltas) * trend * threshold_gain_;
prev_modified_trend_ = modified_trend;
BWE_TEST_LOGGING_PLOT(1."T", now_ms, modified_trend);
BWE_TEST_LOGGING_PLOT(1."threshold", now_ms, threshold_);
/ / 1.
if (modified_trend > threshold_) {
if (time_over_using_ == - 1) {
// Initialize the timer. Assume that we've been
// over-using half of the time since the previous
// sample.
time_over_using_ = ts_delta / 2;
} else {
// Increment timer
time_over_using_ += ts_delta;
}
overuse_counter_++;
/ / 2/3
if (time_over_using_ > overusing_time_threshold_ && overuse_counter_ > 1) {
/ / 4
if (trend >= prev_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 {
time_over_using_ = - 1;
overuse_counter_ = 0;
hypothesis_ = BandwidthUsage::kBwNormal;
}
prev_trend_ = trend;
UpdateThreshold(modified_trend, now_ms);
}
Copy the codeconst double modified_trend = std::min(num_of_deltas_, kMinNumDeltas) * trend * threshold_gain_;
Num_of_deltas_ indicates the number of delay gradient calculations between packet groups. The value ranges from [2, 60]. Threshold_gain_ is the gain parameter of Trendline filter, and its default value is 4. The key here is why the amplified meaning trend is a slope value in the range of values (-1, 1), which is small and the threshold varies with the change, which can easily be exceeded to trigger a continuous overload signal. Amplification prevents the algorithm from being overly sensitive to the fluctuations of.
Condition that is judged to be overload
- The slope of the delay gradient is greater than the current threshold
- Total overload time > kOverUsingTimeThreshold(10ms)
- Overload times >1
- The current delay gradient slope value is greater than the last delay gradient slope value, that is, the delay is deteriorating.
UpdateThreshold
Threshold_ Dynamic adjustment to change the sensitivity of the algorithm to the delay gradient. If the threshold is fixed, it may be too large or too small for the delay gradient. In this way, detection is not sensitive enough to detect network congestion, or too sensitive to detect network congestion all the time.
void TrendlineEstimator::UpdateThreshold(double modified_trend,
int64_t now_ms) {
// Define K coefficient k_down_(0.039) k_up_(0.0087),
const double k = fabs(modified_trend) < threshold_ ? k_down_ : k_up_;
const int64_t kMaxTimeDeltaMs = 100;
// Calculate the last update time, and take the minimum value of 100ms
int64_t time_delta_ms = std::min(now_ms - last_update_ms_, kMaxTimeDeltaMs);
// calculate k and time_delta_ms to update the threshold
threshold_ += k * (fabs(modified_trend) - threshold_) * time_delta_ms;
threshold_ = rtc::SafeClamp(threshold_, 6.f.600.f);
last_update_ms_ = now_ms;
}
Copy the code