一种流量监管方法和装置

摘要

本发明公开了一种流量监管方法及装置，将在采用流量监管算法进行运算的过程中产生的小数部分隐藏于系统计数器，并在该系统计数器计数的过程中，对该小数部分进行累计并及时地进行进位补偿，采用本发明，可以去除每个队列中间变量小数部分的存储空间，消除了这些小数部分引入的误差，从而使得具体实现准确无误差，同时又节省了存储空间。

权利要求

1.一种流量监管方法，其特征在于，将在采用流量监管算法进行运算的过程中产生的小数部分隐藏于系统计数器，并在该系统计数器计数的过程中，对该小数部分进行累计并及时地进行进位补偿，该方法包括：设置一个参数变量存储单元，用于存储若干个队列对应的压缩参数，以及存储若干个队列对应的无误差中间变量及令牌桶算法；

设置一个可循环计数的基本计数器单元，用于将系统时钟单位转化为队列令牌添加的计时基本单元；

设置一个计时器单元，用于对基本计数器单元的计数循环次数进行累加；

设置一个第一处理单元，用于对小数部分及时进位补偿；

以及，设置一个第二处理单元，用于在新报文到来时能够对存储的配置参数及中间变量进行读取、计算顺序到来的两个报文间隔内应添加的令牌数、执行中间变量回写动作、以及执行令牌桶溢出扫描处理与令牌桶令牌添加。

2.如权利要求1所述的流量监管方法，其特征在于，还包括：设置一个着色及丢弃处理单元，用于对报文执行着色及丢弃处理。

3.如权利要求1或2所述的流量监管方法，其特征在于，以系统内需要的最大计时器位宽作为所有队列的计时器单元的位宽。

4.如权利要求1所述的流量监管方法，其特征在于，基本计数器单元每完成一次循环计数，则重新开始计数，计时器单元据此累计加1。

5.一种流量监管装置，其特征在于，在将其应用于网络流量监管时，将在采用流量监管算法进行运算的过程中产生的小数部分隐藏于系统计数器，并在该系统计数器计数的过程中，对该小数部分进行累计并及时地进行进位补偿，该装置包括：参数变量存储单元，用于存储若干个队列对应的压缩参数，以及存储若干个队列对应的无误差中间变量及令牌桶算法；

可循环计数的基本计数器单元，用于将系统时钟单位转化为队列令牌添加的计时基本单元；

计时器单元，用于对基本计数器单元的计数循环次数进行累加；

第一处理单元，用于对小数部分及时进位补偿；

以及，第二处理单元，用于在新报文到来时能够对存储的配置参数及中间变量进行读取、计算顺序到来的两个报文间隔内应添加的令牌数、执行中间变量回写动作、以及执行令牌桶溢出扫描处理与令牌桶令牌添加。

6.如权利要求5所述的流量监管装置，其特征在于，还包括：着色及丢弃处理单元，用于对报文执行着色及丢弃处理。

7.如权利要求5所述的流量监管装置，其特征在于，计时器单元还用于以系统内需要的最大计时器位宽作为所有队列的计时器单元的位宽。

8.如权利要求5所述的流量监管装置，其特征在于，基本计数器单元每完成一次循环计数，则重新开始计数，计时器单元据此累计加1。

说明书

一种流量监管方法和装置

技术领域

[0001] 本发明涉及通信技术领域，具体而言，尤其涉及一种流量监管方法和装置。

背景技术

[0002] 所谓流量监管，是将进入网络的通信流量控制在承诺的流量范围内，并根据预设的突发条件允许一部分突发流量通过的流量管理机制，其目的是确保通信速率处在承诺的服务限制范围内。

[0003] 目前，业界已具有多种流量监管的算法，其中，几种较为常用的流量监管算法主要包括：srTCM单速率三色标记法，trTCM双速率三色标记法以及MEF10.1规定的可配置的三色标记法，实现过程中，此三种流量监管算法均采用令牌桶对流量进行监测。

[0004] 其中，令牌桶可以看作是一个存有一定容量令牌的装置，系统以某一定填充速率向令牌桶中添加令牌，当令牌桶中令牌满时，再添加的令牌就会溢出，令牌桶中的令牌数不再增加。每到达一个报文，就将需要通过的报文长度与令牌桶中的令牌数进行比较，令牌足够就认为符合流量在允许范围内，此时则允许该报文通过，否则，则认为令牌超过一定界限，从而禁止报文通过，从而达到限制流量的目的。

[0005] 这些不同的流量监管算法一定程度上可以满足不同的应用环境的需求，但是，具体实现时，由于现有的流量监管的实现，基本上都是建立在数字电路的基础之上的，这就导致了在算法的具体计算过程中，一旦产生中间变量带有小数的情况，则我们针对该中间变量无论取多少位小数，都无法避免地会引入误差，而且我们保留的小数位越多，计算过程及中间变量的存储所损耗的资源越大，取的越少，则又会导致精度不够的问题。面对着这样一个要么牺牲资源以换取高精度，要么牺牲精度以换取资源的节省的情况，为此，如何尽可能地提高计算过程以及存储的中间变量的精度，同时又能降低资源损耗，已成为我们不得不面对的一个问题。

[0006] 在当今网络对于高密度、多端口、高可扩展、大容量、灵活可配置，同时还对QoS（Quality of Service、服务质量）都具有高要求的背景下：

[0007] 一方面，关于资源问题，尤其在具有战略意义的高端交换路由领域，需要管控的队列（或称分组、数据流，等等），其数目相当庞大，动辄64k或512k，甚至更大，因此如果每条队列能够减小1bit的存储，就意味着64k或512k甚至更大的存储资源的节省。

[0008] 另一方面，对于几百K的业务流或队列的管理，面临着在灵活的配置下，在流量监管算法的实现过程中会遇到一些带小数的非整数量的处理问题，在数字电路中实施算法时，对于所述小数的计算不可能完全做到穷尽所有小数位，其计算精度无法得到有力的保障，同时，小数位的存储还会耗费大量存储资源，造成资源开销加大。例如，当前流量监管令牌添加算法的实现过程中，有因运算过程中对小数位予以舍弃，或在存储时为节省资源，对小数部分压缩，而导致误差引入的问题。

[0009] 因此，如何在不损失任何小数位以及不进行任何有可能损害QoS质量的压缩处理，就能够较为方便的实现这些小数参与的计算，同时还可以尽可能少地减少资源消耗（尤其是存储器资源），便成为目前一个亟需解决的问题。

发明内容

[0010] 为了解决现有技术提供的流量监管方法在实施时遇到中间变量带有小数，会引入误差而导致精度不够，或计算过程及中间变量的存储而导致资源消耗过大的问题，本发明提供了一种流量监管方法及装置。

[0011] 为了达到本发明的目的，本发明采用以下技术方案实现：

[0012] 一种流量监管方法，将在采用流量监管算法进行运算的过程中产生的小数部分隐藏于系统计数器，并在该系统计数器计数的过程中，对该小数部分进行累计并及时地进行进位补偿。

[0013] 优选地，所述流量监管方法包括：

[0014] 设置一个参数变量存储单元，用于存储若干个队列对应的压缩参数，以及存储若干个队列对应的无误差中间变量及令牌桶算法；

[0015] 设置一个可循环计数的基本计数器单元，用于将系统时钟单位转化为队列令牌添加的计时基本单元；

[0016] 设置一个计时器单元，用于对基本计数器单元的计数循环次数进行累加；

[0017] 设置一个第一处理单元，用于对小数部分及时进位补偿；

[0018] 以及，设置一个第二处理单元，用于在新报文到来时能够对存储的配置参数及中间变量进行读取、计算顺序到来的两个报文间隔内应添加的令牌数、执行中间变量回写动作、以及执行令牌桶溢出扫描处理与令牌桶令牌添加。

[0019] 优选地，所述流量监管方法还包括：

[0020] 设置一个着色及丢弃处理单元，用于对报文执行着色及丢弃处理。

[0021] 优选地，以系统内需要的最大计时器位宽作为所有队列的计时器单元的位宽。

[0022] 优选地，基本计数器单元每完成一次循环计数，则重新开始计数，计时器单元据此累计加1。

[0023] 一种流量监管装置，在将其应用于网络流量监管时，将在采用流量监管算法进行运算的过程中产生的小数部分隐藏于系统计数器，并在该系统计数器计数的过程中，对该小数部分进行累计并及时地进行进位补偿。

[0024] 优选地，所述流量监管装置包括：

[0025] 参数变量存储单元，用于存储若干个队列对应的压缩参数，以及存储若干个队列对应的无误差中间变量及令牌桶算法；

[0026] 可循环计数的基本计数器单元，用于将系统时钟单位转化为队列令牌添加的计时基本单元；

[0027] 计时器单元，用于对基本计数器单元的计数循环次数进行累加；

[0028] 第一处理单元，用于对小数部分及时进位补偿；

[0029] 以及，第二处理单元，用于在新报文到来时能够对存储的配置参数及中间变量进行读取、计算顺序到来的两个报文间隔内应添加的令牌数、执行中间变量回写动作、以及执行令牌桶溢出扫描处理与令牌桶令牌添加。

[0030] 优选地，所述流量监管装置还包括：

[0031] 着色及丢弃处理单元，用于对报文执行着色及丢弃处理。

[0032] 优选地，计时器单元还用于以系统内需要的最大计时器位宽作为所有队列的计时器单元的位宽。

[0033] 优选地，基本计数器单元每完成一次循环计数，则重新开始计数，计时器单元据此累计加1。

[0034] 通过上述本发明的技术方案可以看出，本发明提供的流量监管方法及装置，将运算过程中无法避免会产生的小数部分，隐藏于系统计数器，在计数器计数的过程中，对小数进行累计，并及时将这些小数的累计整数进行进位补偿，从而去除了每个队列中间变量小数部分的存储空间，消除了这些小数部分引入的误差，从而使得具体实现准确无误差，同时又节省了存储空间。

附图说明

[0035] 图1为本发明实施例提供的流量监管装置结构示意图。

[0036] 本发明目的的实现、功能特点及优异效果，下面将结合具体实施例以及附图做进一步的说明。

具体实施方式

[0037] 下面结合附图和具体实施例对本发明所述技术方案作进一步的详细描述，以使本领域的技术人员可以更好的理解本发明并能予以实施，但所举实施例不作为对本发明的限定。

[0038] 本发明实施例提供了一种流量监管方法，依据该方法，将在采用流量监管算法进行运算的过程中产生的小数部分隐藏于系统计数器，并在该系统计数器计数的过程中，对该小数部分进行累计并及时地进行进位补偿，其中，所述流量监管算法为现有的各种算法，例如srTCM单速率三色标记法，trTCM双速率三色标记法以及MEF10.1规定的可配置的三色标记法等。

[0039] 具体地，所述流量监管方法包括：

[0040] S100、设置一个参数变量存储单元，用于存储若干个队列对应的压缩参数，以及存储若干个队列对应的无误差中间变量及令牌桶算法；

[0041] S101、设置一个可循环计数的基本计数器单元，用于将系统时钟单位转化为队列令牌添加的计时基本单元；在实施过程之中，基本计数器单元每完成一次循环计数，则重新开始计数，计时器单元据此累计加1；

[0042] S102、设置一个计时器单元，用于对基本计数器单元的计数循环次数进行累加；优选地，其以系统内需要的最大计时器位宽作为所有队列的计时器单元的位宽；

[0043] S103、设置一个第一处理单元，用于对小数部分及时进位补偿；

[0044] S104、设置一个第二处理单元，用于在新报文到来时能够对存储的配置参数及中间变量进行读取、计算顺序到来的两个报文间隔内应添加的令牌数、执行中间变量回写动作、以及执行令牌桶溢出扫描处理与令牌桶令牌添加。

[0045] 更为优选地，所述流量监管方法还包括：

[0046] S105、设置一个着色及丢弃处理单元，用于对报文执行着色及丢弃处理。

[0047] 如图1所示，本发明实施例还提供了一种流量监管装置，在将其应用于网络流量监管时，将在采用流量监管算法进行运算的过程中产生的小数部分隐藏于系统计数器，并在该系统计数器计数的过程中，对该小数部分进行累计并及时地进行进位补偿。

[0048] 具体地，所述流量监管装置包括：

[0049] 参数变量存储单元，用于存储若干个队列对应的压缩参数，以及存储若干个队列对应的无误差中间变量及令牌桶算法；

[0050] 可循环计数的基本计数器单元，用于将系统时钟单位转化为队列令牌添加的计时基本单元；具体实施时，基本计数器单元每完成一次循环计数，则重新开始计数，计时器单元据此累计加1；

[0051] 计时器单元，用于对基本计数器单元的计数循环次数进行累加；具体实施时，计时器单元还用于以系统内需要的最大计时器位宽作为所有队列的计时器单元的位宽；

[0052] 第一处理单元，用于对小数部分及时进位补偿；

[0053] 以及，第二处理单元，用于在新报文到来时能够对存储的配置参数及中间变量进行读取、计算顺序到来的两个报文间隔内应添加的令牌数、执行中间变量回写动作、以及执行令牌桶溢出扫描处理与令牌桶令牌添加。

[0054] 更为优选地，所述流量监管装置还包括：

[0055] 着色及丢弃处理单元，用于对报文执行着色及丢弃处理。

[0056] 下面举一具体实施例的实现步骤以说明本发明。

[0057] 参考图1，正常的流量监管系统都包括以下部分或全部参数的配置：C桶令牌添加速率，即承诺信息速率（Committed Information Rate，CIR）；C桶桶深，即承诺突发大小（Committed Burst Size，CBS）；E桶令牌添加速率，即超额信息速率（Excess Information Rate，EIR）；E桶桶深，即超额突发大小（Excess Burst Size，EBS）。

[0058] 对各种流量监管算法而言，令牌添加的实现上，E桶或与C桶类似，或在C桶实现的基础上作简单操作，故为简化说明，本文以某一队列的C桶令牌添加为主要处理说明对象，即以某一队列配置的CIR、CBS及令牌添加算法的实现过程作为说明对象。

[0059] 并且，在本发明实施例的实施过程中，其一，其采用的流量监管系统基本都是基于数字电路实现的，定义数字电路系统时钟频率为fs，周期为Ts；其二，实际应用中，承诺信息速率CIR都是一些离散的典型非负整数值，定义为n，比如，我们常见的2M、4M、10M、1G等等。所以流量监管系统中对于承诺信息速率CIR值的配置没有必要做到可连续分布。另外，定义承诺信息速率CIR的基本单位，计为V，单位为字节每秒B/s，业内多见此值为64kbps，即8k B/s，具体实现时，每一队列CIR的配置值，采用CIR与V的倍数关系予以表示，即CIR=n*V。

[0060] 其具体实现过程如下：

[0061] 步骤一，将二进制配置参数n压缩表示为（X*2^Y）,以便将不同队列的承诺信息速率CIR规律化，用以表示CIR与V的倍数关系，即CIR=（X*2^Y）*V，另外，承诺突发大小CBS可直接配置，单位为字节Byte。

[0062] 步骤二，定义一个可循环计数的基本计数器base_cnt, 其为一个用于将系统时钟单位转化为队列令牌添加的计时基本单元。对应同一个Y值的队列共用一个这样的基本计数器base_cnt，即：若系统内参数Y的配置占用y比特，则系统就有（2^y – 1）个这样的基本计数器base_cnt。

[0063] 步骤三，定义一个参数CNT，作为队列计时的基本单元，是基本计数器base_cnt的计数上限, 当基本计数器base_cnt等于（CNT-1）时，则复位为0，重新开始计数。对于某个具体队列参数CNT意义是，每CNT个系统时钟周期，可添加X字节个令牌。

[0064] 步骤四，定义一个二进制整数参数MAX，使其等于系统内所有队列CNT的最大可能取值，Y等于0时，CIR最小，也就是说每添加X字节令牌，所需要时间越久，即这段时间内，系统周期计数器的计数越大，此时CNT值最大。从而可以得到这样的关系：

[0065] CNT= MAX/2^Y=MAX>>Y+(MAX[(Y-1):0]/2^Y)；

[0066] 也就是说，CNT可能不是一个整数，原因是，MAX /2^Y 结果未必是整数，其小数部分就是本发明实施例的处理关键。

[0067] 步骤五，定义一个计时器t，以CNT为计时基本单元的计时器，以系统内需要的最大计时器位宽，作为所有队列的计时器位宽，将该位宽定义为W。具体实现时，它是对基本计数器base_cnt循环计数的次数进行累计; 同一队列顺序接收到的两个报文对应的t的数值差Δt，再乘以X ，即为这两个报文之间这段时间间隔内，令牌桶应该添加的令牌字节数。

[0068] 步骤六，对CNT小数部分的处理，我们将MAX/2^Y 的进一法取整的结果定义为Z，即：

[0069] Z=(MAX[(Y-1):0]==Y’d0)?(MAX>>Y):((MAX>>Y)+1)；

[0070] 定义一个小数r，令r=Z–CNT，由于：

[0071] 一方面， CNT越小，令牌桶添加令牌越频繁，表示承诺信息速率越大；CNT越大，令牌桶添加令牌越缓慢，表示承诺信息速率越小。

[0072] 另一方面，众所周知，在数字电路中实施本方法，令牌添加都是整数字节添加的，同时，数字电路的基本计数器base_cnt计数结果，都是整数个系统周期，若我们定义基本计数器base_cnt，循环计数上限为Z，也就是比CNT值大，那么，我们就人为减缓了了令牌桶的添加频率，即每一个基本计数器base_cnt计数循环就少添加了r*X个字节的令牌，其中r=Z-MAX/2^Y，根据以上步骤中的定义，代入这个式子可得r=0或者r=1-(MAX[(Y-1):0]/2^Y)。

[0073] 即r=(MAX[(Y-1):0]==Y’d0)?0:(1(MAX[(Y-1):0]/2^Y))；

[0074] 定义TNC为MAX [（Y-1）：0] 的补，则：

[0075] TNC = 1(MAX [（Y-1）：0] /2^Y)；

[0076] 同时，又因为0的补码是0，所以 r=TNC/2Y ；即：

[0077] ；

[0078] 其中，TNC[i]表示二进制数TNC/2Y 从右向左低i比特的值，TNC[i]等0或者1。

[0079] 那么，在t时刻，有：

[0080] t*r；

[0081] ；

[0082] ；

[0083] 。

[0084] 上式中，在基本计数器base_cnt每完成一次循环计数，重新开始计数，从而使得计时器为此累计加1时；准确时间位置是当base_cnt = Z-1时，此时计时器的值应为t -1，则有：

[0085] 当t满足条件使得以上多项式中的任意一个子式等于1时，都应该向基本计数器base_cnt进一，且每个子式每次满足进一的时候都及时进一；TNC[i] = 0，则无论t为何值，永远也不会使得对应子式产生进位；

[0086] 每当t为1/ 2- 1的整数倍，即t为2的整数倍，子式t*TNC[Y-1]*2-1就满足一次进一条件，base_cnt重新开始计数的起始值加1；

[0087] 每当t为1/ 2- 2的整数倍，即t为4的整数倍，子式t*TNC[Y-2]*2-2就满足一次进一条件，base_cnt重新开始计数的起始值加1；

[0088] 每当t为1/ 2-(Y-i)的整数倍，即t为2-(Y-i)的整数倍，子式t*TNC[i]*2-(Y-i)就满足一次进一条件，base_cnt重新开始计数的起始值加1；

[0089] 同时有m个子式满足进一条件，基本计数器base_cnt重新开始计数的起始值加m。

[0090] 具体可参考下表：

[0091]Y MAX/ 2Y    MAX>>Y Base_cnt r TNC
0 111_1010_0001_0010 111_1010_0001_0010 111_1010_0001_0010 0 /
1 111_1010_0001_001.0 111_1010_0001_001 111_1010_0001_001 0 0
2 111_1010_0001_00.10 111_1010_0001_00 111_1010_0001_01 0.1 10
3 111_1010_0001_0.010 111_1010_0001_0 111_1010_0001_1 0.11 110
4 111_1010_0001_.0010 111_1010_0001 111_1010_0010 0.111 1110
5 111_1010_000.1_0010 111_1010_000 111_1010_001 .0_1110 0_1110
6 111_1010_00.01_0010 111_1010_00 111_1010_01 .10_1110 10_1110
7 111_1010_0.001_0010 111_1010_0 111_1010_1 .110_1110 110_1110
8 111_1010_.0001_0010 111_1010 111_1011 .1110_1110 1110_1110
9 111_101.0_0001_0010 111_101 111_110 .1_1110_1110 1_1110_1110
10 111_10.10_0001_0010 111_10 111_11 .01_1110_1110 01_1110_1110
11 111_1.010_0001_0010 111_1 1000_0 .101_1110_1110 101_1110_1110
12 111_.1010_0001_0010 111 1000 .0101_1110_1110 0101_1110_1110
13 11.1_1010_0001_0010 11 100 .0_0101_1110_1110 0_0101_1110_1110
14 1.11_1010_0001_0010 1 10 .00_0101_1110_1110 00_0101_1110_1110

[0092] 在步骤六中：t的位宽应大于Y；同时t*X，应不小于CBS。取这两个条件计时器所需要的最大位宽作为计时器的位宽；

[0093] 若二进制数TNC/2Y中有M比特为1，则m的最大值为M，TNC/2Y有Y比特，所以M的最大值为Y，即m的最大值为Y。

[0094] 应寻求使得M小于两倍的Z的实现算法，因为当m>=Z时，基本计数器base_cnt就满足完成一次循环计数过程，t相应进行累加1；而当m>=2Z时，基本计数器base_cnt就满足完成一次循环计数过程，t相应进行累加2，这样实现起来比较繁琐，意义不大。

[0095] 步骤七，令牌添加及中间变量的存储。

[0096] 对于某个队列，存储的中间变量有，最近一个新包到来时，令牌桶内的剩余字节数，定义为Tc , 和时间计数器t的计数值。当某一队列收到一个新报文，则：

[0097] 首先，根据报文中的队列描述信息字段，读取该队列存储的参数配置信息和中间变量，其为本领域技术人员所掌握的公知常识，本文对此不做细述；

[0098] 然后，将当前计时器值与存储的最近一个报文到来时的计时器值，相减，得到的值计为Δt，Δt*X，就是当前时刻与最近一次令牌添加时刻，之间的这段时间内，应向令牌桶添加的令牌数，Δt*X+Tc就是当前令牌桶拥有的令牌数。其中，关于添加令牌的溢出判断和处理，以及报文的着色及丢弃处理，都为本领域技术人员所掌握的公知常识，本文对此不做细述。

[0099] 步骤八，令牌桶溢出扫描。

[0100] 当计时器t计数值，满足任意一个Y值对应的队列的令牌桶溢出条件时 ，扫描所有队列，对比配置参数Y值，是否符合令牌桶溢出添加条件，符合则加满令牌桶，不符合的则忽略，令牌桶保持原值。当扫描到某队列，其符合令牌桶溢出添加条件，同时又收到新的报文，此种情况的处理，已存在有相应专利说明，不在本说明关注范围内。

[0101] 以上所述仅为本发明的优选实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。