webrtc QOS筆記一 Neteq直方圖演演算法淺讀

webrtc QOS筆記一 Neteq直方圖演演算法淺讀

想起部落格園帳號了，回來填點webrtc qos的坑， 本文分析個很好用的直方圖演演算法，不僅可以在音訊裡面計算抖動延遲，我發現用來統計丟包率也很好用.

Histogram Algorithm

DelayManager::Update()->Histogram::Add() 會根據計算的iat_packet(inter arrival times, =實際包間間隔 / 打包時長)，將該iat_packet插入IATVector直方圖對應陣列下標內。並更新該直方圖的資料下標下概率引數。[M88 SRC]

一共有四步操作：

1、用遺忘因子，對歷史資料的出現概率進行遺忘, 並統計概率合

2、增大本次計算到的IAT的概率值。

• 例：

假如歷史bucket 資料為:
buckets_ = {0，0，1，0}

遺忘因子為 0.9:
forget_factor = 0.9

新來的抖動延遲資料為66ms， 桶間為20ms一個單位, 那插入位置為 66 / 20 = 3，則更新後

buckets = {0，0，0.9，0.1}

假若使用%95分位的值作為目標延遲， 則更新後的目標延遲為 60ms.

3、調整本次計算到的IAT的概率，使整個IAT的概率分佈之和近似為1。調整方式為假設當前概率分佈之和為tempSum，則：

4、更新forget_factor_, 使遺忘因子forget_factor_逼近base_forget_factor_

a.使用start_forget_weight_更新(預設初始值start_forget_weight_ = 2，base_forget_factor_=0.9993)

獲取目標延遲

依據probability獲取此百分位的值作為目標延遲(初始值0.97)

int Histogram::Quantile(int probability) {
  // Find the bucket for which the probability of observing an
  // inter-arrival time larger than or equal to |index| is larger than or
  // equal to |probability|. The sought probability is estimated using
  // the histogram as the reverse cumulant PDF, i.e., the sum of elements from
  // the end up until |index|. Now, since the sum of all elements is 1
  // (in Q30) by definition, and since the solution is often a low value for
  // |iat_index|, it is more efficient to start with |sum| = 1 and subtract
  // elements from the start of the histogram.
  int inverse_probability = (1 << 30) - probability;
  size_t index = 0;        // Start from the beginning of |buckets_|.
  int sum = 1 << 30;       // Assign to 1 in Q30.
  sum -= buckets_[index];
  
  while ((sum > inverse_probability) && (index < buckets_.size() - 1)) {
    // Subtract the probabilities one by one until the sum is no longer greater
    // than |inverse_probability|.
    ++index;
    sum -= buckets_[index];
  }

  return static_cast<int>(index);
}

​

遺忘因子曲線

測試曲線,調整遺忘因子提高抖動估計靈敏度:

#include <iostream>
#include <cstdint>
#include <vector>

uint32_t packet_loss_rate_ = 0;

int main()
{
  std::vector<int> input;
  std::vector<float> buckets;
  float forget_factor = 0.9993;
  float val = 0;

  for (size_t k = 0; k < 1000; k ++) {
    val = val * forget_factor + (1-forget_factor);
    buckets.push_back(val);
  }

  for (int i = 0; i < 1000; ++i) {
    std::cout << buckets[i]<< " ";
  }

  return 0;
}