>>分享数据结构和算法相关的知识和技术 书籍支持  卫琴直播  品书摘要  在线测试  资源下载  联系我们
发表一个新主题 开启一个新投票 回复文章 您是本文章第 19719 个阅读者 刷新本主题
 * 贴子主题:  令牌桶算法 回复文章 点赞(0)  收藏  
作者:mary    发表时间:2020-03-15 23:01:46     消息  查看  搜索  好友  邮件  复制  引用

       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 重新编辑]
网站系统异常


系统异常信息
Request URL: http://www.javathinker.net/WEB-INF/lybbs/jsp/topic.jsp?postID=2845

java.lang.NullPointerException

如果你不知道错误发生的原因,请把上面完整的信息提交给本站管理人员