一.令牌桶算法简介
在网络中传输数据时，为了防止网络拥塞，需限制流出网络的流量，使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能，可控制发送到网络上数据的数目，并允许突发数据的发送。
[1]
令牌桶算法是
网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。
大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗，或者被消耗的速度小于产生的速度，令牌就会不断地增多，直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。
传送到令牌桶的数据包需要消耗令牌。不同大小的数据包，消耗的令牌数量不一样。
令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌，则允许发送流量；而如果令牌桶中不存在令牌，则不允许发送流量。因此，如果突发门限被合理地配置并且令牌桶中有足够的令牌，那么流量就可以以峰值速率发送。
令牌桶算法的基本过程如下：
假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中；
假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃；
当一个n个字节的
数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络；
如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外；
算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理：
它们可以被丢弃；
它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输；
它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃。
注意：令牌桶算法不能与另外一种常见算法“
漏桶算法（Leaky Bucket）”相混淆。这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输速率外，还允许某种程度的突发传输。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。
二.令牌桶算法令牌桶工作参数
工作过程包括3个阶段：产生令牌、消耗令牌和判断数据包是否通过。其中涉及到2个参数：令牌产生的速率CIR（Committed Information Rate）/EIR（Excess Information Rate）和令牌桶的大小CBS（Committed Burst Size）/EBS（Excess Burst Size）。下面用图形简要概括一下这3个阶段与2个参数的关系。
[1]
-
产生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已到达CBS/EBS，则丢弃多余令牌。
-
消耗令牌：输入数据包会消耗桶中的令牌。在网络传输中，数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多。
-
判断是否通过：输入数据包经过令牌桶后的结果包括输出的数据包和丢弃的数据包。当桶中的令牌数量可以满足数据包对令牌的需求，则将数据包输出，否则将其丢弃。
三.令牌桶算法标记器
业务量的计量和标记主要是应用在区分服务体系机构中，计量器的功能主要是根据该业务量相关的流量规范来计量和检验业务量的流量特性，判断是否与流量规范一直，是否遵守约定的流量规范，计量的依据就是该业务分组流的流量规范，标记器对每一个经过计量的IP分组进行标记，这个标记被作为网络在以后按标记处理给分组的依据，在区分服务体系结构中，对分组的标记是该分组设置与服务类型相应的DSCP值。
[2]
计量与标记功能是协作完成的，计量的结果传给标记器，作为标记的依据。一般标记器就指的是两种功能的结合，其组成如图，
标记器有两种分类标记方法，一种是按颜色的不同进行分类标记，有双色标记和三色标记；另一种是按实现机制分类，有基于令牌桶的标记、基于速率的标记和基于策略的标记。
四.令牌桶算法分类
基于令牌桶的典型标记器有多种算法实现方案，基本算法主要有IN/OUT公平标记器（FM）和三色标记器（TCM），扩展的算法主要有单速率三色标记器（srTCM）和双速率三色标记器（trTCM）。其中单速率标记器和双速率标记器已分别称为IETF的标准建议。
[2]
IN/OUT 公平标记器（FM）
FM是一种双色单令牌桶标记器，它的Tspec是系统的分组平均速录为R，允许的突发度为B，工作原理就是当IP分组到达时若桶中有足够的令牌，则将符合Tspec的分组标记为IN；若此时没有足够的令牌，则认为该到达分组不符合Tpsec，不符合Tpsec的分组将被标记为OUT，网络将可能对这些被标记为不同属性的分组依据相应的策略进行不同的处理。
单速率三色标记器（srTCM）
srTCM是一种三色双令牌桶标记器，它的Tpsec有三个参数：承诺信息速率，承诺突发尺寸和超额突发尺寸。CIR的单位是bps，CBS及EBS的单位是Byte。
srTCM由两个令牌桶C和E组成，它们的CIR相同，容量则分别为CBS和EBS，C桶内存放黄色令牌，开始时令牌桶C与E都是满的。进入的分组没有超过CBS就标记为绿色；超过了CBS而没有超过EBS就标记为黄色；否则标记为红色。在DiffServ中，红、黄、绿可映射为不同的DSCP值。
双速率标记器（trTCM）
trTCM也是一种三色双令牌桶标记器，它的Tpsec有4个参数：峰值信息速率（PIR）、峰值突发尺寸（PBS）、承诺信息速率（CIR）和承诺突发尺寸（CBS）。PIR和CIR的单位是bps，PBS和CBS的单位是Byte。
五.在流量监管中的应用分类
约定访问速率(CAR)是流量监管常用技术之一，可以应用在端口进和出方向，一般应用在入方向，它的监管原理如图1所示。
a. 按特定的速率向令牌桶投放令牌
b. 根据预设的匹配规则先对报文进行分类，不符合匹配规则的报文不需要经过令牌桶的处理，直接发送；
c. 符合匹配规则的报文，则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去，同时令牌桶中的令牌
量按报文的长度做相应的减少；
d. 当令牌桶中的令牌不足时，报文将不能被发送，只有等到桶中生成了新的令牌，报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度，达到限制流量的目的。
二、在通用流量整形中的应用
a. 按特定的速率向令牌桶投放令牌
b. 根据预设的匹配规则先对报文进行分类，不符合匹配规则的报文不需要经过令牌桶的处理，直接发送；
c. 符合匹配规则的报文，则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去，同时令牌桶中的令牌
量按报文的长度做相应的减少；
d. 对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时，报文将被缓存入队列，等有了足够的令牌之后再发送，
e. 当令牌桶中的令牌不足时，报文将不能被发送，只有等到桶中生成了新的令牌，报文才可以发送。
通用流量整形中( GTS)与CAR的原理稍有差别：
第一,GTS只用于出方向流量限速，CAR出入方向均可以，但一般多用于入方向；
第二，利用CAR进行报文流量控制时，对超过速率限制的报文直接丢弃，而GTS是对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时，报文将被缓存入队列，等有了足够的令牌之后再发送，这样就减少了报文的丢弃，但是要注意的是，如果缓存队列已满，这时到达的报文仍旧会被丢弃。
三、在端口限速
中的应用
端口限速(LR)(如图3所示)也用于出方向，但不同于GTS 的是：第一，GTS与CAR是在IP层实现的，所以对于不经过IP层处理的报文不起作用，而LR能够限制在物理接口上通过的所有报文；第二，LR不但能够对超过流量限制的报文进行缓存，并且可以利用QoS丰富的队列如优先级队列(PQ)、自定
义
队列(CQ)、加权公平对列(WFQ)等来缓存报文。
a. 按特定的速率向令牌桶投放令牌
b. 根据预设的匹配规则先对报文进行分类，利用QoS丰富的队列如优先级队列(PQ)、自定
义
队列(CQ)、加权公平对列(WFQ)等来缓存报文
c. 符合匹配规则的报文，则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去，同时令牌桶中的令牌
量按报文的长度做相应的减少；
d. 对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时，报文将被缓存入队列，等有了足够的令牌之后再发送，
e. 当令牌桶中的令牌不足时，报文将不能被发送，只有等到桶中生成了新的令牌，报文才可以发送。
源文档 <http://blog.mecn.cn/post/146/>
