队列调度算法的分析与研究.docxVIP

-1-

队列调度算法的分析与研究1

罗章庆

北京邮电大学网络技术研究院，北京(100876)

摘要：队列调度算法作为流量控制的关键环节，越来越受到人们的关注。本文首先介绍了队列调度算法在流量控制中的关键地位，然后讨论了现有队列调度算法，如基于优先级的调度算法、轮询调度算法与公平队列调度算法，而后对各种队列调度算法进行简要地描述，分析每种算法的性能及影响其性能的关键因素，这对队列调度算法的研究具有积极的意义，最后对队列调度算法的应用给与了指导性的建议。

关键词：队列调度算法；PQ；WRR；DRR；WFQ；Qos1．引言

随着网络应用日益广泛，不同用户根据自身需求可能要求不同的服务质量。有的用户可能需要低延时，有的用户可能需要高带宽，这些不同Qos是由网络中的交换节点通过流量控制来实现地，队列调度又是流量控制的关键环节，因此有必要对队列调度算法做一定的分析与研究，由图1流量控制框架可知，流量控制主要由分类器、丢包器、整形器和调度器四部分组成。

图1流量控制框架

假设现有N个不同的队列，当数据包到来时，分类器负责把数据包分类到相应的队列中，而分类的标准也是多种多样的，可以根据IP地址、端口号、tos值等对数据包进行分类，也可以对这些条件进行组合，产生更加复杂的分类条件。分类器处理完毕后，数据包被添加到相应的队列中，每个队列都有一个缓冲区，缓冲区的大小是有限的，因此当缓冲区满的时候就需要丢弃数据包，这便是丢包器的任务。最简单的是尾部丢弃策略，丢弃队列尾部的数据分组，更复杂的丢包策略是RED[7]算法。整形器是对队列中的数据包进行整形，使其满足一定的特征，整形器是可选的，一些流量控制的实现是没有整形器的，也就是说队列调度算法直接对队列中的数据包进行调度，队列调度算法的任务就是从N个队列中选择下一个要发送的数据分组。

队列调度算法根据其工作模式不同可以分为工作保持算法和非工作保持算法，对于工作保持算法只要队列中有等待分组，那么它就工作，而非工作保持算法并不能保证只要有等待分组，那么算法就工作，因为非工作保持算法一般是对整形器输出的分组进行调度，而不是直接对队列进行调度，因此只有整形器中有数据分组的时候调度算法才工作，由此可见工作保持算法具有更高的链路利用率，而非工作保持算法能对端到端时延及时延抖动进行控制。

11本课题得到国家863项目（No.2007AA01Z2A1，2006AA01Z229），国家自然科学基金项目（No

-2-

2．队列调度算法分析

下面的章节简单地介绍了各种调度算法，并分析了其性能。

2.1FCFS(FirstComeFirstServe)调度算法

FCFS是单队列调度算法，它把所有数据包不加区分的放在一个队列中，先到的数据包放在前面，后到的数据包放在后面，算法根据数据包的到达顺序对数据包服务，先到的数据包先服务，后到的数据包后服务，丢包也是采用简单的尾部丢弃策略。

FCFS算法的最大优点是实现简单、成本低。这也是其得到广泛应用的原因，但是由于FCFS对数据包不加区分，因此它无法提供不同的Qos，但是FCFS一般不单独使用，而是作为其他调度算法的基础和其他调度算法结合来提供不同的Qos。

2.2SFQ(StochasticFairnessQueuing)

随机公平队列严格来说应该不属于调度算法，因为其调度算法其实采用的RR，SFQ算法的核心思想是不断改变哈希算法而使数据包公平地得到服务。

图2SFQ

图2SFQ把数据分组看作是由不同的会话组成，理想情况下为每一个会话建立一个FIFO队列，然后采用简单轮询方式对每个队列而发送一个定量，由此可见每个队列的数据包都得到发送，因此SFQ是公平的。

但是为每个会话建立一个FIFO队列是不现实的，实际实现中队列个数是一定的，每个会话的数据包到底分配到哪个队列是由哈希函数决定的。由于队列的个数是有限的，导致不同会话的数据包可能分类到相同的队列，这样就会导致不同会话对资源的竞争，出现不公平现象。为了避免这种情况，尽量让不同的会话独占不同队列，哈希函数每经过一段时间就要改变（10ms），保证冲突只在一定的时间段内，这样就可以提高公平性。

SFQ公平性得到保证的关键在于哈希函数与哈希函数变更的时间间隔。良好的哈希函数能够让不同的会话尽量分布到不同的队列中，这样减少不同会话对资源的竞争，有效的提高公平性。当出现竞争的时候，哈希函数变更时间决定了竞争的持续时间，因此哈希函数变更时间越小，那么竞争持续的时间越小，但是哈希函数频繁的变更也是会消耗系统资源，因此选择合适的哈希函数与变更间隔是SFQ能