何志強+崔新會+湛維明

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

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

一、引言

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

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

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

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

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

值得注意的是，LARS在保證小數(shù)據(jù)包實時傳輸質(zhì)量中仍會存在一些問題。LARS只使用累積傳輸量和衰減周期計算數(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)時，F(xiàn)1將出現(xiàn)短傳輸停止（周期Tc）。如果F1是一個時間序列和時間延遲敏感的數(shù)據(jù)流，那么可能會導(dǎo)致應(yīng)用程序錯誤的情況發(fā)生。因此，LARS算法一方面可以提高小數(shù)據(jù)包在多網(wǎng)融合環(huán)境下的實時性能，但在滿足實時數(shù)據(jù)流的服務(wù)質(zhì)量方面沒有任何改進。

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

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

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

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

四、仿真實驗與分析

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

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

五、結(jié)論

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

【參考文獻】

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