計算機網路中的令牌桶演算法是什麼？

令牌桶演算法是擁塞控制演算法的一種技術。當網路中存在過多的資料包時，會導致資料包延遲和資料包丟失，從而降低系統性能。這種情況稱為擁塞。

網路層和傳輸層共同負責處理擁塞。控制擁塞的最有效方法之一是嘗試減少傳輸層對網路的負載。為了維護網路，網路層和傳輸層必須協同工作。

令牌桶演算法的示意圖如下所示：

流量過大時，效能會急劇下降。

令牌桶演算法

漏桶演算法以平均速率強制執行輸出模式，無論流量有多繁忙。因此，為了處理更多流量，我們需要一個靈活的演算法，以便資料不會丟失。令牌桶演算法就是其中一種方法。

讓我們逐步瞭解此演算法，如下所示：

• **步驟 1** - 定期將令牌投入桶 f 中。

• **步驟 2** - 桶具有最大容量 f。

• **步驟 3** - 如果資料包已準備就緒，則從桶中取出一個令牌，併發送資料包。

• **步驟 4** - 假設如果桶中沒有令牌，則無法傳送資料包。

示例

讓我們透過一個示例來了解令牌桶演算法：

在圖 (a) 中，桶包含兩個令牌，並且三個資料包正在等待從介面傳送出去。

在圖 (b) 中，透過消耗兩個令牌傳送了兩個資料包，還有一個數據包仍然存在。

與漏桶相比，令牌桶演算法限制較少，這意味著它允許更多流量。繁忙的限制受特定時間點桶中可用令牌數量的限制。

令牌桶演算法的實現很簡單：使用一個變數來計數令牌。每隔 t 秒，計數器就會遞增，然後在每次傳送資料包時遞減。當計數器達到零時，將不再發送任何其他資料包。

這在下面的圖中顯示：

Bhanu Priya

更新於：2023 年 9 月 2 日

72K+ 次檢視

開啟你的職業生涯

透過完成課程獲得認證

開始