令牌桶(令牌桶)
一、什么是漏桶算法和令牌桶算法
什么是令牌桶
在我们讨论突发数据量之前，我们首先要理解令牌桶的概念。令牌桶本身没有丢弃
和优先级策略，
令牌桶是这样工作的：
1．令牌以一定的速率放入桶中。
2．每个令牌允许源发送一定数量的比特。
3．发送一个包，流量调节器就要从桶中删除与包大小相等的令牌数。
4．如果没有足够的令牌发送包，这个包就会等待直到有足够的令牌（在整形
器的情况下）或者包被丢弃，也有可能被标记更低的DSCP（在策略者的情况下）。
5．桶有特定的容量，如果桶已经满了，新加入的令牌就会被丢弃。因此，在
任何时候，源发送到网络上的最大突发数据量与桶的大小成比例。令牌桶允许突发，
但是不能超过限制。
Cisco IOS流量策略（Traffic Policers）
IOS支持两种流量策略：
1．传统的Cisco流量策略：CAR承诺接入速率，使用命令
Router(config-if)#rate-limit{input| output} CIR(bps)
Bc（burst-normal） Be(burst-max) conform-action action exceed-action action
2．新型的Cisco流量策略：基于类的策略（Class-based policer），使用模
块化Qos CLI（MQC）语法。可以使用MQC命令建立流量策略并把策略应用到接口。
一个流量策略包括一个流量类（traffic class）和一个或多个Qos特性。Policy
命令用来执行流量策略特性，它指定了一个流量类所需要的最大速率，超过这个速
率Qos系统会立刻执行一个操作，标准的操作是丢弃或重置包头的DSCP字段。Policy
命令的语法是：
police cir<bps> Bc<bc> Be<be> conform<conform-action> exceed
<exceed-action> violate<violate-action>
理解Bc和Be
对于超额的数据包，流量策略并不会把它们缓存稍候转发，只有整形器（shaper）
会这样做。流量策略只执行一个发送或不发送的策略。因为不能缓存数据包，所以
在发生拥塞时，所能做的最好的方法就是通过配置适当的超额突发数据量Be来不那
么过分的丢弃数据包。这一点对理解流量策略使用Bc和Be来保证达到CIR是非常
重要的。
超额参数模仿路由器的通用缓存规则。The rule recommends configuring buffering
equal to the round-trip time bitrate to accommodate the outstanding TCP
windows of all connections in times of congestion.
突发参数目的推荐公式
普通突发·执行标准的令牌桶·设置最大数量的令牌(尽管如
果Be>Bc的话可以借到令牌).·决定令牌桶有多大，因为如果桶已经满了那么令
牌将被丢弃而不会再加入到桶中。 CIR [bps]*(1 byte)/(8 bits)* 1.5
seconds Note: 1.5 seconds is the typical round trip time.
超额突发·为令牌桶提供超额突发能力·如果Bc= Be那么不
支持超额突发·当Bc= Be，流量调节器就不能借令牌，当令牌不够时只能丢弃数
据包两倍的Bc
对TCP流量的测试表明，Bc和Be的数值应该近似等于配置的平均速率在两秒钟内
的流量。如果你想限制流量在1Mb，应该把Bc设置在1-2Mb，Be在2-4Mb。
举个例子，如果我们想把输出速率限制在1.5Mbps，我们可以做一下步骤：
1．把承诺速率从比特转换成字节，因为突发数据量的单位为字节。
1500000 bits/ 8 bits= 187500 bytes
2．使用标准的1.5秒往返时间（round-trip time）计算Bc
187500 bytes* 1.5秒= 281250 bytes
3．两倍的Bc为Be
281250 bytes* 2= 562500 bytes
使用命令
rate-limit input 1500000 281250 562500 conform-action{action}
exceed-action{action}
超额突发数据量
当数据包到达时可用的令牌数目小于包的大小，就可以使用超额突发数据量。包会
请求借用令牌。可以通过配置大于Bc的Be的数值来为令牌桶提供超额突发能力。
可以通过下面两个例子来理解Be。
第一个例子说明怎样配置CAR策略来允许所有的IP流量。管理员在T3线路上提供
了便宜的20Mbps的子速率服务。用户只花费子速率带宽的金额，也可以按需要增加
带宽。CAR限制了用户可用的流量速率，用户只能使用规定的速率加上承诺的突发
数据量。可以适当的设置Be=32000。
interface hssi 0/0/0
rate-limit output 20000000 24000 32000 conform-action transmit
exceed-action drop
下一个例子，用户只能发送24000字节的突发数据量，所有超过限制的数据包都要
被丢弃，因为设置Bc=Be，数据包流不能通过超额突发能力来借用令牌。
interface Hssi0/0/0
rate-limit output 20000000 24000 24000 conform-action transmit
exceed-action drop
正确设置突发数据量的重要性
策略以字节为单位指定了突发数据量，基于类的策略（class-based policer）支持
最小的突发数据量为1000字节，包括第二层包头。
突发数据量的目的是逐渐的丢弃数据包，就像RED那样，并且避免尾丢弃。设置足
够高的突发数据量对保证良好的吞吐量是非常重要的。
设置突发数据量时，考虑一下内容：
1．如果突发数据量设置的过低，数据到达的速率将远远低于配置的速率。
2．惩罚暂时突发对TCP流的吞吐量来说是相当不利的，具体情况请察看RFC
2001 and Random Early Detection(RED) gateways for Congestion Avoidance。
设置突发数据量来允许路由器容纳暂时突发。
3．对离开接口的数据包的处理基于包的大小和桶中剩余的令牌数。
4．在基于类的策略中，流量测量器不论接口是否拥塞都是激活的。每个包都
会经过令牌桶测量系统来决定是否符合配置的参数。
5．如果数据突发量非常大而且非常突然，那么配置较高的超额突发数据量可
以保证超额令牌桶中存放较多的令牌。而且可以调整接口的MTU等于或大于突发数
据量大小。
允许的突发数据量数值
最初，包括IOS12.0，rate-limit命令支持承诺和超额的突发数据量的范围是：
Router1(config-if)#rate-limit input 18000000?
<8000-2000000> Normal burst bytes
Router1(config-if)#rate-limit input 18000000 2000000?
<8000-8000000> Maximum burst bytes
Router1(config-if)#rate-limit input 18000000 2000000
IOS12.1增加了突发数据量的最大值：
7500-107(config)#interface atm 1/0/0
7500-107(config-if)#rate-limit output?
<8000-2000000000> Bits per second
access-group Match access list
qos-group Match qos-group ID<b
二、令牌桶算法的分类
基于令牌桶的典型标记器有多种算法实现方案，基本算法主要有IN/OUT公平标记器（FM）和三色标记器（TCM），扩展的算法主要有单速率三色标记器（srTCM）和双速率三色标记器（trTCM）。其中单速率标记器和双速率标记器已分别称为IETF的标准建议。
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。
三、令牌桶算法详细资料大全
令牌桶算法是网路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制传送到网路上的数据的数目，并允许突发数据的传送。
基本介绍中文名：令牌桶算法简介,令牌桶工作参数,标记器,分类,简介在网路中传输数据时，为了防止网路拥塞，需限制流出网路的流量，使流量以比较均匀的速度向外传送。令牌桶算法就实现了这个功能，可控制传送到网路上数据的数目，并允许突发数据的传送。令牌桶算法是网路流量整形（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个参数的关系。产生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已到达CBS/EBS，则丢弃多余令牌。消耗令牌：输入数据包会消耗桶中的令牌。在网路传输中，数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多。判断是否通过：输入数据包经过令牌桶后的结果包括输出的数据包和丢弃的数据包。当桶中的令牌数量可以满足数据包对令牌的需求，则将数据包输出，否则将其丢弃。标记器业务量的计量和标记主要是套用在区分服务体系机构中，计量器的功能主要是根据该业务量相关的流量规范来计量和检验业务量的流量特性，判断是否与流量规范一直，是否遵守约定的流量规范，计量的依据就是该业务分组流的流量规范，标记器对每一个经过计量的IP分组进行标记，这个标记被作为网路在以后按标记处理给分组的依据，在区分服务体系结构中，对分组的标记是该分组设定与服务类型相应的DSCP值。计量与标记功能是协作完成的，计量的结果传给标记器，作为标记的依据。一般标记器就指的是两种功能的结合，其组成如图，标记器有两种分类标记方法，一种是按颜色的不同进行分类标记，有双色标记和三色标记；另一种是按实现机制分类，有基于令牌桶的标记、基于速率的标记和基于策略的标记。分类基于令牌桶的典型标记器有多种算法实现方案，基本算法主要有IN/OUT公平标记器（FM）和三色标记器（TCM），扩展的算法主要有单速率三色标记器（srTCM）和双速率三色标记器（trTCM）。其中单速率标记器和双速率标记器已分别称为IETF的标准建议。 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。