一種高精度均勻取樣算法及其網絡應用

武寶剛，白海斌，章 偉

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

0 引言

在通信領域中經常會遇到按比例均勻取樣的問題，如網絡速率限制和流量整形中常用的令牌桶算法，其令牌產生速率 (Committed Information Rate，CIR)本質就是一種按比例的均勻取樣過程，網絡損傷中的按比例均勻丟包產生也是一種按比例均勻取樣過程。

涉及到均勻取樣時，通常根據樣本總數和要取樣的樣本數，通過等間隔均勻抽取的方式進行取樣。根據取樣比例的不同，該方法會引入一定的誤差，在某些對取樣精度要求苛刻的場合，可能會大大影響最終的結果。針對這個問題，提出一種高精度均勻取樣算法，根據樣本選取精度，該算法理論上可針對任意比例的取樣做到零誤差。

1 算法原理和實現過程

1.1 算法原理

一般的按比例均勻取樣方法是根據樣本總數和要取出的樣本數，通過讓二者相除來選取均勻抽取間隔，但當二者不可整除時則不可避免地引入了誤差。雖然可以通過單純丟棄最后一部分樣本點來使實際取出的樣本數和要取出的樣本數相等，但這樣整個抽取過程不是均勻的，在取樣過程的最后一部分會出現一段時間沒有取樣本的情況。在樣本數目很多，抽取過程較長時，前部分和后部分其實是稀疏不等的。該算法為了解決這個問題，基本思路是將多抽取的樣本點分散到整個抽取過程中均勻剔除，這樣無論是從整體還是局部來看，抽取樣本的過程都是完全符合抽取比例的。該算法基本示意圖如圖1所示，其中上方橫線表示整個樣本集，實線箭頭表示取樣點，虛線箭頭表示剔除樣本點。

圖1 改進后的算法基本示意圖

1.2 算法實現過程

設樣本總數為Ns，目的取樣總數Np，取樣周期Ps表示從樣本總數Ns中每Ps個樣本取一個樣本，那么Ps可由下式得到：

(1)

式中，[ ]代表取整，由于Ns、Np不一定可以整除，所以實際取出的樣本數和目的取樣總數Np會產生一定的誤差，實際取樣總數Nr為：

(2)

取樣點數誤差Na為：

Na=Nr-Np。

(3)

由于Ps為取整后的值，所以Na≥0。若Na=0表示沒有取樣點數誤差，即Ns、Np整除，那么只要按照取樣周期Ps從Ns中每Ps個樣本取一個樣本，取出Np個樣本即可。如果Na≠0表示產生了取樣誤差，需要對其進行修正，基本思路是從實際產生的Nr個樣本中盡量均勻地剔除Na個樣本。

由于Nr、Na可能存在最大公約數，將Nr、Na統一除以其最大公約數得到單位實際取樣總數Nr'和單位修正總數Na'，可將問題轉化為從Nr'中均勻剔除Na'，每次得到單位目的取樣數Np'，重復多次得到最終目的樣本數Np的問題：

Ngcd=GCDNr,Na,Na≠0，

(4)

(5)

(6)

式中，GCD( )表示求最大公約數。設取樣修正周期為Pa，那么

(7)

若Pa為整數，即Nr'、Na'可以整除，此時Na'=1，Pa=Nr'，Ngcd=Na，那么只要每取出Pa樣本就剔除最后一個樣本即可。若Pa不為整數，需要將Pa分解為相鄰的2個整數Pa0和Pa1，并相應地將單位修正樣本數Na'分解，將Nr'表達為以下形式：

Nr'=Pa0Na0+Pa1Na1，

(8)

其中，

Pa0=[Pa]，

(9)

Pa1=Pa0+1，

(10)

Na'=Na0+Na1，

(11)

Na1=Na'×(Pa-Pa0)。

(12)

式(8)表示每取出Pa0個樣本就剔除最后一個樣本，一共剔除Na0個，每取出Pa1個樣本就剔除最后一個樣本，一共剔除Na1個，整體一共剔除Na'個樣本。由于Na'可能會很大，如果每隔Pa0連續剔除完Na0個樣本后再每隔Pa1連續剔除完Na1個樣本將會引入一定的不均勻性，為了更均勻地取樣，將按Pa0、Pa1周期剔除的樣本交替剔除，首先計算Na0、Na1的比例：

(13)

若Na0≥Na1，那么每隔Pa0個樣本剔除一個樣本，以這個間隔連續剔除Ra個樣本后，再隔Pa1個樣本剔除一個樣本，如此交替直到剔除完所有Na'個樣本；若Na1>Na0，那么隔Pa0個樣本剔除一個樣本，再每隔Pa1個樣本剔除一個樣本，以這個間隔連續剔除Ra個樣本，如此交替直到剔除完所有Na'個樣本。重復上述過程Ngcd次，完成所有Na個樣本的剔除。綜上所述，算法整體實現流程如圖2所示。

圖2 算法實現流程圖

2 算法在網絡中的典型應用

2.1 令牌桶算法中的應用

令牌桶算法可應用在流量監管、通用流量整形及端口限速等場景中。IETF的RFC2697[1]和RFC2698[2]文件定義了2種令牌桶算法，分別為單速率三色標記算法和雙速率三色標記算法。單速率三色標記算法評估依據以下3個參數：承諾訪問速率(CIR)，即向令牌桶中填充令牌的速率；承諾突發尺寸(CBS)，即令牌桶的容量，每次突發所允許的最大流量尺寸；超額突發尺寸(EBS)。雙速率三色標記算法除了CIR、CBS與單速率三色標記算法一致外，還設置了峰值信息速率(PIR)，峰值突發尺寸(PBS)。

在RFC規定中，令牌添加按照恒定速率CIR添加，即每隔1/CIR時間添加一個令牌，但RFC并沒有指出具體實現過程。不限速時相當于每個單位時間都要放入桶中一個令牌，其一段時間內的所有令牌構成了總樣本，而限速時相當于從這些令牌樣本中按限速比例均勻地選取要投入桶中的令牌即可，因此令牌添加過程本質就是一種按比例取樣均勻的過程，可使用本文算法實現高精度的令牌添加。

以1 000 Mbps網絡帶寬環境下限速21.222 Mbps為例進行算法實現說明。將最終實現結果精確到Bps，令每個令牌表示1 Byte。

首先需要根據取樣精度選取合適的樣本集(樣本數過少會引入誤差)，為了方便，取1 s內的總樣本數Ns為1 000 000 000/8=125 000 000，不限速時相當于每8 ns添加一個令牌，目的取樣總數Np為21 222 000/8=2 652 750，由式(1)與式(2)可得限速添加令牌周期Ps=47，實際速率Nr=2 659 574,根據式(3)得到速率誤差Na=6 824。此時可以看到如果每47×8=376 ns添加一個令牌，實際產生速率為2.659 574 Mbps，速率誤差為6.824 kbps，因此要對其進行修正。根據式(4)～(13)，可以得到Ngcd=2，Nr'=1 329 787，Na'=3 412，Pa0=389，Pa1=390，Na0=893，Na1=2 519，Ra=2。

根據上述結果，按以下流程實現令牌添加過程：

① 每隔376 ns添加一個令牌，每添加389個令牌剔除最后一個令牌，到步驟②；

② 每隔376 ns添加一個令牌，每添加390個令牌剔除最后一個令牌，重復2次，到步驟③；

③ 若已剔除完Na0=893個令牌，則繼續重復步驟②，否則回到步驟①，直到剔除完Na'=3 412個令牌，完成一個單位周期的令牌添加過程，重復單位周期Ngcd=2次完成一個完整周期的令牌添加過程；

④ 不斷重復①～③，進行持續的令牌添加過程，實現網絡限速、整流等應用。

實現時，可以利用FPGA在125 MHz時鐘下精確注入令牌。不限速的情況下每個時鐘周期(8 ns)注入一個令牌，限速情況下，每Ps個時鐘周期注入一個令牌，并根據Pa0,Pa1,Na0,Na1,Ra的情況剔除多余的令牌，不斷重復上述令牌添加過程，實現持續的高精度令牌添加。

2.2 按比例均勻丟包產生

網絡損傷模擬時經常需要實現按比例均勻丟包功能，用戶通過設置預期的丟包率來實現網絡丟包的模擬。按比例均勻丟包的產生本質是一個按比例均勻取樣的過程，即從大量數據包中按比例均勻取出數據包丟棄。下面以產生丟包率3.123%為例進行說明。

將最終實現結果精確到0.001%，即精確到100 000個包丟棄一個包，令樣本總數Ns為100 000。那么目的取樣總數Np為3 123，根據式(1)與式(2)可得取樣周期Ps=32，實際丟包率為Nr=3 125，根據式(3)得到丟包率誤差Na=2。此時可以看到如果每32包丟棄一個包，實際丟包率為3.125%，丟包率誤差為0.002%，需要對其進行修正。根據式(4)～(13)，可以得到Ngcd=1，Nr'=Nr=3 125，Na'=Na=2，Pa0=1 562，Pa1=1 563，Na0=1，Na1=1，Ra=1。

根據上述結果，按以下流程實現丟包產生過程：

① 每32個包丟棄一個包，丟棄1 561個包后，第1 562個標記要丟棄的包不丟棄，到步驟②；

② 每32個包丟棄一個包，丟棄1 562個包后，第1 563個標記要丟棄的包不丟棄，到步驟③；

③ 已修正完Na=2個包，直到取完樣本總數Ns完成一個完整周期的丟包產生過程；

④ 不斷重復①～③，實現持續的均勻丟包產生模擬。

3 結束語

在FPGA上已經使用該算法實現了令牌桶限速和按比例丟包產生功能，并編寫了配置上位機。通過上位機配置界面向FPGA下發限速、丟包率參數，FPGA來實現精準的限速、丟包率控制。通過網絡測試儀器進行測試，測試結果顯示，無論是限速還是丟包產生，與預設速率、預設丟包率的誤差均小于10-5。

該算法不局限于網絡應用，可應用于任何有高精度按比例均勻取樣需求的場景，適用范圍廣，實用性強，實現效果好。