QoS队列调度算法
队列指的是在缓存中对报⽂进⾏排序的逻辑。当流量的速率超过接⼝带宽或超过为该流量设置的带宽时，报⽂就以队列的形式暂存在缓存中。报⽂离开队列的时间、顺序，以及各个队列之间报⽂离开的相互关系由队列调度算法决定。
华为交换机设备的每个端⼝上都有 8 个下⾏队列，称为CQ（Class Queue）队列，也叫端⼝队列（Port-queue），在交换机内部与前⽂提到的 8 个PHB⼀⼀对应，分别为BE、 AF1、AF2、AF3、AF4、EF、CS6 和CS7。单个队列的报⽂采⽤ FIFO（First In First Out）原则⼊队和出队。
PQ（Priority Queuing）调度
PQ（Priority Queuing）调度，就是严格按照队列优先级的⾼低顺序进⾏调度。只有⾼优先级队列中的报
⽂全部调度完毕后，低优先级队列才有调度机会。采⽤PQ 调度⽅式，将延迟敏感的关键业务放⼊⾼优先级队列，将⾮关键业务放⼊低优先级队列，从⽽确保关键业务被优先发送。 PQ调度的缺点是：拥塞发⽣时，如果较⾼优先级队列中长时间有分组存在，那么低优先级队列中的报⽂就会由于得不到服务⽽“饿死”。
假设端⼝有 3 个采⽤PQ调度的队列，分别为⾼优先（High）队列、中优先（Medium）队列、和低优先（Low）队列，它们的优先级依次降低。如图，其中报⽂编号表⽰报⽂到达顺序。
图1 PQ调度
RR（Round Robin）调度
RR调度采⽤轮询的⽅式，对多个队列进⾏调度。RR以环形的⽅式轮询多个队列。如果轮询的队列不为空，则从该队列取⾛⼀个报⽂；如果该队列为空，则直接跳过该队列，调度器不等待。
图2 RR调度
RR调度各个队列之间没有优先级之分，都能够有相等的概率得到调度。RR调度的缺点是：所有队列⽆法体现优先级，对于延迟敏感的关键业务和⾮关键业务⽆法得到区别对待，使得关键业务⽆法及时得到处理
WRR（Weighted Round Robin）调度
加权轮询WRR（Weighted Round Robin）调度主要解决RR不能设置权重的不⾜。在轮询的时候，WRR每个队列享受的调度机会和该队列的权重成⽐例。RR调度相当于权值为 1 的WRR调度。 WRR的实现⽅法是为每个队列设置⼀个计数器 Count，根据权重进⾏初始化。每次轮询到⼀个队列时，该队列输出⼀个报⽂且计数器减⼀。当计数器为 0 时停⽌调度该队列，但继续调度其他计数器不为 0 的队列。当所有队列的计数器都为 0 时，所有计数器重新根据权重初始化，开始新⼀轮调度。在⼀个循环中，权重⼤的队列被多次调度。
图3 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，则可以保证最低权重的队列⾄少获得25Mbit/s带宽，避免了采⽤PQ调度时
低优先级队列中的报⽂可能长时间得不到服务的缺点。WRR对于空的队列直接跳过，循环调度的周期变短，因此当某个队列流量⼩的时候，剩余带宽能够被其他队列按照⽐例占⽤。
WRR调度有两个缺点：
1. WRR调度按照报⽂个数进⾏调度，因此每个队列没有固定的带宽，同等调度机会下⼤尺⼨报⽂获得的实际带宽要⼤于⼩尺⼨报⽂获得
的带宽。⽽⽤户⼀般关⼼的是带宽。当每个队列的平均报⽂长度相等或已知时，通过配置WRR权重，⽤户能够获得想要的带宽；但是，当队列的平均报⽂长度变化时，⽤户就不能通过配置WRR权重获取想要的带宽。
2. 低延时需求业务（如语⾳）得不到及时调度。
DRR（Deficit Round Robin）调度
差分轮询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 的端报⽂，则调度过程如图 4 所⽰。
图4 DRR调度
由图4可以看出，经过第 1~6 轮DRR调度，Q1队列被调出了3个200Bytes 的报⽂， Q2队列被调出了6个100Bytes 的报⽂。从长期的统计看，Q1和 Q2 的实际输出带宽⽐是 1:1，为公平的⽐例。DRR调度避免了采⽤PQ调度时低优先级队列中的报⽂可能长时间得不到服务的缺点。但是，DRR调度不能设置权重，且也具有低延时需求业务（如语⾳）得不到及时调度的缺点。
DWRR（Deficit Weighted Round Robin）调度
差分加权轮询DWRR（Deficit Weighted Round Robin）调度主要解决DRR不能设置权重的不⾜。DRR调度相当于权值为 1 的DWRR调度。 DWRR为每个队列设置⼀个计数器Deficit，Deficit 初始化为Weight * MTU。每次轮询到⼀个队列时，该队列输出⼀个报⽂且计数器Deficit 减去报⽂长度。当计数器为 0 时停⽌调度该队列，但继续调度其他计数器不为 0 的队列。当所有队列的计数器都为 0 时，所有计数器的Deficit 都加上Weight*MTU，开始新⼀轮调度。
图5 DWRR调度
假设某端⼝MTU=150Bytes，有 2 个队列Q1和Q2采⽤DRR调度，Q1 队列中有多个 200Bytes 的长报⽂，Q2队列中有多个 100Bytes 的端报⽂，Q1和Q2配置权重⽐为weight1:weight2=2:1。则DWRR调度过程如图 2-37。
1. 第⼀轮调度 Deficit[1] =weight1* MTU=300，Deficit[2] = weight2* MTU=150Bytes，从 Q1 队列取出 200Bytes 报⽂发送，从Q2队列取
出 100Bytes 发送；发送后，Deficit[1] = 100，Deficit[2] =50。
2. 第⼆轮调度
从 Q1 队列取出 200Bytes 报⽂发送，从Q2队列取出 100Bytes 发送；发送后， Deficit[1] = -100，Deficit[2] =-50。
3. 第三轮调度
此时两个队列都为负，因此，Deficit[1] = Deficit[1]+weight1* MTU=-100+2150=200，Deficit[2] = Deficit[2]+weight2 MTU=-
50+1*150=100。
从 Q1 队列取出 200Bytes 报⽂发送，从Q2队列取出 100Bytes 发送；发送后， Deficit [1] = 0，Deficit[2] = 0。
由上图可以看出，经过第 1~3 轮DWRR调度，Q1队列被调出了3个200Bytes 的报⽂，Q2 队列被调出了3个100Bytes 的报⽂。从长期的统计看，Q1和Q2的实际输出带宽⽐是 2:1，与权重⽐相符。
DWRR调度避免了采⽤PQ调度时低优先级队列中的报⽂可能长时间得不到服务的缺点，也避免了各队列报⽂长度不等或变化较⼤时，WRR 调度不能按配置⽐例分配带宽资源的缺点。但是，DWRR调度也具有低延时需求业务（如语⾳）得不到及时调度的缺点。
WFQ（Weighted Fair Queuing）调度
加权公平队列WFQ（Weighted Fair Queuing）调度是按队列权重来分配每个流应占有出⼝的带宽。同时，为了使得带宽分配更加“公平”，WFQ 以 bit 为单位进⾏调度，类似于图 6的 bit-by-bit 调度模型
图6 WFQ调度weight的所有形式
Bit-by-bit 调度模型可以完全按照权重分配带宽，防⽌长报⽂⽐短报⽂获得更多带宽，从⽽减少⼤⼩报⽂共存时的时延抖动。但Bit-by-bit 调度模型只是理想化的模型，实际上，华为交换机实现的WFQ是按照⼀定的粒度，例如 256B、1KB，或其他粒度，具体按何种粒度，与单板
类型相关。
WFQ的优点主要有以下⼏点：
不同的队列获得公平的调度机会，从总体上均衡各个流的延迟。
短报⽂和长报⽂获得公平的调度：如果不同队列间同时存在多个长报⽂和短报⽂等待发送，让短报⽂优先获得调度，从⽽在总体上减少各个流的报⽂间的抖动。
从统计上看，权重越⼩，所分得的带宽越少。权重越⼤，所分得的带宽越多。