目錄

流量控制算法簡(jiǎn)介

漏桶算法

漏桶算法的實(shí)現(xiàn)

令牌桶算法

漏桶和令牌桶的區(qū)別

令牌桶原理

單速率三色標(biāo)記算法

雙速率三色標(biāo)記算法

令牌桶實(shí)現(xiàn)

流量控制算法簡(jiǎn)介

流量控制在計(jì)算機(jī)領(lǐng)域稱為過(guò)載保護(hù)。何為過(guò)載保護(hù)？所謂“過(guò)載”，即需求超過(guò)了負(fù)載能力;而“保護(hù)”則是指當(dāng)“過(guò)載”發(fā)生了，采取必要的措施保護(hù)自己不受“傷害”。在計(jì)算機(jī)領(lǐng)域，尤其是分布式系統(tǒng)領(lǐng)域，“過(guò)載保護(hù)”是一個(gè)重要的概念。一個(gè)不具備“過(guò)載保護(hù)”功能的系統(tǒng)，是非常危險(xiǎn)和脆弱的，很可能由于瞬間的壓力激增，引起“雪崩效應(yīng)”，導(dǎo)致系統(tǒng)的各個(gè)部分都同時(shí)崩潰，停止服務(wù)。這就好像在沒(méi)有保險(xiǎn)絲的保護(hù)下，電壓突然變高，導(dǎo)致所有的電器都會(huì)被損壞一樣，“過(guò)載保護(hù)”功能是系統(tǒng)的“保險(xiǎn)絲”。

如今互聯(lián)網(wǎng)領(lǐng)域，也借鑒了這一思路扛住雙十二， 控制網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)乃俾?，使流量以比較均勻的速度向外發(fā)送。 最終實(shí)現(xiàn)優(yōu)化性能，減少延遲和提高帶寬等。

漏桶算法

漏桶算法思路很簡(jiǎn)單，水（請(qǐng)求）先進(jìn)入到漏桶里，漏桶以一定的速度出水，當(dāng)水流入速度過(guò)大會(huì)直接溢出，可以看出漏桶算法能強(qiáng)行限制數(shù)據(jù)的傳輸速率。

在某些情況下，漏桶算法不能夠有效地使用網(wǎng)絡(luò)資源。因?yàn)槁┩暗穆┏鏊俾适枪潭ǖ膮?shù)，所以即使網(wǎng)絡(luò)中不存在資源沖突（沒(méi)有發(fā)生擁塞），漏桶算法也不能使某一個(gè)單獨(dú)的流突發(fā)到端口速率。因此，漏桶算法對(duì)于存在突發(fā)特性的流量來(lái)說(shuō)缺乏效率。

而令牌桶算法則能夠滿足這些具有突發(fā)特性的流量。通常，漏桶算法與令牌桶算法可以結(jié)合起來(lái)為網(wǎng)絡(luò)流量提供更大的控制。

漏桶算法的實(shí)現(xiàn)

long timeStamp = getNowTime(); 
int capacity = 10000;// 桶的容量
int rate = 1;//水漏出的速度 
int water = 100;//當(dāng)前水量  
public static bool control() {   
    //先執(zhí)行漏水，因?yàn)閞ate是固定的，所以可以認(rèn)為“時(shí)間間隔*rate”即為漏出的水量
    long  now = getNowTime();
    water = Math.max(0, water - (now - timeStamp) * rate);
    timeStamp = now;
    if (water < capacity) { // 水還未滿，加水
        water ++; 
        return true; 
    } else { 
        return false;//水滿，拒絕加水
   } 
} 

注意：這里的timeStamp是上一次執(zhí)行操作的時(shí)間，這次操作，要先執(zhí)行漏水，漏水量是now-timeStamp 相關(guān)的函數(shù)

該算法很好的解決了時(shí)間邊界處理不夠平滑的問(wèn)題，因?yàn)樵诿看握?qǐng)求進(jìn)桶前都將執(zhí)行“漏水”的操作，再無(wú)邊界問(wèn)題。

但是對(duì)于很多場(chǎng)景來(lái)說(shuō)，除了要求能夠限制數(shù)據(jù)的平均傳輸速率外，還要求允許某種程度的突發(fā)傳輸。這時(shí)候漏桶算法可能就不合適了，令牌桶算法更為適合。

令牌桶算法

令牌桶算法的原理是系統(tǒng)會(huì)以一個(gè)恒定的速度往桶里放入令牌，而如果請(qǐng)求需要被處理，則需要先從桶里獲取一個(gè)令牌，當(dāng)桶里沒(méi)有令牌可取時(shí)，則拒絕服務(wù)。

令牌桶算法的基本過(guò)程如下：

假如用戶配置的平均發(fā)送速率為r，則每隔1/r秒一個(gè)令牌被加入到桶中；

假設(shè)桶最多可以存發(fā)b個(gè)令牌。如果令牌到達(dá)時(shí)令牌桶已經(jīng)滿了，那么這個(gè)令牌會(huì)被丟棄；

當(dāng)一個(gè)n個(gè)字節(jié)的數(shù)據(jù)包到達(dá)時(shí)，就從令牌桶中刪除n個(gè)令牌，并且數(shù)據(jù)包被發(fā)送到網(wǎng)絡(luò)；

如果令牌桶中少于n個(gè)令牌，那么不會(huì)刪除令牌，并且認(rèn)為這個(gè)數(shù)據(jù)包在流量限制之外；

算法允許最長(zhǎng)b個(gè)字節(jié)的突發(fā)，但從長(zhǎng)期運(yùn)行結(jié)果看，數(shù)據(jù)包的速率被限制成常量r。

對(duì)于在流量限制外的數(shù)據(jù)包可以以不同的方式處理：

它們可以被丟棄；

它們可以排放在隊(duì)列中以便當(dāng)令牌桶中累積了足夠多的令牌時(shí)再傳輸；

它們可以繼續(xù)發(fā)送，但需要做特殊標(biāo)記，網(wǎng)絡(luò)過(guò)載的時(shí)候?qū)⑦@些特殊標(biāo)記的包丟棄。

漏桶和令牌桶的區(qū)別

兩者主要區(qū)別在于“漏桶算法”能夠強(qiáng)行限制數(shù)據(jù)的傳輸速率，而“令牌桶算法”在能夠限制數(shù)據(jù)的平均傳輸速率外，還允許某種程度的突發(fā)傳輸。

在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允許突發(fā)地傳輸數(shù)據(jù)直到達(dá)到用戶配置的上限，所以它適合于具有突發(fā)特性的流量。

令牌桶原理

令牌桶是網(wǎng)絡(luò)設(shè)備的內(nèi)部存儲(chǔ)池，而令牌則是以給定速率填充令牌桶的虛擬信息包。每個(gè)到達(dá)的令牌都會(huì)從數(shù)據(jù)隊(duì)列領(lǐng)出相應(yīng)的數(shù)據(jù)包進(jìn)行發(fā)送，發(fā)送完數(shù)據(jù)后令牌被刪除。

請(qǐng)求注解（RFC）中定義了兩種令牌桶算法     單速率三色標(biāo)記算法和雙速率三色標(biāo)記算法，其評(píng)估結(jié)果都是為報(bào)文打上紅、黃、綠三色標(biāo)記。

QoS會(huì)根據(jù)報(bào)文的顏色，設(shè)置報(bào)文的丟棄優(yōu)先級(jí)，其中單速率三色標(biāo)記比較關(guān)心報(bào)文尺寸的突發(fā)，而雙速率三色標(biāo)記則關(guān)注速率上的突發(fā)，兩種算法都可工作于色盲模式和非色盲模式。以下結(jié)合這兩種工作模式介紹一下RFC中所描述的這兩種算法。

單速率三色標(biāo)記算法

網(wǎng)絡(luò)工程師任務(wù)小組（IETF）的RFC文件定義了單速率三色標(biāo)記算法，評(píng)估依據(jù)以下3個(gè)參數(shù)：承諾訪問(wèn)速率(CIR)，即向令牌桶中填充令牌的速率；承諾突發(fā)尺寸(CBS)，即令牌桶的容量，每次突發(fā)所允許的最大流量尺寸（注：設(shè)置的突發(fā)尺寸必須大于最大報(bào)文長(zhǎng)度）；超額突發(fā)尺寸(EBS)。

一般采用雙桶結(jié)構(gòu)：C桶和E桶。Tc表示C桶中的令牌數(shù)，Te表示E桶中令牌數(shù)，兩桶的總?cè)萘糠謩e為CBS和EBS。初始狀態(tài)時(shí)兩桶是滿的，即Tc和Te初始值分別等于CBS和EBS。令牌的產(chǎn)生速率是CIR，通常是先往C桶中添加令牌，等C桶滿了，再往E桶中添加令牌，當(dāng)兩桶都被填滿時(shí)，新產(chǎn)生的令牌將會(huì)被丟棄。

色盲模式下，假設(shè)到達(dá)的報(bào)文長(zhǎng)度為B。若報(bào)文長(zhǎng)度B小于C桶中的令牌數(shù)Tc，則報(bào)文被標(biāo)記為綠色，且C桶中的令牌數(shù)減少B；若Tc<B <Te，則標(biāo)記為黃色，E和C桶中的令牌數(shù)均減少B；若B >Te，標(biāo)記為紅色，兩桶總令牌數(shù)都不減少。

在非色盲模式下，若報(bào)文已被標(biāo)記為綠色或B <Tc，則報(bào)文被標(biāo)記為綠色，Tc減少B；若報(bào)文已被標(biāo)記為黃色或Tc<B <Te，則標(biāo)記為黃色，且Te減少B；若報(bào)文已被標(biāo)記為紅色或B >Te，則標(biāo)記為紅色，Tc和Te都不減少。

雙速率三色標(biāo)記算法

IETF的RFC文件定義了雙速率三色算法，主要是根據(jù)4種流量參數(shù)來(lái)評(píng)估：CIR、CBS、峰值信息速率(PIR)，峰值突發(fā)尺寸(PBS)。前兩種參數(shù)與單速率三色算法中的含義相同，PIR這個(gè)參數(shù)只在交換機(jī)上才有，路由器沒(méi)有這個(gè)參數(shù)。該值必須不小于CIR的設(shè)置值，如果大于CIR，則速率限制在CIR于PRI之間的一個(gè)值。

與單速率三色標(biāo)記算法不同，雙速率三色標(biāo)記算法的兩個(gè)令牌桶C桶和P桶填充令牌的速率不同，C桶填充速率為CIR，P桶為PIR；兩桶的容量分別為CBS和PBS。用Tc和Tp表示兩桶中的令牌數(shù)目，初始狀態(tài)時(shí)兩桶是滿的，即Tc和Tp初始值分別等于CBS和PBS。

色盲模式下，如果到達(dá)的報(bào)文速率大于PIR，超過(guò)Tp+Tc部分無(wú)法得到令牌，報(bào)文被標(biāo)記為紅色，未超過(guò)Tp+Tc而從P桶中獲取令牌的報(bào)文標(biāo)記為黃色，從C桶中獲取令牌的報(bào)文被標(biāo)記為綠色；當(dāng)報(bào)文速率小于PIR，大于CIR時(shí)，報(bào)文不會(huì)得不到令牌，但超過(guò)Tp部分報(bào)文將從P桶中獲取令牌，被標(biāo)記為黃色報(bào)文，從C桶中獲取令牌的報(bào)文被標(biāo)記為綠色；當(dāng)報(bào)文速率小于CIR時(shí)，報(bào)文所需令牌數(shù)不會(huì)超過(guò)Tc，只從C桶中獲取令牌，所以只會(huì)被標(biāo)記為綠色報(bào)文。

在非色盲模式下，如果報(bào)文已被標(biāo)記為紅色或者超過(guò)Tp+Tc部分無(wú)法得到令牌的報(bào)文，被標(biāo)記為紅色；如果標(biāo)記為黃色或者超過(guò)Tc未超過(guò)Tp部分報(bào)文記為黃色；如果報(bào)文被標(biāo)記為綠或未超過(guò)Tc部分報(bào)文，被標(biāo)記為綠色。

令牌桶實(shí)現(xiàn)

假如用戶配置的平均發(fā)送速率為r，則每隔1/r秒一個(gè)令牌被加入到桶中(每秒會(huì)有r個(gè)令牌放入桶中)；

假設(shè)桶中最多可以存放b個(gè)令牌。如果令牌到達(dá)時(shí)令牌桶已經(jīng)滿了，那么這個(gè)令牌會(huì)被丟棄；

當(dāng)一個(gè)n個(gè)字節(jié)的數(shù)據(jù)包到達(dá)時(shí)，就從令牌桶中刪除n個(gè)令牌(不同大小的數(shù)據(jù)包，消耗的令牌數(shù)量不一樣)，并且數(shù)據(jù)包被發(fā)送到網(wǎng)絡(luò)；

如果令牌桶中少于n個(gè)令牌，那么不會(huì)刪除令牌，并且認(rèn)為這個(gè)數(shù)據(jù)包在流量限制之外(n個(gè)字節(jié)，需要n個(gè)令牌。該數(shù)據(jù)包將被緩存或丟棄)；

算法允許最長(zhǎng)b個(gè)字節(jié)的突發(fā)，但從長(zhǎng)期運(yùn)行結(jié)果看，數(shù)據(jù)包的速率被限制成常量r。對(duì)于在流量限制外的數(shù)據(jù)包可以以不同的方式處理：

1)它們可以被丟棄；

2)它們可以排放在隊(duì)列中以便當(dāng)令牌桶中累積了足夠多的令牌時(shí)再傳輸；

3)它們可以繼續(xù)發(fā)送，但需要做特殊標(biāo)記，網(wǎng)絡(luò)過(guò)載的時(shí)候?qū)⑦@些特殊標(biāo)記的包丟棄。

long timeStamp=getNowTime(); 
int capacity; // 桶的容量 
int rate ;//令牌放入速度
 int tokens;//當(dāng)前水量  
bool control() {
   //先執(zhí)行添加令牌的操作
   long  now = getNowTime();
   tokens = max(capacity, tokens+ (now - timeStamp)*rate); 
   timeStamp = now;   //令牌已用完，拒絕訪問(wèn)
   if(tokens<1){
     return false;
   }else{//還有令牌，領(lǐng)取令牌
     tokens--;
     retun true;
   }
 } 

令牌桶算法是網(wǎng)絡(luò)流量整形和速率限制中最常使用的一種算法。典型情況下，令牌桶算法用來(lái)控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)目，并允許突發(fā)數(shù)據(jù)的發(fā)送。

大小固定的令牌桶可自行以恒定的速率源源不斷地產(chǎn)生令牌。如果令牌不被消耗，或者被消耗的速度小于產(chǎn)生的速度，令牌就會(huì)不斷地增多，直到把桶填滿。后面再產(chǎn)生的令牌就會(huì)從桶中溢出。最后桶中可以保存的最大令牌數(shù)永遠(yuǎn)不會(huì)超過(guò)桶的大小。

傳送到令牌桶的數(shù)據(jù)包需要消耗令牌。不同大小的數(shù)據(jù)包，消耗的令牌數(shù)量不一樣。令牌桶這種控制機(jī)制基于令牌桶中是否存在令牌來(lái)指示什么時(shí)候可以發(fā)送流量。令牌桶中的每一個(gè)令牌都代表一個(gè)字節(jié)。如果令牌桶中存在令牌，則允許發(fā)送流量；而如果令牌桶中不存在令牌，則不允許發(fā)送流量。因此，如果突發(fā)門限被合理地配置并且令牌桶中有足夠的令牌，那么流量就可以以峰值速率發(fā)送。