漏桶算法(Leaky Bucket)是網路世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經常使用的一種算法，它的主要目的是控制數據注入到網路的速率，平滑網路上的突發流量。漏桶算法提供了一種機制，通過它，突發流量可以被整形以便為網路提供一個穩定的流量。漏桶可以看作是一個帶有常量服務時間的單伺服器佇列，如果漏桶（包快取）溢出，那么數據包會被丟棄。
基本介紹
- 中文名：漏桶算法
- 外文名：leaky bucket
- 性質：算法
- 目的：控制數據注入到網路的速率
基本內容,套用實例,
基本內容
* 漏桶算法強制一個常量的輸出速率而不管輸入數據流的突發性。當輸入空閒時，該算法不執行任何動作；
* 主機在每一個時間片向網路注入一個數據包，因此產生了一致的數據流，平滑了突發的流量；
* 當數據包具有相同尺寸的時候（例如ATM信元），每個時間片傳輸一個數據包的工作機制沒有任何問題。但對於可變包長，這種工作機制可能存在一點問題，此時，最好每個時間片傳輸固定數目的位元組。例如：如果每個時間片傳輸1024位元組，那么一個時間片允許傳輸一個1024位元組的包，兩個512位元組的包，或者四個 256位元組的包；
在概念上，漏桶算法可以作如下理解：
* 到達的數據包（網路層的PDU）被放置在底部具有漏孔的桶中（數據包快取）；
* 漏桶最多可以排隊b個位元組，漏桶的這個尺寸受限於有效的系統記憶體。如果數據包到達的時候漏桶已經滿了，那么數據包應被丟棄；
* 數據包從漏桶中漏出，以常量速率（r位元組/秒）注入網路，因此平滑了突發流量。
在流量整形中還存在另外一個流行的算法：令牌桶算法（Token Bucket）。有時人們將漏桶算法與令牌桶算法錯誤地混淆在一起。而實際上，這兩種算法具有截然不同的特性並且為截然不同的目的而使用。它們之間最主要的差別在於：漏桶算法能夠強行限制數據的傳輸速率，而令牌桶算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
在某些情況下，漏桶算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的參數，所以，即使網路中不存在資源衝突（沒有發生擁塞），漏桶算法也不能使某一個單獨的流突發到連線埠速率。因此，漏桶算法對於存在突發特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發特性的流量。通常，漏桶算法與令牌桶算法可以結合起來為網路流量提供更大的控制。
