楊曉非 丁志鵬 張宏宇 牛翠翠 黃 勝
內(nèi)容中心網(wǎng)絡(luò)中一種降低自治域內(nèi)內(nèi)容傳輸代價的緩存策略
楊曉非 丁志鵬 張宏宇 牛翠翠 黃 勝
(重慶郵電大學(xué)光纖通信技術(shù)重點(diǎn)實(shí)驗(yàn)室 重慶 400065)
內(nèi)容中心網(wǎng)絡(luò)(CCN)是未來互聯(lián)網(wǎng)中一種有前景的網(wǎng)絡(luò)架構(gòu)。它通過網(wǎng)內(nèi)緩存機(jī)制加強(qiáng)內(nèi)容的傳輸減少網(wǎng)絡(luò)傳輸代價或提高網(wǎng)絡(luò)吞吐量。針對同一個自治域內(nèi)的內(nèi)容分布情況以及熱門內(nèi)容對網(wǎng)絡(luò)的影響,提出一種以降低內(nèi)容傳輸代價為目標(biāo)的緩存機(jī)制——DCR策略。該策略能夠?qū)衢T內(nèi)容推向用戶同時降低內(nèi)容的冗余度。實(shí)驗(yàn)結(jié)果表明:該緩存策略能有效地降低自治域內(nèi)內(nèi)容的傳輸代價,提高了域內(nèi)緩存命中率。
內(nèi)容中心網(wǎng)絡(luò) 緩存機(jī)制 冗余度 內(nèi)容傳輸代價 緩存命中率
現(xiàn)如今,內(nèi)容數(shù)據(jù)的爆炸式增長使得內(nèi)容傳輸開始成為網(wǎng)絡(luò)中最為關(guān)鍵的一環(huán)。因此,傳統(tǒng)的TCP/IP網(wǎng)絡(luò)開始顯露它的靈活性和可靠性等方面的缺陷。在這種情況下出現(xiàn)了一批關(guān)于未來互聯(lián)網(wǎng)體系架構(gòu)的研究。這其中有UC Berkeley RAD實(shí)驗(yàn)室提出的“面向數(shù)據(jù)的網(wǎng)絡(luò)架構(gòu)”DONA(Data-Oriented Network Architecture)[1]、“發(fā)布/訂閱式互聯(lián)網(wǎng)路由范例”PSIRP(Publish-Subscribe Internet Routing Paradigm)[2]。內(nèi)容中心網(wǎng)絡(luò)(CCN)[3,4],這個由施樂公司帕洛阿托研究中心的Van Jacobson等人提出的網(wǎng)絡(luò)架構(gòu)現(xiàn)在已經(jīng)成為了未來互聯(lián)網(wǎng)的研究熱點(diǎn)。
緩存策略是當(dāng)前CCN中的一個研究熱點(diǎn)。在CCN中,每一個節(jié)點(diǎn)都包含一個內(nèi)容庫用來存儲數(shù)據(jù)。CCN中的內(nèi)容庫可以長時間存儲經(jīng)過的數(shù)據(jù)包以便服務(wù)其他節(jié)點(diǎn)發(fā)來的請求。最近已經(jīng)有不少文獻(xiàn)致力于CCN中內(nèi)容存儲策略的研究。文獻(xiàn)[3]提出了一種叫作LCE(Leaving copies everywhere)的緩存策略,該策略中,節(jié)點(diǎn)存儲每個經(jīng)過的數(shù)據(jù)包,該策略由于復(fù)雜度低和易用性得到了廣泛的使用。文獻(xiàn)[5]提出了一種叫做PCP的緩存策略,該策略主要的目標(biāo)是盡量避免邊緣節(jié)點(diǎn)存儲冷門內(nèi)容,而將熱門內(nèi)容盡可能推向離用戶更近的敵方。文獻(xiàn)[6]中提出的ProbCache機(jī)制決定在內(nèi)容傳輸路徑上依概率存儲內(nèi)容。文獻(xiàn)[7]中的MPC機(jī)制提出當(dāng)內(nèi)容被請求的次數(shù)超過一個門限值時就將該內(nèi)容存儲在其鄰居節(jié)點(diǎn)中。文獻(xiàn)[8]中提出的合作緩存機(jī)制是節(jié)點(diǎn)根據(jù)鄰居節(jié)點(diǎn)的內(nèi)容存儲情況來決定自身存儲的內(nèi)容。文獻(xiàn)[9]中提出了一種叫做WAVE的存儲機(jī)制,該機(jī)制為每一個內(nèi)容維持了一個用來記錄該內(nèi)容流行度信息的值來決定該內(nèi)容需要被存儲的數(shù)據(jù)塊的數(shù)量。文獻(xiàn)[10]中提出了一種依概率存儲的緩存機(jī)制,該策略中節(jié)點(diǎn)以一定概率存儲經(jīng)過的數(shù)據(jù)包,相比LCE策略降低了數(shù)據(jù)的冗余度。
然而,上述的緩存合作機(jī)制都只考慮了內(nèi)容在單一路徑上傳輸時如何進(jìn)行緩存,并且沒有考慮內(nèi)容在自治域中時的特殊性,因此會造成網(wǎng)絡(luò)中的內(nèi)容冗余度較高和命中率較低。全球的因特網(wǎng)被分成很多個自治域,不同的運(yùn)營商往往在不同的自治域內(nèi),用戶請求的內(nèi)容在自治域內(nèi)被滿足和在自治域外被滿足有著明顯的區(qū)別。由文獻(xiàn)[3]可知,由于CCN網(wǎng)絡(luò)協(xié)議與TCP/IP協(xié)議的相似性,使得CCN可以架構(gòu)在任何底層協(xié)議之上甚至是IP協(xié)議。因此,CCN可以保持現(xiàn)有的互聯(lián)網(wǎng)域內(nèi)域間特征并且在現(xiàn)有的TCP/IP網(wǎng)絡(luò)之上運(yùn)行CCN。因?yàn)橛騼?nèi)的鏈路帶寬資源通常要比域間鏈路帶寬的更充裕,而且在域內(nèi)獲取資源比在域外的代價更小。所以我們希望用戶發(fā)出的請求盡可能在域內(nèi)被滿足。這樣,如何在域內(nèi)合理地分配內(nèi)容成為了一個問題。針對上述問題,本文提出一種以降低自治域內(nèi)內(nèi)容傳輸代價為目標(biāo)的緩存策略,該策略可以有效地減少內(nèi)容在自治域內(nèi)傳輸?shù)拇鷥r,同時提高內(nèi)容在域內(nèi)的平均命中率。
1.1 CCN基本原理
由Jacobson等人在文獻(xiàn)[3]中提出的內(nèi)容中心網(wǎng)絡(luò)(CCN)的核心是以內(nèi)容為主體,每個內(nèi)容都被它的名字所標(biāo)識,而不再關(guān)心內(nèi)容所在的位置。CCN通信過程中存在兩種類型的包:興趣包和數(shù)據(jù)包。興趣包由用戶發(fā)出用來請求用戶需要的內(nèi)容,數(shù)據(jù)包包含了被興趣包請求的數(shù)據(jù)。每一個CCN節(jié)點(diǎn)包含了以下三種結(jié)構(gòu):內(nèi)容庫CS、未決請求表PIT和轉(zhuǎn)發(fā)信息庫FIB。其中,CS可以在內(nèi)容被轉(zhuǎn)發(fā)到別的接口之后也長時間保存經(jīng)過的內(nèi)容的副本;PIT建立了一個列表用來存放每一個沒有被滿足的興趣包的信息;FIB用來記錄內(nèi)容應(yīng)該被發(fā)往的下一個接口信息。當(dāng)節(jié)點(diǎn)收到一個興趣包時,會依次在CS、PIT和FIB中進(jìn)行查找,若CS中沒有匹配的內(nèi)容,則在PIT中查找;若PIT中有相應(yīng)的條目,則將請求接口加入PIT請求接口列表中,并丟棄該興趣包,否則繼續(xù)在FIB表中查找,若找到相應(yīng)條目,則將該興趣包轉(zhuǎn)發(fā)到對應(yīng)的鄰居節(jié)點(diǎn),同時建立相應(yīng)的PIT條目;若FIB中未查找到相關(guān)條目,則丟棄該興趣包。興趣包被滿足之后,數(shù)據(jù)包嚴(yán)格按照興趣包的發(fā)送路線原路返回至用戶。
CCN的網(wǎng)內(nèi)存儲使得它比傳統(tǒng)的TCP/IP網(wǎng)絡(luò)傳輸內(nèi)容更快,但同時也帶來了一個問題,那就是,怎么樣在網(wǎng)絡(luò)中分配內(nèi)容數(shù)據(jù)才能使網(wǎng)絡(luò)的性能最優(yōu)。這里的最優(yōu)指的是內(nèi)容在自治域內(nèi)的傳輸代價最小,本文中考慮內(nèi)容傳輸?shù)奶鴶?shù)為代價。鑒于CCN網(wǎng)絡(luò)中內(nèi)容的請求服從特定的流行度模型,所以絕大部分的請求都發(fā)生在少數(shù)的熱門內(nèi)容上,因此,我們的重點(diǎn)是如何減少熱門內(nèi)容的傳輸代價。當(dāng)一個節(jié)點(diǎn)接收到數(shù)據(jù)包時,它首先會檢查PIT列表中有沒有相應(yīng)的條目,如果有的話就給相應(yīng)條目的接口發(fā)送數(shù)據(jù)包的副本,否則的話就根據(jù)需要選擇存儲該數(shù)據(jù)包或者將其丟棄。在傳統(tǒng)的CCN中,默認(rèn)的緩存策略是數(shù)據(jù)包經(jīng)過興趣包所經(jīng)過的路徑上的每一個節(jié)點(diǎn)時都被存儲在該節(jié)點(diǎn)的CS中。這樣的存儲策略簡單快捷,但是,卻會使網(wǎng)絡(luò)的中冗余的內(nèi)容副本過多,從而導(dǎo)致大量的用戶請求不得不發(fā)往更遠(yuǎn)的服務(wù)器或者域外獲取內(nèi)容,使得網(wǎng)絡(luò)的傳輸代價過高。
考慮到上述問題,本文提出了一種基于貪婪算法的緩存策略——DCR(Delivery Cost Reduce)策略來降低內(nèi)容的傳輸代價。該策略的主要思想是盡可能將更多的熱門內(nèi)容保存在當(dāng)前自治域中,并通過將熱門內(nèi)容分布在更合理的位置降低自治域中總的內(nèi)容傳輸帶價。
1.2 DCR策略
在本文中,網(wǎng)絡(luò)中內(nèi)容的“冷熱”程度是根據(jù)內(nèi)容的流行度來劃分的,內(nèi)容的流行度定義為單位時間內(nèi)該內(nèi)容收到的請求數(shù)。也就是內(nèi)容的流行度越高,該內(nèi)容就越“熱門”。根據(jù)Zipf定律,絕大部分的請求往往是針對少部分熱門內(nèi)容的。因此,合理的調(diào)整熱門內(nèi)容在自治域中的數(shù)量和位置,可以有效地降低自治域中總的內(nèi)容傳輸帶價,降低用戶獲取內(nèi)容的時延。
當(dāng)一個節(jié)點(diǎn)接收到一個熱門內(nèi)容并且需要發(fā)生替換行為時,傳統(tǒng)的緩存策略往往是簡單地將流行度最低的內(nèi)容替換掉。而如果當(dāng)該內(nèi)容也是熱門內(nèi)容且在自治域中只有一個或很少數(shù)量的副本時,這種替換就可能使得用戶需要從域外獲取該內(nèi)容,反而增大網(wǎng)絡(luò)的負(fù)擔(dān)和消耗。因此,在本文提出的DCR策略中,提出了將兩內(nèi)容“交換”的概念來處理上述的情況。此外,每當(dāng)有內(nèi)容在節(jié)點(diǎn)中存儲時,我們讓該節(jié)點(diǎn)通知所有邊緣節(jié)點(diǎn)建立相應(yīng)的FIB條目,使得用戶發(fā)出的請求的目的地址更明確,這有利于減少自治域中冗余內(nèi)容副本的數(shù)量。
我們定義交換增益Gijic,表示將從ij處發(fā)出的熱門內(nèi)容j到達(dá)熱門內(nèi)容c所在的節(jié)點(diǎn)ic時,若交換j和c的位置所帶來的全局代價節(jié)省。
其中Mic和Mij分別表示從ic和ij處獲取內(nèi)容c和j的邊緣節(jié)點(diǎn)的集合,uoicc、uoijj、uoijc和uoicj分別表示邊緣節(jié)點(diǎn)o從ic獲取內(nèi)容c、邊緣節(jié)點(diǎn)o從ij獲取內(nèi)容j、邊緣節(jié)點(diǎn)o從ij獲取內(nèi)容c和邊緣節(jié)點(diǎn)o從ic獲取內(nèi)容j的請求數(shù),coic和coij分別表示邊緣節(jié)點(diǎn)o到節(jié)點(diǎn)ic以及邊緣節(jié)點(diǎn)o到節(jié)點(diǎn)ij的傳輸代價。當(dāng)需要進(jìn)行是否緩存內(nèi)容的決策時,計算需要緩存的內(nèi)容j和當(dāng)前緩存流行度最低的熱門內(nèi)容c的交換增益。若增益大于零則將兩內(nèi)容進(jìn)行交換,否則不進(jìn)行交換。具體算法步驟如下:
第一步 任意熱門內(nèi)容j到達(dá)節(jié)點(diǎn),若該節(jié)點(diǎn)有剩余空間則存儲j,通知邊緣節(jié)點(diǎn)建立相應(yīng)的FIB條目,算法結(jié)束,否則跳至第二步;
第二步 判斷j的流行度是否高于當(dāng)前節(jié)點(diǎn)流行度最低的熱門內(nèi)容c的流行度,若否,算法結(jié)束,否則跳至第三步;
第三步 判斷c在整個自治域內(nèi)的副本數(shù)量是否大于1,若是,則用j替換c,通知邊緣節(jié)點(diǎn)建立和刪除相應(yīng)的FIB條目,算法結(jié)束,否則跳至第四步;
第四步 計算j和c的交換增益Gijic,若Gijic>0則將j和c交換存儲位置,通知邊緣節(jié)點(diǎn)更新相應(yīng)的FIB條目,算法結(jié)束,若Gijic<0則算法結(jié)束。
在DCR算法中,我們假設(shè)從域外獲取內(nèi)容的代價遠(yuǎn)高于從域內(nèi)獲取相同內(nèi)容的代價。興趣包在被邊緣節(jié)點(diǎn)發(fā)出時會攜帶該邊緣節(jié)點(diǎn)的信息,當(dāng)其在某個節(jié)點(diǎn)或服務(wù)器被滿足時,相應(yīng)的數(shù)據(jù)包從該興趣包上獲取邊緣節(jié)點(diǎn)的信息,同時,每個數(shù)據(jù)包會記錄其被請求的次數(shù)信息以供計算增益。每隔一段時間,數(shù)據(jù)包會將記錄的請求次數(shù)信息更新。我們利用CCN中某一時間段某內(nèi)容所在節(jié)點(diǎn)的PIT列表中接口數(shù)目來判斷該內(nèi)容在自治域中存在的數(shù)量。若某一段時間內(nèi)該內(nèi)容所對應(yīng)的PIT列表接口數(shù)目小于邊緣節(jié)點(diǎn)的數(shù)目,則說明該內(nèi)容的副本在自治域內(nèi)不止一個,反之亦然。該算法基于分布式方式實(shí)現(xiàn),能以較小的代價和較低的復(fù)雜度完成內(nèi)容的分配。
本文使用基于NS-3的仿真軟件ndnSIM[13,14]來搭建仿真平臺。仿真使用的網(wǎng)絡(luò)拓?fù)錇镹SFNet,如圖1所示。其中,A、B、C、D四個節(jié)點(diǎn)為邊緣節(jié)點(diǎn),邊緣節(jié)點(diǎn)發(fā)出的請求如果未在域內(nèi)被滿足會被發(fā)往代表域外的X節(jié)點(diǎn),假設(shè)用戶發(fā)出的請求總可以在域外被滿足。每個邊緣節(jié)點(diǎn)依據(jù)Zipf定律以500個/秒的速率同時產(chǎn)生興趣包,假設(shè)內(nèi)容的總數(shù)為10 000個,Zipf指數(shù)a=0.75,熱門內(nèi)容占總內(nèi)容數(shù)的20%,數(shù)據(jù)包更新請求信息間隔為2 s。我們比較不同緩存容量對網(wǎng)絡(luò)性能的影響,本文的緩存容量指的是緩存大小占總內(nèi)容大小的百分比,取值范圍為1.8%~60%。
圖1 NSFNet
本文考慮的對比算法如下:(1) LCE[3]。LCE策略是目前CCN網(wǎng)絡(luò)中使用最廣泛的緩存策略。在LCE中,節(jié)點(diǎn)將經(jīng)過的每個數(shù)據(jù)包都保留一份副本在其CS中,替換策略使用LRU策略。(2) 依概率存儲策略[15],節(jié)點(diǎn)以一定概率存儲經(jīng)過的數(shù)據(jù)包,本文中用Prob表示這種策略,存儲概率設(shè)為0.7。
本文考慮的網(wǎng)絡(luò)性能評價指標(biāo)如下:(1) 域內(nèi)緩存命中率。域內(nèi)緩存命中率是指在自治域內(nèi)被滿足的興趣包的數(shù)量占用戶發(fā)出的所有興趣包的總大小的比值。(2) 平均訪問時延。平均訪問時延指的是用戶發(fā)出興趣包到收到數(shù)據(jù)包所消耗的時間的均值。(3) 域內(nèi)跳數(shù)節(jié)省率[15]。域內(nèi)跳數(shù)節(jié)省率指的是使用緩存策略時數(shù)據(jù)包的平均響應(yīng)跳數(shù)與不使用緩存策略時數(shù)據(jù)包的平均響應(yīng)跳數(shù)的比值。其中,數(shù)據(jù)包的平均響應(yīng)跳數(shù)指的是數(shù)據(jù)包從節(jié)點(diǎn)或者服務(wù)器到達(dá)用戶所經(jīng)過的跳數(shù)。
圖2顯示了不同緩存容量下各緩存策略域內(nèi)緩存命中率的情況??梢钥闯?,DCR策略由于對自治域內(nèi)熱門內(nèi)容的全局考慮和合理分配,獲得了更高的域內(nèi)命中率。相比之下,由于其余兩種策略沒有從全局考慮內(nèi)容對網(wǎng)絡(luò)性能的影響,因此造成了命中率低下。
圖2 域內(nèi)緩存命中率隨緩存容量變化曲線
圖3顯示的是不同緩存容量下各緩存策略平均訪問時延的情況。從圖中可以看出,DCR策略的平均訪問時延大大低于其他兩種緩存策略。這是因?yàn)镈CR策略將用戶的請求更多地導(dǎo)向自治域內(nèi)的資源,從而使得用戶可以在更近的地方獲取到內(nèi)容,減少了用戶獲取內(nèi)容的時間。而其他兩種策略因?yàn)闆]有考慮內(nèi)容的流行度區(qū)別,使得更多的冷門資源存在于自治域內(nèi),從而導(dǎo)致大量熱門內(nèi)容請求需要到域外被滿足,因而增大了訪問時延。
圖3 平均訪問時延隨緩存容量變化曲線
圖4顯示的是不同緩存下各緩存策略域內(nèi)跳數(shù)節(jié)省率的情況。可以看出,本文提出的DCR策略的域內(nèi)跳數(shù)節(jié)省率明顯高于LCE和Pro策略,也就說明了DCR策略可以有效地減少內(nèi)容在自治域中傳輸?shù)拇鷥r。這得益于DCR策略對自治域內(nèi)熱門內(nèi)容的全局考慮。
圖4 域內(nèi)跳數(shù)節(jié)省率隨緩存容量變化曲線
CCN作為未來互聯(lián)網(wǎng)中一種新興的網(wǎng)絡(luò)架構(gòu),能有效地緩解網(wǎng)絡(luò)擁塞狀況,提升用戶體驗(yàn),然而,它也存在著一些問題。本文將CCN中內(nèi)容放入自治域內(nèi)考慮,提出了一種以降低內(nèi)容傳輸代價為目的的緩存策略——DCR策略。該策略將自治域內(nèi)的熱門內(nèi)容作為考慮對象,通過計算內(nèi)容能給網(wǎng)絡(luò)帶來的代價增益合理分配內(nèi)容的位置。仿真結(jié)果驗(yàn)證了本策略的有效性。接下來的工作中,將考慮DCR策略對網(wǎng)絡(luò)其他性能的影響,例如網(wǎng)絡(luò)帶寬消耗等。
[1] Koponen T,Chawla M,Gon C B,et al.A data-oriented (andbeyond) network architecture[C]//Proceedings of the ACMSIGCOMM 2007 Conference,Kyoto,Japan,2007:181-192.
[2] European Union.Project PSIRP[OL].[2010-10-1].http://www.psirp.org.
[3] Jacobson V,Smetters D K,Thornton J D,et al.Networkingnamed content[C]//Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies,Rome,Italy,2009:1-12.
[4] Jacobson V,Smetters D K,Thornton J D,et al.Networkingnamed content[J].Communications of the ACM,2012,55(1):117-124.
[5] Wang J M,Bensaou B.Progressive caching in ccn[C]//IEEE GLOBECOM’12,Anaheim,CA,2012:2727-2732.
[6] Psaras I,Chai W K,Pavlou G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the second edition of the ICN workshop on Information-centric networking,New York:ACM,2012:55-60.
[7] Bernardini C,Silverston T,Festor O.MPC:Popularity-Based Caching Strategy for Content Centric Networks[C]//Communications(ICC),2013 IEEE International Conference on.IEEE,2013:3619-3623.
[8] Fiore M,Mininni F,Casetti C,et al.To Cache or Not To Cache?[C]//INFOCOM 2009,IEEE.IEEE,2009:235-243.
[9] Cho K,Lee M,Park K,et al.Wave:Popularity-based and collaborative in-network caching for content-oriented networks[C]//INFOCOM Workshops,2012:316-321.
[10] Psaras I,Chai W K,Pavlou G.Probabilistic in-network caching for information-centric networks[C]//Proceedings of the second edition of the ICN workshop on Information-centric networking,ser.ICN ’12.New York,NY,USA:ACM,2012:55-60.
[11] Wang Z,Crowcroft J.Quality of service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1228-1234.
[12] Kangasharju J,Roberts J,Ross K.Object replication strategies in content distribution networks[J].Computer Communications,2002,25(4):376-383.
[13] Afanasyev A,Moiseenko I,Zhang L X,et al.ndnSIM[OL].[2012].http://irl.cs.ucla.edu/ndnSIM.html.
[14] Afanasyev A,Moiseenko I,Zhang L X,et al.ndnSIM: NDN simulator for NS-3[R].California: PARC,2012.
[15] Li J,Wu H,Liu B,et al.Popularity-Driven Coordinated Caching in Named Data Networking[C]//Proceedings of the Eighth ACM/IEEE Symposium on Architectures for Networking and Communications Systems,ACM New York,2012:15-26.
A CACHING STRATEGY FOR REDUCING CONTENT DELIVERY COST OF AUTONOMOUS SYSTEM IN CONTENT CENTRIC NETWORK
Yang Xiaofei Ding Zhipeng Zhang Hongyu Niu Cuicui Huang Sheng
(KeyLabofOpticalFiberCommunicationsTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)
Content centric network (CCN) is a promising network architecture of future internet. It enhances the content delivery, reduces content delivery cost and improves network throughput by utilising intra-network caching mechanism. In light of the content distribution situation within same autonomous system and the influence of hot contents on networks, we proposed a caching mechanism aimed at reducing content delivery cost, i.e., delivery cost reduction (DCR) strategy. DCR strategy can push hot contents to users while reducing contents redundancy. Experimental results showed that the caching strategy proposed could effectively reduce content delivery cost within AS and improved the intra-AS hit ratio as well.
Content centric network (CCN) Caching strategy Redundancy Content delivery costs Cache hit ratio
2014-09-01。國家自然科學(xué)基金項(xiàng)目(61371096);重慶市自然科學(xué)基金項(xiàng)目(cstc2013jcyA40052);重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ130515)。楊曉非,副教授,主研領(lǐng)域:電路,信號與系統(tǒng)。丁志鵬,碩士生。張宏宇,碩士生。牛翠翠,碩士生。黃勝,教授。
TP393
A
10.3969/j.issn.1000-386x.2016.04.029