命名數據網絡中的一種主動擁塞控制機制研究

王亞東，張 悅，陳延祥，張 宇

1 引言

隨著業務模式的快速發展，基于TCP/IP的體系結構逐漸暴露出諸多問題，比如可擴展性差、動態性差、安全可控性差等[1]。為了解決這些問題，命名數據網絡(Named Data Networking，NDN)被提出并成為廣泛研究的未來互聯網體系架構[2]。NDN在處理封包是依據數據內容而非位置來命名，通過利用名稱尋址并加入內容存儲器結構，將內容和位置分離開，從根本上解決了當今TCP/IP網絡中以主機為中心的通信模式和用戶以內容為中心的網絡需求之間的矛盾[3]。

空間網絡不同于地面通信網，具有拓撲動態變化大、鏈路間歇性連接、高傳輸時延、傳輸數據率低、信道不對稱等特點。目前空間容遲容斷網絡(Delay/Disruption Tolerant Networking， DTN)仍然使用單播協議進行端到端的傳輸，這樣的傳輸方式無法滿足載人航天探測任務中對數據傳輸實時性、數據量大、內容共享等需求，空間網絡需要一種不同的網絡架構來解決這些問題。而NDN按名字尋址，完全不依賴位置，路由請求和轉發只依賴數據自身，請求者和提供者之間無需一直保持連接狀態。這使得NDN有著極好的網絡擴展性和對動態網絡的適應性，能夠為載人深空探測任務提供更安全有效、更可靠的通信服務；同時NDN引入節點緩存，使得衛星網絡中因位置變化導致的傳輸中斷無需重新建立連接，可以從臨近節點匹配獲取資源，原生支持網絡多播和信息共享，有效節省數據傳輸開銷，充分利用衛星網絡資源。

空間網絡對網絡的可靠性要求較高，因此擁塞控制極為重要。擁塞的發生與網絡自身的體系架構密切聯系。擁塞控制機制的提出以特定的網絡為前提。相比于TCP/IP網絡，NDN中的節點設有持久性緩存，允許多路徑傳播和多播傳播，這使得擁塞控制變得復雜[4]。在TCP/IP網絡中擁塞控制機制是為端對端連接設計的，通過重復確認字符(Acknowledgement，ACK)和超時機制檢測擁塞，通過基于滑動窗口的和式增加，積式減少(Additive Increase Multiplicative Decrease，AIMD)減小客戶端注入網絡的流量。而NDN中包的傳播是多路徑的，興趣包對應的數據包可能會從不同節點返回，這些節點的遠近會對返回數據的往返時延(Round-Trip Time，RTT)造成很大的影響。因此，在NDN中，無法對一個數據包設置一個合適的RTT值，單純的超時機制無法滿足NDN中擁塞檢測及控制需求，需要更加準確的網絡層控制算法來支持擁塞控制。

目前，現有NDN擁塞控制算法存在對先驗知識的依賴，對網絡狀態的變化不夠敏感，難以適用于空間網絡這種拓撲高度動態，鏈路延遲大、誤碼率高等情況。基于這種現象，本文研究基于強化學習的NDN擁塞控制機制。已有一些研究將強化學習方法應用于傳統TCP/IP網絡的擁塞控制。王春茹等[5]運用強化學習的智能化控制方法設計了網絡擁塞控制器，可以調節源端發送數據的速率，使可能發生擁塞的交換機緩沖區隊列長度逼近設定值，從而減少了擁塞的發生。李鑫[6]基于強化學習理論中的Q-學習方法設計了主動隊列管理算法。控制器學習TCP/IP網絡中狀態-動作對所對應的Q-函數值，并利用反映了Q-函數值與當前網絡狀態聯系緊密程度的可信度值來調節學習率。

本文針對NDN體系架構，以最小時延為目標，在考慮NDN中的網內緩存、多路徑轉發，并不對鏈路容量或數據包大小做任何假設的情況下，結合強化學習中的 Sarsa(λ)算法，充分利用NDN中路由節點的計算和學習能力，設計智能的動態轉發策略，以實現對NDN的擁塞控制功能。

2 基于強化學習的NDN擁塞控制方法設計

良好的轉發策略可以自主選擇合適的鏈路進行數據轉發，能在很大程度上預先規避擁塞鏈路，并在擁塞現象發生后有效地緩解擁塞。本文從轉發策略的角度出發，討論容遲容斷命名數據網絡中的擁塞控制問題。在考慮網內緩存、多路徑轉發，并不對鏈路容量或數據包大小做任何假設的情況下，將NDN中路由節點選擇端口轉發興趣包的過程，建模為強化學習中一個狀態選擇執行動作轉移到另一個狀態的過程，設計更加實際可行的轉發策略。針對NDN應用的特殊網絡環境，本文選擇最小時延為目標，結合強化學習中的Sarsa(λ)算法，在原有轉發策略的基礎上設計智能的轉發策略，以實現擁塞控制的目的。

2.1 模型的建立與分析

在考慮緩存及多路徑路由因素下，網絡擁塞模型難以建立，而時序差分學習無需模型，直接從經驗中學習。時序差分(Temporal Difference，TD)算法中應用較廣的有Q-learning和Sarsa策略[7]。然而結合資格跡后，由于Watkins[8]的Q(λ)算法具有截斷有效序列的問題，而改進的 Peng的Q(λ)算法[9]很難實現，本文使用Sarsa(λ)算法實現NDN中網絡包的智能轉發。

將路由節點轉發興趣包到相應數據包返回該節點的時間記為響應時間RTTr。需要注意的是，RTTr越小越好，因此計算Q值時，將-RTTr作為即時回報。在NDN環境中，節點選擇Q值最大的鏈路，一方面可以在總體上減少用戶收到需求內容的時間，提高用戶體驗；另一方面實現了主動避免擁塞，路由節點轉發興趣包時優先選擇網絡時延短的，即非擁塞的鏈路，避免再向擁塞鏈路注入更多的流量。本文將Q值為轉發策略的依據，采用結合資格跡的Sarsa算法——Sarsa(λ)算法求解最佳策略。

所述模型建立方法如下：

1)利用NDN中路由節點的學習和計算能力，將路由節點看作智能體agent；

2)將路由節點向不同的端口轉發興趣包的過程作為agent選擇執行動作的過程，多個可轉發的端口對應多個可執行的動作；

3)將興趣包從一個路由節點通過選擇端口轉發到另一個路由節點的過程，映射為agent將興趣包從一個狀態通過選擇相應的動作轉移到另一個狀態的過程；

4)NDN中原有的數據包結構如圖1所示。本文在原有結構基礎上，擴展了時間戳字段，如圖2所示。每個路由節點選擇一個端口轉發興趣包后，由興趣包發出到對應數據包返回的時間差RTTr得到反饋給 agent的立即回報值 r(s，a)，RTTr通過相應的數據包返回時攜帶的時間戳信息計算得到。時間戳通過向數據包結構中添加新的字段項以實現攜帶。路由節點的FIB表中每一個前綴對應一個條目，條目中的每一個端口都有一個度量條目(如鏈路開銷等)，可以存儲標準化的度量信息。本文將Q值加入原有的度量條目中，修改后的FIB條目如圖3所示；

5)記狀態空間為 S={St0，St0+1，…，ST-1，ST}，其中，ST表示T時刻agent的狀態，狀態指節點將興趣包從當前節點發送到存儲相應數據的節點；記動作集 A={At0，At0+1，…，AT-1，AT}， 表示不同狀態下所選擇的動作；一個狀態的動作集記為A(s)={a1，a2...，an-1，an}， 表示興趣包到達一個路由節點后可選的n個轉發端口；路由節點為每一個前綴下的每一個轉發端口維護一個動作值Q(s，a)， 動作值更新公式見式(1)、式(2)[7]。

圖1 原有數據包結構Fig.1 Original data packet structure

圖2 修改后的數據包結構Fig.2 Modified data packet structure

圖3 修改后的FIB表項Fig.3 Modified FIB table entries

其中，s為agent的當前狀態，a為當前狀態下選擇的動作，β為學習速率，δt為誤差，r(s，a)為回報值，γ為折扣率，λ為跡衰減參數，St為t時刻agent的狀態，At表示t時刻agent的動作，Qt(s，a)為 t時刻狀態-動作對 (s，a) 的動作值，Et(s，a) 為 t時刻狀態-動作對 (s，a) 的資格跡，資格跡的使用可以提升算法的效率。

2.2 包轉發策略的實現

采用結合資格跡的Sarsa算法——Sarsa(λ)算法求解最佳策略。在更新策略的方法上，采用針對現有動作值的貪婪策略：ε-greedy策略，即，以1-ε的概率選擇最佳動作，以ε的概率選擇其他非貪婪動作[10]。轉發策略分為初始化階段和應用及持續探索階段。

1)初始化階段：獲得初始Q值。當路由節點收到興趣包后，向所有可轉發的端口發送興趣包，獲得每個端口的初始Q值；

2)應用及持續探索階段：根據初始化階段得到的初始Q值，按照貪婪策略進行探索并持續更新Q值。當得到初始Q值后，路由節點依據ε-greedy策略進行探索。路由節點向端口轉發興趣包，以1-ε的概率選擇最佳Q值端口，以ε的概率選擇其他端口以保證持續性探索，在數據包返回的過程中不斷更新Q值。當端口超時后，將公式(1)中的δt設置為一個不小于108的常量，這樣Q值會很大，作為超時的懲罰機制。

包轉發策略的具體實施流程如下(圖4)：

1)路由節點判斷接收的包類型，若為興趣包，轉步驟2，若為數據包，轉步驟7；

2)檢查自身緩存中是否有與該興趣包匹配的數據，若存在，則從該興趣包到達的接口返回與之匹配的數據包，結束；否則直接轉步驟3；

3)在FIB中查找可能的下一跳，若無下一跳，返回 NACK-NOROUTE(查找路由失敗)，結束；有則轉步驟4；

4)判斷當前狀態，若為初始化階段，轉步驟5；若為應用即持續探索階段，則轉步驟6；

5)向所有可轉發的端口發送興趣包，獲得每個端口的初始Q值，結束；

6)依據ε-greedy策略隨機選擇是否貪婪，貪婪則選擇可能的下一跳中Q值最小的節點轉發興趣包，結束；不貪婪則在可能的下一跳中隨機選擇除Q值最小以外的節點轉發興趣包，結束；

7)查詢PIT表，若無對應條目，則丟棄該數據包，結束；否則根據NDN數據包的轉發流程轉發數據包，轉步驟8；

8)從數據包中提取信息并更新對應端口的Q值，結束。

圖4 轉發策略流程圖Fig.4 Flow chart of forwarding strategy

采用上述方法應用于NDN中，能夠在很大程度上避免網絡擁塞的發生。

3 仿真與結果

本文提出的擁塞控制機制在Linux操作系統下，基于ns-3的ndnSIM仿真平臺進行性能測試[11]。網絡拓撲結構如圖5所示。仿真設置中，共有9個網路節點，其中包括4個內容請求者(Consumer)、4個路由器為中間轉發節點(Router)和1個內容生產者(Producer)。其中每條鏈路的帶寬和延遲設置如表1所示。由表1可以看出，Router1和Router2分別有一條相對較好和相對較差的輸出鏈路：Router1-Router4為較好的輸出鏈路，相較Router1-Router3來說，此鏈路具有更大的帶寬和更小的延遲，單位時間傳輸的數據更多。Router2對應的2條輸出鏈路同理，但總體上優于Router1的輸出鏈路。

圖5 拓撲結構Fig.5 Topological structure

表1 鏈路設置表Table 1 Link setting table

本文將提出的智能轉發策略與最佳路由算法(Best Route)、多路徑轉發算法(Multicast)以及請求轉發算法(Request Forwarding)進行對比。仿真硬件為ubuntu16.04LTS操作系統、內存為15.6 GB，Inter Core i7-4749 CPU@3.60GHz?8，硬盤為500 GB的SSD。仿真在ndnSIM2.6環境下進行，依次將上述算法記為 Sarsa(λ)、BestRoute、Multicast和 RFStrategy。 在 Sarsa(λ)算法中，設學習速率β=0.6，折扣率γ=0.5，跡衰減參數 λ=0.5，概率 ε=0.05，仿真實驗的運行時間為100 s。

3.1 數據包交付率

數據包交付率指消費者發出的興趣請求被數據包響應的比例。設消費者發送興趣包的速率為100 Packets/s，交付率隨鏈路誤碼率的變化結果如圖6所示。可以看出，隨著鏈路誤碼率增大，4種轉發策略的交付率都會降低，這是因為誤碼率增大導致網絡丟包增多，一部分數據包無法回到消費者。其中，Best Route根據最小跳數選擇最佳路徑，無法根據鏈路的實際情況進行調整選擇，整體性能最差。Multicast算法會將興趣包轉發到所有記錄的端口，只要有一條較好的鏈路，就可以完成交付任務，對鏈路誤碼率不敏感，因此整體交付性能最好；但這種算法沒有擁塞控制機制，會大量消耗鏈路帶寬。基于Sarsa(λ)的轉發策略和RF算法都是動態轉發策略：RF算法基于每個端口的等待響應的興趣包個數為端口分配權重，再根據權重隨機選擇轉發端口，考慮了數據包是否返回和返回的比例；基于Sarsa(λ)的轉發策略不僅考慮了數據包返回的情況，還隱性地考慮到了鏈路狀態，交付性能優于RF算法。

圖6 數據包交付率隨鏈路誤碼率的變化結果Fig.6 Changes of packet delivery rate with BER

設鏈路誤碼率為0.3，數據包交付率隨負載的變化結果如圖7所示。負載越大，網絡中的流量越大，大量的網包會加重網絡負荷，導致網絡擁塞的發生，此時所有算法的性能都會下降。Multicast多端口轉發興趣包，第一個數據包從某條鏈路返回后，其他鏈路仍然會返回數據包，而這些重復的數據包會被丟棄，造成帶寬的極大浪費；Multicast算法也因此對鏈路可用帶寬較敏感。網絡中數據包的不斷增多可以等價為鏈路可用帶寬的減小，此時，Multicast的性能會下降。從圖7中可看出，當負載較小時，Multicast的性能優于Sarsa(λ)，當負載不斷增大時，Multicast的性能下降較快，落于 Sarsa(λ)之后。RF的交付率排在Multicast之后，Best Route交付率最低。

圖7 數據包交付率隨負載的變化結果Fig.7 Changes of packet delivery rate with load

3.2 丟包率

網絡層的丟包率可以直接反應網絡數據傳輸的可靠性。丟包率隨誤碼率的變化結果如圖8所示，隨負載的變化結果如圖9所示。可見，雖然Multicast的數據交付率很高，其丟包率也非常高，沒有任何擁塞控制的機制。基于Sarsa(λ)的轉發策略和RF能主動避開擁塞和故障的鏈路，從而極大減小了鏈路丟包數量，但Sarsa(λ)的丟包率更小。Best Route丟包率低于Multicast，但由于無法感知鏈路的狀態，可能會選擇擁塞較嚴重的端口轉發興趣包，丟包數量較多。

圖8 丟包率隨誤碼率的變化結果Fig.8 Changes of packet loss rate with BER

3.3 平均時延

圖9 丟包率隨負載的變化結果Fig.9 Changes of packet loss rate with load

平均時延即消費者發送興趣包后，接收到數據包的平均響應時間，是網絡服務質量的重要指標之一。平均時延隨誤碼率的變化結果如圖10所示，隨負載的變化結果如圖 11所示。基于Sarsa(λ)的轉發策略以最小時延為目標，選擇傳輸時延最小的路徑轉發興趣包，使得最終的平均時延最小。圖10中，Multicast的平均時延最優，同數據包交付性能，只要有一條鏈路可用，數據包就可以返回，因此減小了用戶的響應時間。但圖11中，負載增大后，由于網絡中數據包的大量增加，Multicast性能下降，其平均時延也增長較迅速，Sarsa(λ)的平均時延在整體上變為最優。RF在其選擇端口的標準中，主要考慮數據包返回的比例而不是快慢，平均時延較高。Best Route不考慮鏈路時延的問題，時延最大。

由以上對比可知，本文提出的智能轉發策略能有效增加網絡的數據遞交率，減少丟包數量和網絡平均時延，除在平均時延隨誤碼率變化的效果上略低于Multicast算法外，在其他方面整體均優于其他3種算法。

圖10 平均時延隨誤碼率的變化結果Fig.10 Changes of average delay variation with BER

圖11 平均時延隨負載的變化結果Fig.11 Changes of average delay variation with load

4 結論

1)本文將強化學習算法應用到NDN的轉發策略中，實現智能的動態轉發策略，以主動避免和緩解擁塞。將資格跡與在線時序差分策略結合，以最小時延為目標，提出了基于Sarsa(λ)的轉發策略；

2)在 ndnsim平臺上仿真，與已有的 Best route算法、Multicast算法和RF算法進行比較，仿真結果表明，該算法能有效增加網絡的數據遞交率，減小丟包數量和網絡平均時延，除在平均時延隨誤碼率變化的效果上略低于Multicast算法外，在其他方面整體均優于其他3種算法；

3)本文提出的轉發策略很大程度上避免網絡擁塞的發生，并在擁塞發生時及時地發現問題鏈路，選擇鏈路狀態良好的路徑轉發數據，有效地減少擁塞。