一种高精度均匀取样算法及其网络应用

武宝刚，白海斌，章 伟

(中国电子科技集团公司第五十四研究所，河北 石家庄 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。

该算法不局限于网络应用，可应用于任何有高精度按比例均匀取样需求的场景，适用范围广，实用性强，实现效果好。