作者：黄玉栋，北京邮电大学网络与交换国家重点实验室博一在读，研究方向为未来网络体系架构，确定性网络，邮箱地址: hyduni@163.com。

上一节介绍了队列的概念（秒懂确定性网络之玩转队列（上）），本节分析队列机制的演进过程，从单队列延伸到多队列，从软件队列延伸到硬件队列，从软件定义队列延伸到可编程队列，以及每用户、每队列、每流、每包等队列调度粒度。

队列的演进

1单队列到多队列

当出端口只有一个队列时，所有的包都被放在同一个队列进行调度，流与流之间缺少隔离性，容易导致乱序和抖动，因此交换机逐渐从单队列发展到多队列，利用多个队列来保证隔离性。典型的多队列是优先级队列，其具有0-7共八个队列优先级，且一般将7定义为最高优先级。多队列在调度时，不仅要考虑单个队列中包的调度顺序，还要考虑队列之间的调度顺序，即选择哪一个队列为出端口传输队列，常用的传输选择策略[1]有严格优先级（SP, Strict Priority）、加权轮询（WRR，Weighted Round Robin）、加权公平队列（WRQ，Weighted Fair Queuing）。

SP调度就是严格按照队列优先级的高低顺序进行调度，只有高优先级队列中的报文全部调度完毕后，才调度低优先级队列。其优点是关键业务可以优先被传输以降低响应延迟，其缺点是拥塞发生时，如果高优先级队列中一直有报文存在，那么低优先级队列中的报文将一直得不到服务。

RR调度即采用轮询的方式，如果轮询的队列不为空，则从该队列取走一个报文；如果该队列为空，则直接跳过该队列，调度器不等待。轮询保证了队列传输机会的均等性，WRR在轮询的基础上为队列添加权重，根据权重初始化发包计数器，权重越大，调度机会越多，能被传输的包就越多；比如三个队列的权重为50%、25%、25%，则50%权重的队列传输机会比另外两个队列多一倍，能多发一个包。 WRR的优点是解决了SP队列中低优先级队列长时间得不到服务的问题，缺点是其按照报文个数进行调度，会由于报文长度变化导致无法保证每个队列固定的带宽。

WFQ加权公平队列为使带宽分配更加公平，不再像WRR那样以报文数为单位，而是以比特数为单位进行调度，从而防止长报文比短报文获得更多带宽，并减少大小报文共存时的时延抖动。

此外，为了实现更好的隔离性，满足不同维度的隔离需求，还可以采用多级分层队列，各级可采用不同的传输选择算法，实现丰富的调度策略。比如近年来提出的分层核心无状态公平队列HCSFQ，以及异步流量整形器ATS。

2软件队列到硬件队列

上面提到的队列策略都属于软件队列，流量首先通过802.1p/DSCP/IP等字段在分类器进行优先级映射，进入不同的软件队列，然后在调度器根据不同的调度策略进行出队；出队后进入到硬件队列中，最后从接口发送传输到下一跳。实际上，软件队列中存放的并不是真实的数据包，而是数据包的指针，指针就好比是数据包的名字，真实的数据包依然在缓冲区中，所以数据包的大小并不影响队列的长度，一个1500字节的数据包和一个10K的数据包在队列里占用的队列长度均为1，软件队列的总队列长度可以用队列管理工具调整[2]。

硬件队列是Tx输出队列，里面传输的是真实的数据包，其采用先进先出FIFO的方式，实现在接口的ASIC芯片上。每个物理接口上都有且仅有一个硬件队列,且不能被队列管理工具管理。硬件队列的深度一般只有2-3个包，当硬件队列没有被充满或者为空时，说明接口没有发生拥塞，一般数据不会经过软件队列，而会被直接放入硬件队列进行传输。

3软件定义队列与可编程队列

一方面，当前商用交换机里的队列调度策略都是选配的，即只支持诸如在某个端口关闭SP队列、开启WFQ队列之类的操作，无法灵活地定制特定的队列调度策略，因此软件定义队列的想法被提出。其借鉴软件定义网络中通过OpenFlow南向接口下发流表来实时改变转发行为的思想，希望在控制器中实现诸如OpenQueue[3]的接口，定义入队、调度、出队等基本原语，从而能够实时的进行添加队列、删除队列、改变优先级、改变调度算法等操作。理论上可以在每个端口定义65000[4]个虚拟队列，并采用不同的调度算法。

另一方面，P4等可编程交换机的兴起，激发了人们在可编程交换机中创新队列调度算法的设想。可编程队列中的可编程主要作用在流量管理器（TM, Traffic Manager）中的调度器上，通过改变数据结构、改变硬件设计等方式，针对特定场景实现更高效的队列算法。在2016年的SIGCOMM大会上MIT首次利用可编程PIFO队列[5]实现了WFQ等调度算法的调度器，并支持10Gbps的线速转发能力；Sharma提出可编程日历队列（Calendar Queues）调度器[6]来实现公平队列、pFabric等各种调度算法；近来SP-PIFO[7]调度器使用SP严格优先级队列实现了近似PIFO压入先出队列的调度效果，提升了队列在应对海量流量时的可扩展性。

4队列调度的粒度

队列调度的粒度是众多调度算法的兵家必争之地，由粗粒度到细粒度大致可分为每端口、每用户、每业务类、每队列、每流、每包。

每端口粒度的调度基本只能在出队时做端口限速，没有调度算法；每用户调度可以在边缘侧流量接入时保证用户业务间的良好隔离性；在入队映射时，用户的多种业务流可能被分类进不同的优先级队列；每队列调度即如严格优先级调度般的以队列间的调度顺序为最小调度单位；每流调度可以识别流ID，从而在不同流出队时进行每流粒度的限速和整形；每包调度是最细的调度粒度，比如PIFO队列，其能改变一个包在单个队列中的排队顺序。

调度粒度越细，网络服务质量越好，但所需要的开销也越大，比如每流调度往往需要维护每流的状态，缺少可扩展性，当有成千上万条流需要调度时，调度性能会变得很低。不同的调度粒度可以通过分层的多级队列调度来综合，比如下图的HQOS (Hierarchical Quality of Service）[8]技术。

下一节将介绍确定性网络中的队列增强机制，更多内容请看下回分解。

参考文献：
[1] 华为NE40E特性描述-QoS. https://support.huawei.com/enterprise/zh/doc/EDOC1100060834/b3e02b4b.
[2] 阿里云开发者社区-认识队列技术中的硬件队列和软件队列.
https://developer.aliyun.com/article/406920.
[3] K. Kogan et al. Towards Software-Defined Buffer Management. IEEE/ACM Transactions on Networking, vol. 28, no. 5, pp. 2337-2349, Oct. 2020.
[4] A. N. Abbou, T. Taleb and J. Song. A Software-Defined Queuing Framework for QoS Provisioning in 5G and Beyond Mobile Systems. IEEE Network, vol. 35, no. 2, pp. 168-173, 2021.
[5] Anirudh Sivaraman et al. Programmable Packet Scheduling at Line Rate. SIGCOMM ‘16.
[6] Naveen Kr. Sharma et al. Programmable calendar queues for high-speed packet scheduling. NSDI’20.
[7] Albert Gran Alcoz, et al. SP-PIFO: approximating push-in first-out behaviors using strict-priority queues. NSDI’20.
[8] HQOS简介. https://support.huawei.com/enterprise/zh/doc/EDOC1100198531/5da5e7a1.