广告

原创 【转】令牌桶算法

2014-12-2 22:53 295 0 分类: 工程师职场 文集: Ethernet
 在实施QOS策略时,可以将用户的数据限制在特定的带宽,当用户的流量超过额定带宽时,超过的带宽将采取其它方式来处理。要衡量流量是否超过额定的带宽,网络设备并不是采用单纯的数字加减法来决定的,也就是说,比如带宽为100K,而用户发来的流量为110K,网络设备并不是靠110K减去100K等于10K,就认为用户超过流量10K。网络设备

衡量流量是否超过额定带宽,需要使用令牌桶算法来计算。下面详细介绍令牌桶算法机制:

当网络设备衡量流量是否超过额定带宽时,需要查看令牌桶,而令牌桶中会放置一定数量的令牌,一个令牌允许接口发送或接收1bit数据(有时是1 Byty数据),当接口通过1bit数据后,同时也要从桶中移除一个令牌。当桶里没有令牌的时候,任何流量都被视为超过额定带宽,只有当桶中有令牌时,数据才可以通过接口。令牌桶中的令牌不仅仅可以被移除,同样也可以往里添加,所以为了保证接口随时有数据通过,就必须不停地往桶里加令牌,由此可见,往桶里加令牌的速度,就决定了数据通过接口的速度。因此,我们通过控制往令牌桶里加令牌的速度从而控制用户流量的带宽。而设置的这个用户传输数据的速率被称为承诺信息速率(CIR),通常以秒为单位。比如我们设置用户的带宽为1000 bit每秒,只要保证每秒钟往桶里添加1000个令牌即可。

例:

将CIR设置为8000 bit/s,那么就必须每秒将8000个令牌放入桶中,当接口有数据通过时,就从桶中移除相应的令牌,每通过1 bit,就从桶中移除1个令牌。当桶里没有令牌的时候,任何流量都被视为超出额定带宽,而超出的流量就要采取额外动作。

每秒钟往桶里加的令牌就决定了用户流量的速率,这个速率就是CIR,但是每秒钟需要往桶里加的令牌总数,并不是一次性加完的,一次性加进的令牌数量被称为Burst size(Bc),如果Bc只是CIR的一半,那么很明显每秒钟就需要往桶里加两次令牌,每次加的数量总是Bc的数量。

还有就是加令牌的时间,Time interval(Tc),Tc表示多久该往桶里加一次令牌,而这个时间并不能手工设置,因为这个时间可以靠CIR和Bc的关系计算得到, Bc/ CIR= Tc。

例:

如果CIR是8000,Bc是4000,那就是每秒加两次,Tc就是4000/8000=0.5,也就是0.5秒,即500 ms。

如果Bc设为2000,那Tc就是2000/8000=0.25, 也就是250 ms。




一、在流量监管中的应用

约定访问速率(CAR)是流量监管常用技术之一,可以应用在端口进和出方向,一般应用在入方向,它的监管原理如图1所示。

a. 按特定的速率向令牌桶投放令牌

b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;

c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

d. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。

二、在通用流量整形中的应用

a. 按特定的速率向令牌桶投放令牌

b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;

c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

d. 对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时,报文将被缓存入队列,等有了足够的令牌之后再发送,

e. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。

通用流量整形中( GTS)CAR的原理稍有差别:

第一,GTS只用于出方向流量限速CAR出入方向均可以,但一般多用于入方向;

第二,利用CAR进行报文流量控制时,对超过速率限制的报文直接丢弃,而GTS是对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时,报文将被缓存入队列,等有了足够的令牌之后再发送,这样就减少了报文的丢弃,但是要注意的是,如果缓存队列已满,这时到达的报文仍旧会被丢弃。

三、在端口限速 中的应用

端口限速(LR)(如图3所示)也用于出方向,但不同于GTS 的是:第一,GTSCAR是在IP层实现的,所以对于不经过IP层处理的报文不起作用,而LR能够限制在物理接口上通过的所有报文;第二,LR不但能够对超过流量限制的报文进行缓存,并且可以利用QoS丰富的队列如优先级队列(PQ)、自定 队列(CQ)、加权公平对列(WFQ)等来缓存报文。

a. 按特定的速率向令牌桶投放令牌

b. 根据预设的匹配规则先对报文进行分类,利用QoS丰富的队列如优先级队列(PQ)、自定 队列(CQ)、加权公平对列(WFQ)等来缓存报文

c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;

d. 对超过速率限制的报文进行缓冲即当令牌桶的令牌少到报文不能再发送时,报文将被缓存入队列,等有了足够的令牌之后再发送,

e. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。

广告

文章评论 0条评论)

登录后参与讨论
相关推荐阅读
sunyzz 2017-08-19 10:38
【博客大赛】AVALON总线介绍
1、AVALON总线简介Avalon总线是一种协议较为简单的片内总线,是ALTERA公司定义的片上互联总线,该总线可以将诸如NIOS II的CPU与其他外设连接起来,进而进行数据交换。AVALON总线...
sunyzz 2017-08-17 21:36
【博客大赛】不要轻易做职场滥好人
小A毕业于国内普通高校,但是他聪明,勤奋,能干,动手能力强,可是即便有这些优点也不能让小A轻轻松松找到一份好工作。这不,去年9月份小A好不容易找到一份工作,然后立马就入职了C公司,生怕C公司过两天不要...
sunyzz 2017-08-16 21:15
【博客大赛】IC设计低功耗技术四
五:工艺层面的降低功耗前面几节都是在讨论设计人员如何在前期阶段,中期阶段降低功耗,涉及到软件层面的,硬件层面的,这些技巧基本都是前辈总结出来的,或者根据理论推论出来的。但是到了后期,想降低功耗基本就要...
sunyzz 2017-08-14 22:35
【博客大赛】IC设计之低功耗技术三
四:RTL(寄存器传输)级的低功耗设计4.1 状态机的设计状态机编码中一般有两种方式,普通的二进制编码,特殊的格雷码,格雷码的特点是两个数据之间的跳变时只会有一个bit在toggle,显然比起多bit...
sunyzz 2017-08-12 16:51
【博客大赛】IC设计之低功耗技术二
三、架构层面的降低功耗系统的实现有很多的方式,每种方式对功耗的影响都不相同,本节主要介绍架构对功耗的影响。3.1 高级门口电路 在同步电路系统中,时钟占据了大部分的动态功耗,因而在一些情况下,如果有些...
sunyzz 2017-08-12 10:37
【博客大赛】IC 设计之低功耗技术一
一、前言随着计算机技术和微电子技术的迅速发展,嵌入式系统应用领域越来越广泛。节能是全球化的热潮,如计算机里的许多芯片过去用5V供电,现在用3.3V,1.8V,甚至更低的电压。目前的低功耗设计主要从芯片...
我要评论
0
0
广告
关闭 热点推荐上一条 /2 下一条