理解流量监管和整形的关键算法—令牌桶

无论是流量监管还是流量整形都提到一个超额流量的问题，而前面已经描述了监管和整形对超额流量的处理方式不同，监管丢弃或者重标记，流量整形是缓存，通过加大延迟的方式发送平滑的数据流量，那么网络设备怎么去确定这个超额流量，难道链路的带宽为512K，而此时用户以每秒768KB/s发送数据，使用768-512就256KB,难道超额的流量就是256KB吗？不是的，这样做是一种错误的理解，要确定用户的超额流量必须使用如下两种算法中的一种来确定，一种叫漏桶算法（leaky bucket algorithm）另一种叫令牌桶算法（token bucket algorithm），而思科在流量监管和整形时使用的是令牌桶算法，为什么思科会选择令牌桶算法，下面开始来理解：

漏桶算法（leaky bucket algorithm）

   漏桶算法（leaky bucket algorithm）是一种不支持任何数据突发量的算法，为了更好的理解漏桶算法，如图所示，它好比一个底部呈现一个漏孔，然后装满水的桶，而桶的底部有一个恒定大小的漏孔，由于漏孔的大小是是恒定的，所以无论桶上方的水龙头以多大的注水量向桶中注水，水通过漏孙向外泄漏的速率永远是一样的，算法不会因为桶中的水快被溢出而瞬间将桶中的水泄漏完之后，再继续盛水。在这个比喻中桶中的水就好比是数据，水龙头好比是用户发送数据的速率，而桶底部的漏孔比如是流量整形或者监管的速率。

注意：在上面的描述中只是为了更好的理解漏桶算法，因为该算未能不并是需要描述的重点，大家只需要记住这样这个原则：因为漏桶算法只能以恒定速率输送数据，不支持任持续突发和最大突发，所以在流量管理中不使用漏桶算法，而是后面将要描述的令牌桶算法。

令牌桶算法（token bucket algorithm）或叫令牌漏桶算法

如图所示：其实令牌桶的底部也有一个“漏洞”这一点是乎和漏桶非常相似，所以令牌桶还有另一个名命叫“令牌漏桶（本章节至此以后统称它为令牌桶）”但是它与一般所指的常规漏洞有实质上的区别，令牌桶里面装载的是令牌，然后让令牌去关联到数据发送，常规漏桶里面装载的是数据，令牌桶允许用户的正常的持续突发量（Bc），就是一次就将桶里的令牌全部用尽的方式来支持续突发，而常规的漏桶则不允许用户任何突发行。而令牌桶的算法分为“单桶”和“双桶”算法，那现在首先来理解单桶算法。

令牌桶中的令牌如何去关联到数据发送

在令牌桶算法中，只有拿到令牌的数据才能被发送，反之则不能，假设一个令牌可以发送1bit（比特）的数据，那么要发6个bit的数据就需要拿到六个令牌，当拿到令牌的数据被发送后，该令牌就从桶中移除。换句话说桶中有多少令牌就能发送多少数据。如上图所示，一共有6个数据需要被发送，桶中有四个令牌，那么就能发送4个数据。在图示环境中剩下的2个数据因为没有多余的令牌可用它们将不被发送。

令牌桶算法如何判断超额流量以及如何向令牌桶中加入令牌

简单的讲，如果令牌桶中没有可用的令牌，那么在这个时刻到来的所有数据流量都是超额流量。如下图所示，至于超额的流量怎么处理，它可能被监管丢弃，也可能被整形所缓存，但这不是这里讨论的重点，在实验部分会重点讨论丢弃和缓存的效果。至此为止，大家应该清晰的知道使用令牌去关联数据并发送的过程了，令牌除了会从桶中移除以后，算法还会每隔一个的周期不断的向桶中加入令牌，关键加入令牌的速率是多少？是什么时候（间隔时间周期）加入令牌？然后加多少令牌到桶中？这些问题被三个关键因素所决定，它们是：CIR（承诺信息速率）、Tc（时间周期）、Bc（持续突发量）。

CIR（承诺信息速率）：这个速率就是向令牌桶中加入令牌的速度，单位是bits persecond每秒多少个比特，一般情况下，会将这个速率配置成与认购的合同速率相匹配。比如：虽然您的接入速率可能有128K，但是认购速率为64K，那么就应该把CIR配置为64K。

Tc（时间间隔）：承诺的持续突发（Bc）间隔时间，也是让令牌桶充满令牌的时间隔，它的单位是毫秒（ms），这个Tc间隔是不能手工配置的，通常思科会假设这个Tc为125ms。它能被CIR和Bc通过公式计算而得到。

Bc（持续突发量）：它实际上定义了令牌桶的容量，或者这样讲更容易理解，它就是在一个Tc时间时隔内允许用户一次耗尽桶中所有令牌的数量，以比特（bit）为单位。

流量监管和整形必须理解的重要公式：Bc = Tc * CIR

假设现在需要将一个（接入速度是128K）的链路，流量整形为承诺信息速率64K，那么该连接的持续突发量Bc是多少？很简单此时只需要使用思科默认的Tc(125ms)即0.125s乘以64000bit/s即得到8000bits的持续突发量Bc。同样的道理，如果已经知道了CIR和Bc就可以通过公式来计算出Tc。但是请始终注意一个问题：Tc是不可以手工配置的。能手工配置的只有CIR和Bc，而且思科建议只配置CIR，其它的参数，比如Bc，都让系统去自动计算完成。所以在上述的三个参数中最重要的还是CIR。

注意：有些时候读者在参看一些外文书籍或者参资料时，这个CIR也叫整形后的目标速率（Target Rate）或者叫整形速率（Shaped Rate），但其核心意思都一样：往令牌桶中加入令牌的速率。所以公式Bc = Tc * CIR等同于Bc = Tc * Target rate也等同于Bc = Tc * Shaped Rate。但是这有一个前提：就是你整形后的目标速率或者叫整形速率必须与承诺信息速率相同。但是在一些特殊案例中，当用户想获得高于CIR的数据发送速率时，可以将上述后两个公式中的Target rate 和Shaped Rate适当设置得更高些。

理解令牌桶算法支持用户的持续突发行为，为什么叫Bc为“持续”突发？

事实上，在单令牌桶的算法中，用户的持续突发量被Bc所决定的，Bc也代表令牌桶的容量，所谓突发行为是指：允许用户一次用完令牌桶中的所有令牌，那么如何体现“持续”突发的特点呢？持续突发是指间隔一个Tc时间，令牌桶中的令牌会被再次充满，然后用户可以再次用尽令牌桶中的所有令牌，也就是说这个突发行为是可以持续进行的，会在间隔Tc的时间周期上反复充满桶中的令牌同时又不断释放桶中的令牌，而不是在整个流量的较长时间发送过程中的瞬间行为。

流量整形到底是如何将接入速率（AR）转化为认购速率？

比如说接入速率（也就是物理时钟频率工作在128K），而认购速率也就是CIR只有64K，流量整形是如何将这个接入速率128K整形成与CIR相匹配的64K的？在回答这个问题前首先得弄明白一个不可争义的事实：如果接入速率工作在128K通常这个速率被时钟频率所决定，请注意在任何时候该接口都只会以128K的速率发送数据，就接口本身而言它是决不可能自己将发送速率降致64K的，但是它可以采取一种机制，把1秒钟（1s）拿来平均化成N个以毫秒（ms）组成的时间间隔，然后一些间隔时间不让其发送数据，能发送的时间间隔，接口还是以128K的速率来发送，如图所示：就是将128K的接入速率整形为64K的认购速率（也就是CIR），假设配置令牌桶的深度（Bc）8000比特，因为Tc=Bc/CIR,所以就会产生8000除以64000等于0.125s(125ms)的时间间隔，那么8个125ms就是1秒，所以现在以125ms为基础，划分8个时间间隔。然后接口仍然将以128K来发送数据，因为这是不可改变的事实，当前令牌桶的深度(Bc)是8000比特，如果以128K来发送数据，那么8000除以128000等于62.5ms就完成数据发送了（正好是125ms的一半），但是此时由于令牌桶中的令牌耗尽，令牌耗尽就代表数据无法拿到令牌，无法拿到令牌就无法发送数据。所以在125ms的时间间隔中的另一半时间（后62.5ms），数据发送将被抑制，不能发送，直到125ms间隔周期到来，令牌桶又被充满，然后再次耗尽它，然后重复的执行这个过程。所以从一秒钟这个角度来看，虽然接口以128K发送，但是有500ms发送都被抑制，实际上就每秒就等于64K的发送率。最后就能得到如图所示的整形情况：

通过上面的描述应该能理解单桶流量整形的工作机制了，现在需要进一步提出一个问题：如果用户有长时间没有发送数据，或者发送的数据低于令牌桶的容量（也就是不耗尽Bc中的令牌），那么新产生入桶的令牌会发生什么情况？

理解双令牌桶算法：

     如果只有一个令牌桶(Bc)，那么当用户发送的数据低于令牌桶的容量（也就是不耗尽Bc中的令牌），新产生入桶的令牌会充满令牌桶，当桶已经被充满时，多余的令牌将被丢弃，这意味着用户的整个突发量只能维持在Bc之内。不能存在有高过持续突发的超额突发（或者我更喜欢称呼超额突发为瞬间突发）。为了突破这个限制，现在在令牌桶算法中引入双桶机制，如图所示，第一个令牌桶通常被称为桶1也叫Bc或者叫持续突发桶；第二个令牌桶通常叫桶2也叫Be或者叫瞬间突发桶。双桶算法遵守如下重要原则：

1 算法不会直接向桶2产生并加入令牌

2 只有当桶1被填充满载时，从桶1溢出的令牌将被放入到桶2

3 不能保证桶2在每个时间间隔被充满令牌，这被桶1溢出多少令牌到桶2有关。

4 但是如果桶2也被满载，那么多余的令牌将被丢弃

根据上述的原则当引入桶2（Be）后，如果用户发送数据时，他将获得比单桶算法更大的突发量，因为流量耗尽了桶1（Bc）的令牌后，算法让会让流量去使用桶2（Be）中的令牌，所以此时用户的数据突发量将等于Bc+Be。但是在流量整形过程中Bc和Be到底可以配置成多少bits，建议这样的原则：将用户获得ISP的认购合同书上的CIR速率配置到流量整形中，让系统自行去计算最合理的Bc和Be，并不建议用户通过人工的方式去配置Bc和Be，整形系统的Bc可以通过Tc*CIR获得，而Be和Bc在数学上是不存在必然的关系的。思科一般会将Be的大小自动配置为和Bc相同。举一个例子来说明，如图所示为将接入速率128K整形为64K，Bc=8000bits, Be=8000bits,所以图中的流量突发会多一个Be的瞬间突发流量（如箭头所指示的那一部分），为什么Be只有那么一瞬间的突发量，而不能持续，因为算法从来都不会向Be直接加入令牌，Be只能收集被Bc溢出的令牌，如果用户一直以持续的高于64K的速率来发送数据，那么Bc就根本不会有令牌溢出，它将被反复的充满又耗光，然后又充满，然后又耗光，那么就不会有多是余的令牌溢出到桶2(Be)中，所以被允许的Be叫瞬间突发，一般只出现在数据初始发送的第一个时间时隔内，因为只有此时的Bc和Be的令牌都是满桶，还有就是出现在用户以低于CIR的速率在发送数据，只有这个时候桶2（Be）才有机会被充满。

注意区别持续突发和瞬间突发的差异：

持续突发是指Bc，所谓持续是指它可以每隔一个Tc间隔，就能将Bc的令牌全部用完，这意味着这个行为是可以反复持续的进行的，它与CIR和Tc存在必然的数学关系，通常是Bc=CIR*Tc，而瞬间突发或者叫超额突发是指Be，它不能被持续进行，能执行瞬间突发的一个唯一条件就是Bc的令牌已经满了，有令牌溢出到Be，当完成一次突发后，耗完Be的令牌后，如果一直没有令牌从Bc溢出到Be那么就不能在进行瞬间突发行为，所以它只是瞬间。

流量整形的配置及单双桶的确认

以GTS（通用流量整形）为例，默认情况下建议只配置CIR，系统自动计算Bc和Be，系统会使用双桶算法（同时使用Bc和Be），具体如下所示：

关于流量整形的配置说明：

R1(config)#inte s1/0

R1(config-if)#traffic-shape rate 64000   * 配置流量整形到每秒64Kbps

R1(config-if)#exit

    上述配置就仅是配置了整形的CIR，让系统去确定Bc和Be，当完成配置后，可以通过show traffic-shape来查看流量整形的各项配置参数，如图所示，当前的配置是将接入速率整形到64K，桶1(Bc)=8000bits=1000bytes；该参数是系统根据64000/bps(CIR)*0.125s(Tc)=8000bits所得到的。Tc思科默认是125ms。同时系统启动了双桶算法，将桶2（Be）配置成为与桶1（Bc）相同的大小8000bits。所以现在第一个时间时隔的突发量就是Bc+Be=16000bits，换成以字节为单位就是16000除以8等于2000byte。

手工配置Bc并申明使用单桶机制：

R1(config)#intes1/0

R1(config-if)#traffic-shaperate 64000 8000 0

* 整到CIR64K，手工配置桶1（Bc）为8000bits，手工配置桶2（Be）为0，由于Be被配置为0，这就申明目前流量整形只使用单桶算法，具体如图所示。

本文出自 “无名的基督” 博客，谢绝转载！

理解流量监管和整形的关键算法—令牌桶