漏桶算法(Leaky Bucket)是網路世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經常使用的一種算法，它的主要目的是控制數據注入到網路的速率，平滑網路上的突發流量。漏桶算法提供了一種機制，通過它，突發流量可以被整形以便為網路提供一個穩定的流量。
基本介紹
概述,基本內容,概念理解,套用實例,優點,實現原理,漏桶算法和令牌桶算法的區別,
概述
漏桶可以看作是一個帶有常量服務時間的單伺服器佇列，如果漏桶（包快取）溢出，那么數據包會被丟棄。
在網路中，漏桶算法可以控制連線埠的流量輸出速率，平滑網路上的突發流量，實現流量整形，從而為網路提供一個穩定的流量。
基本內容
* 漏桶算法強制一個常量的輸出速率而不管輸入數據流的突發性。當輸入空閒時，該算法不執行任何動作；
* 當數據包具有相同尺寸的時候（例如ATM信元），每個時間片傳輸一個數據包的工作機制沒有任何問題。但對於可變包長，這種工作機制可能存在一點問題，此時，最好每個時間片傳輸固定數目的位元組。例如：如果每個時間片傳輸1024位元組，那么一個時間片允許傳輸一個1024位元組的包，兩個512位元組的包，或者四個 256位元組的包；
概念理解
* 漏桶最多可以排隊b個位元組，漏桶的這個尺寸受限於有效的系統記憶體。如果數據包到達的時候漏桶已經滿了，那么數據包應被丟棄；
* 數據包從漏桶中漏出，以常量速率（r位元組/秒）注入網路，因此平滑了突發流量。
在流量整形中還存在另外一個流行的算法：令牌桶算法（Token Bucket）。有時人們將漏桶算法與令牌桶算法錯誤地混淆在一起。而實際上，這兩種算法具有截然不同的特性並且為截然不同的目的而使用。它們之間最主要的差別在於：漏桶算法能夠強行限制數據的傳輸速率，而令牌桶算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
在某些情況下，漏桶算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的參數，所以，即使網路中不存在資源衝突（沒有發生擁塞），漏桶算法也不能使某一個單獨的流突發到連線埠速率。因此，漏桶算法對於存在突發特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發特性的流量。通常，漏桶算法與令牌桶算法可以結合起來為網路流量提供更大的控制。
套用實例
在ATM網路的交換層，漏桶算法可以用來實現CBR業務。當數據流量超過協商速率一段時間後，漏桶（快取）將會溢出。這時需要檢查每一個信元中的信元丟失優先權（CLP）欄位，低優先權的信元將會被丟棄並被原始傳送設備重新傳輸。
優點
*信源可以容易地保證它的通信量符合標準；
*網路可以容易地驗證通信量是否符合規範；
*網路可以保證嚴格的延遲界限，避免一切由緩衝區溢出引起的丟失；
*由於服務質量根據嚴格的界限說明，用戶能夠驗證網路是否提供了請求的服務質量。
實現原理
如下圖（b）所示，當主機接口向網路中傳送數據包時，可採取漏桶算法，使得接口輸出數據流的速率恆定。
- 輸出不規則數據流的主機類似灌水的水龍頭
- 算法中定義的漏桶類似水桶
- 不規則數據流輸入漏桶類似向漏桶中灌水
流量輸出漏桶類似漏桶漏水
接下來，詳細分解一下漏桶算法在數據包傳送過程中的實現原理。
1、佇列接收到準備轉發的數據包。
2、佇列被調度，得到轉發機會。由於佇列配置了流量整形，佇列中的數據包首先進入漏桶中。
3、根據數據包到達漏桶的速率與漏桶的輸出速率關係，確定數據包是否被轉發。
如果到達速率≤輸出速率，則漏桶不起作用。
如果到達速率>輸出速率，則需考慮漏桶是否能承擔這個瞬間的流量。
1） 若數據包到達的速率-漏桶流出的速率≤配置的漏桶突發速率，則數據包可被不延時的送出。
2） 若數據包到達的速率-漏桶流出的速率>配置的漏桶突發速率，則多餘的數據包被存儲到漏桶中。暫存在漏桶中的數據包在不超過漏桶容量的情況下延時發出。
3） 若數據包到達的速率-漏桶流出的速率>配置的漏桶突發速率，且數據包的數量已經超過漏桶的容量，則這些數據包將被丟棄。
漏桶算法和令牌桶算法的區別
漏桶算法與令牌桶算法在表面看起來類似，很容易將兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。漏桶算法與令牌桶算法的區別在於：
l 漏桶算法能夠強行限制數據的傳輸速率。
l 令牌桶算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
需要說明的是：在某些情況下，漏桶算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的，所以即使網路中沒有發生擁塞，漏桶算法也不能使某一個單獨的數據流達到連線埠速率。因此，漏桶算法對於存在突發特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發特性的流量。通常，漏桶算法與令牌桶算法結合起來為網路流量提供更高效的控制。
