QoS技术中令牌桶算法实现方式比较
- 格式:doc
- 大小:732.50 KB
- 文档页数:9
Date :200937 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)。
摘要:令牌桶算法是目前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 T ask 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业务不断快速增长。
提高信息在IP网络上传输的质量是IP网发展中的一个关键所在。
IP QoS技术的开发,目的就是为用户业务提供端到端的服务质量保证,已成为近几年业界研究的热点。
目前存在多种IP QoS服务模型,其中应用最广的是区分服务模型(DiffServ)。
DiffServ模型通过数据包分类、拥塞管理、拥挤避免、速率限制和流量整形技术来实现服务质量控制,在其速率限制和流量整形中,主要使用了令牌桶算法来评估流量速率是否超过规定值[1]。
本文第一部分阐述了一下网络工程师任务小组(IETF) 请求注解(RFC)建议规范的两种令牌桶算法;第二部分简要介绍了令牌桶算法在IP QoS中的应用;第三部分详细说明了目前业界常用的两种实现方式,并对两种方式的实现过程进行了具体的比较分析。
1 令牌桶算法基本原理令牌桶是网络设备的内部存储池,而令牌则是以给定速率填充令牌桶的虚拟信息包。
每个到达的令牌都会从数据队列领出相应的数据包进行发送,发送完数据后令牌被删除。
RFC中定义了两种令牌桶算法——单速率三色标记算法和双速率三色标记算法,其评估结果都是为报文打上红、黄、绿三色标记。
QoS会根据报文的颜色,设置报文的丢弃优先级,其中单速率三色标记比较关心报文尺寸的突发,而双速率三色标记则关注速率上的突发,两种算法都可工作于色盲模式和非色盲模式。
以下结合这两种工作模式介绍一下RFC中所描述的这两种算法。
1.1 单速率三色标记算法IETF的RFC文件[2]定义了单速率三色标记算法,评估依据以下3个参数:承诺访问速率(CIR),即向令牌桶中填充令牌的速率;承诺突发尺寸(CBS),即令牌桶的容量,每次突发所允许的最大流量尺寸(注:设置的突发尺寸必须大于最大报文长度);超额突发尺寸(EBS)。
一般采用双桶结构:C桶和E桶。
Tc表示C桶中的令牌数,T e表示E桶中令牌数,两桶的总容量分别为CBS和EBS。
初始状态时两桶是满的,即Tc和Te初始值分别等于CBS和EBS。
令牌的产生速率是CIR,通常是先往C桶中添加令牌,等C桶满了,再往E桶中添加令牌,当两桶都被填满时,新产生的令牌将会被丢弃。
色盲模式下,假设到达的报文长度为B。
若报文长度B小于C桶中的令牌数Tc,则报文被标记为绿色,且C桶中的令牌数减少B;若Tc<BTe,标记为红色,两桶总令牌数都不减少。
在非色盲模式下,若报文已被标记为绿色或B<TC,则报文被标记为绿色,TC减少B;若报文已被标记为黄色或TC<BB >Te,则标记为红色,Tc和Te都不减少。
1.2 双速率三色标记算法IETF的RFC文件[3]定义了双速率三色算法,主要是根据4种流量参数来评估:CIR、CBS、峰值信息速率(PIR),峰值突发尺寸(PBS)。
前两种参数与单速率三色算法中的含义相同,PIR这个参数只在交换机上才有,路由器没有这个参数。
该值必须不小于CIR的设置值,如果大于CIR,则速率限制在CIR于PRI之间的一个值。
与单速率三色标记算法不同,双速率三色标记算法的两个令牌桶C桶和P桶填充令牌的速率不同,C桶填充速率为CIR,P桶为PIR;两桶的容量分别为CBS 和PBS。
用Tc和Tp表示两桶中的令牌数目,初始状态时两桶是满的,即Tc和Tp初始值分别等于CBS和PBS。
色盲模式下,如果到达的报文速率大于PIR,超过Tp+Tc部分无法得到令牌,报文被标记为红色,未超过Tp+Tc而从P桶中获取令牌的报文标记为黄色,从C桶中获取令牌的报文被标记为绿色;当报文速率小于PIR,大于CIR时,报文不会得不到令牌,但超过Tp部分报文将从P桶中获取令牌,被标记为黄色报文,从C桶中获取令牌的报文被标记为绿色;当报文速率小于CIR时,报文所需令牌数不会超过Tc,只从C桶中获取令牌,所以只会被标记为绿色报文。
在非色盲模式下,如果报文已被标记为红色或者超过Tp+Tc部分无法得到令牌的报文,被标记为红色;如果标记为黄色或者超过Tc未超过Tp部分报文记为黄色;如果报文被标记为绿或未超过Tc部分报文,被标记为绿色。
2 令牌桶算法的应用2.1 在流量监管中的应用约定访问速率(CAR)是流量监管常用技术之一[4],它的监管原理如图1所示。
根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;符合匹配规则的报文,则需要令牌桶进行处理。
当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌量按报文的长度做相应的减少;当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。
这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。
2.2 在通用流量整形中的应用通用流量整形中(GTS)[4](如图2所示)与CAR的原理稍有差别:第一,GTS只用于出方向流量限速,CAR出入方向均可以,但一般多用于入方向;第二,利用CAR进行报文流量控制时,对超过速率限制的报文直接丢弃,而GTS则是对超过速率限制的报文进行缓冲,即当令牌桶中的令牌少到报文不能再发送时,报文将被缓存入队列,等有了足够的令牌之后再发送,这样就减少了报文的丢弃,但是要注意的是,如果缓存队列已满,这时到达的报文仍旧会被丢弃。
2.3 在端口限速中的应用端口限速(LR)[4](如图3所示)也用于出方向,但不同于GTS的是:第一,GTS与CAR是在IP层实现的,所以对于不经过IP层处理的报文不起作用,而LR则能够限制在物理接口上通过的所有报文;第二,LR不但能够对超过流量限制的报文进行缓存,并且可以利用QoS丰富的队列如优先级队列(PQ)、自定义队列(CQ)、加权公平对列(WFQ)等来缓存报文。
3 令牌桶实现上面介绍了RFC中定义的令牌桶技术原理以及其在IP QoS中的应用,但是在实际应用中,令牌桶究竟是怎么实现的?令牌桶中的令牌是怎么添加的?报文的处理流程又是什么样的?下面就简单谈一谈令牌桶在业界的实现方式[5]。
3.1 单速率三色标记算法的实现3.1.1 桶的构成在令牌桶的构成上,目前业界有两种方式,如图4所示。
可以由一个桶实现,即C桶是E桶中的一部分(图4上),最终桶的容量是由EBS决定的。
不管有没有突发流量,EBS不能为0,必须大于或等于CBS。
这种实现方式完全按照令牌桶的定义来实现,因为CBS和EBS都是令牌桶的参数,所以放入一个相同的桶实现,通过突发计数器来进行区分。
也可以由两个桶实现(图4下),即C桶和E桶分开实现。
如果不允许有突发流量,EBS则设置成0。
3.1.2 令牌添加令牌桶的添加完全依照RFC规定实现,按照恒定的速率CIR添加。
即每隔1/CIR时间添加一个令牌,添加顺序为先添加C桶再添加E桶,当令牌桶添加满的时候,再产生的令牌就会被丢弃。
实际中比较常见的有两种实现方式:(1)周期性的添加,如图5所示,添加的时间间隔就是令牌桶的容量与添加速率的比值:T c=CBS/CIR,每次添加的令牌数为CBS 个;(2)一次性添加,只有当令牌桶中没有令牌时才添加令牌,如图6所示,添加令牌的数量是△t×CIR(△t是当前时间与上次添加令牌的时间之差),且是一次添加完毕,并不是按照一定速率添加。
3.1.3 报文处理流程一般的报文处理方法如图7所示:当报文到来后,直接与桶中的令牌数相比较,如果有足够的令牌就转发,如果没有足够的令牌则丢弃或缓存。
这种令牌桶处理方式在突发流量的处理上没有优势,也就是说当存在较大的突发流量时,令牌桶可能会由于没有足够令牌无法处理报文,而且在没有突发流量且报文到达速率较大时,报文处理流程也不连续,有时会因为令牌数量不足而造成丢包。
为解决这种无谓的丢包问题,目前业界采用了一种借贷机制的报文处理方法,如图8所示。
当报文到来后,只要令牌桶中有令牌,无论数量是否足够,都可以转发报文。
当令牌数量小于报文长度时,就可以欠债转发,即转发后令牌桶中令牌数目为负;当下次添加令牌的时候,先还清所欠债务,再继续转发报文。
这种处理方法较前者在处理突发报文时有优势,能够保证报文发送的连续性。
3.1.4 实现方式比较假设令牌桶的总容量为1 000 kb,CIR为125 kb/s,报文到达的速率为200 kb/s,报文长度为125 kB (1 000 kb)。
方式一:周期性添加令牌,只有当令牌数足够时才转发报文。