高全力，李慶敏，高 嶺，王西漢，胡發(fā)麗

(1.西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710048；2.西安工程大學(xué) 新型網(wǎng)絡(luò)智能信息服務(wù)國(guó)家地方聯(lián)合工程中心，陜西 西安 710048)

0 引 言

目前，互聯(lián)網(wǎng)仍以TCP/IP協(xié)議棧為基礎(chǔ)模型，在數(shù)據(jù)交換時(shí)是以找到數(shù)據(jù)所在的設(shè)備為前提映射到設(shè)備中；對(duì)在網(wǎng)絡(luò)中可能進(jìn)行多次傳播的競(jìng)爭(zhēng)性重復(fù)數(shù)據(jù)，需要分別建立連接來(lái)完成。這種方式過(guò)度依賴中心服務(wù)器的計(jì)算能力以及帶寬資源，會(huì)造成傳輸擁塞和網(wǎng)絡(luò)癱瘓的問(wèn)題。為解決TCP/IP結(jié)構(gòu)存在的問(wèn)題，信息中心化(ICN)作為新一代互聯(lián)網(wǎng)被提出。ICN的網(wǎng)絡(luò)范式和架構(gòu)不同于基于TCP/IP的網(wǎng)絡(luò)。目前，ICN得到廣泛研究和推廣，而命名數(shù)據(jù)網(wǎng)絡(luò)(NDN)是ICN的方案之一。NDN改進(jìn)的是地址命名系統(tǒng)和路由器緩存功能。這種設(shè)計(jì)使得客戶端能快速獲取請(qǐng)求的內(nèi)容，有效地減少網(wǎng)絡(luò)帶寬浪費(fèi)，減輕源服務(wù)器端的響應(yīng)負(fù)擔(dān)，從而提高網(wǎng)絡(luò)的順暢度[1]。

NDN利用內(nèi)容存儲(chǔ)提供緩存功能，而其緩存機(jī)制受替換策略嚴(yán)格控制，因此高效的替換策略是NDN發(fā)展的決定性因素之一。為了提高替換的效率，許多學(xué)者進(jìn)行了有關(guān)NDN緩存替換策略的研究：最近最少使用算法(LRU)[2]對(duì)最近最少使用的緩存內(nèi)容進(jìn)行替換；最少使用算法(LFU)[3]經(jīng)對(duì)比后替換使用頻率低的內(nèi)容；先進(jìn)先出算法(FIFO)替換最先緩存的內(nèi)容；文獻(xiàn)[4]提出淘汰請(qǐng)求代價(jià)小的內(nèi)容；文獻(xiàn)[5]則提出淘汰動(dòng)態(tài)流行度小的內(nèi)容。但是，LRU、LFU、FIFO等算法只考慮單一因素，無(wú)法區(qū)分內(nèi)容的請(qǐng)求頻率是高還是低，存在流行內(nèi)容被非流行內(nèi)容驅(qū)逐的問(wèn)題。

一些研究提出了綜合計(jì)算內(nèi)容流行度的緩存替換算法：BERNARDINI等提出由不同用戶提供的數(shù)據(jù)包應(yīng)該進(jìn)行區(qū)分[6]；FAN等提出利用影響整體緩存增益的因素將內(nèi)容對(duì)象從內(nèi)容文件細(xì)化到內(nèi)容塊，并實(shí)現(xiàn)了對(duì)內(nèi)容塊的存放和替換[7]；文獻(xiàn)[8]提出了一種基于深度學(xué)習(xí)的替換策略。但是以上算法的計(jì)算量較大，而NDN路由器的緩存容量低，計(jì)算資源有限，使得實(shí)際工作時(shí)造成大量網(wǎng)絡(luò)資源的浪費(fèi)。

本文面向NDN網(wǎng)絡(luò)的緩存替換策略展開(kāi)研究，結(jié)合在軟件定義網(wǎng)絡(luò)(SDN)中根據(jù)多屬性值作決策，從而降低網(wǎng)絡(luò)時(shí)延的情況[9]，并綜合考慮了數(shù)據(jù)包大小、內(nèi)容流行度和請(qǐng)求代價(jià)，提出一種基于熵的概率緩存替換策略(EPR)。在該策略中，路由節(jié)點(diǎn)統(tǒng)計(jì)所有緩存數(shù)據(jù)包的大小、內(nèi)容流行度和請(qǐng)求代價(jià)字段的值并進(jìn)行熵權(quán)重值的計(jì)算，然后在需要緩存替換時(shí)選擇熵權(quán)重值最小的數(shù)據(jù)包進(jìn)行替換。該策略不僅計(jì)算量小且綜合考慮了多項(xiàng)影響因素。實(shí)驗(yàn)結(jié)果顯示，相較于NDN網(wǎng)絡(luò)中現(xiàn)有的替換策略，EPR策略在平均緩存命中率和平均請(qǐng)求時(shí)延方面有較大的改善。

1 數(shù)據(jù)結(jié)構(gòu)及替換策略

1.1 NDN節(jié)點(diǎn)組成與數(shù)據(jù)結(jié)構(gòu)

在當(dāng)前的NDN網(wǎng)絡(luò)體系架構(gòu)中，包括客戶端(client)、源服務(wù)器(origin server)和路由器(router)等3個(gè)模塊，其傳輸內(nèi)容主要包括興趣包(interest packet)和數(shù)據(jù)包(data packet)等2類?？蛻舳苏?qǐng)求數(shù)據(jù)時(shí)，首先向網(wǎng)絡(luò)中發(fā)送興趣包[10]。在請(qǐng)求的發(fā)送過(guò)程中，如果遇到某個(gè)節(jié)點(diǎn)中恰有可以滿足請(qǐng)求的數(shù)據(jù)，就會(huì)響應(yīng)一個(gè)數(shù)據(jù)包，將響應(yīng)的數(shù)據(jù)返回客戶端;否則,將轉(zhuǎn)發(fā)到源服務(wù)器請(qǐng)求數(shù)據(jù)。數(shù)據(jù)包會(huì)沿著對(duì)應(yīng)興趣包的傳遞路徑返回作為反饋[10]?？蛻舳双@取內(nèi)容的過(guò)程分為2個(gè)步驟，如圖1所示。

命名數(shù)據(jù)網(wǎng)絡(luò)的網(wǎng)內(nèi)路由節(jié)點(diǎn)有3個(gè)重要的數(shù)據(jù)結(jié)構(gòu)：內(nèi)容存儲(chǔ)庫(kù)(content store，CS),提供內(nèi)容的存儲(chǔ)；未決興趣表(pending interest table，PIT),存儲(chǔ)經(jīng)由這個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)出去的興趣包的名稱和與這些請(qǐng)求相關(guān)的接口信息；轉(zhuǎn)發(fā)信息表(forwarding information base，F(xiàn)IB)，記錄了節(jié)點(diǎn)間的轉(zhuǎn)發(fā)規(guī)則[11]。

圖 1 NDN客戶端請(qǐng)求處理流程Fig.1 NDN client request processing flow

1.2 緩存替換策略

由于NDN中間路由器節(jié)點(diǎn)緩存容量通常較小，計(jì)算資源有限，很容易達(dá)到緩存極限。當(dāng)一個(gè)新的內(nèi)容需要緩存時(shí)，就會(huì)面臨緩存替換。因此，如何選擇合適的數(shù)據(jù)包與CS表中原有數(shù)據(jù)包進(jìn)行替換，以提高緩存空間的效率，對(duì)于緩存替換策略的有效性就顯得尤為重要。

NDN中默認(rèn)使用的緩存替換策略是LRU。LRU主要思想是，當(dāng)數(shù)據(jù)在最近一段時(shí)間內(nèi)經(jīng)常被訪問(wèn)，那么它在以后也會(huì)經(jīng)常被訪問(wèn)，所以需要替換時(shí)優(yōu)先淘汰不經(jīng)常訪問(wèn)的數(shù)據(jù)。LFU的核心思想是，以次數(shù)作為參考，設(shè)置一個(gè)時(shí)間戳，替換時(shí)優(yōu)先考慮時(shí)間戳內(nèi)次數(shù)最少的數(shù)據(jù)內(nèi)容。在FIFO緩存設(shè)計(jì)中，應(yīng)該替換緩存時(shí)間記錄最早的數(shù)據(jù)。Age-based策略是給每個(gè)緩存數(shù)據(jù)設(shè)置過(guò)期時(shí)間(TTL)。緩存數(shù)據(jù)的節(jié)點(diǎn)與源服務(wù)器的距離和用戶的請(qǐng)求跳數(shù)相關(guān)，距離越遠(yuǎn)，請(qǐng)求跳數(shù)越小，TTL就越大，替換時(shí)淘汰TTL較小或歸零的數(shù)據(jù)[1]。CCP策略則是周期性地統(tǒng)計(jì)內(nèi)容的請(qǐng)求次數(shù)，實(shí)時(shí)計(jì)算動(dòng)態(tài)流行度，最后淘汰流行度小的內(nèi)容[1]。不過(guò)，這些替換策略使得用作決策的參數(shù)單一，替換后的效果不夠理想。文獻(xiàn)[6]提出由不同用戶提供的數(shù)據(jù)包應(yīng)該進(jìn)行區(qū)分，不能用相同的方式處理這些數(shù)據(jù)包，發(fā)送的數(shù)據(jù)對(duì)網(wǎng)絡(luò)有影響的用戶所提供的數(shù)據(jù)包應(yīng)該優(yōu)先考慮。緩存替換策略結(jié)合一些社交感知信息可以提高網(wǎng)絡(luò)緩存性能，但也增加了開(kāi)銷。文獻(xiàn)[12-13]提出一種基于效用的替換策略(LVF)。該策略使用延遲、受歡迎程度和年齡等3個(gè)因素計(jì)算效用函數(shù)，以選擇要從CS表中替換的條目。此策略使平均緩存命中率、平均請(qǐng)求時(shí)延等指標(biāo)有較大改善。文獻(xiàn)[13-14]提出最近使用頻率(RUF)緩存替換策略，但錯(cuò)誤地跟蹤了內(nèi)容流行度的變化，為舊數(shù)據(jù)分配了更大的權(quán)重。

2 EPR機(jī)制

在信息論中，Shannon的熵概念反映了一個(gè)事件、屬性或樣本所包含的平均信息量。熵中隱含的思想是，事件發(fā)生的可能性越小，它在發(fā)生時(shí)提供的信息就越多。熵可以作為客觀的權(quán)重度量，并以此作出客觀決策[15-17]。

考慮到現(xiàn)有緩存替換策略的問(wèn)題，基于上述熵的特點(diǎn)，本文提出EPR緩存替換策略。EPR引入了多個(gè)屬性以作替換決策，并且根據(jù)熵權(quán)理論客觀地分配每個(gè)屬性的權(quán)重。當(dāng)需要替換數(shù)據(jù)包時(shí)，路由器會(huì)統(tǒng)計(jì)CS表中所有數(shù)據(jù)包攜帶的緩存內(nèi)容大小、內(nèi)容流行度、請(qǐng)求代價(jià)3個(gè)屬性的信息，然后根據(jù)屬性值和分配的屬性權(quán)重計(jì)算每個(gè)數(shù)據(jù)包的權(quán)重，接著計(jì)算每個(gè)數(shù)據(jù)包的替換概率。最后，基于計(jì)算的替換概率從所有候選中按概率大小選擇替換的數(shù)據(jù)包。

EPR緩存替換策略需要統(tǒng)計(jì)的參數(shù)以及參數(shù)選擇的意義如下：

數(shù)據(jù)包大?。狠^大的數(shù)據(jù)包在一定時(shí)段內(nèi)緩存的位置離客戶端越近，客戶端發(fā)出相同請(qǐng)求時(shí)能就近響應(yīng)，減少網(wǎng)絡(luò)中的帶寬浪費(fèi)。

內(nèi)容流行度：適應(yīng)內(nèi)容流行度的變化。

請(qǐng)求代價(jià)：緩存節(jié)點(diǎn)距離源服務(wù)器的跳數(shù)[18]。

2.1 包格式拓展

為實(shí)現(xiàn)EPR緩存替換策略，在數(shù)據(jù)包原有結(jié)構(gòu)的基礎(chǔ)上，對(duì)其格式進(jìn)行拓展，增加了DataSize、PopularityCount、DataJumpHop等3個(gè)字段，如表1所示。其中Datasize標(biāo)識(shí)數(shù)據(jù)包的大??；PopularityCount標(biāo)識(shí)數(shù)據(jù)包內(nèi)容的請(qǐng)求次數(shù)，即內(nèi)容流行度；DataJumpHops標(biāo)識(shí)數(shù)據(jù)包緩存路由器節(jié)點(diǎn)距離源服務(wù)器的跳數(shù)，即請(qǐng)求代價(jià)。

表 1 拓展后的數(shù)據(jù)包格式Tab.1 Expanded data packet format

2.2 替換算法

在數(shù)據(jù)包返回給客戶端階段，沿途路由節(jié)點(diǎn)根據(jù)EPR策略在CS表達(dá)到上限時(shí)對(duì)CS表中的數(shù)據(jù)包進(jìn)行屬性熵權(quán)重的計(jì)算，然后刪除概率最小的數(shù)據(jù)包，緩存新的數(shù)據(jù)包。同時(shí)，為了節(jié)約計(jì)算資源，快速響應(yīng)客戶端的請(qǐng)求，本策略將路由節(jié)點(diǎn)的一次計(jì)算結(jié)果，用于多次對(duì)新來(lái)的數(shù)據(jù)包進(jìn)行緩存替換，次數(shù)為CS表存儲(chǔ)大小的1/2，實(shí)現(xiàn)“一次計(jì)算，多次決策”。當(dāng)替換到一定的次數(shù)，再對(duì)現(xiàn)存的所有數(shù)據(jù)包進(jìn)行新屬性熵權(quán)重計(jì)算。

計(jì)算屬性權(quán)重的算法流程如下：

步驟1 統(tǒng)計(jì)CS表中各個(gè)表項(xiàng)的DataSize、PopularityCount、DataJumpHops等3個(gè)字段的數(shù)據(jù)，將結(jié)果記錄在創(chuàng)建的二維數(shù)組X中，X由n個(gè)m維樣本構(gòu)成，則X可以表示為一個(gè)n×m的矩陣，即

式中：n為CS表的數(shù)據(jù)包數(shù)量；m為屬性數(shù)量；xij為第i個(gè)數(shù)據(jù)包的第j列字段的值。

步驟2 為了消除量綱影響，解決數(shù)據(jù)的可比性，對(duì)數(shù)據(jù)進(jìn)行歸一化處理[16]，即

(1)

式中：maxxj,minxj為矩陣X中第j列字段的最大值和最小值；minxi為第i行數(shù)的最小值。

步驟3 計(jì)算第i行數(shù)據(jù)包的第j列字段所占比重，即計(jì)算每個(gè)數(shù)據(jù)包的提取字段的權(quán)重Pij[16]，

(2)

步驟4 計(jì)算第j列字段，即DataSize、PopularityCount、DataJumpHops字段的信息熵Ej，

(3)

步驟5 計(jì)算第j列字段的差異系數(shù)dj,

dj=1-Ej

(4)

步驟6 計(jì)算第j列字段的權(quán)重wj，

(5)

步驟7 設(shè)置vi作為對(duì)各個(gè)數(shù)據(jù)包的綜合評(píng)價(jià)指標(biāo)，即

(6)

步驟8 設(shè)置Pbi作為進(jìn)行替換決策的數(shù)值依據(jù)，即

(7)

Pbi的值越小，表示其在該路由節(jié)點(diǎn)繼續(xù)緩存的價(jià)值越小，因此可以選擇該值最小一項(xiàng)對(duì)應(yīng)的數(shù)據(jù)包進(jìn)行替換。

2.3 包緩存替換流程

EPR緩存替換策略的包緩存和替換流程如圖2所示。

圖 2 內(nèi)容緩存與替換階段流程Fig.2 Content caching and replacement stage process

當(dāng)數(shù)據(jù)包返回時(shí)，執(zhí)行4個(gè)步驟：

步驟1 路由節(jié)點(diǎn)接收到源服務(wù)器或上游節(jié)點(diǎn)傳遞的數(shù)據(jù)包，首先查看CS表中是否有相同的內(nèi)容：是，則丟棄數(shù)據(jù)包：否，則執(zhí)行步驟2。

步驟2 查看PIT表中是否有相同條目：否，則丟棄數(shù)據(jù)包：是，則執(zhí)行步驟3。

步驟3 轉(zhuǎn)發(fā)數(shù)據(jù)包到PIT表項(xiàng)中記錄的所有請(qǐng)求接口，并在PIT表中刪除已滿足的條目，判斷CS表是否已達(dá)緩存上限：否，則緩存在該節(jié)點(diǎn)；是，則執(zhí)行步驟4。

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

為了驗(yàn)證本文提出的EPR緩存替換策略在NDN網(wǎng)絡(luò)中的實(shí)際部署效果和效率，在基于NS-3[19]的網(wǎng)絡(luò)仿真平臺(tái)ndnSIM[20-21]上對(duì)EPR機(jī)制進(jìn)行模擬實(shí)驗(yàn),選取NDN網(wǎng)絡(luò)中的LRU、FIFO、LVF、RUF緩存替換策略作為參照對(duì)象。

3.1 仿真環(huán)境

3.1.1 實(shí)驗(yàn)平臺(tái)相關(guān)參數(shù)

所有仿真作業(yè)均在本地計(jì)算機(jī)上進(jìn)行。操作系統(tǒng)及版本為Ubuntu18.04，64-bit，CPU為Intel(R) Core(TM)i7-9700K CPU@ 3.60 GHz；實(shí)驗(yàn)平臺(tái)為ndnSIM ，版本控制在2.7；實(shí)驗(yàn)分配內(nèi)存為10 GiB，硬盤100 GiB，處理器數(shù)量為8個(gè)。

3.1.2 實(shí)驗(yàn)場(chǎng)景

本實(shí)驗(yàn)拓?fù)錇?×8的Grid網(wǎng)絡(luò)拓?fù)淠Ｐ?。此模型所有?jié)點(diǎn)都能兩兩通信，具有高可靠性和高通信效率特點(diǎn)，如圖3所示。圖3中：藍(lán)色代表源服務(wù)器，共24個(gè)；綠色代表客戶端，共12個(gè)；紅色代表中間路由節(jié)點(diǎn)，共28個(gè)。

圖 3 8×8拓?fù)淠Ｐ虵ig.3 8×8 topology model

假設(shè)每個(gè)客戶端請(qǐng)求的內(nèi)容個(gè)數(shù)為20個(gè)，內(nèi)容前綴名為“/prefix1”，后綴為隨機(jī)數(shù)。所有路由節(jié)點(diǎn)的緩存空間容量相同，緩存伊始不包含任何內(nèi)容，采用隨處緩存LCE[22]緩存放置策略。每個(gè)源服務(wù)器響應(yīng)發(fā)出的數(shù)據(jù)包大小不同，范圍為0～2×106。其他設(shè)置：鏈路帶寬為1 Mbis/s，時(shí)延為10 ms;實(shí)驗(yàn)測(cè)試時(shí)間為20 s，客戶端請(qǐng)求頻率為20 個(gè)/s。

3.2 性能評(píng)價(jià)指標(biāo)

主要從平均緩存命中率和平均請(qǐng)求時(shí)延兩方面，對(duì)比分析本方案的性能與LRU、FIFO、LVF、RUF策略。

1) 平均緩存命中率Hr是指在實(shí)驗(yàn)時(shí)間內(nèi)中間路由節(jié)點(diǎn)命中的興趣包數(shù)與各客戶端發(fā)出的請(qǐng)求興趣包的總數(shù)的比值，Hr能反映路由節(jié)點(diǎn)減少源服務(wù)器的工作量[1]。

(8)

式中：N表示客戶端發(fā)送的請(qǐng)求興趣包的總數(shù)；hi表示客戶端請(qǐng)求興趣包在路由節(jié)點(diǎn)Vi得到響應(yīng)的次數(shù)[23]。

2) 平均請(qǐng)求時(shí)延?？蛻舳税l(fā)出請(qǐng)求興趣包到接收響應(yīng)數(shù)據(jù)包的時(shí)間，單位為ms。該值越大，用戶得到反饋越慢，平均請(qǐng)求時(shí)延可以用來(lái)衡量用戶體驗(yàn)好壞[1]。

3.3 實(shí)驗(yàn)結(jié)果分析

3.3.1 平均緩存命中率

圖4顯示了EPR策略和LRU、FIFO、LVF、RUF策略的平均緩存命中率，其統(tǒng)計(jì)時(shí)間為10 s。

圖 4 平均緩存命中率隨緩存量的變化Fig.4 Average cache hit rate with cache size

從圖4可以看出，當(dāng)路由節(jié)點(diǎn)的CS表逐漸增大緩存空間，5種替換策略的平均緩存命中率也隨之緩慢提高。EPR緩存策略使用數(shù)據(jù)包大小、內(nèi)容流行度、請(qǐng)求代價(jià)等3種屬性作為替換的參考，避免了只考慮單一因素可能造成的流行內(nèi)容被非流行內(nèi)容頻繁替換的現(xiàn)象，內(nèi)容的緩存命中率平均提升了10%，對(duì)于比較的所有緩存替換策略，其表現(xiàn)最佳。

3.3.2 平均請(qǐng)求時(shí)延

圖5顯示了EPR策略和LRU、FIFO、LVF、RUF策略的平均請(qǐng)求時(shí)延，統(tǒng)計(jì)時(shí)長(zhǎng)為10 s。

圖 5 平均請(qǐng)求時(shí)延隨緩存量的變化Fig.5 Average request latency with cache size

從圖5可以看出，當(dāng)緩存的容量逐漸增大時(shí)，5種緩存替換策略的平均請(qǐng)求時(shí)延逐漸下降。特別是緩存的容量越大，EPR策略的平均請(qǐng)求時(shí)延效果相比其他4種策略更好。原因是緩存的數(shù)據(jù)包越多，計(jì)算信息熵時(shí)提供的信息越多，做出的替換決策越準(zhǔn)確，效果自然更優(yōu)。EPR策略的平均請(qǐng)求時(shí)延比LRU策略降低了7.21%。

4 結(jié) 語(yǔ)

本文實(shí)現(xiàn)了基于熵的概率緩存替換(EPR)算法，并將其性能與NDN網(wǎng)絡(luò)中LRU、FIFO、LVF、RUF替換策略進(jìn)行比較。仿真結(jié)果表明：與其他4種替換策略相比，EPR替換策略實(shí)現(xiàn)了更高的平均緩存命中率和更低的平均請(qǐng)求時(shí)延；EPR替換策略的平均緩存命中率和平均請(qǐng)求時(shí)延效果取決于分配的內(nèi)容存儲(chǔ)的大小。通過(guò)改變CS容量大小，發(fā)現(xiàn)EPR替換策略在以上兩方面優(yōu)于其他4種替換策略，特別是平均請(qǐng)求時(shí)延這一指標(biāo)優(yōu)勢(shì)明顯。對(duì)于未來(lái)的研究，將在不同的網(wǎng)絡(luò)拓?fù)淠Ｐ椭袑PR與其他4種替換策略進(jìn)行對(duì)比。