基于多源的NDN端節(jié)點擁塞控制算法

沈越欣 王興偉 李潔 曾榮飛

摘? ?要：文章以NDN網絡現(xiàn)存擁塞控制算法的端節(jié)點擁塞信號獲取不準確為研究問題，提出一種基于端節(jié)點的擁塞控制算法。這種算法從源頭上控制擁塞，并依據(jù)多個擁塞信號進行端節(jié)點速率調整，以更貼近全局網絡狀態(tài)的方式進行端速率調整以保證吞吐量。文章考慮NDN多源特性，結合累積排隊時延信息，設計端節(jié)點重傳定時策略，避免過多重傳加重網絡擁塞，進而確保網絡的穩(wěn)定性。

關鍵詞：命名數(shù)據(jù)網絡;多源;端節(jié)點擁塞控制;累積排隊時延;重傳定時策略

1 引言

隨著網絡應用類型的多樣化和用戶數(shù)據(jù)的爆炸式增長，以內容為中心的網絡流量逐漸占據(jù)主要位置[1]。以內容為中心的命名數(shù)據(jù)網絡（Named Data Networking，NDN）也成為了研究熱點[2，3]。隨著網絡流量的不斷增加，擁塞控制對網絡中的內容成功獲取、穩(wěn)定性和服務質量等具有舉足輕重的作用。NDN體系結構支持流量平衡（One-interest-one-data），其基于接收端驅動（Receiver-driven）和多源（Multi-source）、多路徑（Multipath）的特性，更是給NDN擁塞控制機制的設計增添了難度。隨著命名、緩存、路由機制的不斷成熟，針對NDN擁塞控制機制[4]的研究已引起廣泛關注。

NDN擁塞控制面臨著眾多挑戰(zhàn)。由于NDN中沒有類似于TCP中的重復ACK，且因為NDN的多源特性，通過重傳超時（Retransmission Time-Out，RTO）來判斷擁塞并不準確，故適用于TCP/IP的擁塞控制策略如依據(jù)RTO、重復ACK確認的擁塞檢測等均不能直接應用于NDN中。

本文利用NDN獨有的優(yōu)勢和特點進行端節(jié)點擁塞控制算法（End-node Based Congestion Control，EBCC）的設計與實現(xiàn)：（1）針對NDN多源性，設計了三種擁塞信號，基于這些擁塞信號反饋進行相應的速率調整保證網絡吞吐量;（2）通過準確地獲取擁塞信號并經過中間節(jié)點逐跳累積，反映網絡全局信息;擁塞信息的反饋利用數(shù)據(jù)包“捎帶”的方法，不會增加過多額外負載;（3）在端節(jié)點設計了重傳定時機制，具有很好的適應性，避免過多重傳加重網絡擁塞，確保網絡穩(wěn)定性。

2? 相關工作

現(xiàn)有擁塞控制策略可以分為單源擁塞控制、多源擁塞控制。單源擁塞控制中[5，6]，通過在請求方調整興趣包的發(fā)送速率來控制擁塞。文獻[5]提出了一個端節(jié)點興趣控制協(xié)議（Interest Control Protocol，ICP），設置在請求方的AIMD 控制器會根據(jù)當前網絡的擁塞狀況來調整發(fā)送窗口的大小，并通過為每個興趣流維護歷史往返時延RTT值來計算RTO，以此來判斷擁塞。文獻[6]提出基于端節(jié)點的自調整興趣速率控制機制，該機制利用數(shù)據(jù)包的到達時間間隔差，來調整興趣包的發(fā)送時間間隔差，以此來控制興趣包的發(fā)送速率。文獻[5，6]是基于單源的假設，這在NDN中往往不能成立，一些考慮多源特性的端節(jié)點擁塞控制算法被提出，如文獻[7～9]。

文獻[7]提出根據(jù)往返時延來設置超時值是不可靠的，并提出一個基于隱式反饋的接收方驅動擁塞控制策略。但它假設端節(jié)點知道內容源的位置，且在傳輸過程中不會改變，這在實際場景中并不太可能。文獻[8，9]分別提出為每個路徑、內容儲存庫（Content Store，CS）維護一個RTO。文獻[8，9]都是基于將多源問題轉化成多個單源問題，存在兩個弊端：其一，對于擁塞的判斷依然依靠RTO，由于RTO的測量存在不準確性，造成對網絡擁塞狀況的評估不準確，不能保證很好的網絡穩(wěn)定性;其二，在端節(jié)點需要對每個流、內容源或路徑等維護多倍的信息，這會造成高昂的成本，且可擴展性很低。

本文提出的端節(jié)點擁塞算法在AIMD與CoDel的基礎上進行改進，依據(jù)數(shù)據(jù)包攜帶的累積排隊時延、NACK包和數(shù)據(jù)包超時等不同的擁塞信號，進行不同的窗口調整。

3 問題描述

3.1 模型設計

NDN網絡模型可以抽象為一個無向連通圖G =（C，R，E）。其中，C代表網絡中的端節(jié)點集合;R代表網絡中的中間節(jié)點集合;E代表考慮了時延（傳輸時延和排隊時延）、鏈路帶寬等參數(shù)的物理鏈路集合。

為實現(xiàn)擁塞控制，中間節(jié)點在轉發(fā)處理的過程中，記錄網絡擁塞信號，通過數(shù)據(jù)包“捎帶”的方式，將網絡擁塞信號逐跳更新直至反饋回端節(jié)點;端節(jié)點會根據(jù)用戶內容請求生成興趣包，且會根據(jù)收到的具體擁塞信號作出適合當前網絡狀態(tài)的速率調整;若數(shù)據(jù)包沒有在預定時間內成功返回，端節(jié)點根據(jù)當前是否仍需要該內容選擇是否對興趣包重傳，具體流程如圖1所示。

為實現(xiàn)上述通信過程，網絡中運行三種包：興趣包、數(shù)據(jù)包和NACK包。其中，NACK包只是在興趣包的基礎上添加了錯誤碼（Error Code）字段信息，其他字段信息與原興趣包相同，當下游節(jié)點收到NACK包，會為此NACK包重新尋找接口進行轉發(fā)。如果當前節(jié)點無法找到滿足速率限制的可用接口，該興趣包會以NACK包的形式回溯到上一跳。

針對NDN多源性，將基于超時與窗口調整的傳統(tǒng)擁塞控制對于端節(jié)點速率變化的影響進行如下分析。

NDN的通信特性使現(xiàn)有的適用于傳統(tǒng)網絡的擁塞控制策略不能直接遷移使用，NDN中的窗口調整需要重點考慮：（1）僅僅依靠超時作為擁塞信號容易造成對擁塞反應不夠有效，即如何選擇適合NDN的擁塞反饋信號，從而能夠準確迅速地對擁塞作出反應并保證網絡吞吐量;（2）由于NDN多源的特性[7，8，11]，對于端節(jié)點的請求，其內容提供者并不固定造成超時值計算不準確的問題，即如何準確地計算NDN中超時值，如何設置端節(jié)點超時重傳策略以保證網絡穩(wěn)定性。

接口限速分析：本文隊列占用的計算不是基于整個路由器緩沖區(qū)，而是針對具體某個接口。設t時刻接口k的當前興趣包轉發(fā)速率，t時刻接口k的興趣包速率限制記為，為接口k的隊列閾值，為前綴prefix對應的流的隊列占用，N（t）為t時刻流的個數(shù)，數(shù)據(jù)包大小記為D_pktsize;Link_capk為接口k對應的鏈路容量。

第一個速率上限為數(shù)據(jù)包返回速率，如公式（1）所示，單位為包/秒，其中為控制參數(shù)。

第二個速率限制為不同流之間的公平速率，針對每個“前綴接口對”（prefix，k）進行公平速率計算，考慮了接口容量、接口隊列占用以及對應接口鏈路容量，如公式（2）所示，其中h為控制參數(shù)。

最終該接口的限制速率不能超過以上兩個限制，若超過，則該接口不可用，需要選擇次優(yōu)接口，并重新進行判斷，接口速率限制如公式（3）所示。不滿足速率限制的接口將會設為不可用。

4 基于多源的端節(jié)點擁塞控制算法

為了解決NDN中擁塞檢測不準確等問題，本文提出了一種基于多源的端節(jié)點擁塞控制算法EBCC。首先在中間節(jié)點進行擁塞信息維護與傳遞更新，并設定超時重傳，然后設計了三種擁塞信號及相應控制處理。

4.1 擁塞信息維護與傳遞更新

每當數(shù)據(jù)包返回至當前節(jié)點vi時，均攜帶其鄰居節(jié)點vj的擁塞信息，包括“本地擁塞信息”（Local Congestion Information，LCI）和“非本地擁塞信息”（Nonlocal Congestion Information，NCI），故每個節(jié)點需要維護兩種擁塞信息。

4.2 超時重傳設定

超時重傳值作為擁塞信號，若計算值過小會導致?lián)砣`判，降低鏈路資源利用率，而過早的超時重傳也會為網絡注入額外的流量，浪費網絡資源，反之若計算值過大會降低用戶服務質量。在TCP/IP中端節(jié)點超時重傳值ReTimerend的計算一般采用公式（8）和（9）進行計算。

其中，為往返時延的線性移動平均值，為往返時延的線性偏差，m為一固定常數(shù)，為未更新之前的往返時延線性移動平均值，為當前的往返時延，為時延平滑參數(shù)。由于NDN多源特性導致這種通過時延平均值計算超時值的方式不準確，因此在公式（8）和（9）的基礎上，HR-ICP[12]采用公式（10）計算ReTimerend，并證明了其穩(wěn)定性。

其中，為一固定常數(shù)，RTTmax為歷史最大往返時延，RTTmin歷史最小往返時延也被認為是傳輸時延，故RTTmax-RTTmin被認為是最大排隊時延的估計值，其基本思想是主要利用瓶頸鏈路排隊時延值來控制端節(jié)點調整窗口。但是這種方式，并沒有真正考慮到NDN網絡多源的特性，RTTmax和RTTmin的測量包含了到所有內容源的時延記錄，無法反映當前網絡擁塞程度。

中間節(jié)點在包中記錄了排隊時延信息，且排隊時延逐跳累積，形成到達端節(jié)點的累積排隊時延AccumQD，AccumQD經過逐跳累積可以較好的反映全局網絡狀態(tài)，且記錄的是當前內容源到端節(jié)點的排隊時延，不會受多源網絡場景影響準確性。綜合以上分析，本文的超時重傳值采用公式（11）進行計算。

其中 為調整參數(shù)，AccumQDcur表示當前累積排隊時延，AccumQDmax代表歷史最大累積排隊時延，由公式（13）可以看出，ReTimerend受歷史時延和當前網絡擁塞狀況影響，如果AccumQDcur較大，表示網絡擁塞較嚴重，則ReTimerend也會較大，反之，較小。

4.3 擁塞信號設計

針對NDN多源性，本文的端節(jié)點擁塞控制共設計了三種擁塞信號。

（1）成功返回數(shù)據(jù)包信號D_pktSuc：當收到D_pktSuc時，可以從D_pktSuc獲取到達端節(jié)點vend時的累積排隊時延AccumQD。通過排隊時延反映擁塞狀況已被很多研究者使用。在此基礎上，考慮NDN多源場景，本文提出累積排隊時延作為擁塞信號之一來對興趣包的速率進行調整。NDN網絡中請求的內容以數(shù)據(jù)包的形式原路返回，只需在返回的數(shù)據(jù)包中增加一個記錄排隊時延的字段，不會增加過多額外的負載;通過累積排隊時延依概率減小擁塞窗口，可以起到預防擁塞的作用。由于到達端節(jié)點的AccumQD通過逐跳累積得到，其計算公式即為公式（6）。

（2）錯誤應答興趣包信號I_pktNACK：NDN多個內容源可產生多條路徑，每個中間節(jié)點的FIB表記錄了內容前綴和對應的一系列可用接口，由于對于每個前綴有不止一個可用接口，若當前接口已經過度擁塞，則可以尋找下一可用接口進行轉發(fā)，利用多條路徑分流的思想來避免擁塞。如果當前節(jié)點無法找到可用接口，那么興趣包會被添加NACK頭部，以I_pktNACK的形式回溯到上一跳，如果上一跳依然無法找到可用接口，興趣包會再次回溯到上一跳。假定網絡擁塞狀況十分嚴重，所有節(jié)點都無法找到可用接口，則I_pktNACK會最終回溯到端節(jié)點，端節(jié)點收到I_pktNACK時，可以判斷此時的網絡狀況較為擁塞，從而減少興趣包發(fā)送速率來對擁塞作出反應。因此I_pktNACK可以作為一個網絡擁塞較為嚴重的擁塞信號。

（3）數(shù)據(jù)包超時信號D_pktTimeout：數(shù)據(jù)包未在預定超時重傳時間ReTimerend前成功返回，視為D_pktTimeout信號。D_pktTimeout的判定依賴于ReTimerend的計算。具體而言，每收到一個數(shù)據(jù)包，在端節(jié)點維護其時延RTT，對維護的N（N默認設為30）個歷史往返時延樣本RTT_samples={RTT1，RTT2，…，RTTN}，有歷史最小時延RTTmin=min{RTT1，RTT2，…，RTTN}，類似的，對于端節(jié)點維護的N個歷史累積排隊時延樣本，有AccumQD_samples={AccumQD1，AccumQD2，…，AccumQDN}，有歷史最大累積排隊時延AccumQDmax={AccumQD1，AccumQD2，…，AccumQDN}，代入公式（11），可以計算出ReTimerend。

4.4 擁塞控制處理

端節(jié)點擁塞控制主要是基于不同的擁塞信號反饋進行相應的速率調整，針對上述三種不同的信號，擁塞處理方法有三種。

（1）收到成功返回數(shù)據(jù)包D_pktSuc擁塞信號的處理：AccumQD通過數(shù)據(jù)包攜帶返回，可以直接從D_pktSuc中獲取，由于AccumQD是累積值，通過多個鏈路匯聚所得，因此在一定程度上反映了全局網絡狀態(tài)。為了避免僅依賴超時作為擁塞信號的窗口調整對時延過于敏感，導致窗口急劇減小，且存在滯后性，本文采用根據(jù)AccumQD依概率減小擁塞窗口，如果需要執(zhí)行窗口減小，則C_window變?yōu)镃_window*α。由圖2所示為窗口減小的概率圖，其中 、 分別為設定的累積排隊時延最小、最大閾值，概率計算為公式（12）。

D_pkt的成功返回，表示當前網絡狀況相對較良好，因此若沒有執(zhí)行依概率窗口減小，則對窗口進行“和式增加”以充分利用鏈路資源，保證吞吐量。采用這種方式，可以根據(jù)累計排隊時延提前對擁塞進行控制，起到了一定的預防擁塞的作用，且依概率進行的方式，使得擁塞控制更為“溫和”。

（2）收到錯誤應答興趣包I_pktNACK擁塞信號的處理：I_pktNACK通過中間節(jié)點逐跳回溯才能最終返回到端節(jié)點，表示整條路徑上的節(jié)點接口可能都已超過了速率限制，因此應當在端節(jié)點減小請求速率，將C_window變?yōu)镃_window*β。

（3）收到數(shù)據(jù)包超時D_pktTimeout信號的處理：當收到D_pktTimeout時，表明當前路徑較為擁塞，將C_window變?yōu)镃_window*γ，并根據(jù)端節(jié)點是否仍有獲取該內容的需求來決定是否進行端節(jié)點重傳。由于本文根據(jù)累計排隊時延已經依概率減小窗口，因此當收到I_pktNACK或D_pktTimeout時，窗口不會進行減半而是采用一個較大的參數(shù)，其中，避免了對時延“敏感”的擁塞控制。

通過上述分析，本文提出了端節(jié)點擁塞控制算法，偽代碼描述如表1所示。

5 性能評價

5.1 拓撲用例

本文采用的網絡拓撲為啞鈴型拓撲和多路徑拓撲。啞鈴型拓撲結構如圖3所示，含有11個節(jié)點，兩條瓶頸鏈路，包含4個興趣請求者，3個路由器和4個內容提供者;多路徑拓撲結構如圖4所示，含有16個節(jié)點，包含3個興趣請求者，4個路由器和9個內容提供者。實線連接線代表常規(guī)鏈路，虛線連接線代表瓶頸鏈路。

5.2 基準機制

本文選取被廣泛認可的HR-ICP以及ARMN[14]作為基準算法進行對比分析。

5.3 評價指標

（1）平均時延興趣包從請求者發(fā)送的時刻記為Timesent，數(shù)據(jù)包返回的時間記為Timereturned，則從興趣包發(fā)出到收到相應數(shù)據(jù)包的往返時延Delay為：

（13）令Delayi表示第i個興趣包的往返時延，網絡當前共發(fā)送了k個包，則平均往返時延為：

（14）（2）丟包率丟包率的計算如公式（15）。其中，Numdrop為網絡傳輸過程中丟失的包個數(shù)，Numtotal為請求者請求的興趣包總數(shù)。

（15）（3）吞吐量吞吐量定義為單位時間Timeunit內處理的數(shù)據(jù)量Dataprocessing，

5.4 端節(jié)點擁塞控制算法性能評價

為了驗證本文提出的端節(jié)點擁塞控制算法的性能，在兩種網絡拓撲下，將本文設計的端節(jié)點擁塞控制算法（下文圖中用EBCC表示）和兩種基準機制分別進行仿真實驗。在網絡初始化階段后，收集全網500～5000個興趣請求對應的平均時延、丟包率和吞吐量三個指標。

（1）平均時延

由圖5和圖6所示為平均時延隨請求數(shù)變化的情況，當興趣請求個數(shù)大于1500時，三種算法逐漸體現(xiàn)出不同性能。EBCC在端節(jié)點設置了基于多種擁塞信號的窗口調整機制，根據(jù)累積排隊時延依概率調整窗口，可以提前控制擁塞，故始終保持最低的平均時延，相比基準算法減少了18.1%～27.2%。HR-ICP在其端節(jié)點設置基于RTT的窗口調整策略，可以在一定程度上在端節(jié)點控制往返時延，因此時延低于ARMN;在ARMN中，其端節(jié)點僅以NACK包作為擁塞信號進行窗口調整，由于NACK包需要通過逐跳回溯才能到達端節(jié)點，端節(jié)點無法及時獲取網絡狀態(tài)進行速率調整，導致時延很大。

（2）丟包率

由圖8和圖9所示為丟包率隨請求數(shù)變化的情況，在兩種拓撲中丟包率隨興趣請求個數(shù)的變化趨勢大體相似，在興趣請求個數(shù)為500～2500范圍內丟包率隨興趣請求個數(shù)的增大變化相對較為平穩(wěn);當興趣請求個數(shù)逐漸增大后，三種擁塞控制算法逐漸體現(xiàn)出不同的性能。其中，EBCC在端節(jié)點設置了基于多種擁塞信號的速率調整機制，對擁塞信號的反應更加靈敏也更加貼合網絡實際狀態(tài)，且在端節(jié)點設置了基于NDN多源網絡場景的超時定時機制，因此丟包率最低，相比于基準算法減少了14.8%～15.1%。HR-ICP在以RTO作為擁塞信號，當發(fā)生數(shù)據(jù)包超時時，則認為發(fā)生擁塞，并將擁塞窗口乘性減小，一定程度上控制了丟包率;ARMN在端節(jié)點僅以NACK包作為擁塞信號進行窗口調整，由于NACK包需要通過逐跳回溯才能到達端節(jié)點，端節(jié)點無法及時獲取網絡狀態(tài)進行速率調整，導致丟包率最大。

（3）吞吐量

由圖10和圖11所示為吞吐量隨請求數(shù)變化的情況。在興趣請求個數(shù)較小時，吞吐量隨興趣請求個數(shù)增加而增加的趨勢較為明顯;當興趣請求個數(shù)大于2500之后，吞吐量受興趣請求個數(shù)影響不再明顯，不同機制逐漸體現(xiàn)出不同的性能。HR-ICP在其端節(jié)點采用的ICP的調整機制主要是依據(jù)RTT，當RTT過大時會急劇減小窗口，導致端口隊列常處于較小的狀態(tài)，最終端節(jié)點的吞吐量也較低;ARMN利用了多路徑轉發(fā)的思想，對NACK包重新尋找接口而不是延遲轉發(fā)保證了吞吐量;EBCC在端節(jié)點根據(jù)多個擁塞信號進行窗口調整，且擁塞信號的選擇能夠較好地反映全局網絡狀態(tài)，且由于可以根據(jù)累積排隊時延依概率對擁塞窗口進行調整，避免時延敏感，其速率調整也能更好地利用網絡資源，始終保持較高的吞吐量，相比于基準算法提升了13.2%～15.8%。

4 結束語

針對NDN擁塞控制中端節(jié)點擁塞信號獲取不準確等問題，本文通過對NDN現(xiàn)有的擁塞控制算法進行分析，提出了一種基于多源的端節(jié)點擁塞控制算法EBCC。該算法考慮并設計不同的擁塞信號，可以依據(jù)不同的擁塞信號進行端節(jié)點速率調整，并在端節(jié)點對超時進行重新設定，避免時延敏感，保證吞吐量。在下一步研究中，將分析具體緩存策略對擁塞控制的影響，并將NDN中間節(jié)點的轉發(fā)、緩存與擁塞控制三者綜合考慮，使擁塞控制更為有效。