基于排隊論的實時以太網(wǎng)緩存隊列優(yōu)化算法

金海波， 仲崇權(quán)

（大連理工大學 電子信息與電氣工程學部，遼寧 大連 116024）

0 引 言

目前工業(yè)以太網(wǎng)采用全雙工通信、信息優(yōu)先級以及虛擬局域網(wǎng)等技術(shù)使其響應(yīng)時間達到5～10ms.然而對于復(fù)雜高精度網(wǎng)絡(luò)控制系統(tǒng)該響應(yīng)時間仍不能滿足其要求.因此為了提高工業(yè)以太網(wǎng)的實時性，各大公司及組織在IEEE802.3標準的基礎(chǔ)上，對工業(yè)以太網(wǎng)進行改進和擴展，并各自提出自己的技術(shù)方案.按照國際電工委員會IEC/SC65C對實時以太網(wǎng)的定義，這些技術(shù)方案都做到了與標準以太網(wǎng)的無縫連接且響應(yīng)時間小于1ms.因此它們是真正意義上的實時以太網(wǎng)（real－time Ethernet，RTE）.為了規(guī)范各種 RTE技術(shù)方案，2003年5月，國際電工委員會IEC/SC65C專門成立了WG11實時以太網(wǎng)工作組，負責制定IEC61782－2“基于ISO/IEC8802.3的實時應(yīng)用系統(tǒng)中工業(yè)通信網(wǎng)絡(luò)行規(guī)”國際標準[1].該標準收錄并出臺了11種實時以太網(wǎng)通信行規(guī)集（communication profile family，CPF）， 包 括Ethernet/IP（CPF2）、Profinet（CPF3）、P－net/IP（CPF4） 以 及 Modbus－RTPS（CPF15） 和SERCOS－Ⅲ（CPF16）等 標 準. 我 國 的 EPA（CPF14）標準也被收入其中.由此可見在提高以太網(wǎng)的實時性及對以太網(wǎng)進行規(guī)范方面，國內(nèi)外的專家學者、各大公司及組織都做出了巨大貢獻.

然而這些被列入標準的RTE技術(shù)方案在訪問控制層保留了CSMA/CD協(xié)議，這勢必導致在解決沖突時，排隊延時具有很大不確定性.針對這一問題，專家學者們一直不懈努力相繼提出了許多改進方法，其中有采用實時交換機技術(shù)的硬件改進方法，有采用改進協(xié)議和信息調(diào)度的軟件方法，也有采用將排隊論用于端到端時延分析的研究方法.硬件改進方法由于其物理元器件的限制其改進難度很大，而改變協(xié)議和信息調(diào)度的軟件方法作為以太網(wǎng)實時通信的主要研究方向之一取得了一定的研究成果.如Liu等提出的固定優(yōu)先級的單調(diào)速率（rate monotonic，RM）算法和最小截止期優(yōu)先（earlier deadline first，EDF）算法[2]，以及 Sha等提出 的 Priority Ceiling Protocal[3]，它們都在一定程度上有效地減小了改變優(yōu)先級帶來的影響，但這些確定性調(diào)度方法對實時以太網(wǎng)本身的總體性能指標及應(yīng)用運行性能的研究還很欠缺[4].排隊論用于分析實時以太網(wǎng)通信過程具有很大的優(yōu)越性，主要體現(xiàn)在：（1）容易建立通信過程（發(fā)送、接收和處理過程）的排隊模型，便于利用經(jīng)典的排隊論來處理問題；（2）拋棄了次要因素，一定程度上簡化了通信模型，方便建模和分析.因此它能揭示排隊概率的規(guī)律性，建立系統(tǒng)的優(yōu)化方法，對實時以太網(wǎng)進行準確的性能預(yù)測、分析和評估.目前利用排隊論研究實時以太網(wǎng)延時的文獻層出不窮[5～8].文獻[5]給出了基于隨機輸入源為Markov狀態(tài)下的實時通信優(yōu)化策略.文獻[6]用隨機理論對準平穩(wěn)衰減信道下的速率進行了優(yōu)化并給出性能分析，但并沒有考慮發(fā)送端及中繼器中延時對通信性能的影響.文獻[7]構(gòu)造了一種在共享緩沖區(qū)中FIFO和LIFO兩種隊列并行工作的回歸結(jié)構(gòu).然而這種結(jié)構(gòu)需要增加額外存儲單元來保證性能的穩(wěn)定性.文獻[8]給出一種分析大量信息作為輸入源時且隊列中每個元素賦予相同權(quán)值下的整個排隊系統(tǒng)隊長分布特性的方法.該方法只從隊長的分布特性來研究排隊系統(tǒng)的性能，并沒有對隊長進行優(yōu)化.

由此可見排隊論應(yīng)用在通信領(lǐng)域是近年來的研究熱點，但也存在許多問題有待解決.針對數(shù)據(jù)幀在發(fā)送節(jié)點及中繼器緩存隊列中排隊延時給通信性能造成一定影響這一問題，本文用排隊論建立基于損失制的以太網(wǎng)傳輸性能的數(shù)學模型，并給出該模型的目標函數(shù)，推導目標函數(shù)取最小時的最佳緩存隊列長度.

1 以太網(wǎng)緩存隊列模型分析

數(shù)據(jù)幀從發(fā)送節(jié)點到接收節(jié)點傳輸過程中共經(jīng)歷以下幾個環(huán)節(jié)：應(yīng)用程序產(chǎn)生數(shù)據(jù)幀后將其發(fā)送到網(wǎng)絡(luò)接口卡（net interface card，NIC）緩存隊列中等待發(fā)送；當以太網(wǎng)啟動一個通信周期后，NIC緩存隊列中的數(shù)據(jù)幀被發(fā)送到以太網(wǎng)介質(zhì)中傳輸；經(jīng)過若干個中繼器（路由器、中間節(jié)點、網(wǎng)關(guān)節(jié)點等）最終到達接收節(jié)點.該過程如圖1所示.

圖1 以太網(wǎng)傳輸模型Fig.1 Transmission model of Ethernet

從圖1可以看出，數(shù)據(jù)幀傳輸過程中網(wǎng)絡(luò)延時包括以太網(wǎng)介質(zhì)的傳輸延時和經(jīng)過緩存隊列時的排隊延時.由于目前工業(yè)以太網(wǎng)基本采用高速現(xiàn)場總線作為實時傳輸介質(zhì)[9]（100MB以太網(wǎng)）且傳輸距離較小，在以太網(wǎng)介質(zhì)上的延時顯得微乎其微.而數(shù)據(jù)幀在緩存隊列中等待發(fā)送時，如果一次傳輸周期內(nèi)沒能及時發(fā)送需要等待下一次傳輸周期到來時才能發(fā)送，就會產(chǎn)生較大的排隊延時.因此端到端的網(wǎng)絡(luò)延時主要體現(xiàn)在排隊延時上.而產(chǎn)生排隊延時的緩存隊列包括發(fā)送節(jié)點緩存隊列和中繼器緩存隊列.不同物理設(shè)備上的緩存隊列沒有本質(zhì)區(qū)別，都是為減少數(shù)據(jù)幀丟失而開辟的存儲區(qū).因此可以將不同設(shè)備的緩存隊列作為統(tǒng)一的模型來分析.下面就不同設(shè)備數(shù)據(jù)幀在Linux協(xié)議棧緩存隊列中的發(fā)送過程進行統(tǒng)一分析.

圖2中，數(shù)據(jù)幀首先經(jīng)過入口函數(shù)進入鏈路層，之后由入隊函數(shù)進入緩存隊列.當以太網(wǎng)通信周期到來時，數(shù)據(jù)幀由出隊函數(shù)出隊并進入物理層入口函數(shù)得以最終發(fā)送.以上即為數(shù)據(jù)幀在Linux數(shù)據(jù)鏈路層協(xié)議棧中的發(fā)送過程，從發(fā)送過程也可看出，時間延遲主要體現(xiàn)在數(shù)據(jù)幀進入緩存隊列后的排隊延時上.因此如何減小排隊延時是提高通信性能的關(guān)鍵.

圖2 數(shù)據(jù)幀在Linux鏈路層發(fā)送流程Fig.2 Data frames′transmission in Linux′s data link layer

2 數(shù)學模型建立及優(yōu)化

對在Linux鏈路層發(fā)送數(shù)據(jù)過程分析的基礎(chǔ)上，建立與之對應(yīng)的數(shù)學模型.假設(shè)上位機中數(shù)據(jù)幀發(fā)送任務(wù)相互獨立且發(fā)送次數(shù)沒有限制，則由排隊論可知發(fā)送數(shù)據(jù)幀過程服從無限源的Poisson分布[10、11].設(shè)單位時間內(nèi)進入緩存隊列的平均數(shù)據(jù)幀個數(shù)（即數(shù)據(jù)幀的平均到達速率）為λ，則到達時間間隔服從參數(shù)為λ的負指數(shù)分布，其分布密度函數(shù)為

設(shè)實時以太網(wǎng)在單位時間內(nèi)傳輸數(shù)據(jù)幀的平均個數(shù)（即實時以太網(wǎng)的平均傳輸速率）為μ（μ＞λ）.則傳輸強度為

當數(shù)據(jù)幀排隊長度L過大時，以太網(wǎng)處于繁忙期，其負載過大，勢必會導致隊尾的部分數(shù)據(jù)幀在一次現(xiàn)場總線（實時以太網(wǎng)的一種）傳輸周期內(nèi)不能及時傳輸而被丟棄，只能等到下一次傳輸周期到來時重新申請傳輸，從而產(chǎn)生較大的排隊延時，對系統(tǒng)性能造成一定的影響.相反如果數(shù)據(jù)幀排隊長度過小，現(xiàn)場總線處于閑置期，其利用效率很低.因此如何確定適當?shù)木彺骊犃虚L度使隊列中數(shù)據(jù)幀都能成功發(fā)送且以太網(wǎng)利用率最高是本文研究的核心問題.為了研究問題方便，做出如下假設(shè)：

設(shè)最佳隊列長度為Lo，當隊列長度L＞Lo時，不能及時發(fā)送而被丟棄的每個數(shù)據(jù)幀的損失代價（即權(quán)值）為c1，當隊列長度L＜Lo時，沒有及時到達隊列造成現(xiàn)場總線閑置的每個數(shù)據(jù)幀的損失代價為c2.第n個進入隊列的數(shù)據(jù)幀的概率為Pn.由于該排隊模型是 M/G/1/∞ 模型，由生滅過程的平穩(wěn)分布求解公式可得

其中

所以得

由式（4）可知Pn服從幾何分布，且Pi＞Pj，i＞j.當現(xiàn)場總線處于繁忙期時，不能成功傳輸而被丟棄的平均數(shù)據(jù)幀數(shù)記為Nd，則

當現(xiàn)場總線處于閑置期時，沒有進入隊列而不能及時傳輸?shù)钠骄鶖?shù)據(jù)幀數(shù)記為Np，則

由于以太網(wǎng)繁忙與閑置都會給系統(tǒng)帶來一定的損失，在一次傳輸周期中，兼顧這兩方面的因素，將通信損失代價記為

將式（7）作為目標函數(shù).確定該目標函數(shù)取最小值時對應(yīng)Lo的值，即損失代價最小時的最佳隊列長度.下面推導式（7）：

對上式右端第一項的求和進行化簡：

將式（9）代回式（8）得

利用邊際法求解式（10），使F（Lo）取最小的Lo應(yīng)滿足

解上述不等式組得

因為Lo表示隊列長度，即Lo取值必須是一整數(shù)，所以取Lo為

此時Lo即為所求，其中表示下取整.

一般認為申請發(fā)送的數(shù)據(jù)幀在緩存隊列中沒能及時傳輸而被丟棄這種損失對控制系統(tǒng)性能的影響較大，即損失代價c1較大.而現(xiàn)場總線閑置這種損失對控制性能的影響較小，即損失代價c2較小.所以滿足c1≥c2.

3 仿真實驗

由于實時以太網(wǎng)的傳輸速度可達100Mbit/s.設(shè)平均傳輸速率為12.5f/ms，即μ＝12.5.節(jié)點的平均申請速率為10f/ms，即λ＝10.則傳輸強度ρ＝0.8.對于損失代價c1、c2給出3種不同的組合并分別代入式（13）得到對應(yīng)的Lo，如表1所示.

表1 損失權(quán)值與最佳隊列長度關(guān)系Tab.1 Relationship of optimal queue length and loss weight

針對3組最佳隊列長度，用蒙特卡羅方法在Matlab2006a環(huán)境下進行了仿真實驗，并在相同參數(shù)下給出文獻[8]WFQ（weighted fair queuing）算法結(jié)果.實驗結(jié)果如圖3所示.

從理論結(jié)果和實驗結(jié)果都可以看出，當對丟棄的數(shù)據(jù)幀賦較大權(quán)值時（即c1較大時），說明以太網(wǎng)處于繁忙期，進入以太網(wǎng)的數(shù)據(jù)幀較多，為了減少數(shù)據(jù)幀不能及時傳輸而被丟棄就需要更多的緩沖區(qū)來臨時存儲，從而避免對通信性能造成更大的影響.而當c1較小時，說明網(wǎng)絡(luò)處于閑置期，進入以太網(wǎng)的數(shù)據(jù)幀較少，這就不需要很大的緩沖區(qū).然而這種情況雖然沒有丟包現(xiàn)象，但是網(wǎng)絡(luò)利用率不高.另外從3組結(jié)果也能看出，理論分析得到的最優(yōu)隊列長度與實驗結(jié)果完全吻合.

圖3 系統(tǒng)損失值隨隊列長度變化關(guān)系Fig.3 Relationship between system loss and queue length

從對比結(jié)果中可以看出，第1組權(quán)值下，本文得到的系統(tǒng)損失值比 WFQ算法平均低0.15.第2組平均低0.3.第3組平均低0.21.這說明對于系統(tǒng)損失值方面，本文優(yōu)化方案優(yōu)于WFQ算法.原因在于文獻[8]只分析了在發(fā)送端發(fā)送數(shù)據(jù)時間足夠長的情況下，賦予相同權(quán)值隊列的隊長分布情況，并沒有對隊列長度和系統(tǒng)通信性能之間的關(guān)系進行深入研究.而本文在分析發(fā)送端、中繼器中數(shù)據(jù)幀排隊延時及丟包的基礎(chǔ)上，對緩存隊列長度對系統(tǒng)通信性能的影響進行了深入研究，并對隊列長度進行了優(yōu)化.

可見本文通過優(yōu)化緩存隊列長度來減小排隊延時，提高通信性能的方案是行之有效的.

4 結(jié) 論

本文對實時以太網(wǎng)發(fā)送端及中繼器緩存隊列的實際模型即在Linux數(shù)據(jù)鏈路層協(xié)議棧中發(fā)送數(shù)據(jù)幀的過程進行了深入分析，得出數(shù)據(jù)幀排隊延時及丟包是影響通信性能的主要因素.根據(jù)數(shù)據(jù)幀排隊延時及實時以太網(wǎng)傳輸延時的分布特性，確立了二者組成的通信系統(tǒng)為 M/G/1/∞排隊模型.在該模型基礎(chǔ)上，給出了在一次傳輸周期中實時以太網(wǎng)通信效率最優(yōu)即通信損失代價最小這一目標函數(shù).結(jié)合排隊論對該目標函數(shù)進行簡化并最終推導出通信損失代價最小時的最佳隊列長度，從而對隊列緩沖區(qū)的長度進行了優(yōu)化.實驗結(jié)果表明本文方案在一定程度上改善了以太網(wǎng)總體通信性能，對實際系統(tǒng)緩沖區(qū)大小的設(shè)計具有一定指導意義.

[1] 繆學勤.基于國際標準的十一種工業(yè)實時以太網(wǎng)體系結(jié)構(gòu)研究（上）[J].儀器儀表標準化與計量，2009（3）：14－18

[2] LIU C L，LAYLAND J W.Scheduling algorithms for multiprogramming in a hard－real－time environment[J].Journal of the ACM，1973，20（1）：46－61

[3] SHA L，RAJKUMAR R，LEHOCZKY J P.Priority inheritance protocols：an approach to real－time synchronization [J]. IEEE Transactions on Computers，1990，39（9）：1175－1185

[4] 雷 擎，王行剛.應(yīng)用網(wǎng)絡(luò)仿真技術(shù)進行網(wǎng)絡(luò)性能評價[J].計算機應(yīng)用，2001，12（2）：54－56

[5] MAHAJAN A，TENEKETZIS D.Optimal design of sequential real－time communication systems [J].IEEE Transactions on Information Theory，2009，55（11）：5317－5338

[6] SHEN C，LIU T，F(xiàn)ITZ M P.On the average rate performance of hybrid－ARQ in quasi－static fading channels[J].IEEE Transactions on Communications，2009，57（11）：3339－3352

[7] HUANG Po－kai，CHANG Cheng－shang，CHENG Jay，etal.Recursive constructions of parallel FIFO and LIFO queues with switched delay lines[J].IEEE Transactions on Information Theory，2007，53（5）：1778－1798

[8] ASHOUR M， LE－NGOC T. Performance of weighted fair queuing systems with long range dependent traffic inputs[C]//Canadian Conference on Electrical and Computer Engineering 2005.New York：IEEE，2005：1002－1005

[9] 王 智，王天然，宋葉瓊，等.工業(yè)實時通信網(wǎng)絡(luò)（現(xiàn)場總線）的基礎(chǔ)理論研究與現(xiàn)狀（上）[J].信息與控制，2002，31（2）：146－152

[10] GUO Y，GONG W B，TOWSLEY D.Time－stepped hybrid simulation（TSHS）for large scale networks[J].Proceedings－IEEE INFOCOM，2000，2：441－450

[11] KWEON Seok－kyu，SHIN K G.Statistical real－time communication over Ethernet [J]. IEEE Transactions on Parallel and Distributed Systems，2003，14（3）：322－335