什么是计算机网络中的令牌桶算法？

令牌桶算法是拥塞控制算法的技术之一。当网络中存在太多数据包时，会导致数据包延迟和数据包丢失，从而降低系统性能。这种情况称为拥塞。

网络层和传输层共同负责处理拥塞。控制拥塞的最有效方法之一是尝试减少传输层对网络施加的负载。为了维护这个网络和传输层必须一起工作。

令牌桶算法用图表表示如下 -

流量过多，性能急剧下降。

令牌桶算法

漏桶算法以平均速率强制输出模式，无论流量多么繁忙。所以，为了处理更多的流量，我们需要一个灵活的算法，让数据不丢失。一种这样的方法是令牌桶算法。

让我们逐步理解这个算法，如下所示 -

• 第 1 步- 定期将令牌扔到桶 f 中。

• 第 2 步- 存储桶的最大容量为 f。

• Step 3 - 如果数据包准备好，则从桶中删除一个令牌，然后发送数据包。

• Step 4 - 假设如果桶中没有令牌，则无法发送数据包。

示例

让我们通过一个例子来理解令牌桶算法 -

在图(a)中，桶里有两个令牌，三个数据包正在等待从接口发出。

在图(b)中，通过消耗两个令牌已经发送了两个数据包，还剩下一个数据包。

与漏桶相比，令牌桶算法限制较少，这意味着它允许更多流量。繁忙度的限制受特定时刻桶中可用令牌的数量的限制。

令牌桶算法的实现很简单——使用一个变量来计算令牌。对于每 t 秒，计数器递增，然后每当发送数据包时递减。当计数器达到零时，不再发送数据包。

这如下图所示 -