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

简介:

无论是流量监管还是流量整形都提到一个超额流量的问题,而前面已经描述了监管和整形对超额流量的处理方式不同,监管丢弃或者重标记,流量整形是缓存,通过加大延迟的方式发送平滑的数据流量,那么网络设备怎么去确定这个超额流量,难道链路的带宽为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

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

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

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

但是如果桶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







本文转自 kingsir827 51CTO博客,原文链接:http://blog.51cto.com/7658423/1576118,如需转载请自行联系原作者

相关文章
|
29天前
|
算法 数据安全/隐私保护
基于PSO粒子群优化算法的256QAM星座图的最优概率整形matlab仿真,对比PSO优化前后整形星座图和误码率
本项目基于MATLAB 2022a仿真256QAM系统,采用概率星座整形(PCS)技术优化星座点分布,结合粒子群优化(PSO)算法搜索最优整形因子v,降低误码率,提升传输性能。核心程序包含完整优化流程。
53 0
|
3月前
|
算法 JavaScript 数据安全/隐私保护
基于遗传算法的256QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容展示了基于GA(遗传算法)优化的256QAM概率星座整形(PCS)技术的研究与实现。通过Matlab仿真,分析了优化前后星座图和误码率(BER)的变化。256QAM采用非均匀概率分布(Maxwell-Boltzman分布)降低外圈星座点出现频率,减小平均功率并增加最小欧氏距离,从而提升传输性能。GA算法以BER为适应度函数,搜索最优整形参数v,显著降低误码率。核心程序实现了GA优化过程,包括种群初始化、选择、交叉、变异等步骤,并绘制了优化曲线。此研究有助于提高频谱效率和传输灵活性,适用于不同信道环境。
65 10
|
3月前
|
算法 JavaScript 数据安全/隐私保护
基于遗传算法的64QAM星座图的最优概率整形matlab仿真,对比优化前后整形星座图和误码率
本内容主要探讨基于遗传算法(GA)优化的64QAM概率星座整形(PCS)技术。通过改变星座点出现的概率分布,使外圈点频率降低,从而减小平均功率、增加最小欧氏距离,提升传输性能。仿真使用Matlab2022a完成,展示了优化前后星座图与误码率对比,验证了整形增益及频谱效率提升效果。理论分析表明,Maxwell-Boltzman分布为最优概率分布,核心程序通过GA搜索最佳整形因子v,以蒙特卡罗方法估计误码率,最终实现低误码率优化目标。
69 1
|
4月前
|
机器学习/深度学习 存储 监控
上网管理监控软件的 Go 语言流量特征识别算法实现与优化
本文探讨基于Go语言的流量特征识别算法,用于上网管理监控软件。核心内容涵盖AC自动机算法原理、实现及优化,通过路径压缩、哈希表存储和节点合并策略提升性能。实验表明,优化后算法内存占用降低30%,匹配速度提升20%。在1000Mbps流量下,CPU利用率低于10%,内存占用约50MB,检测准确率达99.8%。未来可进一步优化高速网络处理能力和融合机器学习技术。
129 10
|
4月前
|
监控 算法 JavaScript
公司局域网管理视域下 Node.js 图算法的深度应用研究:拓扑结构建模与流量优化策略探析
本文探讨了图论算法在公司局域网管理中的应用,针对设备互联复杂、流量调度低效及安全监控困难等问题,提出基于图论的解决方案。通过节点与边建模局域网拓扑结构,利用DFS/BFS实现设备快速发现,Dijkstra算法优化流量路径,社区检测算法识别安全风险。结合WorkWin软件实例,展示了算法在设备管理、流量调度与安全监控中的价值,为智能化局域网管理提供了理论与实践指导。
106 3
|
10月前
|
算法 容器
令牌桶算法原理及实现,图文详解
本文介绍令牌桶算法,一种常用的限流策略,通过恒定速率放入令牌,控制高并发场景下的流量,确保系统稳定运行。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
令牌桶算法原理及实现,图文详解
|
11月前
|
人工智能 算法 前端开发
无界批发零售定义及无界AI算法,打破传统壁垒,累积数据流量
“无界批发与零售”是一种结合了批发与零售的商业模式,通过后端逻辑、数据库设计和前端用户界面实现。该模式支持用户注册、登录、商品管理、订单处理、批发与零售功能,并根据用户行为计算信用等级,确保交易安全与高效。
|
负载均衡 监控 算法
揭秘负载均衡的五大算法秘籍:让你的服务器轻松应对亿万流量,不再崩溃!
【8月更文挑战第31天】在互联网快速发展的今天,高可用性和可扩展性成为企业关注的重点。负载均衡作为关键技术,通过高效分配网络流量提升系统处理能力。本文介绍了轮询、加权轮询、最少连接及IP哈希等常见负载均衡算法及其应用场景,并提供Nginx配置示例。此外,还探讨了如何根据业务需求选择合适算法、配置服务器权重、实现高可用方案、监控性能及定期维护等最佳实践,助力系统优化与用户体验提升。
281 2
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
670 1
|
存储 算法 Java
【令牌桶算法与漏桶算法】
【令牌桶算法与漏桶算法】
307 0

热门文章

最新文章