具有带宽保障功能的级联令牌桶实现方法

摘要

本发明涉及通信领域，具体提供一种具有带宽保障功能的级联令牌桶实现方法，旨在解决现有令牌桶技术无法解决多维度复杂策略下的流量控制的问题。为此目的，本发明的方法包括下列步骤：以第一恒定速率向第一令牌桶中存放令牌；使用所述第一令牌桶中的令牌发送第一报文；其特征在于，所述方法还包括：将所述第一令牌桶中的剩余令牌注入到第二令牌桶中；以及使用所述第二令牌桶中的令牌发送第二报文。本领域技术人员容易理解的是，与传统的令牌桶技术相比，本发明的方法使独立的令牌桶彼此互联，从而能够共享流控带宽，尤其在某些令牌桶的令牌数不足的情况下，能够明显提高流控策略应用的灵活性。

说明书

技术领域

本发明涉及通信领域，具体提供一种具有带宽保障功能的 级联令牌桶实现方法。

背景技术

在网络中传输数据时，为了防止网络拥塞，需限制流出网 络的流量，使流量以比较均匀的速度向外发送。令牌桶技术是网络流 量整形(TrafficShaping)和速率限制(RateLimiting)中最常用的一 种技术。典型情况下，令牌桶技术用来控制发送到网络上的数据的数 目，并允许突发数据的发送。令牌以恒定的速率源源不断地被送入大 小固定的令牌桶，该速率通常称为流控速率。如果令牌不被消耗或者 被消耗的速度小于流控速率，令牌就会不断增多，直到把桶填满。后 面再送入的令牌就会从桶中溢出，最后桶中可以保存的最大令牌数永 远不会超过桶的大小。传送到令牌桶的报文需要消耗令牌。不同大小 的报文消耗的令牌数量不一样。令牌桶的这种控制机制基于令牌桶中 是否存在令牌来指示什么时候可以发送流量。如果令牌桶中存在令牌， 则允许发送流量；如果令牌桶中不存在令牌，则不允许发送流量。

然而，现有的令牌桶技术存在明显的缺点。具体而言，令 牌桶本身没有优先级策略，并且每个令牌桶相互独立、没有级联，因 此无法解决多维度复杂策略下的流量控制问题。

发明内容

为了解决前述问题，即为了解决现有令牌桶技术无法解决 多维度复杂策略下的流量控制的问题，本发明提供一种具有带宽保障 功能的级联令牌桶实现方法。该方法包括下列步骤：以第一恒定速率 向第一令牌桶中存放令牌；使用所述第一令牌桶中的令牌发送第一报 文；其特征在于，所述方法还包括：将所述第一令牌桶中的剩余令牌 注入到第二令牌桶中；以及使用所述第二令牌桶中的令牌发送第二报 文。

在上述具有带宽保障功能的级联令牌桶实现方法的优选 实施方式中，所述方法还包括：在将所述第一令牌桶中的剩余令牌注 入到第二令牌桶中之前或同时，以第二恒定速率向第二令牌桶中存放 令牌；在使用所述第二令牌桶中的令牌发送第二报文之后，将所述第 二令牌桶中的剩余令牌注入到所述第一令牌桶中；以及使用所述第一 令牌桶中的令牌发送第三报文。

在上述具有带宽保障功能的级联令牌桶实现方法的优选 实施方式中，当所述第一报文的预期报文字节数大于所述第一令牌桶 中的令牌字节数时，所述第一报文的实际报文字节数等于所述第一令 牌桶中的令牌字节数。应当指出的是，尽管上面使用的术语是“报文 字节数”和“令牌字节数”，但是在实际应用中，由于令牌桶本身容 量有限，令牌桶中的存量令牌仅在非常短的时间内(例如零点几秒内) 会起到蓄水池式的缓冲作用，在绝大多数时间里，上述报文字节数和 令牌字节数等同于报文速率和流控速率。换句话说，当所述第一报文 的预期报文速率大于所述第一恒定速率(即流控速率)时，所述第一 报文的实际报文速率就等于所述第一恒定速率(即流控速率)。

在上述具有带宽保障功能的级联令牌桶实现方法的优选 实施方式中，当所述第一报文的预期报文字节数小于所述第一令牌桶 中的令牌字节数时，所述第一报文的实际报文字节数等于所述第一报 文的预期报文字节数。类似地，尽管上面使用的术语是“报文字节数” 和“令牌字节数”，但是在实际应用中，由于令牌桶本身容量有限， 令牌桶中的存量令牌仅在非常短的时间内(例如零点几秒内)会起到 蓄水池式的缓冲作用，在绝大多数时间里，上述报文字节数和令牌字 节数等同于报文速率和流控速率。换句话说，当所述第一报文的预期 报文速率小于所述第一恒定速率(即流控速率)时，所述第一报文的 实际报文速率就等于所述第一报文的预期报文速率。

在上述具有带宽保障功能的级联令牌桶实现方法的优选 实施方式中，当所述第二报文的预期报文字节数大于所述第二令牌桶 中的令牌字节数时，所述第二报文的实际报文字节数等于所述第二令 牌桶中的令牌字节数。应当指出的是，尽管上面使用的术语是“报文 字节数”和“令牌字节数”，但是在实际应用中，由于令牌桶本身容 量有限，令牌桶中的存量令牌仅在非常短的时间内(例如零点几秒内) 会起到蓄水池式的缓冲作用，在绝大多数时间里，上述报文字节数和 令牌字节数等同于报文速率和流控速率。换句话说，当所述第二报文 的预期报文速率大于所述第二恒定速率(即流控速率)时，所述第二 报文的实际报文速率就等于所述第二恒定速率(即流控速率)。

在上述具有带宽保障功能的级联令牌桶实现方法的优选 实施方式中，当所述第二报文的预期报文字节数小于所述第二令牌桶 中的令牌字节数时，所述第二报文的实际报文字节数等于所述第二报 文的预期报文字节数。类似地，尽管上面使用的术语是“报文字节数” 和“令牌字节数”，但是在实际应用中，由于令牌桶本身容量有限， 令牌桶中的存量令牌仅在非常短的时间内(例如零点几秒内)会起到 蓄水池式的缓冲作用，在绝大多数时间里，上述报文字节数和令牌字 节数等同于报文速率和流控速率。换句话说，当所述第二报文的预期 报文速率小于所述第二恒定速率(即流控速率)时，所述第二报文的 实际报文速率就等于所述第二报文的预期报文速率。

本领域技术人员容易理解的是，与传统的令牌桶技术相 比，本发明的方法使独立的令牌桶彼此互联，从而能够共享流控带宽， 尤其在某些令牌桶的令牌数不足的情况下，能够明显提高流控策略应 用的灵活性。

附图说明

图1是根据本发明的级联令牌桶实现方法的第一实施方式 的流程图。

图2是根据本发明的级联令牌桶实现方法的第二实施方式 的流程图。

图3是根据本发明的级联令牌桶实现方法的总流程图。

具体实施方式

下面参照附图来描述本发明的优选实施方式。本领域技术 人员应当理解的是，这些实施方式仅用于解释本发明的技术原理，并 非旨在限制本发明的保护范围。例如，尽管本申请是结合两个令牌桶 来描述的，但是本领域技术人员能够理解的是，本发明的技术方案显 然可以应用于两个以上的令牌桶，从而实现一个令牌桶与其他多个令 牌桶的级联或者实现多个令牌桶与其他多个令牌桶的级联。这种改变 并没有超出本发明的基本原理，因此也将落入本发明的保护范围之内。

首先参阅图1，该图是根据本发明的级联令牌桶实现方法 的第一实施方式的流程图。如图1的左侧所示，在第一实施方式中， 本发明的级联令牌桶实现方法包括下列步骤：以恒定速率(即，规定 速度或流控速率)向A令牌桶中存放令牌；然后使用A令牌桶中的令 牌发送A报文。本发明的方法的特征在于还包括：将A令牌桶中的多 余令牌注入到B令牌桶中以及使用B令牌桶中的令牌发送B报文。

如A令牌桶的下方所示，当A报文的预期报文字节数大 于A令牌桶中的令牌字节数时，则A报文的实际报文字节数等于A令 牌桶中的令牌字节数，多余报文被丢弃。如A令牌桶的右侧所示，当 A报文的预期报文字节数小于A令牌桶中的令牌字节数时，A报文的 实际报文字节数等于A报文的预期报文字节数，即A报文的N个字节 全部通过并且A报文桶中删除N个令牌。

类似地，如B令牌桶的下方所示，当B报文的预期报文 字节数大于B令牌桶中的令牌字节数时，B报文的实际报文字节数等 于B令牌桶中的令牌字节数，多余报文被丢弃。如B令牌桶的右侧所 示，当B报文的预期报文字节数小于B令牌桶中的令牌字节数时，B 报文的实际报文字节数等于B报文的预期报文字节数，即B报文的N 个字节全部通过并且B报文桶中删除N个令牌。

下面参阅图2，该图是根据本发明的级联令牌桶实现方法 的第二实施方式的流程图。与图1的优先级级联方式不同，图2示出 的是加权排队级联方式。具体而言，与第一实施方式相同，本发明的 第二实施方式的方法也包括下列步骤：以恒定速率(即，规定速度或 流控速率)向A令牌桶中存放令牌；使用A令牌桶中的令牌发送A报 文；将A令牌桶中的多余令牌注入到B令牌桶中以及使用B令牌桶中 的令牌发送B报文。然而，与第一实施方式不同的是，在第二实施方 式中，本发明的方法还额外地包括：在将A令牌桶中的剩余令牌注入 到B令牌桶中之前或同时，以另一恒定速率向B令牌桶中存放令牌； 在使用B令牌桶中的令牌发送第二报文之后，将B令牌桶中的剩余令 牌注入到A令牌桶中；以及可选地使用A令牌桶中的令牌发送第三报 文。

同样与第一实施方式相同，在第二实施方式中，当A报文 的预期报文字节数大于A令牌桶中的令牌字节数时，A报文的实际报 文字节数等于A令牌桶中的令牌字节数，多余报文被丢弃。当A报文 的预期报文字节数小于A令牌桶中的令牌字节数时，A报文的实际报 文字节数等于A报文的预期报文字节数，即A报文的N个字节全部通 过并且A报文桶中删除N个令牌。类似地，当B报文的预期报文字节 数大于B令牌桶中的令牌字节数时，B报文的实际报文字节数等于B 令牌桶中的令牌字节数，多余报文被丢弃。当B报文的预期报文字节 数小于B令牌桶中的令牌字节数时，B报文的实际报文字节数等于B 报文的预期报文字节数，即B报文的N个字节全部通过并且B报文桶 中删除N个令牌。

最后参阅图3，该图是根据本发明的级联令牌桶实现方法 的总流程图，综合性地示出了第一和第二实施方式。如图3所示，本 发明的级联令牌桶实现方法开始于步骤S10。在步骤S10中，以第一恒 定速率向第一令牌桶中存放令牌。在步骤S20中，使用第一令牌桶中 的令牌发送第一报文。然后在步骤S30中，以第二恒定速率向第二令 牌桶中存放令牌。接着在步骤S40中，将第一令牌桶中的剩余令牌注 入到第二令牌桶中。之后在步骤S50中，使用第二令牌桶中的令牌发 送第二报文。然后在步骤S60中，将第二令牌桶中的剩余令牌注入到 第一令牌桶中。最后，在步骤S70中，使用第一令牌桶中的令牌发送 额外的第三报文，所述方法由重新回到步骤S10和步骤S20，如此循环。

关于上述方法，需要特别指出的是，在单一循环中，步骤 S30既可以在步骤S40之前执行，也与步骤S40同时执行，这种调整并 不背离本发明的原理，因此也没有超出本发明的保护范围。

至此，已经结合附图所示的优选实施方式描述了本发明的 技术方案，但是，本领域技术人员容易理解的是，本发明的保护范围 显然不局限于这些具体实施方式。在不偏离本发明的原理的前提下， 本领域技术人员可以对相关技术特征作出等同的更改或替换，这些更 改或替换之后的技术方案都将落入本发明的保护范围之内。例如，上 文虽然按照特定的顺序描述了本发明的操作步骤，但是，在不偏离本 发明的基本原理－即将独立的令牌桶相互级联的前提下，本领域技术 人员可以根据需要采用任何特定的顺序、或者删除已有步骤或增加额 外的步骤，调整之后的技术方案仍将落入本发明的保护范围。