令牌桶算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制傳送到網路上的數據的數目，並允許突發數據的傳送。
基本介紹
- 中文名：令牌桶算法
簡介,令牌桶工作參數,標記器,分類,
簡介
在網路中傳輸數據時，為了防止網路擁塞，需限制流出網路的流量，使流量以比較均勻的速度向外傳送。令牌桶算法就實現了這個功能，可控制傳送到網路上數據的數目，並允許突發數據的傳送。
令牌桶算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制傳送到網路上的數據的數目，並允許突發數據的傳送。
大小固定的令牌桶可自行以恆定的速率源源不斷地產生令牌。如果令牌不被消耗，或者被消耗的速度小於產生的速度，令牌就會不斷地增多，直到把桶填滿。後面再產生的令牌就會從桶中溢出。最後桶中可以保存的最大令牌數永遠不會超過桶的大小。
傳送到令牌桶的數據包需要消耗令牌。不同大小的數據包，消耗的令牌數量不一樣。
令牌桶這種控制機制基於令牌桶中是否存在令牌來指示什麼時候可以傳送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許傳送流量；而如果令牌桶中不存在令牌，則不允許傳送流量。因此，如果突發門限被合理地配置並且令牌桶中有足夠的令牌，那么流量就可以以峰值速率傳送。
令牌桶算法的基本過程如下：
假如用戶配置的平均傳送速率為r，則每隔1/r秒一個令牌被加入到桶中；
假設桶最多可以存發b個令牌。如果令牌到達時令牌桶已經滿了，那么這個令牌會被丟棄；
當一個n個位元組的數據包到達時，就從令牌桶中刪除n個令牌，並且數據包被傳送到網路；
如果令牌桶中少於n個令牌，那么不會刪除令牌，並且認為這個數據包在流量限制之外；
算法允許最長b個位元組的突發，但從長期運行結果看，數據包的速率被限制成常量r。對於在流量限制外的數據包可以以不同的方式處理：
它們可以被丟棄；
它們可以排放在佇列中以便當令牌桶中累積了足夠多的令牌時再傳輸；
它們可以繼續傳送，但需要做特殊標記，網路過載的時候將這些特殊標記的包丟棄。
注意：令牌桶算法不能與另外一種常見算法“漏桶算法（Leaky Bucket）”相混淆。這兩種算法的主要區別在於“漏桶算法”能夠強行限制數據的傳輸速率，而“令牌桶算法”在能夠限制數據的平均傳輸速率外，還允許某種程度的突發傳輸。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允許突發地傳輸數據直到達到用戶配置的門限，因此它適合於具有突發特性的流量。
令牌桶工作參數
工作過程包括3個階段：產生令牌、消耗令牌和判斷數據包是否通過。其中涉及到2個參數：令牌產生的速率CIR（Committed Information Rate）/EIR（Excess Information Rate）和令牌桶的大小CBS（Committed Burst Size）/EBS（Excess Burst Size）。下面用圖形簡要概括一下這3個階段與2個參數的關係。
- 產生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不斷增多。如果桶中令牌數已到達CBS/EBS，則丟棄多餘令牌。
- 消耗令牌：輸入數據包會消耗桶中的令牌。在網路傳輸中，數據包的大小通常不一致。大的數據包相較於小的數據包消耗的令牌要多。
- 判斷是否通過：輸入數據包經過令牌桶後的結果包括輸出的數據包和丟棄的數據包。當桶中的令牌數量可以滿足數據包對令牌的需求，則將數據包輸出，否則將其丟棄。
標記器
業務量的計量和標記主要是套用在區分服務體系機構中，計量器的功能主要是根據該業務量相關的流量規範來計量和檢驗業務量的流量特性，判斷是否與流量規範一直，是否遵守約定的流量規範，計量的依據就是該業務分組流的流量規範，標記器對每一個經過計量的IP分組進行標記，這個標記被作為網路在以後按標記處理給分組的依據，在區分服務體系結構中，對分組的標記是該分組設定與服務類型相應的DSCP值。
計量與標記功能是協作完成的，計量的結果傳給標記器，作為標記的依據。一般標記器就指的是兩種功能的結合，其組成如圖，
標記器有兩種分類標記方法，一種是按顏色的不同進行分類標記，有雙色標記和三色標記；另一種是按實現機制分類，有基於令牌桶的標記、基於速率的標記和基於策略的標記。
分類
基於令牌桶的典型標記器有多種算法實現方案，基本算法主要有IN/OUT公平標記器（FM）和三色標記器（TCM），擴展的算法主要有單速率三色標記器（srTCM）和雙速率三色標記器（trTCM）。其中單速率標記器和雙速率標記器已分別稱為IETF的標準建議。
IN/OUT 公平標記器（FM）
FM是一種雙色單令牌桶標記器，它的Tspec是系統的分組平均速錄為R，允許的突發度為B，工作原理就是當IP分組到達時若桶中有足夠的令牌，則將符合Tspec的分組標記為IN；若此時沒有足夠的令牌，則認為該到達分組不符合Tpsec，不符合Tpsec的分組將被標記為OUT，網路將可能對這些被標記為不同屬性的分組依據相應的策略進行不同的處理。
單速率三色標記器（srTCM）
srTCM是一種三色雙令牌桶標記器，它的Tpsec有三個參數：承諾信息速率，承諾突發尺寸和超額突發尺寸。CIR的單位是bps，CBS及EBS的單位是Byte。
srTCM由兩個令牌桶C和E組成，它們的CIR相同，容量則分別為CBS和EBS，C桶記憶體放黃色令牌，開始時令牌桶C與E都是滿的。進入的分組沒有超過CBS就標記為綠色；超過了CBS而沒有超過EBS就標記為黃色；否則標記為紅色。在DiffServ中，紅、黃、綠可映射為不同的DSCP值。
雙速率標記器（trTCM）
trTCM也是一種三色雙令牌桶標記器，它的Tpsec有4個參數：峰值信息速率（PIR）、峰值突發尺寸（PBS）、承諾信息速率（CIR）和承諾突發尺寸（CBS）。PIR和CIR的單位是bps，PBS和CBS的單位是Byte。
