漏桶算法(Leaky Bucket)是网络世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)时经常使用的一种算法,它的主要目的是控制数据注入到网络的速率,平滑网络上的突发流量。漏桶算法提供了一种机制,通过它,突发流量可以被整形以便为网络提供一个稳定的流量。
漏桶可以看作是一个带有常量服务时间的单服务器队列,如果漏桶(包缓存)溢出,那么数据包会被丢弃。
漏桶算法的基本内容如下:
* 漏桶算法强制一个常量的输出速率而不管输入数据流的突发性。当输入空闲时,该算法不执行任何动作;
* 主机在每一个时间片向网络注入一个数据包,因此产生了一致的数据流,平滑了突发的流量;
* 当数据包具有相同尺寸的时候(例如ATM信元),每个时间片传输一个数据包的工作机制没有任何问题。但对于可变包长,这种工作机制可能存在一点问题,此时,最好每个时间片传输固定数目的字节。例如:如果每个时间片传输1024字节,那么一个时间片允许传输一个1024字节的包,两个512字节的包,或者四个 256字节的包;
在概念上,漏桶算法可以作如下理解:
* 到达的数据包(网络层的PDU)被放置在底部具有漏孔的桶中(数据包缓存);
* 漏桶最多可以排队b个字节,漏桶的这个尺寸受限于有效的系统内存。如果数据包到达的时候漏桶已经满了,那么数据包应被丢弃;
* 数据包从漏桶中漏出,以常量速率(r字节/秒)注入网络,因此平滑了突发流量。
在流量整形中还存在另外一个流行的算法:令牌桶算法(Token Bucket)。有时人们将漏桶算法与令牌桶算法错误地混淆在一起。而实际上,这两种算法具有截然不同的特性并且为截然不同的目的而使用。它们之间最主要的差别在于:漏桶算法能够强行限制数据的传输速率,而令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。
在某些情况下,漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使某一个单独的流突发到端口速率。因此,漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常,漏桶算法与令牌桶算法可以结合起来为网络流量提供更大的控制。
漏桶算法的应用实例:
在ATM网络的交换层,漏桶算法可以用来实现CBR业务。当数据流量超过协商速率一段时间后,漏桶(缓存)将会溢出。这时需要检查每一个信元中的信元丢失优先级(CLP)字段,低优先级的信元将会被丢弃并被原始发送设备重新传输。
分享到:
相关推荐
经典限流算法-窗口算法、漏桶算法、令牌桶算法
漏桶算法 Leaky Bucket 是网络世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)时经常使用的一种算法 它的主要目的是控制数据注入到网络的速率 平滑网络上的突发流量 漏桶算法提供了一种机制 通过它 ...
四大常用限流算法原理详解:计数器固定窗口、计数器滑动窗口、漏桶、令牌桶算法.pdf
在分布式系统中,应对高并发访问时,缓存、限流、降级是保护系统正常运行的常用方法。当请求量突发暴涨时,如果不加以限制访问,则可能导致整个系统崩溃,服务不可用。同时有一些业务场景,比如短信验证码,或者其它...
ratelimit 基于令牌桶算法和漏桶算法来实现的限速限流,Golang实现
系统在运行过程中,如遇上某些活动,访问的人数会在一瞬间内爆增,导致服务器瞬间压力飙升,使系统超...本文介绍php基于redis,使用令牌桶算法,实现访问流量的控制,提供完整算法说明及演示实例,方便大家学习使用。
1. 概述 2. 计数器 3. 漏桶算法 4. 令牌桶算法 5. 漏桶算法与令牌桶算法区别
流量控制算法(限流算法)主要有:漏桶算法:平滑输入流量,控制进入网络的流量令牌桶算法:当大的突发流量到来时,输出也能有适当响应漏桶算法漏桶算法思路很简单,请求先
通常有以下两种限流方案:漏桶算法令牌桶算法漏桶算法漏桶算法非常简单,就是将流量放入桶中并按照一定的速率流出。令牌桶算法令牌桶算法是按照恒定的速率向桶中放入令牌,
限流是对某一时间窗口内的请求数进行限制,保持...常用的限流算法有令牌桶和和漏桶,而Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法。 在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流
1.漏桶算法熔断限流可以保证外部系统稳定性 建议用于访问外部系统存在系统瓶颈,有限流等情况 2.令牌桶算法熔断限流可以保证内部系统稳定性 建议用于外部系统访问内部系统,内部系统存在瓶颈,性能问题等情况 3.固定...
1.漏桶算法熔断限流可以保证外部系统稳定性 建议用于访问外部系统存在系统瓶颈,有限流等情况 2.令牌桶算法熔断限流可以保证内部系统稳定性 建议用于外部系统访问内部系统,内部系统存在瓶颈,性能问题等情况 3.固定...
3. 漏桶算法 4 令牌桶算法(`常用`) Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法 二、 分布式限流 1、网关层(Nginx、Openresty、Spring Cloud Gateway等)流量限制 nginx限流 Spring Cloud Gateway...
限流器的算法比较多,常见的比如令牌桶算法、漏斗算法、信号量等。本文主要介绍基于漏斗算法的一个限流器的实现。文本也提供了其他几种开源的实现方法。 基于令牌桶的限流器实现 在golang 的官方扩展包 time 中...
漏桶流算法和令牌桶算法知道?Nginx配置高可用性怎么配置?Nginx怎么判断别P不可访问? 在nginx中,如何使用未定义的服务器名称来阻止处理请求? 怎么限制浏览器访问? Rewrite全局变量是什么? Nginx如何实现后端服务的...
高并发系统有三把利器:缓存、降级和限流; 限流的目的是通过对并发访问/请求进行限速来保护系统,一旦达到...最简单粗暴的限流算法就是计数器法了,而比较常用的有漏桶算法和令牌桶算法; 1.1计数器 计数器法是限流
一个关键的设计决定在于算法本身的选择:漏桶算法,令牌桶算法的一种变体。 之所以选择它,是因为与令牌桶相比,它的实现相对简单。 在其中,每个由其API密钥标识的用户都将获得一个包含10个“滴”或请求的“桶”。...
根据控制器攻击状态来确定用户的可信度,采用令牌漏桶算法的流控思想,降低请求队列溢出的概率,降低队列的拥塞程度。采用加权的轮询调度策略,根据用户可信度和请求数量计算每次应该转发的请求数目。通过在SDN 环境...
常见的技术包括令牌桶算法、漏桶算法等,确保系统的稳定性和可用性。 2. **缓存优化和数据预热**:秒杀系统通常会使用缓存技术,如将商品信息、库存和用户状态等数据提前加载到缓存中。使用缓存可以有效减轻数据库...