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

1(中國科學院 計算技術研究所,北京 10019 0)

2(中國科學院大學,北京 10 0190)

3(金美通信,重慶 400030)

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

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

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

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

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

1)提出一種分級緩存框架,將每個節(jié)點的緩存空間分為RawCache 和HashCache 兩部分:針對RawCache,各節(jié)點基于本地熱度感知進行獨立緩存決策;針對HashCache,通過哈希機制構成域內多節(jié)點間協(xié)作,實現(xiàn)了域內熱度的分布感知及決策,為不同層次的熱度內容提供不同的緩存策略;

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

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

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

1 相關工作及問題分析

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

1.1 On-path緩存策略

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

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

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

各種On-path 緩存策略的共同特點是,網絡節(jié)點只與其請求路徑上游或下游的某些節(jié)點進行協(xié)作.這一共性限制了網絡化緩存的潛在性能提升.由于缺乏全局拓撲視圖與緩存狀態(tài)相關信息,緩存策略只能基于單節(jié)點、單條傳輸路徑對緩存進行優(yōu)化,這就限制了網絡性能提升的上界,也帶來了如下幾個方面的問題.

1)緩存大量冗余.由于各節(jié)點獨立進行緩存決策,同一網絡中各節(jié)點請求分布又基本一致,導致同一層各節(jié)點緩存下的內容基本相同.有限的緩存空間和大量重復的內容,給ICN 網絡帶來了更大的挑戰(zhàn);

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

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

1.2 基于哈希的緩存策略

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

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

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

基于哈希的緩存策略通過設計一種內容分配方案,將內容的緩存任務分配到域內特定的網絡節(jié)點.這種方式有效解決了緩存冗余問題,提高了緩存命中率,但也帶來了一些新的問題.

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

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

1.3 混合緩存策略

關于結合不同緩存策略的緩存機制最近已有不少研究,主要包括基于網絡結構的混合緩存策略以及基于內容熱度的混合緩存策略.

基于網絡結構的混合緩存策略根據節(jié)點所處位置為不同節(jié)點提供不同的緩存策略.Zhang 等人[20]提出將網絡分成一個核心域和多個邊緣域,在核心域使用基于哈希的緩存策略,在邊緣域使用On-path 的緩存策略.該方法實際上是一種多域協(xié)作的部署策略.節(jié)點間緩存策略的融合,雖然在整體上提升了網絡性能,但對于單個域本身來說,緩存性能并沒有改變,因為域內應用的還是原有的緩存策略.該方法并不能解決緩存內容在邊緣節(jié)點過度冗余的問題.

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

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

2 CSTC 運行機制

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

2.1 CSTC基本框架

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

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

1)最熱門內容應在網絡邊緣適度冗余,減少用戶請求跳數.Fayazbakhsh 等人[26]通過大量仿真實驗證明:僅僅簡單地在網絡邊緣部署足夠大的緩存,就能達到可觀的網絡性能提升.這正是熱門內容在網絡邊緣冗余帶來的效果.讓用戶的多數請求在網絡邊緣節(jié)點得到滿足,不僅減少了用戶的請求時間,也極大降低了網絡負載;

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

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

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

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

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

Fig.1 T wo-level cache for CSTC圖1 CSTC 兩級緩存

2.2 CSTC熱度篩選

內容熱度是影響網絡緩存性能的關鍵.相比于常見的利用內容請求次數來表示內容熱度,本節(jié)設計了基于內容命中次數的熱度統(tǒng)計方法,主要基于以下考慮.

1)由于網絡中的內容非常多,統(tǒng)計所有內容的請求數是不現(xiàn)實且不必要的.為了降低時間空間開銷,我們只針對已緩存的內容進行請求次數的統(tǒng)計,已緩存內容的請求次數即為內容的命中數;

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

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

?name:目標內容名字;

?hit:內容命中次數,非負整數;

?popularity:內容在域內的熱度,非負整數;

?time:列表項上次更新時間.

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

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

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

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

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

2.3 CSTC路由策略

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

表1 中,當節(jié)點收到Interest 請求時,首先會查找自身內容存儲表(content st ore,CS)與待定請求表(pending interest ta ble,簡稱PIT),看是否有內容命中.若都沒有命中,則根據哈希映射得到目標節(jié)點,并向其轉發(fā)(第5 行).若Interest 到達目標節(jié)點后仍沒有命中,則將Interest 轉發(fā)至內容源(第3 行).

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

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

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

3 仿真實驗

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

3.1 實驗環(huán)境與配置

考慮到一個請求域的大小,我們選擇了美國愛荷華州的一個真實拓撲結構[29]作為仿真拓撲網絡,該拓撲共有30 個節(jié)點、38 條邊.為了合理模擬真實網絡狀態(tài),當內容在域內未命中時,我們設置的出域路由的請求跳數為10 跳.每個節(jié)點都連接有一組用戶,不間斷地連續(xù)模擬發(fā)起內容請求,用戶請求服從泊松分布.仿真實驗中共有100 萬個不同的內容,我們假設內容整體上服從參數為α的Zipf 分布,也就是說,排名第k的熱門內容的請求概率為:

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

Table 3 P arameters of experiments表3 實驗參數

3.2 對比方案與性能指標

仿真實驗中采用的緩存方案包括如下幾種.

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

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

?LCE:多數ICN 默認緩存策略,即節(jié)點無差別的緩存所有內容[12];

?Prob(p):每個節(jié)點以固定概率p緩存經過的所有內容,我們設置的p=0.05;

?ProbCache:一種基于加權概率的緩存策略,距離請求者越近、存儲空間越大的節(jié)點,緩存該內容的概率越大;

?BidCache:我們實現(xiàn)了文獻[9]中的BidCache 緩存機制,這是一種近年來較為典型的On-path 協(xié)作式緩存策略,它利用較少的代價進行路徑上節(jié)點的通信,結合網絡的拓撲實現(xiàn)緩存決策.

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

(1)請求命中率

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

其中,Numhit表示請求在該節(jié)點的命中次數,Numtotal表示請求總數,i表示第i個節(jié)點.

(2)平均傳輸跳數

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

其中,hopinterest表示Interest 請求所用跳數,hopdata表示Data 返回所用跳數,Numtotal指總請求數.

3.3 實驗結果

3.3.1 緩存內容分布

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

Fig.3 Distribution of cache圖3 緩存內容分布

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

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

3.3.2 緩存大小的影響

緩存大小決定了緩存內容的多少,是影響緩存性能的重要因素之一.本節(jié)分析了不同緩存空間大小對緩存性能的影響.我們設置的緩存空間大小變動范圍為500~7000,其他實驗參數保持不變,觀察請求命中率與平均傳輸跳數的變化.

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

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

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

3.3.3 內容熱度的影響

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

Fig.5 Impact of content popularity圖5 內容熱度的影響

3.3.4 兩級緩存比例的影響

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

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

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

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

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

4 結論

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