王甲，姜希（中国电子科技集团公司第20研究所，西安　710072）



一种基于EDF-FQ的多优先级主动队列管理算法

王甲，姜希
（中国电子科技集团公司第20研究所，西安710072）

摘要：

关键词：

0　引言

近年来，各种异构网络间通信需求剧增，特别在航空、航天和军事通信领域，网间带有时限的实时、近实时以及周期性消息的速率匹配问题逐渐突出。当前常用的主动队列管理算法加权公平队列（WFQ）[1]、严格优先队列（SPQ）[2]和加权循环（WRR）[1-2]等，并未在算法模型中引入时限的约束，无法将时限引入队列反馈中；来源于操作系统优先级调度领域的最早时限优先（EDF）策略将时限作为单一变量，在信道中低负载条件下具有良好的调节反馈作用，但在高负载、突发消息较多的情况下，无法体现高优先级消息的优先发送特性。一些对EDF策略的改进算法，如NEDF，能够较好地调节同一时限条件下的优先级特征，但无法解决高负载条件下大量中低优先级消息被饿死的问题。

本文在分析已有主动队列管理算法的基础上，针对EDF现存缺点，结合工程实践中优先级反馈因素和低优先级翻转应用的需求，提出一种EDF-FQ（Earliest Deadline First with Forecast Queue）具有预测队列的最早时限优先算法，该算法以信息的时限为基本特征，兼顾消息优先级，并支持周期性低优先级翻转。

1　最早时限优先算法（EDF）[3]

EDF算法是一种典型的时限驱动调度算法（DSS），其算法模型抽象出的单变量——绝对时限di（t）来决定其优先级。每次进行调度时，对于当前队列中的每个成员，以绝对时限与当前时间的差值Δti= di（t）-t来更新队列成员的排队顺序。……