漏桶算法

漏桶可以看作是一個帶有常量服務時間的單服務器隊列，如果漏桶（包緩存）溢出，那麼數據包會被丟棄。

在網絡中，漏桶算法可以控制端口的流量輸出速率，平滑網絡上的突發流量，實現流量整形，從而為網絡提供一個穩定的流量。

* 漏桶算法強制一個常量的輸出速率而不管輸入數據流的突發性。當輸入空閒時，該算法不執行任何動作；

* 主機在每一個時間片向網絡注入一個數據包，因此產生了一致的數據流，平滑了突發的流量；

* 當數據包具有相同尺寸的時候（例如ATM信元），每個時間片傳輸一個數據包的工作機制沒有任何問題。但對於可變包長，這種工作機制可能存在一點問題，此時，最好每個時間片傳輸固定數目的字節。例如：如果每個時間片傳輸1024字節，那麼一個時間片允許傳輸一個1024字節的包，兩個512字節的包，或者四個 256字節的包；

* 到達的數據包（網絡層的PDU）被放置在底部具有漏孔的桶中（數據包緩存）；

* 漏桶最多可以排隊b個字節，漏桶的這個尺寸受限於有效的系統內存。如果數據包到達的時候漏桶已經滿了，那麼數據包應被丟棄；

* 數據包從漏桶中漏出，以常量速率（r字節/秒）注入網絡，因此平滑了突發流量。

在流量整形中還存在另外一個流行的算法：令牌桶算法（Token Bucket）。有時人們將漏桶算法與令牌桶算法錯誤地混淆在一起。而實際上，這兩種算法具有截然不同的特性並且為截然不同的目的而使用。它們之間最主要的差別在於：漏桶算法能夠強行限制數據的傳輸速率，而令牌桶算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。

在某些情況下，漏桶算法不能夠有效地使用網絡資源。因為漏桶的漏出速率是固定的參數，所以，即使網絡中不存在資源衝突（沒有發生擁塞），漏桶算法也不能使某一個單獨的流突發到端口速率。因此，漏桶算法對於存在突發特性的流量來説缺乏效率。而令牌桶算法則能夠滿足這些具有突發特性的流量。通常，漏桶算法與令牌桶算法可以結合起來為網絡流量提供更大的控制。

在ATM網絡的交換層，漏桶算法可以用來實現CBR業務。當數據流量超過協商速率一段時間後，漏桶（緩存）將會溢出。這時需要檢查每一個信元中的信元丟失優先級（CLP）字段，低優先級的信元將會被丟棄並被原始發送設備重新傳輸。

*信源可以容易地保證它的通信量符合標準；

*網絡可以容易地驗證通信量是否符合規範；

*網絡可以保證嚴格的延遲界限，避免一切由緩衝區溢出引起的丟失；

*由於服務質量根據嚴格的界限説明，用户能夠驗證網絡是否提供了請求的服務質量。

如下圖（b）所示，當主機接口向網絡中傳送數據包時，可採取漏桶算法，使得接口輸出數據流的速率恆定。

流量輸出漏桶類似漏桶漏水

接下來，詳細分解一下漏桶算法在數據包傳送過程中的實現原理。

1、隊列接收到準備轉發的數據包。

2、隊列被調度，得到轉發機會。由於隊列配置了流量整形，隊列中的數據包首先進入漏桶中。

3、根據數據包到達漏桶的速率與漏桶的輸出速率關係，確定數據包是否被轉發。

如果到達速率≤輸出速率，則漏桶不起作用。

如果到達速率>輸出速率，則需考慮漏桶是否能承擔這個瞬間的流量。

1） 若數據包到達的速率-漏桶流出的速率≤配置的漏桶突發速率，則數據包可被不延時的送出。

2） 若數據包到達的速率-漏桶流出的速率>配置的漏桶突發速率，則多餘的數據包被存儲到漏桶中。暫存在漏桶中的數據包在不超過漏桶容量的情況下延時發出。

3） 若數據包到達的速率-漏桶流出的速率>配置的漏桶突發速率，且數據包的數量已經超過漏桶的容量，則這些數據包將被丟棄。

漏桶算法與令牌桶算法在表面看起來類似，很容易將兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。漏桶算法與令牌桶算法的區別在於：

l 漏桶算法能夠強行限制數據的傳輸速率。

l 令牌桶算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。

需要説明的是：在某些情況下，漏桶算法不能夠有效地使用網絡資源。因為漏桶的漏出速率是固定的，所以即使網絡中沒有發生擁塞，漏桶算法也不能使某一個單獨的數據流達到端口速率。因此，漏桶算法對於存在突發特性的流量來説缺乏效率。而令牌桶算法則能夠滿足這些具有突發特性的流量。通常，漏桶算法與令牌桶算法結合起來為網絡流量提供更高效的控制。