队列及拥塞管理
队列及拥塞管理
拥塞管理的中心内容是当拥塞发生时如何制定一个策略，用于决定报文转发的处理次序和丢弃原则，一般采用队列技术。
队列指的是在缓存中对报文进行排序的逻辑。当流量的速率超过接口带宽或超过为该流量设置的带宽时，报文就以队列的形式暂存在缓存中。报文离开队列的时间、顺序，以及各个队列之间报文离开的相互关系则由队列调度算法决定。
说明：
路由器转发平面的流量管理器TM（Traffic Manager）上有一些高速缓存，用于报文的缓冲和转发，缓存由所有端口共享，各端口竞争使用。为了避免有的端口长时间抢不到缓存而出现断流，路由器给每个端口分配了一块最小可用缓存，并且分配到端口的各个队列上，保证每个队列均有缓存可用。
当TM收到报文时，将报文放入缓存，网络不拥塞时，报文能被及时转发，不会在缓存中产生堆积。这种情况下报文在缓存中的时间为μs级，延迟时间可以忽略不计。
当网络拥塞时，报文在缓存中产生堆积，被延迟处理，延迟时间会大幅增加。延迟时间的大小主要取决于队列的缓存长度以及该队列获得的输出带宽，可以使用如下公式计算时延： 队列时延 = 队列缓存长度 / 队列输出带宽
华为路由器设备的每个端口上都有8个下行队列，称为CQ（Class Queue）队列，也叫端口队列（Port-queue），分别为BE、AF1、AF2、AF3、AF4、EF、CS6和CS7。 单个队列的报文采用FIFO（First In First Out）原则入队和出队。 图1 报文入队出队方式
队列调度算法
本文介绍几种常见队列调度算法：
? ? ? ? ? ? ?
先进先出FIFO（First In First Out） 严格优先级SP（Strict Priority） 轮询RR（Round Robin）
加权轮询WRR（Weighted Round Robin） 差分轮询DRR（Deficit Round Robin）
差分加权轮询DWRR（Deficit Weighted Round Robin） 加权公平队列WFQ（Weighted Fair Queuing）
FIFO
FIFO不对报文进行分类。FIFO按报文到达接口的先后顺序让报文进入队列，在队列的出口让报文按进队的顺序出队，先进的报文将先出队，后进的报文将后出队，如图1。
SP
SP（Strict Priority）调度就是严格按照队列优先级的高低顺序进行调度。只有高优先级队列中的报文全部调度完毕后，低优先级队列才有调度机会。
假设端口有3个采用SP调度算法的队列，分别为高优先（High）队列、中优先（Medium）队列、和低优先（Low）队列，它们的优先级依次降低。如图2，其中报文编号表示报文到达顺序。 图2 SP调度
在报文出队的时候，首先让高优先队列中的报文出队并发送，直到高优先队列中的报文发送完，然后发送中优先队列中的报文，直到发送完，接着是低优先队列。在调度低优先级队列时，如果高优先级队列又有报文到来，则会优先调度高优先级队列。这样，较高优先级队列的报文将会得到优先发送，而较低优先级的报文后发送。
SP调度的缺点是：拥塞发生时，如果较高优先级队列中长时间有报文存在，那么低优先级队列中的报文就会由于得不到服务而“饿死”。
RR
RR调度采用轮询的方式，对多个队列进行调度。RR以环形的方式轮询多个队列。如果轮询的队列不为空，则从该队列取走一个报文；如果该队列为空，则直接跳过该队列，调度器不等待。
图3 RR调度
WRR
加权轮询WRR（Weighted Round Robin）调度主要解决RR不能设置权重的不足。在轮询的时候，WRR每个队列享受的调度机会和该队列的权重成比例。RR调度相当于权值为1的WRR调度。
WRR的实现方法是为每个队列设置一个计数器Count，根据权重进行初始化。每次轮询到一个队列时，该队列输出一个报文且计数器减一。当计数器为0时停止调度该队列，但继续调度其他计数器不为0的队列。当所有队列的计数器都为0时，所有计数器重新根据权重初始化，开始新一轮调度。在一个循环中，权重大的队列被多次调度。 图4 WRR调度
假设某端口有3个队列采用WRR调度，为每个队列配置一个权值，依次为50%、25%、25%，详细的调度过程如下：
首先计数器初始化：Count[1]=2，Count[2]=1，Count[3]= 1。 ?
第1个轮询：
从队列1取出报文1发送，Count[1]=1；从队列2取出报文5发送，Count[2]=0；从队列3取出报文8发送，Count[3]=0。 ?
第2个轮询：
从队列1取出报文2发送，Count[1]=0；由于Count[2]=0，Count[3]=0，队列2和队列3不参与此轮调度。
此时，Count[1]=0，Count[2]=0，Count[3]=0，将计数器重新初始化：Count[1]=2，Count[2]=1，Count[3]= 1。
? 第3个轮询：
从队列1取出报文3发送，Count[1]=1；从队列2取出报文6发送，Count[2]=0；从队列3取出报文9发送，Count[3]=0。
? 第4个轮询：
从队列1取出报文4发送，Count[1]=0；由于Count[2]=0，Count[3]=0，队列2和队列3不参与此轮调度。
此时，Count[1]=0，Count[2]=0，Count[3]=0，将计数器重新初始化：Count[1]=2，Count[2]=1，Count[3]= 1。
从统计上看，各队列中的报文流被调度的次数与该队列的权值成正比，权值越大被调度的次数相对越多。如果该端口为100Mbps，则可以保证最低权重的队列至少获得25Mbps带宽，避免了采用SP调度时低优先级队列中的报文可能长时间得不到服务的缺点。
WRR对于空的队列直接跳过，循环调度的周期变短，因此当某个队列流量小的时候，剩余带宽能够被其他队列按照比例占用。 WRR调度有两个缺点： ?
WRR调度按照报文个数进行调度，因此每个队列没有固定的带宽，同等调度机会下大尺寸报文获得的实际带宽要大于小尺寸报文获得的带宽。而用户一般关心的是带宽。当每个队列的平均报文长度相等或已知时，通过配置WRR权重，用户能够获得想要的带宽；但是，当队列的平均报文长度变化时，用户就不能通过配置WRR权重获取想要的带宽。 ?
低延时需求业务（如语音）得不到及时调度。
DRR
差分轮询DRR（Deficit Round Robin）调度实现原理与RR调度基本相同。
DRR与RR的区别是：RR调度是按照报文个数进行调度，而DRR是按照报文长度进行调度。 DRR为每个队列设置一个计数器Deficit，Deficit初始化为一次调度允许的最大字节数，一般为接口MTU。每次轮询到一个队列时，该队列输出一个报文且计数器Deficit减去报文长度。如果报文长度超过了队列的调度能力，DRR调度允许Deficit出现负值，以保证长报文也能够得到调度。但下次轮循调度时该队列将不会被调度。当计数器为0或负数时停止调度该队列，但继续调度其他计数器为正数的队列。当所有队列的Deficit都为0或负数时，将所有队列的Deficit计数器加上初始值，开始新一轮调度。
假设某端口MTU=150Bytes，有2个队列Q1和Q2采用DRR调度，Q1队列中有多个200Bytes的长报文，Q2队列中有多个100Bytes的端报文，则调度过程如图5。