201110048493.2、 发明名称为 "一种令牌发放方法和系统" 的中国专利 申请的优先权， 其全部内容通过引用结合在本申请中。

技术领域

本发明属于通信技术领域， 具体涉及一种令牌发放方法和系统。 背景技术

令牌桶 （ Token Bucket ) 是一种常见的流量测量技术， 常用于对业 务板的流量进行限制和整形， 还能够对流量的速率进行测量。 其工作原 理是， 令牌桶按用户设定的速度向桶中放置令牌， 当桶中令牌的数量超 出桶的容量的时候， 令牌的数量不再增加。 当报文到来时， 如果令牌桶 中有足够的令牌可以用来发送报文， 则报文直接通过并继续发送， 同时 令牌桶中的令牌量按报文的长度做相应的减少 ； 如果令牌桶中的令牌数 量不足或为空， 则无法得到足够转发令牌的报文将被丟弃或进 行标记， 此时令牌桶中的令牌数量不发生变化。

在实现本发明的过程中发明人发现， 目前令牌桶只能够对单个业务 板上的接口流量进行测量， 无法对分布在不同业务板上的一组接口流量 进行统一测量。

发明内容

本发明实施例提供了一种令牌发放方法和系统 ， 能够对不同业务板 上的接口流量实现统一测量。

本发明实施例釆用如下技术方案：

一种令牌发放方法， 包括：

设置一个负责全局令牌发放的主发放模块； 在每个需要统一进行流量测量的业务板上设置 各自的令牌桶； 所述主发放模块以消息环的方式向每个所述业 务板上的令牌桶统 一发放令牌。

一种令牌发放系统， 包括：

主发放模块， 用于负责全局令牌发放；

多个令牌桶， 分别设置于多个需要统一进行流量测量的业务 板； 所述主发放模块用于以消息环的方式向每个所 述业务板上的令牌 桶统一发放令牌。

由本发明实施例的上述技术方案可知， 通过设置一个负责全局令牌 发放的主发放模块， 并在每个需要统一进行流量测量的业务板上设 置各 自的令牌桶， 由所述主发放模块以消息环的方式对每个所述 业务板上的 令牌桶统一发放令牌， 从而可以对不同业务板上的接口流量实现统一 测 量。

附图说明

下面对本发明描述中所需要使用的附图作一简 单地介绍。

图 1为本发明实施例提供的一种令牌发放方法的� �意图； 图 2为本发明实施例提供的一种令牌发放系统的� �意图； 图 3为应用本发明实施例提供的令牌发放方法的� �个具体示例。 具体实施方式

下面结合附图及实施例， 对本发明的技术方案进行清楚、 完整地描 述。

参见图 1 , 本发明实施例提供的一种令牌发放方法， 包括：

S 11 , 设置一个负责全局令牌发放的主发放模块。

其中， 主发放模块可以选择槽位最小的业务板上的令 牌发放模块承 担， 也可以由专门的业务板承担。 512 ,在每个需要统一进行流量测量的业务板上设� �各自的令牌桶。 在每个需要统一进行流量测量的业务板上都独 立设置各自的令牌 桶， 但每个业务板的令牌桶不独立发放令牌。

513 , 所述主发放模块以消息环的方式向每个所述业 务板上的令牌 桶统一发放令牌。

参见图 2 ,图 2为本发明实施例提供的一种令牌发放系统的� �意图。 所述消息环的方式具体可以是： 所述主发放模块发出令牌发放消息， 将 所述令牌发放消息按逻辑环顺序依次向每个所 述业务板上的令牌桶进 行转发， 并在所述令牌发放消息回到所述主发放模块时 结束本轮的令牌 发放； 然后所述主发放模块发出新一轮的令牌发放消 息， 开始新一轮的 令牌发放。 其中， 所述令牌发放消息携带有： 所述主发放模块的地址、 要发送的下一个业务板的令牌桶的地址、 若干数量的旧令牌和若干数量 的新令牌。 在具体实现时， 若干数量的旧令牌或新令牌可以分别用一个 数值表示， 业务板上的令牌桶从令牌发放消息中领取多少 数量的令牌， 就将令牌发放消息中旧令牌与新令牌的总数值 减去相应的数量， 如令牌 桶领取了 3个令牌， 则将新旧令牌的总数值减去 3。。

主发放模块可以将令牌发放消息简单地按业务 板的槽位号的顺序 进行转发， 达到最高 （升序） 或最低槽位 （降序） 时返回到最低或最高 槽位， 直到最后回到主发放模块所在的业务板， 回到主发放模块， 形成 一个环。

需要说明的是， 上述消息环为逻辑上的环， 环上每个节点需要维护 其下行节点的地址。 消息环的实际物理结构既可以是环型结构、 总线结 构、 全互连结构还可以是交换结构。

下面对令牌发放消息转发过程进行具体说明：

当令牌发放消息按逻辑环顺序依次向每个所述 业务板上的令牌桶 进行转发时， 每个所述业务板上的令牌桶从收到的令牌发放 消息中领取 所需数量的令牌， 并将所述令牌发放消息中的旧令牌数量和 /或新令牌 数量以及要发送的下一个业务板的令牌桶的地 址进行更新， 更新后的令 牌总数为原有令牌总数（新旧令牌的数量之和 ）减去领取的令牌数量后 剩余的令牌数量， 然后依据更新后的所述令牌发放消息中的要发 送的下 一个业务板的令牌桶的地址， 将更新后的所述令牌发放消息转发给逻辑 环顺序中的下一个业务板的令牌桶。

需要说明的是， 在令牌发放消息中包括两种令牌， 一种是本轮分配 的新令牌， 一种是上一轮剩余的旧令牌。 对于上一轮剩余的旧令牌， 最 多保留一圈， 在进行新一轮的令牌发放消息转发时， 上一轮剩余的令牌 都变为旧令牌， 同时发放本轮的新令牌。

对于旧令牌， 任何令牌桶都可以不受限制地领取， 而且优先领取旧 令牌， 并在旧令牌领取完后再领取新令牌。 当令牌发放消息中的新令牌 数量被领取完毕时， 则结束本轮的令牌发放。 这样做的好处是， 可以较 灵活地控制不同业务板上的令牌桶从令牌发放 消息中领取的令牌数量， 例如在令牌发放消息中的旧令牌数量充足的情 况下， 先领取令牌的令牌 桶可以不受限制地领取到所需要数量的令牌。

另外， 为了防止令牌长期被第一次领取令牌的令牌桶 占用， 有必要 规定第一次从令牌发放消息中一次领取的新令 牌的数量， 例如规定不能 超过每一轮分配新令牌数量的一半， 当然也可以设置为其它比例。

在令牌发放消息中的新旧令牌被领取完毕时， 有两种方案开始新一 轮的令牌发放。 一种方案是， 如图 2所示， 最后领取令牌的令牌桶依据 所述令牌发放消息中的所述主发放模块的地址 直接向所述主发放模块 发送令牌发放完毕消息， 此时主发放模块发出的新一轮令牌发放消息， 则直接从该业务板开始， 向该业务板的令牌桶返回新一轮的令牌发放消 息， 在该新一轮的令牌发放消息中携带有新分配的 令牌（此时该新一轮 的令牌发放消息中携带的令牌全部为新令牌） 。 该方案可以保证最后领 取令牌的令牌桶及时领取到所需数量的令牌， 但每一轮令牌发放的时间 无法固定。

另一种方案是， 每一轮的令牌发放消息都统一绕环转发， 即使令牌 发放完毕也绕环一周到达所述主发放模块所在 的业务板， 此时主发放模 块发出的新一轮的令牌发放消息再绕环转发到 最后领取令牌的令牌桶 后才开始分配令牌。 具体实现是， 最后领取令牌的令牌桶依据所述令牌 发放消息中的要发送的下一个业务板的令牌桶 的地址， 将令牌发放完毕 消息转发给逻辑环顺序中的下一个业务板的令 牌桶， 直至所述令牌发放 完毕消息按逻辑环顺序转发到所述主发放模块 ， 并所述主发放模块发出 新一轮的令牌发放消息再按逻辑环顺序转发到 所述最后领取令牌的令 牌桶后， 开始新一轮的令牌发放。 该方案可以将每一轮令牌发放时间固 定。

上述两种方案都是从最后领取令牌的业务板才 开始新一轮的令牌 发放， 其目的是保证每个业务板的令牌桶都能够平等 地领取到令牌。

本发明实施例的令牌发放方法， 通过设置一个负责全局令牌发放的 主发放模块， 并在每个需要统一进行流量测量的业务板上设 置各自的令 牌桶， 然后由所述主发放模块以消息环的方式对每个 所述业务板上的令 牌桶统一发放令牌， 从而可以对不同业务板上的接口流量实现统一 测 量。

下面釆用一个限制 VPN ( Virtual Private Network , 虚拟专用网络） 总带宽的例子对本发明实施例的令牌发放方法 进行具体说明。

参见图 3 , 图 3为应用本发明实施例提供的令牌发放方法的� �个具 体示例。 假设用户 VPN与运营商签约的带宽为 5Μ字节 /秒， 最大突发 尺寸为 2Κ字节， 假设 5个接入点的报文对应接入设备 5块业务板上， 在 5块业务板上分别配置有承诺速率为 5Μ字节 /秒、 突发尺寸为 2Κ的 令牌桶， 并且假设主发放模块按每毫秒 5Κ字节的速度发放令牌， 每个 令牌桶最大能够获取的令牌数为 2K字节， 贝 'J :

令牌发放消息到达 Α令牌桶， 发放令牌数为 5K字节， A令牌桶最 大领取 2K字节的令牌， 剩余 3K字节令牌转发给 B令牌桶；

B令牌桶同样领取 2K字节， 剩余令牌数为 1K字节， 转发给 C令 牌桶；

C令牌桶只能领取 1K字节令牌， 消息返回给主发放模块； 下一个毫秒， 主发放模块将新的令牌发放消息发往 C令牌桶， C令 牌桶领取 1.5K令牌（假设已经消耗了 0.5K令牌）， 剩余 3.5K令牌， 转 发给 D令牌桶；

D令牌桶领取 2K字节令牌， 剩余 1.5K 令牌， 转发给 E令牌桶；

E令牌桶领取 1.5K 字节令牌后， 转发给主发放模块；

下一个毫秒， 主发放模块将新的令牌发放消息发往 E令牌桶， E令 牌桶领取 1K令牌 （假设已经消耗了 0.5K令牌）， 剩余 4K令牌， 转发 给主发放模块；

下一个毫秒，主发放模块开始新一轮令牌发放 ，这时令牌发放消息， 剩余旧令牌 4K, 新令牌 5K;

A令牌桶这时消耗了 1.5K令牌， 领取 1.5K的旧令牌， 剩余旧令牌 2.5k, 新令牌 5K, 转发给 B令牌桶；

B令牌桶消耗了 1K令牌， 领取 1K旧令牌， 剩余旧令牌 1.5K, 新 令牌 5K, 转发给 C令牌桶；

C令牌桶消耗了令牌 2K, 领取 1.5K旧令牌和 0.5K新令牌， 剩余 4.5K新令牌转发给 D令牌桶；

D令牌桶消耗了令牌 2K, 领取 2K新令牌， 剩余 2.5K新令牌， 转 发给 E令牌桶；

E令牌桶也消耗了 2K令牌， 领取 2K新令牌， 剩余 0.5K新令牌， 转发给主发放模块； 下一毫秒， 主发放模块开始新一轮令牌发放， 这时旧令牌为 0.5K, 新令牌为 5K：。

需要说明的是， 为实现总带宽的限制功能， 主发放模块按配置的速 率向各业务板上的令牌桶发放令牌时， 每轮的令牌发放时间可以固定， 也可以不固定。 在每轮发放时间固定时， 主发放模块在每一轮令牌发放 消息中新分配的令牌数量固定； 在每轮发放时间不固定时， 主发放模块 根据消息发送到返回的时间间隔按下发速率计 算出下一轮可以分配的 令牌数量。 例如， 上述对于 5M字节 /秒的限速应用， 如果在某一轮令牌 发放中， 从令牌发放消息发送到返回到主发放模块的时 间由原来的 1ms 变为 0.5ms , 即该轮的令牌发放时间缩短了一半， 则下一轮令牌发放数 量不再是 5K, 而是 10K, 这样就可以克服消息环传递时延的影响。 可 以理解的是， 上述消息环传递的时延越小控制的精度越高， 因此在设计 消息环时可以要求消息转一圈的时延小于令牌 发放的时间间隔。

仍参见图 2 , 本发明实施例提供的一种令牌发放系统， 包括： 主发放模块， 用于负责全局令牌发放；

多个令牌桶， 分别设置于多个需要统一进行流量测量的业务 板； 所述主发放模块用于以消息环的方式向每个所 述业务板上的令牌 桶统一发放令牌。

其中， 所述主发放模块具体可以用于： 发出令牌发放消息， 将所述 令牌发放消息按逻辑环顺序依次向每个所述业 务板上的令牌桶进行转 发， 并在所述令牌发放消息回到所述主发放模块时 结束本轮的令牌发 放； 然后发出新一轮的令牌发放消息， 开始新一轮的令牌发放； 其中， 所述令牌发放消息携带有： 所述主发放模块的地址、 要发送的下一个业 务板的令牌桶的地址、 若干数量的旧令牌和若干数量的新令牌； 以及， 每个所述业务板上的令牌桶在收到所述令牌发 放消息时， 从所述令 牌发放消息中领取所需数量的令牌， 并将所述令牌发放消息中的旧令牌 数量和 /或新令牌数量以及要发送的下一个业务板的� �牌桶的地址更新 后，依据更新后的所述令牌发放消息中的要发 送的下一个业务板的令牌 桶的地址， 将更新后的所述令牌发放消息转发给逻辑环顺 序中的下一个 业务板的令牌桶。

需要说明的是， 对于旧令牌， 任何令牌桶都可以不受限制地领取， 而且优先领取旧令牌， 并在旧令牌领取完后再领取新令牌。 当令牌发放 消息中的新令牌被领取完毕时， 则结束本轮的令牌发放。 这样做的好处 是， 可以较灵活地控制不同业务板上的令牌桶从令 牌发放消息中领取的 令牌数量， 例如在令牌发放消息中的旧令牌数量充足的情 况下， 先领取 令牌的令牌桶可以不受限制地领取到所需要数 量的令牌。

在所述令牌发放消息中的新旧令牌被领取完毕 时， 为保证每个业务 板的令牌桶都能够平等地领取到令牌， 一种方案是， 最后领取令牌的令 牌桶依据所述令牌发放消息中的所述主发放模 块的地址直接向所述主 发放模块发送令牌发放完毕消息， 并在所述主发放模块将新一轮的令牌 发放消息直接发送到所述最后领取令牌的令牌 桶后， 开始新一轮的令牌 发放。 此时所述主发放模块还具体用于： 接收最后领取令牌的令牌桶直 接发送的令牌发放完毕消息， 并向所述最后领取令牌的令牌桶直接返回 新一轮的令牌发放消息后， 开始新一轮的令牌发放。

另一种方案是， 最后领取令牌的令牌桶依据所述令牌发放消息 中的 要发送的下一个业务板的令牌桶的地址向给逻 辑环顺序中的下一个业 务板的令牌桶发送令牌发放完毕消息， 并在所述令牌发放完毕消息按逻 辑环顺序转发到所述主发放模块， 由所述主发放模块发出的新一轮的令 牌发放消息再按逻辑环顺序转发到所述最后领 取令牌的令牌桶后， 开始 新一轮的令牌发放。 此时所述主发放模块还具体用于： 接收最后领取令 牌的令牌桶按逻辑环顺序转发的令牌发放完毕 消息， 并将发出的新一轮 的令牌发放消息按逻辑环顺序转发到所述最后 领取令牌的令牌桶后， 开 始新一轮的令牌发放。

本发明实施例的令牌发放装置， 通过在每个需要统一进行流量测量 的业务板上设置各自的令牌桶， 由主发放模块负责全局令牌发放， 以消 息环的方式对每个所述业务板上的令牌桶统一 发放令牌， 从而可以对不 同业务板上的接口流量实现统一测量。

本发明实施例提供的令牌发放方法和系统可以 应用到数据通信领 域的交换机或路由器产品， 也可应用到无线领域的数据网关产品中。

以上所述， 仅为本发明的具体实施方式， 但本发明的保护范围并不 局限于此， 任何熟悉本技术领域的技术人员在本发明揭露 的技术范围 内， 可轻易想到变化或替换，都应涵盖在本发明的 保护范围之内。 因此， 本发明的保护范围应该以权利要求的保护范围 为准。