流量控制算法总结

zybingliu 2023-03-08 发布于上海

展开全文

流量控制算法简介

流量控制在计算机领域称为过载保护。何为过载保护？所谓“过载”，即需求超过了负载能力;而“保护”则是指当“过载”发生了，采取必要的措施保护自己不受“伤害”。在计算机领域，尤其是分布式系统领域，“过载保护”是一个重要的概念。一个不具备“过载保护”功能的系统，是非常危险和脆弱的，很可能由于瞬间的压力激增，引起“雪崩效应”，导致系统的各个部分都同时崩溃，停止服务。这就好像在没有保险丝的保护下，电压突然变高，导致所有的电器都会被损坏一样，“过载保护”功能是系统的“保险丝”。

如今互联网领域，也借鉴了这一思路扛住双十二，控制网络数据传输的速率，使流量以比较均匀的速度向外发送。最终实现优化性能，减少延迟和提高带宽等。

漏桶算法

漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数，所以即使网络中不存在资源冲突（没有发生拥塞），漏桶算法也不能使某一个单独的流突发到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。

而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。

漏桶算法的实现

long timeStamp = getNowTime(); 
int capacity = 10000;// 桶的容量
int rate = 1;//水漏出的速度 
int water = 100;//当前水量  
public static bool control() {   
    //先执行漏水，因为rate是固定的，所以可以认为“时间间隔*rate”即为漏出的水量
    long  now = getNowTime();
    water = Math.max(0, water - (now - timeStamp) * rate);
    timeStamp = now;
    if (water < capacity) { // 水还未满，加水
        water ++; 
        return true; 
    } else { 
        return false;//水满，拒绝加水
   } 
}

注意：这里的timeStamp是上一次执行操作的时间，这次操作，要先执行漏水，漏水量是now-timeStamp 相关的函数

该算法很好的解决了时间边界处理不够平滑的问题，因为在每次请求进桶前都将执行“漏水”的操作，再无边界问题。

但是对于很多场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

令牌桶算法的基本过程如下：

假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中；

假设桶最多可以存发b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃；

当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌，并且数据包被发送到网络；

如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外；

算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。

对于在流量限制外的数据包可以以不同的方式处理：

它们可以被丢弃；

它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输；

它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃。

漏桶和令牌桶的区别

两者主要区别在于“漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输速率外，还允许某种程度的突发传输。

在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的上限，所以它适合于具有突发特性的流量。

令牌桶原理

令牌桶是网络设备的内部存储池，而令牌则是以给定速率填充令牌桶的虚拟信息包。每个到达的令牌都会从数据队列领出相应的数据包进行发送，发送完数据后令牌被删除。

请求注解（RFC）中定义了两种令牌桶算法 单速率三色标记算法和双速率三色标记算法，其评估结果都是为报文打上红、黄、绿三色标记。

QoS会根据报文的颜色，设置报文的丢弃优先级，其中单速率三色标记比较关心报文尺寸的突发，而双速率三色标记则关注速率上的突发，两种算法都可工作于色盲模式和非色盲模式。以下结合这两种工作模式介绍一下RFC中所描述的这两种算法。

单速率三色标记算法

网络工程师任务小组（IETF）的RFC文件定义了单速率三色标记算法，评估依据以下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文件定义了双速率三色算法，主要是根据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部分报文，被标记为绿色。

令牌桶实现

假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中(每秒会有r个令牌放入桶中)；

假设桶中最多可以存放b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃；

当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌(不同大小的数据包，消耗的令牌数量不一样)，并且数据包被发送到网络；

如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外(n个字节，需要n个令牌。该数据包将被缓存或丢弃)；

算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理：

1)它们可以被丢弃；

2)它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输；

3)它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃。

long timeStamp=getNowTime(); 
int capacity; // 桶的容量 
int rate ;//令牌放入速度
 int tokens;//当前水量  
bool control() {
   //先执行添加令牌的操作
   long  now = getNowTime();
   tokens = max(capacity, tokens+ (now - timeStamp)*rate); 
   timeStamp = now;   //令牌已用完，拒绝访问
   if(tokens<1){
     return false;
   }else{//还有令牌，领取令牌
     tokens--;
     retun true;
   }
 }

令牌桶算法是网络流量整形和速率限制中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗，或者被消耗的速度小于产生的速度，令牌就会不断地增多，直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。

传送到令牌桶的数据包需要消耗令牌。不同大小的数据包，消耗的令牌数量不一样。令牌桶这种控制机制基于令牌桶中是否存在令牌来指示什么时候可以发送流量。令牌桶中的每一个令牌都代表一个字节。如果令牌桶中存在令牌，则允许发送流量；而如果令牌桶中不存在令牌，则不允许发送流量。因此，如果突发门限被合理地配置并且令牌桶中有足够的令牌，那么流量就可以以峰值速率发送。