一種基于兩級(jí)緩存的協(xié)同緩存機(jī)制?

劉嘉琦,張亞文,張瀚文,孟緒穎,周繼華,張玉軍

1(中國(guó)科學(xué)院 計(jì)算技術(shù)研究所,北京 10019 0)

2(中國(guó)科學(xué)院大學(xué),北京 10 0190)

3(金美通信,重慶 400030)

現(xiàn)行的以TCP/IP 為基礎(chǔ)的互聯(lián)網(wǎng)體系結(jié)構(gòu)設(shè)計(jì)之初是為了解決計(jì)算機(jī)間點(diǎn)對(duì)點(diǎn)的通信需求,然而隨著互聯(lián)網(wǎng)規(guī)模和業(yè)務(wù)類(lèi)型的爆炸式增長(zhǎng),互聯(lián)網(wǎng)出現(xiàn)了許多新的問(wèn)題,內(nèi)容的高效傳輸、移動(dòng)性和安全性等問(wèn)題亟待解決[1].互聯(lián)網(wǎng)的主流應(yīng)用模式逐漸轉(zhuǎn)變?yōu)橐砸曨l分發(fā)、文件下載為代表的信息獲取服務(wù)[2].為了有效解決以IP 為中心的網(wǎng)絡(luò)體系架構(gòu)在新時(shí)代下所存在的各種問(wèn)題,近年來(lái),一些以信息為中心的互聯(lián)網(wǎng)體系架構(gòu)被提出,這種架構(gòu)即為信息中心網(wǎng)絡(luò)(information-centric networking,簡(jiǎn)稱(chēng)ICN)[3].

ICN 的本質(zhì)是要將網(wǎng)絡(luò)通信模式從當(dāng)前的以位置為中心轉(zhuǎn)變?yōu)橐孕畔橹行?即實(shí)現(xiàn)位置(服務(wù)器/主機(jī)的IP 地址)到內(nèi)容(用戶(hù)/應(yīng)用關(guān)心的信息)的轉(zhuǎn)變.這就要求ICN 中的節(jié)點(diǎn)擁有一定的緩存能力,使得用戶(hù)需要獲取信息時(shí),不再向信息源所在的主機(jī)地址進(jìn)行請(qǐng)求,而是直接基于內(nèi)容標(biāo)識(shí)向網(wǎng)絡(luò)發(fā)起請(qǐng)求.在ICN 中,緩存呈現(xiàn)泛在化的新特性,網(wǎng)絡(luò)內(nèi)任意節(jié)點(diǎn)具有緩存能力,以此來(lái)緩和服務(wù)器的壓力,減少網(wǎng)絡(luò)中的流量,降低用戶(hù)的訪(fǎng)問(wèn)延遲.

緩存策略是實(shí)現(xiàn)ICN 網(wǎng)絡(luò)潛在優(yōu)勢(shì)的關(guān)鍵技術(shù),得到了學(xué)術(shù)界的廣泛關(guān)注.然而,針對(duì)如何有效利用緩存資源、提升網(wǎng)絡(luò)性能的問(wèn)題,目前并未達(dá)成廣泛共識(shí)[4].Psaras[5]和Dabirmoghaddam[6]等人認(rèn)為:應(yīng)盡量將內(nèi)容緩存在網(wǎng)絡(luò)邊緣位置,以靠近用戶(hù)降低訪(fǎng)問(wèn)延遲.Rossi 等人[7]則認(rèn)為:只有將內(nèi)容緩存在網(wǎng)絡(luò)中心,才能保證單位緩存的復(fù)用效率,提高網(wǎng)絡(luò)緩存的利用率.Wang[4],Li[8]等人主張通過(guò)顯示協(xié)作方式增加緩存多樣性,提升緩存整體效用.而Zhang[2],Gill[9]等人則認(rèn)為:顯示協(xié)作方式需要頻繁地交換信息與計(jì)算開(kāi)銷(xiāo),這將給以線(xiàn)性速度為要求的高速信息中心網(wǎng)絡(luò)帶來(lái)了新的性能瓶頸.當(dāng)前,對(duì)ICN 網(wǎng)絡(luò)化緩存的研究還處于起步階段,現(xiàn)有各種方案大都只側(cè)重某單一方面的性能提升.各緩存策略在緩存內(nèi)容的多樣性和可用性等方面仍有很大的提升空間.

許多研究表明:網(wǎng)絡(luò)中內(nèi)容的熱度服從Zipf 分布[10],多數(shù)請(qǐng)求往往只集中在少數(shù)熱門(mén)內(nèi)容上,請(qǐng)求最多的內(nèi)容稱(chēng)為最熱門(mén)內(nèi)容,其次是次熱門(mén)內(nèi)容,剩余長(zhǎng)尾熱度的內(nèi)容為非熱門(mén)內(nèi)容.通過(guò)前期大量的仿真實(shí)驗(yàn),我們發(fā)現(xiàn):現(xiàn)有各種方案在達(dá)到穩(wěn)態(tài)時(shí),緩存空間仍被大量非熱門(mén)內(nèi)容占據(jù),已緩存的內(nèi)容往往是最熱門(mén)內(nèi)容,次熱門(mén)內(nèi)容難以穩(wěn)定緩存,緩存的利用率仍比較低.為提高緩存的利用率,我們希望能夠盡可能合理利用緩存空間,穩(wěn)定緩存更多次熱門(mén)內(nèi)容;同時(shí),為了降低延遲,最熱門(mén)內(nèi)容也應(yīng)適度冗余.通過(guò)對(duì)仿真實(shí)驗(yàn)結(jié)果的比對(duì)與分析,我們發(fā)現(xiàn):理想狀態(tài)下,最熱門(mén)內(nèi)容應(yīng)適度冗余在網(wǎng)絡(luò)邊緣節(jié)點(diǎn),次熱門(mén)內(nèi)容穩(wěn)定緩存并呈現(xiàn)多樣性.

針對(duì)現(xiàn)有ICN 網(wǎng)絡(luò)化緩存利用率較低和緩存位置缺乏合理規(guī)劃的問(wèn)題,本文提出了一種基于兩級(jí)緩存的協(xié)同緩存機(jī)制(a cache coordination scheme based on two-level cache,簡(jiǎn)稱(chēng)CSTC).主要貢獻(xiàn)包括:

1)提出一種分級(jí)緩存框架,將每個(gè)節(jié)點(diǎn)的緩存空間分為RawCache 和HashCache 兩部分:針對(duì)RawCache,各節(jié)點(diǎn)基于本地?zé)岫雀兄M(jìn)行獨(dú)立緩存決策;針對(duì)HashCache,通過(guò)哈希機(jī)制構(gòu)成域內(nèi)多節(jié)點(diǎn)間協(xié)作,實(shí)現(xiàn)了域內(nèi)熱度的分布感知及決策,為不同層次的熱度內(nèi)容提供不同的緩存策略;

2)在此框架下,提出了熱度篩選機(jī)制與路由策略,以實(shí)現(xiàn)緩存協(xié)作.基于內(nèi)容熱度優(yōu)化了緩存位置,降低了緩存的冗余,增大了域內(nèi)穩(wěn)定緩存內(nèi)容的數(shù)量,從而提高緩存命中率,降低用戶(hù)請(qǐng)求響應(yīng)時(shí)間;

3)通過(guò)仿真實(shí)驗(yàn)與現(xiàn)有5 種主要的ICN 緩存策略進(jìn)行了性能比較,并進(jìn)一步分析了內(nèi)容熱度分布、緩存大小等因素對(duì)各緩存策略性能的影響.實(shí)驗(yàn)結(jié)果表明:CSTC 將次熱門(mén)內(nèi)容緩存數(shù)量提升了2 倍;緩存內(nèi)容數(shù)量的增加及緩存位置的優(yōu)化使得命中率大幅提升,在緩存空間有限的情況下,即使與以高命中率為優(yōu)勢(shì)的哈希緩存策略相比,CSTC 最高可將命中率提升45.4%;同時(shí),CSTC 有效降低了用戶(hù)請(qǐng)求的響應(yīng)時(shí)間,多數(shù)情況下,平均請(qǐng)求響應(yīng)往返跳數(shù)優(yōu)于現(xiàn)有主要的5 種緩存策略.

本文第1 節(jié)對(duì)相關(guān)研究工作進(jìn)行介紹,并分析了現(xiàn)有ICN 緩存策略的問(wèn)題所在.第2 節(jié)詳細(xì)介紹基于兩級(jí)緩存的協(xié)同緩存機(jī)制的運(yùn)行過(guò)程.第3 節(jié)通過(guò)仿真實(shí)驗(yàn),從緩存分布、請(qǐng)求命中率等方面對(duì)方案進(jìn)行定量評(píng)價(jià).最后總結(jié)全文.

1 相關(guān)工作及問(wèn)題分析

緩存策略作為ICN 的重點(diǎn)研究領(lǐng)域,受到學(xué)術(shù)界的廣泛關(guān)注.近年來(lái),各種各樣的緩存策略被相繼提出.根據(jù)不同的分類(lèi)側(cè)重點(diǎn),可以將緩存策略分為不同的種類(lèi)[11].例如:根據(jù)內(nèi)容緩存位置,可以將其分為On-path 緩存策略和Off-path 緩存策略;根據(jù)各節(jié)點(diǎn)協(xié)作關(guān)系,可以將其分為顯式協(xié)同緩存策略和隱式協(xié)同緩存策略;根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)是否都具備緩存能力,可以將其分為同構(gòu)緩存策略和異構(gòu)緩存策略.本節(jié)主要就On-path 緩存策略、基于哈希的緩存策略和混合緩存策略展開(kāi)討論.

1.1 On-path緩存策略

在On-path 緩存策略中,請(qǐng)求內(nèi)容沿返回路徑緩存,而不會(huì)緩存到這條路徑之外的其他節(jié)點(diǎn).這類(lèi)緩存策略簡(jiǎn)單易實(shí)現(xiàn),也在實(shí)際部署中被廣泛采用.LCE(leave copy everywhere)[12]緩存策略是一種典型的On-path 緩存策略,在該策略中,各節(jié)點(diǎn)無(wú)差別地緩存途經(jīng)的所有內(nèi)容.LCE 雖然易于實(shí)現(xiàn),卻不可避免地造成緩存內(nèi)容的大量冗余,緩存空間的浪費(fèi).

Prob(copy with probabi lity)和ProbCache[5]提出了路徑上的節(jié)點(diǎn)按概率緩存內(nèi)容的方法,優(yōu)化On-path 緩存策略.前者指每個(gè)沿途節(jié)點(diǎn)都以某一固定概率緩存內(nèi)容:一方面,每個(gè)節(jié)點(diǎn)雖然以相同概率對(duì)內(nèi)容進(jìn)行緩存,但其隨機(jī)緩存的內(nèi)容卻不一樣,提高了緩存的多樣性;另一方面,某一內(nèi)容越熱門(mén),則其被緩存的概率越大.后者是Psaras 等人提出的一種基于加權(quán)概率的緩存策略,在這種策略下,越靠近請(qǐng)求者的節(jié)點(diǎn)、緩存空間越大的節(jié)點(diǎn),緩存該內(nèi)容的概率越大.該方法不僅降低了緩存的冗余,還提升了共享路徑節(jié)點(diǎn)的效用.

為了有效降低緩存冗余,提高緩存空間利用率,有人[7,9,13,14]開(kāi)始倡導(dǎo)將內(nèi)容緩存在請(qǐng)求路徑上權(quán)重最高的一個(gè)節(jié)點(diǎn)上來(lái)降低緩存冗余,他們對(duì)于節(jié)點(diǎn)權(quán)重的定義各不相同.Rossi 等人[7]研究了各種基于網(wǎng)絡(luò)拓?fù)渲行亩鹊木彺娌呗?并得出,將內(nèi)容緩存至中心度數(shù)最大的節(jié)點(diǎn)處緩存效果相對(duì)較好.Xu 等人[13]設(shè)計(jì)了基于動(dòng)態(tài)LRU隊(duì)列和基于布隆過(guò)濾器兩種內(nèi)容效用統(tǒng)計(jì)方法,將內(nèi)容緩存在路徑上效用最大的節(jié)點(diǎn)上.Ren 等人[14]提出的Magic 緩存策略將內(nèi)容緩存在收益最大的節(jié)點(diǎn)上,并定義了在不同節(jié)點(diǎn)的緩存收益計(jì)算公式,緩存收益由內(nèi)容在該節(jié)點(diǎn)的局部熱度和節(jié)點(diǎn)到請(qǐng)求者的距離兩方面共同決定.然而,文獻(xiàn)并沒(méi)有明確給出內(nèi)容熱度統(tǒng)計(jì)方式.Gill 等人[9]提出了BidCache 競(jìng)拍緩存模型,請(qǐng)求轉(zhuǎn)發(fā)過(guò)程中,各節(jié)點(diǎn)根據(jù)當(dāng)前節(jié)點(diǎn)信息進(jìn)行“出價(jià)”,請(qǐng)求包頭記錄了最大“價(jià)格”及其出價(jià)節(jié)點(diǎn).當(dāng)內(nèi)容返回時(shí),將其緩存至路徑上出價(jià)最高的節(jié)點(diǎn)上.

各種On-path 緩存策略的共同特點(diǎn)是,網(wǎng)絡(luò)節(jié)點(diǎn)只與其請(qǐng)求路徑上游或下游的某些節(jié)點(diǎn)進(jìn)行協(xié)作.這一共性限制了網(wǎng)絡(luò)化緩存的潛在性能提升.由于缺乏全局拓?fù)湟晥D與緩存狀態(tài)相關(guān)信息,緩存策略只能基于單節(jié)點(diǎn)、單條傳輸路徑對(duì)緩存進(jìn)行優(yōu)化,這就限制了網(wǎng)絡(luò)性能提升的上界,也帶來(lái)了如下幾個(gè)方面的問(wèn)題.

1)緩存大量冗余.由于各節(jié)點(diǎn)獨(dú)立進(jìn)行緩存決策,同一網(wǎng)絡(luò)中各節(jié)點(diǎn)請(qǐng)求分布又基本一致,導(dǎo)致同一層各節(jié)點(diǎn)緩存下的內(nèi)容基本相同.有限的緩存空間和大量重復(fù)的內(nèi)容,給ICN 網(wǎng)絡(luò)帶來(lái)了更大的挑戰(zhàn);

2)命中退化現(xiàn)象.熱門(mén)內(nèi)容被拉取到網(wǎng)絡(luò)邊緣后,多數(shù)請(qǐng)求在邊緣節(jié)點(diǎn)得到滿(mǎn)足.邊緣節(jié)點(diǎn)的過(guò)濾效應(yīng),使得靠近中心的節(jié)點(diǎn)收到的內(nèi)容請(qǐng)求分布趨于隨機(jī),加上下游節(jié)點(diǎn)的請(qǐng)求匯聚作用,中心節(jié)點(diǎn)收到的請(qǐng)求熱度分布相對(duì)混亂.這種過(guò)濾與匯聚效應(yīng),使得原本在下游節(jié)點(diǎn)沒(méi)有命中的請(qǐng)求,在上游節(jié)點(diǎn)命中的概率也很低;

3)緩存可用性差.緩存僅為路徑可見(jiàn),即使緩存在請(qǐng)求節(jié)點(diǎn)的鄰居節(jié)點(diǎn),若不在其請(qǐng)求路徑上,則緩存不可用.緩存的可用性對(duì)網(wǎng)絡(luò)性能有很大的影響,較高的可用性,能夠提升單位緩存空間的效用.

1.2 基于哈希的緩存策略

為了有效解決On-path 緩存機(jī)制中緩存大量冗余、緩存命中率低的問(wèn)題,曾在P2P 中廣泛應(yīng)用的基于哈希的緩存策略得到了人們的重新關(guān)注.這類(lèi)策略將內(nèi)容的放置與路由請(qǐng)求通過(guò)哈希機(jī)制相結(jié)合,哈希映射不僅決定了內(nèi)容應(yīng)該緩存到哪,也決定了請(qǐng)求應(yīng)該向哪轉(zhuǎn)發(fā).通過(guò)這種請(qǐng)求的重定向機(jī)制,大幅降低了緩存的冗余,也提高了緩存的命中率,避免了頻繁的信息開(kāi)銷(xiāo).

Thar 等人[15]給出了一種基于哈希的緩存模型,闡述了包括協(xié)作轉(zhuǎn)發(fā)、熱度預(yù)測(cè)、內(nèi)容存取等的詳細(xì)過(guò)程.仿真實(shí)驗(yàn)顯示:該方案在緩存命中率方面有著巨大提升,然而也導(dǎo)致了內(nèi)容傳輸跳數(shù)上的增加.

傳輸跳數(shù)增加是所有哈希緩存策略存在的一個(gè)共同問(wèn)題,下面分別是不同的解決方案[16?19].Saino 等人[16]提出了兩種不同的解決方法:一種使內(nèi)容數(shù)據(jù)返回時(shí),總是沿著最短路徑返回;另一種則通過(guò)廣播的方式,多路徑返回內(nèi)容數(shù)據(jù).Sourlas 等人[17]認(rèn)為:緩存命中率與傳輸跳數(shù)相互制約,當(dāng)協(xié)作域較小時(shí),雖然緩存的整體命中率有所下降,但哈希策略引發(fā)的跳數(shù)增加也被限定在了一定的范圍之內(nèi).作者主張將大的協(xié)作域劃分為多個(gè)小的協(xié)作域,并給出了兩種協(xié)作域劃分算法.Wang 等人[18]設(shè)計(jì)了一種緩存分配算法,該算法在限定的跳數(shù)增加范圍內(nèi),嘗試尋找一種緩存分配方案.內(nèi)容首先哈希映射到一個(gè)Partition,每一個(gè)Partition 對(duì)應(yīng)一個(gè)或多個(gè)緩存節(jié)點(diǎn).由于內(nèi)容分配方案由入口路由器請(qǐng)求分布、網(wǎng)絡(luò)拓?fù)?、?nèi)容熱度等多種因素共同決定,當(dāng)網(wǎng)絡(luò)狀態(tài)發(fā)生改變時(shí),尤其是不同入口請(qǐng)求流量發(fā)生改變時(shí),若不改變已有分配方案,網(wǎng)絡(luò)性能則會(huì)明顯下降.而改變內(nèi)容分配方案帶來(lái)的代價(jià)是極大的,需要改變不同節(jié)點(diǎn)的緩存大小、路由轉(zhuǎn)發(fā)表、Partition 映射表等等.Li 等人[19]提出了一種啟發(fā)式內(nèi)容分配方案,將協(xié)作域內(nèi)的節(jié)點(diǎn)劃分為與出口路由器數(shù)量相等的簇.該算法采用模擬退火的方式,每次交換不同簇種的兩個(gè)節(jié)點(diǎn),看是否優(yōu)于先前分配方案.

基于哈希的緩存策略通過(guò)設(shè)計(jì)一種內(nèi)容分配方案,將內(nèi)容的緩存任務(wù)分配到域內(nèi)特定的網(wǎng)絡(luò)節(jié)點(diǎn).這種方式有效解決了緩存冗余問(wèn)題,提高了緩存命中率,但也帶來(lái)了一些新的問(wèn)題.

1)緩存位置缺乏合理規(guī)劃:內(nèi)容緩存位置被預(yù)先決定、將指定內(nèi)容與特定節(jié)點(diǎn)進(jìn)行綁定的緩存方式,一定程度上違反了ICN 內(nèi)容與位置分離的設(shè)計(jì)原則.現(xiàn)有的各種哈希緩存策略?xún)?nèi)容分配機(jī)制缺少對(duì)熱度內(nèi)容緩存位置的合理規(guī)劃.當(dāng)內(nèi)容熱度隨著時(shí)間、地域發(fā)生變化時(shí),這種問(wèn)題尤為明顯;

2)傳輸路徑的增加:相比On-path 緩存策略中最短路徑路由策略,基于哈希的緩存策略需要先將請(qǐng)求轉(zhuǎn)發(fā)至特定節(jié)點(diǎn),若未命中,再轉(zhuǎn)發(fā)至內(nèi)容源節(jié)點(diǎn).這種路由策略增加了內(nèi)容請(qǐng)求與回傳中的途經(jīng)跳數(shù).這也是現(xiàn)階段各種基于哈希緩存策略著重關(guān)注的問(wèn)題.目前,多數(shù)方案認(rèn)為影響傳輸跳數(shù)的因素與網(wǎng)絡(luò)拓?fù)洹⒄?qǐng)求分布密切相關(guān),忽略了內(nèi)容熱度對(duì)傳輸跳數(shù)的影響.

1.3 混合緩存策略

關(guān)于結(jié)合不同緩存策略的緩存機(jī)制最近已有不少研究,主要包括基于網(wǎng)絡(luò)結(jié)構(gòu)的混合緩存策略以及基于內(nèi)容熱度的混合緩存策略.

基于網(wǎng)絡(luò)結(jié)構(gòu)的混合緩存策略根據(jù)節(jié)點(diǎn)所處位置為不同節(jié)點(diǎn)提供不同的緩存策略.Zhang 等人[20]提出將網(wǎng)絡(luò)分成一個(gè)核心域和多個(gè)邊緣域,在核心域使用基于哈希的緩存策略,在邊緣域使用On-path 的緩存策略.該方法實(shí)際上是一種多域協(xié)作的部署策略.節(jié)點(diǎn)間緩存策略的融合,雖然在整體上提升了網(wǎng)絡(luò)性能,但對(duì)于單個(gè)域本身來(lái)說(shuō),緩存性能并沒(méi)有改變,因?yàn)橛騼?nèi)應(yīng)用的還是原有的緩存策略.該方法并不能解決緩存內(nèi)容在邊緣節(jié)點(diǎn)過(guò)度冗余的問(wèn)題.

基于內(nèi)容熱度的混合緩存策略為不同熱度的內(nèi)容提供不同的緩存策略.近年來(lái),已有許多緩存策略都考慮了內(nèi)容熱度對(duì)緩存的影響:Yu 等人[21]提出了基于熱度的動(dòng)態(tài)緩存權(quán)限策略;Yovita 等人[22]考慮將內(nèi)容按照不同的服務(wù)分成不同類(lèi);Yu 等人[23]將路由器分級(jí),將熱度高的內(nèi)容存儲(chǔ)在等級(jí)高的路由器上.相應(yīng)的混合策略也得到了人們的廣泛關(guān)注,Li[24]和Chang[25]等人通過(guò)理論建模分析,證明了基于熱度合理配置緩存空間,使其一部分緩存最熱門(mén)的內(nèi)容,另一部分參與全局協(xié)作,緩存次熱門(mén)內(nèi)容,能夠有效提高網(wǎng)絡(luò)性能.這種基于單個(gè)節(jié)點(diǎn)緩存空間劃分,有效利用內(nèi)容熱度分布的機(jī)制,使兩種緩存策略相結(jié)合,達(dá)到了優(yōu)勢(shì)互補(bǔ)的效果.文章雖然強(qiáng)調(diào)了內(nèi)容熱度的重要性,卻沒(méi)有給出內(nèi)容熱度的統(tǒng)計(jì)與篩選機(jī)制,且基于信息交換的域內(nèi)協(xié)作機(jī)制也帶來(lái)了頻繁的計(jì)算開(kāi)銷(xiāo)與信道占用.總的來(lái)說(shuō),這類(lèi)方案目前主要集中在理論建模與數(shù)學(xué)分析,并沒(méi)有給出可供實(shí)際部署的緩存策略.

本文提出的CSTC 是一種基于兩級(jí)緩存的協(xié)同緩存機(jī)制,不同于Li[24]和Chang[25]等人通過(guò)域內(nèi)信息交換來(lái)協(xié)作緩存,我們引入哈希機(jī)制,避免了大量的信息傳遞與計(jì)算開(kāi)銷(xiāo).同時(shí),我們也給出了兩部分緩存的協(xié)作方式、替換策略、熱度篩選方法及路由策略,是一種可應(yīng)用于實(shí)際部署環(huán)境的緩存機(jī)制.

2 CSTC 運(yùn)行機(jī)制

CSTC 通過(guò)引入兩級(jí)緩存機(jī)制,實(shí)現(xiàn)了不同熱度內(nèi)容的分級(jí)緩存,一方面降低了緩存的冗余;一方面,利用內(nèi)容熱度對(duì)緩存位置進(jìn)行了合理的規(guī)劃,使得緩存分布更接近理想分布狀態(tài).每個(gè)節(jié)點(diǎn)的緩存空間被分為RawCache 和HashCache 兩部分:針對(duì)RawCache,各節(jié)點(diǎn)基于本地?zé)岫雀兄M(jìn)行獨(dú)立緩存決策;針對(duì)HashCache,則通過(guò)哈希機(jī)制構(gòu)成域內(nèi)多節(jié)點(diǎn)間協(xié)作,實(shí)現(xiàn)了域內(nèi)熱度的分布感知及決策,為不同層次的熱度內(nèi)容提供不同的緩存策略.通過(guò)所設(shè)計(jì)的熱度篩選機(jī)制與路由策略,達(dá)到了內(nèi)容熱度篩選的目的,優(yōu)化了緩存位置,降低了緩存的冗余,增大了域內(nèi)穩(wěn)定緩存內(nèi)容的數(shù)量.本節(jié)將闡述CSTC 的詳細(xì)過(guò)程.

2.1 CSTC基本框架

研究表明:網(wǎng)絡(luò)中內(nèi)容的熱度服從Zipf 分布[10],不同內(nèi)容的請(qǐng)求頻率相差巨大,多數(shù)請(qǐng)求僅僅集中在少數(shù)熱門(mén)內(nèi)容上.Li 等人[24]通過(guò)構(gòu)建模型,分析如何配置單個(gè)路由節(jié)點(diǎn)的緩存空間,以達(dá)到整體網(wǎng)絡(luò)性能與成本的最優(yōu);Chang 等人[25]在Li 等人研究的基礎(chǔ)上提出一種確定節(jié)點(diǎn)緩存空間比例以及如何放置內(nèi)容的方法,證明將緩存空間基于內(nèi)容熱度分塊——一部分采用On-path 來(lái)緩存最熱門(mén)的內(nèi)容,另一部分參與全局協(xié)作,緩存次熱門(mén)內(nèi)容,可以在保持緩存命中率的同時(shí),有效降低請(qǐng)求的平均時(shí)延.

然而,上述方法僅僅是對(duì)最優(yōu)緩存策略的數(shù)學(xué)量化與理論建模.緩存策略也是基于所有內(nèi)容熱度已知的先決條件下完成的,同時(shí),各節(jié)點(diǎn)的緩存依賴(lài)于集中式的決策控制,并不適用于實(shí)際環(huán)境的部署要求.CSTC 基于以下考慮.

1)最熱門(mén)內(nèi)容應(yīng)在網(wǎng)絡(luò)邊緣適度冗余,減少用戶(hù)請(qǐng)求跳數(shù).Fayazbakhsh 等人[26]通過(guò)大量仿真實(shí)驗(yàn)證明:僅僅簡(jiǎn)單地在網(wǎng)絡(luò)邊緣部署足夠大的緩存,就能達(dá)到可觀(guān)的網(wǎng)絡(luò)性能提升.這正是熱門(mén)內(nèi)容在網(wǎng)絡(luò)邊緣冗余帶來(lái)的效果.讓用戶(hù)的多數(shù)請(qǐng)求在網(wǎng)絡(luò)邊緣節(jié)點(diǎn)得到滿(mǎn)足,不僅減少了用戶(hù)的請(qǐng)求時(shí)間,也極大降低了網(wǎng)絡(luò)負(fù)載;

2)次熱門(mén)內(nèi)容應(yīng)穩(wěn)定緩存,盡量避免非熱門(mén)內(nèi)容占據(jù)緩存空間.最熱門(mén)內(nèi)容只占網(wǎng)絡(luò)中內(nèi)容的極少部分,網(wǎng)絡(luò)中存在著大量的次熱門(mén)和非熱門(mén)內(nèi)容.為有效提高請(qǐng)求命中率,我們希望可以選定合理的存儲(chǔ)位置,通過(guò)請(qǐng)求重定向匯聚次熱門(mén)內(nèi)容的熱度,使得次熱門(mén)內(nèi)容能在指定節(jié)點(diǎn)穩(wěn)定緩存,進(jìn)而提高次熱門(mén)內(nèi)容緩存多樣性,降低非熱門(mén)內(nèi)容對(duì)緩存空間的占用;

3)節(jié)點(diǎn)間較小的信息交換開(kāi)銷(xiāo)與線(xiàn)性算法復(fù)雜度.現(xiàn)有的各種全局節(jié)點(diǎn)協(xié)作的內(nèi)容熱度感知方案[8,27]需要不同節(jié)點(diǎn)間頻繁的信息交流與計(jì)算開(kāi)銷(xiāo),同時(shí)會(huì)給集中控制節(jié)點(diǎn)帶來(lái)較大的流量負(fù)擔(dān)與計(jì)算壓力,這會(huì)給以線(xiàn)性速度為要求的高速信息中心網(wǎng)絡(luò)帶來(lái)新的性能瓶頸.

CSTC 中,節(jié)點(diǎn)緩存空間被分為RawCache 和HashCache 兩部分,如圖1所示.RawCache 上采用On-path 緩存策略,對(duì)途經(jīng)的內(nèi)容進(jìn)行緩存,同時(shí)對(duì)緩存下來(lái)的內(nèi)容進(jìn)行基于單節(jié)點(diǎn)熱度統(tǒng)計(jì).通過(guò)這種方式,最熱門(mén)內(nèi)容被拉取到網(wǎng)絡(luò)邊緣穩(wěn)定緩存,而次熱門(mén)與非熱門(mén)內(nèi)容則會(huì)在RawCache 中頻繁替換,難以穩(wěn)定緩存.當(dāng)RawCache中緩存內(nèi)容發(fā)生替換時(shí),若為非熱門(mén)內(nèi)容,則直接替換出緩存空間,否則根據(jù)哈希映射找到其匹配節(jié)點(diǎn),并將其發(fā)往對(duì)應(yīng)節(jié)點(diǎn)的HashCache.不同節(jié)點(diǎn)的HashCache 構(gòu)成一個(gè)協(xié)作整體,一方面,每塊HashCache 通過(guò)哈希機(jī)制緩存不同的內(nèi)容,有效避免了緩存冗余;另一方面,域內(nèi)被替換出的不同內(nèi)容會(huì)被匯聚到不同節(jié)點(diǎn),內(nèi)容會(huì)依照其全局熱度在該節(jié)點(diǎn)展開(kāi)緩存空間的二次競(jìng)爭(zhēng).通過(guò)這種兩級(jí)緩存機(jī)制,最熱門(mén)的內(nèi)容會(huì)留在RawCache 中,次熱門(mén)內(nèi)容會(huì)穩(wěn)定緩存在HashCache 中.不同節(jié)點(diǎn)的HashCache 被分配以不同的緩存任務(wù),這些節(jié)點(diǎn)的HashCache通過(guò)哈希機(jī)制構(gòu)成一個(gè)協(xié)作整體.

節(jié)點(diǎn)上相互關(guān)聯(lián)兩部分的緩存可以采用LRU 或LFU 緩存替換策略.初始階段,兩部分緩存都為空,當(dāng)內(nèi)容經(jīng)過(guò)節(jié)點(diǎn)時(shí),節(jié)點(diǎn)的RawCache 部分執(zhí)行On-path 緩存策略對(duì)內(nèi)容進(jìn)行存儲(chǔ).當(dāng)RawCache 剩余緩存空間大小為0 時(shí),若仍需緩存新內(nèi)容,則會(huì)通過(guò)緩存替換決策替換掉原有的緩存內(nèi)容.這時(shí),節(jié)點(diǎn)先依照所統(tǒng)計(jì)的內(nèi)容命中次數(shù)判斷將被替換出的內(nèi)容的熱度:若為熱門(mén)內(nèi)容,則查找哈希映射表,將內(nèi)容發(fā)往對(duì)應(yīng)節(jié)點(diǎn)的HashCache,再執(zhí)行替換操作;否則,直接執(zhí)行替換操作.協(xié)作域中節(jié)點(diǎn)的HashCache 部分收到從RawCache 發(fā)來(lái)的內(nèi)容時(shí),對(duì)其進(jìn)行緩存決策,此時(shí)若該節(jié)點(diǎn)的RawCache 中已緩存該內(nèi)容,則將內(nèi)容從RawCache 中刪除以避免冗余.當(dāng)HashCache發(fā)生內(nèi)容替換時(shí),考慮到HashCache 中多為熱門(mén)內(nèi)容,節(jié)點(diǎn)將替換內(nèi)容移動(dòng)到本節(jié)點(diǎn)的RawCache 中,而不是直接丟棄.

通過(guò)這種兩級(jí)緩存機(jī)制,域內(nèi)的RawCache 會(huì)對(duì)網(wǎng)絡(luò)中的內(nèi)容進(jìn)行篩選,被頻繁訪(fǎng)問(wèn)的最熱門(mén)內(nèi)容會(huì)穩(wěn)定地緩存在各個(gè)節(jié)點(diǎn)的RawCache 中,降低用戶(hù)的訪(fǎng)問(wèn)跳數(shù),也減輕了網(wǎng)絡(luò)核心節(jié)點(diǎn)的負(fù)載.RawCache 中替換出的仍有一定熱度的內(nèi)容會(huì)通過(guò)哈希映射緩存在HashCache 中,大幅提高了緩存的多樣性,同時(shí)避免了過(guò)度冗余.

Fig.1 T wo-level cache for CSTC圖1 CSTC 兩級(jí)緩存

2.2 CSTC熱度篩選

內(nèi)容熱度是影響網(wǎng)絡(luò)緩存性能的關(guān)鍵.相比于常見(jiàn)的利用內(nèi)容請(qǐng)求次數(shù)來(lái)表示內(nèi)容熱度,本節(jié)設(shè)計(jì)了基于內(nèi)容命中次數(shù)的熱度統(tǒng)計(jì)方法,主要基于以下考慮.

1)由于網(wǎng)絡(luò)中的內(nèi)容非常多,統(tǒng)計(jì)所有內(nèi)容的請(qǐng)求數(shù)是不現(xiàn)實(shí)且不必要的.為了降低時(shí)間空間開(kāi)銷(xiāo),我們只針對(duì)已緩存的內(nèi)容進(jìn)行請(qǐng)求次數(shù)的統(tǒng)計(jì),已緩存內(nèi)容的請(qǐng)求次數(shù)即為內(nèi)容的命中數(shù);

2)在CSTC 方法中,熱度內(nèi)容首先基于On-path 策略存入RawCache,針對(duì)RawCache 中已緩存的內(nèi)容,再利用其熱度信息判斷是否存入HashCache.熱度統(tǒng)計(jì)只是針對(duì)RawCache 已緩存內(nèi)容,命中數(shù)可以很好地反映已緩存內(nèi)容的熱度.

為了準(zhǔn)確感知內(nèi)容熱度,CSTC 中每個(gè)節(jié)點(diǎn)需要維護(hù)兩種數(shù)據(jù)結(jié)構(gòu):本地命中列表(local hit table,簡(jiǎn)稱(chēng)LHT)和熱度統(tǒng)計(jì)列表(popularity tab le,簡(jiǎn)稱(chēng)PT).如圖2所示,LHT 用以維護(hù)節(jié)點(diǎn)已緩存內(nèi)容在該節(jié)點(diǎn)上的命中次數(shù),格式為〈name:(hit,time)〉.PT 用以維護(hù)內(nèi)容在協(xié)作域內(nèi)的熱度,格式為〈name:(popularity,time)〉.各字段含義如下.

?name:目標(biāo)內(nèi)容名字;

?hit:內(nèi)容命中次數(shù),非負(fù)整數(shù);

?popularity:內(nèi)容在域內(nèi)的熱度,非負(fù)整數(shù);

?time:列表項(xiàng)上次更新時(shí)間.

當(dāng)內(nèi)容在節(jié)點(diǎn)的緩存空間(RawCache 或HashCache)命中時(shí),LHT 對(duì)應(yīng)位置上的hit項(xiàng)則加1.LHT 的列表長(zhǎng)度與節(jié)點(diǎn)的緩存大小一樣,當(dāng)內(nèi)容從節(jié)點(diǎn)緩存空間移除時(shí),對(duì)應(yīng)表項(xiàng)也隨之移除.因此,LHT 統(tǒng)計(jì)的內(nèi)容命中次數(shù)只是單節(jié)點(diǎn)局部時(shí)間熱度,保證了列表較小的空間復(fù)雜度.hit的初始值為對(duì)應(yīng)內(nèi)容在PIT 表中記錄的返回接口數(shù)目減1,表示在內(nèi)容被緩存到節(jié)點(diǎn)的CS 中之前,內(nèi)容的熱度等于內(nèi)容的請(qǐng)求數(shù).當(dāng)內(nèi)容被緩存在節(jié)點(diǎn)的CS中后,內(nèi)容在該節(jié)點(diǎn)的請(qǐng)求可以在CS 中命中,此時(shí)內(nèi)容的請(qǐng)求數(shù)等于內(nèi)容的命中數(shù).當(dāng)Interest 在節(jié)點(diǎn)的CS 中命中時(shí),使用下面的公式更新表項(xiàng):

其中,ρ(0<ρ<1)決定了內(nèi)容命中次數(shù)隨時(shí)間衰減的快慢,tcur指當(dāng)前時(shí)間,tlast指上次表項(xiàng)更新時(shí)間.與周期性進(jìn)行熱度衰減的方法不同,我們采用基于命中的時(shí)間衰減方法,這種方法不需要周期性地更新內(nèi)容熱度,只需要在有數(shù)據(jù)包到來(lái)的時(shí)候進(jìn)行衰減操作,降低了更新的開(kāi)銷(xiāo).當(dāng)數(shù)據(jù)包到達(dá)時(shí),首先利用時(shí)間衰變參數(shù)對(duì)歷史的命中數(shù)進(jìn)行衰減,再將衰減操作后的值加1,表示當(dāng)前內(nèi)容在節(jié)點(diǎn)中的熱度,當(dāng)前時(shí)間與上次表項(xiàng)更新時(shí)間間隔越久,歷史命中數(shù)對(duì)當(dāng)前內(nèi)容熱度的影響越小.

Fig.2 Local hit table and popularity table圖2 本地命中列表與熱度統(tǒng)計(jì)表

當(dāng)緩存內(nèi)容在RawCache 中發(fā)生替換時(shí),首先根據(jù)LHT 表中hit項(xiàng)判斷其命中次數(shù)是否大于所設(shè)閾值,若滿(mǎn)足要求,則認(rèn)為該內(nèi)容應(yīng)該被緩存至域內(nèi)HashCache 中,此時(shí)節(jié)點(diǎn)會(huì)將內(nèi)容本身以及該內(nèi)容在LHT 表中的相關(guān)信息一并發(fā)送至哈希映射所得節(jié)點(diǎn).對(duì)應(yīng)節(jié)點(diǎn)收到內(nèi)容以后,除了存儲(chǔ)內(nèi)容本身以外,還會(huì)更新自身PT 表項(xiàng).更新規(guī)則如下:若PT 表中沒(méi)有該項(xiàng)內(nèi)容,則直接將內(nèi)容的單節(jié)點(diǎn)命中次數(shù)作為內(nèi)容熱度,即x.popularity=x.hit;若PT 表中已存在該項(xiàng)內(nèi)容,則使用下面的公式更新表項(xiàng):

其中,θ(0<θ<1)是單節(jié)點(diǎn)內(nèi)容命中次數(shù)在域內(nèi)內(nèi)容熱度上的權(quán)重參數(shù),ρ(0<ρ<1)決定了內(nèi)容熱度隨時(shí)間衰減的快慢,tcur指當(dāng)前時(shí)間,tlast指上次表項(xiàng)更新時(shí)間.為與LHT 表的時(shí)間衰減保持一致,我們?cè)赑T 表的熱度更新中同樣引入時(shí)間衰減.通過(guò)哈希映射機(jī)制,域內(nèi)各節(jié)點(diǎn)RawCache 中替換出的同一內(nèi)容會(huì)被發(fā)送到同一節(jié)點(diǎn),目標(biāo)節(jié)點(diǎn)通過(guò)域內(nèi)各個(gè)節(jié)點(diǎn)的局部命中次數(shù)不斷更新該內(nèi)容的popularity,最終得到的popularity實(shí)際上是域內(nèi)所有節(jié)點(diǎn)命中次數(shù)共同作用的整體結(jié)果.PT 表中內(nèi)容按照popularity由大到小排序,用以指導(dǎo)HashCache 緩存哪些內(nèi)容.節(jié)點(diǎn)會(huì)記錄HashCache 中已緩存內(nèi)容的popularity最小值,當(dāng)要緩存新內(nèi)容時(shí),首先比較二者的popularity:若要緩存的內(nèi)容的popularity大于該值,則進(jìn)行緩存,并替換掉popularity最小的內(nèi)容;否則不做緩存處理.

2.3 CSTC路由策略

本節(jié)假設(shè)我們提出的CSTC 緩存機(jī)制運(yùn)行在典型的ICN 網(wǎng)絡(luò)NDN[12]中,NDN 中共有兩種數(shù)據(jù)類(lèi)型:興趣分組(interest packet)和數(shù)據(jù)分組(data pa cket).用戶(hù)發(fā)起的請(qǐng)求稱(chēng)為Interest,響應(yīng)請(qǐng)求返回的內(nèi)容數(shù)據(jù)稱(chēng)為Data.需要說(shuō)明的是:HashCache 上采用的哈希映射機(jī)制的詳細(xì)過(guò)程并不是CSTC 關(guān)注的主要內(nèi)容,就像我們并不限制RawCache 上必須采用某種On-path 緩存策略一樣.

表1 中,當(dāng)節(jié)點(diǎn)收到Interest 請(qǐng)求時(shí),首先會(huì)查找自身內(nèi)容存儲(chǔ)表(content st ore,CS)與待定請(qǐng)求表(pending interest ta ble,簡(jiǎn)稱(chēng)PIT),看是否有內(nèi)容命中.若都沒(méi)有命中,則根據(jù)哈希映射得到目標(biāo)節(jié)點(diǎn),并向其轉(zhuǎn)發(fā)(第5 行).若Interest 到達(dá)目標(biāo)節(jié)點(diǎn)后仍沒(méi)有命中,則將Interest 轉(zhuǎn)發(fā)至內(nèi)容源(第3 行).

Table 1 INTEREST routing algorithm表1 INTEREST 路由算法

表2 中,節(jié)點(diǎn)收到Data 數(shù)據(jù)分為兩類(lèi):一類(lèi)是普通的Data,另一類(lèi)是其他節(jié)點(diǎn)RawCache 中替換出的內(nèi)容重新組裝成的Data.若是普通Data(第14 行),則按照RawCache 上采用的On-path 緩存策略對(duì)其進(jìn)行處理,同時(shí),如果在緩存的過(guò)程中發(fā)生了內(nèi)容替換,則節(jié)點(diǎn)將內(nèi)容本身及其所對(duì)應(yīng)的PT 表項(xiàng)封裝為新的Data,轉(zhuǎn)發(fā)至哈希映射所得目標(biāo)節(jié)點(diǎn),轉(zhuǎn)發(fā)過(guò)程中的途經(jīng)節(jié)點(diǎn)不再對(duì)其進(jìn)行處理(第12 行).當(dāng)目標(biāo)節(jié)點(diǎn)收到其他節(jié)點(diǎn)發(fā)送來(lái)的Data 時(shí)(第2 行),則將其緩存至HashCache 中并按照公式(2)更新PT 表項(xiàng).HashCache 中替換出的內(nèi)容會(huì)被移動(dòng)至該節(jié)點(diǎn)的RawCache 中,而不會(huì)直接丟棄.

Table 2 DA TA routing algorithm表2 DATA 路由算法

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

為了評(píng)估CSTC 的緩存效果與性能,我們基于ccnSim[28]設(shè)計(jì)實(shí)現(xiàn)了緩存仿真實(shí)驗(yàn),將CSTC 與多種現(xiàn)有緩存方案進(jìn)行了對(duì)比分析實(shí)驗(yàn),并探究了各緩存因素對(duì)緩存性能的影響.本節(jié)將從實(shí)驗(yàn)環(huán)境與配置、對(duì)比方案與性能指標(biāo)、仿真結(jié)果與分析這3 個(gè)方面詳細(xì)闡述仿真實(shí)驗(yàn)與結(jié)果.

3.1 實(shí)驗(yàn)環(huán)境與配置

考慮到一個(gè)請(qǐng)求域的大小,我們選擇了美國(guó)愛(ài)荷華州的一個(gè)真實(shí)拓?fù)浣Y(jié)構(gòu)[29]作為仿真拓?fù)渚W(wǎng)絡(luò),該拓?fù)涔灿?0 個(gè)節(jié)點(diǎn)、38 條邊.為了合理模擬真實(shí)網(wǎng)絡(luò)狀態(tài),當(dāng)內(nèi)容在域內(nèi)未命中時(shí),我們?cè)O(shè)置的出域路由的請(qǐng)求跳數(shù)為10 跳.每個(gè)節(jié)點(diǎn)都連接有一組用戶(hù),不間斷地連續(xù)模擬發(fā)起內(nèi)容請(qǐng)求,用戶(hù)請(qǐng)求服從泊松分布.仿真實(shí)驗(yàn)中共有100 萬(wàn)個(gè)不同的內(nèi)容,我們假設(shè)內(nèi)容整體上服從參數(shù)為α的Zipf 分布,也就是說(shuō),排名第k的熱門(mén)內(nèi)容的請(qǐng)求概率為:

實(shí)驗(yàn)中,緩存默認(rèn)替換算法采用LRU(least recently used),每次替換掉最近最少使用的內(nèi)容.仿真過(guò)程中,首先等待每個(gè)節(jié)點(diǎn)的緩存空間被占滿(mǎn),然后等待每個(gè)節(jié)點(diǎn)處于穩(wěn)定狀態(tài)(即節(jié)點(diǎn)收到的請(qǐng)求數(shù)上下波動(dòng)處于較小范圍)后,開(kāi)始數(shù)據(jù)收集與統(tǒng)計(jì).仿真實(shí)驗(yàn)中,各項(xiàng)參數(shù)見(jiàn)表3.下文未特別說(shuō)明實(shí)驗(yàn)參數(shù)的情形下,均采用表3 中默認(rèn)值.

Table 3 P arameters of experiments表3 實(shí)驗(yàn)參數(shù)

3.2 對(duì)比方案與性能指標(biāo)

仿真實(shí)驗(yàn)中采用的緩存方案包括如下幾種.

?CSTC:即本文提出的基于兩級(jí)緩存的緩存機(jī)制.實(shí)驗(yàn)中,每個(gè)緩存節(jié)點(diǎn)的RawCache 與HashCache 各占一半,RawCache 上采用Prob(0.05)的On-path 策略,設(shè)置的命中閾值為1,熱度權(quán)重參數(shù)θ為0.6,時(shí)間權(quán)重參數(shù)ρ為0.9;

?OH:我們實(shí)現(xiàn)了文獻(xiàn)[15]中的哈希映射機(jī)制,將其應(yīng)用到仿真實(shí)驗(yàn)中,以代表現(xiàn)有各種基于哈希的緩存策略,我們將這類(lèi)策略簡(jiǎn)稱(chēng)為OH(only Hash);

?LCE:多數(shù)ICN 默認(rèn)緩存策略,即節(jié)點(diǎn)無(wú)差別的緩存所有內(nèi)容[12];

?Prob(p):每個(gè)節(jié)點(diǎn)以固定概率p緩存經(jīng)過(guò)的所有內(nèi)容,我們?cè)O(shè)置的p=0.05;

?ProbCache:一種基于加權(quán)概率的緩存策略,距離請(qǐng)求者越近、存儲(chǔ)空間越大的節(jié)點(diǎn),緩存該內(nèi)容的概率越大;

?BidCache:我們實(shí)現(xiàn)了文獻(xiàn)[9]中的BidCache 緩存機(jī)制,這是一種近年來(lái)較為典型的On-path 協(xié)作式緩存策略,它利用較少的代價(jià)進(jìn)行路徑上節(jié)點(diǎn)的通信,結(jié)合網(wǎng)絡(luò)的拓?fù)鋵?shí)現(xiàn)緩存決策.

本文主要從兩個(gè)方面評(píng)判緩存方案的優(yōu)劣.

(1)請(qǐng)求命中率

內(nèi)容請(qǐng)求在域內(nèi)總的命中率反映了域內(nèi)整體緩存狀態(tài)(包括緩存多樣性、緩存可用性、緩存冗余度等)的好壞,命中率越高,說(shuō)明緩存效果越好,帶來(lái)的網(wǎng)絡(luò)性能提升也越明顯.請(qǐng)求命中率的計(jì)算公式如下:

其中,Numhit表示請(qǐng)求在該節(jié)點(diǎn)的命中次數(shù),Numtotal表示請(qǐng)求總數(shù),i表示第i個(gè)節(jié)點(diǎn).

(2)平均傳輸跳數(shù)

平均傳輸跳數(shù)不僅反映了緩存內(nèi)容的好壞,還體現(xiàn)了緩存位置是否合理.當(dāng)請(qǐng)求命中率較高時(shí),多數(shù)請(qǐng)求在域內(nèi)命中,避免了出域的跳數(shù)代價(jià),跳數(shù)也就越小.同時(shí),緩存內(nèi)容位置越合理,平均傳輸跳數(shù)也就越小,用戶(hù)訪(fǎng)問(wèn)延時(shí)越低.其計(jì)算公式如下:

其中,hopinterest表示Interest 請(qǐng)求所用跳數(shù),hopdata表示Data 返回所用跳數(shù),Numtotal指總請(qǐng)求數(shù).

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

3.3.1 緩存內(nèi)容分布

前文分析已知:在緩存空間一定的情況下,能夠在本地域內(nèi)緩存的內(nèi)容數(shù)量越多,緩存內(nèi)容的熱度越高,越能高效響應(yīng)用戶(hù)的不同請(qǐng)求.本節(jié)分析了不同緩存策略下緩存內(nèi)容的分布狀態(tài),內(nèi)容總數(shù)為1 000 000.根據(jù)Zipf分布定律,我們將熱度排名為1~1 000 的內(nèi)容用黑色表示,代表最熱門(mén)內(nèi)容;排名在1 000~10 000 的內(nèi)容用灰色表示,代表次熱門(mén)內(nèi)容;其他內(nèi)容用白色表示,代表非熱門(mén)內(nèi)容.圖3 在真實(shí)拓?fù)渖侠L制了各個(gè)節(jié)點(diǎn)在不同緩存方案下緩存內(nèi)容分布狀況.

Fig.3 Distribution of cache圖3 緩存內(nèi)容分布

從圖3(a)可以看出:Prob(0.05)策略下,各節(jié)點(diǎn)缺乏合理協(xié)作機(jī)制,最熱門(mén)的內(nèi)容在各節(jié)點(diǎn)上形成了大量冗余,緩存空間被最熱門(mén)的一小部分內(nèi)容大量占據(jù),次熱門(mén)緩存數(shù)量極少,緩存多樣性較差,緩存空間利用率較低.這也印證了前文所述的On-path 所存在的各種問(wèn)題.圖3(b)展示了OH 策略下各節(jié)點(diǎn)緩存狀態(tài),與Prob(0.05)不同的是:在該策略下,雖然有效避免了緩存冗余,緩存的多樣性得到了極大的提升,但緩存的內(nèi)容大多為非熱門(mén)內(nèi)容,緩存內(nèi)容的效用較差.

與前兩種緩存機(jī)制相比,CSTC 緩存效果最為理想.如圖3(c)所示,各個(gè)節(jié)點(diǎn)對(duì)最熱門(mén)內(nèi)容產(chǎn)生適度冗余,在次熱門(mén)內(nèi)容上緩存種類(lèi)較多,有效避免了非熱門(mén)內(nèi)容對(duì)緩存空間的過(guò)量占據(jù).這主要是因?yàn)镽awCache 的內(nèi)容熱度感知保證了HashCache 中緩存內(nèi)容的熱度,通過(guò)基于哈希的請(qǐng)求重定向,使得這些次熱門(mén)內(nèi)容的請(qǐng)求被匯聚并穩(wěn)定緩存到特定節(jié)點(diǎn).

3.3.2 緩存大小的影響

緩存大小決定了緩存內(nèi)容的多少,是影響緩存性能的重要因素之一.本節(jié)分析了不同緩存空間大小對(duì)緩存性能的影響.我們?cè)O(shè)置的緩存空間大小變動(dòng)范圍為500~7000,其他實(shí)驗(yàn)參數(shù)保持不變,觀(guān)察請(qǐng)求命中率與平均傳輸跳數(shù)的變化.

從圖4(a)可以看出,請(qǐng)求命中率隨著緩存空間的增大而增大.CSTC 與OH 兩種策略在命中率上要顯著高于另外4 種基于On-path 的緩存策略,這得益于哈希映射機(jī)制有效降低了緩存冗余,提高了本地域內(nèi)的緩存多樣性,從而使得更多的用戶(hù)請(qǐng)求能在本地域內(nèi)得到響應(yīng).從圖中可以發(fā)現(xiàn):CSTC 即使內(nèi)容多樣性不如OH,但命中率卻大于OH.這主要是因?yàn)镃STC 基于熱度感知使得緩存下的內(nèi)容熱度較高,能夠在適當(dāng)?shù)奈恢帽环€(wěn)定緩存;而OH 雖然可能緩存下更多內(nèi)容,但由于沒(méi)有熱度感知,使得緩存下的很多是非熱度內(nèi)容,這些內(nèi)容將在緩存中頻繁進(jìn)出,浪費(fèi)緩存空間.同時(shí)我們發(fā)現(xiàn):當(dāng)緩存空間較小時(shí),CSTC 的優(yōu)勢(shì)更為明顯.這是因?yàn)榫彺婵臻g變大以后,即使OH 缺乏合理熱度感知機(jī)制,也能將大多數(shù)熱門(mén)內(nèi)容緩存下來(lái),從而縮小了與CSTC 的命中率差距.另外,ProbCache 與Prob(0.05)兩種緩存策略在命中率上基本一致,都高于LCE,BidCache 的命中率略高于ProbCache.這是由于BideCache 不僅考慮與用戶(hù)的距離,還考慮當(dāng)前節(jié)點(diǎn)的中心度等,只有綜合分?jǐn)?shù)最高的節(jié)點(diǎn)才能夠緩存內(nèi)容.因此,BidCache 有更合理的內(nèi)容放置策略,緩存的內(nèi)容更多,內(nèi)容命中率更高.當(dāng)緩存空間越來(lái)越大時(shí),ProbCache 緩存的內(nèi)容越來(lái)越多,兩種方法緩存的內(nèi)容種類(lèi)差距變小,命中率也就越來(lái)越接近.

圖4(b)展示了不同緩存空間大小對(duì)平均傳輸跳數(shù)的影響.從圖中可以看出:當(dāng)緩存空間較小時(shí),由于Onpath 緩存策略可以將最為熱門(mén)的內(nèi)容緩存在網(wǎng)絡(luò)邊緣,所以在平均跳數(shù)上優(yōu)勢(shì)較為明顯;而OH 因?yàn)樾枰獙?duì)所有請(qǐng)求重定向到特定節(jié)點(diǎn),其請(qǐng)求和響應(yīng)的平均跳數(shù)最大.但隨著緩存空間的增大,CSTC 與OH 在跳數(shù)上的下降較為明顯,而另外4 種On-path 策略對(duì)緩存空間大小的變化并不敏感.這是因?yàn)楫?dāng)緩存空間增大時(shí),CSTC 與OH 可以緩存下來(lái)更多不同的內(nèi)容,從而大幅減少轉(zhuǎn)發(fā)至域外的請(qǐng)求數(shù)量,多數(shù)請(qǐng)求在域內(nèi)命中,總的平均跳數(shù)也隨之下降.

Fig.4 Impact of cache size圖4 緩存大小的影響

3.3.3 內(nèi)容熱度的影響

已有研究表明,網(wǎng)絡(luò)中內(nèi)容熱度分布服從Zipf 分布.本節(jié)探究了Zipf 分布參數(shù)α對(duì)緩存性能的影響.從圖5(a)中我們可以看出:隨著參數(shù)α值的增大,內(nèi)容的熱度收斂更加明顯,更多的請(qǐng)求集中在少數(shù)的熱門(mén)內(nèi)容上,導(dǎo)致請(qǐng)求的整體命中率提高.這是因?yàn)楦鞴?jié)點(diǎn)只需將較為熱門(mén)的少許內(nèi)容進(jìn)行存儲(chǔ),便能達(dá)到較高的命中率.從圖中可以看出:CSTC 的命中率要高于OH,但隨著參數(shù)α的增大,二者的命中率逐漸趨于相同.這是由于參數(shù)α較小時(shí),內(nèi)容熱度較不明顯,OH 雖然緩存的內(nèi)容多樣性更豐富,但由于較差的熱度感知能力,多數(shù)都為請(qǐng)求率較低的非熱門(mén)內(nèi)容.圖5(b)展示了不同參數(shù)α下,各緩存機(jī)制的平均傳輸跳數(shù).CSTC 的平均傳輸跳數(shù)不僅優(yōu)于簡(jiǎn)單哈希機(jī)制,在多數(shù)情形下也優(yōu)于各種On-path 緩存機(jī)制.這是因?yàn)殡m然On-path 緩存機(jī)制極大地減少了命中內(nèi)容的往返跳數(shù),但由于存在著大量的冗余,其緩存內(nèi)容的多樣性較差,命中率也較低.當(dāng)內(nèi)容在域內(nèi)沒(méi)有命中時(shí),就要將請(qǐng)求轉(zhuǎn)發(fā)至域外,導(dǎo)致跳數(shù)的大幅增加.

Fig.5 Impact of content popularity圖5 內(nèi)容熱度的影響

3.3.4 兩級(jí)緩存比例的影響

本節(jié)分析了CSTC 中RawCache 和HashCache 兩級(jí)緩存比例對(duì)緩存性能的影響.通過(guò)大量實(shí)驗(yàn)我們發(fā)現(xiàn):兩級(jí)緩存比例對(duì)網(wǎng)絡(luò)性能的影響在不同條件下是不一致的,應(yīng)該結(jié)合內(nèi)容熱度分布參數(shù)α和緩存大小綜合考慮.而內(nèi)容熱度分布參數(shù)α對(duì)其影響最為突出,下文以α為代表,分析其影響.

圖6(a)描述了兩級(jí)緩存比例對(duì)CSTC 命中率的影響,橫坐標(biāo)代表RawCache 所占比例的變化,縱坐標(biāo)表示請(qǐng)求命中率.圖中不同曲線(xiàn)反映了不同α下,兩級(jí)緩存比例對(duì)請(qǐng)求命中率的影響.從圖中可以看出:隨著RawCache比例的提高,緩存的命中率在逐漸降低.同時(shí)我們發(fā)現(xiàn):當(dāng)α越小,其下降也越明顯.當(dāng)RawCache 比例提高,也就是HashCache 比例下降時(shí),域內(nèi)穩(wěn)定緩存的次熱度內(nèi)容數(shù)量減少,即緩存內(nèi)容多樣性隨之下降,從而導(dǎo)致了命中率的降低.α越小,緩存內(nèi)容熱度分布越不集中,RawCache 基于本地?zé)岫雀兄芊€(wěn)定緩存下的熱度內(nèi)容減少,因此命中率會(huì)有所下降.從圖中可以發(fā)現(xiàn):當(dāng)RawCache 比例提高到100%,即退化為僅基于本地?zé)岫雀兄囊患?jí)緩存策略時(shí),命中率下降最為明顯.這也說(shuō)明了兩級(jí)緩存的設(shè)計(jì)是緩存性能提升的優(yōu)勢(shì)所在.

圖6(b)與圖6(c)展示了兩級(jí)緩存比例對(duì)用戶(hù)請(qǐng)求響應(yīng)平均傳輸跳數(shù)的影響.從圖6(b)我們發(fā)現(xiàn):當(dāng)α較小時(shí),隨著RawCache 比例的提高,平均傳輸跳數(shù)在逐漸升高.而圖6(c)顯示:當(dāng)α較大時(shí),隨著RawCache 比例的提高,平均傳輸跳數(shù)會(huì)先降低再上升.我們分析了其中的原因:當(dāng)RawCache 比例提高時(shí),一方面,RawCache 可以通過(guò)On-path 方式緩存更多的內(nèi)容,On-path 較小的傳輸跳數(shù)會(huì)減小CSTC 的平均傳輸跳數(shù);另一方面,因HashCache比例的下降,會(huì)導(dǎo)致許多原本在域內(nèi)就可以命中的內(nèi)容,現(xiàn)在需要將其轉(zhuǎn)發(fā)至域外,這增加了基于二級(jí)緩存的緩存方式的平均傳輸跳數(shù).所以當(dāng)α較小時(shí),On-path 緩存機(jī)制本身命中率較低,其對(duì)CSTC 跳數(shù)的降低不足以彌補(bǔ)由于HashCache 下降所帶來(lái)的跳數(shù)下降,從而展現(xiàn)出整體平均傳輸跳數(shù)的增加;而當(dāng)α較大時(shí),On-path 緩存機(jī)制的命中率較高,當(dāng)其比例提升時(shí),會(huì)較大幅度的降低往返跳數(shù),所以CSTC 的平均傳輸跳數(shù)開(kāi)始呈現(xiàn)出下降的趨勢(shì).但隨著RawCache 的比例不斷增大,其帶來(lái)的跳數(shù)下降也越來(lái)越微弱,而HashCache 比例的下降導(dǎo)致的跳數(shù)增加開(kāi)始顯現(xiàn),所以CSTC 的平均傳輸跳數(shù)開(kāi)始呈現(xiàn)上升趨勢(shì).

Fig.6 Impact of two-level cache ratio圖6 兩級(jí)緩存比例的影響

通過(guò)這一小節(jié)的分析,我們發(fā)現(xiàn)兩級(jí)緩存比例對(duì)請(qǐng)求命中率與平均傳輸跳數(shù)的影響在不同條件下是不一致的,它取決于On-path 緩存方式的命中率的高低.而影響On-path 緩存方式的命中率又受內(nèi)容熱度分布參數(shù)α和緩存大小等其他因素影響,所以我們認(rèn)為:在考慮兩級(jí)緩存比例對(duì)網(wǎng)絡(luò)性能的影響前,要先明確其他影響因素,不能一概而論.

4 結(jié)論

本文針對(duì)現(xiàn)有方案存在的緩存內(nèi)容效用較差、緩存位置不合理的問(wèn)題,提出了一種基于兩級(jí)緩存的緩存機(jī)制(CSTC).該方案通過(guò)引入兩級(jí)緩存,既保證了緩存的多樣性,又合理規(guī)劃了熱門(mén)內(nèi)容的緩存位置.仿真實(shí)驗(yàn)表明:CSTC 將次熱門(mén)內(nèi)容緩存數(shù)量提升了2 倍;緩存內(nèi)容數(shù)量的增加及緩存位置的優(yōu)化,使得命中率相比原有方案有大幅提升,即使與以高命中率為優(yōu)勢(shì)的哈希緩存策略相比,在緩存空間有限的情況下,CSTC 最高可將命中率提升45.4%;同時(shí),CSTC 有效降低了用戶(hù)請(qǐng)求的響應(yīng)時(shí)間,多數(shù)情況下,平均請(qǐng)求響應(yīng)往返跳數(shù)優(yōu)于現(xiàn)有主要的5 種緩存策略.內(nèi)容熱度的統(tǒng)計(jì)方法是影響CSTC 的關(guān)鍵因素之一,下一步工作將充分考慮內(nèi)容請(qǐng)求熱度的地域與時(shí)域性分布特征,考慮真實(shí)網(wǎng)絡(luò)中內(nèi)容熱度隨時(shí)間的動(dòng)態(tài)變化,進(jìn)一步研究?jī)?nèi)容熱度的動(dòng)態(tài)感知方法,以?xún)?yōu)化CSTC 的緩存性能.