命名數據網絡中基于Dec-POMDP的緩存策略

姚進發

(銳捷網絡股份有限公司 銳捷研究院，福建 福州350002）

0 引言

隨著網絡技術的發展以及互聯網用戶的快速增加，網絡應用的主體正逐步向內容獲取和信息服務演進。早期為解決端到端通信問題而設計的基于TCP/IP的體系架構對計算機網絡性能的限制使得傳統互聯網難以滿足海量的網絡數據處理需求，這激發了人們對未來網絡架構設計的重新思考與研究。信息中心網絡(Information-Centric Networking，ICN）[1]作為一種“革命性”體系架構，其以內容為中心的特點無縫迎合了未來網絡的發展趨勢，因而受到研究學者的廣泛關注。在ICN體系的諸多部署方案中，命 名 數據網絡(Named Data Networks，NDN）因其先進的設計理念、靈活的路由轉發機制以及分布式的網內緩存方式等良好特性已經成為ICN中的研究熱點。

為了滿足高效的內容分發與獲取的需求，NDN在設計時通過引入網內緩存(in-network caching）機制來減少不必要的網絡數據傳輸，從而提高數據傳輸效率，增強網絡的可擴展性。在NDN中，每個網絡節點都具有一個內容存儲庫(Content Store，CS），用于緩存經過本地節點的數據，從而為后續與數據對應的相關請求提供路徑緩存服務。然而，與海量的數據相比，網絡節點中CS的容量相當有限，因此如何合理地進行內容放置和緩存決策，是影響NDN性能的關鍵因素。

NDN在設計之初默認采用處處緩存(Cache Everything Everywhere，CEE）策 略[2]，但 該 方 法 會 導 致節點緩存內容趨于同質化，故無法充分發揮網內緩存效率。近年來，學術界圍繞NDN緩存技術的研究已經取得了不少成果。文獻[3]針對CEE策略的緩存冗余問題，提出只在請求命中節點的直接下一跳緩存數據(Leave Copy Down，LCD），一定程度上提高了網絡緩存的利用率，但流行度高的內容需要被訪問多次才能緩存到邊緣節點上。文獻[4]提出了一種基于內容流行度的協作緩存策略(WAVE），它根據內容請求次數以指數方式逐步增加沿途節點上所緩存的數據包個數，從而實現數據在空間存儲位置上的差異化，但該方案并沒有考慮內容請求序列的相關性。文獻[5]通過估算路徑的剩余存儲能力來計算同一路徑上的不同數據流在沿途各節點上的緩存概率，從而提出了一種兼顧不同數據流間存儲公平性的概率緩存策略(ProbCache）。文獻[6]提出了一種分布式沿途緩存策略，即最大增益網內緩存(MAGIC）。網絡節點基于內容流行度和路由跳數來計算內容的緩存增益，并在數據傳輸路徑上選擇具有最大緩存增益的節點進行內容緩存，從而達到減少網絡帶寬消耗的目的。但該方案在進行緩存決策時需要重新計算各內容的流行度，因此計算量大，執行復雜度高。文獻[7]提出了一種主動緩存策略，其主要思想是利用熵來衡量移動性預測的不確定性，并定位最佳的預取節點，從而降低服務器負載，并減少緩存冗余。

針對NDN的網絡架構特性，本文提出了一種基于Dec-POMDP的NDN緩存策略。首先利用Dec-POMDP理論框架對NDN網絡的緩存問題進行建模，該模型考慮了緩存節點間的相互協作，以實現降低緩存內容冗余度和內容優化存儲的目的。在此基礎上，通過限制節點的協作域的方法來避免引入過量的額外通信開銷，進而降低模型求解的復雜度。最后，本文給出了一種基于強化學習的局部近似最優緩存策略的求解算法。仿真結果表明，該方法能夠有效增加緩存內容的多樣性，提升緩存命中率，進而減小用戶請求內容的總跳數。

1 NDN工作原理

NDN網絡中的數據傳輸采用基于用戶驅動的“拉”模式數據獲取方式。NDN中存在兩種數據包類型 ： 興 趣 包 (Interest Packet）和 數 據 包 (Data Packet）。用戶通過發送包含內容名稱的興趣包來向網絡請求數據，該請求興趣包將被路由到存有對應數據的鄰近節點或服務器節點；然后，攜帶該請求內容的數據包沿著興趣包的反向路徑被逐跳傳送給數據請求者。

如圖1所示，當請求興趣包到達時，網絡節點根據所請求的內容名字依次在內容存儲庫(Content Store，CS）、待定興趣表(Pending Interest Table，PIT）和轉發信息庫(Forwarding Information Base，FIB）中進行匹配查詢。若CS中存在與該請求對應的數據包則直接將數據傳回給請求者；否則，如果PIT中含有與該請求對應的條目，則將該請求的進入接口添加到對應條目的接口列表中，然后將該請求拋棄；如果PIT也匹配失敗，則新建一個PIT條目并查詢節點的FIB，將請求轉發到下一跳節點。

圖1 NDN中請求包轉發過程

當節點收到響應數據包時，節點根據對應的PIT表項中所記錄的請求接口列表進行數據轉發，并根據相應的存儲策略將其存儲在節點的CS中，如圖2所示。

圖2 NDN中數據包轉發過程

2 基于Dec-POMDP的NDN緩存策略

考慮一個離散時間的Dec-POMDP動態系統。在每一個決策時刻，每個智能體首先從系統中獲取在當前狀態下各自的觀測信息，然后做出決策并執行動作，系統根據狀態轉移函數轉移到下一個狀態，并獲得一個即時回報，整個過程周而復始。因此，一個Dec-POMDP模型通常可以由一個7元組定義[8]：

其中，N={1，…，N}表示系統中所有智能體的集合。S={Si}表示一個有限的系統狀態集合，其中Si表示智能體i的內部狀態集。A={Ai}表示所有智能體的聯合動作集，其中Ai表示智能體i的可用動作集。Ω={Ωi}表示系統聯合觀測的有限集，其中 Ωi為智能體 i的觀測集。P：S×A→[0，1]表示系統的狀態轉移函數，p(s′|s，a）表示系統在狀態 s下采取聯合行動 a后轉移到新狀態 s′的概率。O：S×A×S→[0，1]表示系統的觀測函 數。 O(o|s，a，s′）表示狀態s中采取聯合行動a后轉移到新狀態 s′時獲得聯合觀測 o={o1，…，oN}∈Ω 的條件概率。 R：S×A→Z表示系統的效用函數。R(s，a）表示智能體集合在狀態s中采取聯合行動a后所獲得的回報。H表示整個決策過程的總周期數，稱為步數(Horizon）。下面給出關于NDN緩存問題的Dec-POMDP模型中各元組定義。

2.1 網絡模型及相關假設

NDN網絡模型如圖3所示。網絡由源服務器節點、路由節點以及用戶節點構成。源服務器節點是內容數據的發布者，維護內容數據的一個永久副本。路由節點具備存儲功能，可以緩存經過節點的部分數據。用戶節點通過邊緣路由節點向網絡請求數據。用戶請求被逐跳轉發至擁有該請求內容的中間路由節點或源服務器節點，并觸發相應數據包沿著請求興趣包的反向路徑傳送給請求者。

在NDN中每個內容對象被劃分成若干相同大小的數據塊，并以數據塊為單位進行存儲。假設網絡中共有M種不同的數據塊對象，記為M，且都具有一個固定的數據源。考慮具有N個路由節點的網絡，節點 n的緩存大小記為 Cn，且 Cn?M；節點接收來自本地用戶或相鄰下游節點所轉發的內容請求。節點n上的轉發接口個數記為Fn。假設網絡中的用戶請求服從泊松分布，根據隨機服務系統原理，服從泊松分布的輸入流的輸出也服從泊松分布，因此鄰節點上未命中的請求序列也服從泊松分布。

圖3 NDN網絡模型

2.2 狀態和狀態空間

網絡中的所有節點構成Dec-POMDP模型的智能體集合 N。記網絡節點 n的狀態為 sn=[xn，yn]，其中 xn=[x11，…，x1M，…，xFn1，…，xFnM]表示當前時刻節點n中各轉發接口上待響應的內容請求的情況，xfnm表示節點n中第fn個接口上關于數據塊m的待響應請求數量；yn=[yn1，…，ynM}表示當前時刻節點 n上 CS中的緩存情況，ynm∈{-1，0，1}表示數據塊 m的緩存狀態。ynm=-1表示節點n上不存在數據塊m的副本；ynm=0表示節點n上擁有數據塊m的臨時副本，但數據塊m不被存儲于節點的CS中而是僅用于響應當前請求，且當數據轉發完成后就會被立即刪除；ynm=1表示數據塊m被存儲于節點n的CS中。各網絡節點的狀態構成當前決策時刻的網絡狀態，記為 s=[s1，…，sN]。

2.3 決策時刻

2.4 行動和行動空間

由NDN的工作原理可知，當收到響應數據包時，節點根據其CS中的存儲剩余空間以及該內容被訪問的情況來決定是否緩存該數據包的副本。因此，本文定義NDN節點接收到響應數據包的時刻為有效決策時刻。具體地，當事件或事件發生時節點不進行任何存儲決策，此時節點n的行動記為an=。當事件發生時，(1）若節點 n的 CS具有剩余存儲空間則直接緩存該數據包副本而不需要任何決策，也即采取行動an=；(2）若節點 n的 CS中無足夠存儲空間且節點需要存儲該數據包，那么節點根據存儲策略選擇當前CS中的某個數據包 k(k∈{1， … ，M}）進 行 替 換 ，記為an=；(3）此外，令 an=表示節點n采取“不存儲該數據副本”的行動。綜上，網絡節點n的行動空間An可以表示為：{-1，0，1，…，M}}。進而可得到所有網絡節點的聯合行動為 a=[a1，…，aN]，以及網絡節點的聯合動作

2.5 觀測空間

在每個決策時刻，網絡節點先獲取當前網絡狀態的一個觀測然后再進行存儲決策。假設同一時刻只有一個事件e∈E發生。定義節點的觀測表示當前決策時刻下該節點上CS中緩存內容的變化情況。具體地，當事件生，即節點接收到數據請求或完成數據請求服務時，定義節點 n的觀測為 on=yn。 當事件生，即節點n接收到新響應數據包時，定義節點n的觀測為 on=yn+2Bm，其中 Bi=(0，…，1，…，0）表示第i個元素為1的單位向量。根據上述定義可知，當Σon≤Cn時，節點不需要進行決策，當Σon=Cn+1時，節點需要根據存儲策略刪除CS中的某個數據塊。進而各網絡節點的本地觀測on構成網絡的一個聯合觀測 o={o1，…，oN}。

2.6 效用函數

網絡性能分析是網絡優化的基礎，網絡性能評價指標是判斷網絡優化效果的依據。常用的評價指標包括帶寬、時延、吞吐量等。本文考慮以緩存命中率以及網絡平均跳數作為聯合策略的衡量標準。定義節點n的效用函數為：

如果對于任意聯合策略向量ω(t），任意初始狀態 s0，有 J(ω*(t），s0）≥J(ω(t），s0），那 么 策 略 ω*(t）為最優聯合策略，其相應的最優性能值記為J*。

2.7 狀態轉移函數

由于當Σyn≤Cn時節點n采用貪婪存儲策略，故不需要進行存儲決策，僅考慮在Σyn=Cn+1的情況下，節點n在內部狀態sn=[xn，yn]上采取行動an后轉移到下一個狀態的概率。

2.8 觀測概率

定義M3={m|ynm=-1}表示不存在于節點n上的內容集合。根據節點觀測狀態的定義，可得到如下節點觀測概率函數：

3 基于Dec-POMDP的分布式緩存協作策略搜索算法

Dec-POMDP模型最優策略的求解是一個NEXP-complete問題，即使是小規模的問題也往往需要在巨大策略空間上進行最優策略搜索，從而限制了其在較大規模實際問題中的運用。鑒于Dec-POMDP模型精確求解所要求的時間和空間復雜度高，因此不少學者致力于模型近似解的研究，通過利用動態規劃或者啟發式算法來搜索最優策略，以緩解模型求解過程的維度災難和計算復雜度的問題。而Q學習算法作為經典的強化學習算法，近年來被廣泛應用于多智能體系統體系結構模型的求解中[9-13]。此外，理想情況下，節點通過感知網絡全局狀態信息，并根據其他節點所采取的緩存策略進行緩存決策，從而實現網內緩存資源配置的全局最優化。然而，這種全域節點間的相互協作會帶來大量的額外通信開銷，因此實際中一般只考慮一定跳數范圍內的節點協作方式。這里只考慮一跳的情況，即網絡節點通過與相鄰節點進行緩存協作逐漸達到整個網絡的最優聯合策略。基于上述考慮，本文采用一種近似的Q學習方法來求解局部最優策略。

定義節點n的鄰居節點集合為Nn，根據文獻[14]，假設網絡狀態滿足狀態轉移獨立性，則可以得到近似局部聯合觀測概率為：

4 數值仿真

為了評估本方案的性能，本文采用基于NS-3的ndnSIM[15]進行仿真。仿真拓撲共有100個節點，其中1個源服務器節點和20個客戶端節點，其余為路由節點。源服務器節點中存儲5 000個不同的數據，每個數據包的大小均為1 024 KB，數據包的流行度服從Zipf分布，實驗中參數α的取值范圍為0.7～1.3。除特殊說明外，實驗中路由節點 CS的總容量設定為數據總數的10%，且初始為空。客戶端通過邊緣路由節點向網絡請求數據，且請求到達率服從泊松分布。仿真時間為2 000 s，其余參數均為固定默認值。下面給出本文所提出的基于Dec-POMDP緩存算法與CEE、LCD緩存策略的實驗結果對比分析。首先定義如下性能指標：

(1）平均緩存命中率：定義為由網內路由節點服務的請求數與總的用戶請求數之比，即：

式中，Req_hitn表示在路由節點上命中的請求數量；Req_usern表示路由節點n上接收到的本地用戶請求個數。

(2）平均跳數減少率：反映由于緩存系統的加入使用戶請求內容跳數減少的比率，定義為：

式中，hop_csi表示緩存命中節點到請求用戶間的跳數；hop_seri表示請求用戶到源服務器節點間的跳數；R_count表示總的用戶請求數。

圖4為不同緩存策略下，用戶請求在網內的平均緩存命中率隨Zipf分布參數α變化的曲線。如圖所示，相比于另外兩種策略，基于Dec-POMDP的緩存策略能夠顯著提高用戶請求的緩存命中率。這是由于Dec-POMDP模型中節點在進行緩存決策時考慮了鄰居節點間的緩存協作，因此能夠有效地減少緩存內容的冗余度，提升緩存利用率。此外，隨著參數α的增大，三種策略的緩存命中率不斷增大；當參數α大于1.1時，命中率增大的速率有所減緩，這主要是受限于網絡路由節點的緩存容量。

圖4 平均緩存命中率隨參數α變化曲線

圖5為不同緩存策略下，用戶請求的平均跳數減少率隨Zipf分布參數α變化的曲線。由于Dec-POMDP模型能夠更好地刻畫網絡狀態的不確定性和用戶請求的隨機性，因此Dec-POMDP策略能夠更準確地預測請求內容的流行度并有選擇性地緩存更有價值的內容，從而有效減少用戶請求所需的跳數。

圖5 平均跳數減少率隨參數α變化曲線

圖6為不同緩存策略下，用戶請求在網內的平均緩存命中率隨網內存儲總容量變化的曲線。由圖可知，在不同網內存儲容量配置下，基于Dec-POMDP的緩存策略的性能均優于CEE和LCD，說明本文提出的緩存策略能更有效地利用緩存資源。此外，對于CEE和LCD兩種緩存策略，當網內存儲容量小于15%時，網內存儲容量的增加對平均緩存命中率的提升效果并不明顯；當網內存儲容量繼續增加直至達到35%時，網內請求的平均緩存命中率有顯著提升；此后，網內存儲容量繼續增長，平均緩存命中率的增長速度逐漸變緩。這是因為這兩種策略存在緩存冗余，因此無法充分利用網內緩存資源。而基于Dec-POMDP的緩存策略由于能夠處理請求的動態變化，因此在不同網內存儲容量下均能更有效地利用緩存資源。

圖6 平均緩存命中率隨網內存儲容量變化曲線

圖7為不同緩存策略下，用戶請求的平均跳數減少率隨網內存儲總容量變化的曲線。從圖中可看出，在不同網內存儲容量條件下，三種緩存策略的平均跳數減少率性能曲線與圖6中對應的曲線趨勢相符。由于基于Dec-POMDP的緩存策略能夠有效地利用緩存資源，因此在不同網內存儲容量下，基于Dec-POMDP的緩存策略相對于CEE和LCD能夠更有效減少用戶請求所需的跳數；且隨著網內存儲容量的增加，基于Dec-POMDP的緩存策略與另兩種策略間的性能差異越明顯。

圖7 平均跳數減少率隨網內存儲容量變化曲線

5 結論

NDN作為一個新型的網絡體系架構，廣泛存在的網內緩存是其最重要的特征之一。然而，必須合理地利用NDN中有限的網內緩存資源才能充分發揮NDN網絡的性能。因此，本文將NDN中的網內緩存問題抽象為一個多智能體分布式協作的Dec-POMDP模型，并將其建模為一個多目標優化問題。基于緩存性能與網絡通信開銷的權衡，本文僅考慮有限跳數范圍內的網內節點緩存協作并在該模型的基礎上提出了一種近似Q學習的強化學習算法以求解局部最優緩存策略。仿真實驗結果表明，基于Dec-POMDP緩存策略能夠根據用戶請求的動態變化更好地分配緩存資源，從而提高了用戶請求的網內緩存命中率，有效地緩解了服務器壓力。