熊 煉，李朋明,，陳 翔，朱紅梅

(1.重慶郵電大學 通信工程應用研究所，重慶 400065； 2.移動通信技術重慶市重點實驗室(重慶郵電大學)，重慶 400065)(*通信作者電子郵箱2205603330@qq.com)

0 引言

在網絡規(guī)模高速增長和多樣化應用需求不斷涌現的今天，網絡角色定位已經發(fā)生了巨大變化。Cisco全球云指數報告[1]預測，2021年全球IP流量將達到20.6 ZB，其中內容類流量占80%以上。這不但帶給網絡帶寬巨大壓力，也表明用戶主要需求已變?yōu)閷Ａ績热莸墨@取，以“主機到主機”通信為核心的傳統(tǒng)架構難以滿足未來網絡發(fā)展需求。為此，研究者們提出以內容為中心的網絡架構——內容中心網絡(Content-Centric Network, CCN)[2]。CCN架構核心特征之一是網絡內建存儲，即通過有存儲功能的節(jié)點將緩存的內容資源高效地共享給更多潛在用戶，減少相似數據在網絡中的大量重復傳輸，緩解網絡帶寬壓力。

網絡設備的線速轉發(fā)要求制約著節(jié)點緩存容量大小，面對網絡中持續(xù)產生的海量內容，在相對有限的存儲空間下，研究緩存策略、提高緩存系統(tǒng)性能是CCN研究的熱點之一。

現有研究為提升緩存系統(tǒng)性能，均從“內容”與“節(jié)點”兩個角度出發(fā)來設計緩存策略。“內容”即緩存的內容，用控制內容冗余[2-5]增加緩存內容多樣性，以及考慮內容重要度[6-7]，在有限的空間里緩存更需要的內容。“節(jié)點”即緩存節(jié)點的選擇，僅部分重要節(jié)點緩存便能起到較好效果[8]。節(jié)點重要性有拓撲和需求上的重要性，用拓撲上邊緣節(jié)點緩存[9-10]，可以降低用戶獲取時延；用中心節(jié)點緩存[11-13]，可以提高內容分發(fā)效率。需求上的重要性即實際需求中某節(jié)點的重要度，如考慮以節(jié)點處的緩存能耗與收益為節(jié)點重要度指標[14]。現有研究考慮內容重要性時忽略了用戶對不同內容的偏好，更沒有充分結合不同位置節(jié)點緩存的獨有優(yōu)勢。

為進一步提高緩存內容“質量”，實現內容最佳放置，本文提出一種基于用戶偏好的協作緩存策略(Cooperative Caching strategy based on User Preference，CCUP)，結合用戶對內容類型的喜好與內容流行度選擇性緩存本地偏好內容，通過節(jié)點間協作將本地偏好內容與其中全局活躍的內容緩存在最佳位置，達到最佳用戶體驗、緩存系統(tǒng)性能。

1 相關工作

LCE(Leave Copy Everywhere)[2]是CCN默認緩存機制，要求網絡節(jié)點緩存所有經過的內容，處處緩存使網絡中存在大量冗余副本，緩存空間填滿后的頻繁替換也會增加緩存處理開銷。針對內容冗余問題，LCD(Leave Copy Down)[3]策略僅在命中節(jié)點的下一跳復制緩存，在控制冗余的同時將內容逐步推向網絡邊緣。而用戶在邊緣節(jié)點就近獲取內容的同時，上游節(jié)點不可避免地會存在冗余副本，隨著時間增長冗余會持續(xù)增加，未能實現最佳冗余控制。

文獻[4]提出ProbCache緩存策略，途徑節(jié)點以加權概率緩存內容，越靠近邊緣緩存概率越大，以概率緩存控制冗余，并利用邊緣存儲優(yōu)勢。文獻[5]提出基于相關概率的協作緩存策略，通過節(jié)點間協作以本地緩存狀態(tài)影響下一跳節(jié)點緩存概率大小，以削弱概率緩存的盲目性，進一步控制冗余。

文獻[6]提出基于內容流行度的概率緩存策略，以內容請求頻率和潛在熱度為流行度指標，增大流行內容緩存概率，以提高緩存內容“質量”。結合內容緩存位置，文獻[7]將高“質量”內容緩存在中心重要節(jié)點，提出基于流行度和生存時間的緩存方案，以流行度決定內容是否向請求經過路徑的中間節(jié)點緩存，以及內容的生存時間。

文獻[8]驗證了內容緩存節(jié)點的重要性，并提出Betw(cache “l(fā)ess for more”)緩存策略，僅高介數節(jié)點緩存內容，利用了中心節(jié)點存儲便于內容快速分發(fā)的特點。而文獻[9]則考慮僅邊緣節(jié)點緩存內容，便于用戶就近快速獲取內容。文獻[10]提出基于邊緣優(yōu)先的緩存協作策略,利用邊緣存儲優(yōu)勢，結合緩存處理開銷的優(yōu)化;在興趣包轉發(fā)階段邊緣節(jié)點優(yōu)先進行緩存決策，方便用戶就近獲取內容，并減小后續(xù)節(jié)點不必要的緩存決策開銷。文獻[8-10]均證明了選擇緩存節(jié)點的重要性。

為進一步選擇緩存節(jié)點，文獻[11]考慮通過選擇緩存位置減少請求跳數，提出了基于介數的最佳緩存位置選擇方法，有效減少了請求所需時間；文獻[12]考慮提高內容分發(fā)效率，提出一種基于內容流行度和節(jié)點級別匹配的概率緩存策略，讓內容按流行度有序地緩存在中心重要節(jié)點；文獻[13]則提出一種基于節(jié)點中心性度量的緩存機制，由軟件定義網絡(Software Defined Network, SDN)控制器根據節(jié)點中心性度量指標，選擇中心度高的節(jié)點并向其下發(fā)緩存指令，但增加了算法復雜度和對拓撲變化的敏感性。

現有方案均在考慮如何進一步提高緩存內容的“質量”或發(fā)揮重要節(jié)點的緩存優(yōu)勢，卻沒有利用不同位置節(jié)點的緩存優(yōu)勢，也忽略了用戶對不同類型內容的偏好因素，未能充分發(fā)揮緩存系統(tǒng)性能。

2 CCUP策略

2.1 CCUP基本原理

CCUP考慮用戶偏好進一步提高緩存內容“質量”，對于需要緩存的本地偏好內容，通過節(jié)點協作優(yōu)先將其中全局活躍內容放置在中心重要節(jié)點；普通本地偏好內容則根據偏好度級別、與節(jié)點距離用戶跳數的多少匹配緩存，偏好度越高存儲距離用戶越近。如圖1所示，若A域用戶對C1、C2、C3三種類型內容喜好C1>C2>C3，流行度相等的內容h、q、s分別屬于以上三類內容，本地偏好度h>q>s，則本地偏好度高的內容h潛在需求更大，緩存優(yōu)先級應該滿足：h>q>s。

圖1 分析示例拓撲Fig. 1 Example topology for analysis

對于本地偏好度高的內容h，若非全局活躍則偏好度越高緩存位置應該距A區(qū)越近，便于用戶獲??；若內容全局活躍度高，則緩存在中心節(jié)點V5更有利于內容分發(fā)。對全局活躍內容的放置以傳統(tǒng)方案用節(jié)點拓撲的介數、緊密度等為指標，難以將內容準確地放置在最佳節(jié)點V5，因此本文以節(jié)點處內容實際需求為重要中心節(jié)點的選擇指標。

本地偏好度指標內容喜好度和流行度定義如下。

定義1 內容喜好度。接入節(jié)點統(tǒng)計的用戶對此類內容的需求占比(用戶接入的第一跳節(jié)點為接入節(jié)點，接入節(jié)點對用戶需求最敏感)，表示用戶對不同類型內容的需求程度。CM類內容的用戶喜好度PM為：

PM=count_M/count_All

(1)

其中:count_M為此類內容請求數;count_All為請求總數。

定義2 內容流行度。一個統(tǒng)計周期T內，節(jié)點j中i內容的流行度表示節(jié)點j處收到對i內容請求的頻率，計算式為：

Lij=count_Ti/count_Tall

(2)

其中:count_Ti為取樣時段內i內容的請求次數;count_Tall為統(tǒng)計時段本地收到請求數。但僅考慮一個周期，會將前段時間流行此時已不流行內容，誤判為流行內容，不能充分利用各時段內容表現出的流行趨勢。所以選擇內容流行度CLij如式(3)：

(3)

其中，η1+η2+η3=1，即綜合考慮三個周期，仿真中周期權重η1、η2和η3值為0.6、0.3、0.1。內容偏好度Hi為：

Hi=PM·CLij

(4)

考慮本地偏好度高的重要內容中的全局活躍內容的快速分發(fā)，進一步提高緩存系統(tǒng)性能，本文將全局活躍內容緩存在中心重要節(jié)點。內容活躍度定義如下。

定義3 內容活躍度。中心節(jié)點統(tǒng)計的網絡中內容i的活躍程度(網絡中心節(jié)點服務的用戶更多，對內容活躍度更敏感)。j節(jié)點處i內容的活躍度ADij計算式為：

(5)

其中，DV為內容請求經過節(jié)點集合。將更多用戶需要的全局活躍內容緩存在重要的中心節(jié)點,更利于內容的分發(fā)。

2.2 CCUP策略實現

CCUP策略的實現需要在原興趣包、數據包結構基礎上擴展，擴展字段如圖2灰色部分。擴展的興趣包中:Interest Total Hops字段值ITH為請求所經過跳數；Local Importance Level字段值LIL為內容偏好級別；Activity Degree字段值AD為內容全局活躍度；Activity Hop字段用于記錄高需求節(jié)點的跳數。數據包中:Data Total Hops字段值DTH為數據包歷經跳數;Execution Cache Hops字段值ECH為執(zhí)行緩存跳數。

圖2 包結構擴展Fig. 2 Extension of packet structure

假設請求者到緩存內容i的節(jié)點Vn有n跳，路徑上各節(jié)點均未緩存內容i，此時請求者發(fā)出對i的請求。在興趣包轉發(fā)過程中，請求首先到達接入節(jié)點V1，V1查詢表1，計算內容偏好度Hi與內容級別Wi。Wi計算式如下：

Wi=Ri/U

(6)

其中:Ri為重要度排名;U為內容總數。Wi若小于ΔW(0<ΔW<1)，將Wi寫入興趣包Local Importance Level字段；否則，不修改LIL值(初始值為空)。然后，Interest Total Hops字段值ITHi加1后轉發(fā)(初始值為0)，即每個轉發(fā)節(jié)點累加，以記錄請求經過的節(jié)點數。

表1 內容信息統(tǒng)計表Tab. 1 StatisticalTable of content information

內容命中前沿途節(jié)點j判斷ITHi值不為0，則匹配LIL值確認是否為本地偏好度高的重要內容。字段值非空，則計算ADij,若大于興趣包Activity Degree字段ADi值,則修改ADi=ADij，并將ITHi值賦予興趣包Activity Hop字段值AHi;否則不對興趣包作任何修改，最后將ITHi值加1后轉發(fā)。

若節(jié)點Vn的CS(Content Store)中存在請求的內容，節(jié)點將數據包歷經跳數值DTHi與緩存執(zhí)行跳數值ECHi寫入數據包Data Total Hops字段和Execution Cache Hops字段，然后返回數據包。其中DTHi=ITHi-1，求取ECHi時首先節(jié)點計算內容全局活躍度歸一化值NADi：

NADi=(ADi-ADmin)/(ADmax-ADmin)

(7)

其中，ADmin和ADmax分別為表1中可查的最大與最小活躍度值。然后,分兩種情況求取ECHi：

1)若NADi≥ΔAD，則認為內容i為全局活躍內容，則將內容i緩存在其活躍度最高的節(jié)點，即將興趣包中AHi值賦予ECHi。

2)若NADi<ΔAD，即內容為非活躍內容，則讀取LIL字段值與ITHi，計算層級匹配值CHi，CHi=Round(Wi·ITHi)，即內容偏好級別與經過跳數的積向近取整，然后將CHi值賦予ECHi。

以上為興趣包轉發(fā)和緩存決策的過程，在數據包返回階段，沿途節(jié)點只需簡單地識別DTHi值是否等于ITHi值，兩值相等則執(zhí)行緩存操作，兩值不相等則不執(zhí)行緩存操作。然后，將DTHi值減1后轉發(fā)下一跳。直到數據返回給用戶，完成整個請求過程。結合上面介紹，CCUP策略偽碼如下。

算法1 興趣包轉發(fā)處理過程。

1)

收到興趣包

2)

if (CS命中)

3)

執(zhí)行算法2

4)

else 讀取ITHi

5)

if (THi=0)

6)

計算Wi

//式(6)

7)

if (Wi≤ΔW)

8)

Wi值寫入LIL字段

9)

else 執(zhí)行步驟18)

10)

else 查看LIL值

11)

if (LIL=Null)

12)

執(zhí)行步驟18)

13)

else 計算ADij

//式(5)

15)

if (ADij>ADi)

16)

修改AD、AH值

17)

else

18)

ITHi++

19)

轉發(fā)下一節(jié)點

算法2 緩存決策過程。

1)

讀取興趣包中ADi、AHi、ITHi

2)

計算NADi

3)

if (NADi≥ΔAD)

4)

ECHi=AHi

5)

執(zhí)行步驟8)

6)

else

7)

ECHi=CHi

8)

DTHi=ITHi-1

9)

返回數據包

算法3 數據包處理過程。

1)

收到數據包

2)

讀取DTHi和ITHi

3)

if (DTHi=ECHi)

4)

if (CS is full)

5)

執(zhí)行近期最少使用(Least Recently Used, LRU)替換策

略并緩存

6)

else

7)

緩存數據

8)

else

9)

DTHi=DTHi-1

10)

轉發(fā)數據包

算法1中,步驟6)與步驟7)結合用戶喜好完成了對緩存內容的篩選，實現選擇性緩存高“質量”內容的目的;步驟11)選擇需要中心節(jié)點計算內容活躍度的請求，由步驟15)判斷并記錄下重要中心節(jié)點的跳數。既釋放了路徑中節(jié)點跟蹤每個內容活躍度的計算壓力，還可以由每個區(qū)域內容偏好度的變化及時發(fā)現潛在全局活躍內容。對需要緩存的內容，由算法2進行的差異化緩存決策，確定執(zhí)行緩存操作的跳數。算法2中：步驟4)是將跟蹤發(fā)現的全局活躍內容緩存在重要中心節(jié)點，快速高效地分發(fā)給更多潛在需求用戶；步驟7)是將非全局活躍度內容按偏好等級與節(jié)點距離用戶跳數層級匹配緩存，便于用戶快速就近獲取區(qū)域偏好內容。數據包返回時節(jié)點處理過程見算法3，僅當前數據包歷經跳數DTHi與緩存執(zhí)行跳數ECHi匹配時才執(zhí)行緩存操作(算法3中步驟3))，否則直接轉發(fā)數據包。通過上述機制，CCUP在控制冗余并提高緩存資源“質量”的同時，滿足了用戶對區(qū)域偏好內容的就近獲取、更多區(qū)域用戶偏好活躍內容的快速分發(fā)。

3 仿真實驗及結果分析

3.1 實驗設置

表2 仿真參數Tab. 2 Simulation parameters

3.2 性能評價指標

仿真對比LCE[2]、Prob(0.6)(Probabilistic caching with 0.6)[4]和Betw[8]策略，均采用LRU緩存替換策略,分別在CS容量、Zipf分布參數α和請求頻率的變化下，從以下2個指標定量地比較和分析。

1)平均緩存命中率(Average Cache Hit, ACH):即網內緩存命中數interest_hit與用戶請求總數的比值。

(8)

2)平均請求時延(Average Request Delay, ARD)：即用戶請求時延delay的總和與請求總次數interest_all的比值。

(9)

其中:V為路由節(jié)點的集合;N為用戶請求集合。平均緩存命中率越高，服務器負載越小。平均請求時延越小，用戶請求需要的時間越短，體驗感越好。

3.3 結果分析

3.3.1 節(jié)點緩存容量對性能的影響

本節(jié)研究分析不同節(jié)點緩存容量下四種緩存機制在緩存命中率和平均請求時延上的性能表現,結果如圖3所示。從圖3可以看出，隨著節(jié)點緩存容量的增加，四種緩存機制的緩存命中率逐漸增大，平均請求時延均逐漸減小。這是因為隨著緩存容量的增加，系統(tǒng)能夠緩存更多的內容來滿足用戶需求，間接地增加了緩存內容的多樣性。但不同策略對冗余控制的差異性使得CS增加量對系統(tǒng)性能的提升效果各不相同，當每節(jié)點均增加10 slot時，LCE、Prob(0.6)、Betw和CCUP四種策略的命中率分別能提高0.014、0.033、0.027、0.035個百分點。該結果進一步驗證了提高控制緩存冗余和緩存內容“質量”以增加緩存內容多樣性對提升系統(tǒng)性能的必要性。從圖3對比可以看出，CCUP在兩個評價指標上均優(yōu)于其他緩存策略，具有較高的緩存性能與較好的用戶體驗。

3.3.2 Zipf分布參數對性能的影響

本節(jié)研究不同Zipf分布參數α對緩存系統(tǒng)性能的影響，比較隨著Zipf參數α的變化四種緩存策略的性能表現，結果如圖4所示。從圖4可知，隨著α增大，四種緩存機制在平均緩存命中率、平均請求時延這兩個指標上的性能都越來越好。這是由于隨著Zipf分布參數變大，請求越來越趨于集中，網內緩存資源利用率越來越高，請求時延也隨之降低，但因網內冗余的客觀存在與節(jié)點緩存容量的限制，使得整體性能增長率先大后小。如Betw策略僅高介數節(jié)點緩存，無法充分利用存儲空間資源，隨著請求趨于集中性能反而會降低。由圖4分析可知，在這兩個指標上CCUP均優(yōu)于另三種策略，即相同Zipf分布參數下，CCUP具有更高的緩存資源利用率和更低的請求時延。

圖3 緩存容量對性能的影響Fig. 3 Impact of caching capacity on performance

圖4 Zipf分布參數對性能的影響Fig. 4 Impact of Zipf distribution parameter on performance

3.3.3 請求速率對性能的影響

本節(jié)研究分析不同請求速率下四種緩存機制在緩存命中率和平均請求時延上的性能表現,結果如圖5所示。從圖5(a)可以看出，隨著用戶請求速率的增加，四種緩存機制的緩存命中率的整體趨勢均有小幅度提升。雖然用戶請求速率增大時，單位時間內注入網絡的分組數量增加，會小幅度提高緩存資源的利用率；但分組數的增多使得分組在排隊系統(tǒng)中的排隊時延增加，總體上如圖5(b)所示，平均請求時延并沒有太明顯的改變。由圖5可以看出，相比于另三種緩存策略，CCUP仍具有較高的緩存性能。

圖5 請求速率對性能的影響Fig. 5 Impact of request rate on performance

4 結語

為進一步提高緩存系統(tǒng)性能，提升用戶體驗，本文提出一種基于用戶偏好的協作緩存策略(CCUP)。該策略考慮用戶偏好與內容流行度進一步提高緩存內容“質量”，發(fā)揮不同位置節(jié)點的獨特緩存優(yōu)勢，選擇最佳內容放置在最優(yōu)位置。實驗結果表明，CCUP在平均緩存命中率、平均請求時延方面較現有策略有顯著優(yōu)勢。但由于內容流行度的被動統(tǒng)計存在一定滯后性，制約著緩存內容質量的進一步提高，下一步將考慮結合流行度的預測進行研究。