一種高精度均勻取樣算法及其網(wǎng)絡(luò)應(yīng)用

武寶剛，白海斌，章 偉

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

0 引言

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

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

1 算法原理和實現(xiàn)過程

1.1 算法原理

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

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

1.2 算法實現(xiàn)過程

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

(1)

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

(2)

取樣點數(shù)誤差Na為：

Na=Nr-Np。

(3)

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

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

Ngcd=GCDNr,Na,Na≠0，

(4)

(5)

(6)

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

(7)

若Pa為整數(shù)，即Nr'、Na'可以整除，此時Na'=1，Pa=Nr'，Ngcd=Na，那么只要每取出Pa樣本就剔除最后一個樣本即可。若Pa不為整數(shù)，需要將Pa分解為相鄰的2個整數(shù)Pa0和Pa1，并相應(yīng)地將單位修正樣本數(shù)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連續(xù)剔除完Na0個樣本后再每隔Pa1連續(xù)剔除完Na1個樣本將會引入一定的不均勻性，為了更均勻地取樣，將按Pa0、Pa1周期剔除的樣本交替剔除，首先計算Na0、Na1的比例：

(13)

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

圖2 算法實現(xiàn)流程圖

2 算法在網(wǎng)絡(luò)中的典型應(yīng)用

2.1 令牌桶算法中的應(yīng)用

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

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

以1 000 Mbps網(wǎng)絡(luò)帶寬環(huán)境下限速21.222 Mbps為例進行算法實現(xiàn)說明。將最終實現(xiàn)結(jié)果精確到Bps，令每個令牌表示1 Byte。

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

根據(jù)上述結(jié)果，按以下流程實現(xiàn)令牌添加過程：

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

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

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

④ 不斷重復(fù)①～③，進行持續(xù)的令牌添加過程，實現(xiàn)網(wǎng)絡(luò)限速、整流等應(yīng)用。

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

2.2 按比例均勻丟包產(chǎn)生

網(wǎng)絡(luò)損傷模擬時經(jīng)常需要實現(xiàn)按比例均勻丟包功能，用戶通過設(shè)置預(yù)期的丟包率來實現(xiàn)網(wǎng)絡(luò)丟包的模擬。按比例均勻丟包的產(chǎn)生本質(zhì)是一個按比例均勻取樣的過程，即從大量數(shù)據(jù)包中按比例均勻取出數(shù)據(jù)包丟棄。下面以產(chǎn)生丟包率3.123%為例進行說明。

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

根據(jù)上述結(jié)果，按以下流程實現(xiàn)丟包產(chǎn)生過程：

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

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

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

④ 不斷重復(fù)①～③，實現(xiàn)持續(xù)的均勻丟包產(chǎn)生模擬。

3 結(jié)束語

在FPGA上已經(jīng)使用該算法實現(xiàn)了令牌桶限速和按比例丟包產(chǎn)生功能，并編寫了配置上位機。通過上位機配置界面向FPGA下發(fā)限速、丟包率參數(shù)，F(xiàn)PGA來實現(xiàn)精準的限速、丟包率控制。通過網(wǎng)絡(luò)測試儀器進行測試，測試結(jié)果顯示，無論是限速還是丟包產(chǎn)生，與預(yù)設(shè)速率、預(yù)設(shè)丟包率的誤差均小于10-5。

該算法不局限于網(wǎng)絡(luò)應(yīng)用，可應(yīng)用于任何有高精度按比例均勻取樣需求的場景，適用范圍廣，實用性強，實現(xiàn)效果好。