一種基于分類改進的LARS調(diào)度算法及其動態(tài)參數(shù)性能分析

何志強，林永君

(1.華北電力大學 控制與計算機工程學院，河北 保定 071009；2.河北金融學院 信息管理與工程系，河北 保定 071051)

一種基于分類改進的LARS調(diào)度算法及其動態(tài)參數(shù)性能分析

何志強1,2，林永君1

(1.華北電力大學 控制與計算機工程學院，河北 保定 071009；2.河北金融學院 信息管理與工程系，河北 保定 071051)

以工業(yè)以太網(wǎng)與商用網(wǎng)絡信息整合為研究背景，從調(diào)度算法入手，研究了基于LARS調(diào)度算法在多業(yè)務網(wǎng)絡中改進網(wǎng)絡服務質(zhì)量的問題.在研究LARS調(diào)度算法的原理和優(yōu)缺點基礎上，提出了利用數(shù)據(jù)分類技術改進LARS的方法，并在算法參數(shù)不同取值的條件下對轉(zhuǎn)發(fā)性能做了測試，證明該方法在實際應用中能夠保留LARS的基本特性，同時能夠有效提升LARS的執(zhí)行效率，并具有較好的動態(tài)參數(shù)穩(wěn)定性.

調(diào)度算法;分類;排隊;時延

以太網(wǎng)具有高帶寬、靈活組網(wǎng)、支持廣泛等突出特點，受到了工業(yè)控制領域的關注，以工業(yè)4.0為代表的多業(yè)務網(wǎng)絡信息融合的發(fā)展趨勢[1-2]，更使以太網(wǎng)被越來越多地應用到工業(yè)控制領域[3].但以太網(wǎng)具有一些不利于工業(yè)應用的特征，例如共享介質(zhì)訪問控制采用自由競爭機制，采用IP作為3層協(xié)議，自身無連接、無可靠性保證等.很多學者試圖改進以太網(wǎng)性能，以使其適應工業(yè)控制的需要[4].

目前工業(yè)以太網(wǎng)的相關研究成果中，主要有鏈路層協(xié)議改進和調(diào)度算法改進2個主要方向.多數(shù)鏈路層協(xié)議改進研究是從改進封裝或介質(zhì)訪問控制方法入手，能很好地克服傳統(tǒng)以太網(wǎng)的缺陷，但也會導致不兼容的問題，例如TTE、EtherCAT等[5-6]；調(diào)度算法的改進，由于是通過優(yōu)化排隊或請求響應來改進服務質(zhì)量，僅涉及協(xié)議層內(nèi)部調(diào)度，不會導致兼容性問題.可見，通過調(diào)度算法改進網(wǎng)絡性能，更加適應未來工業(yè)信息融合和創(chuàng)新的需要，相關研究領域也有了很多成果，例如已形成標準的IEEE802.1p協(xié)議、PQ(priority queueing)、WFQ(weighted fair queueing)等[7-8].

多業(yè)務網(wǎng)絡的信息融合使網(wǎng)絡數(shù)據(jù)成分更加復雜，對傳統(tǒng)的調(diào)度算法提出了挑戰(zhàn)，因此需要一種簡便、有效、動態(tài)的調(diào)度算法來保證其服務質(zhì)量.動態(tài)調(diào)度算法中的Size-based調(diào)度算法是近年來的研究熱點之一，該算法屬于公平型調(diào)度算法，其優(yōu)先權是基于獲得的服務量來分配.已有的研究已證明了Size-based算法對提高小數(shù)據(jù)流轉(zhuǎn)發(fā)性能的有效性[9-10].在工業(yè)網(wǎng)絡融合的多業(yè)務網(wǎng)中應用Size-based調(diào)度算法，將能夠使網(wǎng)絡提供更加公平的服務質(zhì)量保證.

Size-based調(diào)度算法也存在很多問題，例如其中較新的LARS(least attained recent service)算法通過采用歷史累積加權和周期性的計算方法，解決了早期Size-based算法易出現(xiàn)“服務饑餓”的問題[11]，但仍存在內(nèi)存開銷大、性能不穩(wěn)定等問題，限制了算法的應用.本文對LARS算法的原理進行了深入分析，提出了LARS算法改進方案，并對改進后的算法進行了可變參數(shù)下的性能分析.

1 LARS算法的原理及存在的問題

1.1 LARS算法的基本原理

LARS調(diào)度算法可視為LAS調(diào)度算法的改進版[12].相比于LAS算法，LARS算法將優(yōu)先級計算周期化，并設置了可整定的歷史累積值權重系數(shù).算法公式表示如下：

(1)

a.FIFO;b.LARS.圖1 FIFO和LARS數(shù)據(jù)發(fā)送特性對比Fig.1 Comparison of the characteristics of FIFO and LARS

從圖1的性能對比可見，LARS的轉(zhuǎn)發(fā)性能與FIFO的主要不同在于：在FIFO中，當有新的數(shù)據(jù)流(f2)出現(xiàn)時，新的數(shù)據(jù)流會和已有的數(shù)據(jù)流f1平分轉(zhuǎn)發(fā)機會；而在LARS中，由于新的數(shù)據(jù)流獲得的轉(zhuǎn)發(fā)量少，其衰減值必然較小，故f1會暫停發(fā)送(圖1b中的tc時間段).當新數(shù)據(jù)流的衰減值達或超過f1時，f1可重新獲得轉(zhuǎn)發(fā)機會，而tc的長度由衰減因子決定.

1.2 LARS算法存在的問題及分析

通過LARS的原理可知，LARS基于衰減值判別優(yōu)先級，而衰減值的計算又是一個歷史累積的過程.相比于基于數(shù)據(jù)分類的調(diào)度算法，衰減值賦予了LARS較強的適應性，但也會產(chǎn)生一系列問題：

首先是衰減值表內(nèi)存占用率過高的問題，衰減值和數(shù)據(jù)流是一一對應的，而數(shù)據(jù)流一般采用套接字即“IP+端口”加以區(qū)分，這會導致在數(shù)據(jù)成分復雜的網(wǎng)絡中，數(shù)據(jù)流數(shù)量將非常龐大，導致衰減值表占用大量的內(nèi)存，網(wǎng)絡設備可用內(nèi)存下降會導致?lián)砣陌l(fā)生幾率上升；其次，數(shù)據(jù)分組在插入等待隊列之前，需要找到并更新對應的衰減值，規(guī)模過大的衰減值表，會使LARS維護、更新和使用衰減值表的CPU開銷變大，降低轉(zhuǎn)發(fā)性能；再次，LARS的歷史累積衰減值初值為“0”，導致多業(yè)務網(wǎng)中新數(shù)據(jù)流的長分組搶占高優(yōu)先級的情況增加，使小數(shù)據(jù)流的轉(zhuǎn)發(fā)性能出現(xiàn)較大的波動.

2 基于分類改進的LARS調(diào)度算法

2.1 數(shù)據(jù)分組分類

通過上述分析可知，LARS目前存在的主要問題在于衰減值維護的計算開銷過大和衰減值計算規(guī)則有不合理之處所致，因此減小衰減值表規(guī)模并優(yōu)化衰減值計算規(guī)則是解決上述問題的直接方法.本文通過捕獲多個商用網(wǎng)絡骨干鏈路的數(shù)據(jù)發(fā)現(xiàn)，幀長度低于70字節(jié)的數(shù)據(jù)僅占總數(shù)據(jù)量的1%左右，絕大多數(shù)辦公應用數(shù)據(jù)為長數(shù)據(jù).而數(shù)據(jù)包短小正是工業(yè)、傳感網(wǎng)絡實時數(shù)據(jù)的典型特征.因此，可采用長度分類數(shù)據(jù)包，僅計算短數(shù)據(jù)流的衰減值，而長數(shù)據(jù)流作為非實時數(shù)據(jù)處理的方法.這種方法盡管精確度低，但由于短數(shù)據(jù)在網(wǎng)絡中的占比極低，故其分類效果可滿足算法實施的要求.

根據(jù)數(shù)據(jù)分組承載業(yè)務類型的不同，可以將數(shù)據(jù)分為3類：高于70字節(jié)的“低優(yōu)先級數(shù)據(jù)”，為TCP承載的非實時數(shù)據(jù)；低于70字節(jié)的“中優(yōu)先級數(shù)據(jù)”，有一定的實時性要求，例如傳感器數(shù)據(jù)；用于承載控制信令的“高優(yōu)先級數(shù)據(jù)”，對轉(zhuǎn)發(fā)性能要求最為嚴格.

2.2 改進后LARS算法的工作過程

2.2.1 處理流程和基本特性

由于對實時和非實時數(shù)據(jù)作了分類，因此轉(zhuǎn)發(fā)設備采取高、低優(yōu)先級隊列結構，有實時性要求的數(shù)據(jù)被放入高優(yōu)先級隊列，采取LARS算法調(diào)度數(shù)據(jù)；非實時數(shù)據(jù)放入低優(yōu)先級隊列，采取FIFO規(guī)則.為了保證轉(zhuǎn)發(fā)性能，采取實時隊列非空則非實時隊列等待的調(diào)度原則，由于短數(shù)據(jù)在網(wǎng)絡中占比極低，故該做法不會引發(fā)非實時數(shù)據(jù)“服務饑餓”的現(xiàn)象.此外，“高優(yōu)先級數(shù)據(jù)”采用固定的“0”衰減值，以保證其發(fā)送性能.

此外，由于基于長度的數(shù)據(jù)分類準確度較低，在此附加了字段特征的識別手段，對參與LARS調(diào)度的數(shù)據(jù)流進行后期識別.具體做法是：將數(shù)據(jù)流特征的穩(wěn)定性作為依據(jù)，即數(shù)據(jù)流的分類特征若保持穩(wěn)定，則認為該數(shù)據(jù)為實時數(shù)據(jù)的可信度較高，可減小其衰減值；數(shù)據(jù)流特征發(fā)生突變，則可認為該數(shù)據(jù)為非實時數(shù)據(jù)，應增大其衰減值.分類過程的偽代碼如下：

procedure classify_packet_in

begin

while list_packet_in.notEmpty()do

packet = list_packet_in.remove();

packet_key = packet.getKey();

if packet.isControlPacket()then

map_control.add(〈packet_key,list_packet〉);// 利用數(shù)據(jù)分組標識識別高優(yōu)先級數(shù)據(jù)

elseif packet.size==Length_Threshold then

list_lars.add( packet);// 檢測是否為穩(wěn)定的中優(yōu)先級數(shù)據(jù)流，是則減小其衰減值

if map_flow_count.get( packet_key)== lars_stable_threshold then

map_decay.decreaseDecay( packet_key);

map_flow_count.countFlush( packet_key);

end if

map_flow_count.increment( packet_key);

else

list_normal.add( packet);// 若非穩(wěn)定的中優(yōu)先級數(shù)據(jù)流，應增大衰減值的方法降低其優(yōu)先級

if map_decay.contains( packet_key)then

map_decay.increaseDecay( packet_key);

end if

end if

end while

end classify_packet_in

2.2.2 改進后LARS的性能分析

1) 低優(yōu)先級數(shù)據(jù)的性能

由于有高低優(yōu)先級隊列的存在，低優(yōu)先級數(shù)據(jù)的轉(zhuǎn)發(fā)需要等待高優(yōu)先級隊列為空后方可進行，其進入轉(zhuǎn)發(fā)節(jié)點至轉(zhuǎn)發(fā)完畢的時延如公式(2)所示.

由公式(2)可知，實時數(shù)據(jù)的搶占會導致非實時數(shù)據(jù)的轉(zhuǎn)發(fā)性能比在FIFO中有所下降，但一般情況實時數(shù)據(jù)的總量在網(wǎng)絡總數(shù)據(jù)量中的占比極低，這一變化不足以導致服務質(zhì)量顯著變差.此外，非實時數(shù)據(jù)一般由TCP承載，性能下降導致的丟包率小幅度上升可依靠TCP的可靠傳輸機制彌補.

2) 中優(yōu)先級數(shù)據(jù)的性能

由于中優(yōu)先級數(shù)據(jù)需要進行LARS計算和排隊，因此分組的處理時間主要由衰減值處理時間、排隊時間和接口傳輸時間決定，其時延如公式(3)所示.

(3)

式中,neLARS為 當前數(shù)據(jù)分組排隊序號的期望值;nrLARS為當前分組處理完畢前，新插入分組數(shù)量;vq為高優(yōu)先級隊列的字節(jié)總量;

3) 高優(yōu)先級數(shù)據(jù)的性能

由于高優(yōu)先級數(shù)據(jù)的衰減值為0，只有當隊列中有未處理的同類數(shù)據(jù)或當前端口已經(jīng)被占用時才需等待.此類數(shù)據(jù)轉(zhuǎn)發(fā)的時延如公式(4)所示.

(4)

式中,ncCBSBS為高優(yōu)先級數(shù)據(jù)在隊列中的數(shù)量期望值;vx：當前占用端口的數(shù)據(jù)幀長度.

3 測試結果及分析

3.1 網(wǎng)絡環(huán)境

模擬測試網(wǎng)絡的拓撲圖如圖2所示，正中位置的路由器負責兩側(cè)的IP包轉(zhuǎn)發(fā)，可分別運行傳統(tǒng)LARS和改進后的LARS算法.數(shù)據(jù)產(chǎn)生器用于產(chǎn)生3類優(yōu)先級數(shù)據(jù)，產(chǎn)生的數(shù)據(jù)幀長度特征參照了實際網(wǎng)絡的數(shù)據(jù)分布.同時，為了得到極限條件下的算法性能表現(xiàn)，采用了數(shù)據(jù)產(chǎn)生速度略高于路由器處理速度，路由器無擁塞控制，且不斷產(chǎn)生新的低優(yōu)先級數(shù)據(jù)流的策略，因此測試時延有增大的趨勢屬正?，F(xiàn)象.為了使算法更加體現(xiàn)LARS的特性，衰減因子的取值范圍為(0.5，1]；衰減周期的取值為2 s，與數(shù)據(jù)生成策略一致.

圖 2 測試網(wǎng)絡的拓撲圖Fig.2 Topology of the test network

3.2 結果及分析

圖3—6分別是3類數(shù)據(jù)在不同調(diào)度算法下衰減因子分別取0.5、0.7和0.9時的時延對比.圖3為低優(yōu)先級數(shù)據(jù)的轉(zhuǎn)發(fā)性能對比，其中T-LARS代表傳統(tǒng)LARS，I-LARS代表改進后的LARS.結果表明，盡管算法改進后轉(zhuǎn)發(fā)時延略有增大，但性能穩(wěn)定性有了顯著改善.從圖3還可見，衰減因子增大會加大轉(zhuǎn)發(fā)性能波動，同時也會使時延降低，因此在實施過程中衰減因子的取值應根據(jù)轉(zhuǎn)發(fā)性能需求確定衰減因子取值.另外，對比圖4和圖5的結果可見，衰減因子取不同值時，調(diào)度算法的特性對比與圖3相似，可見在不同的衰減因子環(huán)境下，改進后的LARS表現(xiàn)出了較好的可變參數(shù)魯棒性.

a.μ=0.5;b.μ=0.7;c.μ=0.9.圖3 低優(yōu)先級數(shù)據(jù)在μ取不同值的條件下轉(zhuǎn)發(fā)時延性能對比Fig.3 Forward performance comparison of low priority data at different values of μ

圖4為中優(yōu)先級數(shù)據(jù)的轉(zhuǎn)發(fā)性能對比.圖4可見，在運行改進的LARS調(diào)度算法后，無論衰減因子取值如何，轉(zhuǎn)發(fā)性能均有顯著提高，且性能波動也有所改善.其主要原因在于分類器降低了LARS的處理負荷，且杜絕了低優(yōu)先級長數(shù)據(jù)包搶占最高優(yōu)先級的情況.

a.μ=0.5;b.μ=0.7;c.μ=0.9.圖4 中優(yōu)先級數(shù)據(jù)在μ取不同值的條件下轉(zhuǎn)發(fā)時延性能對比Fig.4 Forward performance comparison of mid priority data at different values of μ

圖5為高優(yōu)先級數(shù)據(jù)的轉(zhuǎn)發(fā)時延性能對比.與圖4中的結果類似，改進后的LARS算法的時延性能明顯優(yōu)于傳統(tǒng)LARS算法.其主要原因在于改進后的LARS采取高優(yōu)先級數(shù)據(jù)衰減值保持“0”值的策略，使此數(shù)據(jù)在改進后的LARS中更加容易搶占轉(zhuǎn)發(fā)資源；低優(yōu)先級數(shù)據(jù)的大數(shù)據(jù)分組搶占發(fā)送端口的情況減少，使改進后的LARS中的數(shù)據(jù)傳輸性能波動明顯減少.此外，從圖4和5可見，改進后LARS的數(shù)據(jù)傳輸性能穩(wěn)定性有了改善，但仍存在性能波動，其主要原因是端口被一個長數(shù)據(jù)包占用而導致實時數(shù)據(jù)須等待至當前數(shù)據(jù)發(fā)送完畢而產(chǎn)生不可控的時延.

圖6是2種算法的衰減值表規(guī)模.結果表明，在改進后的算法中由于分類的作用，衰減值數(shù)量一直處于較低的水平，相比之下在執(zhí)行傳統(tǒng)LARS算法時，衰減值表規(guī)模呈快速上升的趨勢，證明了通過數(shù)據(jù)分類控制LARS衰減值表規(guī)模的有效性.

4 結語

基于分類改進的LARS算法在縮減了衰減值計算規(guī)模后，能夠基本保持LARS小數(shù)據(jù)流優(yōu)先的公平調(diào)度特性，且能夠提供比傳統(tǒng)LARS算法更加穩(wěn)定的傳輸性能；算法改進后，衰減值表的規(guī)模得到了有效控制，降低了內(nèi)存占用率，降低了處理過程的計算復雜度，使小數(shù)據(jù)流的轉(zhuǎn)發(fā)性能有了顯著提高，同時提高了轉(zhuǎn)發(fā)發(fā)設備的可靠性；不同的衰減因子條件下，算法的整體性能較為穩(wěn)定，表現(xiàn)出了較好的動態(tài)參數(shù)寬容度.

a.μ=0.5;b.μ=0.7;c.μ=0.9.圖5 高優(yōu)先級數(shù)據(jù)在μ取不同值的條件下轉(zhuǎn)發(fā)時延性能對比Fig.5 Forward performance comparison of high priority data at different values of μ

圖6 衰減值表變化情況對比Fig.6 Comparison of changes in decay values

[1] DECOTIGNIE J D.The many faces of industrial ethernet[Past and Present][J].IEEE Industrial Electronics Magazine,2009,3(1):8-19.DOI: 10.1109/MIE.2009.932171.

[2] GORECKY D,SCHMITT M,LOSKYLL M,et al.Human-machine-interaction in the industry 4.0 era[J].Management Science,2014,23(6):595-605.DOI: 10.1109/INDIN.2014.6945523.

[3] 楊金翠,方濱興,翟立東,等.面向物聯(lián)網(wǎng)的通用控制系統(tǒng)安全模型研究通信學報[J].通信學報,2012,1(11):49-56.DOI:10.3969/j.issn.1000-436x.2012.11.007.

[4] SKEIE T,JOHANNESSEN S,HOLMEIDE O.Timeliness of real-time IP communication in switched industrial Ethernet networks[J].IEEE Transactions on Industrial Informatics,2006,2(1):25-39.DOI: 10.1109/TII.2006.869934.

[5] ABUTEIR M,OBERMAISSER R.Simulation environment for Time-Triggered Ethernet[Z].IEEE International Conference on Industrial Informatics,Bochum,2013.

[6] PRYTZ G.A performance analysis of EtherCAT and PROFINET IRT[Z].IEEE International Conference on Emerging Technologies &Factory Automation,Hamburg,2008.

[7] TIAN Z,GAO X,KUN L I,et al.The improvement of IEEE 802.1p priority scheduling protocol in industrial ethernet[J].Information &Control,2012,41(1):117-68.DOI:10.3724/SP.J.1219.2012.00117.

[8] 姜國臣,譚賢四,范照勇等.排隊規(guī)則對FTP,Video,VoIP應用的性能影響[J].現(xiàn)代電子技術,2006,29(5):50-51,56.DOI:10.3969/j.issn.1004-373X.2006.05.027.

[9] DELL'AMICO M,CARRA D,PASTORELLI M,et al.Revisiting size-based scheduling with estimated job sizes[Z].IEEE,International Symposium on Modelling,Analysis &Simulation of Computer and Telecommunication Systems,Paris,2014.

[10] HARCHOL-BALTER M， SCHROEDER B， BANSAL N， et al.Size-based scheduling to improve web performance[J].Acm Transactions on Computer Systems,2003,21(2):207-233.DOI: 10.1145/762483.762486.

[11] KHADEMI N,OTHMAN M.Least attained service queue management for ns-2 network simulator[Z].International Conference on Computer Research &Development,Kuala Lumpur,2010.

[12] AUCHMANN M,URVOY-KELLER G.On the variance of the least attained service policy and its use in multiple bottleneck networks[M].Network Control and Optimization,Springer Berlin Heidelberg,2008:70-77.

[13] RAI I A， BIERSACK E W， URVOY-KELLER G.Size-based scheduling to improve the performance of short TCP flows[J].IEEE Network,2005,19(1):12-17.DOI: 10.1109/mnet.2005.1383435.

[14] HEUSSE M,URVOY-KELLER G,BROWN T X,et al.Least attained recent service for packet scheduling over access links[J].Pervasive &Mobile Computing,2011,7(4):479-494.DOI: 10.1016/j.pmcj.2011.04.002.

(責任編輯：孟素蘭)

ALARSschedulingalgorithmbasedonclassificationimprovementanditsdynamicparameterperformanceanalysis

HEZhiqiang1,2,LINYongjun1

(1.School of Control and Computer Engineering,North China Electric Power University,Baoding 071009,China;2.Information Management and Engineering Department,Hebei Finance University,Baoding 071051,China)

Aiming at the demand of industrial ethernet and office network information integration,this paper studies the problem of improving the quality of network service in multi-service network based on LARS scheduling algorithm.The principles,advantages and disadvantages of LARS are studied,and a method for improving LARS by using data classification technology is proposed.The forwarding performance test under different parameters proves that the method can preserve LARS’s basic characteristics,can effectively improve the efficiency of the implementation of LARS,and has a good robustness.

scheduling algorithm;classification;queuing;delay time

TP 393.0

A

1000-1565(2017)05-0537-08

10.3969/j.issn.1000-1565.2017.05.014

2017-03-07

河北省高校智慧金融應用技術研發(fā)中心資助項目 (XZJ2017006)

何志強 (1977—)，男，河北保定人，河北金融學院副教授，華北電力大學在讀博士，主要從事信息安全、網(wǎng)絡性能優(yōu)化、隱私保護研究.E-mail：hezhiqiang_net@126.com