ＱｏＳ技術(shù)中令牌桶算法實(shí)現(xiàn)方式比較

摘要：令牌桶算法是目前IP QoS中最常采用的一種流量測(cè)量方法，廣泛應(yīng)用于約定訪問速率技術(shù)、通用流量整形技術(shù)以及物理接口總速率限制等技術(shù)中。IETF RFC 建議規(guī)范了單速率三色標(biāo)記和雙速率三色標(biāo)記兩種令牌桶算法，在桶的構(gòu)成、令牌添加和報(bào)文處理流程方面前者較后者簡(jiǎn)單，成為目前業(yè)界比較常用的流量標(biāo)記方式。在實(shí)際應(yīng)用中，應(yīng)針對(duì)不同的流量特征選擇恰當(dāng)?shù)臉?biāo)記方式。

關(guān)鍵詞：令牌桶；單速率三色標(biāo)記；雙速率三色標(biāo)記；流量監(jiān)管

Abstract: The token bucket algorithm is the most popular method of traffic measuring in IP QoS technology. It has been widely used in Committed Access Rate (CAR)， Generic Traffic Shaping (GTS)， and Line Rate (LR) technologies. Two kinds of token bucket algorithms—a single rate three color marker and a two rate three color marker—have been recommended in the Internet Engineering Task Force (IETF) Request for Comment (RFC) documents. In view of the bucket architecture， the token adding， and the packet process， the single rate three color marker is easier than the two rate one. For practical applications， different traffic characteristics choose different algorithm.

Key words: token bucket; a single rate three color marker; a two rate three color marker; traffic policing

隨著因特網(wǎng)的發(fā)展，IP業(yè)務(wù)不斷快速增長(zhǎng)。提高信息在IP網(wǎng)絡(luò)上傳輸?shù)馁|(zhì)量是IP網(wǎng)發(fā)展中的一個(gè)關(guān)鍵所在。IP QoS技術(shù)的開發(fā)，目的就是為用戶業(yè)務(wù)提供端到端的服務(wù)質(zhì)量保證，已成為近幾年業(yè)界研究的熱點(diǎn)。目前存在多種IP QoS服務(wù)模型，其中應(yīng)用最廣的是區(qū)分服務(wù)模型(DiffServ)。DiffServ模型通過數(shù)據(jù)包分類、擁塞管理、擁擠避免、速率限制和流量整形技術(shù)來實(shí)現(xiàn)服務(wù)質(zhì)量控制，在其速率限制和流量整形中，主要使用了令牌桶算法來評(píng)估流量速率是否超過規(guī)定值[1]。

本文第一部分闡述了一下網(wǎng)絡(luò)工程師任務(wù)小組(IETF) 請(qǐng)求注解(RFC)建議規(guī)范的兩種令牌桶算法；第二部分簡(jiǎn)要介紹了令牌桶算法在IP QoS中的應(yīng)用；第三部分詳細(xì)說明了目前業(yè)界常用的兩種實(shí)現(xiàn)方式，并對(duì)兩種方式的實(shí)現(xiàn)過程進(jìn)行了具體的比較分析。

1 令牌桶算法基本原理

令牌桶是網(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ù)后令牌被刪除。

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中所描述的這兩種算法。

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

IETF的RFC文件[2]定義了單速率三色標(biāo)記算法，評(píng)估依據(jù)以下3個(gè)參數(shù)：承諾訪問速率(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；若TcTe，標(biāo)記為紅色，兩桶總令牌數(shù)都不減少。

在非色盲模式下，若報(bào)文已被標(biāo)記為綠色或B

B >Te，則標(biāo)記為紅色，Tc和Te都不減少。

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

IETF的RFC文件[3]定義了雙速率三色算法，主要是根據(jù)4種流量參數(shù)來評(píng)估：CIR、CBS、峰值信息速率(PIR)，峰值突發(fā)尺寸(PBS)。前兩種參數(shù)與單速率三色算法中的含義相同，PIR這個(gè)參數(shù)只在交換機(jī)上才有，路由器沒有這個(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，超過Tp+Tc部分無法得到令牌，報(bào)文被標(biāo)記為紅色，未超過Tp+Tc而從P桶中獲取令牌的報(bào)文標(biāo)記為黃色，從C桶中獲取令牌的報(bào)文被標(biāo)記為綠色；當(dāng)報(bào)文速率小于PIR，大于CIR時(shí)，報(bào)文不會(huì)得不到令牌，但超過Tp部分報(bào)文將從P桶中獲取令牌，被標(biāo)記為黃色報(bào)文，從C桶中獲取令牌的報(bào)文被標(biāo)記為綠色；當(dāng)報(bào)文速率小于CIR時(shí)，報(bào)文所需令牌數(shù)不會(huì)超過Tc，只從C桶中獲取令牌，所以只會(huì)被標(biāo)記為綠色報(bào)文。

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

2 令牌桶算法的應(yīng)用

2.1 在流量監(jiān)管中的應(yīng)用

約定訪問速率(CAR)是流量監(jiān)管常用技術(shù)之一[4]，它的監(jiān)管原理如圖1所示。

根據(jù)預(yù)設(shè)的匹配規(guī)則先對(duì)報(bào)文進(jìn)行分類，不符合匹配規(guī)則的報(bào)文不需要經(jīng)過令牌桶的處理，直接發(fā)送；符合匹配規(guī)則的報(bào)文，則需要令牌桶進(jìn)行處理。當(dāng)桶中有足夠的令牌則報(bào)文可以被繼續(xù)發(fā)送下去，同時(shí)令牌桶中的令牌量按報(bào)文的長(zhǎng)度做相應(yīng)的減少；當(dāng)令牌桶中的令牌不足時(shí)，報(bào)文將不能被發(fā)送，只有等到桶中生成了新的令牌，報(bào)文才可以發(fā)送。這就可以限制報(bào)文的流量只能是小于等于令牌生成的速度，達(dá)到限制流量的目的。

2.2 在通用流量整形中的應(yīng)用

通用流量整形中(GTS)[4](如圖2所示)與CAR的原理稍有差別：第一，GTS只用于出方向流量限速，CAR出入方向均可以，但一般多用于入方向；第二，利用CAR進(jìn)行報(bào)文流量控制時(shí)，對(duì)超過速率限制的報(bào)文直接丟棄，而GTS則是對(duì)超過速率限制的報(bào)文進(jìn)行緩沖，即當(dāng)令牌桶中的令牌少到報(bào)文不能再發(fā)送時(shí)，報(bào)文將被緩存入隊(duì)列，等有了足夠的令牌之后再發(fā)送，這樣就減少了報(bào)文的丟棄，但是要注意的是，如果緩存隊(duì)列已滿，這時(shí)到達(dá)的報(bào)文仍舊會(huì)被丟棄。

2.3 在端口限速中的應(yīng)用

端口限速(LR)[4](如圖3所示)也用于出方向，但不同于GTS的是：第一，GTS與CAR是在IP層實(shí)現(xiàn)的，所以對(duì)于不經(jīng)過IP層處理的報(bào)文不起作用，而LR則能夠限制在物理接口上通過的所有報(bào)文；第二，LR不但能夠?qū)Τ^流量限制的報(bào)文進(jìn)行緩存，并且可以利用QoS豐富的隊(duì)列如優(yōu)先級(jí)隊(duì)列(PQ)、自定義隊(duì)列(CQ)、加權(quán)公平對(duì)列(WFQ)等來緩存報(bào)文。

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

上面介紹了RFC中定義的令牌桶技術(shù)原理以及其在IP QoS中的應(yīng)用，但是在實(shí)際應(yīng)用中，令牌桶究竟是怎么實(shí)現(xiàn)的？令牌桶中的令牌是怎么添加的？報(bào)文的處理流程又是什么樣的？下面就簡(jiǎn)單談一談令牌桶在業(yè)界的實(shí)現(xiàn)方式[5]。

3.1 單速率三色標(biāo)記算法的實(shí)現(xiàn)

3.1.1 桶的構(gòu)成

在令牌桶的構(gòu)成上，目前業(yè)界有兩種方式，如圖4所示。

可以由一個(gè)桶實(shí)現(xiàn)，即C桶是E桶中的一部分(圖4上)，最終桶的容量是由EBS決定的。不管有沒有突發(fā)流量，EBS不能為0，必須大于或等于CBS。這種實(shí)現(xiàn)方式完全按照令牌桶的定義來實(shí)現(xiàn)，因?yàn)镃BS和EBS都是令牌桶的參數(shù)，所以放入一個(gè)相同的桶實(shí)現(xiàn)，通過突發(fā)計(jì)數(shù)器來進(jìn)行區(qū)分。也可以由兩個(gè)桶實(shí)現(xiàn)(圖4下)，即C桶和E桶分開實(shí)現(xiàn)。如果不允許有突發(fā)流量，EBS則設(shè)置成0。

3.1.2 令牌添加

令牌桶的添加完全依照RFC規(guī)定實(shí)現(xiàn)，按照恒定的速率CIR添加。即每隔1/CIR時(shí)間添加一個(gè)令牌，添加順序?yàn)橄忍砑覥桶再添加E桶，當(dāng)令牌桶添加滿的時(shí)候，再產(chǎn)生的令牌就會(huì)被丟棄。

實(shí)際中比較常見的有兩種實(shí)現(xiàn)方式：(1)周期性的添加，如圖5所示，添加的時(shí)間間隔就是令牌桶的容量與添加速率的比值：T c=CBS/CIR，每次添加的令牌數(shù)為CBS 個(gè)；(2)一次性添加，只有當(dāng)令牌桶中沒有令牌時(shí)才添加令牌，如圖6所示，添加令牌的數(shù)量是△t×CIR(△t是當(dāng)前時(shí)間與上次添加令牌的時(shí)間之差)，且是一次添加完畢，并不是按照一定速率添加。

3.1.3 報(bào)文處理流程

一般的報(bào)文處理方法如圖7所示：當(dāng)報(bào)文到來后，直接與桶中的令牌數(shù)相比較，如果有足夠的令牌就轉(zhuǎn)發(fā)，如果沒有足夠的令牌則丟棄或緩存。這種令牌桶處理方式在突發(fā)流量的處理上沒有優(yōu)勢(shì)，也就是說當(dāng)存在較大的突發(fā)流量時(shí)，令牌桶可能會(huì)由于沒有足夠令牌無法處理報(bào)文，而且在沒有突發(fā)流量且報(bào)文到達(dá)速率較大時(shí)，報(bào)文處理流程也不連續(xù)，有時(shí)會(huì)因?yàn)榱钆茢?shù)量不足而造成丟包。

為解決這種無謂的丟包問題，目前業(yè)界采用了一種借貸機(jī)制的報(bào)文處理方法，如圖8所示。當(dāng)報(bào)文到來后，只要令牌桶中有令牌，無論數(shù)量是否足夠，都可以轉(zhuǎn)發(fā)報(bào)文。當(dāng)令牌數(shù)量小于報(bào)文長(zhǎng)度時(shí)，就可以欠債轉(zhuǎn)發(fā)，即轉(zhuǎn)發(fā)后令牌桶中令牌數(shù)目為負(fù)；當(dāng)下次添加令牌的時(shí)候，先還清所欠債務(wù)，再繼續(xù)轉(zhuǎn)發(fā)報(bào)文。這種處理方法較前者在處理突發(fā)報(bào)文時(shí)有優(yōu)勢(shì)，能夠保證報(bào)文發(fā)送的連續(xù)性。

3.1.4 實(shí)現(xiàn)方式比較

假設(shè)令牌桶的總?cè)萘繛? 000 kb，CIR為125 kb/s，報(bào)文到達(dá)的速率為200 kb/s，報(bào)文長(zhǎng)度為125 kB (1 000 kb)。

方式一：周期性添加令牌，只有當(dāng)令牌數(shù)足夠時(shí)才轉(zhuǎn)發(fā)報(bào)文。添加令牌的周期為8 s，而轉(zhuǎn)發(fā)一條報(bào)文的時(shí)間為5 s。

方式二：一次性添加令牌，當(dāng)令牌數(shù)不足時(shí)采用借債機(jī)制。轉(zhuǎn)發(fā)一條報(bào)文的時(shí)間是5 s，但是添加令牌的時(shí)間是不一定的，每次添加令牌的數(shù)目為CIR×△t。

圖9至圖11是對(duì)這兩種方式的令牌桶中令牌數(shù)、報(bào)文轉(zhuǎn)發(fā)速率和令牌添加過程的比較。

分析數(shù)據(jù)的處理流程得出以下結(jié)論：

(1) 數(shù)據(jù)包丟棄率：方式二的丟包率遠(yuǎn)小于方式一。

方式一中，由于令牌添加周期與報(bào)文發(fā)送周期的不一致，導(dǎo)致第6 s到第8 s由于沒有令牌不能轉(zhuǎn)發(fā)報(bào)文。而第8 s到第16 s雖然在不斷添加令牌，但令牌數(shù)不足以轉(zhuǎn)發(fā)一個(gè)報(bào)文，所以仍舊無法轉(zhuǎn)發(fā)報(bào)文，那在這一段時(shí)間內(nèi)到達(dá)的報(bào)文將被丟棄掉。在前16s的時(shí)間內(nèi)丟包率達(dá)到了10/16≈62.5%，由于添加令牌和發(fā)送報(bào)文的時(shí)間都是固定的，所以整個(gè)發(fā)送過程中的丟包率也為62.5%。

方式二中，第5 s第一條報(bào)文發(fā)送結(jié)束令牌被消耗光，但第6 s又立即加入了550 kb令牌，雖不夠轉(zhuǎn)發(fā)一條報(bào)文，但可以采用借債機(jī)制，直到第10 s第二條報(bào)文發(fā)送結(jié)束，累計(jì)欠債250 kb。這時(shí)若有報(bào)文到達(dá)，就不能繼續(xù)欠債，而要注入新的令牌才能繼續(xù)轉(zhuǎn)發(fā)。直到第15 s第三條報(bào)文發(fā)送完畢由于一次添加令牌不夠還清所欠令牌，所以造成了短暫的丟包現(xiàn)象，而在前17s內(nèi)丟包率僅為1/17≈5.9%。

(2) 突發(fā)流量處理：方式二在突發(fā)流量處理方面優(yōu)于方式一。

由圖10可知，對(duì)方式一來說，由于令牌桶總的容量只有1 000 kb，發(fā)送完每條報(bào)文后桶中剩余令牌數(shù)都為0。此時(shí)若有突發(fā)流量，則報(bào)文必然被丟棄。而方式二令牌數(shù)可為負(fù)，當(dāng)突發(fā)報(bào)文到達(dá)時(shí)即使令牌數(shù)不足仍可通過欠債方式現(xiàn)將報(bào)文轉(zhuǎn)發(fā)出去，后續(xù)再償還債務(wù)。

(3) 大小包混合時(shí)：方式一可能會(huì)造成大包始終得不到轉(zhuǎn)發(fā)，而方式二則不會(huì)。

如果發(fā)送一長(zhǎng)度大于1 000 kb的報(bào)文，方式一中則始終會(huì)由于令牌不足而丟棄報(bào)文，方式二則可以通過借債方式現(xiàn)轉(zhuǎn)發(fā)報(bào)文后償還債務(wù)。

(4) 數(shù)據(jù)流發(fā)送過程平緩程度：方式二數(shù)據(jù)處理的時(shí)間較長(zhǎng)，所以趨勢(shì)明顯比方式一平緩。

3.2 雙速率三色算法的實(shí)現(xiàn)

3.2.1 桶的構(gòu)成

雙速率三色算法的實(shí)現(xiàn)，目前業(yè)界的實(shí)現(xiàn)基本上完全依照RFC的規(guī)定，用兩個(gè)令牌桶來實(shí)現(xiàn)，兩個(gè)令牌桶的容量不同，第一個(gè)是CBS，第二個(gè)是PBS。

3.2.2 令牌添加

雙速率三色標(biāo)記算法中兩桶添加令牌的速率不同，CBS桶添加令牌的速率是CIR，PBS桶添加令牌的速率則是PIR。添加令牌時(shí)先添加CBS桶，CBS桶填滿后再添加PBS桶。

3.2.3 報(bào)文處理流程

當(dāng)發(fā)送連續(xù)流量時(shí)，先看報(bào)文速率是否超過PIR：當(dāng)報(bào)文速率大于PIR時(shí)，超過PBS部分流量無法得到令牌，被標(biāo)記為紅色報(bào)文；未超過PBS而從PBS桶中獲取令牌的報(bào)文標(biāo)記為黃色報(bào)文；從CBS桶中獲取令牌的報(bào)文被標(biāo)記為綠色報(bào)文。當(dāng)報(bào)文速率小于PIR，大于CIR時(shí)，報(bào)文不會(huì)得不到令牌，但會(huì)超過CBS部分報(bào)文將從PBS桶中獲取令牌，被標(biāo)記為黃色報(bào)文；其他報(bào)文將從CBS桶中取令牌，被標(biāo)記為綠色報(bào)文；當(dāng)報(bào)文速率小于CIR時(shí)，報(bào)文所需令牌數(shù)不會(huì)超過CBS，所以只會(huì)被標(biāo)記為綠色報(bào)文。

當(dāng)發(fā)送突發(fā)報(bào)文時(shí)，若突發(fā)流量大于PBS，則超出部分統(tǒng)計(jì)為紅色報(bào)文；當(dāng)突發(fā)流量大于CBS，但小于PBS時(shí)，則超過CBS部分標(biāo)記為黃色報(bào)文；當(dāng)突發(fā)流量小于CBS時(shí)，全部標(biāo)記為綠色報(bào)文。

在流量控制中，用戶可針對(duì)不同顏色的報(bào)文設(shè)定不同行為，如；允許通過、丟棄、或重新標(biāo)記優(yōu)先級(jí)等。

3.3 單速率三色算法與雙速率三色算法的比較

單、雙速率三色標(biāo)記算法的比較如表1所示。

單速率三色標(biāo)記算法采用單桶或雙桶結(jié)構(gòu)，令牌添加方式和報(bào)文處理流程比較簡(jiǎn)單；雙速率三色記算法采用雙桶結(jié)構(gòu)，令牌添加方式和報(bào)文處理流程相對(duì)復(fù)雜。前者關(guān)注報(bào)文尺上的突發(fā)，后者關(guān)注速率上的突發(fā)，兩者各有優(yōu)點(diǎn)。

4 結(jié)束語

相對(duì)雙速率三色標(biāo)記算法而言，單速率三色標(biāo)記算法由于實(shí)現(xiàn)簡(jiǎn)單等原因，成為目前業(yè)界比較常用流量標(biāo)記方式。但不同的實(shí)現(xiàn)方式?jīng)Q定了其具有一定的性能差異，合理的采用借債方式可以彌補(bǔ)其在丟包率、突發(fā)流量處理性能、大小包混合轉(zhuǎn)發(fā)性能、數(shù)據(jù)轉(zhuǎn)發(fā)平緩程度等性能方面的不足，但當(dāng)存在較大速率的突發(fā)流量時(shí)，單速率三色標(biāo)記算法的借債機(jī)制將不能較好的改善性能問題，所以單速率三色標(biāo)記算法不能完全取代雙速率三色表算法。在實(shí)際應(yīng)用中，應(yīng)針對(duì)不同的流量特征選擇恰當(dāng)?shù)臉?biāo)記方式。

5 參考文獻(xiàn)：

[1] 何寶宏. IP網(wǎng)絡(luò)的服務(wù)質(zhì)量講座: 第4講 IP網(wǎng)絡(luò)流量與擁塞控制技術(shù)[J]. 中國(guó)數(shù)據(jù)通信， 2003， 5(5): 96-99.

[2] Heinanen J， Guerin R. IETF RFC 2697: A single rate three color marker[R]. Philadelphia， PA， USA: University of Pennsylvania， 1999.

[3] Heinanen J， Guerin R. IETF RFC 2698: A two rate three color marker[R]. Philadelphia， PA， USA: University of Pennsylvania， 1999.

[4] 李建寶， 桑海. 令牌桶算法在IP QoS中的應(yīng)用[J]. 華南金融電腦， 2006， 14 (4): 98-99.

[5] QoS技術(shù)白皮書[EB/OL].

http: //www.huawei-3com.com.cn/.

收稿日期：2007-04-03