了解流量監管和×××的關鍵算法—令牌桶
無論是流量監管還是流量×××都提到一個超額流量的問題，而前面已經描述了監管和×××對超額流量的處理方式不同，監管丢棄或者重标記，流量×××是緩存，通過加大延遲的方式發送平滑的資料流量，那麼網絡裝置怎麼去确定這個超額流量，難道鍊路的帶寬為512K，而此時使用者以每秒768KB/s發送資料，使用768-512就256KB,難道超額的流量就是256KB嗎？不是的，這樣做是一種錯誤的了解，要确定使用者的超額流量必須使用如下兩種算法中的一種來确定，一種叫漏桶算法（leaky bucket algorithm）另一種叫令牌桶算法（token bucket algorithm），而思科在流量監管和×××時使用的是令牌桶算法，為什麼思科會選擇令牌桶算法，下面開始來了解：
漏桶算法（leaky bucket algorithm）
漏桶算法（leaky bucket algorithm）是一種不支援任何資料突發量的算法，為了更好的了解漏桶算法，如圖所示，它好比一個底部呈現一個漏孔，然後裝滿水的桶，而桶的底部有一個恒定大小的漏孔，由于漏孔的大小是是恒定的，是以無論桶上方的水龍頭以多大的注水量向桶中注水，水通過漏孫向外洩漏的速率永遠是一樣的，算法不會因為桶中的水快被溢出而瞬間将桶中的水洩漏完之後，再繼續盛水。在這個比喻中桶中的水就好比是資料，水龍頭好比是使用者發送資料的速率，而桶底部的漏孔比如是流量×××或者監管的速率。
注意：在上面的描述中隻是為了更好的了解漏桶算法，因為該算未能不并是需要描述的重點，大家隻需要記住這樣這個原則：因為漏桶算法隻能以恒定速率輸送資料，不支援任持續突發和最大突發，是以在流量管理中不使用漏桶算法，而是後面将要描述的令牌桶算法。
令牌桶算法（token bucket algorithm）或叫令牌漏桶算法
如圖所示：其實令牌桶的底部也有一個“漏洞”這一點是乎和漏桶非常相似，是以令牌桶還有另一個名命叫“令牌漏桶（本章節至此以後統稱它為令牌桶）”但是它與一般所指的正常漏洞有實質上的差別，令牌桶裡面裝載的是令牌，然後讓令牌去關聯到資料發送，正常漏桶裡面裝載的是資料，令牌桶允許使用者的正常的持續突發量（Bc），就是一次就将桶裡的令牌全部用盡的方式來支援續突發，而正常的漏桶則不允許使用者任何突發行。而令牌桶的算法分為“單桶”和“雙桶”算法，那現在首先來了解單桶算法。
令牌桶中的令牌如何去關聯到資料發送
在令牌桶算法中，隻有拿到令牌的資料才能被發送，反之則不能，假設一個令牌可以發送1bit（比特）的資料，那麼要發6個bit的資料就需要拿到六個令牌，當拿到令牌的資料被發送後，該令牌就從桶中移除。換句話說桶中有多少令牌就能發送多少資料。如上圖所示，一共有6個資料需要被發送，桶中有四個令牌，那麼就能發送4個資料。在圖示環境中剩下的2個資料因為沒有多餘的令牌可用它們将不被發送。
令牌桶算法如何判斷超額流量以及如何向令牌桶中加入令牌
簡單的講，如果令牌桶中沒有可用的令牌，那麼在這個時刻到來的所有資料流量都是超額流量。如下圖所示，至于超額的流量怎麼處理，它可能被監管丢棄，也可能被×××所緩存，但這不是這裡讨論的重點，在實驗部分會重點讨論丢棄和緩存的效果。至此為止，大家應該清晰的知道使用令牌去關聯資料并發送的過程了，令牌除了會從桶中移除以後，算法還會每隔一個的周期不斷的向桶中加入令牌，關鍵加入令牌的速率是多少？是什麼時候（間隔時間周期）加入令牌？然後加多少令牌到桶中？這些問題被三個關鍵因素所決定，它們是：CIR（承諾資訊速率）、Tc（時間周期）、Bc（持續突發量）。
CIR（承諾資訊速率）：這個速率就是向令牌桶中加入令牌的速度，機關是bits persecond每秒多少個比特，一般情況下，會将這個速率配置成與認購的合同速率相比對。比如：雖然您的接入速率可能有128K，但是認購速率為64K，那麼就應該把CIR配置為64K。
Tc（時間間隔）：承諾的持續突發（Bc）間隔時間，也是讓令牌桶充滿令牌的時間隔，它的機關是毫秒（ms），這個Tc間隔是不能手工配置的，通常思科會假設這個Tc為125ms。它能被CIR和Bc通過公式計算而得到。
Bc（持續突發量）：它實際上定義了令牌桶的容量，或者這樣講更容易了解，它就是在一個Tc時間時隔内允許使用者一次耗盡桶中所有令牌的數量，以比特（bit）為機關。
流量監管和×××必須了解的重要公式：Bc = Tc * CIR
假設現在需要将一個（接入速度是128K）的鍊路，流量×××為承諾資訊速率64K，那麼該連接配接的持續突發量Bc是多少？很簡單此時隻需要使用思科預設的Tc(125ms)即0.125s乘以64000bit/s即得到8000bits的持續突發量Bc。同樣的道理，如果已經知道了CIR和Bc就可以通過公式來計算出Tc。但是請始終注意一個問題：Tc是不可以手工配置的。能手工配置的隻有CIR和Bc，而且思科建議隻配置CIR，其它的參數，比如Bc，都讓系統去自動計算完成。是以在上述的三個參數中最重要的還是CIR。
注意：有些時候讀者在參看一些外文書籍或者參資料時，這個CIR也叫×××後的目标速率（Target Rate）或者叫×××速率（Shaped Rate），但其核心意思都一樣：往令牌桶中加入令牌的速率。是以公式Bc = Tc * CIR等同于Bc = Tc * Target rate也等同于Bc = Tc * Shaped Rate。但是這有一個前提：就是你×××後的目标速率或者叫×××速率必須與承諾資訊速率相同。但是在一些特殊案例中，當使用者想獲得高于CIR的資料發送速率時，可以将上述後兩個公式中的Target rate 和Shaped Rate适當設定得更高些。
了解令牌桶算法支援使用者的持續突發行為，為什麼叫Bc為“持續”突發？
事實上，在單令牌桶的算法中，使用者的持續突發量被Bc所決定的，Bc也代表令牌桶的容量，所謂突發行為是指：允許使用者一次用完令牌桶中的所有令牌，那麼如何展現“持續”突發的特點呢？持續突發是指間隔一個Tc時間，令牌桶中的令牌會被再次充滿，然後使用者可以再次用盡令牌桶中的所有令牌，也就是說這個突發行為是可以持續進行的，會在間隔Tc的時間周期上反複充滿桶中的令牌同時又不斷釋放桶中的令牌，而不是在整個流量的較長時間發送過程中的瞬間行為。
流量×××到底是如何将接入速率（AR）轉化為認購速率？
比如說接入速率（也就是實體時鐘頻率工作在128K），而認購速率也就是CIR隻有64K，流量×××是如何将這個接入速率128K×××成與CIR相比對的64K的？在回答這個問題前首先得弄明白一個不可争義的事實：如果接入速率工作在128K通常這個速率被時鐘頻率所決定，請注意在任何時候該接口都隻會以128K的速率發送資料，就接口本身而言它是決不可能自己将發送速率降緻64K的，但是它可以采取一種機制，把1秒鐘（1s）拿來平均化成N個以毫秒（ms）組成的時間間隔，然後一些間隔時間不讓其發送資料，能發送的時間間隔，接口還是以128K的速率來發送，如圖所示：就是将128K的接入速率×××為64K的認購速率（也就是CIR），假設配置令牌桶的深度（Bc）8000比特，因為Tc=Bc/CIR,是以就會産生8000除以64000等于0.125s(125ms)的時間間隔，那麼8個125ms就是1秒，是以現在以125ms為基礎，劃分8個時間間隔。然後接口仍然将以128K來發送資料，因為這是不可改變的事實，目前令牌桶的深度(Bc)是8000比特，如果以128K來發送資料，那麼8000除以128000等于62.5ms就完成資料發送了（正好是125ms的一半），但是此時由于令牌桶中的令牌耗盡，令牌耗盡就代表資料無法拿到令牌，無法拿到令牌就無法發送資料。是以在125ms的時間間隔中的另一半時間（後62.5ms），資料發送将被抑制，不能發送，直到125ms間隔周期到來，令牌桶又被充滿，然後再次耗盡它，然後重複的執行這個過程。是以從一秒鐘這個角度來看，雖然接口以128K發送，但是有500ms發送都被抑制，實際上就每秒就等于64K的發送率。最後就能得到如圖所示的×××情況：
通過上面的描述應該能了解單桶流量×××的工作機制了，現在需要進一步提出一個問題：如果使用者有長時間沒有發送資料，或者發送的資料低于令牌桶的容量（也就是不耗盡Bc中的令牌），那麼新産生入桶的令牌會發生什麼情況？
了解雙令牌桶算法：
如果隻有一個令牌桶(Bc)，那麼當使用者發送的資料低于令牌桶的容量（也就是不耗盡Bc中的令牌），新産生入桶的令牌會充滿令牌桶，當桶已經被充滿時，多餘的令牌将被丢棄，這意味着使用者的整個突發量隻能維持在Bc之内。不能存在有高過持續突發的超額突發（或者我更喜歡稱呼超額突發為瞬間突發）。為了突破這個限制，現在在令牌桶算法中引入雙桶機制，如圖所示，第一個令牌桶通常被稱為桶1也叫Bc或者叫持續突發桶；第二個令牌桶通常叫桶2也叫Be或者叫瞬間突發桶。雙桶算法遵守如下重要原則：
1 算法不會直接向桶2産生并加入令牌
2 隻有當桶1被填充滿載時，從桶1溢出的令牌将被放入到桶2
3 不能保證桶2在每個時間間隔被充滿令牌，這被桶1溢出多少令牌到桶2有關。
4 但是如果桶2也被滿載，那麼多餘的令牌将被丢棄
根據上述的原則當引入桶2（Be）後，如果使用者發送資料時，他将獲得比單桶算法更大的突發量，因為流量耗盡了桶1（Bc）的令牌後，算法讓會讓流量去使用桶2（Be）中的令牌，是以此時使用者的資料突發量将等于Bc+Be。但是在流量×××過程中Bc和Be到底可以配置成多少bits，建議這樣的原則：将使用者獲得ISP的認購合同書上的CIR速率配置到流量×××中，讓系統自行去計算最合理的Bc和Be，并不建議使用者通過人工的方式去配置Bc和Be，×××系統的Bc可以通過Tc*CIR獲得，而Be和Bc在數學上是不存在必然的關系的。思科一般會将Be的大小自動配置為和Bc相同。舉一個例子來說明，如圖所示為将接入速率128K×××為64K，Bc=8000bits, Be=8000bits,是以圖中的流量突發會多一個Be的瞬間突發流量（如箭頭所訓示的那一部分），為什麼Be隻有那麼一瞬間的突發量，而不能持續，因為算法從來都不會向Be直接加入令牌，Be隻能收集被Bc溢出的令牌，如果使用者一直以持續的高于64K的速率來發送資料，那麼Bc就根本不會有令牌溢出，它将被反複的充滿又耗光，然後又充滿，然後又耗光，那麼就不會有多是餘的令牌溢出到桶2(Be)中，是以被允許的Be叫瞬間突發，一般隻出現在資料初始發送的第一個時間時隔内，因為隻有此時的Bc和Be的令牌都是滿桶，還有就是出現在使用者以低于CIR的速率在發送資料，隻有這個時候桶2（Be）才有機會被充滿。
注意差別持續突發和瞬間突發的差異：
持續突發是指Bc，所謂持續是指它可以每隔一個Tc間隔，就能将Bc的令牌全部用完，這意味着這個行為是可以反複持續的進行的，它與CIR和Tc存在必然的數學關系，通常是Bc=CIR*Tc，而瞬間突發或者叫超額突發是指Be，它不能被持續進行，能執行瞬間突發的一個唯一條件就是Bc的令牌已經滿了，有令牌溢出到Be，當完成一次突發後，耗完Be的令牌後，如果一直沒有令牌從Bc溢出到Be那麼就不能在進行瞬間突發行為，是以它隻是瞬間。
流量×××的配置及單雙桶的确認
以GTS（通用流量×××）為例，預設情況下建議隻配置CIR，系統自動計算Bc和Be，系統會使用雙桶算法（同時使用Bc和Be），具體如下所示：
關于流量×××的配置說明：
R1(config)#inte s1/0
R1(config-if)#traffic-shape rate 64000 * 配置流量×××到每秒64Kbps
R1(config-if)#exit
上述配置就僅是配置了×××的CIR，讓系統去确定Bc和Be，當完成配置後，可以通過show traffic-shape來檢視流量×××的各項配置參數，如圖所示，目前的配置是将接入速率×××到64K，桶1(Bc)=8000bits=1000bytes；該參數是系統根據64000/bps(CIR)*0.125s(Tc)=8000bits所得到的。Tc思科預設是125ms。同時系統啟動了雙桶算法，将桶2（Be）配置成為與桶1（Bc）相同的大小8000bits。是以現在第一個時間時隔的突發量就是Bc+Be=16000bits，換成以位元組為機關就是16000除以8等于2000byte。
手工配置Bc并申明使用單桶機制：
R1(config)#intes1/0
R1(config-if)#traffic-shaperate 64000 8000 0
* 整到CIR64K，手工配置桶1（Bc）為8000bits，手工配置桶2（Be）為0，由于Be被配置為0，這就申明目前流量×××隻使用單桶算法，具體如圖所示。