基于負(fù)載分類的交換式以太網(wǎng)的實(shí)時(shí)性研究

董海勇，林 奕

（西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710129）

交換式以太網(wǎng)因結(jié)構(gòu)簡單，管理方便，可擴(kuò)展性強(qiáng)，已在商業(yè)應(yīng)用中獲得了成功。但負(fù)載延遲的不確定性致使交換式以太網(wǎng)不適合直接應(yīng)用在強(qiáng)實(shí)時(shí)通信領(lǐng)域。根據(jù)對(duì)實(shí)時(shí)要求的不同，通信數(shù)據(jù)主要分為周期性實(shí)時(shí)數(shù)據(jù)、突發(fā)性實(shí)時(shí)數(shù)據(jù)、有一定實(shí)時(shí)要求的受控類負(fù)載數(shù)據(jù)和不需要提供實(shí)時(shí)保障的數(shù)據(jù)。

目前，新興的網(wǎng)絡(luò)演算作為一門能夠解決當(dāng)前網(wǎng)絡(luò)復(fù)雜問題的理論，因其可以方便地計(jì)算網(wǎng)絡(luò)節(jié)點(diǎn)之間的延遲和積壓上限，逐漸發(fā)展成網(wǎng)絡(luò)通信實(shí)時(shí)性能分析的最有效的理論工具。GEORGES[1]應(yīng)用網(wǎng)絡(luò)演算研究了交換式以太網(wǎng)的時(shí)延上限，但沒有區(qū)分?jǐn)?shù)據(jù)類型。F.FRANCES、和張奇智[2]等應(yīng)用網(wǎng)絡(luò)演算理論計(jì)算了交換式以太網(wǎng)中周期性實(shí)時(shí)數(shù)據(jù)、突發(fā)性實(shí)時(shí)數(shù)據(jù)的實(shí)時(shí)性，但沒有研究受控類負(fù)載的實(shí)時(shí)性。RIDOUARD[3]討論了在 FIFO（First In First Out，先進(jìn)先出）和SPQ（Static Priority Queueing，靜態(tài)優(yōu)先級(jí)隊(duì)列）兩種調(diào)度機(jī)制下周期性實(shí)時(shí)數(shù)據(jù)的延遲上限。

文中應(yīng)用網(wǎng)絡(luò)演算理論分析周期性和突發(fā)性實(shí)時(shí)數(shù)據(jù)的時(shí)延上限，并針對(duì)如何提高受控類負(fù)載實(shí)時(shí)性的問題進(jìn)行研究。

1 相關(guān)模型及概念

1.1 網(wǎng)絡(luò)演算基本理論

R.L.Cruz在文獻(xiàn)[4-5]在分析不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下數(shù)據(jù)延遲的方法時(shí)，定義了固定時(shí)延線、接收緩沖區(qū)、多路復(fù)用器、解多路復(fù)用器、（σ，ρ）整形器和先到先出隊(duì)列等6個(gè)基本網(wǎng)絡(luò)服務(wù)元素。隨后，C.S.Chang[6]，J.Y.Boudec等人基于最小加代數(shù)的數(shù)學(xué)解釋為網(wǎng)絡(luò)模型提出了網(wǎng)絡(luò)演算理論。

應(yīng)用基于極小加代數(shù)的網(wǎng)絡(luò)演算，需要掌握其基本定義[8]。

定義 1（廣義增函數(shù)）定理廣義增函數(shù)是指當(dāng) s≤t，f（s）≤f（t）時(shí)的函數(shù)。另記F為在t＜0是取值為0的廣義增函數(shù)的集合，F(xiàn)0為在t≤0時(shí)取值為0的廣義增函數(shù)的集合。

定義 2（極小卷積）設(shè) f，g∈F，則 f，g 的極小卷積定義為（f⊙g）（t）=inf{f（t-s）+g（s）|0≤s≤t}，且當(dāng) t＜0 時(shí)，（ f⊙g）（t）=0。

定義3（到達(dá)曲線）設(shè)廣義增函數(shù)A，α∈F，如果對(duì)于所有s≤t滿足 A（t）-A（s）≤α（t-s），則稱 A 是被 α 限制的，α 被稱為A的到達(dá)曲線。

定義4（服務(wù)曲線）當(dāng)網(wǎng)絡(luò)元素S的輸入和輸出累積函數(shù)分別為A（t）和D（t）時(shí)，稱服務(wù)曲線為β當(dāng)且僅當(dāng)β是廣義增函數(shù)，β（0）=0 且 D＞A⊙β。

1.2 多路復(fù)用器中的排隊(duì)延遲

本節(jié)分析輸入流編號(hào)為i在先進(jìn)先出多路復(fù)用器（FIFO MUX）和靜態(tài)優(yōu)先級(jí)隊(duì)列多路復(fù)用器（SPQMUX）的時(shí)延上限。

1.2.1 先進(jìn)先出多路復(fù)用器

先進(jìn)先出多路復(fù)用器（FIFO MUX）由于不考慮數(shù)據(jù)流的優(yōu)先級(jí)，所以只有一個(gè)輸出緩沖區(qū)。如圖1所示，F(xiàn)IFOMUX將輸入流的數(shù)據(jù)幀按照它們到達(dá)的次序傳輸?shù)捷敵鲦溌罚渲蠦（t）表示MUX在時(shí)刻t的緩沖區(qū)積壓。

圖1 僅有一個(gè)緩沖的FIFOMUXFig.1 FIFOMUX with one buffer

當(dāng)Cout足夠大時(shí)，任意時(shí)刻的積壓B（t）至多就是一個(gè)在轉(zhuǎn)發(fā)的幀。則對(duì)于單個(gè)幀即可傳輸完成的長度為L的負(fù)載的時(shí)延上限為 Dqs=（Lmax+L）/Cout。

對(duì)于需要分割成多個(gè)幀才能完成傳輸?shù)呢?fù)載，若平均長度為Lavg，共被分割成m個(gè)數(shù)據(jù)幀，則該負(fù)載的時(shí)延上限為Dqm=（m*Lavg+L）/Cout。

當(dāng)Cout不夠大時(shí)，任意時(shí)刻的積壓B（t）就可能不止一個(gè)幀。則對(duì)于單個(gè)幀可傳輸完成的長度為L的負(fù)載的時(shí)延上限為 Dqs=（B（t）+L）/Cout。

需要分割成多個(gè)幀才能完成傳輸任務(wù)的負(fù)載進(jìn)入緩沖區(qū)需要的時(shí)間為 Tin=（m*Lavg）/Ci。 在T in的時(shí)間內(nèi)，其他數(shù)據(jù)鏈路也可以發(fā)送數(shù)據(jù)到緩沖區(qū)，則此時(shí)間內(nèi)共可進(jìn)入的一些數(shù)據(jù)，再加上之前的積壓B（t），一起以Cout的速率傳輸出去，則此負(fù)載的時(shí)延上限為Dqm。

1.2.2 靜態(tài)優(yōu)先級(jí)隊(duì)列多路復(fù)用器

靜態(tài)優(yōu)先級(jí)隊(duì)列多路復(fù)用器（SPQ MUX）由于考慮數(shù)據(jù)流的優(yōu)先級(jí)，所以對(duì)應(yīng)每個(gè)優(yōu)先級(jí)提供一個(gè)輸出緩沖區(qū)。如圖2所示，SPQMUX將輸入流的數(shù)據(jù)幀按照它們的優(yōu)先級(jí)依次傳輸?shù)捷敵鲦溌罚瑢?duì)于優(yōu)先級(jí)相同的數(shù)據(jù)幀，則按它們到達(dá)的次序傳輸?shù)捷敵鲦溌罚渲蠦i（t）表示MUX在時(shí)刻t的第i個(gè)緩沖區(qū)的積壓。

圖2 附有多個(gè)緩沖的SPQMUXFig.2 SPQMUX withmany buffers

當(dāng)Cout足夠大時(shí)時(shí)，負(fù)載的延遲上限與FIFOMUX相同。

對(duì)于需要分割成多個(gè)數(shù)據(jù)幀才能完成傳輸任務(wù)的負(fù)載的時(shí)延上限為Dqm。

當(dāng)輸入流過大時(shí)，則無法得到該負(fù)載的時(shí)延上限，盡管時(shí)延上限是最悲觀的理論分析值。這也符合基于優(yōu)先級(jí)調(diào)度的實(shí)際情況，即只要高優(yōu)先級(jí)任務(wù)一直沒有完成，則低優(yōu)先級(jí)的任務(wù)便得不到調(diào)度。

2 網(wǎng)絡(luò)模型

2.1 模型設(shè)計(jì)

為了研究交換式以太網(wǎng)的實(shí)時(shí)性，本文所建模型是一個(gè)基于交換式以太網(wǎng)的兩級(jí)樹形拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)系統(tǒng)，如圖3，其中SW表示交換機(jī)，SLV代表數(shù)據(jù)源端；MST代表中央控制器。圖中的1個(gè)一級(jí)交換機(jī)連接著6個(gè)二級(jí)交換機(jī)，每個(gè)二級(jí)交換機(jī)又連著10個(gè)數(shù)據(jù)終端。即數(shù)據(jù)終端的個(gè)數(shù)為60。存儲(chǔ)轉(zhuǎn)發(fā)速率均設(shè)為常見的C=100 Mb/s，每個(gè)設(shè)備的連接線長度設(shè)為200m，電信號(hào)在電纜中的傳輸速率設(shè)為2*108m/s。

圖3 兩級(jí)樹形拓?fù)涞木W(wǎng)絡(luò)模型Fig.3 Networkmodelwith two-level tree topological

每個(gè)數(shù)據(jù)終端發(fā)送數(shù)據(jù)的模式相同，即都發(fā)送周期性實(shí)時(shí)數(shù)據(jù)、突發(fā)性實(shí)時(shí)數(shù)據(jù)、受控類負(fù)載和其他負(fù)載。定義周期性實(shí)時(shí)數(shù)據(jù)的優(yōu)先級(jí)為最高的7，突發(fā)性實(shí)時(shí)數(shù)據(jù)的優(yōu)先級(jí)為次高的6，受控類負(fù)載優(yōu)先級(jí)被定義為1到4，其他數(shù)據(jù)優(yōu)先級(jí)為0。

設(shè)每個(gè)數(shù)據(jù)終端10ms發(fā)送一個(gè)最小以太網(wǎng)幀用以傳輸周期性數(shù)據(jù)；同時(shí)使用漏桶整形器對(duì)突發(fā)性實(shí)時(shí)數(shù)據(jù)進(jìn)行整流，使其平均每100 ms發(fā)送一個(gè)突發(fā)性實(shí)時(shí)數(shù)據(jù)幀，為了提高突發(fā)性實(shí)時(shí)數(shù)據(jù)的實(shí)時(shí)性，允許其連續(xù)發(fā)送10個(gè)突發(fā)性實(shí)時(shí)數(shù)據(jù)幀，幀的大小同樣采取最小以太網(wǎng)的幀格式。

對(duì)于受控類負(fù)載，設(shè)數(shù)據(jù)終端發(fā)出的數(shù)據(jù)大小分別為1 KB，10 KB，100 KB和1MB 4種。同時(shí)假設(shè)數(shù)據(jù)終端在發(fā)送完成一個(gè)受控類負(fù)載的之前，不會(huì)發(fā)送新的受控類負(fù)載，即規(guī)定數(shù)據(jù)終端發(fā)送出去的聚合流僅能包含一個(gè)受控類負(fù)載微數(shù)據(jù)流。

對(duì)于優(yōu)先級(jí)最低的其他負(fù)載，則是不受任何限制的隨機(jī)發(fā)送，但系統(tǒng)不為該類負(fù)載提供任何實(shí)時(shí)性保證。

2.2 時(shí)延分析

應(yīng)用文獻(xiàn)[3]可知周期性實(shí)時(shí)數(shù)據(jù)和突發(fā)性實(shí)時(shí)數(shù)據(jù)的延遲上限分別為0.700 430 987ms和5.311 312 44ms。

在不對(duì)受控類負(fù)載進(jìn)行分類的情況下，只能采取FIFO調(diào)度機(jī)制，該機(jī)制可以保證每個(gè)受控類負(fù)載不會(huì)無限期的等待。數(shù)據(jù)終端i發(fā)出的受控類負(fù)載Pa在該系統(tǒng)的延遲上限為DΣ。

發(fā)送一個(gè)類型為Pa的受控類負(fù)載，加上該負(fù)載在傳輸?shù)拈g隙等，需要傳輸Pb的數(shù)據(jù)量。

表1 受控類負(fù)載傳輸信息表Tab.1 Information of controlled data

負(fù)載分類策略通過為較小負(fù)載分配較高優(yōu)先級(jí)，為較大負(fù)載分配較低優(yōu)先級(jí)，并采用SPQ的調(diào)度機(jī)制進(jìn)行緩沖區(qū)管理，以降低較高優(yōu)先級(jí)受控類負(fù)載的時(shí)延上限。采用SPQ的調(diào)度機(jī)制，設(shè)每個(gè)數(shù)據(jù)終端i發(fā)送優(yōu)先級(jí)是p的受控類負(fù)載的速率上限為 Ci-p，在時(shí)刻t的速率為Ri-p（t），在交換機(jī)中的積壓為 Bi-p（t），p的取值范圍是 1～4。 數(shù)據(jù)終端i發(fā)出的受控類負(fù)載Pa在該系統(tǒng)的延遲上限為DΣ。

對(duì)比兩種機(jī)制所得到的時(shí)延上限，根據(jù)系統(tǒng)為受控類負(fù)載提供有效帶寬的大小，得到如下兩點(diǎn)：

1）Band充分大的情況下，兩種時(shí)延上限相同；

2）Band不是充分大時(shí)，采用FIFO調(diào)度機(jī)制可以得到一個(gè)非常大的時(shí)延上限，但不會(huì)出現(xiàn)任務(wù)的無限等待；采用負(fù)載分類策略則可以使優(yōu)先級(jí)較高的任務(wù)得到快速的轉(zhuǎn)發(fā)，但可能會(huì)導(dǎo)致低優(yōu)先級(jí)的任務(wù)無限期的等待。

2.3 模型仿真

為了驗(yàn)證理論分析的結(jié)果，本節(jié)應(yīng)用VS2010設(shè)計(jì)并實(shí)現(xiàn)了該模型的仿真系統(tǒng)，該仿真系統(tǒng)是一個(gè)時(shí)間觸發(fā)的離散事件動(dòng)態(tài)系統(tǒng)。同時(shí)規(guī)定各種受控類負(fù)載發(fā)送的概率相同。

2.4 結(jié)果比較

仿真程序在不同的調(diào)度策略，不同的負(fù)載情況分別運(yùn)行1 000 s。當(dāng)一級(jí)交換機(jī)平均負(fù)載為30%時(shí)，各類受控類負(fù)載在使用負(fù)載分類策略前后的統(tǒng)計(jì)結(jié)果做箱圖如圖4。

仿真結(jié)果表明，無論在何種負(fù)載的情況下，F(xiàn)IFO調(diào)度機(jī)制會(huì)給所有受控類負(fù)載以公平的調(diào)度方式，延遲差異不大；而采用分類負(fù)載策略可以明顯地降低了較高優(yōu)先級(jí)的傳輸時(shí)延，而低優(yōu)先級(jí)的時(shí)延較FIFO雖有提高，但提高比例不大。然而，隨著平均負(fù)載的不斷提高，多個(gè)1MB的負(fù)載同時(shí)出現(xiàn)在一個(gè)交換機(jī)中的頻次增加，導(dǎo)致了最大延遲的急劇增加。

圖4 受控類負(fù)載時(shí)延箱型統(tǒng)計(jì)圖Fig.4 Box plot of controlled loads delay

應(yīng)用負(fù)載分類策略，對(duì)受控類負(fù)載采用SPQ調(diào)度機(jī)制，給較小的負(fù)載以較高優(yōu)先級(jí)，給較大的負(fù)載以較低的優(yōu)先級(jí)，理論分析和實(shí)驗(yàn)共同表明：該策略可以有效的降低高優(yōu)先級(jí)的傳輸時(shí)延，同時(shí)對(duì)低優(yōu)先級(jí)數(shù)據(jù)延遲影響較小。

3 結(jié) 論

文中應(yīng)用網(wǎng)絡(luò)演算分析了交換式以太網(wǎng)中周期性和突發(fā)性實(shí)時(shí)數(shù)據(jù)時(shí)延上限，以滿足強(qiáng)實(shí)時(shí)通信領(lǐng)域應(yīng)用要求。針對(duì)原有對(duì)受控類負(fù)載調(diào)度管理算法的不足，提出了對(duì)受控類負(fù)載進(jìn)行負(fù)載分類并賦予不同優(yōu)先級(jí)的策略。通過實(shí)驗(yàn)仿真，表明該策略可以大幅度降低受控類負(fù)載的時(shí)延，進(jìn)而提高了受控類負(fù)載的實(shí)時(shí)性。

[1]Georges J P，Rondeau E，Divoux T.Evaluation of switched ethernet in an industrial context by using the network calculus[C]//Factory Communication Systems，2002.4th IEEE InternationalWorkshop on.IEEE，2002:19-26.

[2]張奇智，張彬，張衛(wèi)東，等.基于網(wǎng)絡(luò)演算計(jì)算交換式工業(yè)以太網(wǎng)中的最大時(shí)延[J].控制與決策，2005，20（1）:117-120.ZHANG Qi-zhi，ZHANG Bin，ZHANG Wei-dong，et al.Calculation of maximum delay in switched industrial Ethernet based on network calculus[J].Controland Decision，2005，20（1）:117-120.

[3]Ridouard F，Scharbarg J L，F(xiàn)raboul C.Probabilistic upper bounds for heterogeneous flows using a static priority queueing on an AFDX network[C]//Emerging Technologies and Factory Automation， 2008.ETFA 2008.IEEE International Conference on.IEEE，2008:1220-1227.

[4]Cruz R.L..A calculus for network delay.I.Network elements in isolation[J].Information Theory， IEEE Transactions on，1991，37（1）:114-131.

[5]Cruz R.L..A calculus of delay Part II:Network analysis[J].IEEE Trans.Inform.Theory，1991，37（1）:132-141.

[6]Chang C S.On deterministic traffic regulation and service guarantees:a systematic approach by filtering[J].Information Theory， IEEE Transactions on，1998，44（3）:1097-1110.