|
|
CISCO IOS管制器和×××器使用信令牌桶算法建模。本质上令牌桶算法是测量引擎，跟踪能够发送多少流量来证实指定的流量速率。一个令牌允许该算法发送单个位（某些情况下，可以是一个字节）的流量。这些令牌在某个时间增量开始时得到授权，通常是每秒，根据指定的速率，一般称为承诺的信息速率（CIR）。CIR是与服务提供商或维护的服务级约定的访问比特率。
举例来说，如果CIR设置为8000bin/s，那么在每个时间周期的开始将8000个令牌放入"桶"里（注意，这个描述给出了该算法一个简单观点，在所有情况下并不严格认真，但它说明了桶里面有令牌，该流量就被放行。每放行流量中的一位，就从桶中移除一个令牌。因此，流量可以看成是服务速率的， 因此服从流量的行为得以实现。（通常来说，服从的流量会被发送）当桶里没有令牌的时候，出现的任何额外流量都被视作超出速率，此时就采取超出的动作。（过量流量通常要么被标记，要么被丢弃）
在每秒的最后，都可能有未用的令牌，未使用令牌的处理是各种管制器之间的关键区别。
当对某个接口施加速率限制（或CIR）时，受限制的流量就被分配一个亚秒级时间片，它可以在这个时间片中被发送。亚秒级时间片也可称为间隔（或 TC）。举例来说，如果一个8Kbit/s的CIR作用在一个64Kbit/s的链路上，流量可以以125毫秒（64000bit/s/8000位）的间隔发送。
CIR的总数（8000位）可以一次发送，但这时算法在能够发送更多数据之前（作用到速率限制）就必须等待875毫秒。这样的分组间延迟有可能被看成是过量。因此，为了平滑每秒流出的流量，CIR被分成更小的单位，被称为承诺突发（BC），即每个时间间隔传输持续数量的位。这些更小的单位在单个秒中通过多个实例发送。继续前面的例子，如果BC被设置为1000，每个承诺突发仅需15.6ms（1000位/64000bit/s）以时钟速率将流量送出接口。该算法等待109.4ms（125ms-15.6ms），然后再以15.6ms发送另一组数据。该过程在每秒内重复8次。
因此，令牌桶算法可以描述如下：
CIR=Bc/Tc
Cisco IOS软件不允许间隔的显示定义。与此相反，它采用CIR和BC作为参数，间隔和每秒的农历发量可以根据它们计算得到。兴例来说，如果CIR是8000， BC是4000，每秒产生二个突发（TC=500ms）。如果BC设置为2000，那么每秒就产生4个突发（TC=250ms）。如果BC设置为 1000，每秒就产生8个突发（TC=125ms）。
最早的管制器都使用单一速率双色标记器和单桶。这种模型中，流量被标记为二种状态（对应二种颜色）之一：符合或超过CIR.标记和丢弃动作作用在这二种流量状态上。该标记器和管制器的类型是相当粗糙的。
1）承诺的访问速率（CAR）（典型的单速率双色和单桶应用）
CAR是CISCO IOS软件中提供的最古老的管制工具，古老原因有：
CAR与DiffServ RFC不兼容。
没有基本百分比的带宽规范和分层管制
CAR不能使用MQC语法。
NBAR不能用在CAR中，还有其它方面。
RFC中定义了两种令牌桶算法——单速率三色标记算法和双速率三色标记算法，其评估结果都是为报文打上红、黄、绿三色标记。
QoS会根据报文的颜色，设置报文的丢弃优先级，其中单速率三色标记比较关心报文尺寸的突发，而双速率三色标记则关注速率上的突发，
两种算法都可工作于色盲模式和非色盲模式。
以下结合这两种工作模式介绍一下RFC中所描述的这两种算法。
单速率三色标记算法
IETF的RFC文件[2]定义了单速率三色标记算法，评估依据以下3个参数：承诺访问速率(CIR)，即向令牌桶中填充令牌的速率；承诺突发尺寸(CBS)，即令牌桶的容量，每次突发所允许的最大流量尺寸（注：设置的突发尺寸必须大于最大报文长度）；超额突发尺寸(EBS)。
一般采用双桶结构：C桶和E桶。Tc表示C桶中的令牌数，Te表示E桶中令牌数，两桶的总容量分别为CBS和EBS。初始状态时两桶是满的，即Tc和Te初始值分别等于CBS和EBS。令牌的产生速率是CIR，通常是先往C桶中添加令牌，等C桶满了，再往E桶中添加令牌，当两桶都被填满时，新产生的令牌将会被丢弃。
色盲模式下，假设到达的报文长度为B。若报文长度B小于C桶中的令牌数Tc，则报文被标记为绿色，且C桶中的令牌数减
少B；若Tc<B <Te，则标记为×××，E和C桶中的令牌数均减少B；若B >Te，标记为红色，两桶总令牌数都不减少。
在非色盲模式下，若报文已被标记为绿色或B <Tc，则报文被标记为绿色，Tc减少B；若报文已被标记为×××或Tc<B <Te，则标记为×××，且Te减少B；若报文已被标记为红色或
B >Te，则标记为红色，Tc和Te都不减少。
双速率三色标记算法
IETF的RFC文件[3]定义了双速率三色算法，主要是根据4种流量参数来评估：CIR、CBS、峰值信息速率(PIR)，峰值突发尺寸(PBS)。前两种参数与单速率三色算法中的含义相同，PIR这个参数只在交换机上才有，路由器没有这个参数。该值必须不小于CIR的设置值，如果大于CIR，则速率限制在CIR于PRI之间的一个值。
与单速率三色标记算法不同，双速率三色标记算法的两个令牌桶C桶和P桶填充令牌的速率不同，C桶填充速率为CIR，P桶为PIR；两桶的容量分别为CBS和PBS。用Tc和Tp表示两桶中的令牌数目，初始状态时两桶是满的，即Tc和Tp初始值分别等于CBS和PBS。
色盲模式下，如果到达的报文速率大于PIR，超过Tp+Tc部分无法得到令牌，报文被标记为红色，未超过Tp+Tc而从P桶中获取令牌的报文标记为×××，从C桶中获取令牌的报文被标记为绿色；当报文速率小于PIR，大于CIR时，报文不会得不到令牌，但超过Tp部分报文将从P桶中获取令牌，被标记为×××报文，从C桶中获取令牌的报文被标记为绿色；当报文速率小于CIR时，报文所需令牌数不会超过Tc，只从C桶中获取令牌，所以只会被标记为绿色报文。
在非色盲模式下，如果报文已被标记为红色或者超过Tp+Tc部分无法得到令牌的报文，被标记为红色；如果标记为×××或者超过Tc未超过Tp部分报文记为×××；如果报文被标记为绿或未超过Tc部分报文，被标记为绿色。
----------------------------
原文链接:https://blog.51cto.com/kalng/903225
程序猿的技术大观园：www.javathinker.net
[这个贴子最后由 flybird 在 2020-03-15 23:01:46 重新编辑]
|
|
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → 令牌桶算法
消息
查看
搜索
好友
邮件
复制
引用
IP: 已设置保密
