基于优先级标签的LARS调度算法在网络传输实时优化中的应用研究

何志强+崔新会+湛维明

【摘 要】LARS数据流传输调度算法依赖于数据流当前传输的数据量，这使其在提高随机数据包转发的实时性时存在瓶颈。本文首先分析了LARS调度算法的理论特性，接着论证了该算法在复杂网络传输中进行实时传输的可行性和存在的问题，最后提出了一个基于优先级标签的LARS调度算法。仿真实验表明，改进后算法相对LARS调度算法在提高特定数据流的服务质量和传输稳定性方面有一定的改进。

【关键词】LARS；优先级标签；实时性

一、引言

近些年来，以太网技术在物联网的实时信息采集领域得到了迅速的发展与推广。但以太网存在着其固有的缺陷：基于竞争的带宽分配机制使得其发送时延变得不确定，严重阻碍了以太网在实时数据采集领域中的应用。LARS（最少到达最近的服务）调度算法使用转发量作为数据流传输优先级的评价标准，可以为短数据流提供更好的实时性能，对于提高短数据流的传输性能，如Web服务，网络实时数据采集等具有很大优势。然而，LARS算法同样存在一定的缺陷。首先，LARS总是给新数据流提供更高的转发优先级，这将大大增加DDOS攻击的破坏力；二是LARS并不支持不同类型服务的细化分级，这可能会减少某些重要数据流的服务质量与传输效率。本文采用优先级标签对LARS调度算法进行改进，主要目的是解决重要数据流的服务质量保证问题。

二、LARS调度算法的原理及方法

LARS算法最基本的特征是以数据传输量的大小作为基准来进行数据流的传输调度，其与FIFO算法最核心的区别是LARS对短数据流的传输非常有利，因此很早就在提高Web服务的服务质量方面进行了应用。国外学者Martin Heusse使用无线局域网的对LARS调度算法进行了测试，表明LARS算法可以有效减少平均响应时间，这也是LARS适合在物联网（Internet of Things）数据采集尤其是在多网融合环境中应用的主要原因。LARS算法对每个数据流的转发量（达到服务）进行计数，并将它作为一个数据流的优先级。具体计算公式如下：

其中：Sj（t）是的数据流j在当前调度时刻的总传输量， 表示在t时刻数据流j的衰减值。 表示发生调度的时间间隔，？滋表示衰减值系数，这两个参数是公式中的重要参数，它们能够影响到LARS的调度性能，？滋的取值范围为（0，1]，表示在每个 时间后当前衰减值会以一定比例减少。当 和？滋均设置为零时，LARS算法会转变为FIFO算法。显然，LARS算法可以保证得到最少的服务的数据流在队列中拥有最高的优先权，随着调度周期的增加，算法最终将使每个数据流得到相同的转发量。LARS算法和FIFO算法的传输特征如图1所示：

早期的实时数据采集通常采用RS-485或总线作为网络接入的方式。随着以太网/无线接口模块和多网融合技术的日益成熟，利用现有的以太网进行实时数据采集变的简单可行。如何使现有的以太网能够满足不同的数据转发性能需求的应用成为多网融合技术的关键问题。物联网实时数据采集的应用一般具有实时性要求高、传输频率高、数据包小等特点，如果数据传输采用FIFO算法进行调度，一些小数据包可能要等待很长时间才能获得传输。这可能会在一些顺序敏感型应用中导致严重错误。物联网实时数据采集的数据转发量远远小于普通商业应用的数据转发量，这意味着物联网数据相对于普通商业应用数据传输没有任何优势。但如果使用LARS调度算法，这些应用程序将得到更好的实时性能和较低的丢包率，同时整个网络的吞吐量也会的到一定的提升。很明显，在LARS调度策略中，一般应用的数据转发性能将略微降低，但这些应用中的大部分对时间延迟并不敏感（除了一些特殊应用（如VoIP），所以LARS算法更适合于提高小数据流在多网融合中的传输质量。

值得注意的是，LARS在保证小数据包实时传输质量中仍会存在一些问题。LARS只使用累积传输量和衰减周期计算数据流的优先级，但没有能力为不同数据流提供差异化的服务，与现有的QoS技术如IEEE 802.1P相比，LARS可能不能对有着不同的服务质量要求数据流提供差异化服务。我们可以清楚地从图1（b）看到，当有更高优先级的数据流F2出现时，F1将出现短传输停止（周期Tc）。如果F1是一个时间序列和时间延迟敏感的数据流，那么可能会导致应用程序错误的情况发生。因此，LARS算法一方面可以提高小数据包在多网融合环境下的实时性能，但在满足实时数据流的服务质量方面没有任何改进。

三、基于优先级标签的LARS调度算法

传统LARS调度算法需要解决的一个关键问题是不能稳定的保持一个特定的数据流的优先级值。本文设计了一种用于LARS的优先级标签。标签根据队列优先级值采用了数据包保留字段中的3位。以0级为最高优先级，默认值为7。LARS只需要设置一个或几个特殊的数据流的优先级标签值，就可以为某些重要数据流提供更好的服务质量，同时保证其他使用默认值的物联网数据相对普通商业应用获得较高的转发优先级。基于优先级标签LARS算法公式如下：

在这个公式中，P是优先标记的最大值，在使用三位保留字段的情况下，该值为7。Pj是特定数据流的优先级标签，当该值与P相同时，改进的LARS算法将回归普通LARS算法。当有重要数据流出现时，Pj的值可以设置0和6之间。当有一个需要严格的实时性能和序列性能的数据包到达转发节点时，该数据包需要得到的最高优先级或最小的衰减值。一种方法是将Pj值设置为0来确保数据包得到的最高优先级，但这可能会降低网络的可扩展性。因此，该设置可以满足当前需求的最大值，而不是直接设置为零。这对于保持网络的可伸缩性很重要。本文认为，确定优先级的值只需要确保衰减值小于其他数据流即可。即：（右图）

由此可见，为了确保高优先级数据流j的传输，其相应的优先级应小于其他每个数据流的优先级。

四、仿真实验与分析

仿真环境由一个路由节点和两个网段组成，所有的数据流都需要通过路由节点转发。有四个工作站以随机方式传送数据，八个物联网数据采集节点以实时模式向服务器提交数据。其中一个节点的对数据时延和序列非常敏感，其发送频率为其他普通节点的3倍。其优先级值设置为2。路由节点分别运行LARS（tag=7）和基于优先级标签的LARS（tag=2）算法进行性能比较，结果如图2所示：

从图2可以看出，LARS算法（tag=7）在进行数据传输时时延曲线有明显的波动，当采用改进的LARS算法（tag=2）时，数据包的延迟时间非常稳定，因此，当存在对服务质量有较高要求的节点时，采用改进的LARS算法是提高特定数据流服务质量和传输稳定性的可行途径。

五、结论

本文在分析LARS调度算法原理的基础上，针对LARS算法没有区分不同应用之间性能需求的缺点提出了一种基于优先级标签的改进算法。实验证明，这种改进的LARS算法在保证特殊数据流的服务质量同时还能保持其他数据流按照LARS算法正常传输。提高了数据传输的整体质量和稳定性。当然，这种改进方法仍然具有一定的缺陷，与FIFO和LARS算法相比，这种算法需要占用更多的路由器的计算资源，尤其是转发和排序过程中产生的计算，这可能使路由器的转发性能变差，这也是本文下一步将要解决的问题。

【参考文献】

[1] Masudur Rahman， Wah Man Cheung. A Novel Cloud Computing Security Model to Detect and Prevent DoS and DDoS Attack. IJACSA ， vol. 5， no. 6， 2014.

[2]Martin Heusse ， Guillaume Urvoy-Keller ， Timothy X. Brown， Andrzej Duda. Least attained recent service for packet scheduling over access links. Pervasive and Mobile Computing，2011，479-494.

[3]Martin Heusse ， Guillaume Urvoy-Keller ， Andrzej Duda and Timothy X Brown. Least Attained Recent Service for packet Scheduling over Wireless LANs. 11th IEEE International Symposium on a World of Wireless， Mobile and Multimedia Networks，2010.

[4]Guillaume Urvoy-keller， André-luc Beylot. Improving flow level fairness and interactivity in WLANs using size-based scheduling policies. International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems - MSWiM ， 2008， 333-340.

[5] Liang Zhou， Athanasios V. Vasilakos， Joel Rodrigues， Baoyu Zheng， Jingwu Cui， Sulan Tang. Security-aware multimedia scheduling over heterogeneous wireless networks. International Conference on Wireless Communications and Mobile Computing， 2010 ， 1156-1160.