基于多级队列调度模型的研究

王 琳，吉 萌

(1.光纤通信技术和网络国家重点实验室，湖北武汉430074;2.武汉烽火网络有限责任公司，湖北武汉430074)

随着用户数量的持续增长和网络业务的丰富化，传统的QoS已无法保证每个用户的业务质量。而层次化QoS(Hierarchy QoS)，通过建立多级的调度器，把多个端口的QoS通过树形结构来进行调度，可实现多业务多用户的灵活调度，提供更加精细的服务。本文以某高端路由器为背景，研究以太网多级队列调度的模型和算法。

1 多级队列调度原理

1.1 分级调度依据

层次化QoS的核心指导思想是QoS处理能真实体现网络拓扑结构和业务转发路径［1］。根据DSL论坛的TR-059协议定义的层次化QoS的基本模型，调度器的层次可分为五层:Session Scheduler→VC Scheduler→VC Group Scheduler→VP Scheduler→ Physical Port Scheduler［2］。调度的根节点为Physical Port Scheduler，是流量的汇聚点，叶子节点为Session Scheduler的调度队列，功能是确定输出端口在下一个时刻，从哪个队列中输出数据包［3］。分支节点为中间的各级调度器。TM(Traffic Management)调度器的作用是决定数据包将从哪一个队列中传送，调度节点是其一个重要的模块。父调度节点和其所属的子节点为一个调度单元，作用是完成调度的配置及策略。分层依据包括端口(LAN、WAN)、VLAN、服务(逻辑概念)、COS/DSCP/TOS、ETH Type、IP 地址、TCP/UDP 端口号等［4］。

1.2 调度节点

调度节点的处理包括调度逻辑和状态计算。调度逻辑可以通过改写该调度节点的寄存器和子调度节点的寄存器进行配置。状态计算逻辑输入包括整形器的状态、所选择的子调度节点(winner节点)和本地的配置，可将输入转换成从当前的调度节点传递到其父调度节点的调度参数。状态计算逻辑的输出有节点的可利用性、调度的优先级和传播的优先级。节点的可利用性是指该节点可用来传输数据;调度的优先级是指父调度节点调度优先级，即使用哪个调度器的调度逻辑，根据其选择子调度节点。传播的优先级是指一旦一个子调度节点被当前的调度节点的调度逻辑选择，子调度节点将优先级水平传播到父调度节点。传播优先级也是处理用户调度层(subscriber)时延敏感数据流量的一种方法。

1.3 调度单元

调度单元包括状态寄存器、配置寄存器和子队列寄存器。调度单元的队列状态和调度状态存放在状态寄存器中。队列状态是指当前各个队列的数据情况，即在调度过程中队列中有无数据或者有多少数据;调度状态的作用可以根据上一次调度策略的结果作为本次调度的依据。如配置了调度策略RR后，可将上一次轮询后的队列状态作为这次调度的依据。配置寄存器可以配置调度策略为SP、RR、WRR，以及调度权重weight的值。

1.4 转发类

转发类(ForwardingClass)是调度策略树中的一个调度实体，对应于树中的叶子节点。一个转发类与一个调度队列相对应。根据设置的映射关系，报文会进入不同的调度队列。系统共有4 种预定义转发类，即 BE，AF，EF，NC［4］，与该 4 种转发类对应的参数信息将决定调度队列的行为。BE(BestEffort)对应的业务类型是尽力而为的业务，如普通网页浏览;AF(AssuredForwarding)对应传输质量有保障的业务，如VPN、数据报文的传输;EF(ExpeditedForwarding)对应对延时/抖动敏感的业务，如IP语音、IPTV报文的传输;NC(NetworkControl)表示转发业务具有最高优先级，如网络控制报文的传输。

2 多级队列调度模型及流程

2.1 多级队列调度模型

以五级调度为例，如图1所示，数据包存储在大小为64×103的FIFO队列，即session队列中，大小为64×103的session队列映射到16×103的A级节点，1×103～16×103的A级节点映射到4×103的B级节点，1×103～4×103的B级节点将映射到512个C级节点，1～512个C级节点映射到56个端口，即根节点。对于每个根节点端口，B和C级节点对应于逻辑接口和服务，A级节点对应于用户，队列对应于各种服务应用。调度器的层次决定了HQOS能否应用到拓扑结构更复杂的情况，层次越多，可以应用的场合越多，可提供的服务越精细。对于调度层次不需要五级的调度，A级和B级可以配置成透明的虚节点，即通过禁用需要设置成透明节点的所有整形和调度特征，并连接父节点和孩子层节点到透明节点。

调度节点在子节点中执行调度，一个或多个子节点可以映射到一个父节点。子节点到父节点之间的映射是灵活的。整个的调度过程从队列级别的调度开始，队列级的调度可以获取队列的状态，确定配置的三重信息(资格、调度优先级和传播的优先级)，并将配置信息传播到其父调度节点(A级节点)。

图1 五级调度模型结构

通过配置某一层节点的寄存器到子节点和父节点可完成调度树分层的配置，只有一系列连续的节点才可以映射到父调度节点。有两种类型的映射关系:

1)从上到下的映射，通过定义映射的范围，在子节点层定义开始节点和结束节点来完成。

2)从下到上的映射，通过一对一的映射，子节点层被映射到父节点层。

为了保持分层数据库的一致性，根据节点配置的子节点映射范围，所有的子节点应该指向它们属于的同一个父节点。

调度树的多层结构使得具有嵌套关系的父子节点得以存在。所以在子节点对流量进行分类和调度后，从下一级汇聚的流量将会由父节点上配置的分类规则和控制参数进行再一次的流量管理。节点可以针对不同的分类需求(如用户、业务、流量类型等)配置分类规则和控制参数，并且在不同的节点上还可以对流量进行不同的操作处理，从而可实现多层次、多业务、多用户的流量管理［5］。

2.2 多级调度流程

对于一个五级调度的模型，可以采用流水作业机制进行调度。每级的调度都是相互独立并且类似的。每级调度之间的通信通过先进先出FIFO(FirstInFirstOut)机制完成［6］。假设有N个数据流量需要处理，需要在queues、A级、B级、C级和Port五级调度器组成的流水线完成流量处理，流量处理的顺序为从左到右。五级调度可同时进行操作，保证了调度的效率。每级的调度流程如图2所示。

1)读取上一级的FIFO接口中存储的队列调度的队列信息，如队列ID到本级的调度器。

2)通过读取队列信息，可得到其作为父调度器的信息和调度单元的信息，包括配置信息和状态信息，根据配置信息中的调度算法和队列的状态进行下一轮的调度，同时可获取队列的优先级传播到下一个调度节点。

根据调度单元中状态信息和配置信息，队列的优先级信息，以及令牌桶的状态整形以及调度，然后在下一级的FIFO接口中写入调度结果并传递给下级调度模块。

图2 某一级调度机制

3 以太网接口的多级调度实验仿真及分析

3.1 以太网接口多级调度的实验仿真

将该多级调度模型用于以太网接口二级调度，测试拓扑如图3所示，测试仪表为Spirent TestCenter，选择端口GE3/1/1，GE3/1/2，GE3/1/3作为测试端口，仪表发包给端口GE3/1/1和GE3/1/2，仪表从端口GE3/1/3收包。该模型在出端口限速500 Mbit/s，以VLAN来区分不同的用户群，每个用户的多种业务都在一个VLAN内承载。接入网络设备的用户分为个人用户和企业用户。对于企业网用户数据不区分数据类型，都要求优先发送;而对于个人用户数据则要根据报文优先级进行调度，因此需要采用HQoS功能来实现需求。

图3 以太网接口二级调度测试拓扑图

承载个人用户群A的Service VLAN ID范围是100～299，业务类型分为以下4种:VoIP业务，具有最高优先级，优先级为6的流量最小带宽保证为20 Mbit/s，优先级为7的流量最小带宽保证为30 Mbit/s;VoD业务，具有较高优先级，IEEE802.1p优先级为4、5;VPN业务，具有普通优先级，IEEE802.1p优先级为 2、3;HTTP浏览业务，最低优先级，IEEE802.1p优先级为0、1。承载企业用户群的Service VLAN ID范围为500～506，501～503为A组企业用户，504～506为B组企业用户。企业用户群总流量要求限速100 Mbit/s，最小带宽保证为50 Mbit/s。

在调度处理中，需要首先先调度企业网的数据，完成后再调度个人用户的数据。在调度企业网的数据时，按照2∶1的比例对A组企业用户和B组企业用户进行调度。在调度个人用户数据时，首先调度VoIP业务的数据，完成后再轮询调度VoD、VPN、HTTP 的流量，调度比例为 3∶2∶1(调度 3 个VoD报文后，调度2个PN报文，再调度1个HTTP报文)。

在建立调度树模型的过程中，对于企业网用户的流量，可以将其配置为父转发组，其中嵌套6个子转发组，分别对应A组和B组企业用户的共6个VLAN的数据，然后为分属不同用户的转发组配置 WRR调度权重，实现按比例进行调度的需求。最后，为父转发组关联SP转发策略，使企业网用户流量得到优先调度，并通过流量整形和最小带宽保证实现流量速率的控制。对个人用户的各种流量，根据其IEEE802.1p优先级映射到不同的本地优先级，并匹配到8个转发组中。为VoIP业务的转发组关联 SP转发策略、配置最小带宽保证，使其优先被调度。其余队列则采用WRR队列调度，并配置相应的权重值，实现不同的调度比例。根据以上思路，建立的一个二层调度树模型如图4所示。

图4 二层调度树模型

在建立完调度模型后，在出端口应用该多级调度模型。通过测试仪表向端口打流来测试HQoS性能。个人用户和企业用户调度测试结果分别如表1和表2所示。

表1 个人用户业务调度测试情况 Mbit/s

表2 企业用户业务调度测试情况 Mbit/s

3.2 以太网接口多级调度的实验仿真分析

从测试结果来看，在网络拥塞的情况下，首先要保证企业网用户200 Mbit/s的最小带宽。然后进行企业网用户组的调度，根据所配置的权重和WRR算法进行调度，并根据配置的CIR限速值对企业网总的数据流进行整形处理。企业网用户数据处理完后，接着处理个人用户的业务数据。在调度中，对于个人用户的实时业务VoIP按最高优先级处理，在保证其最小带宽的情况下可实现语音数据快速转发，从而保证IP语音通信的质量。VoD，VPN和HTTP业务根据配置权重按照WRR算法进行调度，可使较高优先级的业务得到较大的带宽，使得VoD业务能得到较多的流量，从而保证视频业务的质量，而优先级最低的HTTP业务也不会因为优先级低导致“饿死”现象的发生。

由上可知，每级调度可以采用不同的调度算法，调度级数也可灵活多变，可以根据队列需求选择调度级数［7］。多级调度模型可对不同用户的不同业务流量进行有效的限速、带宽管理等控制操作，且在保证高优先级业务的前提下，可充分地利用带宽资源。

4 小结

一个灵活映射、灵活配置的多级调度树可用于实现多用户、多业务的流量管理。配置调度节点和调度单元的属性可以配置调度算法、整形器以及权重。通过一个FIFO多级流水作业机制来实现调度过程，每级调度相互独立，同一时刻多级调度同时进行。从上一级FIFO接口中获取上一级队列调度的队列信息，在调度操作完成后写入FIFO接口，确保了调度的灵活与高效。根据不同的应用需求，应用该调度模型在用户类别和业务类型较多的场合，可有效保证每种业务以及每个用户或用户组的服务质量。

［1］刘辰.基于DiffServ模型的层次化QoS研究［D］.南京:南京航天航空大学，2008.

［2］杨宏亮.层次化QoS流量控制技术在PTN传输网络中的研究与应用［D］.银川:宁夏大学，2013.

［3］俊超，王爱国.流量管理中队列调度算法研［J］.电视技术，2013，37(17):102-105.

［4］肖恒杰.家庭网关中分层服务质量管理功能的设计与实现［D］.武汉:华中科技大学，2010.

［5］黎晓亮，陈晓梅.DiffServ网络中的分层流量整形及改进［C］//2010通信理论与技术新发展——第十五届全国青年通信学术会议论文集(下册).［出版地不详］:中国通信学会青年工作委员会，2010:265-269.

［6］谢延婷.一种基于分布式系统的队列多级调度算法［J］.贵阳学院学报，2012，7(3):33-36.

［7］张蕾，戴锦友，基于交换芯片的3级调度算法的研究与实现［J］.电视技术，2012，36(9):117-119.

［8］刘阳，季新生.一种支持实时业务QoS的跨层分组调度方案［J］.计算机应用研究，2011，28(5):1810-1813.