token bucket

令牌桶算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。

基本介紹

• 中文名：電子工程詞典
• 外文名：token bucket
• 算法：令牌桶算法
• 套用：網路流量整形速率限制等

簡介

電子工程詞典

Token Bucket

令牌桶算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制傳送到網路上的數據的數目，並允許突發數據的傳送。

令牌桶這種控制機制基於令牌桶中是否存在令牌來指示什麼時候可以傳送流量。令牌桶中的每一個令牌都代表一個位元組(對於流量整形來說代表一個bit，就traffic policing來講代表一個byte。參見CCIE Routing and Switching Official Exam Certification Guide 2nd Edition）。如果令牌桶中存在令牌，則允許傳送流量；而如果令牌桶中不存在令牌，則不允許傳送流量。因此，如果突發門限被合理地配置並且令牌桶中有足夠的令牌，那么流量就可以以峰值速率傳送。

基本過程

如下(圖)：

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

假設桶最多可以存發b個令牌。如果令牌到達時令牌桶已經滿了，那么這個令牌會被丟棄；

當一個n個位元組的數據包到達時，就從令牌桶中刪除n個令牌，並且數據包被傳送到網路；

如果令牌桶中少於n個令牌，那么不會刪除令牌，並且認為這個數據包在流量限制之外；

算法允許最長b個位元組的突發，但從長期運行結果看，數據包的速率被限制成常量r。對於在流量限制外的數據包可以以不同的方式處理：

它們可以被丟棄；

它們可以排放在佇列中以便當令牌桶中累積了足夠多的令牌時再傳輸；

它們可以繼續傳送，但需要做特殊標記，網路過載的時候將這些特殊標記的包丟棄。

注意：令牌桶算法不能與另外一種常見算法“漏桶算法（Leaky Bucket）”相混淆。這兩種算法的主要區別在於“漏桶算法”能夠強行限制數據的傳輸速率，而“令牌桶算法”在能夠限制數據的平均傳輸數據外，還允許某種程度的突發傳輸。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允許突發地傳輸數據直到達到用戶配置的門限，因此它適合於具有突發特性的流量。