車載異構網絡中基于前向時延的多徑傳輸路徑調度優化

趙海濤，陳躍，張唐偉，朱奇星，朱洪波

（1.南京郵電大學教育部泛在網絡健康服務系統工程研究中心，江蘇 南京 210003；2.南京郵電大學通信與信息工程學院，江蘇 南京 210003）

1 引言

近年來，隨著工業技術和互聯網技術的不斷發展，硬件設備成本大大降低，網絡設備普及越來越廣，越來越多的終端設備裝有多個網絡接口，同時，裝備在車輛上的網絡接口也越來越復雜多樣。新一代的車載網絡可以實現移動過程中車輛之間的通信，以及低速移動或者靜止時車輛與路邊基礎設施之間的通信，這些能為車輛提供安全消息傳輸、智能交通信息業務、多媒體數字業務等。異構網絡中，多徑傳輸技術可以同時利用多個網絡的資源進行傳輸，聚合多個網絡的傳輸能力[1-3]，有效提高吞吐量和資源利用率，實現負載均衡。多徑傳輸中也面臨很多問題，因為在異構網絡中，為了使用多個路徑進行數據傳輸，需要一個分組調度器，它的職責是決定通過哪條路徑發送哪個數據分組。另一方面，為了獲得更高的可靠性，數據傳輸時需要按照它們在發送方傳輸的相同順序而在接收方傳送數據分組（到上層應用程序）。然而，不同的路徑具有不同的特性，如分組丟失率、帶寬、往返時間等，不同路徑發送的數據到達接收端時會發生亂序，這就需要對數據分組重新排序。這些無序分組會被累積在有限的接收緩沖器中，有可能導致緩沖區阻塞并影響車輛之間的通信性能。所以，需要設計一種有效的路徑調度優化方法來避免較少的重新排序工作，防止多徑傳輸的性能降低。

2 研究現狀

多徑傳輸可在協議棧的多個層實現，不同層的解決方案針對不同的問題，同時受該層特性的影響。因為應用層可以很好地適應應用的特性，所以可以實現更好的業務優化，但會增加應用層的復雜度。網絡層對更高層透明，且對現有的基礎設施兼容性好，但數據分組亂序會造成TCP（transmission control protocol）性能下降。由于鏈路層可以獲取信道的信息，因此可以更好地適應信道的動態變化，但鏈路層的解決方案不適應于端到端傳播。傳輸層的解決方案可以兼顧不同層的優缺點。本文主要針對傳輸層多徑傳輸技術進行研究，并對數據分組亂序問題提出解決方案來提高傳輸性能和資源利用率。

基于數據調度可以解決數據分組亂序問題，文獻[4]提出一種基于強化學習深度Q 網絡的數據調度算法，該算法先收集各條路徑的信息，依據路徑的傳輸效果對各條路徑進行獎懲，動態地估計各條路徑的傳輸能力，將數據盡可能地分配到傳輸能力強的路徑上，但會嚴重降低網絡利用率。文獻[5]針對路徑時延對接收端亂序的影響，提出了一種基于時延約束的主動數據調度算法，該算法的核心思想是當路徑時延小于設定的閾值時，則認為路徑可用。但是該算法忽略了分組丟失率和帶寬在實際網絡中與亂序的制衡關系，而且也不能保證可用路徑是全部路徑中相互時延差最小的路徑集合。文獻[6]提出了一種多路徑數據調度傳輸解決方案，該方案將單個數據流分成不同路徑上的多個單獨流，并在接收主機上將它們組合在一起，但在接收主機上組合時可能會出現拼接錯誤。文獻[7]提出了一種改進的數據調度算法，在計算中加入分組丟失率這個參數，對各個路徑的傳輸數據大小進行建模，通過仿真結果可知，該算法提高了吞吐量，但其不能適應網絡的動態變化。文獻[8]提出了Kim-2012 算法，該算法通過發送完數據分組并收到該數據分組的確認后，然后基于往返時間（RTT,round-trip time）在每條路徑上調度數據分組。該算法使用固定的時間（）作為前向時延的估計，如圖1 所示，但是，由于前向時延和后向時延不對稱，因此這不是一個好的估計。

圖1 前向時延和后向時延說明

基于路徑調度可以解決數據分組亂序問題，文獻[9]針對目前多路徑并行傳輸過程中由于傳輸路徑質量的差異導致網絡傳輸性能整體下降的問題，提出一種多路徑并行傳輸的路徑動態決策（CMT-DS,concurrent multipath transfer-dynamic selection）方法。該方法考慮到路徑傳輸質量對網絡吞吐量的影響，通過測量時延、抖動、分組丟失率和緩存占用比這4 個路徑傳輸屬性，擬合成路徑質量的關聯函數，根據該關聯函數對路徑進行動態選擇，從而實現動態選擇路徑的功能，以達到最理想的傳輸效果，但在室外環境或路徑更多時效果明顯降低。文獻[10]提出2 種新穎的基于塊估計調度程序和最短傳輸時間優先的調度技術，仿真結果表明，該技術可以降低交互時延，但對提高吞吐量效果不顯著。文獻[11]提出根據應用程序的工作量動態調整路徑解決方案，該方案首先利用TCP 建模的思想來估計正在調度的路徑上的等待時間以及同時在其他路徑上發送的數據量，然后以減少完成的目標為目的，定期確定用于某些應用程序的路徑集，但其實現起來較復雜。文獻[12]提出一種基于FIFO（first input first output）的車道擁堵緩解策略，仿真實驗表明，分批策略可以使滑行流出量增加25%以上，但該方法的實時性還有待驗證。文獻[13]提出一種調度多條路徑的方法，該方法先估計亂序的數據分組，提前預測緩沖區阻塞，并阻止在性能差的路徑上傳輸數據分組。但該方法選擇路徑時僅考慮分組丟失率和帶寬，因此，選擇路徑時會出現偏差。文獻[14]提出一種無線多跳網絡環境下并行多徑傳輸中的公平機制，使用Q 學習機制來獲得網絡中的動態信息，根據所獲得的動態信息來選擇最佳路徑，以獲得更高的帶寬利用率并提高網絡公平性指數，從而有效均衡流量并提高服務質量，但準確率還有待提高。文獻[15]提出一種基于MPSCTP（multipath stream control transmission protocal）的優化分流技術，并提出使用一種時延不敏感的優化的啟發式算法來研究多路徑選擇的策略，提高了對MPSCTP 中確認損耗的敏感性，從而提高了網絡利用率，并為終端用戶提供更好的服務質量，但是其內存空間占用較大，在實際應用中不夠方便。

針對上述在解決多徑傳輸中數據分組亂序的問題，本文提出了車載異構網絡中基于前向時延的多徑傳輸路徑調度優化方案。該方案根據前向路徑之間的估計時延和帶寬差異來調度分組，可以減少重新排序工作，從而提高系統吞吐量。

3 基于前向時延的路徑調度算法

3.1 估計前向時延差異

本文規定前向時延為從發送方到接收方的時延，后向時延為從接收方到發送方的時延。前向時延加后向時延就是往返時間（RTT）（如圖1 所示）。因為發送器和接收器的時鐘一般存在差異，所以估計前向時延在實際中并不是微不足道的。然而，從本節證明中可以看出，即使發送器和接收器的時鐘存在差異，也可以估計得到路徑之間的前向時延差異。

時延差計算如圖2 所示，發送方通過2 條不同的路徑向接收方發送2 個分組。S 代表發送方，R代表接收方，發送方在時間經路徑1 將分組1 發送到接收方，分組1 的到達時間為，發送方在時間將分組2 經路徑2 發送到接收方，分組2 的到達時間為。然后利用式(1)算出2 個數據分組的發送時間差Δs，利用式(2)得到2 個數據分組的接收時間差Δr，令ΔT=clkS-clkR 為發送方和接收方之間的時鐘差，通過式(3)算出數據分組1 的前向時延。同理，利用式(4)算出數據分組2 的前向時延。最后通過式(5)得到2 條路徑之間的前向時延差。

圖2 時延差計算

3.2 調度數據分組

本節首先需要找到前向時延最短的路徑。其中P={P1,P2,…,PN}是MPTCP 傳輸數據路徑的集合，前向時延最短的pi可以由圖3 中的算法確定。

該算法的主要思想是首先輸入一條路徑pi，然后依次計算該路徑與其他所有路徑pj之間的前向時延差Δpi pj，2 條路徑之間的差異必須是一個非正數，最后計算得到最大的Sum 值對應的路徑就是本文要找的路徑pi。

得到前向時延最短的路徑后，發送方就將調度數據分組。仿真實驗時假設發送方使用子流之間共享的緩沖區，并且應用層的數據足夠大來填充緩沖區。將發送緩沖區中的數據分區為數據分組，每個數據分組的大小等于TCP 路徑的MSS（maximum segment size）。然后，利用本文提出的算法調度程序在前向時延小的路徑上發送序列號低的數據分組。當決定選擇路徑i上的子流來傳輸數據之前，算法調度程序將先根據式(6)計算出數值idxi，然后緩沖區中idxi處對應的數據分組就將被傳輸。

圖3 系統算法流程

其中，xi代表路徑i的平均傳輸能力（B/s），MSS代表消息段大小，代表路徑i的歸一化速率，因此，乘積可以被解釋為路徑i和i*之間的“帶寬?時延乘積差”。因此，在數據分組到達路徑i之前，路徑i*上有足夠的空間來發送分組，在路徑i上發送的分組應該在式(6)計算得出的分組之后。在發送一個數據分組之后，較大的idxi對應的數據分組將被移位送到緩沖區，如圖4 所示。本文的分組調度算法原理是生成的數據分組先被存儲在發送緩沖器中，然后只有當用于發送數據的窗口打開時才被分配給子流。

圖4 根據前向時延差異分配數據分組

4 仿真結果與分析

本節評估了FDPS（forward delay-based packet scheduling）算法的性能，并與MPTCP[6]、FIFO[12]（具有最低RTT 的先進先出）和Kim-2012[15]的性能進行比較，重點比較的是重新排序緩沖區占用密度（RBD,reorder-buffer-occupancy density）和吞吐量這2 個參數。通過仿真得到不同參數下4 種算法的RBD 和吞吐量并進行比較。

本文的評估基于圖5 所示的拓撲結構，并在NS-3 上進行了模擬。表1 給出了各種網絡條件下模擬實驗的參數。

圖5 仿真路徑拓撲

表1 仿真參數

4.1 雙路徑傳輸

本文假設數據流在沒有后臺流量的2 個單獨的路徑上傳輸。表1 是仿真參數，表2 是仿真時2 條路徑的基本參數。如圖6 所示，本文首先按照表1調整好實驗參數，然后規定路徑A 帶寬為5 Mbit/s，時延為10 ms；路徑B 帶寬為5 Mbit/s，帶寬為10 ms。通過圖6 可以看出，即使2 條路徑相同，所有算法仍然會發生無序分組現象。但是，4 種算法的性能仍有很大的差異，FIFO 和MPTCP 的表現是最差的，Kim-2012 的性能稍微比前兩者表現得要好。與其他算法相比，FDPS 獲得了最佳性能，其RBD 集中在零點附近。

接下來，在條件2 下進行仿真，結果如圖7 所示。規定路徑A 的帶寬為5 Mbit/s，時延為10 ms；路徑B 的帶寬為5 Mbit/s，時延為25 ms，可以看到，此次仿真路徑B 的時延增加。FIFO 和MPTCP算法的RBD 比圖6 中的性能顯著降低。在這種情況下，Kim-2012 依然比FIFO 和MPTCP 表現得要好，但是從圖7 中可以看出FDPS 的性能仍然是最好的，其RBD 依然集中在零點附近。

圖8 是在條件3 下進行的仿真。規定路徑A 的帶寬為4 Mbit/s，時延為10 ms；路徑2 的帶寬為8 Mbit/s，時延為30 ms。此次仿真是在具有不同時延和帶寬的2 條路徑上進行的。從圖8 中可以看出，Kim-2012的性能比FIFO 和MPTCP 的性能表現得要好，但FDPS 的表現還是最好的，FDPS 的分組重新排序密度密集地集中在零點附近，而其他的則比較分散。

表2 仿真時2 條路徑的基本參數

4.2 具有后臺流量的雙路徑傳輸

實際上，網絡中的TCP 流經常與其他前向或后向流共享帶寬，為了評估在此類路徑上發送數據分組時數據分組調度算法的效率，本文進行了具有后臺流量的雙路徑傳輸仿真實驗，此實驗路徑參數按表2 中的條件2 進行配置。從圖9 可以看出，因為后臺流使RTT 估算的精確度降低，所以所有算法性能都大大降低，且MPTCP 和Kim-2012 的表現差于FIFO，因為前兩者對時變更敏感，但FDPS 的性能表現仍然是最好的。

4.3 3 條路徑傳輸

圖10 是本文在具有后臺流量3 條相同的路徑上進行的仿真實驗。可以看到，所有算法性能都變差了。這表明，當并發路徑數增加時，重新排序問題變得更加嚴重，但是，在這種情況下，FDPS 仍然表現最佳。

4.4 吞吐量比較

圖6 條件1 下沒有后臺流量的雙路徑傳輸仿真實驗

圖7 條件2 下沒有后臺流量的雙路徑傳輸仿真實驗

圖9 具有后臺流量的雙路徑傳輸仿真實驗

圖10 具有后臺流量3 條路徑傳輸仿真實驗

圖11 是相同條件下4 種算法的吞吐量仿真。從圖11 中可以看出，MPTCP 吞吐量在剛開始時上升的趨勢很快，但很快就開始下降然后趨于平緩，并且趨于平緩后MPTCP 吞吐量表現是最差的，另外，Kim-2012 和MPTCP、FIFO 的曲線走勢基本相同，但Kim-2012 的吞吐量總體比FIFO 和MPTCP 表現得要好，FDPS 的吞吐量曲線是走勢最好的，剛開始上升很快，一段時間后趨于平緩后，代表FDPS 吞吐量的曲線依然在其他3 條曲線的上方。綜合4.1～4.3 節考慮分析，因為相同條件下FDPS 始終獲得最優的重新排序緩沖區占用密度，數據分組亂序造成緩沖區擁塞的可能性最低，從而系統性能處于最優狀態，所以FDPS 獲得了最優的吞吐量表現。

5 結束語

本文針對多徑傳輸中數據分組亂序問題，提出了一種基于前向時延的多徑傳輸路徑調度優化算法，所提算法在不同條件仿真實驗中始終獲得最佳的緩沖器占用率，這表明在各種網絡條件下所提算法的性能表現都很穩定。在本文的模擬中，使用不限大小的重新排序緩沖區，因為本文希望捕獲接收器上的所有數據分組以進行正確的RBD 和吞吐量測量。由于所提算法與其他算法相比都得到了最佳的重新排序緩沖器占用率，因此如果使用所提算法，則有限重新排序緩沖器大小的影響將是最小的，可以降低亂序問題提高吞吐量。針對本文中在數據分組調度方面仍然存在的問題，下一步的工作計劃是設計更加合理的數據調度算法，進一步提升多路徑傳輸性能。

圖11 相同條件下4 種算法的吞吐量仿真