令牌桶算法

令牌桶算法

令牌桶算法分为以下几种：

QOS是用来给特定的网络或用户数据有效带宽的工具，它限速的核心思想是令牌捅算法。所谓的令牌捅算法就是每秒都要往令牌捅中加令牌(每个令牌1bit)，数据只有取出令牌捅中的令牌才会被转发，如果没有取到令牌则不会被网络设备转发，对此采用了三种令牌捅算法。

1.单速算色

在单色双速的令牌算法中，只存在一个令牌捅，并且只会出现两种结果，即符合CIR（conform）和超出的CIR(exceed)，符合的将做传输，超出的将丢弃。

2.单速双色

在单色双速的令牌捅算法中，使用两个令牌捅，用户每秒的可用带宽总和是两个的令牌之和，第一个捅的算法和单速双色的算法是一样，而第二个捅的令牌是把第一个捅前一秒没有被数据取走的令牌移到第二桶中存起来。我门把第一个捅称为bc，第二捅称为be。

每秒可传输的数据=bc+be，be和bc每秒都要清除一次，其中be不能无限的加，只能小于或等于CIR。

由于使用两个捅用户数据出现三种流量。

小于等于CIR(conform)。

大于CIR或等于CIR与be之和（exceed）。

超过CIR与be之和（voilation）。

3.双速三色

双速三色算法同样也使用两个捅，但与单色双速不一样，在这里bc与be是完全的，bc和be之间好无关系。第一个捅采用的算法与前两种的第一个捅的算法一样都是CIR；第二桶的算法是CIR+Be。当有相应的QOS数据流时，先检查第二桶，若大于则采取相应的动作。若小于则再检查第一个捅，大于第一个捅采用相应的动作，小于则正常传输。

1. 单速双色

在单速双色算法中只存在一个桶。每秒钟放入桶中的令牌总数我们称为给被服务对象提供的承诺速率及CIR，但并不是每一秒中一次性的全部放入所有的CIR。只要我们在每秒之内放完即可，我们把在一秒内每次放入桶的令牌的多少称为BC。例如8000bit/s 如果我们每秒中之内方入两次每次放入4000及我们的BC值等于4000也是可以的。只要我们在一秒钟之内放完即可。

这种情况下用户最大速率只能小于或者等于8000比特每秒超出了则会采取动作。

2. 单速三色

单速三色算法中只存在两个桶。每一秒钟可用带宽总是两个桶可用带宽之和。当第一个桶放入的令牌数目在开始的一秒时，如果用户没有用完，则把剩余的放入第二个桶中，从第二秒开始，如果第二秒用户发送的数据有超出则使用第二个桶中未使用完得数据比如：CIR放入8000个令牌，如果用户使用的6000则把剩余的放入第二个桶中，如果第二次用户使用8000那刚好第一个桶用完，那么第二个桶中的2000则清除。如果用10000那么则第一个桶和第二个桶一起使用。

这种

算法中用户第二个桶中的放入的令牌称为be，且be小于等于CIR。

这种情况下用户数据数据小于每秒钟放入的令牌则完全传输。剩余的放入第个桶中。

用户数据大于第一个桶中的令牌总数，则使用第二个桶中剩余的加第一个桶中的加起来使用，

用户数据超过两桶之和多出的则丢弃。

3．双速三色

双速三色这种算法中也有两个桶，一个桶以 CIR的数量每秒传输而第二个桶直接以CIR+BE之和传输称为PIR.传输的时候先检查用户发送使用的总流量如果超出了PIR.则以PIR的发送量传输，超出的部分则采取动作。如果用的发送量小于PIR则使用CIR量传输，超出的部分采取动作。

这种算法中，用户传输量小于CIR正常传输，用户的传输量在CIR和PIR之间的且大于CIR的部分丢弃。

如果大于等于PIR则以PIR的速率传输，超出PIR 的部分则采取动作。