九章业务量管理课件

1、第九章 业务量管理主要内容业务量监管分组调度队列管理流量调节流量控制主要内容业务量监管分组调度队列管理业务量监管业务监管：Traffic Policing对业务进行监视，以避免超过许可的服务质量参数约定（平均速率，峰值速率、突发长度等）通过业务监管机制，可以对超过约定QoS参数业务的流量进行调节业务监管功能一般由位于网络入口处的边缘路由器上执行实现机制漏桶算法 令牌桶算法漏桶算法应用于分组传输的漏桶算法平滑突发业务流不论输入的速率为多大，输出速率始终是常数漏桶算法算法过程1）将漏桶看做是一个有限长度的队列，以字节为单位计数，当分组到达的时候，如果队列中还有空间的话，就被添加到对列的尾部，否则该

2、分组将被丢弃2）在每一个嘀嗒周期，首先将计数器初始化为n，如果队列中第一个分组的字节数少于计时器的当前值，则将分组发送出去，并且将计数器减去该分组的字节数。然后对下一个分组执行同样的过程，直到出现计数器的值小于队列中的分组的长度为止。此时，传输过程终止，直到下一个嘀嗒再开始3）到达下一个嘀嗒的时候，计数器被重置，执行步骤2），再次开始分组发送过程令牌桶算法算法过程1）每个令牌桶维护一个字节计数器，每隔T秒，计数器的值增加K字节，这就相当于往桶中放一个令牌，一个令牌代表了传输K字节的权利，令牌速率为r=K/T（Bps）。假设桶的大小为b字节，当计数器的值大于b字节时，就会发生溢出，需要注意的是，

3、这里溢出丢弃的是令牌，而不是数据 2）当有分组等待发送时，如果计数器的值大于当前分组的长度，则发送该分组，并且将计数器的值减去分组长度。如果还有分组等待发送，继续执行上面的过程，直到计数器的值小于分组长度为止漏桶和令牌桶两者都可以用于业务监管，判断一个流是否违反约定的参数 漏桶算法的输出保持的是严格的均匀速率，不管业务流量的突发程度如何在漏桶算法中，不允许将空闲时的发送许可权保存起来以便发送大的突发数据（每个时钟嘀嗒后，漏桶的字节计数器都将被重置）令牌桶算法在大量突发数据到来的时候，允许输出流适当的加快可以将发送许可权保存起来，直到到达桶的最大尺寸。这也就意味着只要突发数据不超过桶的大小，就可

4、以一次发送出去 在漏桶算法中，桶中填充的是数据，所以当桶填满后将丢弃分组，而在令牌桶中，桶中填充的是令牌，所以当桶填满后将丢弃令牌，相当于是传输许可，而不是分组6543210Arrival time at bucketDeparture time from a leaky bucketLeaky bucket rate = 1 packet / 2 time units65432106543210Departure time from a token bucketToken bucket rate = 1 token / 2 time unitsToken bucket size = 2 to

5、kens漏桶和令牌桶主要内容业务量监管分组调度队列管理概述分组调度用于缓存区中的多个分组竞争使用同一个输出链路时使用什么样的策略来选择分组发送？该策略会对性能有什么影响？1990年代的一个热点研究领域共享存储交换占主导传输链路带宽特别是骨干网链路带宽是稀缺的资源路由器输出缓存以队列的方式进行组织，调度主要对输出队列进行调度可以更加有效地利用路由器有限的带宽资源，以尽量满足不同业务的需求设计考虑因素在设计调度算法时，应该根据实际情况考虑三个因素优先级（Priorization）：如果不同的流具有不同的QoS需求，需要使用优先级来实现流区分。例如某些流可能需要更低的延迟，那么属于这些流的分组将被优

6、先调度公平性（Fairness）：不同流能够平等地访问网络资源，也就是说这些流对于网络资源具有相同的权利隔离（Protection）：对于以超过其分配带宽发送分组的恶意流不应该影响到其它正常流的性能算法先到先服务优先级调度Round Robin公平调度GPS、FQ、WFQ等常用于具有QoS需求的场合先到先服务先到先服务（FCFS：First-Come-First Served）发送机会到来时，最先到达的分组具有最高的调度优先级缺点：无法实现流区分，不支持基于流的优先级，也无法保证公平性和隔离优先级调度当有比当前正在发送分组优先级更高的分组到达时，如何处理？继续发送低优先级分组，直到发送完成后再

7、处理高优先级分组低优先级分组被停止服务，重新放回队列中或者被丢弃，开始发送高优先级分组非抢占式调度抢占式调度Round RobinRound Robin调度到达输出队列的流被分成不同的队列当有发送机会到来时，采用轮询的方式选择队列，并且从队列中选择分组发送 缺点：当每个流的分组大小不同时，难以保证公平性队列1：分组1，2，4队列2：分组3，5Round Robin在Round Robin调度的过程中，如果某个队列为空，如何处理？在分配给该队列的时间内链路保持空闲，也就是说即使队列中没有分组要发送，也在每一轮调度中都保留为该队列分配的资源 直接转到下一个队列。也就就是说，只要有分组在队列中等待发

8、送，链路就不会空闲non-work-conversing调度work-conversing调度公平调度公平（Fairness）不是指用户分配相同份额的资源，而是指每个用户对资源具有相同的访问权利问题：如果系统没有足够的资源满足所有用户的需求，并且某些用户可能比其他用户需要更少的资源。在保证公平的情况下如何分配资源？ Max-Min公平共享：首先要满足那些需求小于它们可以得到部分的用户，然后将多余的资源在那些需求更大的用户之间平均分配 可以证明，在Round Robin调度算法中，如果每个队列中的分组大小都相等，则满足Max-Min公平共享Max-Min公平共享定义资源按照递增的顺序分配没有用户

9、获得大于其所需的资源无法满足需求的用户获得相同的资源分配过程假设系统总资源R用户集合1，2， n对应的资源需求r1，r2，rn，r1r2= maxth then mark or drop the packet else if minth= avgQ 0)wq：RED对拥塞的反应程度过大，不能过滤由于突发导致的短暂拥塞过小，对实际队列长度反应过慢，不能有效地检测拥塞avgQ = (1-wq)mavgQ (if q=0)m=queue_idle_time/typical_transmission_timeWq: 由路由器或者交换机允许的突发业务大小和持续时间决定RED计算标记（丢弃）概率方法1：P

10、b = maxp*(avgQ-minth)/(maxth-minth) maxth-minth应该大于一个往返时间内平均队 列的增加值，以避免由于丢弃过多的分组而导致全局同步一般将maxth设置为minth的2倍方法2：P = Pb/(1-count*Pb) count:上一次丢弃到现在进入队列的分组数量，实现均匀分组间隔地丢包，避免对突发流的偏见和产生全局同步现象Average Queue Length01minthmaxthmaxp在假设平均队列长度为常数的情况下，丢弃概率的选择应该使得分组丢弃间隔尽量均匀避免对突发业务流的偏见避免产生全局同步现象X：连续两次分组丢弃之间到达分组数量（包括

11、后一次丢弃分组）1）直接使用Pb计算丢弃概率2）在计算丢弃概率时考虑count均匀间隔丢弃RED性能分析TimeMax Queue Sizemax_thmin_thForced dropProbabilistic dropsNo dropsDrop probabilityAverage queue length丢弃概率依赖于拥塞程度，并且均匀间隔丢弃，避免了由于分组连续丢弃导致的全局同步现象发生拥塞时，丢弃某个流的分组的概率基本上与该流在路由器或者交换机上获得的带宽成比例平均队列超过阈值后就开始丢弃分组，有效地控制了平均队列长度，限制了平均延迟，并且允许一定程度的突发分组RED参数设置问题RED的参数的微小变化会给总体性能带来很大的影响，与特定的业务环境相关不能有效估计拥塞的严重性从路由器或者交换机开始丢弃分组到源端检查到丢弃从而做出反应，可能需要很长的时间，RED