命名數據網絡中適用于區分服務的緩存策略研究

陳秋瑤,鄭 烇

(中國科學技術大學 自動化系 未來網絡實驗室,合肥 230026)

0 概述

根據Cisco的視覺網絡指數(VNI)預測報告[1]可知,到2022年全球IP流量將增長5倍,年IP流量將達到4.8 ZB。為應對大規模內容分發的網絡需求,一種新型的以內容為中心的網絡(Information-Centric Network,ICN)架構被提出,該網絡架構的一種主流實現方式是命名數據網絡(Named Data Network,NDN)[3]。在NDN網絡中,每個內容有全球唯一命名,內容消費者根據內容名字發出興趣包獲取內容。網絡中的路由節點均可緩存內容,興趣包可在源服務器也可在路由節點上得到響應。

近年來,許多關于NDN的緩存研究通過設計和應用合理的緩存策略降低了服務器負載,減少了內容獲取時延和網絡帶寬消耗,但較少關注到內容所屬的服務類型以及不同服務類型的QoS需求差異,使得這些緩存算法難以應用在服務多樣、用戶需求復雜的實際場景。

Diffserv模型是在IP網絡中廣泛應用的區分服務模型。該模型根據流量特征及其服務的QoS要求將網絡中的流量劃分為12個種類,在路由節點中對每種流量類型規定單跳行為PHB(Per-Hop Behavior),同時結合流量監控、隊列管理功能,給不同的流量類型提供區分服務。

受Diffserv模型啟發,本文提出一種適用于NDN的區分服務緩存策略。通過簡化Diffserv模型的服務分類,建立緩存內容分類模型,并給出區分服務的概率緩存算法DiffCache。該算法同時考慮內容分類和網絡特性實現緩存資源的動態分配,使不同類型的內容具有不同的緩存命中率及下載時延,從而利用緩存資源滿足不同服務的QoS需求。

1 相關研究

緩存算法是NDN研究熱點之一[4-5],它考慮的問題是路由節點應緩存哪些內容以獲得更高的緩存命中率,減少內容下載時延和帶寬消耗。NDN中較為經典的緩存策略有LCE(Leave Copy Everywhere)[6]、LCD(Leave Copy Down)[7]及概率緩存Probability[8]。LCE是NDN默認的緩存策略,實現方式是路由節點不加區分地緩存每一個到達的內容。該算法簡單、速度快,但容易造成大量內容冗余。LCD僅在命中節點的下一跳緩存內容,使請求次數多的內容更快地到達網絡邊緣,彌補了LCE中大量內容冗余的不足,但內容通常要經過幾次請求才能到達網絡邊緣,當鏈路帶寬不足時不能有效利用緩存減少下載時延。概率緩存Probability對每個到達路由節點的內容以固定概率決定是否緩存,算法簡單高效,但存在隨機性。

在經典緩存算法的基礎上,研究者提出了基于內容流行度和致力于減少傳輸延遲的緩存算法[9-10]。在NDN中,內容流行度可分為內容原始流行度和路由節點本地流行度。路由節點本地流行度是指由路由節點統計到的內容流行度。由于對相同內容的未滿足請求會聚合在PIT表中,不再向上游節點轉發,因此路由器本地流行度通常與內容原始流行度有所區別。文獻[11]提出的OCPCP算法在路由節點中設置了一個閾值,當統計到某種興趣包請求數目到達該閾值時緩存對應的數據包。文獻[12]提出基于路由節點本地流行度的貪心緩存算法,將隨機的網絡拓撲解耦成有向無環圖,圖中每個節點緩存其本地流行度最高的部分內容,明顯提高了緩存內容的命中率。在致力于減少傳輸延遲的緩存算法中,文獻[13]證明了在瓶頸鏈路下游緩存單個內容副本能最大化緩存內容種類數量,最小化網絡平均下載時延,并提出了LAC(Latency Aware Cache)緩存算法,根據內容下載時延估計鏈路擁塞情況,用本次內容下載時延與t時刻前內容下載時延的比值來計算內容緩存概率,結合路由節點在鏈路中的位置做緩存決策。文獻[14]提出了基于RTT(Round Trip Time)的緩存算法,路由器通過計算本次內容的興趣包發出到數據包返回的時間與一個時間窗內內容往返時間的均值之比得到本次內容的緩存概率,然后使用該值做概率緩存。上述算法通過優先緩存流行度高的內容或下載時間長的內容,提高了緩存命中率,減少了下載時延和帶寬消耗,但是這些算法都將網絡中的內容同等對待,沒有考慮內容分類和區分服務,因此,不能很好地適用于需要給不同服務提供不同QoS質量的場景。

能對不同服務類型提供區分服務的Diffserv模型在IP網絡中研究較為成熟[15-17],RFC文檔中也有詳細描述[18-19]。最早將Diffserv模型用于NDN網絡的是文獻[20]提出的區分服務的轉發和緩存策略。緩存策略是將內容分類,由內容提供者標記內容屬于哪個分類并注冊到網絡提供商的內容列表中。當路由節點收到一個數據包時,先檢查該數據包是否在內容列表中,然后讀取數據包的標記判斷內容屬于哪個分類,并將內容緩存到該分類對應的緩存空間中。該模型實現了區分服務的緩存,但每種類型的緩存空間大小是固定配置的,不能隨各類內容數量變化動態調整,且會在數據包經過的沿路節點緩存內容,與LCE一樣容易造成內容冗余,浪費寶貴的緩存空間。文獻[21]提出的區分服務緩存算法給出每類內容的權重矩陣,利用反饋控制理論實現給不同類型的內容動態分配緩存空間,保證了不同類型內容的命中率在一個可接受范圍內波動。但該算法只是保持各類服務的命中率大小,沒有充分利用緩存資源來減少內容下載時延,且算法計算復雜,不能滿足NDN對緩存處理需要快速執行的要求。

綜上所述,如果能對NDN中的緩存內容做合理分類,把考慮到內容流行度和內容下載時延的緩存算法分別應用于不同類別的內容中,動態調整各類內容的緩存空間,將能更好地利用緩存資源滿足不同服務的QoS需求,更貼合NDN未來的實際使用場景。

2 DiffCache緩存算法

NDN網絡中的數據傳輸主要通過興趣包和數據包完成。一個典型的內容請求與響應在路由節點的處理過程如圖1所示。為使處理過程更適用于多種服務類型、多種QoS需求的場景,本文提出了NDN中的緩存內容分類模型與基于該分類模型的概率緩存算法DiffCache。在興趣包轉發過程中,當路由節點收到未在CS命中的請求時,在FIB中添加到達接口的記錄,并更新該內容的請求次數與請求到達時間。當源服務器返回數據包時,根據其服務的QoS需求從緩存內容分類模型中找到對應分類并做標記,該標記分類將作為沿途節點做緩存決策的依據之一。路由節點接收到數據包時,根據數據包的標記分類、路由節點統計的請求次數與等待內容響應時間做概率緩存。

圖1 NDN中內容請求與響應處理過程Fig.1 Content request and response process in NDN

合理的緩存內容分類模型有助于路由節點明確網絡中各種內容的優先級與其對應的服務要求,從而能做出更好的緩存決策。結合同時考慮內容分類和網絡特性的緩存算法DiffCache,把有限的緩存空間分配給高優先級、高QoS要求的內容,實現了緩存資源的動態分配,更好地利用了緩存資源滿足不同服務的QoS需求。

2.1 緩存內容分類模型

本文提出的緩存內容分類模型基于IP網絡中的Diffserv模型。下文介紹Diffserv模型中對流量的分類方式以及緩存內容分類模型,并說明如何將Diffserv模型中的內容分類對應到緩存內容分類中,最后應用緩存內容分類模型對Cisco VIN預測的未來流量進行分類,說明該模型有較好的適應性。

網絡中的內容有多種分類方式,Diffserv模型中推薦的分類方式是將內容分為網絡控制(Network Control)和用戶/訂閱者流量(User/Subscriber Traffic)兩大類,每類下再根據流量特征和對抖動、丟包及延遲的容忍程度分出共12種服務類型,網絡管理員可根據實際需要在這12類服務類型中做進一步細分[18]。

與Diffserv模型類似,緩存內容分類模型中首先按是否需要緩存將網絡中的內容分為無需緩存(No Cache,NC)和需要緩存(Do Cache,DC)兩大類。部分內容時效性強,過期時間短,且一般不會被重復請求,緩存這些不能重復利用的內容會浪費寶貴的緩存空間,因此將其歸類于無需緩存。

在需要緩存的內容分類中,依據內容對應的服務對于QoS中延遲指標的要求高低,進一步將內容細分為盡力而為和減少延遲2種類型。此處選擇延遲需求作為分類依據的原因是:減少下載延遲是緩存能帶來的最直接的優點——當一個請求能在網絡內緩存命中時,不必從源服務器獲取內容,那么就可節省從源服務器到命中節點這段路徑的傳輸時間。由于抖動是衡量分組傳輸延遲的指標,是由網絡擁塞時的排隊時延變化引起的,其能帶來的好處不直接,在緩存內容分類模型中不以該指標作為依據。同樣地,對于分組丟失或比特丟失引起的丟包緩存帶來的好處也不直接,故對丟包率高低的需求不作為緩存內容分類的依據。

緩存內容分類模型中將內容分為了無需緩存(NC)、盡力而為(BE)和減少延遲(Less Delay,LD)3種,其中BE和LD屬于需要緩存的大類,下面將Diffserv模型中的服務分類對應到緩存內容分類中,可以看到兩者能很好地兼容。

在Diffserv的12種服務類型中,網絡控制服務和OAM(Operations,Administrations and Management)服務屬于網絡控制這一大分類,它們的傳輸要求低延遲,但對抖動容忍程度高。由于這一類服務的內容通常不會被重復請求,因此在緩存內容分類模型中將這一類內容歸類為NC。另一類屬于NC分類的內容特征是具有強時效性,過期時間短,包括電話、信號、多媒體會議和實時互動4種內容。其余分類的內容可重復利用,因此被歸類于需要緩存。對于多媒體流、廣播視頻和低延遲數據3類內容,由于它們對延遲要求較高,可將其歸類于LD。而對于高吞吐量內容、標準內容和低優先級內容,由于它們的可容忍延遲時間較長,將其歸類于BE。上述內容分類總結如表1所示。

表1 緩存內容分類模型Table 1 Cache content classification model

除了能與Diffserv模型中的服務分類良好兼容外,緩存內容分類模型也可以很好地應用在未來流量的分類中。據Cisco的VNI預測報告,未來幾年的IP網絡流量中視頻流量將占到82%[1],包括短視頻、長視頻、直播視頻、網絡電視、在線視頻購物及網絡視頻監控。其余流量還有網頁、郵件、即時通信、共享文件、在線游戲等。按照上述方法,緩存內容分類模型中的分類如郵件、即時通信、在線游戲、在線視頻購物及網絡視頻監控等實時性強,可歸類于NC。直播視頻、網絡電視需要減少延遲,且內容在一個時間段內可以重復利用,因此,將其歸類于LD。長視頻、短視頻、網頁、共享文件等內容由于缺少明確的實時性要求,可歸類于BE。Cisco VNI預測流量類型的分類如表2所示。

表2 Cisco VNI預測流量類型的分類Table 2 Classification of Cisco VNI predicted traffic types

與Diffserv模型類似,若考慮到不同用戶、內容提供商的優先級等服務要求,在每個分類下可進一步細分出其他類型。

2.2 DiffCache緩存算法

基于上述的緩存內容分類模型,DiffCache算法同時考慮內容分類與網絡特性,根據內容類別、路由節點本地流行度和內容等待時間計算出每個內容的緩存概率,由路由節點做概率緩存。算法通過給不同類別的內容以不同的緩存概率實現動態分配緩存資源,從而能更好地利用緩存資源滿足不同服務的QoS需求。

在DiffCache算法中,每個內容c在路由節點n上的緩存概率Pc,n由式(1)計算得出:

(1)

(2)

(3)

其中,參數的含義與取值如下:

1)clc是內容在緩存內容分類模型中所屬類別對應的數值,內容分類由源服務器在返回數據包時予以標記,類別對應數值由路由節點查詢內容分類表獲取。

4)α、β、γ是對應項的權重因子,三者之和等于1。

表3 內容分類表示例Table 3 Example of content classification representation

表4 PIT表示例Table 4 Example of PIT representation

圖2 DiffCache算法應用示例Fig.2 Example of DiffCache algorithm

3 實驗結果與分析

3.1 實驗參數與設置

由于文獻[20]的緩存算法結合了相應的轉發算法,單獨實驗緩存算法進行比較的結果不準確,文獻[21]所提的算法涉及權重矩陣計算與反饋控制,計算復雜,不滿足NDN中緩存需要快速執行的要求,本文采用NDN中經典的緩存策略LCE、LCD和Probability作為對照組,其中Probability設置的緩存概率為0.7。

3.2 結果分析

圖3和圖4是4種緩存策略的路由節點平均命中率和內容下載時延。

圖3 平均命中率隨緩存容量的變化Fig.3 Average hit rate varying with cache capacity

圖4 內容下載時延隨緩存容量的變化Fig.4 Average download latency varying with cache capacity

從圖中可以看到,隨著緩存空間的增加,各算法的緩存命中率均增大,內容下載時延減少,其中DiffCache算法的命中率增幅達7.34倍,下載時延減少約一半。由于DiffCache算法將緩存空間分配給了可重復利用的LD及BE類型內容,因此即使少緩存了部分內容,總體命中率與內容下載時延仍稍優于其余3種算法。在下載時延方面,當緩存空間較小時,LCD算法略優,但是當緩存空間增大到內容總數的0.03時,DiffCache表現逐漸優于LCD算法。當緩存空間為內容總數的0.1時,DiffCache算法對比LCD算法減少了15.38%,這是由于DiffCache算法優先緩存下載延時大的內容,能更快地將下載時間長的內容緩存在邊緣節點,而LCD算法可能由于內容替換過快,使得內容難以移動到用戶附近。

圖5和圖6是LD類型內容的緩存命中率與下載時延,圖7和圖8是BE類型內容的緩存命中率和下載時延,可以看到2種類型內容的評價指標均好于另外3種算法,且LD和BE類型在內容評價指標上有明顯區分,當緩存空間較小時,LD類型內容的命中率比BE類型約高8.77%,下載時延比BE類型減少了約11.43%。隨著緩存空間的增大,不同類型的內容間的命中率及下載時延區分更明顯。圖9和圖10是在實驗過程中LD類型及BE類型在路由節點的緩存中所占比例。

圖5 LD類型平均命中率隨緩存容量的變化Fig.5 Average hit rate of LD types varying with cache capacity

圖6 LD類型下載時延隨緩存容量的變化Fig.6 Download latency of LD types varying with cache capacity

圖7 BE類型平均命中率隨緩存容量的變化Fig.7 Average hit rate of BE types varying with cache capacity

圖8 BE類型下載時延隨緩存容量的變化Fig.8 Download latency of BE types varying with cache capacity

圖9 緩存中的LD類型占比Fig.9 Proportion of LD types in cache

圖10 緩存中的BE類型占比Fig.10 Proportion of BE types in cache

在DiffCache算法中,LD類型的內容緩存所占比例約為71.2%,BE類型的內容緩存所占比例約為28.8%,與其他3種算法相比,DiffCache實現了在不同類型的內容間動態分配緩存。

本文通過簡化Diffserv模型的服務分類,建立一個新的緩存內容分類模型,根據NDN上不同內容的流量特征及其服務的QoS要求,將內容分為無需緩存(No Cache,NC)、盡力而為(Best Effort,BE)及減少延遲(Less Delay,LD)類。然后,提出區分服務的概率緩存算法DiffCache,即對這3類內容根據內容提供商的推薦分類、路由器本地流行度及內容等待響應時間計算出不同緩存概率,路由節點對到達的內容做概率緩存。該算法同時考慮內容分類和網絡特性,實現了緩存資源的動態分配,使不同類型的內容具有不同的緩存命中率及下載時延,從而能更好地利用緩存資源滿足不同服務的QoS需求,且算法復雜度低,執行速度快,擴展性好。

4 結束語

本文借鑒IP網絡中區分服務的Diffserv模型,提出一個用于NDN的緩存內容分類模型,并基于該模型設計分類緩存算法DiffCache。該算法同時考慮內容分類和網絡特性,結合內容提供商指定的分類、路由節點統計的本地流行度及路由節點記錄的下載時間,對每個到達路由節點的內容分配不同的緩存概率。仿真結果表明,與經典NDN緩存算法相比,DiffCache算法在不影響全局命中率和內容下載延時的情況下,能準確區分每種內容類型的性能指標表現,從而能更好地利用緩存資源滿足不同服務對于延遲的QoS需求。本文的緩存內容模型只是簡單地將緩存內容分為3類,下一步將研究更精細的緩存內容分類模型,以更好地適應網絡變化的情況。