馮博昊，周華春，張宏科，張明川,2

?

智慧協(xié)同網(wǎng)絡(luò)服務(wù)內(nèi)容在傳輸路徑上的緩存分配策略

馮博昊1，周華春1，張宏科1，張明川1,2

(1.北京交通大學(xué)電子信息工程學(xué)院，北京100044；2.河南科技大學(xué)信息工程學(xué)院，河南洛陽471023)

針對智慧協(xié)同網(wǎng)絡(luò)提出一種服務(wù)內(nèi)容在傳輸路徑上的緩存分配策略。該策略根據(jù)服務(wù)內(nèi)容的流行度部署其在傳輸路徑上的緩存位置，以求充分、高效地發(fā)揮網(wǎng)絡(luò)緩存作用，進(jìn)而提升網(wǎng)絡(luò)的總體性能。所提分配策略分別在5層樹型拓?fù)浜陀?79個節(jié)點組成的真實網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行了性能測試。結(jié)果顯示，該策略在所測的性能參數(shù)中表現(xiàn)出色，就平均服務(wù)獲取距離而言，較命名數(shù)據(jù)網(wǎng)絡(luò)（NDN, named data nerworking）所使用的LCE（leave copy everywhere）策略，其性能提高20%以上。

緩存分配策略；智慧協(xié)同網(wǎng)絡(luò)；智慧標(biāo)識網(wǎng)絡(luò)；以信息為中心網(wǎng)絡(luò)；未來網(wǎng)絡(luò)體系架構(gòu)

1 引言

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展和不斷創(chuàng)新，互聯(lián)網(wǎng)早已成為現(xiàn)代人們工作和生活必不可少的工具之一。然而，隨著互聯(lián)網(wǎng)用戶不斷激增、互聯(lián)網(wǎng)業(yè)務(wù)爆炸式增長等，現(xiàn)有互聯(lián)網(wǎng)的原始設(shè)計理念早已無法滿足當(dāng)今人們對網(wǎng)絡(luò)的多元化要求，諸多難以解決的問題暴露出來。因此，如何設(shè)計能夠滿足未來發(fā)展需求的下一代互聯(lián)網(wǎng)體系與機(jī)制已成為當(dāng)今學(xué)術(shù)領(lǐng)域研究的熱點問題之一。

造成現(xiàn)有互聯(lián)網(wǎng)諸多嚴(yán)重弊端的本質(zhì)原因在于其“三重綁定”特性，即“身份與位置綁定”、“資源與位置綁定”以及“控制與轉(zhuǎn)發(fā)綁定”[1]。智慧協(xié)同網(wǎng)絡(luò)（也稱智慧標(biāo)識網(wǎng)絡(luò)）的提出旨在同時解決上述“三重綁定”的問題，實現(xiàn)能夠滿足未來需求的下一代互聯(lián)網(wǎng)體系結(jié)構(gòu)。本文的工作集中于智慧協(xié)同網(wǎng)絡(luò)的“資源與位置分離”機(jī)制上[2]。

現(xiàn)有互聯(lián)網(wǎng)中，服務(wù)資源的名稱與其所處的網(wǎng)絡(luò)位置耦合，并且數(shù)據(jù)采用通道傳輸，中間節(jié)點無法獲悉所傳數(shù)據(jù)的實際內(nèi)容，不利于數(shù)據(jù)的高效分發(fā)。

為實現(xiàn)“資源與位置的分離”，智慧協(xié)同網(wǎng)絡(luò)以獨立于位置標(biāo)識的服務(wù)標(biāo)識(SID, service identifier)對服務(wù)內(nèi)容進(jìn)行命名，并且在路由器中引入了緩存功能。這樣，服務(wù)資源可存儲在網(wǎng)絡(luò)中的任意位置，用戶不必非要到遙遠(yuǎn)的服務(wù)器獲取服務(wù)內(nèi)容。服務(wù)內(nèi)容的獨立命名以及緩存的使用一方面有利于用戶的就近獲取服務(wù)資源，另一方面，網(wǎng)絡(luò)中的重復(fù)流量也大幅降低，網(wǎng)絡(luò)整體性能得到提升。該思路也與當(dāng)今以信息為中心網(wǎng)絡(luò)(ICN, information centric network)的概念不謀而合。學(xué)術(shù)界圍繞ICN概念啟動了大量的研究項目，例如NDN項目[3]、PURSUIT項目[4]和NetInF項目[5]等。雖然這些項目在ICN的實施細(xì)節(jié)上存在差異，但其核心思想，即在對服務(wù)直接命名、利用路由器緩存服務(wù)內(nèi)容上保持一致。

本文提出一種服務(wù)內(nèi)容在傳輸路徑上的緩存分配策略(CA, cache allocation policy)。其基本思想是：在網(wǎng)絡(luò)中引入服務(wù)內(nèi)容流行度感知節(jié)點，它通過周期性地收集用戶請求來對服務(wù)內(nèi)容進(jìn)行流行度的排序，之后，將感知結(jié)果通告給用戶所處的接入路由器。接入路由器隨后根據(jù)被請求內(nèi)容的流行度排序指定該服務(wù)內(nèi)容在傳輸路徑中被緩存的位置，以求合理利用傳輸路徑上的緩存資源，充分、高效地發(fā)揮網(wǎng)絡(luò)緩存的作用，提升網(wǎng)絡(luò)的總體性能。

2 相關(guān)工作

毫無疑問，緩存對于“資源與位置分離”網(wǎng)絡(luò)架構(gòu)的性能改善是至關(guān)重要的。由于緩存路由器面向網(wǎng)絡(luò)中所有服務(wù)內(nèi)容進(jìn)行存儲，各服務(wù)內(nèi)容特點不一，如何合理規(guī)劃和使用緩存資源、將流行服務(wù)內(nèi)容存儲在離用戶更近的地方一直是諸如網(wǎng)頁緩存、以信息為中心網(wǎng)絡(luò)等緩存網(wǎng)絡(luò)研究的熱點議題。緩存的分配問題可分為2類，第一類問題是如何在網(wǎng)絡(luò)中選擇合適的緩存位置并設(shè)置相應(yīng)的緩存大小以存儲服務(wù)內(nèi)容[6~8]。第二類問題則是在給定網(wǎng)絡(luò)緩存位置的情況下，研究存儲哪些服務(wù)內(nèi)容以求網(wǎng)絡(luò)性能最優(yōu)。本文專注于第二類問題，更準(zhǔn)確地，是如何在傳輸路徑上緩存資源有限的情況下，合理地為服務(wù)內(nèi)容選擇最佳的緩存位置以達(dá)到降低用戶獲取時延、網(wǎng)絡(luò)重復(fù)流量的目標(biāo)。該問題也與緩存準(zhǔn)入策略，即緩存節(jié)點決定哪些服務(wù)內(nèi)容可以進(jìn)入緩存的議題十分相似，本文將一并討論。

LCD(leave copy down)[9]和MCD(move copy down)[9]是網(wǎng)頁緩存下的2種服務(wù)內(nèi)容在傳輸路徑上的準(zhǔn)入策略。LCD和MCD每次只將服務(wù)內(nèi)容緩存在服務(wù)器或命中節(jié)點下游直連的節(jié)點上。LCD與MCD的區(qū)別在于MCD將服務(wù)內(nèi)容下移后，該服務(wù)內(nèi)容會被命中節(jié)點刪除。LCD、MCD根據(jù)需求下移服務(wù)內(nèi)容，服務(wù)內(nèi)容每被請求一次，其緩存位置下移一跳，請求的越多，服務(wù)內(nèi)容下移的距離就越遠(yuǎn)、其離用戶也就更近。這樣，流行內(nèi)容由于擁有更多的請求數(shù)量將被緩存在網(wǎng)絡(luò)的邊緣?？梢?，LCD和MCD可粗略地反映服務(wù)內(nèi)容的流行度。

文獻(xiàn)[9]還與LCE(leave copy everywhere)和Prob()2種策略進(jìn)行比較。LCE也是NDN(named data networking)所使用的緩存準(zhǔn)入策略，它可視為一種極端的策略，即服務(wù)內(nèi)容存儲在傳輸路徑上的所有節(jié)點上。其缺點在于沿途路由器都會存儲重復(fù)的服務(wù)內(nèi)容、造成緩存資源的浪費。此外，被緩存的服務(wù)內(nèi)容極易被新的服務(wù)內(nèi)容所替換，使緩存中的服務(wù)內(nèi)容極不穩(wěn)定。多數(shù)服務(wù)內(nèi)容在被二次請求前就被刪除，緩存無法發(fā)揮出預(yù)期的效果。Prob()則是沿途節(jié)點按照一個固定概率存儲服務(wù)內(nèi)容，同樣也無法體現(xiàn)出內(nèi)容的流行度。

文獻(xiàn)[10]提出一種服務(wù)內(nèi)容在傳輸路徑上的緩存準(zhǔn)入策略Betw。該策略根據(jù)介數(shù)中心性(BC, betweeness centrality)來緩存服務(wù)內(nèi)容。節(jié)點的BC是指該節(jié)點處在拓?fù)渲腥我馄渌麅牲c的最短路徑上的次數(shù)，它反映出該節(jié)點在拓?fù)渲械闹匾潭?。Betw的優(yōu)勢在于服務(wù)內(nèi)容被存儲在拓?fù)渲凶钪匾墓?jié)點上，利于共享。但BC是拓?fù)涮匦裕c內(nèi)容的流行度沒有關(guān)系，無法反映出內(nèi)容的流行度。此外，高BC節(jié)點的緩存替換速率將極高，造成被緩存內(nèi)容的不穩(wěn)定。

ProbCache、ProbCache+[11, 12]根據(jù)傳輸路徑上剩余緩存容量、離用戶的距離計算出緩存概率，它需要在請求報文和服務(wù)內(nèi)容報文中分別攜帶距離用戶和服務(wù)器的跳數(shù)信息。該策略可有效地減少進(jìn)入緩存的服務(wù)內(nèi)容的數(shù)量，但服務(wù)內(nèi)容的流行度這一重要因素沒有被直接考慮進(jìn)來。

文獻(xiàn)[13, 14]利用散列函數(shù)和求余的方式對服務(wù)內(nèi)容的命名空間進(jìn)行劃分。其優(yōu)點在于不同的內(nèi)容被指定到不同位置，保證了服務(wù)內(nèi)容的穩(wěn)定性。其缺點在于，服務(wù)標(biāo)識本身無法體現(xiàn)出流行度，如果不添加較為復(fù)雜的流量平衡算法，緩存節(jié)點易出現(xiàn)負(fù)載失衡問題。

此外，利用最優(yōu)化或線性規(guī)劃等算法是解決緩存分配問題的常見方式，文獻(xiàn)[15, 16]通過計算緩存服務(wù)內(nèi)容的收益來決定是否存儲在節(jié)點中。但由于其計算粒度為一次請求，復(fù)雜度極高，只能作為最優(yōu)結(jié)果進(jìn)行參考而不適宜被實際系統(tǒng)進(jìn)行實時測算。

3 服務(wù)內(nèi)容在傳輸路徑上的緩存分配策略

本節(jié)首先介紹智慧協(xié)同網(wǎng)絡(luò)用于實現(xiàn)“資源與位置分離”機(jī)制的基本模型；其次，在分析現(xiàn)有服務(wù)請求模型的基礎(chǔ)上，給出本文所提緩存分配策略的設(shè)計原則；最后，詳細(xì)說明所提緩存分配策略的具體機(jī)制。

3.1 智慧協(xié)同網(wǎng)絡(luò)的基本模型

圖1給出了智慧協(xié)同網(wǎng)絡(luò)用于實現(xiàn)“資源與位置分離”機(jī)制的基本模型。智慧協(xié)同網(wǎng)絡(luò)選擇解析的方法進(jìn)行服務(wù)內(nèi)容與位置的映射，映射關(guān)系被保存在服務(wù)標(biāo)識查詢系統(tǒng)中。當(dāng)用戶發(fā)送請求報文至接入路由器后，接入路由器代替用戶向服務(wù)標(biāo)識查詢系統(tǒng)詢問SID所對應(yīng)的位置信息。服務(wù)標(biāo)識查詢系統(tǒng)查詢后返回相應(yīng)的位置信息。接入路由器收到后，在請求報文中填寫SID所對應(yīng)的目的位置信息并根據(jù)路由表轉(zhuǎn)發(fā)請求報文。沿途路由器收到請求報文后，查詢SID所對應(yīng)的服務(wù)內(nèi)容是否被緩存在本地，是則直接返回服務(wù)內(nèi)容；否則繼續(xù)根據(jù)路由表轉(zhuǎn)發(fā)。當(dāng)請求報文到達(dá)服務(wù)器后，服務(wù)器根據(jù)請求報文的目的位置信息返回服務(wù)內(nèi)容，傳輸路徑上的路由器按需進(jìn)行存儲。

3.2 服務(wù)請求模型分析

互聯(lián)網(wǎng)是面向用戶需求的網(wǎng)絡(luò)，用戶的服務(wù)請求模型對網(wǎng)絡(luò)性能優(yōu)化起到?jīng)Q定性的作用。大量文獻(xiàn)使用Zipf分布作為服務(wù)請求的模型，即服務(wù)內(nèi)容的流行度排序與請求概率呈反比。文獻(xiàn)[17]給出了常見網(wǎng)絡(luò)服務(wù)的的變化范圍。

Zipf分布的數(shù)學(xué)表達(dá)式如式(1)所示，其中，(,,)代表排序為的服務(wù)內(nèi)容的請求概率，代表內(nèi)容總體個數(shù)，為函數(shù)的調(diào)節(jié)參數(shù)。

圖2 Zipf分布的累計概率

此外，由于路由器的容量要遠(yuǎn)小于服務(wù)內(nèi)容的總量，過多的服務(wù)內(nèi)容進(jìn)入緩存勢必會引起較高的緩存替換速率，導(dǎo)致緩存的服務(wù)內(nèi)容不穩(wěn)定。鑒于每條傳輸路徑的緩存資源有限且存在其他交叉路徑競爭緩存資源的現(xiàn)象，假設(shè)用戶到服務(wù)器的傳輸路徑由該用戶獨享，且能容納個服務(wù)內(nèi)容，那么排序在后的服務(wù)內(nèi)容都不應(yīng)該進(jìn)入緩存，以免增加路由器的緩存替代速率，從而降低緩存性能。

因此，服務(wù)內(nèi)容應(yīng)按照請求排序依次存儲在從用戶到服務(wù)器的傳輸路徑上、并且非傳輸路徑所能容納的服務(wù)內(nèi)容不能進(jìn)入緩存。這也是本文所提出的緩存分配策略的設(shè)計原則。

3.3 具體機(jī)制

3.3.1 服務(wù)內(nèi)容流行度的感知

為實現(xiàn)服務(wù)內(nèi)容流行度的測算，CA中引入了“服務(wù)內(nèi)容流行度感知節(jié)點”。如圖1所示，它部署在網(wǎng)絡(luò)邊緣、靠近用戶接入路由器的位置，負(fù)責(zé)某一區(qū)域服務(wù)內(nèi)容流行度的測算。服務(wù)內(nèi)容流行度感知節(jié)點統(tǒng)一通告一個任播地址，接入路由器將信令報文發(fā)往該任播地址，便可與最近的服務(wù)內(nèi)容流行度感知節(jié)點進(jìn)行交互。為了感知服務(wù)內(nèi)容的流行度，接入路由器每收到一次服務(wù)請求，都將該請求中的SID提取出來發(fā)往服務(wù)內(nèi)容流行度感知節(jié)點，便于后者對服務(wù)內(nèi)容的流行度進(jìn)行評估。網(wǎng)絡(luò)初始時，接入路由器還需將自己的位置信息注冊到服務(wù)內(nèi)容流行度感知節(jié)點，以便后者主動推送關(guān)于服務(wù)內(nèi)容流行度排序的信令報文。此外，接入路由器還需向服務(wù)內(nèi)容流行度感知節(jié)點通告其所有傳輸路徑中最大的路徑緩存容量，即傳輸路徑上所有緩存節(jié)點緩存容量之和，以便后者決定向其推送排序列表的長度。

服務(wù)內(nèi)容流行度感知節(jié)點周期性的測算服務(wù)內(nèi)容的流行度，假設(shè)感知周期為。服務(wù)內(nèi)容的流行度通過其請求數(shù)量來體現(xiàn)。服務(wù)內(nèi)容流行度感知節(jié)點為每個被請求的服務(wù)內(nèi)容維護(hù)如表1所示的流行度表項。該表項由3部分組成，“服務(wù)標(biāo)識”用于標(biāo)識一個服務(wù)內(nèi)容，“本周期請求數(shù)”記錄在當(dāng)前周期內(nèi)該服務(wù)內(nèi)容的請求數(shù)量，“流行度”則為上一周期測算的服務(wù)內(nèi)容流行度的值。當(dāng)前周期結(jié)束后，服務(wù)內(nèi)容流行度感知節(jié)點重新計算服務(wù)內(nèi)容的流行度。

表1 服務(wù)內(nèi)容流行度感知節(jié)點維護(hù)的流行度

服務(wù)內(nèi)容流行度感知節(jié)點使用指數(shù)加權(quán)移動平均值(EWMA, exponentially weighted moving average)[18]的方式計算流行內(nèi)容的流行度。EWMA的表達(dá)式如式(2)所示。的初始值為服務(wù)內(nèi)容第一個周期的請求數(shù)量。是過去測量值的權(quán)重系數(shù)，越小，過去測量值所占比重越大。

服務(wù)內(nèi)容流行度感知節(jié)點根據(jù)新計算出來的流行度對服務(wù)內(nèi)容進(jìn)行排序并將該結(jié)果推送給向其注冊的接入路由器。同時，計算出來的流行度將覆蓋流行度表項中原有的流行度。

接入路由器收到服務(wù)內(nèi)容流行度感知節(jié)點推送的包含內(nèi)容流行度排序的信令報文后，創(chuàng)建或更新其維護(hù)的排序表項，如表2所示，其只需要記錄SID和流行度排序，并維護(hù)一個計時器?？紤]到信令報文的傳輸時間，計時器的計時長度略長于，超時后，接入路由器刪除相應(yīng)表項。

表2 接入路由器維護(hù)的排序

3.3.2 傳輸路徑上路由器的相關(guān)操作

用戶發(fā)送的請求報文如圖3所示。目的位置信息、源位置信息分別為目的節(jié)點和源節(jié)點的通信地址。SID為用戶請求的服務(wù)標(biāo)識，Rank為該SID的流行度排序，初始值為MAX，MAX為一個很大的整數(shù)，遠(yuǎn)遠(yuǎn)大于路徑緩存容量。CacheCapacity用于記錄傳輸路徑上的緩存容量，以確定服務(wù)內(nèi)容的存儲位置，其初始值為0。Node-ID用于記錄緩存該服務(wù)內(nèi)容的節(jié)點標(biāo)識，初始值為NULL?；貜?fù)的數(shù)據(jù)報文格式報頭與請求報文格式類似，區(qū)別在于前者不含Rank和CacheCapacity域。

目的位置信息 源位置信息 SID RankCacheCapacity Node-ID

圖3 請求報文格式

路由器的處理流程如圖4所示。當(dāng)接入路由器收到請求報文后，首先根據(jù)SID查詢排序表項，如果存在對應(yīng)表項，則在請求報文中填寫對應(yīng)表項中的Rank值。之后，按照普通路由器處理。普通路由器首先將自身的緩存容量與CacheCapacity相加，之后與Rank比較。如果新的CacheCapacity小于Rank，則說明該服務(wù)內(nèi)容應(yīng)該存儲在后續(xù)傳輸節(jié)點上。如果新的CacheCapacity大于或等于Rank，則說明該路由器需要存儲該服務(wù)內(nèi)容。此時，該路由器將自己的ID號寫入請求報文的Node-ID中并將Rank改寫為MAX，這樣，后續(xù)路由器將不會存儲該服務(wù)內(nèi)容。之后，普通路由器將查詢本地緩存列表，如果存有該SID的服務(wù)內(nèi)容，普通路由器復(fù)制請求報文中Node-ID域至返回的數(shù)據(jù)報文頭部對應(yīng)處并返回服務(wù)內(nèi)容。否則，路由器根據(jù)路由表發(fā)送請求報文。當(dāng)服務(wù)內(nèi)容回傳時，沿途路由器查看返回報文中的Node-ID是否為自己的節(jié)點標(biāo)識，若是，則緩存該服務(wù)內(nèi)容，否，則直接轉(zhuǎn)發(fā)。

圖5給出了一個簡單的用戶發(fā)送請求報文至服務(wù)器的例子，以說明路由器對請求報文操作的過程。假設(shè)每臺路由器可以容納5個服務(wù)內(nèi)容，被請求內(nèi)容排序為12，節(jié)點1、2、3均沒有存儲相應(yīng)的服務(wù)內(nèi)容。節(jié)點1為用戶的接入路由器，它首先查詢本地排序列表，發(fā)現(xiàn)SID的排序為12，并將12填寫至請求報文中的Rank域；之后改寫CacheCapacity為5。節(jié)點1將請求發(fā)往下一跳節(jié)點2。節(jié)點2首先改寫CacheCapacity為10，發(fā)現(xiàn)小于Rank域的12，繼續(xù)發(fā)往下一跳。節(jié)點3首先改寫CacheCapacity為15，發(fā)現(xiàn)大于Rank域的12，改寫Node-ID域為3并將Rank域設(shè)為MAX。當(dāng)服務(wù)內(nèi)容回傳時，只有節(jié)點3進(jìn)行存儲。

CA的提出旨在將流行的服務(wù)內(nèi)容存儲在傳輸路徑有限的緩存資源上，并且，越流行的內(nèi)容越靠近用戶。不同于NDN所使用的LCE策略，在CA中，服務(wù)內(nèi)容在請求時已經(jīng)被指定緩存位置，路由器的緩存替代速率大幅降低，非流行服務(wù)內(nèi)容替代流行服務(wù)內(nèi)容的現(xiàn)象也得到有效的解決，緩存內(nèi)容的穩(wěn)定性得以保證，其被共享的幾率也大幅增加。然而，CA付出的代價是每個接入網(wǎng)的服務(wù)內(nèi)容流行度感知節(jié)點需要為每個SID記錄請求數(shù)量。一方面，服務(wù)請求報文轉(zhuǎn)發(fā)到服務(wù)內(nèi)容流行度感知節(jié)點會造成鏈路帶寬的開銷；另一方面，對于服務(wù)內(nèi)容流行度感知節(jié)點需要維護(hù)很長的SID列表。

對于鏈路開銷的問題，由于一個區(qū)域內(nèi)的請求分布大致相同，接入網(wǎng)的服務(wù)內(nèi)容流行度感知節(jié)點可隨機(jī)選取某個或某幾個用戶作為探測服務(wù)內(nèi)容流行度的樣本，這樣可有效降低鏈路的開銷。對于服務(wù)內(nèi)容流行度感知節(jié)點自身處理開銷的問題，本文所提流行度測試方法僅僅是初步方案，由于傳輸路徑上無法存儲所有服務(wù)內(nèi)容，服務(wù)內(nèi)容流行度感知節(jié)點也沒必要存儲所有SID的請求數(shù)量。該問題的實質(zhì)其實與緩存替代策略所解決的問題完全一樣，即在一個有限長度的列表中進(jìn)行表項優(yōu)先級的排序。由于服務(wù)內(nèi)容流行度感知節(jié)點只需要知道服務(wù)內(nèi)容的排序而不是具體請求數(shù)量，可使用基于頻率的替代策略進(jìn)行流行度的排序，如P-LFU(period least frequently used)、LFU-DA(LFU-dynamic aging)[19]等。

4 性能測試與分析

為了驗證所提緩存分配策略CA的性能，本文利用基于NS3[20]的ndnSIM[21]實現(xiàn)了緩存分配策略CA。此外，本文還實現(xiàn)了LCD、MCD、Prob()、ProbCache (PRC)、ProbCache+(PRC+)以及Betw用于性能比較。所有策略均使用(LRU, least recently used)作為緩存替代策略。此外，LCE+LRU也是NDN所使用的默認(rèn)策略，ndnSIM已經(jīng)提供。本文分別在5層的樹型拓?fù)浜?79個節(jié)點的真實網(wǎng)絡(luò)拓?fù)渲袑λ胁呗赃M(jìn)行性能測試。樹型拓?fù)涑Ｓ糜诮尤刖W(wǎng)，但其無法表現(xiàn)出真實網(wǎng)絡(luò)的無標(biāo)度特性。故本文從Rocketfuel’s AT&T topology[22]中選擇編號為1221的真實網(wǎng)絡(luò)拓?fù)洹?種拓?fù)淙鐖D6所示。

(a) 樹型拓?fù)?/p>

(b) 真實拓?fù)?/p>

圖6 真實網(wǎng)絡(luò)拓?fù)?/p>

在5層樹型拓?fù)渲?，一個服務(wù)器接入在樹根處，16個用戶模擬器分別接入到16個葉節(jié)點上，故用戶到服務(wù)器的距離為6跳（用戶到接入路由器、服務(wù)器到第一跳路由器均計為1跳，真實拓?fù)湟惨源朔绞接嬎闾鴶?shù)）。樹型拓?fù)渲泄?jié)點的帶寬設(shè)置的較大，所以擁塞問題不會對最終的結(jié)果造成多大的影響。真實拓?fù)涔灿?31條鏈路，其中，接入節(jié)點有169個，網(wǎng)關(guān)節(jié)點45個，骨干網(wǎng)節(jié)點65個。本文并未改變該拓?fù)涞脑袇?shù)。50個服務(wù)器和100個用戶模擬器將隨機(jī)接入到不同的接入節(jié)點中。2.5104個內(nèi)容將隨機(jī)分布到這100個服務(wù)器中，而每個服務(wù)內(nèi)容只被某一個服務(wù)器提供。另外，在2種拓?fù)渲?，每個網(wǎng)關(guān)節(jié)點（灰色）都連接一個服務(wù)內(nèi)容流行度感知節(jié)點。樹型拓?fù)涞木W(wǎng)關(guān)節(jié)點為第5層節(jié)點。

表3 仿真參數(shù)

測試的性能指標(biāo)包括服務(wù)獲取距離、緩存刪除操作總量以及請求報文數(shù)量。這些指標(biāo)又分為實時指標(biāo)和平均指標(biāo)2類。實時指標(biāo)為每5 s內(nèi)的平均值、平均指標(biāo)為1 000 s內(nèi)的總平均值。

服務(wù)獲取距離定義為請求報文到達(dá)服務(wù)器或存有服務(wù)內(nèi)容副本的節(jié)點所經(jīng)過的跳數(shù)。平均值的計算方式為規(guī)定時間內(nèi)所有請求報文的跳數(shù)之和與總請求數(shù)的商。它反映出緩存的共享率，距離越短，效率越高，用戶的服務(wù)獲取時延就越低；節(jié)點的緩存刪除操作總量定義為網(wǎng)絡(luò)中所有節(jié)點每秒刪除緩存內(nèi)容數(shù)量之和，它反映出緩存內(nèi)容的穩(wěn)定性。請求報文數(shù)量記錄規(guī)定時間內(nèi)網(wǎng)絡(luò)中所有節(jié)點發(fā)送的請求報文的數(shù)量，由于一個請求報文回復(fù)一個數(shù)據(jù)報文，它可以粗略地反映出網(wǎng)絡(luò)中的流量狀況。

需要說明的是，在測算服務(wù)獲取距離時，由于其他策略并未考慮服務(wù)解析的問題，為了公平起見，緩存分配策略CA在計算服務(wù)獲取距離時不包含解析過程所產(chǎn)生的跳數(shù)，即假設(shè)接入路由器已知服務(wù)器的位置信息。另外，緩存分配策略CA的測算周期默認(rèn)為10 s，默認(rèn)為0.85。另外，考慮到測試參數(shù)實時的簡潔性，性能表現(xiàn)中等的MCD、PRC以及Prob(0.3)將不在圖中呈現(xiàn)，其平均值將在對應(yīng)列表中體現(xiàn)。

4.1 緩存分配策略CA自身參數(shù)對其的影響

本文首先測試緩存分配策略CA自身參數(shù)對其的影響。1 000 s內(nèi)的總平均服務(wù)獲取距離隨測算周期以及大小變化的情況如圖7所示?？梢钥吹剑?種拓?fù)湎?，平均服?wù)距離均未發(fā)生明顯變化。因此，測算周期以及并非是影響緩存分配策略CA性能的主要因素。另外，緩存分配策略CA在2種拓?fù)湎缕骄?wù)獲取距離的差異源于2種拓?fù)浞?wù)器數(shù)量、用戶模擬器數(shù)量等設(shè)定以及拓?fù)浔旧硖匦缘牟煌?/p>

4.2 各策略服務(wù)獲取距離的比較

圖8分別給出了在樹型拓?fù)浜驼鎸嵕W(wǎng)絡(luò)拓?fù)湎赂鞑呗缘膶崟r服務(wù)獲取距離。各策略1 000 s內(nèi)的總平均服務(wù)獲取距離以及相對于LCE的減小率如表4所示。可以看出，2種拓?fù)湎滦阅茏詈玫氖荂A，在樹型拓?fù)湎缕骄?wù)獲取距離為3.81跳，在真實拓?fù)湎聻?.13跳，相對于LCE，減小率大于20%。其次是LCD，相對于LCE的減小率為14%左右。

LCE性能較差的原因在于其不限制服務(wù)內(nèi)容進(jìn)入緩存。由于傳輸路徑上的緩存資源有限，其總?cè)萘恳h(yuǎn)遠(yuǎn)小于服務(wù)內(nèi)容的請求數(shù)量。在這種情況下，當(dāng)服務(wù)內(nèi)容回傳時，途徑節(jié)點都會緩存相同的服務(wù)內(nèi)容，造成緩存資源的極度浪費。此外，這種方式加速了緩存內(nèi)容的替代速率，很多服務(wù)內(nèi)容在被二次請求前就被刪除，緩存沒有發(fā)揮出很好的共享作用，致使用戶的服務(wù)獲取距離較高。

Prob(0.3)是一種純基于概率的策略，其性能優(yōu)于LCE的原因在于它并不是讓所有服務(wù)內(nèi)容都進(jìn)入緩存。這樣，傳輸路徑上緩存內(nèi)容的多樣性得到一定的保證，同時，緩存內(nèi)容的替代速率也大幅降低，故其性能較之LCE有所提高。

ProbCache和ProCache+也是一種基于概率的策略，不同之處在于它們還考慮了服務(wù)內(nèi)容回傳時路徑上所剩緩存容量以及離用戶的距離等因素。由于其概率計算更具針對性，其性能較之Prob(0.3)提高較多。

Betw根據(jù)BC緩存服務(wù)內(nèi)容，它利用BC確定服務(wù)內(nèi)容在傳輸路徑上的存儲位置。但Betw的缺陷在于BC是反映網(wǎng)絡(luò)拓?fù)涞奶匦裕男阅芘c拓?fù)渲苯酉嚓P(guān)，而且高BC的節(jié)點緩存替代速率較高，不易實現(xiàn)服務(wù)內(nèi)容的共享。

LCD和MCD則是根據(jù)請求下移數(shù)據(jù)，它可以粗略的反映出服務(wù)內(nèi)容的流行度。對于流行內(nèi)容，由于其擁有較多的請求數(shù)量，其最終會被下移到離用戶更近的地方。另外，MCD性能遜于LCD的原因在于命中節(jié)點會刪除被命中的服務(wù)內(nèi)容，降低了服務(wù)內(nèi)容被共享的概率。

CA表現(xiàn)最為出色，原因在于其按照用戶需求存儲服務(wù)內(nèi)容。如前所述，服務(wù)請求服從Zipf分布，服務(wù)內(nèi)容的請求數(shù)量隨流行度排序的升高呈指數(shù)遞減。而CA按照服務(wù)內(nèi)容流行度排序遞增的方式從用戶方向依次在傳輸路徑上存儲服務(wù)內(nèi)容，這樣，更多的服務(wù)請求能夠被就近滿足。此外，由于傳輸路徑上的緩存資源遠(yuǎn)不足以存儲用戶所請求的所有內(nèi)容，排序靠后的服務(wù)內(nèi)容將不會進(jìn)入緩存，這大幅降低了緩存內(nèi)容的替換速率，保證緩存內(nèi)容的穩(wěn)定性，便于服務(wù)內(nèi)容的共享。

4.3 各策略服務(wù)器緩存刪除操作總量的比較

圖9分別給出了在樹型拓?fù)浜驼鎸嵕W(wǎng)絡(luò)拓?fù)湎赂鞑呗缘膶崟r緩存刪除操作總量。各策略1 000 s內(nèi)的總平均緩存刪除操作總量以及相對于LCE的減小率如表4所示。可以看出，2種拓?fù)湎滦阅茏詈玫氖荂A，在樹型拓?fù)湎戮彺鎰h除操作總量為每秒95.98次，在真實拓?fù)湎聻槊棵?80.44次，相對于LCE，減小率在98%左右。這說明在緩存分配策略CA中，被緩存的服務(wù)內(nèi)容相對穩(wěn)定，利于服務(wù)內(nèi)容的共享。其原因在于緩存分配策略CA指定了服務(wù)內(nèi)容在傳輸路徑的存儲位置并阻止非流行服務(wù)內(nèi)容進(jìn)入緩存，有效降低了緩存內(nèi)容的替代速率。

4.4 各策略請求報文數(shù)量的比較

圖10給出了在樹型拓?fù)浜驼鎸嵕W(wǎng)絡(luò)拓?fù)湎赂鞑呗缘膶崟r請求報文數(shù)量。各策略1 000 s內(nèi)的總平均請求報文數(shù)量以及相對于LCE的減小率如表4所示。

緩存分配策略CA在2種拓?fù)湎卤憩F(xiàn)良好，相對于LCE的減小率分別為20.34%和12.27%。真實拓?fù)湎鄬τ贚CE的減小率低于樹型拓?fù)涞脑蛟谟谡鎸嵕W(wǎng)絡(luò)是無標(biāo)度網(wǎng)絡(luò)并且用戶傳輸路徑相互重疊、相互影響，加之其節(jié)點數(shù)量、用戶模擬器數(shù)量遠(yuǎn)遠(yuǎn)多于樹型拓?fù)洌?wù)請求在網(wǎng)絡(luò)中的傳輸更具一般性。此外，雖然Betw的請求報文數(shù)量也很低，但由于其只考慮了拓?fù)涮匦远皇欠?wù)內(nèi)容的流行度，其用戶的服務(wù)獲取距離并不是最短的。緩存分配策略CA則是根據(jù)服務(wù)內(nèi)容的流行度存儲，故在請求報文數(shù)量降低的同時，用戶的平均服務(wù)獲取距離最小。

綜上所述，緩存分配策略CA性能出色的原因在于其按照服務(wù)內(nèi)容流行度排序遞增的方式從用戶方向依次在傳輸路徑上存儲服務(wù)內(nèi)容。此外，由于傳輸路徑上的緩存資源遠(yuǎn)不足以存儲用戶所請求的所有內(nèi)容，排序靠后的服務(wù)內(nèi)容將不會進(jìn)入緩存，這大幅降低了緩存內(nèi)容的替換速率，保證緩存內(nèi)容的穩(wěn)定性。測試結(jié)果顯示，緩存分配策略CA在服務(wù)獲取距離、緩存刪除操作總量、請求報文數(shù)量3方面性能出色，這也證明了本文設(shè)計緩存分配策略CA的原則是有效的。

表4 各性能指標(biāo)平均值以及相對于LCE的減小率

5 結(jié)束語

本文提出了一種服務(wù)內(nèi)容在傳輸路徑上的緩存分配策略，旨在合理利用傳輸路徑上的緩存資源，充分、高效地發(fā)揮網(wǎng)絡(luò)緩存的作用，進(jìn)而提升網(wǎng)絡(luò)的總體性能。本文分別在5層的樹型拓?fù)浜陀?79個節(jié)點組成的真實網(wǎng)絡(luò)中對緩存分配策略CA進(jìn)行性能測試。同時，本文還實現(xiàn)了LCD、MCD、Betw、ProbCache、ProbCache+、Prob(0.3)的功能并與緩存分配策略CA、NDN所使用的策略LCE進(jìn)行性能對比。結(jié)果顯示，緩存分配策略CA在所測的性能參數(shù)中表現(xiàn)出色，就平均服務(wù)獲取距離而言，較之LCE，其性能提高20%以上。

[1] 張宏科, 羅洪斌. 智慧協(xié)同網(wǎng)絡(luò)體系基礎(chǔ)研究[J]. 電子學(xué)報, 2013, 41(7): 1249-1254.

ZHANG H K, LUO H B. Fundamental research on theories of smart and cooperative networks[J]. Acta Electronic Silica, 2013, 41(7): 1249-1254.

[2] 蘇偉, 陳佳, 周華春, 等. 智慧協(xié)同網(wǎng)絡(luò)中的服務(wù)機(jī)理研究[J]. 電子學(xué)報, 2013, 41(7): 1255-1260.

SU W, CHEN J, ZHOU H C, et al. Research on the service mechanisms in smart and cooperative networks[J]. Acta Electronic Silica, 2013, 41(7): 1255-1260.

[3] ZHANG L, ESTRIN D, BURKE J, et al. Named data networking (NDN) project NDN-0001[J]. Acm Sigcomm Computer Communication Review, 2010, 44(3): 66-73.

[4] TROSSEN D, PARISIS G, VISALA K, et al. Conceptual architecture: principles, patterns and subcomponents descriptions[R]. Technical Report, FP7-INFSO-ICT-257217_PURSUIT_D2.2, 2011.

[5] AHLGREN B, D’AMBROSIO M, DANNEWITZ C, et al. Second NetInf architecture description[R]. Technical Report, FP7-ICT- 2007-1-216041-4WARD / D-6.2, 2010.

[6] ROSSI D, ROSSINI G. On sizing CCN content stores by exploiting topological information[C]//Computer Communications Workshops (INFOCOM WKSHPS), IEEE Conference. Orlando, c2012: 280-285.

[7] LI Z, XIE G, WANG Y, et al. Optimal cache allocation for content-centric networking[C]//IEEE International Conference on Network Protocols (ICNP). Goettingen, c2013: 1-10.

[8] XU Y, LI Y, LIN T, et al. A novel cache size optimization scheme based on manifold learning in content centric networking[J]. Journal of Network & Computer Applications, 2014, 37(1): 273-281.

[9] LAOUTARIS N, SYNTILA S, STAVRAKAKIS I, Meta algorithms for hierarchical Web caches[C]// IEEE International Conference on Performance, Computing, and Communications. Phoenix, c2004: 445-452.

[10] WEI K C, HE D, PSARAS I, et al. Cache "less for more" in information-centric networks (extended version)[J]. Computer Communications, 2013, 36(7): 758-770.

[11] PAVLOU G, PSARAS I, WEI K C. Probabilistic in-network caching for information-centric networks[C]//The Second Edition of the ICN Workshop on Information-Centric Networking, ICN ’12. New York, c2012: 55-60.

[12] PSARAS I, WEI K C, PAVLOU G. In-network cache management and resource allocation for information-centric networks[J]. Parallel & Distributed Systems IEEE Transactions, 2014, 25(11): 2920-2931.

[13] ROSENSWEIG E J, KUROSE J. Breadcrumbs: efficient, best-effort content location in cache networks[C]// IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). Rio de Janeiro, c2009: 2631-2635.

[14] ZHU Y, CHEN M, NAKAO A. CONIC: content-oriented network with indexed caching[C]// IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). San Diego, c2010:1-6.

[15] SOURLAS V, GKATZIKIS L, FLEGKAS P, et al. Distributed cache management in information-centric networks[J]. IEEE Transactions on Network & Service Management, 2013, 10(3): 286-299.

[16] KIM Y, YEOM I. Performance analysis of in-network caching for content-centric networking[J]. Computer Networks, 2013, 57(13): 2465-2482.

[17] PENTIKOUSIS K, OHLMAN B, DAVIES E, et al. Information- centric networking: evaluation methodology[J/OL].http://www.ietf. org/ proceedings/90/slidcs/sildes-90-icnrg-8.pdf.

[18] EWMA[EB/OL]. http://www.itl.nist.gov/div898/handbook/pmc/secti on4/ pmc431.htm.

[19] ARLITT M, CHERKASOVA L, DILLEY J, et al. Evaluating content management techniques for web proxy caches[R]. Technical Report, HPL-98-173, 1999.

[20] NS-3[EB/OL]. https://www.nsnam.org/.

[21] ndnSIM documentation[EB/OL]. http://ndnsim.net/.

[22] SPRING N, MAHAJAN R, WETHERALL D. Measuring ISP topologies with rocketfuel[J]. Networking IEEE/ACM Transactions, 2002, 32(4):133-145.

Cache allocation policy of service contents along delivery paths for the smart collaborative network

FENG Bo-hao1, ZHOU Hua-chun1, ZHANG Hong-ke1, ZHANG Ming-chuan1,2

(1.Institute of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China; 2. Information Engineering College, Henan University of Science and Technology, Luoyang 471023, China)

A cache allocation policy (CA) of service contents along delivery paths was proposed for the smart collaborative network. CA allocates on-path caches to service contents based on their popularity, expecting to fully and efficiently utilize the cache resource along the delivery path and further improving the network performance. The performance of proposed policy CA was evaluated under a 5-layer tree topology and a 279-node real network topology. The results show that CA outperforms others in terms of tested performance indexes. Compared with LCE(leave copy everywhere) used by named data networking (NDN), CA reduces the distance that users fetch service contents over 20%.

cache allocation policy, smart collaborative network, smart identifier network, information centric networking, future network architecture

TN915

A

10.11959/j.issn.1000-436x.2016060

2015-05-11；

2015-08-27基金項目：國家基礎(chǔ)研究發(fā)展計劃（“973”計劃）基金資助項目（No.2013CB329101）；國家高技術(shù)研究發(fā)展計劃（“863”計劃）基金資助項目（No.2015AA015702）；國家自然科學(xué)基金資助項目（No.61271202, No.U1404611）

The National Basic Research Program of China (973 Program) (No.2013CB329101), The National High Technology of China (863 Program) (No. 2015AA015702), The National Natural Science Foundation of China (No.61271202, No.U1404611)

馮博昊（1988-），男，北京人，北京交通大學(xué)博士生，主要研究方向為未來互聯(lián)網(wǎng)體系架構(gòu)、信息為中心網(wǎng)絡(luò)、網(wǎng)絡(luò)緩存、軟件定義網(wǎng)絡(luò)、時延容忍網(wǎng)絡(luò)等。

周華春（1965-），男，安徽貴池人，北京交通大學(xué)教授、博士生導(dǎo)師，主要研究方向為未來互聯(lián)網(wǎng)體系架構(gòu)、移動互聯(lián)網(wǎng)、網(wǎng)絡(luò)安全、空間網(wǎng)絡(luò)等。

張宏科（1957-），男，山西大同人，北京交通大學(xué)教授、博士生導(dǎo)師，主要研究方向為下一代互聯(lián)網(wǎng)架構(gòu)、協(xié)議理論與技術(shù)、移動互聯(lián)網(wǎng)絡(luò)路由、傳感器網(wǎng)絡(luò)技術(shù)等。

張明川（1977-），男，河南汝州人，河南科技大學(xué)副教授、碩士生導(dǎo)師，主要研究方向為下一代互聯(lián)網(wǎng)架構(gòu)、信息中心網(wǎng)絡(luò)、路由協(xié)議、物聯(lián)網(wǎng)技術(shù)等。