一種基于EDF-FQ的多優先級主動隊列管理算法

王甲，姜希（中國電子科技集團公司第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來更新隊列成員的排隊順序。更新規則是：

每次調度后，當前隊列Q總形成新的排隊順序：

｛E1，E2，E3，…，En｝其中?Ei的（di（t）-t）≤（d（i+1）（t）-t）

在EDF算法模型中，一個重要的基本假設即隊列元素間不存在優先級約束，該假設雖然簡化了模型，也造成了當EDF算法應用在具有優先級特征的隊列管理時，同時限不同優先級隊列元素的順序不確定性：不同優先級消息在時限逼近后將無差別對待，在高負載情況下，被發送的消息優先級具有明顯的隨機性，在統計學意義上即體現為發送的數量取決于該優先級消息占消息總數的比值，在極端情況下，存在高優先級元素總被低優先級元素無差別擠占而超時的問題。

2　具有預測隊列的最早時限優先算法（EDF-FQ）

EDF-FQ算法中，按照不同消息優先級對消息進行分類，并使用差異化的隊列管理機制管理各個隊列；使用權值（Weight）綜合衡量和調節不同隊列消息的發送能力；對消息發送時間進行預判，去除預判可能超時的消息以節省計算資源。下面，對EDF-FQ算法從隊列模型、算法描述和算法仿真進行介紹。

2.1建立典型應用隊列模型

首先，為描述EDF-FQ算法及其應用環境，抽象出以下典型單隊列模型。隊列有3種隊列元素，其類型分別是：

Priority High Message（PHM），其工程原型為控制類信息，具有較高的優先級（Priority）和較強的實時性，即生存時間（Time To Live，TTL）較長；

（1）Priority Low Message（PLM），其工程原型為一般信息，具有較低的優先級和較低的實時性，即TTL較短；

（2）Type Interval Message（TIM），其工程原型為周期發送的本地狀態信息，具有最低的優先級，要求在N個消息周期內每組至少發出1條TIM。

（3）隊列元素PHM、PLM是在整個發送時間[0，T]上隨機產生的，其總體產生概率服從以λ為期望的泊松過程（泊松流）模型[4]。上述每種隊列元素具有相同的長度，隊首以跳為單位進行發送，每跳僅能發送一個完整的隊列元素。

2.2EDF-FQ算法描述

本算法的實現可以細分為四個步驟，分別是隊列初始化、消息進入隊列、隊列更新、全局擇優和發送。算法基本流程如圖1所示。

（1）根據3種隊列元素特點，建立3個待發隊列，分別是PHM隊列（Q0）、PLM隊列（Q1）、TCM隊列（Q2）。進入的消息按照其類型分別進入相應隊列，并按照入隊順序依次鏈入隊列。每個隊列有若干屬性，分別是：隊列當前最大權值，隊列長度，隊列容量。圖2是以線性表形式描述該隊列模型的數據結構。

圖1　EDF-FQ算法基本流程

圖2　EDF-FQ隊列算法隊列模型數據結構描述

Q0、Q1的消息體要素一致，分別是待發消息、權值、TTL以及預計發送TTL。TIM消息由于其為周期狀態信息，因此在帶寬受限情況下，應優先考慮最有價值的新入隊信息，因此在消息體中加入了同組消息指針及同組消息數用以標示相關新入隊消息。

①權值是消息優先級、TTL、同類積壓數等因素的函數，其對應的權重函數記為Fn（XPri，XTTL，XOverStack）n= 1，2，3，遞增且時變；權值函數需要根據消息時效性和消息發送率要求具體設計，需要具有原則：

●是分段函數，分段函數具有更好的適應性；

●同一優先級，相同TTL，權值相同；

●不同優先級，相同TTL，WPH＞WPL。

②TTL指消息超時還需要經歷的跳數（hop，每一次全局發送視為一跳）；

③預計發送TTL指發送完比本節點權值大的消息時，本節點剩余的TTL。

（3）當有信道消息需要發送時，首先按照消息類型進入相應隊尾，即PHM進入Q0、PLM進入Q1、TIM進入Q2。更新各消息隊列頭元素。對TIM同組消息，即周期狀態信息，則鏈入該組消息“同組消息體”最末端，同時更新該組消息的“本組消息數”元素。

（3）更新各消息體元素。各個隊列每個消息體TTL皆遞減1，各節點按照對應隊列的權重函數記為Fn重新計算權值，分別計算各個消息體的預計發送TTL，若該TTL不大于0，則直接丟棄該消息體。

（4）每次發送時，僅比對各隊列頭元素，從頭元素中即可比對出Q0、Q1、Q2權值最大的消息體（Elemax），發送Elemax。

這里作簡單示例說明該管理算法。可參考圖3所示，該示例中Q0權值公式為W1=64/TTL，Q1權值公式為W2=32/TTL，Q2權值公式為W3=（8/TTL）n（n為同組消息體數，下同）。

圖3　EDF-FQ算法示例

圖3中表示了從某一跳至下一跳時隊列各節點的優先級和擇優情況。與當前時間的偏移量，由于發送速率一定時，那么在每次查詢時，可以計算出該節n點是否超時。消息每被查詢一次，首先判斷其是否超時，若超時則刪除該節點，否則其TTL遞減，并以TTL為自變量，計算并回填其節點中的“權值”屬性。若隊列中正在被遍歷的節點“權值”比隊列頭節點中所指示的節點權值大，則更新“隊列當前最大權值節點”為當前遍歷節點。特別的，對Q3隊列中某節點具有多個同源消息的情況，則需要對其權值運算公式進行變換，同源節點分支深度每加一，則權值公式變換一次，圖中變換規則為權值公式指數變換（每多一層同類積壓，n以一為步長遞增一次），從而使得經過若干次查詢后，深度較深的分支具有較高的發送權值。

2.3EDF-FQ算法仿真[5]

以某已實用系統信道發送能力、待發消息分類和消息生成規則為仿真輸入，分別設置該信道具有4包/s發送速率，消息配比為1：1：2，設置EDF-FQ的生成函數為：

以泊松分布在信道能力150％的重壓力下對EDF、EDF-FQ算法分別進行仿真試驗，并對比其有效發送量（TIM在其TTL內多條同源狀態信息發送一條即可反映其實際狀態），如圖4所示。

可以看出EDF-FQ算法在合理設置生成函數的前提下，在高負載且突發消息較多時，較EDF算法明顯的體現出優先級的調節作用。特別在TIM消息較多情況時，突出了有效發送的效果，同時也避免了優先級的因素導致TIM消息無法發送被餓死的現象。

3　結語

EDF-FQ算法在受限信道發送時對多優先級消息發送具有良好的適用性，但較EDF算法的在復雜度上有所提升，如何在保留EDF-FQ算法各項優勢的基礎上降低復雜度是今后值得研究的課題。

圖4　EDF與EDF-FQ仿真結果對比圖

參考文獻：

[1]Balogh T，Medvecky M.Performance Evaluation of WFQ，WF2Q+ and WRR Queue Scheduling Algorithms[C].Telecommunications and Signal Processing（TSP），2011 34th International Conference on，2011：136-140.

[2]Yue Qian，Zhonghai Lu，Qiang Dou.QoS Scheduling for NoCs：Strict Priority Queueing versus Weighted Round Robin[C].Computer Design：VLSI in Computers and Processors，（ICCD），IEEE International Conference on，2010，52-59.

[3]Alan Burns，Sanjoy Baruah.Sensitivity Analysis of Task Period for EDF Scheduled Arbitrary Deadline Real-Time Systems[C].Proceedings of 2010 3rd IEEE International Conference on Computer Science and Information Technology VOL.3，2010.

[4]Ferrari A，Letac G，Tourneret，J Y.Multivariate Mixed Poisson Distributions[C].Signal Processing Conference，2004 12th European，2014：6-10.

[5]姜希，王甲.面向隊列調度算法的通用驗證評估方法[J].科學技術與工程，2015，31：218-220.

A Multi-Priority Active Queue Management Algorithm based on EDF-FQ

WANG Jia，JIANG Xi
（The 20th Research Institute of CETC，Xi'an 710072）

Abstract：

To deal with the problem that EDF algorithm has a low adaptability to schedule queues with priority constraints，proposes an improved algorithm EDF-FQ considering priorities and priority reverse.It illustrates the queuing model，the principle，the implementation of EDFFQ.The simulation shows EDF-FQ can improve the efficiency of scheduling queues with multi- priorities.

Keywords：

針對有時限隊列調度經典算法——最早時限優先（EDF）算法中對有優先級約束隊列適應性較差的問題，提出一種具有優先級、優先級翻轉特征的預測隊列最早時限優先算法（EDF-FQ）。闡述EDF-FQ的隊列模型、算法思想和實現方式，并對EDF-FQ算法進行仿真，證明該算法在受限信道多優先級消息調度應用中良好的適用性。

多優先級；最早時限優先；服務質量；主動隊列管理

文章編號：1007-1423（2016）14-0019-04

DOI：10.3969/j.issn.1007-1423.2016.14.004

作者簡介：

王甲（1984-），男，，陜西西安人，碩士，工程師，研究方向為通信與信息系統。

姜希（1986-），女，黑龍江大慶人，碩士，工程師，研究方向為通信系統與系統仿真

收稿日期：2016-03-15修稿日期：2016-05-10

Multi-Priority；EDF；QoS；Active Queue Management