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

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

?

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

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

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

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

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

1 引言

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

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

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

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

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

2 相關工作

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

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

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

文獻[10]提出一種服務內(nèi)容在傳輸路徑上的緩存準入策略Betw。該策略根據(jù)介數(shù)中心性(BC, betweeness centrality)來緩存服務內(nèi)容。節(jié)點的BC是指該節(jié)點處在拓撲中任意其他兩點的最短路徑上的次數(shù)，它反映出該節(jié)點在拓撲中的重要程度。Betw的優(yōu)勢在于服務內(nèi)容被存儲在拓撲中最重要的節(jié)點上，利于共享。但BC是拓撲特性，與內(nèi)容的流行度沒有關系，無法反映出內(nèi)容的流行度。此外，高BC節(jié)點的緩存替換速率將極高，造成被緩存內(nèi)容的不穩(wěn)定。

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

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

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

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

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

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

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

3.2 服務請求模型分析

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

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

圖2 Zipf分布的累計概率

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

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

3.3 具體機制

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

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

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

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

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

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

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

表2 接入路由器維護的排序

3.3.2 傳輸路徑上路由器的相關操作

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

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

圖3 請求報文格式

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

圖5給出了一個簡單的用戶發(fā)送請求報文至服務器的例子，以說明路由器對請求報文操作的過程。假設每臺路由器可以容納5個服務內(nèi)容，被請求內(nèi)容排序為12，節(jié)點1、2、3均沒有存儲相應的服務內(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域設為MAX。當服務內(nèi)容回傳時，只有節(jié)點3進行存儲。

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

對于鏈路開銷的問題，由于一個區(qū)域內(nèi)的請求分布大致相同，接入網(wǎng)的服務內(nèi)容流行度感知節(jié)點可隨機選取某個或某幾個用戶作為探測服務內(nèi)容流行度的樣本，這樣可有效降低鏈路的開銷。對于服務內(nèi)容流行度感知節(jié)點自身處理開銷的問題，本文所提流行度測試方法僅僅是初步方案，由于傳輸路徑上無法存儲所有服務內(nèi)容，服務內(nèi)容流行度感知節(jié)點也沒必要存儲所有SID的請求數(shù)量。該問題的實質(zhì)其實與緩存替代策略所解決的問題完全一樣，即在一個有限長度的列表中進行表項優(yōu)先級的排序。由于服務內(nèi)容流行度感知節(jié)點只需要知道服務內(nèi)容的排序而不是具體請求數(shù)量，可使用基于頻率的替代策略進行流行度的排序，如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所使用的默認策略，ndnSIM已經(jīng)提供。本文分別在5層的樹型拓撲和279個節(jié)點的真實網(wǎng)絡拓撲中對所有策略進行性能測試。樹型拓撲常用于接入網(wǎng)，但其無法表現(xiàn)出真實網(wǎng)絡的無標度特性。故本文從Rocketfuel’s AT&T topology[22]中選擇編號為1221的真實網(wǎng)絡拓撲。2種拓撲如圖6所示。

(a) 樹型拓撲

(b) 真實拓撲

圖6 真實網(wǎng)絡拓撲

在5層樹型拓撲中，一個服務器接入在樹根處，16個用戶模擬器分別接入到16個葉節(jié)點上，故用戶到服務器的距離為6跳（用戶到接入路由器、服務器到第一跳路由器均計為1跳，真實拓撲也以此方式計算跳數(shù)）。樹型拓撲中節(jié)點的帶寬設置的較大，所以擁塞問題不會對最終的結(jié)果造成多大的影響。真實拓撲共有731條鏈路，其中，接入節(jié)點有169個，網(wǎng)關節(jié)點45個，骨干網(wǎng)節(jié)點65個。本文并未改變該拓撲的原有參數(shù)。50個服務器和100個用戶模擬器將隨機接入到不同的接入節(jié)點中。2.5104個內(nèi)容將隨機分布到這100個服務器中，而每個服務內(nèi)容只被某一個服務器提供。另外，在2種拓撲中，每個網(wǎng)關節(jié)點（灰色）都連接一個服務內(nèi)容流行度感知節(jié)點。樹型拓撲的網(wǎng)關節(jié)點為第5層節(jié)點。

表3 仿真參數(shù)

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

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

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

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

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

4.2 各策略服務獲取距離的比較

圖8分別給出了在樹型拓撲和真實網(wǎng)絡拓撲下各策略的實時服務獲取距離。各策略1 000 s內(nèi)的總平均服務獲取距離以及相對于LCE的減小率如表4所示?？梢钥闯觯?種拓撲下性能最好的是CA，在樹型拓撲下平均服務獲取距離為3.81跳，在真實拓撲下為4.13跳，相對于LCE，減小率大于20%。其次是LCD，相對于LCE的減小率為14%左右。

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

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

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

Betw根據(jù)BC緩存服務內(nèi)容，它利用BC確定服務內(nèi)容在傳輸路徑上的存儲位置。但Betw的缺陷在于BC是反映網(wǎng)絡拓撲的特性，它的性能與拓撲直接相關，而且高BC的節(jié)點緩存替代速率較高，不易實現(xiàn)服務內(nèi)容的共享。

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

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

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

圖9分別給出了在樹型拓撲和真實網(wǎng)絡拓撲下各策略的實時緩存刪除操作總量。各策略1 000 s內(nèi)的總平均緩存刪除操作總量以及相對于LCE的減小率如表4所示?？梢钥闯?，2種拓撲下性能最好的是CA，在樹型拓撲下緩存刪除操作總量為每秒95.98次，在真實拓撲下為每秒680.44次，相對于LCE，減小率在98%左右。這說明在緩存分配策略CA中，被緩存的服務內(nèi)容相對穩(wěn)定，利于服務內(nèi)容的共享。其原因在于緩存分配策略CA指定了服務內(nèi)容在傳輸路徑的存儲位置并阻止非流行服務內(nèi)容進入緩存，有效降低了緩存內(nèi)容的替代速率。

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

圖10給出了在樹型拓撲和真實網(wǎng)絡拓撲下各策略的實時請求報文數(shù)量。各策略1 000 s內(nèi)的總平均請求報文數(shù)量以及相對于LCE的減小率如表4所示。

緩存分配策略CA在2種拓撲下表現(xiàn)良好，相對于LCE的減小率分別為20.34%和12.27%。真實拓撲相對于LCE的減小率低于樹型拓撲的原因在于真實網(wǎng)絡是無標度網(wǎng)絡并且用戶傳輸路徑相互重疊、相互影響，加之其節(jié)點數(shù)量、用戶模擬器數(shù)量遠遠多于樹型拓撲，服務請求在網(wǎng)絡中的傳輸更具一般性。此外，雖然Betw的請求報文數(shù)量也很低，但由于其只考慮了拓撲特性而不是服務內(nèi)容的流行度，其用戶的服務獲取距離并不是最短的。緩存分配策略CA則是根據(jù)服務內(nèi)容的流行度存儲，故在請求報文數(shù)量降低的同時，用戶的平均服務獲取距離最小。

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

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

5 結(jié)束語

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

[1] 張宏科, 羅洪斌. 智慧協(xié)同網(wǎng)絡體系基礎研究[J]. 電子學報, 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)絡中的服務機理研究[J]. 電子學報, 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基金項目：國家基礎研究發(fā)展計劃（“973”計劃）基金資助項目（No.2013CB329101）；國家高技術研究發(fā)展計劃（“863”計劃）基金資助項目（No.2015AA015702）；國家自然科學基金資助項目（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-），男，北京人，北京交通大學博士生，主要研究方向為未來互聯(lián)網(wǎng)體系架構(gòu)、信息為中心網(wǎng)絡、網(wǎng)絡緩存、軟件定義網(wǎng)絡、時延容忍網(wǎng)絡等。

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

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

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