Cisco IOS 管制器和整形器使用Token Bucket算法建模。本質(zhì)上，令牌桶算法是測(cè)量引擎，跟蹤能夠發(fā)送多少流量來(lái)證實(shí)指定的流量速率。關(guān)于令牌桶的算法有三種技術(shù)，單速率雙色，單速率三色，雙速率三色機(jī)制。其中單速率雙色是對(duì)單速率三色的邏輯描述。
1. 單速率三色標(biāo)記(a single rate three color marker)
IETF RFC 2697定義了單速率三色標(biāo)記算法，評(píng)估依據(jù)以下3個(gè)參數(shù)：承諾訪問(wèn)速率(CIR)，即向令牌桶中填充令牌的速率；承諾突發(fā)尺寸(CBS)，即令牌桶的容量，每次突發(fā)所允許的最大流量尺寸（注：設(shè)置的突發(fā)尺寸必須大于最大報(bào)文長(zhǎng)度）；超額突發(fā)尺寸(EBS)。單速率三色標(biāo)記關(guān)注的是數(shù)據(jù)包的尺寸突發(fā)。

單速率三色機(jī)制有兩個(gè)令牌桶。任何CBS中未使用的令牌都放入第二個(gè)桶，用作以后臨時(shí)突發(fā)可能超過(guò)CIR的信用證。因此第二個(gè)桶的大小為第一個(gè)桶中未使用的令牌數(shù)加第二個(gè)桶的大小。可以做如下的理解：
一個(gè)數(shù)據(jù)包A大小為B，我們記為A(B)
if A(B)<TC
then (the packet conform,and the CBS size=TC‐B+TE)
else if B>TC and B<TE
then (the packet exceed,and the CBS size=TE)
else (The packet violate)
正常情況下，不會(huì)使用第二個(gè)桶測(cè)量，之所以把未使用的CBS的令牌放入第二個(gè)桶就是為后面數(shù)據(jù)的突發(fā)提供信用令牌數(shù)。

IEEE RFC定義了三種顏色，分別是紅色，黃色，綠色。因此三色由此而來(lái)。我們可以理解為交通燈。綠燈行，黃燈要注意了，應(yīng)該減慢速度準(zhǔn)備停車，而紅燈為等車。但將數(shù)據(jù)包標(biāo)記為這三種顏色的一種時(shí)，可以定義相應(yīng)的策略，比如：轉(zhuǎn)發(fā)，丟棄，設(shè)置優(yōu)先級(jí)等等。
對(duì)于顏色的判斷，RFC也定義了兩個(gè)模式，一種是色盲模式(Color‐Blind)，一種是非色盲模式(Color‐Aware)。這兩種模式處理的方式稍有不同。下面分別討論(使用程序設(shè)計(jì)的思想來(lái)描述)：
A：色盲模式(Color‐Blind)
Packets size(PS)
if PS<TC
then (The packets bepaint GREEN,Conform)
else if PS>TC and PS<TE
then (The packets bepaint YELLOW,Exceed)
else then (The packets bepaint RED,Violate)
B: 非色盲模式(Color‐Aware)
Packets size(PS)
if PS<TC or (The packets has bepainted GREEN)
then (The packets bepaint GREEN,Conform)
else if (PS>TC and PS<TE) or (The packets has bepainted YELLOW)
then (The packets bepaint YELLOW,Exceed)
else PS>TE or (The packets has bepainted RED)
then (The packets bepaint RED,Violate)

從上圖可以看出來(lái)，僅僅在第一個(gè)桶有未使用完的令牌放入到第二個(gè)桶的情況下，才允許臨時(shí)的數(shù)據(jù)突發(fā)。
2. 雙速率三色標(biāo)記(a two rate three color marker)
IETF RFC 2687定義了雙速率三色標(biāo)記，主要是根據(jù)4種流量參數(shù)來(lái)評(píng)估：CIR、CBS、峰值信息速率(PIR)，峰值突發(fā)尺寸(PBS)。前兩種參數(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。雙速率三色標(biāo)記關(guān)注的是速率的突發(fā)。它不在像單速率三色標(biāo)記那樣把第一個(gè)未使用的令牌放到第二個(gè)桶中。雙速率三色標(biāo)記使用兩個(gè)獨(dú)立的令牌桶。第一個(gè)桶為PIR大小為PBS，第二個(gè)桶為CIR大小為CBS。數(shù)據(jù)的測(cè)量是先比較PIR，然后再比較CIR(換句話說(shuō)，雙速率三色標(biāo)記首先判斷的是違約情況，最后是正常情況)，雙速率三色標(biāo)記的突發(fā)速率可以根據(jù)以下的公式計(jì)算出來(lái)
PIR=CIR(1+BE/BC)
我們不可能改變接口的物理時(shí)鐘，但是可以利用TDMA(時(shí)分多路復(fù)用)來(lái)講接口劃分為亞秒級(jí)的時(shí)間片,每一個(gè)時(shí)間間隔我們都可以定義相應(yīng)的數(shù)據(jù)傳遞大小，如下圖:

正常情況下我們?cè)谝粋€(gè)TC中能傳遞BC大小數(shù)據(jù)，而剩下的TC‐(BC/link BW)的時(shí)間保持靜默，如果有突發(fā)流量，僅僅能利用剩下的TC‐(BC/link BW)時(shí)間來(lái)傳遞(默認(rèn)Cisco IOS TC=125ms)。如下圖所示：

下圖是雙速率三色標(biāo)記的處理流程：

同樣RFC定義了兩個(gè)模式，色盲模式(Color‐Blind),非色盲模式(Color‐Aware),下面分別討論(使用程序設(shè)計(jì)思想描述)：
A: 色盲模式(Color‐Blind)
Packets Size(PS)
if PS>TP
then (The packets bepaint RED,Violate)
else if PS<TP and PS>TC
then (The packets bepaint YELLOW,Exceed)
else PS<TC
then (The packets bepaint GREEN,Conform)
B: 非色盲模式(Color‐Blind)
if PS>TP or (The packets has bepainted RED)
then (The packets bepaint RED,Violate)
else if (PS<TP and PS>TC) or (The packets has bepainted YELLOW)
then (The packets bepaint YELLOW,Exceed)
else PS<TC or (The packets has bepainted GREEN)
then (The packets bepaint GREEN,Conform)

3. 令牌桶的實(shí)現(xiàn)方式①
A.單速率三色標(biāo)記算法的實(shí)現(xiàn)
a.桶的構(gòu)成
在令牌桶的構(gòu)成上，目前業(yè)界有兩種方式，可以由一個(gè)桶實(shí)現(xiàn)，即C桶是E桶中的一部分，最終桶的容量是由EBS決定的。不管有沒(méi)有突發(fā)流量，EBS不能為0，必須大于或等于CBS。這種實(shí)現(xiàn)方式完全按照令牌桶的定義來(lái)實(shí)現(xiàn)，因?yàn)镃BS和EBS都是令牌桶的參數(shù)，所以放入一個(gè)相同的桶實(shí)現(xiàn)，通過(guò)突發(fā)計(jì)數(shù)器來(lái)進(jìn)行區(qū)分。也可以由兩個(gè)桶實(shí)現(xiàn)，即C桶和E桶分開(kāi)實(shí)現(xiàn)。如果不允許有突發(fā)流量，EBS則設(shè)置成0。
b.令牌添加
令牌桶的添加完全依照RFC規(guī)定實(shí)現(xiàn)，按照恒定的速率CIR添加。即每隔1/CIR時(shí)間添加一個(gè)令牌，添加順序?yàn)橄忍砑覥桶再添加E桶，當(dāng)令牌桶添加滿的時(shí)候，再產(chǎn)生的令牌就會(huì)被丟棄。實(shí)際中比較常見(jiàn)的有兩種實(shí)現(xiàn)方式：(1)周期性的添加，添加的時(shí)間間隔就是令牌桶的容量與添加速率的比值：Tc=CBS/CIR，每次添加的令牌數(shù)為CBS 個(gè)；(2)一次性添加，只有當(dāng)令牌桶中沒(méi)有令牌時(shí)才添加令牌，添加令牌的數(shù)量是△t×CIR(△t是當(dāng)前時(shí)間與上次添加令牌的時(shí)間之差)，且是一次添加完畢，并不是按照一定速率添加。
c.報(bào)文處理流程
當(dāng)報(bào)文到來(lái)后，直接與桶中的令牌數(shù)相比較，如果有足夠的令牌就轉(zhuǎn)發(fā)，如果沒(méi)有足夠的令牌則丟棄或緩存。這種令牌桶處理方式在突發(fā)流量的處理上沒(méi)有優(yōu)勢(shì)，也就是說(shuō)當(dāng)存在較大的突發(fā)流量時(shí)，令牌桶可能會(huì)由于沒(méi)有足夠令牌無(wú)法處理報(bào)文，而且在沒(méi)有突發(fā)流量且報(bào)文到達(dá)速率較大時(shí)，報(bào)文處理流程也不連續(xù)，有時(shí)會(huì)因?yàn)榱钆茢?shù)量不足而造成丟包。為解決這種無(wú)謂的丟包問(wèn)題，目前業(yè)界采用了一種借貸機(jī)制的報(bào)文處理方法。當(dāng)報(bào)文到來(lái)后，只要令牌桶中有令牌，無(wú)論數(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ù)性。
c.實(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。
分析數(shù)據(jù)的處理流程得出以下結(jié)論：
(1) 數(shù)據(jù)包丟棄率：方式二的丟包率遠(yuǎn)小于方式一。
方式一中，由于令牌添加周期與報(bào)文發(fā)送周期的不一致，導(dǎo)致第6 s到第8 s由于沒(méi)有令牌不能轉(zhuǎn)發(fā)報(bào)文。而第8 s到第16 s雖然在不斷添加令牌，但令牌數(shù)不足以轉(zhuǎn)發(fā)一個(gè)報(bào)文，所以仍舊無(wú)法轉(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ā)送過(guò)程中的丟包率也為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ì)方式一來(lái)說(shuō)，由于令牌桶總的容量只有1 000 kb，發(fā)送完每條報(bào)文后桶中剩余令牌數(shù)都為0。此時(shí)若有突發(fā)流量，則報(bào)文必然被丟棄。而方式二令牌數(shù)可為負(fù)，當(dāng)突發(fā)報(bào)文到達(dá)時(shí)即使令牌數(shù)不足仍可通過(guò)欠債方式現(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)文，方式二則可以通過(guò)借債方式現(xiàn)轉(zhuǎn)發(fā)報(bào)文后償還債務(wù)。

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

B. 雙速率三色算法的實(shí)現(xiàn)
a. 桶的構(gòu)成
雙速率三色算法的實(shí)現(xiàn)，目前業(yè)界的實(shí)現(xiàn)基本上完全依照RFC的規(guī)定，用兩個(gè)令牌桶來(lái)實(shí)現(xiàn)，兩個(gè)令牌桶的容量不同，第一個(gè)是CBS，第二個(gè)是PBS。
b. 令牌添加
雙速率三色標(biāo)記算法中兩桶添加令牌的速率不同，CBS桶添加令牌的速率是CIR，PBS桶添加令牌的速率則是PIR。添加令牌時(shí)先添加CBS桶，CBS桶填滿后再添加PBS桶。
c. 報(bào)文處理流程
當(dāng)發(fā)送連續(xù)流量時(shí)，先看報(bào)文速率是否超過(guò)PIR：當(dāng)報(bào)文速率大于PIR時(shí)，超過(guò)PBS部分流量無(wú)法得到令牌，被標(biāo)記為紅色報(bào)文；未超過(guò)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ì)超過(guò)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ì)超過(guò)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í)，則超過(guò)CBS部分標(biāo)記為黃色報(bào)文；當(dāng)突發(fā)流量小于CBS時(shí)，全部標(biāo)記為綠色報(bào)文。
在流量控制中，用戶可針對(duì)不同顏色的報(bào)文設(shè)定不同行為，如；允許通過(guò)、丟棄、或重新標(biāo)記優(yōu)先級(jí)等。

4. 單速率三色算法與雙速率三色算法的比較
單速率三色標(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)。
相對(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ī)制將不能較好的改善性能問(wèn)題，所以單速率三色標(biāo)記算法不能完全取代雙速率三色表算法。在實(shí)際應(yīng)用中，應(yīng)針對(duì)不同的流量特征選擇恰當(dāng)?shù)臉?biāo)記方式