QoS技术中令牌桶算法实现方式比较

Date ：2009­3­7 Author: Bay Wei Keywords: Cisco;QoS Token Bucket; ;a singl e rate three color marker;a two rate three col or marker;traffic policingIn this document apart from Cisco all other contents remain the owners of the posted materials. Please respect the author's intellectual property rights; documentation is limited to studying and exchange of use. It is strictly prohibited the use of my documentation for commercial activities, identified by one, will be held accountable by law.Cisco IOS 管制器和整形器使用Token Bucket 算法建模。

本质上，令牌桶算法是测量引擎，跟踪能够发送多少流量来证实指定的流量速率。

关于令牌桶的算法有三种技术，单速率双色，单速率三色，双速率三色机制。

其中单速率双色是对单速率三色的逻辑描述。

1. 单速率三色标记(a single rate three color marker)IETF RFC 2697定义了单速率三色标记算法，评估依据以下3个参数：承诺访问速率(CIR)，即向令牌桶中填充令牌的速率；承诺突发尺寸(CBS)，即令牌桶的容量，每次突发所允许的最大流量尺寸（注：设置的突发尺寸必须大于最大报文长度）；超额突发尺寸(EBS)。

单速率三色标记关注的是数据包的尺寸突发。

摘要：令牌桶算法是目前IP QoS中最常采用的一种流量测量方法，广泛应用于约定访问速率技术、通用流量整形技术以及物理接口总速率限制等技术中。

IETF RFC 建议规范了单速率三色标记和双速率三色标记两种令牌桶算法，在桶的构成、令牌添加和报文处理流程方面前者较后者简单，成为目前业界比较常用的流量标记方式。

在实际应用中，应针对不同的流量特征选择恰当的标记方式。

关键词：令牌桶；单速率三色标记；双速率三色标记；流量监管Abstract:The token bucket algorithm is the most popular method of traffic measuring in IP QoS technology. It has been widely used in Committed Access Rate (CAR), Generic Traffic Shaping (GTS), and Line Rate (LR) technologies. Two kinds of token bucket algorithms—a single rate three color marker and a two rate three color marker—have been recommended in the Internet Engineering Task Force (IETF) Request for Comment (RFC) documents. In view of the bucket architecture, the token adding, and the packet process, the single rate three color marker is easier than the two rate one. For practical applications, different traffic characteristics choose different algorithm.Key words:token bucket; a single rate three color marker; a two rate three color marker; traffic policing随着因特网的发展，IP业务不断快速增长。

CISCO IOS管制器和整形器使用信令牌桶算法建模。

本质上令牌桶算法是测量引擎，跟踪能够发送多少流量来证实指定的流量速率。

在进行流量控制时，CISCO IOS有三种方式可以实现，分别是单速率双色、单速率三色和双速率三色。

1.单速率双色（单桶）在CISCO IOS中的此种典型配置就是CAR在此种算法中，使用单个令牌桶的机制。

在这里有几个关键的参数。

CIR—承诺访问速率，即向令牌桶放入令牌的速率Bc—承诺突发，即令牌桶的大小Be—过量突发，在标准的单速率双色算法中，BE=BCTc—算法所考察的时间间隔上面几个参数符合如下关系：CIR=Bc/Tc配置时，在CISCO IOS中，只能设置CIR和Bc，Tc会自动算出Tc的意义为值越小，设备考察的时间间隔越小，即控制越精细，在工程中Tc一般要小于125ms此算法的实现方式为在Tc时间内，一个令牌桶刚好被填满，这时通过的数据包向令牌桶借令牌：当数据包大小<=令牌数量，则认为此流量为承诺流量，执行conform-action当数据包大小>令牌数量，则认为此流量为过量流量，执行exceed-action 此算法双色由此而来。

在下一个Tc内，继续重复上面的操作2.单速率双色（双桶）policers突破了前面管制器的所有缺点，在控制流量的精度上极大地增强。

该管制器的工作逻辑为：policers 管制器使遥了单速率三色和双桶算法。

第一个桶中任何未用的令牌都被放入第二个令牌桶中，用做以后临时突发可能超过CIR的信用证，放置在第二个桶中的令牌供应被称为过量突发（BE），当BC满的时候（第一个桶），令牌的数量被放置在桶里（第二个桶），当BC未满时，第二个桶包含了第一个桶未用的令牌。

BE 是可以超过突发大小的最大位数。

3.双速率三色单速率三色和双桶基于RFC 2697来定义，而双速率三色双桶基于RFC 2698来定义。

在单速率三色双桶中，它为临时流量突发提供信用量，但是，过量突发信用量积累数量的变化会引起流量流到某种程度的不可预测性，为了改进这一点，所以出现了双速率三色双桶。

令牌桶限流算法令牌桶限流算法令牌桶算法是⼀个桶，匀速向桶⾥放令牌，控制桶最⼤容量（令牌最⼤数）和放⼊令牌速率（⽣成令牌/秒）。

所有的请求在处理之前都需要拿到⼀个可⽤的令牌才会被处理，如果桶⾥⾯没有令牌的话，则拒绝服务；接⼝限制 t 秒内最⼤访问次数为 n，则每隔 t/n 秒会放⼀个 token 到桶中；桶中最多可以存放 b 个 token，如果 token 到达时令牌桶已经满了，那么这个 token 会被丢弃；接⼝请求会先从令牌桶中取 token，拿到 token 则处理接⼝请求，拿不到 token 则执⾏限流；当⼀个n个字节的数据包到达时，就从令牌桶中删除n个令牌（不同⼤⼩的数据包，消耗的令牌数量不⼀样），并且数据包被发送到⽹络；Rate limiting Spring Boot with bucket4j每分钟10个限流，每分钟10个速度放⼊令牌tokenRefill refill = Refill.intervally(10, Duration.ofMinutes(1));Bandwidth limit = Bandwidth.classic(10, refill);Bucket bucket = Bucket4j.builder().addLimit(limit).build();for (int i = 1; i <= 10; i++) {assertTrue(bucket.tryConsume(1));}assertFalse(bucket.tryConsume(1));Use Spring MVC Interceptorpublic class RateLimitInterceptor implements HandlerInterceptor {@Autowiredprivate PricingPlanService pricingPlanService;@Overridepublic boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object handler)throws Exception {String apiKey = request.getHeader("X-api-key");if (apiKey == null || apiKey.isEmpty()) {response.sendError(HttpStatus.BAD_REQUEST.value(), "Missing Header: X-api-key");return false;}String url = request.getRequestURI();Bucket tokenBucket = pricingPlanService.resolveBucket(apiKey+"-"+url);ConsumptionProbe probe = tokenBucket.tryConsumeAndReturnRemaining(1);if (probe.isConsumed()) {response.addHeader("X-Rate-Limit-Remaining", String.valueOf(probe.getRemainingTokens()));return true;} else {long waitForRefill = probe.getNanosToWaitForRefill() / 1_000_000_000;response.addHeader("X-Rate-Limit-Retry-After-Seconds", String.valueOf(waitForRefill));response.sendError(HttpStatus.TOO_MANY_REQUESTS.value(),"You have exhausted your API Request Quota");return false;}}}public class PricingPlanService {private final Map<String, Bucket> cache = new ConcurrentHashMap<>();public Bucket resolveBucket(String apiKey) {return puteIfAbsent(apiKey, this::newBucket);}private Bucket newBucket(String apiKey) {PricingPlan pricingPlan = PricingPlan.resolvePlanFromApiKey(apiKey);return Bucket4j.builder().addLimit(pricingPlan.getLimit()).build();}}public enum PricingPlan implements BandwidthFactory {FREE(){@Overridepublic Bandwidth getLimit() {return Bandwidth.classic(20, Refill.intervally(20, Duration.ofHours(1)));}},BASIC(){@Overridepublic Bandwidth getLimit() {return Bandwidth.classic(40, Refill.intervally(40, Duration.ofHours(1)));}},PROFESSIONAL(){@Overridepublic Bandwidth getLimit() {return Bandwidth.classic(100, Refill.intervally(100, Duration.ofHours(1)));}};}@SpringBootConfigurationpublic class AppConfig implements WebMvcConfigurer {@Autowiredprivate RateLimitInterceptor interceptor;@Overridepublic void addInterceptors(InterceptorRegistry registry) {registry.addInterceptor(interceptor).addPathPatterns("/api/v1/area/**");}}@PostMapping("/api/v1/area/rectangle3")public ResponseEntity<AreaV1> rectangle3(@RequestHeader(value = "X-api-key") String apiKey, @RequestBody RectangleDimensionsV1 dimensions) {return ResponseEntity.ok().body(new AreaV1("rectangle", dimensions.getLength() * dimensions.getWidth()));}发起测试请求curl -v -X POST http://localhost:8071/api/v1/area/rectangle3 \-H "Content-Type: application/json" -H "X-api-key:FX001-99999" \-d '{ "length": 10, "width": 12 }'每⼩时20个token，剩余19个token可⽤。

qos单速三色法原理QoS单速三色法原理引言：在网络通信中，QoS（Quality of Service，服务质量）是指网络中传输数据的质量保证机制。

在实际应用中，为了满足不同数据流的传输要求，需要对网络中的数据流进行分类和控制。

而QoS单速三色法就是一种常用的数据流分类和控制机制。

本文将介绍QoS单速三色法的原理及其在网络中的应用。

一、QoS单速三色法的原理QoS单速三色法是一种基于令牌桶算法的流量控制方法，用于对网络中的数据流进行分流和限速。

1.1 令牌桶算法令牌桶算法是一种常用的流量控制算法，它基于令牌桶的概念。

令牌桶中以固定的速率产生令牌，数据包只有在获取到令牌时才能被发送出去。

如果令牌桶中没有令牌，则数据包需要等待，直到令牌桶中产生了足够的令牌。

1.2 单速三色法QoS单速三色法是在令牌桶算法的基础上，结合三种颜色进行数据流的分类和控制。

这三种颜色分别为绿色（Green）、黄色（Yellow）和红色（Red）。

绿色：表示网络中的数据流处于正常传输状态，速率在允许范围内。

黄色：表示网络中的数据流接近超出允许的速率范围，但尚未达到丢弃的阈值。

红色：表示网络中的数据流已经超出了允许的速率范围，需要进行丢弃或降速处理。

1.3 工作原理QoS单速三色法通过使用三个令牌桶来对数据流进行分类和控制。

数据包进入绿色令牌桶，如果绿色令牌桶中有足够的令牌，则数据包被发送出去，并从绿色令牌桶中消耗一个令牌。

如果绿色令牌桶中没有足够的令牌，则数据包进入黄色令牌桶。

黄色令牌桶允许的速率较低，如果黄色令牌桶中有足够的令牌，则数据包被发送出去，并从黄色令牌桶中消耗一个令牌。

如果黄色令牌桶中也没有足够的令牌，则数据包进入红色令牌桶。

红色令牌桶的速率最低，如果红色令牌桶中有足够的令牌，则数据包被发送出去，并从红色令牌桶中消耗一个令牌。

如果红色令牌桶中也没有足够的令牌，则数据包被丢弃或降速处理。

二、QoS单速三色法的应用QoS单速三色法在网络通信中有广泛的应用，常见的应用场景包括：2.1 互联网服务提供商（ISP）ISP需要对不同用户的网络流量进行分类和控制，以保证公平性和服务质量。

比较QoS服务策略的Bandwidth及Priority命令bandwidth 和priority 命令的比较具体来说，这两种命令均为匹配的数据包提供了带宽保证。

然而这两种命令在带宽保证的实现上存在很大的功能差异。

换句话说，这两种命令都能达到带宽保证的目的，但使用的队列技术是截然不同的。

也正因如此,这两个命令实质上是根据具体需要为保证不同性质的流量而分别设计的。

下表列出bandwidth及priority命令功能上的区别。

Bandwidth：保证最小带宽，但不限制最大带宽。

Priority：保证最小带宽，但也限制了最大带宽。

另外Bandwidth和priority这两条命令用于实现不同的QoS目标。

Bandwidth：常用于广域网链路带宽的质量保证，不具备对链路抖动、延时及响应时间的保证。

Priority：只是在某种程度上应用于广域网链路带宽的质量保证，具备链路延时、抖动及响应时间的保证。

Bandwidth和Priority命令都提供了最低带宽保证，但不同的是Priority 命令还实现了最大带宽保证，从内部实现来说，优先级队列（PQ）使用一种令牌桶算法，只有取得令牌的数据包才能被转发，通过令牌填入桶的速率控制数据包的平均传输速率。

根据令牌桶的容量还允许某种程度的突发传输。

在“令牌桶算法”中，只要令牌桶中存在剩余的令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。

当我们设置了priority值，也就类似于确定了令牌的填入速率，此时无论链路是否拥塞，超出的流量因无法获得令牌而被直接丢弃。

但是，在链路没有拥塞时，令牌桶中有多余的令牌，此时允许一定程度的突发流量，但不会超出priority设置的平均流量。

bandwidth使用加权公平排队(WFQ)作为底层算法实现带宽保证，通过此算法实现各个类的队列基于权值的公平调度，当接口中某些类别的报文没有时，BQ 队列的报文还可以公平地得到空闲的带宽，大大提高了线路的利用率，同时在接口拥塞的时候仍然能保证各类报文得到用户设定的最小带宽。

计算机网络的QoS保证技术计算机网络的发展已经成为我们生活不可或缺的一部分，人们对网络连接速度、可靠性和延迟等性能指标的要求也越来越高。

因此，保证网络服务质量（Quality of Service，QoS）成为了极为关键的问题。

本文将介绍计算机网络的QoS保证技术。

一、QoS的概念和重要性QoS是指计算机网络中对网络传输质量的要求和保证。

在传统的网络中，数据包的传输服务是按照”先到先得“的原则进行，即无论数据包的种类和重要性，都被平等对待。

在这种情况下，网络上的实时语音、视频、在线游戏等对实时性要求较高的应用会受到严重的影响，导致用户体验不佳。

为了解决这一问题，QoS技术应运而生。

QoS技术旨在通过优先级分类、流量控制和拥塞管理等手段，提高网络传输的稳定性和效率，保证关键应用的实时性和可靠性。

二、优先级分类技术优先级分类技术是QoS保证技术中的重要一环。

通过将不同类型的数据包进行优先级分类，网络设备可以对其进行不同的处理和调度，从而实现对关键应用或重要数据的优先传输。

常见的优先级分类技术有三个层次：流分类、服务类型分类以及应用优先级分类。

流分类是指将数据包按照流的特征进行分类，如源IP 地址、目的IP地址、端口号等；服务类型分类是根据IP数据包中的服务类型字段对其进行分类；应用优先级分类则是根据具体应用的特征进行分类。

三、流量控制技术流量控制技术是保证QoS的另一个关键因素。

流量控制技术通过控制传输数据的速率和数量，避免网络拥塞和资源浪费，提高网络传输的效率和可靠性。

最常见的流量控制技术是令牌桶算法和漏桶算法。

令牌桶算法中，令牌以固定速率产生，并存放在一个令牌桶中，如果数据包需要传输，则需要先从令牌桶中获取令牌，相当于获得了发送的许可；而漏桶算法则是通过固定的速率接收数据，并丢弃多余的数据，相当于控制了发送速率。

四、拥塞管理技术拥塞管理技术是QoS保证技术中的关键一环。

在高负载情况下，网络中的路由器和交换机可能会出现拥塞现象，导致网络传输的延迟和丢包率增加。

版本知识点之QOS(3)网络带宽的有限，使得我们不得不在网络中的流量进行管理，以便大家有序使用。

通常使用的技术有：流量监管和流量整形。

流量监管是通过监督进入网络的某一流量的规格，限制它在一个允许的范围之内，若某个连接的报文流量过大，就丢弃报文，或重新设置该报文的优先级（比如限制HTTP报文不能占用超过50%的网络带宽）流量整形是一种主动调整流量输出速率的措施。

其作用是限制流出某一网络的某一连接的流量与突发，使这类报文以比较均匀的速度向外发送。

通常会使用缓冲技术。

流量监管和整形大多用于区分服务的边缘设备上。

一、令牌桶算法：IE考试中整形和管制的概念以都是基于此算法，也是实际应用中最常见的一种算法！！！首先，根据预先设置的匹配规则来对报文进行分类。

如果是没有规定流量特性的报文，就直接继续发送，并不需经令牌桶的处理：如果是需要进行流量控制的报文，则会进入令牌桶中进行处理。

令牌桶算法的基本过程如下：1. 令牌桶按用户设定的速度向桶中放置令牌。

2.用户可以设置令牌桶的容量。

令牌到达时如令牌桶已经满了，则此令牌会被丢弃；3.当一个n字节的数据包到达时，就从令牌桶中删除n个令牌，且数据包被发送到网络；仅供学习参考，请勿用于商业活动~4.若令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外；对于在流量限制外的数据包可以以不同的方式处理：1.它们可以被丢弃；2.它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输；3.它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃。

参数解释如下：BC：承诺突发量，即一次性加进的令牌数量TC：向令牌桶中添加的令牌的时间周期，默认125ms，即1s要向令牌中放8次令牌。

CIR：承诺信息速率。

即每秒钟往桶里加的令牌的速率，这个速率也就决定了用户流量，这是一个平均量，可由公式：CIR=BC/TC得出。

令牌桶算法的三种模式：1.单速双色在单速双色的令牌桶算法中，只存在一个令牌桶，并且流量只会出现两种结果，即符合CIR （conform）和超出CIR（exceed）。