基于令牌桶算法的填充速率区间的划分方法和装置

摘要

本发明实施例提供了一种基于令牌桶算法的填充速率区间的划分方法和装置，该方法包括：得到在填充速率区间中当前令牌桶内令牌数为最小值时对应的小数位数据位宽M，以及令牌数为最大值时对应的整数位数据位宽N，M和N为正整数；选取所述数据位宽M和数据位宽N中较大的数据位宽；根据所述较大的数据位宽将所述填充速率区间划分成多个子区间，所述子区间中令牌桶内的令牌数对应的数据位宽为所述较大的数据位宽。本发明实施例通过对填充速率区间划分成若干子区间，使得在网络设备的包处理时间间隔较小，而填充速率范围较大时，只需要较小数据位宽的Memory即可实现流量控制的要求，减少了流量控制具体实现的电路资源，从而大幅降低了成本。

说明书

技术领域

本发明涉及数据通信领域，尤其是涉及一种基于令牌桶算法的填充速率区间的划分方法和装置。

背景技术

在数据通信技术中，流量控制是实现服务质量(Quality of Service，QOS)的一个关键技术，通过流量控制，可以为用户提供不同的访问速率和突发带宽。目前数据通信系统中的流量控制基本都是基于RFC2697/RFC2698令牌桶算法来实现的。

以RFC2698规定的tcTCM令牌桶算法为例来说，实现该算法的参数包括：承诺访问速率(Committed Information Rate，CIR)，承诺突发度(Committed Burst Size，CBS)，峰值访问速率(Peak Information Rate，PIR)和峰值突发度(Peak Burst Size，PBS)，其中CBS代表C桶的最大深度，PBS代表P桶的最大深度，CIR为往C桶中增加令牌的速度，PIR为往P桶中增加令牌的速度。

总的来说，利用令牌桶算法实现流量控制的关键是要计算出当前时刻C桶和P桶内的令牌数目，假设t0时刻C桶和P桶内的令牌数分别为Tc(t0)和Tp(t0)，在t1时刻下一个数据包到达的时候，C桶和P桶内的令牌数分另0为Tc(t1)和Tp(t1)，则：

Tc(t1)＝Tc(t0)+(t1-t0)×CIR＝ΔT×CIR；

Tp(t1)＝Tp(t0)+(t1-t0)×PIR＝ΔT×PIR；

即每次进来数据包，都需要刷新此时令牌桶中的令牌数，也即都需要计算ΔT×CIR和ΔT×PIR，由于现在网络技术发展越来越快，使得网络设备的包处理能力也越来越大，这就意味着ΔT的最小值越来越小，即前后两个数据包到达的时间间隔越来越小，这样，当系统对流量控制要求的范围比较大时，即CIR和PIR的范围比较大时，要表示出ΔTmin×CIRmin---ΔTmax×CIRmax的数值范围就比较广，从而要表示该范围内所有的数据就需要有很宽的数据位宽。

由于Tc(tn)和Tp(tn)都存储在外部闪存(Memory)中，数据位宽很大的Tc(tn)和Tp(tn)就导致了需要大容量的Memory加以支持；另外，对于流量控制进行具体实现的电路中，由于涉及到众多的算术运算逻辑，数据位宽很大的Tc(tn)和Tp(tn)将消耗的更多的电路资源。总的来说，数据位宽很大的Tc(tn)和Tp(tn)导致了流量控制的精确实现需要付出更多的成本。

发明内容

本发明实施例提供了基于令牌桶算法的填充速率区间的划分方法和装置，在网络设备的包处理时间间隔较小，而填充速率范围较大时，可以占用较小的数据位宽来达到精确的流量控制要求。

一方面，本发明实施例提出了一种基于令牌桶算法的填充速率区间的划分方法，该方法包括：得到在填充速率区间中当前令牌桶内令牌数为最小值时对应的小数位数据位宽M，以及令牌数为最大值时对应的整数位数据位宽N，M和N为正整数；选取所述数据位宽M和数据位宽N中较大的数据位宽；根据所述较大的数据位宽将所述填充速率区间划分成多个子区间，所述子区间中令牌桶内的令牌数对应的数据位宽为所述较大的数据位宽。

另一方面，本发明实施例还提出了一种基于令牌桶算法的填充速率区间的划分装置，包括：数据位宽获取单元，用于得到在填充速率区间中当前令牌桶内令牌数为最小值时对应的小数位数据位宽M，以及令牌数为最大值时对应的整数位数据位宽N，M和N为正整数；选择单元，用于选取所述数据位宽M和数据位宽N中较大的数据位宽；区间划分单元，用于根据所述较大的数据位宽将所述填充速率区间划分成多个子区间，所述子区间中令牌桶内的令牌数对应的数据位宽为所述较大的数据位宽。

本发明实施例通过对填充速率区间划分成若干子区间，使得在网络设备的包处理时间间隔较小，而填充速率范围较大时，可以占用较小的数据位宽精确表示当前桶内的令牌数并保证了流量控制的精度，而较小的数据位宽也放宽了对Memory规格的要求，以及减少了流量控制具体实现的电路资源，从而大幅降低了成本。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为发明实施例提供的一种基于令牌桶算法的填充速率区间的划分方法流程示意图；

图2为发明实施例提供的另一种基于令牌桶算法的填充速率区间的划分方法流程示意图；

图3为本发明实施例提供的一种基于令牌桶算法的填充速率区间的划分装置结构示意图；

图4为本发明实施例提供的另一种基于令牌桶算法的填充速率区间的划分装置结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

如图1为本发明实施例提供的一种基于令牌桶算法的填充速率区间的划分方法流程示意图，该方法包括如下步骤：

S101：得到在填充速率区间中当前令牌桶内令牌数为最小值时对应的小数位数据位宽M，以及令牌数为最大值时对应的整数位数据位宽N，M和N为正整数。

在本实施例中，填充速率既可以为往C桶中添加令牌的CIR，也可以为往P桶中添加令牌的PIR。以CIR为例来说，设当有数据包达到时的当前令牌桶内令牌数为Tc(tn)，而上一个数据包到达后令牌桶内剩余令牌数为Tc(tn-1)，两个数据包达到的时间间隔为ΔT，则：

Tc(tn)＝Tc(tn-1)+ΔT×CIR；

可见，当ΔT取最小值，且CIR取最小值时，Tc(tn)内的令牌数为最小值；而当ΔT取最大值，且CIR取最大值时，Tc(tn)内的令牌数为最大值。而该最小值及最大值都需要用二进制计算机语言进行表示后再进行相关的数据处理，因此该最小值及最大值都会对应一定的数据位宽。

为了更清楚地对本步骤进行说明，在本实施例中假设CIR范围为10Kbps～50Gbps，ΔT范围为10ns～100ms，

则Tc(tn)内的令牌数为最小值时：

(ΔT×CIR)_min＝ΔT_min×CIR_min＝10Kbps×10ns＝10×10³×10×10^-9

≈10^-1×2^-10；

Tc(tn)内的令牌数为最大值时：

(ΔT×CIR)_max＝ΔT_max×CIR_max＝50Gbps×100ms＝50×10⁹×100×10^-3

≈5×2³⁰；

由上述(ΔT×CIR)_min及(ΔT×CIR)_max的结果可知，Tc(tn)内的令牌数为最小值时，需要13bit的小数来表示(ΔT×CIR)_min；而Tc(tn)内的令牌数为最大值时，需要33bit的整数来表示(ΔT×CIR)_max，即此时M＝13bit，N＝33bit。

S102：选取所述数据位宽M和数据位宽N中较大的数据位宽。

为了保证最终流量控制的精度，即保证选取的数据位宽可以表示出(ΔT×CIR)_min～(ΔT×CIR)_max中任意一个数值，需要选取M和N中较大的数据位宽，假设ΔT的范围和CIR的范围如步骤S101中所设，则选择33bit的数据位宽。

S103：根据所述较大的数据位宽将所述填充速率区间划分成多个子区间，所述子区间中令牌桶内的令牌数对应的数据位宽为所述较大的数据位宽。

根据步骤S101的描述，需要精确表示(ΔT×CIR)_min~(ΔT×CIR)_max这个范围内的所有数值，需要(13+33＝46)bit宽度的数据来加以表示。而本发明实施例通过将一个大范围的填充速率区间划分成多个子区间，每个子区间内对应的ΔT×CIR都可以用相比于现有技术46bit而言较小宽度的数据加以表示，在本实施例中，为了保证最终流量控制的精度，该较小宽度选用M和N中较大的数据位宽，即步骤S102中所选择的33bit的数据位宽。

当然，作为本发明的一个实施例，作为填充速率区间划分依据的数据位宽也可以大于M和N中较大的值，而小于M+N的值，这样，相对于现有技术而言，仍然可以在一定程度上减少数据位宽的占用。

本发明实施例通过对填充速率区间划分成若干子区间，使得在网络设备的包处理时间间隔较小，而填充速率范围较大时，可以占用较小的数据位宽精确表示当前桶内的令牌数并保证了流量控制的精度，而较小的数据位宽也放宽了对Memory规格的要求，以及减少了流量控制具体实现的电路资源，从而大幅降低了成本。

如图2所示为本发明实施例提供的另一种基于令牌桶算法的填充速率区间的划分方法流程示意图，该方法包括如下步骤：

S201：得到在填充速率区间中当前令牌桶内令牌数为最小值时对应的小数位数据位宽M，以及令牌数为最大值时对应的整数位数据位宽N；

其中，在本发明实施例中，M和N为正整数。

具体来说，小数位数据位宽M可以根据下述方式得到：计算ΔT_min×V_min，其中ΔT_min为填充时间ΔT的最小值，V_min为填充速率V的最小值，根据ΔT_min×V_min的结果得到所述小数位数据位宽M；

整数位数据位宽N可以根据下述方式得到：计算ΔT_max×V_max，其中ΔT_max为填充时间ΔT的最小值，V_max为填充速率V的最大值，根据ΔT_max×V_max的结果得到所述整数位数据位宽N。

S202：选取所述数据位宽M和数据位宽N中较大的数据位宽；

在本发明实施例中，如果采用上述实施例中的数据，即选取33bit的数据位宽。

S203：判断M是否大于N，如果是，进入步骤S207，如果否，进入步骤S204；

S204：由于整数位数据位宽N大于小数位数据位宽M，则当填充速率选用最小值V_min，填充时间选用ΔT_min时，其对应的小数位数据位宽为M；而在总位宽为N的情况下，当填充速率选用最小值V_maxA，填充时间选用ΔT_max时，其对应的整数位数据位宽为(N-M)，则根据公式ΔT_max×V_maxA＝2^N-M可以计算出V_maxA，以V_min～V_maxA作为第A速率区间；

其中，在本发明实施例中，A＝1；

S205：根据ΔT_min×V_maxA的结果判断该结果是否为纯小数，如果是，则根据ΔT_min×V_maxA的2次幂结果得到小数位数据位宽M1，并进入步骤S206，如果否，则结束区间划分。

S206：令M＝M1、V_min＝V_maxA并返回步骤S204，A+＝1。

下面通过一具体实例来对步骤S204-S206加以进一步说明，假设CIR范围为10Kbps～50Gbps，ΔT范围为10ns～100ms，则M＝13bit，N＝33bit，则：

第一速率区间的划分：ΔT_max×V_max1＝100ms×V_max1＝2^N-M＝2^33-13＝2²⁰；

从上式得到V_max1＝10.24Mbps，则第一速率区间为V_min～V_max1，即10Kbps～10.24Mbps；

ΔT_min×V_max1＝10ns×*10.24Mbps＝10×*10^-9×*10.24×*10⁶

≈1.6×2^-4；

从上式可得到ΔT_min×V_max1结果为纯小数，且M1＝4，则：M＝M1＝4，V_min＝V_max1＝10.24Mbps，A＝2。

第二速率区间的划分：ΔT_max×V_max2＝100ms×V_max2＝2^N-M＝2^33-4＝2²⁹；

从上式得到V_max2＝5.12Gbps，则第二速率区间为V_min～V_max2，即10.24Mbps～5.12Gbps；

ΔT_min×V_max2＝10ns×5.12Gbps＝10×10^-9×5.12×10⁹

≈51.2；

由于上式51.2大于1，不是纯小数，则结束区间划分，第三速度区间为5.12Gbps～50Gbps。

S207：根据公式ΔT_min×V_minB＝2^N-M计算出V_minB，以V_minB～V_max作为第B速率区间，其中B＝1；

S208：根据ΔT_max×V_minB的结果判断是否为纯整数，如果是，则得到整数位数据位宽N1，并进入步骤S209，如果不是，则结束区间划分。

S209：令N＝N1、V_max＝V_minB并返回步骤S207，B+＝1。

下面通过一具体实例来对步骤S207-S209加以进一步说明，假设CIR范围为0.001Kbps～50Mbps，ΔT范围为1ns～10ms，

则Tc(tn)内的令牌数为最小值时：

(ΔT×CIR)_min＝ΔT_min×CIR_min＝0.001Kbps×lns＝10^-3×10³×1×10^-9

＝10^-9≈2^-30；

Tc(tn)内的令牌数为最大值时：

(ΔT×CIR)_max＝ΔT_max×CIR_max＝50Mbps×10ms＝50×10⁶×10×10^-3

≈500×2¹⁰；

由上述(ΔT×CIR)_min及(ΔT×CIR)_max的结果可知，Tc(tn)内的令牌数为最小值时，需要30bit的小数来表示(ΔT×CIR)_min；而Tc(tn)内的令牌数为最大值时，需要19bit的整数来表示(ΔT×CIR)_max，即此时M＝30bit，N＝19bit，则第一速率区间的划分：ΔT_min×V_minB＝lns×V_min1＝2^N-M＝2^19-30＝2^-11；

从上式得到V_min1≈2Kbps，则第一速率区间为V_min1～V_max，即2Kbps～50Mbps；

ΔT_max×V_min1＝10ms×2Kbps＝10×10^-3×2×10³

≈20；

从上式可得到ΔT_max×V_max1结果为纯整数，且N1＝5，则：N＝N1＝5，V_max＝V_min1＝2Kbps，B＝2。

第二速率区间的划分：ΔT_min×V_min2＝1ns×V_min2＝2^N-M＝2^5-30＝2^-25；

从上式得到V_min2＝0.032Kbps，则第二速率区间为V_min2～V_max，即0.032Kbps～2Kbps；

ΔT_max×V_min2＝10ms×0.032Kbps＝10×10^-3×0.032×10³

≈10×2^-5；

由于上式10×2^-5小于1，不是纯整数，则结束区间划分，第三速度区间为0.001Kbps～0.032Kbps。

本发明实施例通过对填充速率区间划分成若干子区间，使得在网络设备的包处理时间间隔较小，而填充速率范围较大时，可以占用较小的数据位宽精确表示当前桶内的令牌数并保证了流量控制的精度，而较小的数据位宽也放宽了对Memory规格的要求，以及减少了流量控制具体实现的电路资源，从而大幅降低了成本。

如图3所示为本发明实施例提供的一种基于令牌桶算法的填充速率区间的划分装置结构示意图，该装置包括：数据位宽获取单元310、选择单元320和区间划分单元330，其中选择单元320分别和数据位宽获取单元310及区间划分单元330相连，其中：

数据位宽获取单元310，用于得到在填充速率区间中当前令牌桶内令牌数为最小值时对应的小数位数据位宽M，以及令牌数为最大值时对应的整数位数据位宽N，M和N为正整数。

在本实施例中，上述填充速率既可以为往C桶中添加令牌的CIR，也可以为往P桶中添加令牌的PIR。以CIR为例来说，设当有数据包达到时的当前令牌桶内令牌数为Tc(tn)，而上一个数据包到达后令牌桶内剩余令牌数为Tc(tn-1)，两个数据包达到的时间间隔为ΔT，则：

Tc(tn)＝Tc(tn-1)+ΔT×CIR；

可见，当ΔT取最小值，且CIR取填充速率区间内的最小值时，Tc(tn)内的令牌数为最小值；而当ΔT取最大值，且CIR取填充速率区间内的最大值时，Tc(tn)内的令牌数为最大值。而该最小值及最大值都需要用二进制计算机语言进行表示后再进行相关的数据处理，因此该最小值及最大值都会对应一定的数据位宽。

选择单元320用于选取所述数据位宽M和数据位宽N中较大的数据位宽。为了保证最终流量控制的精度，即保证选取的数据位宽可以表示出(ΔT×CIR)_min～(ΔT×CIR)_max中任意一个数值，需要选取M和N中较大的数据位宽，

区间划分单元330用于根据所述较大的数据位宽将所述填充速率区间划分成多个子区间，所述子区间中令牌桶内的令牌数对应的数据位宽为所述较大的数据位宽。

对于现有技术而言，需要精确表示(ΔT×CIR)_min～(ΔT×CIR)_max这个范围内的所有数值，需要(M+N)bit宽度的数据来加以表示。而本发明实施例通过将一个大范围的填充速率区间划分成多个子区间，每个子区间内对应的ΔT×CIR都可以用相比于现有技术(M+N)bit而言较小宽度的数据加以表示，在本实施例中，为了保证最终流量控制的精度，该较小宽度选用M和N中较大的数据位宽。

当然，作为本发明的一个实施例，作为填充速率区间划分依据的数据位宽也可以大于M和N中较大的值，而小于M+N的值，这样，相对于现有技术而言，仍然可以在一定程度上减少数据位宽的占用。

本发明实施例通过对填充速率区间划分成若干子区间，使得在网络设备的包处理时间间隔较小，而填充速率范围较大时，可以占用较小的数据位宽精确表示当前桶内的令牌数并保证了流量控制的精度，而较小的数据位宽也放宽了对Memory规格的要求，以及减少了流量控制具体实现的电路资源，从而大幅降低了成本。

如图4所示为本发明实施例提供的另一种基于令牌桶算法的填充速率区间的划分装置结构示意图，该装置包括：数据位宽获取单元410、选择单元420和区间划分单元430，其中数据位宽获取单元410还包括第一获取模块411和第二获取模块412，而区间划分单元430还包括第一区间划分模块431和第二区间划分模块432。选择单元420的作用和图3对应实施例中相类似，不再进行赘述。

第一获取模块411用于计算ΔT_min×V_min，其中ΔT_min为填充时间ΔT的最小值，V_min为填充速率V的最小值，根据ΔT_min×V_min的结果得到所述小数位数据位宽M。

第二获取模块412用于计算ΔT_max×V_max，其中ΔT_max为填充时间ΔT的最小值，V_max为填充速率V的最小值，根据ΔT_max×V_max的结果得到所述整数位数据位宽N。

第一区间划分模块431用于执行如下操作：

a.根据公式ΔT_max×V_maxA＝2^N-M计算出V_maxA，以V_min～V_maxA作为第A速率区间，其中A＝1；

b.根据ΔT_min×V_maxA的结果判断所述结果是否为纯小数，如果是，则根据所述结果得到小数位数据位宽M1，令M＝M1、V_min＝V_maxA并返回步骤a，A+＝1。

具体的描述可以参见图2对应实施例中关于步骤S204-S206的描述。

第二区间划分模块432用于执行如下操作：

c.根据公式ΔT_min×V_minB＝2^N-M计算出V_minB，以V_minB～V_max作为第B速率区间，其中B＝1，V_max0＝V_max；

d.根据ΔT_max×V_maxB的结果判断所述结果是否为纯整数，如果是，则根据所述结果得到整数位数据位宽N1，令N＝N1、V_max＝V_minB并返回步骤c，B+＝1。

具体的描述可以参见图2对应实施例中关于步骤S207-S209的描述。

本发明实施例通过对填充速率区间划分成若干子区间，使得在网络设备的包处理时间间隔较小，而填充速率范围较大时，可以占用较小的数据位宽精确表示当前桶内的令牌数并保证了流量控制的精度，而较小的数据位宽也放宽了对Memory规格的要求，以及减少了流量控制具体实现的电路资源，从而大幅降低了成本。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-Only Memory，ROM)或随机存储记忆体(Random Access Memory，RAM)等。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。