令牌桶算法是什么？

令牌桶算法是一种流量控制方法。在这种方法中，令牌以固定的速率被添加到桶中（直到达到最大容量为止）。只有当有足够的令牌可用时，才能传输数据包。

• 控制进入网络的流量的平均发送速率。
• 在桶的容量范围内支持突发传输，同时又能遵守长期限制条件。
• 用于QoS、流量整形以及流量控制方面。

令牌桶算法的需求

“令牌桶”机制是必要的，因为固定速率限制会迫使流量以恒定的速度进行传输，而实际的网络流量则具有突发性。这种机制能够确保短期的流量峰值不会被阻塞，同时又能确保长期的带宽限制得到遵守。

• 网络具有有限的带宽，因此，无控制的流量会导致拥塞和数据包丢失。
• 真实的流量（包括网页访问、视频播放以及API调用等）是以突发的形式到达的，而不是以稳定的速度持续不断地到来。
• 固定速率限制器可能会在短暂的、合理的网络波动期间，延迟或丢弃数据包。
• 通常情况下，应用程序需要以高速方式发送数据，以保持其响应速度。
• 如果不受控制的话，无限制的发送数据可能会导致网络过载。
• 令牌桶算法通过平衡突发流量与长期平均速率来控制流量。

关键术语与参数

• 代币：传输数据需要获得许可；只有当有足够的令牌可用时，才能发送数据包。
• 铲子：这是一种逻辑存储方式，用于保存令牌，直到这些令牌被使用为止。
• 代币生成率 (r)：每秒钟添加的令牌数量；用于控制长期的发送速率。
• 铲斗容量（B）：桶可以存储的最大令牌数量；它定义了允许的最大突发大小。
• 代币消耗规则：令牌的扣除是基于传输的数据量来进行的。通常情况下，每字节传输的数据会对应一个令牌的扣除（有时则按每个数据包来计算）。具体数值取决于配置设置。

工作/运作

• 令牌以恒定的速率被添加到桶中，其添加速率为 r。这些令牌会被存储到桶的最大容量范围内，即 B 以内。
• 在空闲期间，代币会不断积累，从而为后续的快速传输提供条件。
• 当数据包到达时，系统会检查是否有足够的令牌可用。
• 如果有足够的令牌，那么这些令牌会被扣除，数据包也会立即被发送出去。
• 如果令牌不可用，那么该数据包将被延迟、排队或丢弃，直到有新的令牌生成为止。

令牌桶算法所涉及的步骤

桶的创建：定义了一个具有固定容量（速率限制）的逻辑桶，该桶表示其能够容纳的最大令牌数量。
2. 令牌补充：令牌会以恒定的速率被添加到桶中，直到该桶达到其最大容量为止。
3. 请求到达时间：当请求或数据包到达时，系统会检查是否有可用的令牌。
4. 令牌消耗：如果存在令牌的话，那么会移除其中一个令牌，从而允许请求继续进行。同时，还会记录下消耗令牌的时间。
5. 桶已空：如果没有剩余的令牌，那么传入的请求将被拒绝或延迟处理。这样就能避免系统过载，同时还能确保系统始终遵循既定的速率限制。

流动特性

Token Bucket主要负责管理带宽和流量速率，但它也会间接影响其他与网络性能相关的参数。

• 可靠性：它并非由 Token Bucket 直接控制；其可靠性主要由 TCP 等传输协议来保障。
• 延迟：通过调节交通流量，可以减少过度排队的情况，从而有助于降低传输延迟。
• 抖动：更顺畅的流量流动能够减少时间上的巨大波动，从而提升应用程序的实时性能。
• 带宽：它能够控制平均传输速率，同时允许有限的突发数据传输，从而有效防止网络出现突然的过载情况。

令牌桶算法与漏桶算法

令牌桶算法

漏桶算法

优点/优势

• 能够支持突发流量，同时还能保持长期稳定的平均传输速率。
• 通过限制交通流量随时间推移而不断增加的速率，从而减少突然的拥堵现象。
• 通过让未使用的资源能够在之后被重新利用，从而有效利用了带宽资源。
• 通过可调节的参数，如令牌率(r)和桶大小(B)，实现灵活的速率控制。
• 常用于QoS、流量整形以及流量控制中，以管理不同的流量类别。

缺点/不利因素

• 无法保证零数据包丢失，尤其是在网络拥塞严重时。
• 需要适当的缓冲/队列管理机制，以避免在令牌数量不足时出现掉线的情况。
• 如果网络已经处于繁忙状态，那么这些突发情况仍可能导致短期的拥塞或抖动现象。
• 需要正确调整令牌率(r)和桶大小(B)。如果数值设置错误，可能会导致性能下降或控制能力减弱。

应用程序/软件

• 被用于路由器和交换机中，以实施针对不同流量类别的QoS策略。
• 应用于交通疏导，以缓解出行的拥堵情况。
• 被互联网服务提供商用来执行用户带宽计划，从而防止某个用户独占网络资源。
• 在视频流传输和实时媒体传输中很常见，用于应对那些短暂且较高的比特率变化，而不会超出平均限制。
• 被用于云网络以及API中，用于限制访问频率、控制公平使用行为，同时防止流量突然增加所带来的问题。
• 示例：该令牌桶的配置如下：令牌的发送速率为 5 Mbps，而桶的容量为 10 MB。如果发送方保持闲置状态，那么令牌会不断积累，直到桶的容量达到上限。当发生突发数据传输时，发送方可以迅速传输最多 10 MB的数据（使用已存储的令牌）。一旦所有令牌被使用完，数据传输速度则继续以稳定的 5 Mbps 进行。