基于負載分類的交換式以太網的實時性研究

董海勇，林 奕

（西北工業大學 計算機學院，陜西 西安 710129）

交換式以太網因結構簡單，管理方便，可擴展性強，已在商業應用中獲得了成功。但負載延遲的不確定性致使交換式以太網不適合直接應用在強實時通信領域。根據對實時要求的不同，通信數據主要分為周期性實時數據、突發性實時數據、有一定實時要求的受控類負載數據和不需要提供實時保障的數據。

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

文中應用網絡演算理論分析周期性和突發性實時數據的時延上限，并針對如何提高受控類負載實時性的問題進行研究。

1 相關模型及概念

1.1 網絡演算基本理論

R.L.Cruz在文獻[4-5]在分析不同網絡拓撲結構下數據延遲的方法時，定義了固定時延線、接收緩沖區、多路復用器、解多路復用器、（σ，ρ）整形器和先到先出隊列等6個基本網絡服務元素。隨后，C.S.Chang[6]，J.Y.Boudec等人基于最小加代數的數學解釋為網絡模型提出了網絡演算理論。

應用基于極小加代數的網絡演算，需要掌握其基本定義[8]。

定義 1（廣義增函數）定理廣義增函數是指當 s≤t，f（s）≤f（t）時的函數。另記F為在t＜0是取值為0的廣義增函數的集合，F0為在t≤0時取值為0的廣義增函數的集合。

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

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

定義4（服務曲線）當網絡元素S的輸入和輸出累積函數分別為A（t）和D（t）時，稱服務曲線為β當且僅當β是廣義增函數，β（0）=0 且 D＞A⊙β。

1.2 多路復用器中的排隊延遲

本節分析輸入流編號為i在先進先出多路復用器（FIFO MUX）和靜態優先級隊列多路復用器（SPQMUX）的時延上限。

1.2.1 先進先出多路復用器

先進先出多路復用器（FIFO MUX）由于不考慮數據流的優先級，所以只有一個輸出緩沖區。如圖1所示，FIFOMUX將輸入流的數據幀按照它們到達的次序傳輸到輸出鏈路，其中B（t）表示MUX在時刻t的緩沖區積壓。

圖1 僅有一個緩沖的FIFOMUXFig.1 FIFOMUX with one buffer

當Cout足夠大時，任意時刻的積壓B（t）至多就是一個在轉發的幀。則對于單個幀即可傳輸完成的長度為L的負載的時延上限為 Dqs=（Lmax+L）/Cout。

對于需要分割成多個幀才能完成傳輸的負載，若平均長度為Lavg，共被分割成m個數據幀，則該負載的時延上限為Dqm=（m*Lavg+L）/Cout。

當Cout不夠大時，任意時刻的積壓B（t）就可能不止一個幀。則對于單個幀可傳輸完成的長度為L的負載的時延上限為 Dqs=（B（t）+L）/Cout。

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

1.2.2 靜態優先級隊列多路復用器

靜態優先級隊列多路復用器（SPQ MUX）由于考慮數據流的優先級，所以對應每個優先級提供一個輸出緩沖區。如圖2所示，SPQMUX將輸入流的數據幀按照它們的優先級依次傳輸到輸出鏈路，對于優先級相同的數據幀，則按它們到達的次序傳輸到輸出鏈路，其中Bi（t）表示MUX在時刻t的第i個緩沖區的積壓。

圖2 附有多個緩沖的SPQMUXFig.2 SPQMUX withmany buffers

當Cout足夠大時時，負載的延遲上限與FIFOMUX相同。

對于需要分割成多個數據幀才能完成傳輸任務的負載的時延上限為Dqm。

當輸入流過大時，則無法得到該負載的時延上限，盡管時延上限是最悲觀的理論分析值。這也符合基于優先級調度的實際情況，即只要高優先級任務一直沒有完成，則低優先級的任務便得不到調度。

2 網絡模型

2.1 模型設計

為了研究交換式以太網的實時性，本文所建模型是一個基于交換式以太網的兩級樹形拓撲結構的網絡系統，如圖3，其中SW表示交換機，SLV代表數據源端；MST代表中央控制器。圖中的1個一級交換機連接著6個二級交換機，每個二級交換機又連著10個數據終端。即數據終端的個數為60。存儲轉發速率均設為常見的C=100 Mb/s，每個設備的連接線長度設為200m，電信號在電纜中的傳輸速率設為2*108m/s。

圖3 兩級樹形拓撲的網絡模型Fig.3 Networkmodelwith two-level tree topological

每個數據終端發送數據的模式相同，即都發送周期性實時數據、突發性實時數據、受控類負載和其他負載。定義周期性實時數據的優先級為最高的7，突發性實時數據的優先級為次高的6，受控類負載優先級被定義為1到4，其他數據優先級為0。

設每個數據終端10ms發送一個最小以太網幀用以傳輸周期性數據；同時使用漏桶整形器對突發性實時數據進行整流，使其平均每100 ms發送一個突發性實時數據幀，為了提高突發性實時數據的實時性，允許其連續發送10個突發性實時數據幀，幀的大小同樣采取最小以太網的幀格式。

對于受控類負載，設數據終端發出的數據大小分別為1 KB，10 KB，100 KB和1MB 4種。同時假設數據終端在發送完成一個受控類負載的之前，不會發送新的受控類負載，即規定數據終端發送出去的聚合流僅能包含一個受控類負載微數據流。

對于優先級最低的其他負載，則是不受任何限制的隨機發送，但系統不為該類負載提供任何實時性保證。

2.2 時延分析

應用文獻[3]可知周期性實時數據和突發性實時數據的延遲上限分別為0.700 430 987ms和5.311 312 44ms。

在不對受控類負載進行分類的情況下，只能采取FIFO調度機制，該機制可以保證每個受控類負載不會無限期的等待。數據終端i發出的受控類負載Pa在該系統的延遲上限為DΣ。

發送一個類型為Pa的受控類負載，加上該負載在傳輸的間隙等，需要傳輸Pb的數據量。

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

負載分類策略通過為較小負載分配較高優先級，為較大負載分配較低優先級，并采用SPQ的調度機制進行緩沖區管理，以降低較高優先級受控類負載的時延上限。采用SPQ的調度機制，設每個數據終端i發送優先級是p的受控類負載的速率上限為 Ci-p，在時刻t的速率為Ri-p（t），在交換機中的積壓為 Bi-p（t），p的取值范圍是 1～4。 數據終端i發出的受控類負載Pa在該系統的延遲上限為DΣ。

對比兩種機制所得到的時延上限，根據系統為受控類負載提供有效帶寬的大小，得到如下兩點：

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

2）Band不是充分大時，采用FIFO調度機制可以得到一個非常大的時延上限，但不會出現任務的無限等待；采用負載分類策略則可以使優先級較高的任務得到快速的轉發，但可能會導致低優先級的任務無限期的等待。

2.3 模型仿真

為了驗證理論分析的結果，本節應用VS2010設計并實現了該模型的仿真系統，該仿真系統是一個時間觸發的離散事件動態系統。同時規定各種受控類負載發送的概率相同。

2.4 結果比較

仿真程序在不同的調度策略，不同的負載情況分別運行1 000 s。當一級交換機平均負載為30%時，各類受控類負載在使用負載分類策略前后的統計結果做箱圖如圖4。

仿真結果表明，無論在何種負載的情況下，FIFO調度機制會給所有受控類負載以公平的調度方式，延遲差異不大；而采用分類負載策略可以明顯地降低了較高優先級的傳輸時延，而低優先級的時延較FIFO雖有提高，但提高比例不大。然而，隨著平均負載的不斷提高，多個1MB的負載同時出現在一個交換機中的頻次增加，導致了最大延遲的急劇增加。

圖4 受控類負載時延箱型統計圖Fig.4 Box plot of controlled loads delay

應用負載分類策略，對受控類負載采用SPQ調度機制，給較小的負載以較高優先級，給較大的負載以較低的優先級，理論分析和實驗共同表明：該策略可以有效的降低高優先級的傳輸時延，同時對低優先級數據延遲影響較小。

3 結 論

文中應用網絡演算分析了交換式以太網中周期性和突發性實時數據時延上限，以滿足強實時通信領域應用要求。針對原有對受控類負載調度管理算法的不足，提出了對受控類負載進行負載分類并賦予不同優先級的策略。通過實驗仿真，表明該策略可以大幅度降低受控類負載的時延，進而提高了受控類負載的實時性。

[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]張奇智，張彬，張衛東，等.基于網絡演算計算交換式工業以太網中的最大時延[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，Fraboul 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.