九章业务量管理.ppt

《九章业务量管理.ppt》由会员分享，可在线阅读，更多相关《九章业务量管理.ppt（65页珍藏版）》请在三一文库上搜索。

1、第九章 业务量管理,主要内容,业务量监管 分组调度 队列管理,流量调节,流量控制,主要内容,业务量监管 分组调度 队列管理,业务量监管,业务监管：Traffic Policing 对业务进行监视，以避免超过许可的服务质量参数约定（平均速率，峰值速率、突发长度等） 通过业务监管机制，可以对超过约定QoS参数业务的流量进行调节 业务监管功能一般由位于网络入口处的边缘路由器上执行 实现机制 漏桶算法 令牌桶算法,漏桶算法,漏桶算法：Leaky Bucket 只要桶中有水，水流出的速率就是常数 桶中没有水的时候，水流出的速率为0 桶满以后，往里面流的水会溢出,漏桶算法,应用于分组传输的漏桶算法 平滑突

2、发业务流 不论输入的速率为多大，输出速率始终是常数,漏桶算法,算法过程 1）将漏桶看做是一个有限长度的队列，以字节为单位计数，当分组到达的时候，如果队列中还有空间的话，就被添加到对列的尾部，否则该分组将被丢弃 2）在每一个嘀嗒周期，首先将计数器初始化为n，如果队列中第一个分组的字节数少于计时器的当前值，则将分组发送出去，并且将计数器减去该分组的字节数。然后对下一个分组执行同样的过程，直到出现计数器的值小于队列中的分组的长度为止。此时，传输过程终止，直到下一个嘀嗒再开始 3）到达下一个嘀嗒的时候，计数器被重置，执行步骤2），再次开始分组发送过程,令牌桶算法,令牌桶：Token Bucket 桶中

3、保存的是令牌，每隔T秒产生一个 只有当桶中有令牌时才能传输数据 允许突发流量,Arriving packets,假设： S:突发长度（s） b: 令牌桶容量（B） M：最大输出速率（Bps） r：令牌到达速率（Bps） b+rS = MS S=b/(M-r),令牌桶算法,算法过程 1）每个令牌桶维护一个字节计数器，每隔T秒，计数器的值增加K字节，这就相当于往桶中放一个令牌，一个令牌代表了传输K字节的权利，令牌速率为r=K/T（Bps）。假设桶的大小为b字节，当计数器的值大于b字节时，就会发生溢出，需要注意的是，这里溢出丢弃的是令牌，而不是数据 2）当有分组等待发送时，如果计数器的值大于当前分组

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

5、而在令牌桶中，桶中填充的是令牌，所以当桶填满后将丢弃令牌，相当于是传输许可，而不是分组,6,5,4,3,2,1,0,Arrival time at bucket,漏桶和令牌桶,主要内容,业务量监管 分组调度 队列管理,概述,分组调度用于缓存区中的多个分组竞争使用同一个输出链路时 使用什么样的策略来选择分组发送？ 该策略会对性能有什么影响？ 1990年代的一个热点研究领域 共享存储交换占主导 传输链路带宽特别是骨干网链路带宽是稀缺的资源,路由器输出缓存以队列的方式进行组织，调度主要对输出队列进行,调度可以更加有效地利用路由器有限的带宽资源，以尽量满足不同业务的需求,设计考虑因素,在设计调度算法时

6、，应该根据实际情况考虑三个因素,优先级（Priorization）：如果不同的流具有不同的QoS需求，需要使用优先级来实现流区分。例如某些流可能需要更低的延迟，那么属于这些流的分组将被优先调度 公平性（Fairness）：不同流能够平等地访问网络资源，也就是说这些流对于网络资源具有相同的权利 隔离（Protection）：对于以超过其分配带宽发送分组的恶意流不应该影响到其它正常流的性能,设计考虑因素,公平性和优先级 公平性保证相同优先级的业务流接受相同的服务 公平性和隔离 相关，公平性会自动地提供隔离，将恶意流限制在其所享有的资源范围内,算法,先到先服务 优先级调度 Round Robin 公

7、平调度 GPS、FQ、WFQ等,常用于具有QoS需求的场合,先到先服务,先到先服务（FCFS：First-Come-First Served） 发送机会到来时，最先到达的分组具有最高的调度优先级,缺点：无法实现流区分，不支持基于流的优先级，也无法保证公平性和隔离,优先级调度,优先级队列（PQ：Priority Queueing） 到达输出队列的流被分成若干个具有不同优先级的队列 当发送机会到来时，选择最高优先级并且非空的队列中的分组来发送，对于属于同一个优先级队列的分组，采用FCFS调度机制,缺点：无法提供公平性和隔离，低优先级队列调度会出现“饥饿”现象，因为只有高优先级队列中无分组发送时，低

8、优先级的分组才有发送机会,高优先级队列：分组1，3，4 低优先级队列：分组2，5,优先级调度,当有比当前正在发送分组优先级更高的分组到达时，如何处理？ 继续发送低优先级分组，直到发送完成后再处理高优先级分组 低优先级分组被停止服务，重新放回队列中或者被丢弃，开始发送高优先级分组,非抢占式调度,抢占式调度,Round Robin,Round Robin调度 到达输出队列的流被分成不同的队列 当有发送机会到来时，采用轮询的方式选择队列，并且从队列中选择分组发送,缺点：当每个流的分组大小不同时，难以保证公平性,队列1：分组1，2，4 队列2：分组3，5,Round Robin,在Round Robi

9、n调度的过程中，如果某个队列为空，如何处理？ 在分配给该队列的时间内链路保持空闲，也就是说即使队列中没有分组要发送，也在每一轮调度中都保留为该队列分配的资源 直接转到下一个队列。也就就是说，只要有分组在队列中等待发送，链路就不会空闲,non-work-conversing调度,work-conversing调度,公平调度,公平（Fairness） 不是指用户分配相同份额的资源，而是指每个用户对资源具有相同的访问权利,问题：如果系统没有足够的资源满足所有用户的需求，并且某些用户可能比其他用户需要更少的资源。在保证公平的情况下如何分配资源？,Max-Min公平共享：首先要满足那些需求小于它们可以得

10、到部分的用户，然后将多余的资源在那些需求更大的用户之间平均分配,可以证明，在Round Robin调度算法中，如果每个队列中的分组大小都相等，则满足Max-Min公平共享,Max-Min公平共享,定义 资源按照递增的顺序分配 没有用户获得大于其所需的资源 无法满足需求的用户获得相同的资源 分配过程 假设 系统总资源R 用户集合1，2， n 对应的资源需求r1，r2，rn，r1r2rn 步骤 首先将R/n的资源分配给用户1，也就是具有最小资源需求的那个用户，R/n可能大于r1，也就是比用户1需求的要多，此时将r1分配给用户1，并且继续这个过程来，在剩余用户中分配剩下来的资源，直到出现第一个分配到

11、的资源不比其需要的多为止，该用户的需求没有得到满足,Max-Min公平共享分配例子-步骤1,Max-Min公平共享分配例子-步骤2,Max-Min公平共享分配例子-步骤3,Max-Min公平共享分配例子-步骤4,加权Max-Min公平共享,赋予某些用户比其它用户具有获取更大份额资源的权利 对每一个用户i都赋予相应的权重wi，以反应其获取资源的相对权利 加权Max-Min公平共享分配定义 对用户需求通过权重归一化，然后按递增顺序来分配资源。 没有用户获得大于其所需的资源 无法满足需求的用户获得与其权重成比例的资源份额,加权Max-Min公平共享例子,链路容量C=1Mbps=1,000,000bp

12、s,权重为：w1=0.5, w2=2, w3=1.75, w4=0.75,权重归一化后得到2/20, 8/20, 7/20, 3/20。第1轮分配结束后，3多出的145,200在1，2，4中进行分配，1得到145200*2/(2+8+3)=22338bps, 2得到145200*8/(2+8+3)=89354bps, 4得到145200*3/(2+8+3)=33508bps，需要注意的是，在分配时只用考虑剩下用户的权值,权重为：w1=0.5, w2=2, w3=1.75, w4=0.75,权重为：w1=0.5, w2=2, w3=1.75, w4=0.75,加权Max-Min公平共享例子,公平

13、调度算法,GPS 理想情况下实现Max-Min公平共享的调度算法 FQ 在实际环境下模拟GPS算法 WFQ 加权FQ，权重决定用户对资源的权利,GPS和FQ的目标是实现或者接近MAX-MIN公平共享，在实现时采用类似于Round Robin的调度规则,GPS调度,GPS：Generalized Processor Sharing 为属于不同流的分组分别维护不同的队列 以bit-by-bit round robin的方式工作 路由器从队列1选择1个比特发送，然后从队列2选择1个比特发送，如此循环,Aij:第i个流的第j个分组的到达时间 流1的分组长度为2比特 流2和流3的分组长度为3比特,对于每

14、个队列，有以下两个假设： 1）队列内的调度是先到先服务 2）队列内采用非抢占调度,对于一个k比特的分组，需要k轮调度才能完成，但是实际所需的时间随着活跃流的数量而变化,GPS总结,GPS算法实现了MAX-MIN共享公平 GPS调度算法是一个理想情况下调度算法 在实际环境下，路由器或者交换机是以分组而不是比特为单位来调度的,FQ,FQ：Fair Queuing 为属于不同流的分组维护不同的等待队列 以分组为单位执行调度,选择哪个分组来发送？ 1）计算每个分组采用bit-by-bit round robin（GPS）方式完成发送所需要的轮数，这个轮数也被称为分组的Finish Number 2）按

15、照Finish Number从小到大的顺序来选择分组发送,FQ,Finish Number的计算,Aij: 第i个流的第j个分组 Lij: Aij的长度(以比特为单位) Fij: Aij的Finish Number ta: Aij的到达时间 R(ta): Aij到达时已经完成的调度轮数 Aij开始被发送时已经完成的调度轮数是下面两个值中的最大者： 在分组到达时间ta时已经完成的轮数(R(ta) 这实际上意味着分组一到达就被发送 Ai,j-1的Finish Number 这也就意味着分组到达时有分组在发送或者在等待发送 因此可以得到Aij的Finish Number： Fij = maxFi,j

16、-1, R(ta) + Lij,FQ,FQ在每个新的分组到达时执行以下的过程 1）利用Fij = maxFi,j-1, R(ta) + Lij计算新到达分组的finish number 2）对于所有等待发送的分组，按照它们的finish number递增的顺序排列 3）如果当前有分组正在发送，则等待分组发送完后选择一个finish number最小的分组来发送,在FQ中，调度分组的选择除了和Finish Number有关外，还和分组的到达时间相关，应该选择已经到达并且Finish Number最小的分组发送,4 queues, sharing 1 bits/sec of bandwidth,A

17、2, C3 arrive,C1, D1的Finish Number为1,C2的Finish Number为2,T=0时的队列列状态,T=4时的队列列状态,4 queues, sharing 1 bits/sec of bandwidth,Sort by finish number of packets,B1, D2的Finish Number为2,C3, A1的Finish Number为4，A2为6,由于A2，C3在时间4到达，而根据FQ调度，它们分别在时间12、14开始发送，大于它们到达的时间，所以以上调度过程有效,2 queues, sharing 1 bits/sec of bandw

18、idth,t=1,C2=1,1,0,1,2,3,4,5,2,3,4,5,6,C1发送完成，选择A1发送，发送完A1需要4s,t=3,C2的Finish Number=3,6,t,R,虽然C2的Finish Number要小于A1，但是由于A1还在发送，因此实际上只有在A1发送完以后才能选择C2发送,需要注意的是： 1）计算Finish Number的分组发送采用bit-by-bit Round Robin，与实际分组发送不一样！ 2）根据分组的到达时间寻找对应的计算Finish Number的虚拟时间，从而确定起始轮数,C1完成,C2到达,C2完成,A1完成,FQ总结,FQ可以看作在实际环境下

19、对GPS的接近，但不是精确模拟 在FQ中，对每个新到达的分组都需要计算Finish Number 对于高速网络来说，计算过于复杂,WFQ,WFQ: Weighted Fair Queuing 每个流对资源拥有不平等的权利 对于流1, 2, , n, 分别有权重w1, w2, , wn，每个流的权重反映了该流对资源的权利 在加权Max-Min公平共享下，假设链路带宽为C，则流i获得的带宽为：,Ci =,WFQ下Finish Number的计算,Ai,j: 流i的第j个分组 ta: Ai,j的到达时间 R(ta): Ai,j到达时完成的调度轮数 Li,j: Ai,j的长度 Wi: 流i的权重,4

20、queues, sharing 4 bits/sec of bandwidth, Weights 3:2:2:1,A2, C3 arrive,C1, C2, D1的Finish Number为1,T=0时的队列列状态,4 queues, sharing 4 bits/sec of bandwidth, Weights 3:2:2:1,Sort by finish number of packets,Sort packets,A1, A2, B1的Finish Number为2,主要内容,业务量监管 分组调度 队列管理,概述,当进入网络的业务超过网络的容量时，网络将出现拥塞，导致大量分组被丢弃

21、分组丢弃主要是由于在路由器或者交换机上的队列空间有限造成的 什么时候开始丢弃分组？ 使用什么样的策略来选择丢弃的分组？ 丢弃策略会对网络性能产生什么样的影响？,队列管理决定路由器输出队列的分组丢弃策略，以缓解或者避免网络拥塞,丢弃策略,丢弃策略不仅仅是丢弃分组，还需要能够有效地缓解网络拥塞，这需要和具体的业务配合工作,概述,拥塞无响应流 对网络拥塞没有反应，仍然保持原有行为的业务流 基于UDP的业务流 拥塞响应流 当发生网络拥塞时，能够做出相应调整的业务流，例如降低发送速率 基于TCP的业务流,TCP中的拥塞控制机制,TCP发送端维护一个发送窗口，决定了一次能够发送的最大的数据量 发送窗口的大

22、小由TCP接收端的接收能力和现有网络容量来确定 发送窗口的上限值=Minrwnd, cwnd rwnd：接收端窗口，反应了接收端的接收能力 cwnd：拥塞窗口，反应了当前的可用网络容量,rwnd由接收端当前可用的接收缓存来确定，关键是如何确定cwnd,TCP中的拥塞控制机制,TCP拥塞控制算法过程 当一个连接初始化时，将拥塞窗口置为一个最大数据段长度，并设置慢启动阈值ssthresh。 发送端的发送窗口不能超过拥塞窗口和接收窗口中的最小值，并假定接收端不进行流量控制。 发送端若收到了对所有发出的数据段的确认，就在下一次发送时将拥塞窗口加倍。可见拥塞窗口从1开始按指数规律增长 拥塞窗口增长到ss

23、thresh时，就每次将拥塞窗口加1，使拥塞窗口按线性规律增长 如果出现数据段丢失，就将当时拥塞窗口值减半，作为新的ssthresh，同时将拥塞窗口变为1 重复上述过程,慢启动,拥塞避免,TCP中的拥塞控制机制,基于TCP的流在检测到网络拥塞时将通过主动减少发送窗口来降低发送速率,分类,被动队列管理（PQM：Passive Queue Management） 当队列满时开始丢弃分组 拥塞恢复策略 Drop-tail，Drop-Front，Drop-Random等 主动队列管理（AQM：Active Queue Management） 预见拥塞将要发生时开始丢弃分组 拥塞防止策略 RED，ARE

24、D，SRED，FRED，BLUE等,Drop-Tail,PQM策略 队列满时丢弃随后到达的分组 Internet上缺省使用的丢弃策略 缺点 全局同步（Global Synchronization）问题 死锁（Lock-Out）问题 满队列（Full Queues）问题,全局同步问题,Can result in very low throughput during periods of congestion,Max Queue Length,全局同步问题,Queue Size,Time,Total Queue,全局同步问题,Flow 1,Rate,Time,Flow 2,Aggregate lo

25、ad,bottleneck rate,死锁问题,某个流或者少部分流垄断队列空间，阻止其他流的分组进入队列,Max Queue Length,满队列问题,队列长时间处于满的状态 增加排队延迟 导致突发数据丢弃,Max Queue Length,RED,RED：Random Early Detection AQM策略 避免全局同步、死锁、满队列问题 原理 通过检测队列平均长度来探测拥塞，当发现拥塞逼近时，开始以一定的概率选择分组标记（丢弃） 分组标记（丢弃）的概率与平均队列长度相关 只标记（丢弃）正进入路由器或者交换机的分组，实现简单,RED,算法过程,Upon packet arrival do

26、 Compute the average queue size avgQ if avgQ = maxth then mark or drop the packet else if minth= avgQ maxth then mark or drop packet with probability P end if end do,1）计算平均队列长度avgQ 2）计算标记（丢弃）概率P,RED,计算平均队列长度avgQ q：测量时当前队列长度 avgQ = (1 wq)avgQ + wqq (if q 0) wq：RED对拥塞的反应程度 过大，不能过滤由于突发导致的短暂拥塞 过小，对实际队列长

27、度反应过慢，不能有效地检测拥塞 avgQ = (1-wq)mavgQ (if q=0) m=queue_idle_time/typical_transmission_time,Wq: 由路由器或者交换机允许的突发业务大小和持续时间决定,RED,计算标记（丢弃）概率 方法1：Pb = maxp*(avgQ-minth)/(maxth-minth) maxth-minth应该大于一个往返时间内平均队 列的增加值，以避免由于丢弃过多的分组而导致全局同步 一般将maxth设置为minth的2倍 方法2：P = Pb/(1-count*Pb) count:上一次丢弃到现在进入队列的分组数量，实现均匀分组

28、间隔地丢包，避免对突发流的偏见和产生全局同步现象,在假设平均队列长度为常数的情况下，丢弃概率的选择应该使得分组丢弃间隔尽量均匀 避免对突发业务流的偏见 避免产生全局同步现象,X：连续两次分组丢弃之间到达分组数量（包括后一次丢弃分组） 1）直接使用Pb计算丢弃概率 2）在计算丢弃概率时考虑count,均匀间隔丢弃,RED,性能分析,丢弃概率依赖于拥塞程度，并且均匀间隔丢弃，避免了由于分组连续丢弃导致的全局同步现象 发生拥塞时，丢弃某个流的分组的概率基本上与该流在路由器或者交换机上获得的带宽成比例 平均队列超过阈值后就开始丢弃分组，有效地控制了平均队列长度，限制了平均延迟，并且允许一定程度的突发分组,RED,参数设置问题 RED的参数的微小变化会给总体性能带来很大的影响，与特定的业务环境相关 不能有效估计拥塞的严重性 从路由器或者交换机开始丢弃分组到源端检查到丢弃从而做出反应，可能需要很长的时间，RED必须配置足够的缓存空间 RED还需确保丢弃分组在充分降低源端发送速率的同时不能降低链路的利用率 一般权值wq很小(例如0.002)，平均队列长度变化很小 当系统负载很重时，平均队列长在maxth附近震荡，导致分组长时间连续丢弃（avgQmaxth）或者连续随机丢弃(avgQmaxth)，有可能导致全局同步现象 公平性问题 拥塞无响应流可能导致拥塞响应流陷入饥饿状态,