一種基于分類改進的LARS調度算法及其動態參數性能分析

何志強，林永君

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

一種基于分類改進的LARS調度算法及其動態參數性能分析

何志強1,2，林永君1

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

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

調度算法;分類;排隊;時延

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

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

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

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

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

1.1 LARS算法的基本原理

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

(1)

a.FIFO;b.LARS.圖1 FIFO和LARS數據發送特性對比Fig.1 Comparison of the characteristics of FIFO and LARS

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

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

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

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

2 基于分類改進的LARS調度算法

2.1 數據分組分類

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

根據數據分組承載業務類型的不同，可以將數據分為3類：高于70字節的“低優先級數據”，為TCP承載的非實時數據；低于70字節的“中優先級數據”，有一定的實時性要求，例如傳感器數據；用于承載控制信令的“高優先級數據”，對轉發性能要求最為嚴格.

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

2.2.1 處理流程和基本特性

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

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

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〉);// 利用數據分組標識識別高優先級數據

elseif packet.size==Length_Threshold then

list_lars.add( packet);// 檢測是否為穩定的中優先級數據流，是則減小其衰減值

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);// 若非穩定的中優先級數據流，應增大衰減值的方法降低其優先級

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) 低優先級數據的性能

由于有高低優先級隊列的存在，低優先級數據的轉發需要等待高優先級隊列為空后方可進行，其進入轉發節點至轉發完畢的時延如公式(2)所示.

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

2) 中優先級數據的性能

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

(3)

式中,neLARS為 當前數據分組排隊序號的期望值;nrLARS為當前分組處理完畢前，新插入分組數量;vq為高優先級隊列的字節總量;

3) 高優先級數據的性能

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

(4)

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

3 測試結果及分析

3.1 網絡環境

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

圖 2 測試網絡的拓撲圖Fig.2 Topology of the test network

3.2 結果及分析

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

a.μ=0.5;b.μ=0.7;c.μ=0.9.圖3 低優先級數據在μ取不同值的條件下轉發時延性能對比Fig.3 Forward performance comparison of low priority data at different values of μ

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

a.μ=0.5;b.μ=0.7;c.μ=0.9.圖4 中優先級數據在μ取不同值的條件下轉發時延性能對比Fig.4 Forward performance comparison of mid priority data at different values of μ

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

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

4 結語

基于分類改進的LARS算法在縮減了衰減值計算規模后，能夠基本保持LARS小數據流優先的公平調度特性，且能夠提供比傳統LARS算法更加穩定的傳輸性能；算法改進后，衰減值表的規模得到了有效控制，降低了內存占用率，降低了處理過程的計算復雜度，使小數據流的轉發性能有了顯著提高，同時提高了轉發發設備的可靠性；不同的衰減因子條件下，算法的整體性能較為穩定，表現出了較好的動態參數寬容度.

a.μ=0.5;b.μ=0.7;c.μ=0.9.圖5 高優先級數據在μ取不同值的條件下轉發時延性能對比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] 楊金翠,方濱興,翟立東,等.面向物聯網的通用控制系統安全模型研究通信學報[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] 姜國臣,譚賢四,范照勇等.排隊規則對FTP,Video,VoIP應用的性能影響[J].現代電子技術,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

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

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