基于类的加权公平队列调度方法及装置

摘要

本发明公开了一种基于类的加权公平队列调度方法及装置，该方法包括：根据接收到的报文所属报文类别的报文缓冲量和表征该报文类别允许使用带宽的分类令牌桶的容量，为报文分配表征报文发送等级的等级令牌；根据通过接口的报文的发送流量和表征接口总带宽的接口令牌桶的容量，确定当前调度周期内的接口带宽使用情况；根据预设的接口带宽使用情况与允许的发送等级的对应关系，确定与当前调度周期的接口带宽使用情况对应的允许的发送等级；将携带允许的发送等级的等级令牌的报文缓冲至报文发送队列中。该方法通过分类令牌桶和接口令牌桶控制报文发送，减少了报文缓冲队列数量，减少了报文调度的队列轮询，节约了系统资源，提高了系统性能。

说明书

技术领域

本发明涉及数据传输技术领域，尤指一种基于类的加权公平队列调度方法及装置。

背景技术

基于类的加权公平队列(Class-based Weighted Fair Queuing，CBWFQ)是服务质量(QoS)队列机制中的一种，CBWFQ增加了用户定制队列，是对加权公平队列(Weighted Fair Queuing，WFQ)标准功能的扩展，CBWFQ也包含了低延迟队列(Low Latency Queue，LLQ)，能够确保网络带宽按照用户定义在各类网络数据流之间按照设定规则公平分配。

现有技术中，基于类的加权公平队列调度是根据报文的分类规则，将不同分类的报文放入不同的队列中，在报文离开设备接口时进行队列带宽限制的相关操作，并且出队报文。如图1所示即为现有技术中基于类的加权公平队列调度的实现原理示意图，数据包的发送调度具体包括下列过程：

将需要由某个设备接口发送的数据包按照用户预先定义的分类规则进行分类。

其中，合乎用户自定义的同一个匹配规则的数据包将被当作同一个数据流放入同一个CBWFQ队列，不合乎用户自定义的匹配规则的将按照WFQ分类规则处理，例如，相同源IP地址、目的IP地址、源媒体接入控制(Media AccessControl，MAC)地址、目的MAC地址、源端口号、目的端口号、协议类型、服务类型(Type of Service，TOS)的报文属于同一个数据流，每一个数据流被分配到一个保留的WFQ队列中。例如图1中所示的队列1、队列2、......、队列N等。

在进行发送时，执行出队调度过程，按照CBWFQ设定的带宽分配规则分配带宽确定离开接口的数据包并进行发送。

可见，现有的加权公平队列调度，当用户定义了n个数据分类时，将会使用n个队列进行数据报文的缓冲；同时，对于非用户定义的数据分类又会使用WFQ分类规则进行处理，相当于又增加了多个缓冲队列。随着报文队列数量的增加，在报文离开接口时，由于需要轮询调度各个报文队列，将会出现频繁的队列调度切换操作，导致系统的性能下降，而一旦系统性能不足，服务质量也会显著下降或完全得不到保证。

发明内容

本发明实施例提供一种基于类的加权公平队列调度方法及装置，用以解决现有技术中基于类的加权公平队列调度过程中存在的轮询操作频繁，导致系统性能下降的问题。

本发明包括如下内容：

一种基于类的加权公平队列调度方法，包括：

根据接收到的报文所属报文类别的报文缓冲量和表征该报文类别允许使用带宽的分类令牌桶的容量，为接收到的报文分配表征报文发送等级的等级令牌；以及

根据通过接口的报文的发送流量和表征接口总带宽的接口令牌桶的容量，确定当前调度周期内的接口带宽使用情况；

根据预先设定的接口带宽使用情况与允许的发送等级的对应关系，确定出与所述当前调度周期内的接口带宽使用情况对应的允许的发送等级；

将接收到的携带所述允许的发送等级对应的等级令牌的报文，缓冲至报文发送队列中。

一种基于类的加权公平队列调度装置，包括：

令牌分配模块，用于根据接收到的报文所属报文类别的报文缓冲量和表征该报文类别允许使用带宽的分类令牌桶的容量，为接收到的报文分配表征报文发送等级的等级令牌；

带宽监控模块，用于根据通过接口的报文的发送流量和表征接口总带宽的接口令牌桶的容量，确定当前调度周期内的接口带宽使用情况；

等级确定模块，用于根据预先设定的接口带宽使用情况与允许的发送等级的对应关系，确定出与所述当前调度周期内的接口带宽使用情况对应的允许的发送等级；

发送调度模块，用于将接收到的携带所述允许的发送等级对应的等级令牌的报文，缓冲至报文发送队列中。

一种网络设备，包括：上述的基于类的加权公平队列调度装置。

本发明有益效果如下：

本发明实施例提供的基于类的加权公平队列调度方法及装置，根据接收到的报文所属报文类别的报文缓冲量和表征该报文类别允许使用带宽的分类令牌桶的容量，为接收到的报文分配表征报文发送等级的等级令牌；以及根据通过接口的报文的发送流量和表征接口总带宽的接口令牌桶的容量，确定当前调度周期内的接口带宽使用情况；根据预先设定的接口带宽使用情况与允许的发送等级的对应关系，确定出与所述当前调度周期内的接口带宽使用情况对应的允许的发送等级；将携带所述允许的发送等级的等级令牌的报文，缓冲至报文发送队列中。该方法通过分类令牌桶和接口令牌桶控制报文发送，实现了根据接口的拥塞程度调度和控制报文发送，且使得分类报文不必再各自进入各自的缓冲队列，只需允许携带相应等级令牌的报文缓冲进入统一的至少一个报文发送队列中发送即可，这有效的减少了报文缓冲队列数量，从而减少了报文调度的队列轮询，避免了频繁的调度切换操作，节约了系统资源，提高了系统性能。

附图说明

图1为现有技术中基于类的加权公平队列调度原理示意图；

图2为本发明实施例一中基于类的加权公平队列调度方法的流程图；

图3为本发明实施例二中基于类的加权公平队列调度方法的流程图；

图4为本发明实施例二中分类令牌的分类结构示意图；

图5为本发明实施例二中报文入队的流程图；

图6为本发明实施例二中报文出队发送的的流程图；

图7为本发明实施例中基于类的加权公平队列调度装置的结构示意图。

具体实施方式

本发明实施例提供的基于类的加权公平队列调度方法，首先为接收到的报文分配不同发送等级的等级令牌，然后，根据接口的拥塞程度和报文携带的等级令牌决定是否发送接收到的报文，实现基于类的加权公平队列的报文调度。具体实现过程通过下面的实施例进行说明。

实施例一：

本发明实施例一提供的基于类的加权公平队列调度方法，其流程如图2所示，执行步骤如下：

步骤S101：对接收到的报文进行分类。

接收到其他网络设备发送的报文后，首先根据用户定义的规则对报文进行分类，确定报文的分类号，并进行分类标识。

其中，满足用户定义的分类规则的报文按照用户定义的分类规则归入相应的类别，不满足用户定义的分类规则的报文按照加权公平队列默认的分类规则归入相应的类别，并给接收到的报文添加分类标识。

步骤S102：为分类后的报文分配表征报文发送等级的等级令牌。

为分类后的报文分配等级令牌时，一般根据根据接收到的报文所属报文类别的报文缓冲量和表征该报文类别允许使用带宽的分类令牌桶的容量，为接收到的报文分配表征报文发送等级的等级令牌。

其中，各类报文所对应的分类令牌桶有一个预先分配的容量值，各报文类别所对应的分类令牌桶的容量总和小于等于表征接口带宽的接口令牌桶的容量。根据各个分类令牌桶的容量为各个报文类别分别设定至少一个发送等级阈值，以表征该类报文的分类令牌桶的令牌分配情况。

在为接收到的报文分配等级令牌时，具体先根据接收到的报文的类别，确定该报文类别的报文缓冲情况，一般可以监控接收到的报文所属的报文类别的报文缓冲量。然后，比较该报文类别的报文缓冲量与该报文类别的发送等级阈值的大小关系，分别确定接收到的各个报文的发送等级，并为每个报文分配相应发送等级的等级令牌。

较佳的，在为报文分配等级令牌后，根据该报文类别的报文缓冲量更新该报文类别对应的令牌桶中的令牌数量。

因此也可以说是根据接收到的报文所属的报文类别的剩余令牌，为接收到的报文分配所属的报文类别的分类令牌桶中的发送等级最高的等级令牌。

步骤S103：根据通过接口的报文的发送流量和表征接口总带宽的接口令牌桶的容量，确定当前调度周期内的接口带宽使用情况。具体包括：

监控当前调度周期内通过接口的报文的发送流量。

判断发送流量与预先设定的至少一个流量等级门限的大小关系，确定表征接口带宽使用情况的流量等级；其中，流量等级门限根据接口令牌桶容量设定。例如：当发送流量小于等于流量等级门限时，认为接口带宽使用情况处于该门限对应的流量等级。

步骤S104：确定出与当前调度周期内的接口带宽使用情况对应的允许的发送等级。

预先设定接口带宽使用情况与允许的发送等级的对应关系，具体可以设定每个流量等级所对应的允许的发送等级。在步骤S103确定出接口带宽使用情况后，就可以根据预先设定的接口带宽使用情况与允许的发送等级的对应关系，确定出与当前调度周期内的接口带宽使用情况对应的允许的发送等级了。

具体根据预先设定的接口的每个流量等级与所允许的发送等级的对应关系，确定表征当前调度周期内的接口带宽使用情况的当前流量等级所对应的允许的发送等级。

步骤S105：判断接收到的报文携带的等级令牌是否是当前调度周期内所允许的发送等级的等级令牌。

也就是说，根据确定出的允许的发送等级和报文携带的等级令牌，判断接收到的各个报文是否能够被发送。具体是根据接收到的报文携带的等级令牌是否是当前调度周期内所允许的发送等级的等级令牌来确定的。

若是，则认为接收到的报文允许被发送，执行步骤S106；否则，认为接收到的报文不允许被发送，执行步骤S107。

步骤S106：将报文缓冲至报文发送队列中。

即将携带接口所允许的发送等级的等级令牌的报文，缓冲至报文发送队列中。其中，报文发送队列可以只有一个，也可以根据优先级设定两个或多个。此时的报文发送队列与类别无关，也就是说不用再根据类别缓冲报文之不同类别的发送队列中。

步骤S107：丢弃接收到的报文。

不符合发送等级的报文将不能被发送。

实施例二

本发明实施例二提供的基于类的加权公平队列调度方法，以包含两个报文发送队列为例进行说明，其实现流程如图3所示，执行步骤如下：

步骤S201：对接收到的报文进行分类。

具体划分方式同步骤S101。

例如：网络设备接收到的报文可能包含N个类别。

步骤S202：为分类后的接收到的报文分配表征报文发送等级的等级令牌。

具体分配过程同步骤S102。

分类令牌的分配结构可以如图4所示。可分配的总令牌数根据接口带宽确定，也就是说根据接口令牌桶的容量确定。然后将令牌分配给各个报文类别，得到各个类别的分类令牌桶。其中包括根据用户定义的分类规则确定的报文类别和根据加权公平队列默认的分类规则确定的报文类别。首先，为用户定义的类别(即定制类别)分配令牌，例如，分类令牌1、......、分类令牌N等，剩余的令牌再分配给默认的报文分类。例如：剩余令牌按照报文TOS优先级进行令牌发放，可以分为0-7共八级类别，然后根据当前存在的类别数进行分配。

例如：接口带宽为500M，分配给类别A的令牌桶1的容量(即该报文类别允许使用带宽)为50M，分配给类别B的令牌桶2容量的为40M，......，分配给类别X的令牌桶N的容量为10M，等等。所有类别的令牌桶的容量总和不大于接口带宽，即接口令牌桶的容量。每个类别对应保存自己当前令牌桶的可用令牌数量。

以类别A的令牌桶1为例，设置的发送等级阈值分别为50M和60M，通过这两个等级阈值将报文发送等级分为三级，其中，报文缓冲量小于等于50M时，表示所分配给该报文类别的带宽尚未使用完，对应的等级令牌为绿色令牌；报文缓冲量大于50M且小于60M时，表示所分配给该报文类别的带宽已使用完，但当接口带宽允许时，可以允许发送该部分报文，对应的等级令牌为黄色令牌，报文缓冲量大于60M时，表示所分配给该报文类别的带宽已使用完，且其缓冲量已经超过了分配给该报文类别的允许使用带宽设定的等级阈值范围，则只有当接口带宽相当空闲时，才可以允许发送该部分报文，对应的等级令牌为红色令牌。上述发送等级阈值可以根据系统的缓冲能力设定。

则当接收到的报文为类别A时，根据该报文类别的报文缓冲量为其分配绿色、黄色或红色的等级令牌。也可以说根据该类别的报文缓冲量和发送等级门限为报文着色，将报文标记为绿色、黄色、红色等。当报文缓冲量或说令牌桶的令牌分配达到相应发送等级门限时，为报文着相应发送等级的颜色。

如图3中所示，令牌桶2、3、......N的使用情况与令牌桶1类似，不再一一赘述。这样接收到的报文都被添加了不同颜色的等级令牌。

步骤S203：根据通过接口的报文的发送流量和表征接口总带宽的接口令牌桶的容量，确定当前调度周期内的接口带宽使用情况。具体包括：

例如：仍以接口带宽为500M为例，设定流量等级门限为400M和500M，当报文发送流量小于等于400M时，确认流量等级为绿色等级，即接口使用情况为空闲，当报文发送流量大于400M小于500M时，确认流量等级为黄色等级，即接口使用情况为正常；当流量大于等于500M时，确认流量等级为红色等级，即接口使用情况为拥堵。流量等级门限用于表征接口是否处于拥塞状态，其可以根据接口的物理线路发送能力进行调整，可根据接口初始发送能力进行初始化。

在设定了流量等级阈值后，则通过监控当前调度周期内通过接口的报文的发送流量，确认接口带宽的使用情况，与设定的流量等级阈值比较，确认接口带宽处于绿色、黄色还是红色的流量等级，从而可以知道接口的拥塞程度。

步骤S204：确定出与当前调度周期内的接口带宽使用情况对应的允许的发送等级。

预先设定接口带宽使用情况与允许的发送等级的对应关系，具体可以设定每个流量等级所对应的允许的发送等级。例如：表征接口带宽使用情况的流量等级为绿色时，可以发送携带的等级令牌为绿色、黄色和红色的所有报文；流量等级为黄色时，可以发送携带的等级令牌为绿色、黄色的报文；流量等级为红色时，只能发送携带的等级令牌为绿色的报文。

则在步骤S203确定了接口带宽使用情况所对应的流量等级之后，就可以确定允许发送报文的发送等级，例如：允许发送携带绿色等级令牌的报文，或允许发送携带绿色和黄色等级令牌的报文，或携带任何一种等级令牌的报文都能发送。

步骤S205：判断接收到的报文携带的等级令牌是否是当前调度周期内所允许的发送等级的等级令牌。

也就是说，根据接收到的报文携带的等级令牌是否是当前调度周期内所允许的发送等级的令牌确定报文是否能够被发送。

若是，则认为接收到的报文允许被发送，执行步骤S207；否则，认为接收到的报文不允许被发送，执行步骤S206。

例如：根据带宽使用情况确定当前流量等级为黄色，则若报文携带的是绿色和黄色的等级令牌，则该报文允许被发送，若报文携带的是红色的等级令牌，则该报文不能被发送。

步骤S206：丢弃接收到的报文。

携带的令牌不是允许发送等级的等级令牌的报文将被丢弃。

步骤S207：根据确定出的允许发送的报文所属的报文类别的优先级，将允许发送的报文缓冲至对应的优先级队列中。

以报文发送的优先级队列包括低延迟报文队列和质量服务QoS普通队列为例。其中，低延迟缓冲队列对满足低延迟规则的在发送能力之内的报文进行缓冲，普通报文缓冲队列，对非低延迟以外的处于发送能力之内的报文进行缓冲，则报文入队的流程如图5所示，包括：

步骤S207a：判断报文是否属于低延迟队列的报文类别。

若是，执行步骤S207b；否则，执行步骤S207c。

步骤S207b：将允许发送的报文缓冲至低延迟队列中。

步骤S207c：将允许发送的报文缓冲至质量服务QoS普通队列中。

例如：如果当前数据流匹配为语音或视频流，则为低延迟数据报文流；如果为网页请求或者FTP流则为普通报文流。在用户设置报文的分类时，需要同时为其制定单位时间内的发送能力，如果未进行发送能力的分配，则对接口的空闲带宽进行均匀抢占。

较佳的，各个分类的发送能力通过允许发送的报文数量或者比特流大小来体现，通过用户配置确定，对于定制队列的带宽进行严格保证，对于未分配的带宽则进行均匀抢占。例如：用户可以定义满足当前流为视频流时，其占用的带宽为接口带宽的20％(根据接口总带宽换算为比特数)或者为100,000数据包/秒(packets/s)。在比特数和允许发送的报文数量冲突时，取其小。

当设定的优先级队列比较多时，则需确定报文类别所属的优先级队列，并将报文缓冲至相应的优先级队列中。

步骤S208：根据缓冲队列的优先级出队发送报文。

仍以报文发送队列包括低延迟报文队列和质量服务QoS普通队列为例，则报文出队发送的流程如图6所示，包括：

步骤S208a：判断低延迟队列中是否有待发送的报文。

若是，执行步骤S208c；否则，执行步骤S208b。

步骤S208b：判断普通队列中是否有待发送的报文。

若是，执行步骤S208c；否则，返回继续执行步骤S208a。

步骤S208c：发送待发送的报文。

发送带发送的报文后返回继续执行步骤S208a，查看低延迟队列中是否有待发送的报文。

当设定的优先级队列比较多时，则需按照优先及顺序依次调度各个优先级队列。

也就是说，和现有实现方式不同，本申请可以只通过两个队列实现报文的缓冲。在报文入队阶段，直接对对超过发送能力的报文进行丢弃处理，保证报文能够出队，同时，保证低延迟缓冲队列的优先出队。

根据本发明实施例提供的上述基于类的加权公平队列调度方法，可以提供一种基于类的加权公平队列调度装置，该装置可以设置于用于报文传输的网络设备中，例如：路由器、交换机等。该装置的结构如图7所示，包括：令牌分配模块10、带宽监控模块20、等级确定模块30和发送调度模块40。

令牌分配模块10，用于根据接收到的报文所属报文类别的报文缓冲量和表征该报文类别允许使用带宽的分类令牌桶的容量，为接收到的报文分配表征报文发送等级的等级令牌。

较佳的，上述令牌分配模块10，具体包括：阈值设置单元101、第一监控单元102和比较分配单元103。

阈值设置单元101，用于根据分类令牌桶的容量为各个报文类别分别设定至少一个发送等级阈值。

第一监控单元102，用于监控接收到的报文所属的报文类别的报文缓冲量。

比较分配单元103，用于第一监控单元102得到的比较报文缓冲量与阈值设置单元101设置的发送等级阈值的大小关系，分别确定接收到的各个报文的发送等级，并为每个报文分配相应发送等级的等级令牌。

带宽监控模块20，用于根据通过接口的报文的发送流量和表征接口总带宽的接口令牌桶的容量，确定当前调度周期内的接口带宽使用情况。

较佳的，上述带宽监控模块20，具体包括：第二监控单元201和等级判断单元202。

第二监控单元201，用于监控当前调度周期内通过接口的报文的发送流量。

等级判断单元202，用于判断第二监控单元201确定出的发送流量与预先设定的至少一个流量等级门限的大小关系，确定表征接口带宽使用情况的流量等级；其中，流量等级门限根据接口令牌桶容量设定。

等级确定模块30，用于根据预先设定的接口带宽使用情况与允许的发送等级的对应关系，确定出与当前调度周期内的接口带宽使用情况对应的允许的发送等级。

发送调度模块40，用于将携带允许的发送等级的等级令牌的报文，缓冲至报文发送队列中。

较佳的，上述发送调度模块40，具体包括：判断单元401和调度单元402。

判断单元401，用于根据接收到的报文携带的等级令牌，判断该报文是否是当前调度周期内所允许的发送等级的报文。

调度单元402，用于当判断单元401判断为是时，将报文缓冲至报文发送队列中；否则，丢弃该报文。

较佳的，上述调度单元402，具体用于：根据确定出的允许发送的报文所属的报文类别的优先级，将允许发送的报文缓冲至对应的优先级队列中。

本发明实施例提供的上述基于类的加权公平队列调度方法及装置，根据每个报文分类的报文缓冲量和该报文分类的允许使用带宽，确定接收到的报文的发送等级，并根据接口的实际流量确定接口的允许发送等级，实现对接收到的报文的发送控制，从而不必在针对每个类别设定缓冲队列，只需将允许发送的报文缓冲至一个、两个或多个缓冲队列中，从而实现了缓冲队列的合并，使得分类报文不必再各自进入各自的缓冲队列，只需允许携带相应等级令牌的报文缓冲进入统一的至少一个报文发送队列中发送即可；当采用多个优先级队列缓冲时，只需将属于同一个优先级的各个类别的报文缓冲至该优先级队列中即可，在报文出队发送时，只需轮询各个优先级队列即可；从而有效的减少了队列轮询的切换操作，避免了频繁的调度切换操作所带来的系统资源的浪费，节约了系统资源，提高了系统的性能。

且本申请中通过接口令牌和分类令牌两级令牌来控制报文发送，分类令牌和分类号关联，实现了根据接口的拥塞程度调度和控制报文发送，有效的协调了接口发送能力和各类别的报文的允许发送量，最大限度的提高了带宽的利用率，避免了现有技术中仅根据类别和优先级为各个类别的缓冲队列分配带宽多带来的带宽分配不均、以及不能根据动态需求实时调整的问题。且有效的解决了现有技术中低延时队列中报文的大延时，也平滑普通队列由于调度不均衡出现的大延时情况，保证了同一优先级报文的先进先出原则。

由于分类令牌桶中的令牌可以根据当前类别的缓冲情况动态更新，从而仅采用单一或几个优先级队列即可实现现有技术中采用多个类别队列缓冲、轮询调度时的控制效果，且每个类别剩余的允许使用带宽可以根据优先级和活跃程度在设定的发送等级阈值范围内动态更新分配，确保数据量大的数据流能够得到及时的发送。

例如：如果存在5个用户设定的低延迟队列，按照以前的方法，则在每次调度时都需要轮询这5个队列，这时，如果第一个队列在发送能力之内一直有报文发送，则其后的低延迟队列中的报文延迟时间将增大。这种影响对最后轮询到的队列影响更明显，普通队列和低延时队列类似。而采用单个队列缓冲则能保证先入队列的报文先发送，能够更大程度上满足报文的低延时要求。

较佳的，可以根据视频和非视频的数据流对时延的不同要求将优先级队列设置为低延时队列和普通队列，在根据上述方式确定进入这两个队列的报文后，在出队发送时只需轮询这两个队列即可。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。