流量控制算法

当前用的最多的流量控制算法时令牌桶限速，今天就简单讲一下令牌桶限速的几种实现方式。

主题思想：通过速度可知的令牌控制速度不可知的数据报文。

令牌桶限速核心思想：通过速度可知的令牌桶来控制速度不可知的报文（流量：各种类型报文）。

CBS：commit burst size，承诺突发尺寸，可表示为图中红色矩形的面积（令牌桶最大能够放入令牌的数量也就是

允许最大网络流量突发的大小，网络之中最怕的是突发的情况）

CIR：commit information rate，承诺信息速率。可表示为图中船的速度（单位时间内放入令牌的速度）

说明：1> 把数据报文比作图中的货物，即小方格；货物到来的速度是不可知的。

2> 河道的长度固定不变，不考虑小船从右边到左边占用的时间；小船占用的河道宽度可控制，宽度越大，能容纳的小船就越多（CBS参数）。

3> 运货船的速度可控制（CIR参数）。

   当货物的到来的速度非常大的时候，我们需要对其进行限制，使右侧收到货物的最大速度不超过一个特定的值。指定CBS参数和CIR参数，对船的运输速度和运输船的个数进行限制，从而达到对货物速度的限制的效果，结合源代码可能会理解的更深刻，代码注释的很详细了。

这个类比中可能有一个小缺陷，就是实际的报文来到时，如果此时没有可用的令牌则丢弃该报文，当然可以使用buf对其中一部分进行缓存，超过缓存的部分再丢弃。该源代码是令牌限速中最简单的一种实现,也就是仅仅实现没有令牌时丢弃报文操作，没有实现超出部分的缓存操作，功能更强大的可以自己去google、百度下。

简单的令牌桶限速实现流程图如上所示。

令牌桶算法，算法大纲如下(一个令牌对应一bit报文):

1、指定一个速率(CIR)，该速率是允许流量通过的最高速率，如10Kbps。 2、指定一个令牌桶(CBS)，用来盛放令牌，在处理报文时进行加减令牌操作,用于控制报文的流量。 3、要发送或接收一个Xbit长度的报文，令牌桶内必须要有足够的令牌才能处理，即令牌数>=X。 4、令牌数是动态的，一段时间内会流入一些令牌，也会流出一些令牌。 5、流入的令牌是由限定的速率决定的，在一段时间内，流入的令牌数为time(s)*rate(kbps)=Xbit，也就是速率越高，单位时间内流入的令牌数越多。 6、流出的令牌是有处理的报文长度决定的，报文长度为Xbit，则流出的令牌数为X。 7、流入和流出的令牌数都是在报文到来时再计算的，最后得到桶中剩余的令牌数。 8、当流入的令牌数小于流出的令牌数时，报文就被流量限制而不能进一步处理了。 9、当流入的令牌数已经超过桶的大小时（即报文太少，没有耗费流入的令牌），桶中剩余令牌数重置为桶的大小。

针对1、2的描述做进一步的理解：

1：速率在代码实现上做的是单位时间内令牌流入令牌桶的速率。如10Kbps，即每秒最大允许有10K个令牌放入令牌桶，即每秒允许通过最大的报文速率（单位bit/s），否则报文流入的速率超过令牌流入的速率，在令牌桶中的令牌被消耗殆尽之后，就没有可用的令牌，此时在有新的报文到来，就处理不了，开始丢弃报文。

2：报文来到时根据上次计算令牌的时间到现在的时间的间隔    *    cir（单位时间内流入令牌的个数），计算出可供流入令牌桶令牌的个数和需要流出令牌桶令牌的个数（流量的大小），具体规则查看（5、6、7、8、9）。领最理想的情况下是，报文可用的令牌的个数为令牌桶的尺寸即最大值（查看步骤九），即此时允许通过报文的流量就为令牌桶的尺寸，不能超过这个值，也就是说承诺允许发生的最大冲突的尺寸（流量）：CBS。

需要代码实现的童鞋可以私信我。