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

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

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

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

流量过大时，性能会急剧下降。

令牌桶算法

漏桶算法以平均速率强制执行输出模式，无论流量有多繁忙。因此，为了处理更多流量，我们需要一个灵活的算法，以便数据不会丢失。令牌桶算法就是其中一种方法。

让我们逐步了解此算法，如下所示：

• **步骤 1** - 定期将令牌投入桶 f 中。

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

• **步骤 3** - 如果数据包已准备就绪，则从桶中取出一个令牌，并发送数据包。

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

示例

让我们通过一个示例来了解令牌桶算法：

在图 (a) 中，桶包含两个令牌，并且三个数据包正在等待从接口发送出去。

在图 (b) 中，通过消耗两个令牌发送了两个数据包，还有一个数据包仍然存在。

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

令牌桶算法的实现很简单：使用一个变量来计数令牌。每隔 t 秒，计数器就会递增，然后在每次发送数据包时递减。当计数器达到零时，将不再发送任何其他数据包。

这在下面的图中显示：

Bhanu Priya

更新于：2023 年 9 月 2 日

72K+ 次查看

开启你的职业生涯

通过完成课程获得认证

开始