首页 > 代码库 > 理解流量监管和整形的关键算法—令牌桶

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

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


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


漏桶算法(leaky bucket algorithm

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

wKiom1RkX4DgZ64AAADN0Fv77GM064.jpg

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

 

令牌桶算法(token bucket algorithm)或叫令牌漏桶算法

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

wKioL1RkYDvy3-gvAADmX3_QR-0429.jpg

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

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

 

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

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

wKiom1RkYA3QVvj-AAEFtGqBjoE749.jpg

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

Tc(时间间隔):承诺的持续突发(Bc)间隔时间,也是让令牌桶充满令牌的时间隔,它的单位是毫秒(ms),这个Tc间隔是不能手工配置的,通常思科会假设这个Tc125ms。它能被CIRBc通过公式计算而得到。

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

 

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

假设现在需要将一个(接入速度是128K)的链路,流量整形为承诺信息速率64K,那么该连接的持续突发量Bc是多少?很简单此时只需要使用思科默认的Tc(125ms)0.125s乘以64000bit/s即得到8000bits的持续突发量Bc。同样的道理,如果已经知道了CIRBc就可以通过公式来计算出Tc。但是请始终注意一个问题:Tc是不可以手工配置的。能手工配置的只有CIRBc,而且思科建议只配置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),假设配置令牌桶的深度(Bc8000比特,因为Tc=Bc/CIR,所以就会产生8000除以64000等于0.125s(125ms)的时间间隔,那么8125ms就是1秒,所以现在以125ms为基础,划分8个时间间隔。然后接口仍然将以128K来发送数据,因为这是不可改变的事实,当前令牌桶的深度(Bc)8000比特,如果以128K来发送数据,那么8000除以128000等于62.5ms就完成数据发送了(正好是125ms的一半),但是此时由于令牌桶中的令牌耗尽,令牌耗尽就代表数据无法拿到令牌,无法拿到令牌就无法发送数据。所以在125ms的时间间隔中的另一半时间(后62.5ms),数据发送将被抑制,不能发送,直到125ms间隔周期到来,令牌桶又被充满,然后再次耗尽它,然后重复的执行这个过程。所以从一秒钟这个角度来看,虽然接口以128K发送,但是有500ms发送都被抑制,实际上就每秒就等于64K的发送率。最后就能得到如所示的整形情况:


wKiom1RkYJ-jxsqzAAGW3KnddLs906.jpg

wKioL1RkYQ2Txw3DAACfEN3GukE055.jpg

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

 

理解双令牌桶算法:

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

wKioL1RkYWfw468SAAERJdq9SuQ363.jpg

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

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

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

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

 

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


wKioL1RkYaaC8iK0AAE-Jt9AzoI516.jpg


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

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

 

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

GTS(通用流量整形)为例,默认情况下建议只配置CIR,系统自动计算BcBe,系统会使用双桶算法(同时使用BcBe),具体如下所示:

 

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

R1(config)#inte s1/0

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

R1(config-if)#exit

 

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


wKiom1RkYb7TBxoWAAEjnkx_OFg969.jpg

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

R1(config)#intes1/0

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

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


wKiom1RkYgigHDNIAAM1edV768M100.jpg








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

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