帶寬節省的多路徑傳輸協議動態分包算法

黃 輝 許長橋 朱軍龍

(北京郵電大學網絡與交換國家重點實驗室 北京 100876)

帶寬節省的多路徑傳輸協議動態分包算法

黃 輝 許長橋 朱軍龍

(北京郵電大學網絡與交換國家重點實驗室 北京 100876)

隨著移動互聯網和多接口技術的發展，并行多路徑傳輸已成為當前的研究熱點，然而現有的機制存在帶寬資源浪費問題。首先通過實驗分析的方法，發現傳輸過程中的分包大小對帶寬資源利用率存在較大的影響。在此基礎上，對數據分包傳輸過程進行數學建模，分析獲得期望最高的帶寬資源利用率時應該滿足的條件。在所建模型的基礎上，設計了一種動態分包算法，能夠根據鏈路的丟包情況，動態調整數據包大小。實驗結果表明，與采用固定大小的分包策略相比，所提算法能夠有效減少多路徑傳輸中帶寬資源的浪費。

動態分包 協議優化 MPTCP CMT

0 引 言

近年來，隨著互聯網的高速發展，涌現了大量高帶寬傳輸需求的業務，比如以流媒體、在線視頻等為代表的業務。雖然移動互聯網的發展推動了無線接入技術的不斷變革和并行多路傳輸技術的發展，但是無線鏈路的動態性和不穩定性導致的大量數據包重傳造成了比較嚴重的網絡資源浪費。針對此類問題，現有一些解決方案通過引入網絡編碼的思想來弱化丟包的影響，從而提高資源的使用效率[1-3]。文獻[1]提出了NC-MPTCP，通過將網絡編碼的思想應用到多路徑傳輸協議(MPTCP[4])子流的子集中，減緩因丟包造成的接收端阻塞。文獻[2]將網絡編碼的思想應用到MPTCP的所有子流中，以應對無線異構網絡環境下鏈路的隨機丟包。課題組將網絡編碼的思想同CMT-SCTP[5]結合，優化無線網絡環境下的數據傳輸過程，提高了傳輸效率[3]。雖然采用網絡編碼的思想，可以打破傳輸序列號同數據包之間的嚴格綁定關系，在一定程度上弱化了丟包帶來的影響，但是現有基于網絡編碼的傳輸協議中采用的還是固定大小的分包方式，難以適應網絡環境的變化，造成帶寬資源的浪費。此外，在基于網絡編碼的方案中，發送端和接收端都需要進行協議的修改。

除了以上解決方案，文獻[6]提出了一種基于TCP的自適應壓縮傳輸方案，通過將應用數據壓縮傳輸，在接收端解壓縮的方式，降低對帶寬資源需求的同時提高了傳輸效率。然而，采用壓縮方案，只能用于傳輸那些還可以被壓縮的應用數據，而對于圖片和音視頻等主流媒體類型的數據已經很難再壓縮，此時帶寬資源節省的效果有限。文獻[7]通過對MAC層的通信過程構建分析模型，分析了802.11b的數據分包效率，并提出了一種最優分包策略，可以減少與藍牙設備間的干擾。然而，傳輸協議固定的分包方式將對MAC層的優化造成干擾。

因此，本文提出一種帶寬節省的傳輸協議動態分包算法，可以應用于以數據包為傳輸單元的多路傳輸方案中，比如MPTCP、SCTP等，能夠減少帶寬資源的浪費，進一步提高這些傳輸方案的性能。所提算法只需在協議的發送端部分進行修改，降低了實現和部署的難度。

1 問題發現

本節基于仿真軟件NS-2[8]設計一個實驗，結合當前最流行的多路徑傳輸協議MPTCP，對傳輸過程中數據包大小以及丟包率對帶寬資源的使用情況進行分析，使用的拓撲如圖1所示。

圖1 實驗環境使用的網絡拓撲

圖1場景描述的是使用智能手機與服務器通信的過程。智能手機同時通過Wi-Fi接口和LTE接口接入網絡，手機端和服務器端使用的傳輸協議是MPTCP。具體的網絡環境參數如表1所示。

表1 實驗拓撲環境參數

本實驗通過分別變化子流中數據包大小和丟包率，檢查在傳輸10 MB數據時，消耗多少的帶寬資源。數據包凈荷大小的變化范圍為100字節到1400字節，步長為100字節。

圖2描述了路徑1的傳輸情況，誤碼率為2×10e-5。從圖中可以看出在數據包大小過小或者過大的時候，都存在比較嚴重的帶寬浪費現象。在數據包過大的時候，一個錯誤的比特影響到的數據量更多，使得重傳的冗余數據增加，浪費過多的帶寬資源；在數據包過小時，由于每個數據包都需要攜帶一個固定大小的包頭，造成過多的帶寬資源都浪費在頭部的傳輸開銷中，使得傳輸的效率下降。

圖2 數據傳輸量隨著數據包大小的變化

在另一組實驗中，無線鏈路的誤碼率在1.0×10e-5到2.3×10e-5內變化，在固定數據包大小時，考查實際的數據傳輸量隨著誤碼率的變化情況。數據包凈荷的大小分別為1000和500字節。實驗結果如圖3所示，從圖中可以看出，隨著誤碼率的增大，實際傳輸的數據總量呈現一個近似線性的增長趨勢。在相同的誤碼率時，兩種數據包大小在實際傳輸的數據總量之間的差異進一步說明了數據包分包大小對帶寬資源的使用率會造成影響。

圖3 固定包大小時實際傳輸量隨誤碼率的變化

2 問題建模

通過上一節的實驗分析發現，數據包的大小對網絡資源的使用率有較大的影響。本節通過數學分析的方法探索使網絡資源得到最高效利用的數據包大小。建模過程中的變量及其具體的含義如表2所示。

表2 模型中變量及其含義

在已知BER的情況下，成功傳輸一個數據包的概率為[9]：

ps=(1-BER)8(x+h)

(1)

其中，x+h表示一個完整的數據包的大小，單位為字節。因此，一個數據包期望的傳輸次數為：

(2)

為了分析期望傳輸的數據總量與數據包凈荷大小的關系，定義期望傳輸的數據總量為：

(3)

(4)

為了分析是否存在最優解使得f(x)取得最小值，可以通過證明f(x)是一個凸函數，并求解極小值。f(x)的一階導數和二階導數為：

(5)

(6)

由式(6)可知，f″(x)>0，所以f(x)是一個凸函數，極值點存在且唯一[10]。令f′(x)=0，即：

(7)

因為x>0，h>0，又x2(1-BER)8(x+h)≠0，則式(7)可寫為：

h+8x(x+h)ln(1-BER)=0

(8)

從而得到最優解(過濾負值)：

(9)

通過以上分析，在已知誤碼率時，可以得到最優的數據包大小。圖4是通過式(4)獲得的曲線，其中，頭部大小為40字節，誤碼率為BER=10-5，需要傳輸的數據總量為10 000字節，數據包的凈荷從90字節到1 440字節變化，步長為10字節。在數據包凈荷大小取值480字節的時候(圖中虛線處)，f(x)取得最小值11 773字節。

圖4 數據傳輸量隨著數據包大小的變化

從圖4可以看出，在數據凈荷過小或者過大的時候，都無法獲得最好的傳輸效果，與實驗的結果相吻合。

3 算法設計

在前面實驗和數學分析的基礎上，提出一個動態分包算法，能夠減少帶寬資源的浪費，算法的設計將以MPTCP作為載體。該算法也可以應用到其他以數據包為傳輸單元的傳輸協議中。

首先，需要能夠獲得對底層鏈路誤碼率一個比較準確的估計，但在傳輸層要完成這項任務還需要一些輔助技術。因此，根據相關工作[9]，誤碼率為：

(10)

其中，pe為丟包率。

如果傳輸方案在沒有辦法獲取誤碼率時，可以按照式(10)所示的方法，基于丟包率進行估算，雖然會使準確率降低，但是采用這種估計后還是可以減少帶寬資源的浪費。

下面說明如何采用統計抽樣的方法計算丟包率，抽樣的周期確定為每一條子流發送一個窗口數據的時間。在每個周期可以收集一個樣本psample，然后和歷史值進行加權平滑。考慮到在一個動態無線網絡環境下，太久的歷史數據并沒有多大的意義。因此，丟包率的抖動因子定義為：

(11)

其中，vpe為pe的標準差。加權因子為：

(12)

其中，?v」符號表示小于等于v的最大整數值。丟包率更新為：

pe=(1-β)·pe+β·psample

(13)

其中，psample為采集的一個丟包率樣本。Pjitter用來衡量當前丟包率的抖動情況，在抖動較大時，歷史信息將占更小的權重(1-β)，使得最新的樣本能夠盡快地反映到最新的估計值中。

在確定了誤碼率后，按照式(9)計算當前最合適的數據包大小。這里需要考慮以下幾個問題：

(1) 數據包過小問題。比如比頭部的大小還小的時候，通過設定一個數據包大小的下界，保證最后的數據包大小不會小于該值。之所以這樣處理，一方面數據包太小，引入的頭部開銷導致的資源浪費比較嚴重，另一方面會使傳輸進程處理的開銷增大，需要在帶寬資源和處理資源之間進行權衡。本文下界值設置為400字節，可根據不同協議調整。

(2) 數據包過大問題。當數據包大小超過了底層鏈路的最大傳輸單元(MTU)時，通過設定一個數據包大小的上界，保證最后的數據包大小不會大于該值。一般上界值設置為最大傳輸單元減去頭部開銷后的值(1 440)，可根據不同協議調整。

(3) 對齊問題。在計算出了最合適的數據包大小之后，還需要考慮到數據包對齊問題，在保證不觸發以上兩個問題的基礎上，保證數據包的字節數是4的整數倍。

完整的算法描述：

for 每一條路徑ido

if當前發送窗口的數據已經發送完then

if能成功獲取MAC層的BERthen獲取BER；

else

根據發送和丟失的數據包計算psample；

按照式(11)-式(13)更新pe；

endif

else

if不能獲取MAC層的BERthen

記錄當前周期內發送和丟失的數據包數量；

endif

endif

if丟包率估計值或者獲取的BER有變化then

按照式(9)更新路徑i的數據包分包大小Size；

Size=(Size%4<=1 ? 4*?Size/4」 : 4*「Size/4?)；

ifSize<400thenSize=400

elseifSize>1440thenSize=1440

endif

endif

if有新的數據需要發送then

根據最新Size確定發送數據包的大小；

endif

endfor

4 仿真評估

仿真采用如圖5所示的拓撲，終端設備通過三條路徑和服務器通信。其中，路徑1和路徑2經過的鏈路存在共享的瓶頸。路徑3形成一條獨立的路徑。具體的網絡參數設置如表3所示。

表3 仿真拓撲參數設置

為了使得仿真拓撲更加接近現實的場景，添加如圖5所示的背景流量。背景流量采用VBR流量生成器生成，包含TCP和UDP兩種類型的流量，具體的流量比例分配參考文獻[3]。比較對象為傳統的MPTCP。在傳統的MPTCP中，數據包凈荷大小設置為1 440字節。主要的評估指標包括傳輸量隨丟包率的變化、期望數據包大小的分布圖。主要考察的是路徑1的傳輸情況。無線鏈路的誤碼率在0.1×10e-5到3.0×10e-5內變化。

圖5 仿真拓撲

4.1 傳輸數據量隨丟包率的變化

如圖6所示，描述的是實際數據傳輸量隨著誤碼率的增大的變化曲線。傳輸的數據量為10 MB。隨著誤碼率的增大，實際傳輸的字節數也在增加。在誤碼率大于0.7×10e-5的時候，實際傳輸的總字節數隨著誤碼率的變化趨勢開始變緩。同時，通過同靜態分包的方式(固定數據包凈荷大小為1440字節)相比較，發現在誤碼率比較低時，實際傳輸量很接近，因為在低丟包率時，動態分包傾向于分配比較大的數據包大小。但是，隨著誤碼率的增大，動態分包方式和靜態分包方式之間的差距也越來越大，在3×10e-5的誤碼率時，動態分包方式實際傳輸的數據總量為13 454 KB，而靜態分包方式為15 826 KB，可以節省17%左右的帶寬資源。

圖6 數據傳輸量隨著誤碼率的變化

4.2 頻率最高的數據包大小隨著誤碼率的變化

圖7描述了在不同的誤碼率情況下，實際傳輸過程中數據包大小分布的最大值曲線圖，從圖中可以看出，隨著丟包率的上升，數據包的大小趨向于變小，和理論分析的結果一樣。同時，這種變小的趨勢隨著丟包率的繼續上升也變得平緩，因此，當數據包的大小在小于算法設定的下邊界值而被截取時，對算法的效果影響不大。在誤碼率很低或者很高的時候，數據包的大小受到算法所規定的上下邊界限制。

圖7 頻率最高的數據包大小隨著誤碼率的變化

5 結 語

本文首先通過實驗的方法，發現數據包大小和丟包率對實際數據傳輸量存在一定影響。然后，建立了一個數學模型進行分析，證明了使得資源浪費最少的最優解的存在，并導出了最優解。在此基礎上，提出了一個動態分包算法，可以應用于以數據包為傳輸單元的傳輸協議中，對帶寬資源的使用進行優化配置，減少帶寬資源的浪費。基于MPTCP的仿真結果顯示，提出的算法能夠有效地減少帶寬資源的浪費，相比于沒有優化的解決方案，最好時可以節約17%左右的帶寬資源。

[1] Li M,Lukyanenko A,Cui Y.Network coding based multipath TCP[C]//Computer Communications Workshops (INFOCOM WKSHPS),2012 IEEE Conference on.IEEE,2012:25-30.

[2] Cloud J,Calmon F D P,Zeng W,et al.Multi-path TCP with network coding for mobile devices in heterogeneous networks[C]//2013 IEEE 78th Vehicular Technology Conference (VTC Fall).IEEE,2013:1-5.

[3] Xu C,Li Z,Zhong L,et al.CMT-NC:improving the concurrent multipath transfer performance using network coding in wireless networks[J].IEEE Transactions on Vehicular Technology,2016,65(3):1735-1751.

[4] Bagnulo M.Threat analysis for TCP extensions for multipath operation with multiple addresses[DB].RFC 6181,2011.

[5] Iyengar J R,Amer P D,Stewart R.Concurrent multipath transfer using SCTP multihoming over independent end-to-end paths[J].IEEE/ACM Transactions on Networking,2006,14(5):951-964.

[6] 牟璇,王俊峰,王敏,等.TCP自適應壓縮傳輸方案研究[J].計算機應用與軟件,2013,30(11):279-282.

[7] Howitt I,Awad F.Optimizing IEEE 802.11b packet fragmentation in collocated bluetooth interference[J].IEEE Transactions on Communications,2005,53(6):936-938.

[8] NS-2 Documentation and Software Version 2.35[OL].http://www.isi.edu/nsnam/ns.

[9] Mirani F H,Zhang X,Boukhatem N,et al.Cross-layer FPS:a SCTP-based cross-layer data scheduling approach[C]//2011 IEEE Consumer Communications and Networking Conference (CCNC).IEEE,2011:192-197.

[10] Boyd S,Vandenberghe L.Convex optimization[M].Cambridge,UK:Cambridge university press,2004.

DYNAMICALLY BANDWIDTH-SAVING PACKETIZATION ALGORITHM FOR MULTIPATH TRANSMISSION PROTOCOLS

Huang Hui Xu Changqiao Zhu Junlong

(StateKeyLaboratoryofNetworkingandSwitchingTechnology,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)

With the rapid development of the Mobile Internet and Multi-interface technology, Concurrent Multipath Transmission (CMT) has been a research hotspot. However, the waste of bandwidth resources is still a challenging problem in CMT. Firstly, it is found that the packet size has a great impact on the utilization of bandwidth resources through experiments. Based on the results of the experiments, a mathematical model about the data transmission process is proposed and the solution to the maximum resource utilization is derived. Based on the derived solution, a dynamic packetization algorithm is designed to achieve flexible scheduling of packet size according to the packet loss rate and bit error rate of the link. Simulation results demonstrate that the designed algorithm outperforms the fixed-size packetization strategy in terms of bandwidth resources utilization.

Dynamically fragmentation Protocol optimization MPTCP CMT

2016-01-19。國家自然科學基金面上項目(61372112)；北京市自然科學基金項目(4142037)。黃輝，碩士生，主研領域：計算機網絡，互聯網傳輸協議。許長橋，教授。朱軍龍，博士生。

TP393

A

10.3969/j.issn.1000-386x.2017.02.027