基于優(yōu)先級標(biāo)簽的LARS調(diào)度算法在網(wǎng)絡(luò)傳輸實(shí)時(shí)優(yōu)化中的應(yīng)用研究

何志強(qiáng)+崔新會(huì)+湛維明

【摘 要】LARS數(shù)據(jù)流傳輸調(diào)度算法依賴于數(shù)據(jù)流當(dāng)前傳輸?shù)臄?shù)據(jù)量，這使其在提高隨機(jī)數(shù)據(jù)包轉(zhuǎn)發(fā)的實(shí)時(shí)性時(shí)存在瓶頸。本文首先分析了LARS調(diào)度算法的理論特性，接著論證了該算法在復(fù)雜網(wǎng)絡(luò)傳輸中進(jìn)行實(shí)時(shí)傳輸?shù)目尚行院痛嬖诘膯栴}，最后提出了一個(gè)基于優(yōu)先級標(biāo)簽的LARS調(diào)度算法。仿真實(shí)驗(yàn)表明，改進(jìn)后算法相對LARS調(diào)度算法在提高特定數(shù)據(jù)流的服務(wù)質(zhì)量和傳輸穩(wěn)定性方面有一定的改進(jìn)。

【關(guān)鍵詞】LARS；優(yōu)先級標(biāo)簽；實(shí)時(shí)性

一、引言

近些年來，以太網(wǎng)技術(shù)在物聯(lián)網(wǎng)的實(shí)時(shí)信息采集領(lǐng)域得到了迅速的發(fā)展與推廣。但以太網(wǎng)存在著其固有的缺陷：基于競爭的帶寬分配機(jī)制使得其發(fā)送時(shí)延變得不確定，嚴(yán)重阻礙了以太網(wǎng)在實(shí)時(shí)數(shù)據(jù)采集領(lǐng)域中的應(yīng)用。LARS（最少到達(dá)最近的服務(wù)）調(diào)度算法使用轉(zhuǎn)發(fā)量作為數(shù)據(jù)流傳輸優(yōu)先級的評價(jià)標(biāo)準(zhǔn)，可以為短數(shù)據(jù)流提供更好的實(shí)時(shí)性能，對于提高短數(shù)據(jù)流的傳輸性能，如Web服務(wù)，網(wǎng)絡(luò)實(shí)時(shí)數(shù)據(jù)采集等具有很大優(yōu)勢。然而，LARS算法同樣存在一定的缺陷。首先，LARS總是給新數(shù)據(jù)流提供更高的轉(zhuǎn)發(fā)優(yōu)先級，這將大大增加DDOS攻擊的破壞力；二是LARS并不支持不同類型服務(wù)的細(xì)化分級，這可能會(huì)減少某些重要數(shù)據(jù)流的服務(wù)質(zhì)量與傳輸效率。本文采用優(yōu)先級標(biāo)簽對LARS調(diào)度算法進(jìn)行改進(jìn)，主要目的是解決重要數(shù)據(jù)流的服務(wù)質(zhì)量保證問題。

二、LARS調(diào)度算法的原理及方法

LARS算法最基本的特征是以數(shù)據(jù)傳輸量的大小作為基準(zhǔn)來進(jìn)行數(shù)據(jù)流的傳輸調(diào)度，其與FIFO算法最核心的區(qū)別是LARS對短數(shù)據(jù)流的傳輸非常有利，因此很早就在提高Web服務(wù)的服務(wù)質(zhì)量方面進(jìn)行了應(yīng)用。國外學(xué)者M(jìn)artin Heusse使用無線局域網(wǎng)的對LARS調(diào)度算法進(jìn)行了測試，表明LARS算法可以有效減少平均響應(yīng)時(shí)間，這也是LARS適合在物聯(lián)網(wǎng)（Internet of Things）數(shù)據(jù)采集尤其是在多網(wǎng)融合環(huán)境中應(yīng)用的主要原因。LARS算法對每個(gè)數(shù)據(jù)流的轉(zhuǎn)發(fā)量（達(dá)到服務(wù)）進(jìn)行計(jì)數(shù)，并將它作為一個(gè)數(shù)據(jù)流的優(yōu)先級。具體計(jì)算公式如下：

其中：Sj（t）是的數(shù)據(jù)流j在當(dāng)前調(diào)度時(shí)刻的總傳輸量， 表示在t時(shí)刻數(shù)據(jù)流j的衰減值。 表示發(fā)生調(diào)度的時(shí)間間隔，？滋表示衰減值系數(shù)，這兩個(gè)參數(shù)是公式中的重要參數(shù)，它們能夠影響到LARS的調(diào)度性能，？滋的取值范圍為（0，1]，表示在每個(gè) 時(shí)間后當(dāng)前衰減值會(huì)以一定比例減少。當(dāng) 和？滋均設(shè)置為零時(shí)，LARS算法會(huì)轉(zhuǎn)變?yōu)镕IFO算法。顯然，LARS算法可以保證得到最少的服務(wù)的數(shù)據(jù)流在隊(duì)列中擁有最高的優(yōu)先權(quán)，隨著調(diào)度周期的增加，算法最終將使每個(gè)數(shù)據(jù)流得到相同的轉(zhuǎn)發(fā)量。LARS算法和FIFO算法的傳輸特征如圖1所示：

早期的實(shí)時(shí)數(shù)據(jù)采集通常采用RS-485或總線作為網(wǎng)絡(luò)接入的方式。隨著以太網(wǎng)/無線接口模塊和多網(wǎng)融合技術(shù)的日益成熟，利用現(xiàn)有的以太網(wǎng)進(jìn)行實(shí)時(shí)數(shù)據(jù)采集變的簡單可行。如何使現(xiàn)有的以太網(wǎng)能夠滿足不同的數(shù)據(jù)轉(zhuǎn)發(fā)性能需求的應(yīng)用成為多網(wǎng)融合技術(shù)的關(guān)鍵問題。物聯(lián)網(wǎng)實(shí)時(shí)數(shù)據(jù)采集的應(yīng)用一般具有實(shí)時(shí)性要求高、傳輸頻率高、數(shù)據(jù)包小等特點(diǎn)，如果數(shù)據(jù)傳輸采用FIFO算法進(jìn)行調(diào)度，一些小數(shù)據(jù)包可能要等待很長時(shí)間才能獲得傳輸。這可能會(huì)在一些順序敏感型應(yīng)用中導(dǎo)致嚴(yán)重錯(cuò)誤。物聯(lián)網(wǎng)實(shí)時(shí)數(shù)據(jù)采集的數(shù)據(jù)轉(zhuǎn)發(fā)量遠(yuǎn)遠(yuǎn)小于普通商業(yè)應(yīng)用的數(shù)據(jù)轉(zhuǎn)發(fā)量，這意味著物聯(lián)網(wǎng)數(shù)據(jù)相對于普通商業(yè)應(yīng)用數(shù)據(jù)傳輸沒有任何優(yōu)勢。但如果使用LARS調(diào)度算法，這些應(yīng)用程序?qū)⒌玫礁玫膶?shí)時(shí)性能和較低的丟包率，同時(shí)整個(gè)網(wǎng)絡(luò)的吞吐量也會(huì)的到一定的提升。很明顯，在LARS調(diào)度策略中，一般應(yīng)用的數(shù)據(jù)轉(zhuǎn)發(fā)性能將略微降低，但這些應(yīng)用中的大部分對時(shí)間延遲并不敏感（除了一些特殊應(yīng)用（如VoIP），所以LARS算法更適合于提高小數(shù)據(jù)流在多網(wǎng)融合中的傳輸質(zhì)量。

值得注意的是，LARS在保證小數(shù)據(jù)包實(shí)時(shí)傳輸質(zhì)量中仍會(huì)存在一些問題。LARS只使用累積傳輸量和衰減周期計(jì)算數(shù)據(jù)流的優(yōu)先級，但沒有能力為不同數(shù)據(jù)流提供差異化的服務(wù)，與現(xiàn)有的QoS技術(shù)如IEEE 802.1P相比，LARS可能不能對有著不同的服務(wù)質(zhì)量要求數(shù)據(jù)流提供差異化服務(wù)。我們可以清楚地從圖1（b）看到，當(dāng)有更高優(yōu)先級的數(shù)據(jù)流F2出現(xiàn)時(shí)，F(xiàn)1將出現(xiàn)短傳輸停止（周期Tc）。如果F1是一個(gè)時(shí)間序列和時(shí)間延遲敏感的數(shù)據(jù)流，那么可能會(huì)導(dǎo)致應(yīng)用程序錯(cuò)誤的情況發(fā)生。因此，LARS算法一方面可以提高小數(shù)據(jù)包在多網(wǎng)融合環(huán)境下的實(shí)時(shí)性能，但在滿足實(shí)時(shí)數(shù)據(jù)流的服務(wù)質(zhì)量方面沒有任何改進(jìn)。

三、基于優(yōu)先級標(biāo)簽的LARS調(diào)度算法

傳統(tǒng)LARS調(diào)度算法需要解決的一個(gè)關(guān)鍵問題是不能穩(wěn)定的保持一個(gè)特定的數(shù)據(jù)流的優(yōu)先級值。本文設(shè)計(jì)了一種用于LARS的優(yōu)先級標(biāo)簽。標(biāo)簽根據(jù)隊(duì)列優(yōu)先級值采用了數(shù)據(jù)包保留字段中的3位。以0級為最高優(yōu)先級，默認(rèn)值為7。LARS只需要設(shè)置一個(gè)或幾個(gè)特殊的數(shù)據(jù)流的優(yōu)先級標(biāo)簽值，就可以為某些重要數(shù)據(jù)流提供更好的服務(wù)質(zhì)量，同時(shí)保證其他使用默認(rèn)值的物聯(lián)網(wǎng)數(shù)據(jù)相對普通商業(yè)應(yīng)用獲得較高的轉(zhuǎn)發(fā)優(yōu)先級?；趦?yōu)先級標(biāo)簽LARS算法公式如下：

在這個(gè)公式中，P是優(yōu)先標(biāo)記的最大值，在使用三位保留字段的情況下，該值為7。Pj是特定數(shù)據(jù)流的優(yōu)先級標(biāo)簽，當(dāng)該值與P相同時(shí)，改進(jìn)的LARS算法將回歸普通LARS算法。當(dāng)有重要數(shù)據(jù)流出現(xiàn)時(shí)，Pj的值可以設(shè)置0和6之間。當(dāng)有一個(gè)需要嚴(yán)格的實(shí)時(shí)性能和序列性能的數(shù)據(jù)包到達(dá)轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，該數(shù)據(jù)包需要得到的最高優(yōu)先級或最小的衰減值。一種方法是將Pj值設(shè)置為0來確保數(shù)據(jù)包得到的最高優(yōu)先級，但這可能會(huì)降低網(wǎng)絡(luò)的可擴(kuò)展性。因此，該設(shè)置可以滿足當(dāng)前需求的最大值，而不是直接設(shè)置為零。這對于保持網(wǎng)絡(luò)的可伸縮性很重要。本文認(rèn)為，確定優(yōu)先級的值只需要確保衰減值小于其他數(shù)據(jù)流即可。即：（右圖）

由此可見，為了確保高優(yōu)先級數(shù)據(jù)流j的傳輸，其相應(yīng)的優(yōu)先級應(yīng)小于其他每個(gè)數(shù)據(jù)流的優(yōu)先級。

四、仿真實(shí)驗(yàn)與分析

仿真環(huán)境由一個(gè)路由節(jié)點(diǎn)和兩個(gè)網(wǎng)段組成，所有的數(shù)據(jù)流都需要通過路由節(jié)點(diǎn)轉(zhuǎn)發(fā)。有四個(gè)工作站以隨機(jī)方式傳送數(shù)據(jù)，八個(gè)物聯(lián)網(wǎng)數(shù)據(jù)采集節(jié)點(diǎn)以實(shí)時(shí)模式向服務(wù)器提交數(shù)據(jù)。其中一個(gè)節(jié)點(diǎn)的對數(shù)據(jù)時(shí)延和序列非常敏感，其發(fā)送頻率為其他普通節(jié)點(diǎn)的3倍。其優(yōu)先級值設(shè)置為2。路由節(jié)點(diǎn)分別運(yùn)行LARS（tag=7）和基于優(yōu)先級標(biāo)簽的LARS（tag=2）算法進(jìn)行性能比較，結(jié)果如圖2所示：

從圖2可以看出，LARS算法（tag=7）在進(jìn)行數(shù)據(jù)傳輸時(shí)時(shí)延曲線有明顯的波動(dòng)，當(dāng)采用改進(jìn)的LARS算法（tag=2）時(shí)，數(shù)據(jù)包的延遲時(shí)間非常穩(wěn)定，因此，當(dāng)存在對服務(wù)質(zhì)量有較高要求的節(jié)點(diǎn)時(shí)，采用改進(jìn)的LARS算法是提高特定數(shù)據(jù)流服務(wù)質(zhì)量和傳輸穩(wěn)定性的可行途徑。

五、結(jié)論

本文在分析LARS調(diào)度算法原理的基礎(chǔ)上，針對LARS算法沒有區(qū)分不同應(yīng)用之間性能需求的缺點(diǎn)提出了一種基于優(yōu)先級標(biāo)簽的改進(jìn)算法。實(shí)驗(yàn)證明，這種改進(jìn)的LARS算法在保證特殊數(shù)據(jù)流的服務(wù)質(zhì)量同時(shí)還能保持其他數(shù)據(jù)流按照LARS算法正常傳輸。提高了數(shù)據(jù)傳輸?shù)恼w質(zhì)量和穩(wěn)定性。當(dāng)然，這種改進(jìn)方法仍然具有一定的缺陷，與FIFO和LARS算法相比，這種算法需要占用更多的路由器的計(jì)算資源，尤其是轉(zhuǎn)發(fā)和排序過程中產(chǎn)生的計(jì)算，這可能使路由器的轉(zhuǎn)發(fā)性能變差，這也是本文下一步將要解決的問題。

【參考文獻(xiàn)】

[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.