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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中

所以得

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

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

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

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

對(duì)上式右端第一項(xiàng)的求和進(jìn)行化簡(jiǎn)：

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

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

解上述不等式組得

因?yàn)長(zhǎng)o表示隊(duì)列長(zhǎng)度，即Lo取值必須是一整數(shù)，所以取Lo為

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4 結(jié) 論

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

[1] 繆學(xué)勤.基于國(guó)際標(biāo)準(zhǔn)的十一種工業(yè)實(shí)時(shí)以太網(wǎng)體系結(jié)構(gòu)研究（上）[J].儀器儀表標(biāo)準(zhǔn)化與計(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ù)進(jìn)行網(wǎng)絡(luò)性能評(píng)價(jià)[J].計(jì)算機(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è)實(shí)時(shí)通信網(wǎng)絡(luò)（現(xiàn)場(chǎng)總線）的基礎(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