一種基于QoS的空間延遲/中斷容忍網絡擁塞控制方法

時文豐- 高德云 周華春

?

一種基于QoS的空間延遲/中斷容忍網絡擁塞控制方法

時文豐-*高德云 周華春

(北京交通大學電子信息工程學院 北京 100044)

為緩解網絡擁塞對空間延遲/中斷容忍網絡產生的影響，該文提出一種基于QoS的網絡擁塞控制算法。該算法包括接觸擁塞判斷和基于QoS的數據轉發(fā)兩種機制，分別從接觸剩余可用容量和節(jié)點剩余存儲空間兩方面對每一段接觸的擁塞程度進行預測，將接觸劃分為不同的擁塞等級。在計算路由時，以整段路徑中所包含接觸的最高擁塞等級為該路徑的擁塞等級，并根據該擁塞等級發(fā)送不同優(yōu)先級的數據。實驗表明，基于QoS的擁塞控制算法可以提高低優(yōu)先級數據的傳遞率并在節(jié)點存儲空間不足時降低最高優(yōu)先級數據的傳遞時延。

空間延遲容忍網絡；擁塞控制；路徑擁塞等級；基于QoS的轉發(fā)

1 引言

延遲容忍網絡[1,2](Delay Tolerant Network, DTN)是為應對空間網絡頻繁的鏈路中斷、較長的端到端時延、高信道誤碼率等問題而設計的網絡協(xié)議。該協(xié)議將應用層數據分割成緊急(urgent)、標準(standard)、大塊(bulk) 3種優(yōu)先級的束(bundle)作為DTN協(xié)議的數據單元，并按此順序依次發(fā)送。DTN協(xié)議使用存儲轉發(fā)的策略應對鏈路中斷，當無端到端路徑時需將束存儲下來等待傳輸機會，而節(jié)點存儲空間不足時將造成數據丟失，導致網絡擁塞發(fā)生。

在空間環(huán)境中，節(jié)點的運動軌跡可以調度和預知，能夠預先獲得兩個節(jié)點間的通信起始和終止時間、傳輸速率、節(jié)點間距離等信息。接觸圖路由[3,4]將兩個節(jié)點間的鏈路信息作為一個“接觸”，配置在“接觸計劃”里，并根據預先配置的接觸信息，按照束的最早到達時間計算出合適的路由。

在資源受限的空間DTN中進行擁塞控制至關重要，但是目前關于空間DTN的研究主要集中在路由方面，針對空間網絡擁塞控制路由算法的研究還不是很多，且主要單獨以存儲管理的方式進行[8,9]，處理方式包括根據自身或其他節(jié)點的剩余存儲狀況控制發(fā)包速率、轉移數據以及選擇下一跳節(jié)點等，并沒有關注空間DTN節(jié)點軌跡及通信容量可預知的特點。文獻[10]提出的CGR-ETO雖然通過考慮鏈路排隊延時來提高精確性，當鏈路容量不足時優(yōu)先轉發(fā)高優(yōu)先級數據，但是并沒有考慮下一跳節(jié)點剩余存儲空間小于接觸容量的情況，當下一跳節(jié)點存儲空間不足時將導致數據被丟棄。

根據以上分析，本文提出一種基于QoS的空間延遲容忍網絡擁塞控制方法，同時考慮空間節(jié)點軌跡可預知的特點與節(jié)點的剩余存儲空間狀況，從接觸的剩余可用容量和節(jié)點的剩余存儲空間兩方面設計擁塞控制算法，緩解擁塞對網絡性能的影響。

2 基于QoS的擁塞控制算法

基于QoS的擁塞控制算法是一種擁塞避免算法，包括接觸擁塞等級判斷和基于QoS的數據轉發(fā)兩種機制。

2.1 接觸擁塞判斷機制

接觸擁塞判斷機制包括根據接觸剩余可用容量做出的接觸擁塞判斷，根據節(jié)點剩余存儲空間做出的接觸擁塞判斷和擁塞信息通告3部分，該機制的實現(xiàn)算法如表1，具體實現(xiàn)方法如下：

(1)以接觸剩余可用容量為依據的擁塞判斷：首先找出以本地節(jié)點為起點的所有接觸，每隔1 s對每段接觸分別進行判斷。將新判斷的擁塞等級與之前擁塞等級作對比，檢查是否發(fā)生變化，如果發(fā)生變化則向擁塞通告域內的其他節(jié)點通告。

本文使用接觸的剩余可用容量占接觸剩余容量的比例(Contact Available Capacity Ratio, CACR)作為接觸擁塞等級的判斷依據：

當剩余可用容量占剩余接觸容量的比例小于20%時認為接觸發(fā)生輕度擁塞，當小于10%時為重度擁塞，當小于0.05%時為完全擁塞，留出0.05%的容量作為束重傳、時間不同步等意外情況的開銷。

(2)以節(jié)點剩余存儲空間為依據的擁塞判斷：首先從接觸計劃中找出所有以本地節(jié)點為終點的接觸，檢查節(jié)點剩余存儲空間是否小于這些接觸的剩余容量，如果小于則檢測節(jié)點的剩余存儲空間占衡量基準的比例RNCR(Residual Node Capacity Ratio)。RNCR按下式計算：

當節(jié)點剩余存儲空間小于接觸的剩余容量時，接觸真實的可用容量應該以接觸終止節(jié)點的剩余存儲空間來計算，因為當無傳輸機會時，數據將存儲在接觸終止節(jié)點上，上限則為節(jié)點的剩余存儲空間。

表1接觸擁塞判斷機制

接觸擁塞等級判斷算法： 1 每隔1 s執(zhí)行以下操作： 2 對于接觸計劃中每一條接觸記錄 3 If 接觸的起始節(jié)點是本地節(jié)點 4 If CACR<0.2 5 If CACR<0.1 6 If CACR<0.0005 7 判斷接觸擁塞等級為完全擁塞 8 Else判斷接觸擁塞等級為重度擁塞 9 Else 判斷接觸擁塞等級為輕度擁塞 10 Else 判斷接觸未發(fā)生擁塞 11 If 接觸擁塞等級未發(fā)生變化 12 檢測下一條接觸記錄 13 Else 生成該接觸的擁塞通告，設置生存時間，計算通告域，隨后檢測下一條接觸 14 Else if 接觸的終止節(jié)點是本地節(jié)點 15 If 節(jié)點剩余存儲空間小于接觸剩余容量 16 If RNCR<0.2 17 If RNCR<0.1 18 If RNCR<0.0005 19 判斷接觸擁塞等級為完全擁塞 20 Else 判斷接觸擁塞等級為重度 21 Else 判斷接觸擁塞等級為輕度 22 Else 判斷接觸未發(fā)生擁塞 23 If接觸擁塞等級未發(fā)生變化 24 檢測下一條接觸記錄 25 Else生成該接觸的擁塞通告，設置生存時間，計算通告域，隨后檢測下一條接觸26 Else 檢查下一條接觸記錄27 Else 檢查下一條接觸記錄

當剩余存儲空間占比RNCR小于20%時判斷接觸為輕度擁塞，當RNCR小于10%時判定為重度擁塞，當RNCR小于0.05%時判定為完全擁塞。

(3)擁塞信息通告：當判斷到接觸擁塞狀態(tài)變化時，向其他節(jié)點發(fā)送擁塞信息，并將擁塞通告排入傳輸隊列的首位，保證最高的發(fā)送優(yōu)先級，如果未發(fā)現(xiàn)擁塞或擁塞等級未發(fā)生變化則不發(fā)送任何信息。擁塞通告信息包括接觸的起始節(jié)點、終止節(jié)點、起始時間、終止時間、擁塞判斷依據和擁塞等級。

因為有些節(jié)點用不到該發(fā)生擁塞的接觸，如當該接觸終止時還未開始使用的接觸，這些接觸的起始和終止節(jié)點將不會使用該接觸，因此使用通告域限制通告信息的有用性，避免發(fā)往不需要的節(jié)點耗費衛(wèi)星能量等資源。并且將擁塞通告信息的生存時間設置為接觸終止時間與發(fā)送通告當前時刻的時間差，將生存時間之內無法到達的節(jié)點視為無效。通告域定義為{接觸計劃中滿足開始時間小于擁塞接觸終止時間的所有接觸的開始節(jié)點和終止節(jié)點}。

2.2基于QoS的數據轉發(fā)機制

該機制包括接觸擁塞信息更新，路徑擁塞程度計算和基于QoS的束轉發(fā)3部分，其實現(xiàn)流程如表2算法所示。

當節(jié)點接收到擁塞通告信息時，根據通告信息中的起始節(jié)點、終止節(jié)點、起始時間、終止時間在接觸計劃中找到相應接觸，更新該接觸的擁塞等級。當節(jié)點為束計算路由時，首先根據CGR計算出最優(yōu)路徑，然后根據路徑中所有接觸的擁塞等級來決定該路徑的擁塞等級，路徑的擁塞程度由路徑中接觸的最高擁塞等級決定。

根據整條路徑的擁塞程度來決定發(fā)送束的優(yōu)先級：首先檢查束的目的節(jié)點是否為下一跳節(jié)點，如果是則所有優(yōu)先級的束都需要發(fā)送；當無擁塞時，發(fā)送所有優(yōu)先級的數據；當路徑輕度擁塞時允許前兩個優(yōu)先級的束發(fā)送，當重度擁塞時只允許最高優(yōu)先級的束發(fā)送，當完全擁塞時檢查接觸擁塞判斷依據，如果是接觸剩余容量不足引起的擁塞則允許最高優(yōu)先級的束發(fā)送，若判斷依據為節(jié)點存儲空間，則為所有束均選擇次優(yōu)路徑發(fā)送。

表2基于QoS的束轉發(fā)機制

基于QoS的束轉發(fā)算法： 1當束到來 2 If 束為擁塞通告信息 3 If 擁塞判斷依據為接觸剩余容量不足 4 更新以剩余容量為依據的擁塞等級 5 Else 在接觸計劃中找到相應接觸，更新該接觸以節(jié)點剩余存儲空間為依據的擁塞等級 6 Else 7 為束計算路由和路徑的擁塞等級8 If 束目的節(jié)點是下一跳節(jié)點 9 轉發(fā)該束10 Else if 路徑無擁塞 11 轉發(fā)該束 12 Else if 路徑擁塞等級為輕度擁塞 13 If 束優(yōu)先級為緊急或標準 14 轉發(fā)該束 15 Else使用次優(yōu)路徑轉發(fā) 16 Else if路徑擁塞等級為重度擁塞 17 If 束優(yōu)先級為緊急 18 轉發(fā)該束 19 Else使用次優(yōu)路徑轉發(fā) 20 Else if路徑擁塞等級為完全擁塞 21 If路徑擁塞等級判斷依據為接觸剩余容量不足&&束優(yōu)先級為緊急 22 轉發(fā)該束 23 Else 使用次優(yōu)路徑轉發(fā)

3 性能分析

實驗使用我們的基于分離映射機制的空天地一體化網絡實驗平臺完成，拓撲如圖1所示。節(jié)點1和節(jié)點2作為源衛(wèi)星節(jié)點向移動節(jié)點MN發(fā)送數據，數據首先發(fā)送到網關6進行協(xié)議轉換，星間鏈路延遲設置為100 ms，鏈路速率參考文獻[11]中的無人機中繼場景設置為2 Mbit/s。實驗參照銥星系統(tǒng)使用STK[12]仿真了兩顆LEO分別在節(jié)點稠密與稀疏情況下與地面網關間的接觸圖，我們將仿真結果簡化為表3和表4所示，其中FN, TN分別表示起始、終止節(jié)點，F(xiàn)T, TT分別表示起始、終止時間。

空間網絡使用NASA開發(fā)的DTN實現(xiàn)軟件ION-3.3.1[13]，我們在軟件中加入了基于QoS的擁塞控制算法實現(xiàn)模塊，并在實驗中與CGR-ETO[10]算法進行了比較，分別對比了接觸剩余可用容量和節(jié)點剩余存儲空間以及不同接觸擁塞等級判斷參數對傳輸性能的影響。使用束傳遞率反映網絡丟包情況，使用束傳遞時延反映網絡的傳輸效率。

3.1 接觸剩余可用容量對傳輸性能的影響

因為在源節(jié)點發(fā)送數據時，衛(wèi)星網絡中也同時存在其他節(jié)點發(fā)送的數據，我們在網絡中流量大小不同時分析接觸剩余可用容量不足情況下?lián)砣刂扑惴ǖ男阅堋?/p>

(1)不同網絡流量下?lián)砣刂茖鬏斝阅艿挠绊懀簩嶒灲佑|圖如表3所示，節(jié)點1和節(jié)點2每3 s向MN發(fā)送緊急、標準和大塊優(yōu)先級的束各一個，大小為200 kB，我們將節(jié)點3通往節(jié)點1和節(jié)點2的數據視為網絡中流量，使用網絡中流量占用鏈路帶寬比例作為變量。

圖 1 實驗拓撲

圖2所示為網絡中流量占用鏈路帶寬比對束傳遞率的影響曲線，圖中urg-cc, std-cc, bulk-cc, avg-cc曲線分別代表使用擁塞控制算法時緊急、標準、大塊束和平均的傳遞率曲線，urg, std, bulk, avg為無擁塞控制算法時(CGR-ETO)3種優(yōu)先級束和平均的傳遞率曲線。從圖2中可以看出當使用擁塞控制算法時，隨著網絡中流量占用鏈路帶寬比的增加，平均傳遞率可以提高10%~25%，對大塊束傳遞率最高可以提高近40%，對標準束最高可以提升20%。圖3為不同網絡中流量占用鏈路帶寬比對傳遞時延的影響曲線，對比標準和大塊曲線可以發(fā)現(xiàn)使用擁塞控制時傳遞時延增加，而無擁塞控制算法時，由于大量的大塊和標準束丟失，發(fā)送的數據變少，傳遞時延反而小于使用擁塞控制算法的情況。

(2)擁塞判斷參數對網絡性能的影響：我們對輕度擁塞和重度擁塞判斷參數的不同設置情況進行了分析。實驗使用(1)中發(fā)包方式，網絡中流量占用帶寬比例設置為90%。

圖5和圖6分別為接觸容量參數對束傳遞率和傳遞時延的影響圖，可以看出輕度擁塞判斷參數的增大帶來大塊束傳遞率的小幅提升，但是其傳遞時延也會增加。重度擁塞判斷參數的增加同樣會帶來大塊束傳遞率的提升，并使得標準束以及平均傳遞時延增加。我們使用平均傳遞時延作為性能指標，選擇平均傳遞時延最小的一組參數作為擁塞控制算法的參數設置，即0.2/0.1，表示輕擁塞判斷參數為0.2，重度擁塞判斷參數為0.1。

通過以上對比分析得出，當接觸剩余容量不足時，QoS擁塞控制算法可以提高大塊和標準優(yōu)先級束的傳遞率，但帶來了時延上的增加。

3.2 節(jié)點剩余存儲空間對傳輸性能的影響

實驗使用表4所示接觸圖，模擬節(jié)點稀疏場景。該場景下發(fā)送節(jié)點沒有到達目的節(jié)點的直接路徑，數據必須暫時緩存在中間節(jié)點。實驗使用3.1節(jié)中發(fā)包方式，束大小設置為100 kB，使用中間節(jié)點3的存儲空間作為變量。

圖4和圖8分別為存儲空間對傳遞率和傳遞時延的影響曲線，通過對比可以看出當無擁塞控制算法時，隨著存儲空間的減小，3種優(yōu)先級束的傳遞率均發(fā)生大幅下降，而使用擁塞控制算法時可以極大提升傳遞率，3種束的傳遞率均接近1。同時基于QoS的擁塞控制可以降低緊急束的傳遞時延，且隨著存儲空間的減小，降低的趨勢更加明顯。但大塊束的傳遞時延反而會增加，對標準束則無明顯影響。

同樣我們分析了節(jié)點存儲空間不足情況下不同接觸擁塞等級判斷參數對傳輸性能的影響，我們將擁塞判斷參數分別設置為圖7中6種不同情況。

圖7所示為存儲空間參數對束傳遞時延的影響圖，通過對比可以看出當重度擁塞判斷參數不變時，輕度擁塞判斷參數的增加帶來大塊束的傳遞時延和平均傳遞時延的增加，當輕度擁塞判斷參數不變時，重度擁塞判斷參數的變大將導致大塊和標準束的傳遞時延以及平均傳遞時延增加。當選擇參數0.2/0.1時，3種優(yōu)先級束的平均傳遞時延最小，在擁塞控制算法中我們使用輕度擁塞判斷參數為0.2，重度判斷參數為0.1作為算法設計的標準。

通過以上對比可以得出，當節(jié)點剩余存儲空間不足時，QoS擁塞控制算法不僅可以提高束的傳遞率，而且可以降低緊急束的傳遞時延。

表3稠密接觸圖參數

FN1122435 TN4335666 FT310113103101310 TT600300300600600300600

表4稀疏接觸圖參數

FN1122435 TN4335666 FT31011310610310610 TT600300300600900600900

圖2網絡中流量對傳遞率的影響?????圖3網絡中流量對傳遞時延的影響?????圖4 存儲空間對傳遞率的影響

圖5 接觸容量參數對傳遞率的影響????圖6 接觸容量參數對傳遞時延的影響????圖7 存儲空間參數對傳遞時延的影響

圖8存儲空間對傳遞時延的影響

4 結束語

本文利用空間網絡節(jié)點軌跡可預知的特點，提出一種基于QoS的擁塞控制算法，從接觸的剩余可用容量和節(jié)點的剩余存儲空間兩個方面對接觸進行擁塞預測，通過路徑中每段接觸的擁塞預期得到整段路徑的擁塞等級，并根據該等級決定路徑中允許發(fā)送的束的優(yōu)先級，實驗表明當接觸剩余可用容量不足引起網絡擁塞時，基于QoS的擁塞控制算法可以提高大塊和標準優(yōu)先級束的傳遞率，當節(jié)點剩余存儲空間不足時，可以提高束的傳遞率，并降低緊急束的傳遞時延。

[1] CERF V, BURLEIGH S, HOOKE A,Delay-tolerant networking architecture[S]. IETF RFC 4838, 2007.

[2] SCOTT K L and BURLEIGH S. Bundle protocol specification[S]. IETF RFC 5050, 2007.

[3] ARANITI G, BEZIRGIANNIDIS N, BIRRANE E,Contact graph routing in DTN space networks: overview, enhancements and performance[J].,2015, 53(3): 38-46.

[4] BURLEIGH S. Contact graph routing[S]. IETF Internet, draft-burleigh-dtnrg-cgr-00, 2010.

[5] BEZIRGIANNIDIS N, TSAPELI F, DIAMANTOPOULOS S,Towards flexibility and accuracy in space DTN Communications[C]. Proceedings of the 8th ACM MobiCom Workshop on Challenged Networks, Miami, Florida, USA, 2013: 43-48.

[6] FRAIRE J and FINOCHIETTO J M. Routing-aware fair contact plan design for predictable delay tolerant networks[J]., 2015, 25(Part B): 303-313.

[7] FRAIRE J and FINOCHIETTO J M. Design challenges in contact plans for disruption-tolerant satellite networks[J].,2015, 53(5): 163-169.

[8] SILVA A P, BURLEIGH S, HIRATA C M,. A survey on congestion control for delay and disruption tolerant networks[J]., 2015, 25(Part B): 480-494.

[9] RASHID S, AYUB Q, and ABDULLAH A H. Reactive weight based buffer management policy for DTN routing protocols[J]., 2015, 80(3): 993-1010.

[10] BEZIRGIANNIDIS N, CAINI C, and PADALINO M D D,. Contact graph routing enhancements for delay tolerant space communications[C]. Proceedings of IEEE 2014 7th Advanced Satellite Multimedia Systems Conference and the 13th Signal Processing for Space Communications Workshop (ASMS/SPSC), New York, USA, 2014: 17-23.

[11] IVANCIC W D and SULLIVAN D V. Delivery of Unmanned Aerial Vehicle DATA[M]. USA, National Aeronautics and Space Administration, Glenn Research Center, 2011: 1-6.

[12] Satellite Tool Kit (STK)[OL]. http://www.agi.com/ products/stk/, 2016.

[13] Interplanetary Overlay Network (ION) [OL]. https:// sourceforge.net/projects/ion-dtn/, 2015.

QoS Based Congestion Control for Space Delay/Disruption Tolerant Networks

SHI Wenfeng GAO Deyun ZHOU Huachun

(,,100044,)

In order to alleviate the influence of network congestion in space delay/disruption tolerant networks, a QoS based congestion control algorithm is proposed in this paper. The algorithm consists of contact congestion forecasting scheme and QoS based data forwarding scheme. The contacts are divided into different congestion levels according to their residual available capacity and nodes’ storage resource. The congestion level of forwarding path calculated by routing is decided by the highest congestion level of contacts consisted in the path and different priority data will be forwarded according to the path congestion level. Experiment shows that QoS based algorithm could improve the transmission rate of data with lower priority and reduce the delivery delay of highest priority data when the node storage space is insufficient.

Space delay tolerant network; Congestion control; Path congestion level; QoS based forwarding

TP393

A

1009-5896(2016)11-2982-05

10.11999/JEIT160140

2016-01-29；改回日期：2016-07-04；

2016-09-08

時文豐 14111038@bjtu.edu.cn

國家863計劃(2015AA015702)，國家自然科學基金 (61271202)，國家973計劃(2013CB329101)

The National 863 Program of China (2015AA015702), The National Natural Science Foundation of China (61271202), The National 973 Program of China (2013CB329101)

時文豐： 男，1990生，博士生，研究方向為延遲容忍網絡、空天地一體化網絡.

高德云： 男，1973年生，教授，研究方向為傳感器網絡、車載網絡.

周華春： 男，1965年生，教授，研究方向為未來網絡、空天地一體化網絡.