姚進發(fā)

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

0 引言

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

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

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

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

1 NDN工作原理

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

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

圖1 NDN中請求包轉發(fā)過程

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

圖2 NDN中數(shù)據(jù)包轉發(fā)過程

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

考慮一個離散時間的Dec-POMDP動態(tài)系統(tǒng)。在每一個決策時刻，每個智能體首先從系統(tǒng)中獲取在當前狀態(tài)下各自的觀測信息，然后做出決策并執(zhí)行動作，系統(tǒng)根據(jù)狀態(tài)轉移函數(shù)轉移到下一個狀態(tài)，并獲得一個即時回報，整個過程周而復始。因此，一個Dec-POMDP模型通?？梢杂梢粋€7元組定義[8]：

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

2.1 網(wǎng)絡模型及相關假設

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

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

圖3 NDN網(wǎng)絡模型

2.2 狀態(tài)和狀態(tài)空間

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

2.3 決策時刻

2.4 行動和行動空間

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

2.5 觀測空間

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

2.6 效用函數(shù)

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

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

2.7 狀態(tài)轉移函數(shù)

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

2.8 觀測概率

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

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

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

定義節(jié)點n的鄰居節(jié)點集合為Nn，根據(jù)文獻[14]，假設網(wǎng)絡狀態(tài)滿足狀態(tài)轉移獨立性，則可以得到近似局部聯(lián)合觀測概率為：

4 數(shù)值仿真

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

(1）平均緩存命中率：定義為由網(wǎng)內(nèi)路由節(jié)點服務的請求數(shù)與總的用戶請求數(shù)之比，即：

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

(2）平均跳數(shù)減少率：反映由于緩存系統(tǒng)的加入使用戶請求內(nèi)容跳數(shù)減少的比率，定義為：

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

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

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

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

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

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

圖6 平均緩存命中率隨網(wǎng)內(nèi)存儲容量變化曲線

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

圖7 平均跳數(shù)減少率隨網(wǎng)內(nèi)存儲容量變化曲線

5 結論

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