武寶剛，白海斌，章 偉

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

0 引言

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

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

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

1.1 算法原理

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

圖1 改進(jìn)后的算法基本示意圖

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

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

(1)

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

(2)

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

Na=Nr-Np。

(3)

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

由于Nr、Na可能存在最大公約數(shù)，將Nr、Na統(tǒng)一除以其最大公約數(shù)得到單位實(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'可以整除，此時(shí)Na'=1，Pa=Nr'，Ngcd=Na，那么只要每取出Pa樣本就剔除最后一個(gè)樣本即可。若Pa不為整數(shù)，需要將Pa分解為相鄰的2個(gè)整數(shù)Pa0和Pa1，并相應(yīng)地將單位修正樣本數(shù)Na'分解，將Nr'表達(dá)為以下形式：

Nr'=Pa0Na0+Pa1Na1，

(8)

其中，

Pa0=[Pa]，

(9)

Pa1=Pa0+1，

(10)

Na'=Na0+Na1，

(11)

Na1=Na'×(Pa-Pa0)。

(12)

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

(13)

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

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

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

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

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

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

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

首先需要根據(jù)取樣精度選取合適的樣本集(樣本數(shù)過少會(huì)引入誤差)，為了方便，取1 s內(nèi)的總樣本數(shù)Ns為1 000 000 000/8=125 000 000，不限速時(shí)相當(dāng)于每8 ns添加一個(gè)令牌，目的取樣總數(shù)Np為21 222 000/8=2 652 750，由式(1)與式(2)可得限速添加令牌周期Ps=47，實(shí)際速率Nr=2 659 574,根據(jù)式(3)得到速率誤差Na=6 824。此時(shí)可以看到如果每47×8=376 ns添加一個(gè)令牌，實(shí)際產(chǎn)生速率為2.659 574 Mbps，速率誤差為6.824 kbps，因此要對(duì)其進(jìn)行修正。根據(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é)果，按以下流程實(shí)現(xiàn)令牌添加過程：

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

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

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

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

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

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

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

將最終實(shí)現(xiàn)結(jié)果精確到0.001%，即精確到100 000個(gè)包丟棄一個(gè)包，令樣本總數(shù)Ns為100 000。那么目的取樣總數(shù)Np為3 123，根據(jù)式(1)與式(2)可得取樣周期Ps=32，實(shí)際丟包率為Nr=3 125，根據(jù)式(3)得到丟包率誤差Na=2。此時(shí)可以看到如果每32包丟棄一個(gè)包，實(shí)際丟包率為3.125%，丟包率誤差為0.002%，需要對(duì)其進(jìn)行修正。根據(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é)果，按以下流程實(shí)現(xiàn)丟包產(chǎn)生過程：

① 每32個(gè)包丟棄一個(gè)包，丟棄1 561個(gè)包后，第1 562個(gè)標(biāo)記要丟棄的包不丟棄，到步驟②；

② 每32個(gè)包丟棄一個(gè)包，丟棄1 562個(gè)包后，第1 563個(gè)標(biāo)記要丟棄的包不丟棄，到步驟③；

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

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

3 結(jié)束語

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

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