蔡 凌 , 王興偉 , 汪晉寬 , 黃 敏

1(東北大學(xué) 秦皇島分校 控制工程學(xué)院,河北 秦皇島 066004)

2(東北大學(xué) 軟件學(xué)院,遼寧 沈陽 110819)

3(東北大學(xué) 信息科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

互聯(lián)網(wǎng)設(shè)計(jì)之初,用戶主要的需求是聯(lián)通性和資源共享.經(jīng)過近50年的發(fā)展,以視頻分發(fā)、文件下載等為代表的內(nèi)容獲取服務(wù)已成為互聯(lián)網(wǎng)中的主流應(yīng)用需求,用戶對內(nèi)容本身的關(guān)注勝于對內(nèi)容位置的關(guān)注.為滿足新的網(wǎng)絡(luò)需求,提出了信息中心型網(wǎng)絡(luò)(information centric neworking,簡稱ICN)[1],將內(nèi)容名字作為網(wǎng)絡(luò)路由和傳輸?shù)臉?biāo)識,當(dāng)用戶請求某一內(nèi)容時(shí),任何緩存該內(nèi)容的節(jié)點(diǎn)都可以做出響應(yīng),從而顯著提升內(nèi)容傳輸效率.Named Data Networking(NDN)/Content-Centric Networking(CCN)[2],Data-Oriented Network Architecture (DONA)[3],Network of Information(NetInf)[4]和ContentMediator architecture for content-aware nETworks (COMET)[5]等是典型的ICN類型的網(wǎng)絡(luò)架構(gòu).

網(wǎng)內(nèi)緩存是ICN的重要特征.雖然緩存理論及相關(guān)技術(shù)已經(jīng)在P2P,CDN和Web等領(lǐng)域中得到了較為廣泛和深入的研究和應(yīng)用,但是它們并不適用于ICN架構(gòu)體系,主要原因是:ICN中的內(nèi)容基于全網(wǎng)統(tǒng)一命名,具有緩存透明化的特征,可服務(wù)于不同類型的網(wǎng)絡(luò)流量,而采用私有協(xié)議的P2P,基于域自主命名的Web,相同的內(nèi)容很難被統(tǒng)一命名,難以被全網(wǎng)共享,且服務(wù)對象單一;ICN的緩存具有泛在化特性,任何節(jié)點(diǎn)都可緩存任意內(nèi)容,任何內(nèi)容都可緩存在任意節(jié)點(diǎn)上,而且節(jié)點(diǎn)上緩存的內(nèi)容存在被不斷替換的可能,這導(dǎo)致緩存拓?fù)浣Y(jié)構(gòu)具有動(dòng)態(tài)變化的特征[6?8],而Web和CDN緩存點(diǎn)的位置一般是確定的,緩存拓?fù)浣Y(jié)構(gòu)較為規(guī)則,因此需要探索和研究新的機(jī)制與策略.

適用于ICN的緩存機(jī)制與策略首先要解決內(nèi)容部署問題.ICN的網(wǎng)內(nèi)緩存是作為一種基礎(chǔ)設(shè)施服務(wù)提供給網(wǎng)絡(luò)的,需要緩存大量內(nèi)容,而路由節(jié)點(diǎn)的存儲空間相對而言非常有限.為了充分利用有限的節(jié)點(diǎn)緩存資源,已經(jīng)提出了一些新的緩存算法.這些算法大致可以分為3類:一類是基于節(jié)點(diǎn)數(shù)據(jù)的算法,根據(jù)節(jié)點(diǎn)在拓?fù)浣Y(jié)構(gòu)中的位置、節(jié)點(diǎn)的性能等,為內(nèi)容選擇緩存節(jié)點(diǎn);一類是基于內(nèi)容數(shù)據(jù)的算法,根據(jù)內(nèi)容流行度選擇要緩存的內(nèi)容.這兩類算法雖然可改善網(wǎng)內(nèi)緩存性能,但由于節(jié)點(diǎn)和內(nèi)容之間缺乏相互感知,前一類算法無法探知不同流行度的內(nèi)容對緩存資源的不同需求,后一類算法缺乏獲取網(wǎng)絡(luò)性能的手段,不能對網(wǎng)內(nèi)緩存資源進(jìn)行有效控制.因此提出了結(jié)合節(jié)點(diǎn)數(shù)據(jù)和內(nèi)容數(shù)據(jù)的又一類算法,根據(jù)節(jié)點(diǎn)和內(nèi)容之間相互影響的關(guān)系,確定內(nèi)容與節(jié)點(diǎn)的匹配關(guān)系,進(jìn)行自適應(yīng)的緩存.

由于ICN具有動(dòng)態(tài)特性,不同時(shí)期的網(wǎng)絡(luò)特性不同,節(jié)點(diǎn)狀態(tài)不同,且ICN網(wǎng)絡(luò)具有泛在緩存的特征,任何節(jié)點(diǎn)都可以緩存任意內(nèi)容,同時(shí),任何內(nèi)容都可以緩存在任意的節(jié)點(diǎn)上,因此節(jié)點(diǎn)和內(nèi)容均衍生出了海量的數(shù)據(jù)信息,而以上文獻(xiàn)所建立的自適應(yīng)數(shù)學(xué)模型與算法均未涉及對海量數(shù)據(jù)的處理與分析.已有研究表明:利用網(wǎng)內(nèi)大數(shù)據(jù)獲取的數(shù)據(jù)關(guān)聯(lián)性,可更高效地分配網(wǎng)絡(luò)資源并獲得最大化的收益[9,10],這說明大數(shù)據(jù)方法可以作為分析ICN網(wǎng)絡(luò)中海量的節(jié)點(diǎn)和內(nèi)容間感知信息的技術(shù)手段,通過對不同階段感知信息關(guān)聯(lián)性的分析,可挖掘出節(jié)點(diǎn)和內(nèi)容匹配關(guān)系的演變規(guī)律,并利用該規(guī)律進(jìn)行自適應(yīng)的緩存.鑒于此,本文提出將ICN中節(jié)點(diǎn)和內(nèi)容的狀態(tài)數(shù)據(jù)流作為網(wǎng)絡(luò)資源,利用從中獲得的節(jié)點(diǎn)和內(nèi)容的多屬性數(shù)據(jù),挖掘出緩存決策與各屬性間的依賴關(guān)系.在挖掘過程中,根據(jù)當(dāng)前節(jié)點(diǎn)和內(nèi)容的狀態(tài)數(shù)據(jù)流,采用集成分類算法Adaboost[11]對已觀測到的節(jié)點(diǎn)和緩存內(nèi)容樣本進(jìn)行分析,尋找其中的規(guī)律.這個(gè)規(guī)律就是當(dāng)前階段數(shù)據(jù)流所定義的概念(concept),然后利用這個(gè)規(guī)律或概念對未知節(jié)點(diǎn)和內(nèi)容的關(guān)系進(jìn)行預(yù)測.然而隨著時(shí)間的推移,數(shù)據(jù)流中定義的概念也隨時(shí)可能發(fā)生變化,例如,內(nèi)容從發(fā)布階段進(jìn)入到流行階段,即產(chǎn)生概念漂移[12],因此需要訓(xùn)練新的分類器以適應(yīng)新到的概念.特別是,有時(shí)某些概念會(huì)在數(shù)據(jù)流中重復(fù)出現(xiàn).例如:當(dāng)流行期可達(dá)幾個(gè)月之久的YOUTUBE音樂視頻文件[13]和流行期相對較短的Olympic視頻文件[14]的流行期沖突時(shí),音樂視頻流所對應(yīng)的概念將發(fā)生漂移;而當(dāng)Olympic視頻文件流行期結(jié)束后,音樂視頻流所對應(yīng)的新概念可能會(huì)與Olympic視頻文件發(fā)布前的概念相似或者重復(fù).當(dāng)概念重現(xiàn)時(shí),本文將歷史概念加入到對新樣本的分類計(jì)算中,在提高緩存決策準(zhǔn)確性的同時(shí),降低分類器的學(xué)習(xí)代價(jià).

本文提出的基于概念學(xué)習(xí)的自適應(yīng)緩存策略,利用感知的節(jié)點(diǎn)數(shù)據(jù)和內(nèi)容數(shù)據(jù)為驅(qū)動(dòng),實(shí)現(xiàn)自適應(yīng)緩存的目標(biāo),主要貢獻(xiàn)如下.

(1) 提出大數(shù)據(jù)驅(qū)動(dòng)的節(jié)點(diǎn)和內(nèi)容的多屬性表達(dá)模型,用來識別并標(biāo)準(zhǔn)化節(jié)點(diǎn)、內(nèi)容的實(shí)時(shí)狀態(tài);

(2) 提出一種基于信息熵的概念漂移識別算法,根據(jù)節(jié)點(diǎn)、內(nèi)容的實(shí)時(shí)狀態(tài)的熵變,檢測概念漂移,不需要對緩存狀態(tài)進(jìn)行實(shí)時(shí)標(biāo)記;

(3) 提出一種基于概念重現(xiàn)的緩存算法,根據(jù)概念漂移結(jié)果更新分類器,重新定義多維狀態(tài)屬性與緩存匹配之間的函數(shù)映射關(guān)系,并在更新的過程中,考慮了概念重現(xiàn)的情況.

1 相關(guān)工作

網(wǎng)內(nèi)緩存是ICN的重要特征,因此,如何選擇合適的節(jié)點(diǎn)部署恰當(dāng)?shù)膬?nèi)容、最大化利用有限的緩存資源是研究的重點(diǎn).ICN提出之初,采用CEE(cache everything everywhere)泛在緩存策略[15],大量冗余內(nèi)容存在于網(wǎng)絡(luò),緩存資源浪費(fèi)嚴(yán)重.為了提高緩存資源的利用率,一些研究提出了基于節(jié)點(diǎn)數(shù)據(jù)的方法.例如將命中節(jié)點(diǎn)的下游節(jié)點(diǎn)[16]或介數(shù)最大的下游節(jié)點(diǎn)[17]作為緩存節(jié)點(diǎn).文獻(xiàn)[18]提出一種基于網(wǎng)絡(luò)全局節(jié)點(diǎn)重要度的緩存節(jié)點(diǎn)選擇算法.文獻(xiàn)[19]提出一種基于網(wǎng)絡(luò)社團(tuán)特性的緩存節(jié)點(diǎn)選擇算法.文獻(xiàn)[20]提出一種基于邊緣優(yōu)先逐級反饋的緩存協(xié)作策略,上游緩存節(jié)點(diǎn)的選擇需要參考下游節(jié)點(diǎn)的緩存決策信息和統(tǒng)計(jì)信息.文獻(xiàn)[21]提出一種綜合考慮節(jié)點(diǎn)緊密中心性、介數(shù)中心性和度中心性等中心性指標(biāo)的緩存機(jī)制.

一些研究在選擇緩存節(jié)點(diǎn)的過程中引入了概率機(jī)制.文獻(xiàn)[22]提出一種節(jié)點(diǎn)以概率p緩存內(nèi)容的算法Prob(copy with PROBability).在文獻(xiàn)[23,24]中,緩存概率參考了緩存節(jié)點(diǎn)與源節(jié)點(diǎn)之間的距離以及緩存容量等因素.文獻(xiàn)[25]中提出的緩存概率因子反比于請求者與源服務(wù)器間的距離.文獻(xiàn)[26]提出的 MBP(max-benefit probability-based caching)策略,緩存概率因子考慮的是節(jié)點(diǎn)的替換代價(jià).這些研究主要考慮節(jié)點(diǎn)的屬性,把節(jié)點(diǎn)的位置和緩存容量等作為緩存選擇的主要依據(jù),內(nèi)容在空間上的分布沒有變得更加均勻和合理.

基于內(nèi)容數(shù)據(jù)的網(wǎng)內(nèi)緩存算法主要關(guān)注的是內(nèi)容流行度的特性.文獻(xiàn)[27]提出了一種基于流行度的緩存內(nèi)容選擇方法,流行度計(jì)算的是基于本地流行度進(jìn)行加權(quán)求得的全局流行度.文獻(xiàn)[28]提出了一種啟發(fā)式概率緩存方法,基于緩存收益和內(nèi)容熱度等因素計(jì)算內(nèi)容的被緩存概率.另外,還有一些研究工作關(guān)注的是內(nèi)容的使用效率,例如,文獻(xiàn)[29,30]將內(nèi)容的使用效率作為是否緩存的判斷依據(jù).文獻(xiàn)[31]提出的StreamCache策略從流的角度出發(fā),將流細(xì)分為不同的內(nèi)容塊,通過統(tǒng)計(jì)不同內(nèi)容塊的使用效率,選擇需要緩存的內(nèi)容塊.基于內(nèi)容數(shù)據(jù)的緩存算法雖然考慮了緩存內(nèi)容的選擇問題,但由于缺少對網(wǎng)絡(luò)環(huán)境、節(jié)點(diǎn)狀態(tài)的考慮,可能造成對節(jié)點(diǎn)緩存資源利用的不合理問題.例如,高流行度的內(nèi)容可能被緩存在高訪問頻率、高負(fù)載率的節(jié)點(diǎn),這將導(dǎo)致該內(nèi)容在節(jié)點(diǎn)上被替換的概率也較高.

為了研究內(nèi)容與節(jié)點(diǎn)的自適應(yīng)緩存問題,實(shí)現(xiàn)內(nèi)容資源和節(jié)點(diǎn)緩存資源的合理配置,部分研究采用結(jié)合節(jié)點(diǎn)數(shù)據(jù)和內(nèi)容數(shù)據(jù)的方法,在節(jié)點(diǎn)和內(nèi)容狀態(tài)相互感知的情況下進(jìn)行節(jié)點(diǎn)和內(nèi)容的匹配.對內(nèi)容狀態(tài)的度量主要是使用流行度,對節(jié)點(diǎn)狀態(tài)的刻畫則不盡相同,例如,文獻(xiàn)[32,33]將緩存容量作為研究節(jié)點(diǎn)狀態(tài)的主要參考因素,文獻(xiàn)[34,35]是將緩存節(jié)點(diǎn)與源節(jié)點(diǎn)之間的跳數(shù)作為節(jié)點(diǎn)的主要特性,其中,文獻(xiàn)[34]中的MAGIC(max-gain in-network caching)算法考慮的是跳數(shù)的減少率,而文獻(xiàn)[35]中的OPP(opportunistic on-path)算法計(jì)算的是緩存節(jié)點(diǎn)至源節(jié)點(diǎn)的跳數(shù)與路徑總跳數(shù)的比值,文獻(xiàn)[36,37]中的節(jié)點(diǎn)狀態(tài)主要是基于其在拓?fù)浣Y(jié)構(gòu)中的位置,文獻(xiàn)[38]考慮的則是節(jié)點(diǎn)的路徑跳數(shù)和緩存容量.這些算法雖然從不同角度綜合考慮了內(nèi)容數(shù)據(jù)與節(jié)點(diǎn)數(shù)據(jù),但是它們?nèi)狈W(wǎng)絡(luò)整體的視角,沒有從全網(wǎng)的角度深層次地挖掘和分析節(jié)點(diǎn)數(shù)據(jù)和內(nèi)容數(shù)據(jù)的關(guān)聯(lián)性,也沒有進(jìn)一步考慮不同時(shí)間階段,即不同概念間的相互影響關(guān)系.

上述成果為基于概念學(xué)習(xí)的緩存研究提供了基礎(chǔ).本文所提出的緩存機(jī)制與策略,在節(jié)點(diǎn)數(shù)據(jù)和內(nèi)容數(shù)據(jù)相互感知的基礎(chǔ)上,通過對不同環(huán)境下概念的挖掘與學(xué)習(xí),自適應(yīng)地實(shí)現(xiàn)在不同概念下的緩存匹配.

2 基于概念漂移學(xué)習(xí)的緩存策略

2.1 多維狀態(tài)屬性數(shù)據(jù)的定義

為了實(shí)現(xiàn)緩存內(nèi)容與網(wǎng)絡(luò)節(jié)點(diǎn)的匹配,將適當(dāng)?shù)膬?nèi)容部署在恰當(dāng)?shù)墓?jié)點(diǎn)上,緩存策略不僅需要考慮節(jié)點(diǎn)的當(dāng)前狀態(tài),還需要考慮內(nèi)容的當(dāng)前屬性.因此,緩存策略所需的數(shù)據(jù)應(yīng)是能描述節(jié)點(diǎn)特性和內(nèi)容屬性等內(nèi)容的多維數(shù)據(jù).本文從數(shù)據(jù)分析的角度出發(fā),按照以下兩個(gè)維度進(jìn)行數(shù)據(jù)提取[39].

(1) 在節(jié)點(diǎn)的維度上,計(jì)算節(jié)點(diǎn)的緩存率及緩存替換率;

(2) 在內(nèi)容的維度上,定義內(nèi)容在節(jié)點(diǎn)上的流行度及請求內(nèi)容權(quán)重,刻畫出內(nèi)容熱度與節(jié)點(diǎn)的相關(guān)性.

2.1.1 節(jié)點(diǎn)維度

不同位置的節(jié)點(diǎn)在不同的時(shí)期具有不同的訪問熱度,熱度的變化可以通過節(jié)點(diǎn)緩存負(fù)載的變化來描述.節(jié)點(diǎn)維度就是通過緩存率和緩存替換率來分別描述節(jié)點(diǎn)在不同時(shí)期的負(fù)載狀態(tài).

定義節(jié)點(diǎn)緩存率為CR:

其中,CCS(v)為節(jié)點(diǎn)v的緩存容量,CCSi則表示該節(jié)點(diǎn)在單位時(shí)間內(nèi)被緩存的第i個(gè)內(nèi)容的大小.緩存率可有效地描述輕載時(shí)的緩存負(fù)載率.

定義節(jié)點(diǎn)緩存替換率為RR:

其中,RCSi表示該節(jié)點(diǎn)在單位時(shí)間內(nèi)被替換的第i個(gè)內(nèi)容的大小.假設(shè)網(wǎng)絡(luò)進(jìn)入穩(wěn)定狀態(tài)后,大多數(shù)節(jié)點(diǎn)緩存空間被占滿,此時(shí),緩存替換率可以有效地描述節(jié)點(diǎn)的負(fù)載和緩存狀態(tài),并能反映出不同內(nèi)容在節(jié)點(diǎn)的時(shí)效性[40].節(jié)點(diǎn)緩存率與節(jié)點(diǎn)緩存替換率的結(jié)合構(gòu)成了對節(jié)點(diǎn)完整狀態(tài)的描述.

2.1.2 內(nèi)容維度

任何流行內(nèi)容在時(shí)間上都會(huì)經(jīng)歷上升期、流行高峰到最后衰減的動(dòng)態(tài)變化過程,而且內(nèi)容的流行程度也受到地域位置因素的影響,同一內(nèi)容在不同節(jié)點(diǎn)上的流行程度也不盡相同.內(nèi)容維度就是分析內(nèi)容流行程度與時(shí)間和空間的相關(guān)性,流行度描述了內(nèi)容的流行程度隨時(shí)間的動(dòng)態(tài)變化趨勢,本文提出的請求內(nèi)容權(quán)重則是在借鑒IDF(逆文檔頻率)概念[41]的基礎(chǔ)上分析內(nèi)容與節(jié)點(diǎn)的空間相關(guān)性.

定義節(jié)點(diǎn)內(nèi)容的流行度為LPvi:統(tǒng)計(jì)的是用戶對該節(jié)點(diǎn)的總請求量.

定義請求內(nèi)容權(quán)重為RWvi:

其中,IRNvi計(jì)算的是單位時(shí)間內(nèi)用戶在節(jié)點(diǎn)v上對內(nèi)容i的請求量,

其中,m(i)為請求內(nèi)容i的節(jié)點(diǎn)數(shù)量,m為節(jié)點(diǎn)總量.是關(guān)于節(jié)點(diǎn)集合范圍的全局因子,只關(guān)注節(jié)點(diǎn)數(shù)量,不關(guān)注具體的節(jié)點(diǎn).通過分析可知,當(dāng)較少的節(jié)點(diǎn)請求內(nèi)容i時(shí),權(quán)重值較大,表明節(jié)點(diǎn)v與內(nèi)容i有著較強(qiáng)的相關(guān)性,因此,利用該權(quán)重值可區(qū)分出不同內(nèi)容間的相對重要性.

2.2 匹配值的定義

內(nèi)容與節(jié)點(diǎn)是否匹配可建模為二分類問題,匹配值對應(yīng)的就是分類結(jié)果.

TF-IDF(詞頻-逆文檔頻率)[41]算法可以有效地評估一個(gè)詞對一個(gè)語料庫中一篇文檔的重要程度,而緩存黏度也用于評估內(nèi)容的重要性,因此在借鑒TF-IDF思想的基礎(chǔ)上,定義內(nèi)容的緩存黏度為CVvi:

定義匹配度的門限值TH,當(dāng)緩存黏度CVvi≥TH時(shí),表明當(dāng)前內(nèi)容與節(jié)點(diǎn)具有較高的匹配度,適宜緩存,則令匹配值為1;否則,令匹配值為?1.TH根據(jù)第1次采集到的緩存黏度集合的中位值來確定.采用中位值主要是為了避免極端緩存黏度值對匹配判斷的影響,并避免訓(xùn)練樣本分布不均勻?qū)е掠?xùn)練的不準(zhǔn)確.

2.3 訓(xùn)練集與測試集的定義

訓(xùn)練集與測試集的符號描述借鑒文獻(xiàn)[39]中的部分定義,其中,

定義數(shù)據(jù)集Avi=(a11,a12,…,avi)為t時(shí)刻的標(biāo)記數(shù)據(jù)集.為簡化數(shù)據(jù)集的表示方式,令A(yù)vi=Xl=(x1,x2,…,xl),其中,x1=a11.

定義數(shù)據(jù)集Yl=(y1,y2,…,yl)為類別標(biāo)記集合,其中,yq∈{1,?1},類別標(biāo)記與匹配值相對應(yīng),若標(biāo)記值yq=1,則意味著該節(jié)點(diǎn)與內(nèi)容匹配度較高,緩存;否則,不緩存.

定義測試數(shù)據(jù)集Xu=(xl+1,xl+2,…,xl+u)是時(shí)間序列t+Δt上需要計(jì)算的未標(biāo)記數(shù)據(jù)集,對應(yīng)的類別標(biāo)記集合定義為Yu=(yl+1,yl+2,…,yl+u).若計(jì)算結(jié)果為yu=1,則該節(jié)點(diǎn)上應(yīng)緩存當(dāng)前內(nèi)容;若yu=?1,則不緩存.

2.4 基于概念漂移學(xué)習(xí)的緩存算法

ICN網(wǎng)絡(luò)中存在著海量的數(shù)據(jù)包在高速傳輸,這些數(shù)據(jù)包構(gòu)成了一種典型的數(shù)據(jù)流應(yīng)用.由于網(wǎng)絡(luò)流的分布隨著網(wǎng)絡(luò)環(huán)境動(dòng)態(tài)變化,因而任何內(nèi)容在一定的空間區(qū)域內(nèi),其流行程度在時(shí)間維度上都會(huì)經(jīng)歷從上升、流行高峰到最后衰減的過程,這個(gè)過程的變化,即概念的變化,將對流量分布造成較大的影響,因此,本文提出一種面向不同概念進(jìn)行自適應(yīng)學(xué)習(xí)的方法來求解緩存匹配問題.

2.4.1 網(wǎng)絡(luò)概念漂移的識別算法

針對概念漂移的識別,很多研究主要是通過分析分類的準(zhǔn)確率來識別是否發(fā)生了概念漂移,但基于準(zhǔn)確率的判斷需要實(shí)時(shí)地對樣本類別進(jìn)行標(biāo)記.然而標(biāo)記樣本需要大量的時(shí)間和資源作為代價(jià),因此本文提出了一種基于熵值檢測的無標(biāo)記概念漂移識別算法.定義兩個(gè)由m×n個(gè)基窗口組成的滑動(dòng)窗口,一個(gè)記錄歷史數(shù)據(jù),一個(gè)記錄當(dāng)前數(shù)據(jù),通過滑動(dòng)窗口機(jī)制不斷比較兩個(gè)窗口的熵值來分析其差異,并根據(jù)差異性來識別是否發(fā)生漂移.其中,m是節(jié)點(diǎn)數(shù)量,n是流行度為前20%的內(nèi)容的數(shù)量(由于ICN中內(nèi)容的訪問次數(shù)與其流行度滿足Zipf-Like定律,流行度排名為前20%的訪問量約占網(wǎng)絡(luò)總訪問量的80%,因此以排名為前20%的流行內(nèi)容為研究對象),m×n個(gè)基窗口即是對當(dāng)前網(wǎng)絡(luò)環(huán)境下節(jié)點(diǎn)和內(nèi)容狀態(tài)屬性的較完整描述.

定義在時(shí)刻t,當(dāng)前數(shù)據(jù)窗口的形式化表達(dá)為NW=(x1,x2,…,xmn),如果未發(fā)生概念漂移,則該窗口中的狀態(tài)屬性數(shù)據(jù)將不斷地被更新,其中,mn=l.

定義在時(shí)刻t,歷史數(shù)據(jù)窗口的形式化表達(dá)為

定義j是屬性向量,即窗口xq中第j個(gè)元素,j∈{1,4},q∈{1,mn}.

定義b是元素的分支.將xq中每個(gè)元素的值都進(jìn)行歸一化處理,并將處理后仍位于[0,1]之外的數(shù)據(jù)賦值為0或者1,然后將1分為10等分,比較歸一化后的數(shù)值屬于哪個(gè)區(qū)間,對應(yīng)的區(qū)間值則為1.例如,當(dāng)前數(shù)據(jù)為0.32,則[0.3～0.4]區(qū)間的值為1.

定義窗口xq中元素j在分支b上出現(xiàn)的次數(shù)為rqjb:

定義窗口xq的元素j在分支b上的熵為Hqjb=?Pqjblog2(Pqjb),Pqjb=rqjb/mn,表示元素j在分支b上的概率.

定義窗口xq的熵為

定義前q個(gè)窗口的熵為

隨機(jī)變量R的M個(gè)獨(dú)立樣本的均值和真實(shí)平均值的誤差不超過ε的概率為1?δ,則:

Hoeffding邊界默認(rèn)δ=10?7,二分類問題的隨機(jī)變量R=log22=1,文中樣本數(shù)M為1 600,計(jì)算得到ε的值為0.07.

算法1描述了概念漂移的識別方法.算法實(shí)際上執(zhí)行的是q次獨(dú)立的運(yùn)算,每次運(yùn)算都圍繞一個(gè)三元組展開.OW是歷史數(shù)據(jù)窗口,記錄的是從檢測到概念漂移后開始的m×n個(gè)狀態(tài)屬性樣本.通過窗口的不斷向前滑動(dòng),檢測是否ΔH>ε:如果是,則識別出概念漂移,用依次到來的兩組數(shù)據(jù)分別更新OW和NM中的內(nèi)容,然后重復(fù)整個(gè)過程.

算法1.概念漂移識別算法.

2.4.2 基于集成學(xué)習(xí)的緩存算法

當(dāng)ICN的緩存環(huán)境發(fā)生概念漂移時(shí),根據(jù)先前概念訓(xùn)練的分類器對新樣本空間的適用性將逐步減弱,導(dǎo)致分類模型的分辨能力下降.因此,需要在漂移點(diǎn)引入對新概念的重新學(xué)習(xí),更新分類器.為了避免單一分類器在不同問題上泛化表現(xiàn)的不同,減少因分類器選擇不當(dāng)導(dǎo)致的泛化性能不佳的風(fēng)險(xiǎn),本文采用經(jīng)典的Adaboost(adaptive boosting)集成學(xué)習(xí)算法生成緩存匹配決策的集成分類器,通過對多種分類器的集成,提高了分類結(jié)果的準(zhǔn)確性.

集成學(xué)習(xí)的前提是:在檢測到漂移點(diǎn)后,需更新歷史數(shù)據(jù)窗口OW的內(nèi)容,還需要對OW的內(nèi)容進(jìn)行標(biāo)記,并生成訓(xùn)練集{(xq,yq),q=1,2,…,m×n}.Adaboost算法對訓(xùn)練集進(jìn)行迭代學(xué)習(xí),每次迭代生成的弱分類器的分類結(jié)果都與標(biāo)記進(jìn)行比較,然后根據(jù)降低分類正確樣本的權(quán)重,調(diào)高分類錯(cuò)誤樣本的權(quán)重的規(guī)則來更新樣本的分布,并將新樣本作為下一輪學(xué)習(xí)器的輸入進(jìn)行新的弱分類器的學(xué)習(xí),若干個(gè)弱分類器的加權(quán)組合就是最終的集成分類器.弱分類器選用線性分類器.用集成分類器對后續(xù)時(shí)間序列上的狀態(tài)屬性值Xu=(xm×n+1,xm×n+2,…,xm×n+u)進(jìn)行預(yù)測,即對不斷更新的當(dāng)前數(shù)據(jù)窗口NM中的數(shù)據(jù)進(jìn)行預(yù)測,預(yù)測結(jié)果Yu=(ym×n+1,ym×n+2,…,ym×n+u)就是對應(yīng)的緩存匹配值.

2.4.3 基于概念重現(xiàn)的緩存學(xué)習(xí)算法

集成分類算法可以在檢測到概念漂移時(shí)對分類器進(jìn)行動(dòng)態(tài)調(diào)整,以適應(yīng)新出現(xiàn)的概念,即適應(yīng)當(dāng)前的ICN網(wǎng)絡(luò)環(huán)境.但需注意的是:有時(shí),某些概念會(huì)在ICN網(wǎng)絡(luò)運(yùn)行中重復(fù)出現(xiàn).當(dāng)概念重現(xiàn)時(shí),如果能夠?qū)⑾嗤拍畹臍v史分類算法遷移到當(dāng)前的分類算法中,這將有效地減少分類器的學(xué)習(xí)代價(jià),提高分類的準(zhǔn)確率.

定義歷史樣本特征集合為HS={hs1,hs2,…,hsk},hsk中存儲的是當(dāng)?shù)趉次檢測到漂移點(diǎn)后的新的OW窗口中內(nèi)容對應(yīng)的標(biāo)記.

定義歷史樣本特征的哈希值集合為HHS={hhs1,hhs2,…,hhsk},hhk記錄的是對hs進(jìn)行β次哈希計(jì)算后得到的β個(gè)最小哈希值.

定義歷史概念集合為HC={hc1,hc2,…,hck}里面存儲的是每次概念漂移后由集成學(xué)習(xí)算法Adaboost生成的集成分類器,與HHS表相對應(yīng).

設(shè)漂移后根據(jù)Adaboost算法生成的分類器為hck+1,將其定義為主分類器mhc,為了將從歷史概念上學(xué)習(xí)到的知識遷移到當(dāng)前概念中,需從HC中選擇一個(gè)與當(dāng)前概念最為相似的概念作為輔助分類器.為從HC中選擇最相似的分類器,每次發(fā)現(xiàn)新概念后,都通過minhash[43]算法對當(dāng)前的hs進(jìn)行降維,使用β個(gè)哈希函數(shù)對hs求哈希值,得到β個(gè)最小哈希值hhs,并將hs和hhs分別存入歷史樣本特征集合HS和歷史樣本特征的哈希值集合HHS,然后基于LSH(局部敏感哈希)[44]算法,將已知的hhs中對應(yīng)的哈希值進(jìn)行聚類,將相似的哈希值聚集到一起,為后續(xù)的查找節(jié)約時(shí)間.計(jì)算當(dāng)前概念下樣本對應(yīng)β的個(gè)最小哈希值,并將當(dāng)前概念下生成的哈希值分別與相似集中的每一個(gè)hs生成的哈希值hhs行相似度比較,即計(jì)算最小哈希值相同元素的個(gè)數(shù)與總元素個(gè)數(shù)之間的比值τ,比值越大,越相似.選取相似度最大的hs對應(yīng)的hc作為輔助分類器ahc,則基于概念重現(xiàn)的分類學(xué)習(xí)算法的表達(dá)式為

其中,ω1和ω2分別為輔助分類器和主分類器的權(quán)重系數(shù).若相似度大于閾值,則令ω1=ω2=1/2,說明是概念的重現(xiàn),預(yù)測的結(jié)果將是主、輔分類器共同作用的結(jié)果.假設(shè)主分類器mhc的預(yù)測準(zhǔn)確率為δ,輔助分類器ahc的準(zhǔn)確率為?,顯然,f的準(zhǔn)確率是大于δ和?中的最大值,因而提高了算法的準(zhǔn)確率.若相似度小于閾值HTH,則令ω1=0,ω2=1,這說明是一個(gè)新生成的概念,并將該概念對應(yīng)的哈希值和分類器分別加入HHS和HC.詳細(xì)描述見算法2.

算法2.概念重現(xiàn)的分類學(xué)習(xí)算法.

算法執(zhí)行過程中,相似度閾值HTH由中位值計(jì)算確定.由于每次識別出漂移后都需從歷史概念集合中選擇一個(gè)與當(dāng)前概念最為相似的概念作為輔助分類器,即計(jì)算當(dāng)前概念與歷史概念的相似度,因此任意兩個(gè)歷史概念間都對應(yīng)有一個(gè)相似度值,從歷史相似度中取中位值,可有效避免極端相似度的影響,而且算法簡單.

2.5 緩存資源管理系統(tǒng)

緩存資源管理系統(tǒng)結(jié)構(gòu)如圖1所示:每一個(gè)路由節(jié)點(diǎn)通過對Data數(shù)據(jù)包的統(tǒng)計(jì)分析,可以計(jì)算出節(jié)點(diǎn)維度所需的原始參數(shù),如單位時(shí)間內(nèi)節(jié)點(diǎn)上被緩存的內(nèi)容數(shù)量或被替換的內(nèi)容數(shù)量;通過對Interest數(shù)據(jù)包的分析,可以獲得內(nèi)容維度計(jì)算所需的原始參數(shù),如單位時(shí)間內(nèi)對不同內(nèi)容的請求次數(shù),也可統(tǒng)計(jì)出對已緩存內(nèi)容的請求次數(shù).這些原始參數(shù)作為附加內(nèi)容,隨著Interest包轉(zhuǎn)發(fā)給緩存資源管理服務(wù)器節(jié)點(diǎn).為了便于對舊概念學(xué)習(xí)算法模型的快速調(diào)用,在資源管理服務(wù)器中定義了一張存儲歷史概念的表,表結(jié)構(gòu)見表1.該服務(wù)器節(jié)點(diǎn)通過對獲得的多維數(shù)據(jù)進(jìn)行挖掘、學(xué)習(xí),并將學(xué)習(xí)后的匹配結(jié)果通過Data數(shù)據(jù)包轉(zhuǎn)發(fā)到各個(gè)節(jié)點(diǎn)上,各節(jié)點(diǎn)根據(jù)匹配關(guān)系緩存相應(yīng)的內(nèi)容,實(shí)現(xiàn)緩存內(nèi)容的差異化.

Fig.1 Resource management system architecture圖1 緩存資源管理系統(tǒng)結(jié)構(gòu)

Table 1 Table for storing historical concepts表1 存儲歷史概念的表結(jié)構(gòu)

2.6 基于概念漂移學(xué)習(xí)的緩存策略描述

緩存策略的基本思想就是:通過對感知獲得的關(guān)于節(jié)點(diǎn)和內(nèi)容的歷史數(shù)據(jù),如緩存率、替換率、內(nèi)容流行度、請求內(nèi)容權(quán)重等狀態(tài)特征進(jìn)行分析挖掘,并利用挖掘出的狀態(tài)特征與緩存匹配值之間的函數(shù)映射關(guān)系,對未來時(shí)期內(nèi)的節(jié)點(diǎn)與內(nèi)容間的匹配關(guān)系進(jìn)行預(yù)測.預(yù)測方法整體流程描述如下.

首先,采用高斯方法對多維狀態(tài)屬性的歷史數(shù)據(jù)進(jìn)行歸一化處理,以避免因?yàn)槎嗑S數(shù)據(jù)取值范圍的不同對特征挖掘可能造成的影響.具體步驟如下.

· 然后,將歸一后仍位于[0,1]之外的數(shù)據(jù)賦值為0或者1,公式如下:

在歸一化處理的基礎(chǔ)上,確定各屬性值屬于的分支區(qū)間.

然后,采用自適應(yīng)的概念重現(xiàn)學(xué)習(xí)算法,利用多維狀態(tài)屬性值與緩存匹配值之間的函數(shù)映射關(guān)系,預(yù)測未來時(shí)期的對應(yīng)關(guān)系,具體描述如算法3所示.

· 第1行、第2行是算法的初始化階段;

· 第3行～第9行是當(dāng)概念發(fā)生漂移后,分類算法對OW中的狀態(tài)屬性值所定義的概念的學(xué)習(xí)過程,包含對重現(xiàn)概念的遷移學(xué)習(xí);

· 第10行～第36行是對隨后到來的NW窗口中數(shù)據(jù)的處理過程,其中,

? 第10行～第17行描述的是利用OW窗口中學(xué)習(xí)到的概念對NW窗口中數(shù)據(jù)的關(guān)系進(jìn)行預(yù)測,即預(yù)測節(jié)點(diǎn)與內(nèi)容的匹配關(guān)系;

? 第18行～第23行描述的是與預(yù)測同時(shí)進(jìn)行的概念漂移的識別過程,其中,行18描述的是漂移識別的算法,行19描述的是當(dāng)識別到概念漂移后進(jìn)行重新學(xué)習(xí)的過程;

? 第20行～第30行描述的是當(dāng)服務(wù)器在進(jìn)行重學(xué)習(xí)時(shí),內(nèi)容與節(jié)點(diǎn)的匹配關(guān)系仍然按照漂移前的算法進(jìn)行計(jì)算;

? 第31行則說明:當(dāng)重學(xué)習(xí)過程結(jié)束時(shí),將立即采用新的學(xué)習(xí)算法預(yù)測后續(xù)內(nèi)容與節(jié)點(diǎn)的匹配關(guān)系;

? 第32行、第33行描述的是若未識別到概念漂移的處理動(dòng)作:若未識別到概念漂移,則繼續(xù)采用當(dāng)前分類算法進(jìn)行學(xué)習(xí),如第32行所示;若對NW窗口中所有數(shù)據(jù)都已識別完成,仍未有漂移產(chǎn)生,則重新更新NW窗口中的數(shù)據(jù),再進(jìn)行學(xué)習(xí)和識別,如第33行所示.

算法3.自適應(yīng)的概念學(xué)習(xí)算法.

3 仿真實(shí)驗(yàn)與分析

3.1 評價(jià)指標(biāo)

緩存是ICN網(wǎng)絡(luò)的重要特性之一,其目的主要是為了降低網(wǎng)絡(luò)運(yùn)行成本和提高用戶的體驗(yàn)質(zhì)量,使用戶能快速就近獲取內(nèi)容.為量化上述緩存目標(biāo),針對網(wǎng)絡(luò)和用戶分別引入不同的評價(jià)指標(biāo).在分析網(wǎng)絡(luò)運(yùn)行成本時(shí),定義了網(wǎng)絡(luò)鏈路平均利用率(所有鏈路單位時(shí)間利用率的平均值)、服務(wù)器負(fù)載率(網(wǎng)絡(luò)中所有服務(wù)器單位時(shí)間接收的請求次數(shù)與用戶發(fā)出的請求總次數(shù)的比值)、緩存替換數(shù)(單位時(shí)間內(nèi)所有節(jié)點(diǎn)替換內(nèi)容數(shù)量的均值)、節(jié)點(diǎn)負(fù)載的Gini系數(shù)[45](節(jié)點(diǎn)負(fù)載指的是節(jié)點(diǎn)上所有被緩存內(nèi)容的總訪問量,Gini系數(shù)定義為所有節(jié)點(diǎn)間負(fù)載的差值之和與負(fù)載均值之比再除以節(jié)點(diǎn)數(shù)量平方值的2倍);在分析用戶體驗(yàn)質(zhì)量時(shí),定義了訪問緩存命中率(興趣包被緩存響應(yīng)的數(shù)量與用戶發(fā)送的興趣包數(shù)量的比值)、訪問延時(shí)(從發(fā)出興趣包至接收到對應(yīng)的數(shù)據(jù)包所需要的時(shí)間)、訪問跳數(shù)減少率(利用緩存算法獲得所需內(nèi)容而經(jīng)過的跳數(shù)與到服務(wù)器端獲取內(nèi)容的跳數(shù)相比而減少的比值)、內(nèi)容差異率(節(jié)點(diǎn)緩存的內(nèi)容種類數(shù)量與網(wǎng)絡(luò)中服務(wù)器所產(chǎn)生的所有內(nèi)容數(shù)量的比值)等指標(biāo).在實(shí)驗(yàn)過程中,又分別分析了緩存容量及用戶請求速率對網(wǎng)絡(luò)運(yùn)行成本及用戶體驗(yàn)質(zhì)量的影響.

在CDL算法性能評價(jià)方面,針對算法的準(zhǔn)確率,定義了誤報(bào)率(真實(shí)值為?1,而預(yù)測值為1的概率)和漏報(bào)率(真實(shí)值為1,而預(yù)測值為?1的概率)這兩個(gè)評價(jià)指標(biāo).

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

本文的仿真實(shí)驗(yàn)采用真實(shí)的域間拓?fù)浣Y(jié)構(gòu)AS-1755,假設(shè)內(nèi)容請求到達(dá)過程服從泊松分布,用戶對內(nèi)容的請求模式遵循Zipf分布.用戶的平均請求速率為100個(gè)興趣包/s,Zipf參數(shù)設(shè)為0.7.網(wǎng)絡(luò)中的內(nèi)容數(shù)量共有71 000個(gè).每個(gè)內(nèi)容緩存時(shí)需要占用一個(gè)緩存單位,網(wǎng)內(nèi)緩存總?cè)萘糠秶鸀?.25GB～1.5GB.實(shí)驗(yàn)初始時(shí),每個(gè)節(jié)點(diǎn)的緩存內(nèi)容量為0.本文將CDL策略與CEE策略[15]、LCD策略[16]、prob0.5策略[22]和OPP[35]策略的性能進(jìn)行對比分析.針對OPP策略,由于其考慮了內(nèi)容流行度因素但沒有考慮概念漂移對流行度的影響,因此本文分析了兩種場景下OPP策略的緩存效果:場景1是流行度的統(tǒng)計(jì)時(shí)間包含了概念漂移前與漂移后的兩段時(shí)間,實(shí)驗(yàn)結(jié)果在圖中用符號OPPNC表示;場景2是流行度的計(jì)算只基于概念漂移后的數(shù)據(jù)進(jìn)行統(tǒng)計(jì),實(shí)驗(yàn)結(jié)果用符號OPPC表示.

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

1.對網(wǎng)絡(luò)運(yùn)行成本的影響

· 性能指標(biāo)參數(shù)隨緩存容量的變化情況

圖2為6種緩存策略的網(wǎng)絡(luò)鏈路平均利用率隨緩存容量的變化情況.可以看出,鏈路利用率隨著緩存容量的增加而減小.這是因?yàn)殡S著緩存容量的增大,可緩存內(nèi)容的數(shù)量也隨即增多,用戶可在中間緩存節(jié)點(diǎn)獲取所需內(nèi)容的概率增大,減少了緩存節(jié)點(diǎn)到服務(wù)器節(jié)點(diǎn)間鏈路的流量,因此鏈路平均利用率降低.進(jìn)一步分析發(fā)現(xiàn),CDL的性能優(yōu)于其他5種.例如:當(dāng)容量為1GB時(shí),CDL與LCD相比,鏈路平均利用率降低了約10%,與OPPC相比降低了約2%.產(chǎn)生這一結(jié)果的原因是:CEE,LCD和prob0.5在節(jié)點(diǎn)中緩存內(nèi)容時(shí)并沒有考慮節(jié)點(diǎn)緩存容量和轉(zhuǎn)發(fā)差異性等因素,只是較盲目地進(jìn)行緩存,當(dāng)緩存的內(nèi)容不能滿足用戶需求時(shí),用戶仍然需要向服務(wù)器發(fā)出請求.在這三者中,CEE由于在節(jié)點(diǎn)上緩存所有內(nèi)容,網(wǎng)絡(luò)中緩存的內(nèi)容量最大,用戶從中間節(jié)點(diǎn)讀取內(nèi)容的概率最高,因此鏈路平均利用率優(yōu)于另兩種策略.OPPNC與OPPC均考慮了內(nèi)容流行度與節(jié)點(diǎn)位置的匹配關(guān)系,但由于在計(jì)算內(nèi)容流行度的過程中,OPPNC沒有主動(dòng)消弭概念漂移前的數(shù)據(jù)對流行度計(jì)算產(chǎn)生不良影響的手段,因此,OPPNC對流行度的評估不如OPPC的準(zhǔn)確,最終導(dǎo)致對鏈路平均利用率的優(yōu)化效果不如OPPC.而CDL通過不斷捕捉網(wǎng)絡(luò)概念的漂移,并從漂移點(diǎn)進(jìn)行新概念的學(xué)習(xí),然后利用學(xué)習(xí)的結(jié)果確定內(nèi)容與節(jié)點(diǎn)的匹配關(guān)系,同OPPC策略相比,其對內(nèi)容與節(jié)點(diǎn)的匹配關(guān)系的預(yù)測及評估更加準(zhǔn)確,因此鏈路平均利用率的優(yōu)化效果更佳.

圖3為6種緩存策略下服務(wù)器負(fù)載率隨緩存容量的變化情況.可以看出,服務(wù)器負(fù)載率均隨著緩存容量的增大而減少.這是因?yàn)?隨著緩存容量的增大,節(jié)點(diǎn)上緩存內(nèi)容的總量隨即增多,滿足用戶請求的概率相應(yīng)增大,用戶到服務(wù)器直接請求內(nèi)容的概率相應(yīng)減少.當(dāng)容量為1GB時(shí),CDL與LCD相比,服務(wù)器負(fù)載率降低了約10%,與OPPC相比降低了約2%.

Fig.2 Average link utilization ratio圖2 網(wǎng)絡(luò)鏈路平均利用率

Fig.3 Server load ratio圖3 服務(wù)器負(fù)載率

圖4為6種緩存策略下緩存替換數(shù)隨緩存容量的變化情況.可以看出,緩存替換數(shù)均隨著緩存容量的增大而減少.進(jìn)一步分析可知:CEE策略中被替換的內(nèi)容數(shù)量最多,prob0.5策略替換數(shù)量最少.這是因?yàn)镃EE策略的泛在緩存,節(jié)點(diǎn)緩存了大量的冗余內(nèi)容,有效緩存容量最少,新內(nèi)容的緩存將產(chǎn)生較多的替換操作,因此替換數(shù)量最多;prob0.5策略基于概率緩存,緩存內(nèi)容總量最少,有效緩存容量相對較多,因此當(dāng)有內(nèi)容緩存時(shí),需要替換的數(shù)量最少.CDL策略通過內(nèi)容與節(jié)點(diǎn)的匹配計(jì)算,有效地減少了緩存替換數(shù)量,因此由緩存替換導(dǎo)致的節(jié)點(diǎn)存儲操作開銷也較少.

圖5為6種緩存策略下節(jié)點(diǎn)負(fù)載Gini系數(shù)隨緩存容量的變化情況.負(fù)載的Gini系數(shù)是一個(gè)用于衡量概率分布不均勻程度的測度,系數(shù)越小,說明均衡性越好.從圖中可知,CDL的Gini系數(shù)最小.這是因?yàn)樵趦?nèi)容維度中定義了請求內(nèi)容權(quán)重,該權(quán)重與請求節(jié)點(diǎn)集合密切相關(guān);而在內(nèi)容的緩存黏度的定義中也引入了緩存節(jié)點(diǎn)集合這一參數(shù),因此CDL策略不僅只是局限于追求某個(gè)內(nèi)容與節(jié)點(diǎn)的緩存匹配效果,還兼顧了節(jié)點(diǎn)集合的整體訴求,將內(nèi)容較均衡地分配給緩存節(jié)點(diǎn),網(wǎng)絡(luò)流量則被較均衡地引導(dǎo)到緩存節(jié)點(diǎn)上,降低了網(wǎng)絡(luò)擁塞節(jié)點(diǎn)出現(xiàn)的概率,可有效減少網(wǎng)絡(luò)運(yùn)行的維護(hù)成本.

Fig.4 Cache replacement number圖4 緩存替換數(shù)

Fig.5 Node load coefficient圖5 節(jié)點(diǎn)負(fù)載系數(shù)

· 性能指標(biāo)參數(shù)隨用戶請求速率的變化情況

圖6～圖9分別為6種緩存策略下網(wǎng)絡(luò)鏈路平均利用率、服務(wù)器負(fù)載率、緩存替換數(shù)、節(jié)點(diǎn)負(fù)載Gini系數(shù)隨用戶請求速率的變化趨勢.此時(shí),緩存容量為1GB,速率的變化范圍是每個(gè)請求節(jié)點(diǎn)每秒發(fā)送50～250個(gè)請求.從圖中可以看出:隨著用戶請求速率的增長,這6種策略在鏈路平均利用率、服務(wù)器負(fù)載率、緩存替換數(shù)、節(jié)點(diǎn)負(fù)載系數(shù)等方面沒有明顯變化,但是CDL策略的指標(biāo)優(yōu)于其余5種策略.

Fig.6 Average link utilization ratio圖6 網(wǎng)絡(luò)鏈路平均利用率

Fig.7 Server load ratio圖7 服務(wù)器負(fù)載率

Fig.8 Cache replacement number圖8 緩存替換數(shù)

Fig.9 Node load coefficient圖9 節(jié)點(diǎn)負(fù)載系數(shù)

2.對用戶體驗(yàn)質(zhì)量的影響

· 性能指標(biāo)參數(shù)隨緩存容量的變化情況

圖10為6種緩存策略下命中率隨緩存容量的變化情況.可以看出,命中率均隨著緩存容量的增大而增加.這是因?yàn)殡S著緩存容量的增大,中間路由器節(jié)點(diǎn)為用戶提供的可訪問內(nèi)容相應(yīng)增加,從而緩存命中率提升.進(jìn)一步分析表明,CDL的性能優(yōu)于其他5種.例如:當(dāng)容量為1GB時(shí),CDL與LCD相比,命中率提升了約20%,與OPP相比提高了約3%.產(chǎn)生這一結(jié)果的原因是:CEE,LCD和prob0.5對內(nèi)容的重復(fù)冗余緩存導(dǎo)致節(jié)點(diǎn)緩存內(nèi)容頻繁更新,影響了命中率;OPP增加了流行度高的內(nèi)容在靠近用戶節(jié)點(diǎn)處的緩存概率,提高了網(wǎng)內(nèi)緩存命中率;CDL在時(shí)間上分析了網(wǎng)絡(luò)的當(dāng)前概念,然后在空間上把內(nèi)容合理地分布在網(wǎng)絡(luò)中不同的節(jié)點(diǎn)上,因而更有效地提高了網(wǎng)內(nèi)緩存命中率.

圖11為6種緩存策略下,訪問跳數(shù)減少率隨緩存容量的變化情況.可以看出,訪問跳數(shù)減少率均隨緩存容量的增大而增加.當(dāng)容量為1GB時(shí),CDL與LCD相比,訪問跳數(shù)減少率降低了約30%,與OPP相比降低了約2%.這是因?yàn)殡S緩存命中率的增加,用戶易從更近的節(jié)點(diǎn)獲取所需內(nèi)容,訪問跳數(shù)減少,從而訪問跳數(shù)減少率降低.

Fig.10 Cache ratio圖10 命中率

Fig.11 Hop reduction ratio圖11 跳數(shù)減少率

圖12為6種緩存策略下,訪問延時(shí)隨緩存容量的變化情況.隨著用戶獲取所需內(nèi)容跳數(shù)的減少,訪問延時(shí)均減少.當(dāng)容量為1GB時(shí),CDL與LCD相比,訪問延時(shí)降低了約40%,與OPP相比降低了約2%.

· 性能指標(biāo)參數(shù)隨用戶請求速率的變化情況

圖13～圖15分別為6種緩存策略下命中率、跳數(shù)減少率、訪問延時(shí)隨用戶請求速率的變化趨勢.此時(shí),緩存容量為1GB,速率的變化范圍是每個(gè)請求節(jié)點(diǎn)每秒發(fā)送50～250個(gè)請求.從圖中可以看出:隨著用戶請求速率的增長,這6種策略在命中率、跳數(shù)減少率、訪問延時(shí)等方面沒有明顯變化,但是CDL策略的指標(biāo)優(yōu)于其余5種策略.

Fig.12 Delay圖12 訪問延時(shí)

Fig.13 Cache ratio圖13 命中率

Fig.14 Hop reduction ratio圖14 跳數(shù)減少率

Fig.15 Delay圖15 訪問延時(shí)

圖16是內(nèi)容差異率的情況,橫坐標(biāo)表示的是緩存內(nèi)容的類別數(shù)量與內(nèi)容類別總量比值的累積分布,縱坐標(biāo)表示的是節(jié)點(diǎn)的數(shù)量占總節(jié)點(diǎn)的比例.圖16(a)描述的是當(dāng)緩存容量為0.75時(shí),在不同的緩存策略下,內(nèi)容差異率分布的變化趨勢.CDL下內(nèi)容差異率小于25%的節(jié)點(diǎn)數(shù)量約占30%,差異率小于50%的節(jié)點(diǎn)數(shù)約為80%,幾乎所有節(jié)點(diǎn)的差異率均小于75%.圖16(b)描述的是在CDL下,內(nèi)容差異率分布的變化趨勢與緩存容量間的關(guān)系.當(dāng)緩存容量大于0.75GB時(shí),CDL的內(nèi)容差異率分布的變化趨勢大體相同,這是因?yàn)楣?jié)點(diǎn)能夠提供足夠的空間緩存匹配的內(nèi)容,特定的節(jié)點(diǎn)緩存特定的內(nèi)容,不需要其他節(jié)點(diǎn)的協(xié)作;而當(dāng)緩存容量為0.25GB時(shí),一些節(jié)點(diǎn)的緩存容量不足以提供滿足內(nèi)容存儲的空間,需要緩存在其他節(jié)點(diǎn),因此內(nèi)容差異率小于25%的節(jié)點(diǎn)數(shù)量約占15%,差異率小于50%的節(jié)點(diǎn)數(shù)約為40%.

Fig.16 Content diversity ratio圖16 內(nèi)容差異率

3.算法準(zhǔn)確率分析

CDL算法的誤報(bào)率和漏報(bào)率的結(jié)果見表2.

Table 2 False positive rate and false negative rate of CDL algorithm表2 CDL算法的誤報(bào)率和漏報(bào)率

從表2中可以看出:緩存容量的增長并未對誤報(bào)率產(chǎn)生明顯的影響,而只是漏報(bào)率產(chǎn)生了小幅提升.這是因?yàn)?由緩存黏度值的定義可知,黏度值與節(jié)點(diǎn)上被緩存內(nèi)容的訪問量成正比.隨著緩存容量的增加,緩存替換數(shù)量減少,這就意味著節(jié)點(diǎn)上的某個(gè)內(nèi)容在被替換前可以被多次訪問,訪問量增加,因此黏度值相應(yīng)地增加,緩存匹配門限值變大,因此漏報(bào)率增加;但同時(shí),黏度值又與總訪問量成反比,當(dāng)某一內(nèi)容的訪問量增加時(shí),總訪問量也相應(yīng)增加,因此黏度的增長又受到總訪問量的制約,門限值的增長幅度受到限制,漏報(bào)率增長并不十分明顯.

4 結(jié)束語

如何將恰當(dāng)?shù)膬?nèi)容部署在合適的節(jié)點(diǎn)上從而提高ICN緩存資源利用率,已經(jīng)成為ICN緩存管理的研究重點(diǎn)之一.本文提出了一種基于概念漂移學(xué)習(xí)的緩存策略,在對節(jié)點(diǎn)和內(nèi)容等多維狀態(tài)屬性值和緩存匹配值的歷史數(shù)據(jù)學(xué)習(xí)的基礎(chǔ)上,預(yù)測未來時(shí)期內(nèi)的節(jié)點(diǎn)與內(nèi)容間的關(guān)系.特別地,本文提出了概念漂移識別算法和基于概念重現(xiàn)的緩存算法,使內(nèi)容能夠根據(jù)當(dāng)前網(wǎng)絡(luò)環(huán)境對應(yīng)的概念自適應(yīng)地匹配到節(jié)點(diǎn)上.仿真實(shí)驗(yàn)結(jié)果表明:該策略不僅改善了用戶體驗(yàn)質(zhì)量,而且降低了網(wǎng)絡(luò)運(yùn)行成本.

未來研究工作的重點(diǎn)擬基于軟件定義網(wǎng)絡(luò)的設(shè)計(jì)思想,通過進(jìn)一步感知網(wǎng)絡(luò)實(shí)時(shí)狀態(tài)信息,在控制層挖掘出節(jié)點(diǎn)與內(nèi)容的黏度關(guān)系,確定出是否需要緩存,進(jìn)而在數(shù)據(jù)層執(zhí)行這一決策,從而進(jìn)一步改善ICN性能.