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

王甲，姜希（中國電子科技集團公司第20研究所，西安　710072）

?

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

王甲，姜希
（中國電子科技集團公司第20研究所，西安710072）

摘要：

關(guān)鍵詞：

0　引言

近年來，各種異構(gòu)網(wǎng)絡(luò)間通信需求劇增，特別在航空、航天和軍事通信領(lǐng)域，網(wǎng)間帶有時限的實時、近實時以及周期性消息的速率匹配問題逐漸突出。當(dāng)前常用的主動隊列管理算法加權(quán)公平隊列（WFQ）[1]、嚴格優(yōu)先隊列（SPQ）[2]和加權(quán)循環(huán)（WRR）[1-2]等，并未在算法模型中引入時限的約束，無法將時限引入隊列反饋中；來源于操作系統(tǒng)優(yōu)先級調(diào)度領(lǐng)域的最早時限優(yōu)先（EDF）策略將時限作為單一變量，在信道中低負載條件下具有良好的調(diào)節(jié)反饋作用，但在高負載、突發(fā)消息較多的情況下，無法體現(xiàn)高優(yōu)先級消息的優(yōu)先發(fā)送特性。一些對EDF策略的改進算法，如NEDF，能夠較好地調(diào)節(jié)同一時限條件下的優(yōu)先級特征，但無法解決高負載條件下大量中低優(yōu)先級消息被餓死的問題。

本文在分析已有主動隊列管理算法的基礎(chǔ)上，針對EDF現(xiàn)存缺點，結(jié)合工程實踐中優(yōu)先級反饋因素和低優(yōu)先級翻轉(zhuǎn)應(yīng)用的需求，提出一種EDF-FQ（Earliest Deadline First with Forecast Queue）具有預(yù)測隊列的最早時限優(yōu)先算法，該算法以信息的時限為基本特征，兼顧消息優(yōu)先級，并支持周期性低優(yōu)先級翻轉(zhuǎn)。

1　最早時限優(yōu)先算法（EDF）[3]

EDF算法是一種典型的時限驅(qū)動調(diào)度算法（DSS），其算法模型抽象出的單變量——絕對時限di（t）來決定其優(yōu)先級。每次進行調(diào)度時，對于當(dāng)前隊列中的每個成員，以絕對時限與當(dāng)前時間的差值Δti= di（t）-t來更新隊列成員的排隊順序。更新規(guī)則是：

每次調(diào)度后，當(dāng)前隊列Q總形成新的排隊順序：

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

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

2　具有預(yù)測隊列的最早時限優(yōu)先算法（EDF-FQ）

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

2.1建立典型應(yīng)用隊列模型

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

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

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

（2）Type Interval Message（TIM），其工程原型為周期發(fā)送的本地狀態(tài)信息，具有最低的優(yōu)先級，要求在N個消息周期內(nèi)每組至少發(fā)出1條TIM。

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

2.2EDF-FQ算法描述

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

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

圖1　EDF-FQ算法基本流程

圖2　EDF-FQ隊列算法隊列模型數(shù)據(jù)結(jié)構(gòu)描述

Q0、Q1的消息體要素一致，分別是待發(fā)消息、權(quán)值、TTL以及預(yù)計發(fā)送TTL。TIM消息由于其為周期狀態(tài)信息，因此在帶寬受限情況下，應(yīng)優(yōu)先考慮最有價值的新入隊信息，因此在消息體中加入了同組消息指針及同組消息數(shù)用以標(biāo)示相關(guān)新入隊消息。

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

●是分段函數(shù)，分段函數(shù)具有更好的適應(yīng)性；

●同一優(yōu)先級，相同TTL，權(quán)值相同；

●不同優(yōu)先級，相同TTL，WPH＞W(wǎng)PL。

②TTL指消息超時還需要經(jīng)歷的跳數(shù)（hop，每一次全局發(fā)送視為一跳）；

③預(yù)計發(fā)送TTL指發(fā)送完比本節(jié)點權(quán)值大的消息時，本節(jié)點剩余的TTL。

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

（3）更新各消息體元素。各個隊列每個消息體TTL皆遞減1，各節(jié)點按照對應(yīng)隊列的權(quán)重函數(shù)記為Fn重新計算權(quán)值，分別計算各個消息體的預(yù)計發(fā)送TTL，若該TTL不大于0，則直接丟棄該消息體。

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

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

圖3　EDF-FQ算法示例

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

2.3EDF-FQ算法仿真[5]

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

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

可以看出EDF-FQ算法在合理設(shè)置生成函數(shù)的前提下，在高負載且突發(fā)消息較多時，較EDF算法明顯的體現(xiàn)出優(yōu)先級的調(diào)節(jié)作用。特別在TIM消息較多情況時，突出了有效發(fā)送的效果，同時也避免了優(yōu)先級的因素導(dǎo)致TIM消息無法發(fā)送被餓死的現(xiàn)象。

3　結(jié)語

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

圖4　EDF與EDF-FQ仿真結(jié)果對比圖

參考文獻：

[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]姜希，王甲.面向隊列調(diào)度算法的通用驗證評估方法[J].科學(xué)技術(shù)與工程，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：

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

多優(yōu)先級；最早時限優(yōu)先；服務(wù)質(zhì)量；主動隊列管理

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

DOI：10.3969/j.issn.1007-1423.2016.14.004

作者簡介：

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

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

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

Multi-Priority；EDF；QoS；Active Queue Management