一种基于分类改进的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