段 煉，楊龍祥，任美翠

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

內(nèi)容中心網(wǎng)絡(luò)及其緩存策略研究

段 煉，楊龍祥，任美翠

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

當(dāng)今，因特網(wǎng)的使用已經(jīng)演進(jìn)到以內(nèi)容的分發(fā)和檢索為主，但是目前使用的IP結(jié)構(gòu)并不能很好地滿足這樣的需求。內(nèi)容中心網(wǎng)絡(luò)(Content Centric Networking，CCN)打破了傳統(tǒng)的“主機(jī)—主機(jī)”的通信模式，將內(nèi)容置于核心地位，是目前未來(lái)網(wǎng)絡(luò)領(lǐng)域的研究熱點(diǎn)之一。CCN將內(nèi)容與主機(jī)分割開并將內(nèi)容存儲(chǔ)在網(wǎng)絡(luò)節(jié)點(diǎn)中。任何存有內(nèi)容的節(jié)點(diǎn)都可以充當(dāng)服務(wù)器向用戶提供服務(wù)，因此CCN可以高效地進(jìn)行內(nèi)容傳輸。CCN的這種優(yōu)勢(shì)來(lái)自于它可以進(jìn)行網(wǎng)絡(luò)內(nèi)緩存，可以說(shuō)緩存是CCN的基石。緩存策略的性能直接影響了整個(gè)CCN的性能。簡(jiǎn)要概括了CCN和IP的區(qū)別，介紹了CCN的一些核心概念和工作機(jī)制，給出了CCN中相關(guān)的緩存算法并分析了它們的優(yōu)缺點(diǎn)。

內(nèi)容中心網(wǎng)絡(luò)；未來(lái)網(wǎng)絡(luò)；網(wǎng)絡(luò)體系結(jié)構(gòu)；緩存算法

1 概 述

在計(jì)算機(jī)系統(tǒng)開發(fā)的初期，系統(tǒng)內(nèi)的資源非常有限。隨后，為了解決資源共享的問(wèn)題，不同的網(wǎng)絡(luò)結(jié)構(gòu)逐漸演化，最終形成了客戶端-服務(wù)器的通信模式[1]。在這種模式中，一個(gè)節(jié)點(diǎn)擁有資源并且其他節(jié)點(diǎn)可以利用這些資源。這是一種以主機(jī)為中心的面向連接的網(wǎng)絡(luò)模型。在這種模式中，為了從一個(gè)特定服務(wù)器獲取相應(yīng)服務(wù)，節(jié)點(diǎn)必須與此服務(wù)器進(jìn)行連接。計(jì)算機(jī)系統(tǒng)發(fā)展至今，系統(tǒng)內(nèi)的資源不再匱乏且變得相對(duì)廉價(jià)，加上技術(shù)的進(jìn)步，使得這種模式在逐漸轉(zhuǎn)變。

計(jì)算機(jī)體系結(jié)構(gòu)設(shè)計(jì)的初衷是用于共享資源，但是隨著網(wǎng)絡(luò)的不斷發(fā)展，資源的共享已經(jīng)不能滿足人們的需求。現(xiàn)今，人們對(duì)于內(nèi)容的傳播更為感興趣(主要是視頻)，而這也占據(jù)了因特網(wǎng)中大部分的流量。TCP/IP正是為了應(yīng)對(duì)內(nèi)容的傳播而設(shè)計(jì)的。

例如，考慮到圖1中的網(wǎng)絡(luò)拓?fù)洌渚W(wǎng)絡(luò)結(jié)構(gòu)使用的是TCP/IP。因此網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)將遵循TCP/IP協(xié)議。在此情況下，如果節(jié)點(diǎn)1需要獲取內(nèi)容A，那么此節(jié)點(diǎn)首先需要和提供內(nèi)容A的服務(wù)器進(jìn)行連接。因此，節(jié)點(diǎn)1需要向服務(wù)器發(fā)送一個(gè)連接請(qǐng)求。如果此時(shí)服務(wù)器可以提供服務(wù)，那么它將會(huì)接收連接請(qǐng)求。之后節(jié)點(diǎn)1和服務(wù)器之間將會(huì)建立連接?，F(xiàn)在，節(jié)點(diǎn)1發(fā)送需求內(nèi)容A的請(qǐng)求，而服務(wù)器將會(huì)把內(nèi)容A轉(zhuǎn)發(fā)給節(jié)點(diǎn)1來(lái)完成響應(yīng)。

圖1 IP結(jié)構(gòu)的低效性

同樣，如果節(jié)點(diǎn)2和節(jié)點(diǎn)3也需要內(nèi)容A，那么它們將會(huì)執(zhí)行和上面一樣的操作。可以說(shuō)，無(wú)論多少節(jié)點(diǎn)需要內(nèi)容A，它們都需要進(jìn)行相同的操作，即和提供內(nèi)容的服務(wù)器進(jìn)行連接?？梢钥闯?，IP網(wǎng)絡(luò)以主機(jī)為中心，它更加關(guān)注被請(qǐng)求信息的位置而不是信息本身的內(nèi)容，因此，所有對(duì)于相同內(nèi)容的請(qǐng)求都需要源服務(wù)器來(lái)完成，不僅導(dǎo)致網(wǎng)絡(luò)的效率不高，還造成了巨大的帶寬浪費(fèi)。內(nèi)容中心網(wǎng)絡(luò)(CCN)[2]正是為了克服IP網(wǎng)絡(luò)的這種缺陷而提出的新型網(wǎng)絡(luò)架構(gòu)。

CCN支持網(wǎng)絡(luò)內(nèi)緩存，即在網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)都設(shè)有緩存功能[3]。通過(guò)網(wǎng)絡(luò)內(nèi)緩存，CCN避免了對(duì)相同內(nèi)容的重復(fù)傳輸。當(dāng)轉(zhuǎn)發(fā)的內(nèi)容經(jīng)過(guò)某一節(jié)點(diǎn)時(shí)，此節(jié)點(diǎn)可以緩存該內(nèi)容。當(dāng)此節(jié)點(diǎn)再次收到對(duì)這一內(nèi)容的請(qǐng)求時(shí)，它可以直接將請(qǐng)求的內(nèi)容發(fā)送給請(qǐng)求者而不再需要請(qǐng)求服務(wù)器。因而CCN節(jié)省了網(wǎng)絡(luò)資源，加快了內(nèi)容傳輸。

文中主要對(duì)內(nèi)容中心網(wǎng)絡(luò)及其緩存策略進(jìn)行研究，分析了CCN體系結(jié)構(gòu)與IP體系結(jié)構(gòu)的不同，介紹了CCN的包類型、節(jié)點(diǎn)轉(zhuǎn)發(fā)的工作機(jī)制，闡述了幾種典型的CCN緩存決策策略和緩存替換策略。在此基礎(chǔ)上，重點(diǎn)研究了幾種具有代表性的緩存決策策略，并對(duì)其性能的優(yōu)缺點(diǎn)進(jìn)行了分析，為未來(lái)的研究工作奠定了理論基礎(chǔ)。

2 內(nèi)容中心網(wǎng)絡(luò)中的核心概念

與傳統(tǒng)的主機(jī)到主機(jī)的網(wǎng)絡(luò)結(jié)構(gòu)不同，CCN是一種面向內(nèi)容的結(jié)構(gòu)。當(dāng)今用戶的需求已經(jīng)由傳統(tǒng)的“資源共享”向“內(nèi)容傳播”轉(zhuǎn)變，這正是CCN被提出的內(nèi)在動(dòng)力。CCN是一種全新結(jié)構(gòu)，它與傳統(tǒng)的IP結(jié)構(gòu)截然不同。圖2在協(xié)議棧方面對(duì)CCN和IP進(jìn)行了比較。

可以看出，IP中的大部分層都需要雙邊協(xié)議，例如IP的2層框架協(xié)議是兩個(gè)物理終端之間的協(xié)議，4層傳輸協(xié)議是生產(chǎn)者和消費(fèi)者之間的協(xié)議，而只有第3層即網(wǎng)絡(luò)層需求統(tǒng)一的協(xié)議。CCN的第3層即策略層有效地利用了多徑連接。CCN采用接收端驅(qū)動(dòng)的方式，保證了傳輸內(nèi)容的安全性，避免了許多一直困擾IP網(wǎng)絡(luò)的安全隱患[4]。

圖2 IP和CCN協(xié)議棧

在CCN中，傳入流量一般遵循Zipf分布[5]。這種分布為流行的內(nèi)容分配相應(yīng)的等級(jí)。流行度表示某一內(nèi)容在一定時(shí)間內(nèi)被訪問(wèn)的次數(shù)。被訪問(wèn)的次數(shù)越多意味著這個(gè)內(nèi)容的流行度越高。Zipf分布依據(jù)流行度對(duì)內(nèi)容進(jìn)行分類并給內(nèi)容分配相應(yīng)的等級(jí)。內(nèi)容的流行度越高其等級(jí)越低，流行度越低等級(jí)也就越高。

在CCN中任何的通信都由用戶自己管理，而不再由傳統(tǒng)的服務(wù)器進(jìn)行管理。用戶只會(huì)接收到那些已經(jīng)需求過(guò)的內(nèi)容。然而，在IP網(wǎng)絡(luò)中，除了那些被需求的內(nèi)容外，一些未被需求的內(nèi)容也可能隨之一起發(fā)送給用戶。顯然，相比IP網(wǎng)絡(luò)，CCN更具有安全性。

CCN結(jié)構(gòu)建立在命名數(shù)據(jù)的基礎(chǔ)上，使用分級(jí)命名來(lái)唯一地命名內(nèi)容。在CCN中有兩種包結(jié)構(gòu)：Interest包和Data包。在CCN中，通過(guò)Interest包中的內(nèi)容名稱進(jìn)行內(nèi)容的請(qǐng)求。如果用戶需求某個(gè)內(nèi)容，他將會(huì)廣播Interest包，任何節(jié)點(diǎn)在收到Interest包后，如果在此節(jié)點(diǎn)內(nèi)存有用戶請(qǐng)求的內(nèi)容，那么此節(jié)點(diǎn)將向用戶返回相應(yīng)的Data包。當(dāng)Interest包的內(nèi)容名與Data包內(nèi)容名的前綴相符合時(shí)，則該Data包滿足該Interest包的請(qǐng)求。在CCN中，一個(gè)Interest包只會(huì)收到一個(gè)Data包作為響應(yīng)，這確保了流量的平衡以及在節(jié)點(diǎn)之間高效的通信。

由于網(wǎng)絡(luò)的高度動(dòng)態(tài)性，Data包和Interest包都有可能出現(xiàn)丟失的情況。因此，為了確保CCN的可靠性，當(dāng)需求在一段時(shí)間內(nèi)未被滿足時(shí)，請(qǐng)求節(jié)點(diǎn)需要重發(fā)Interest包。

3 CCN工作機(jī)制

CCN致力于對(duì)數(shù)據(jù)的高速獲取。為了達(dá)成這個(gè)目標(biāo)，CCN采用了新的轉(zhuǎn)發(fā)引擎模型。其中包含三個(gè)主要的數(shù)據(jù)結(jié)構(gòu)：轉(zhuǎn)發(fā)信息表(Forwarding Information Base，F(xiàn)IB)、內(nèi)容存儲(chǔ)表(Content Store，CS)和待定請(qǐng)求表(Pending Interest Table，PIT)。

FIB將Interest包轉(zhuǎn)發(fā)到包含有請(qǐng)求內(nèi)容的服務(wù)器。CCN的FIB和IP的FIB類似，不同的是CCN的FIB有一系列的出口，而IP的FIB只有一個(gè)[6]。因此CCN中的節(jié)點(diǎn)可以向多個(gè)源服務(wù)器發(fā)送請(qǐng)求。CCN中的CS和IP中的緩沖區(qū)域類似，用來(lái)作為緩存內(nèi)容的存儲(chǔ)區(qū)域。但CS有著不同的緩存替換策略。IP緩沖區(qū)中的內(nèi)容在轉(zhuǎn)發(fā)之后就將被丟棄，而CCN中的CS將會(huì)盡可能長(zhǎng)時(shí)間地緩存內(nèi)容，以便更快地為之后的請(qǐng)求提供服務(wù)。PIT記錄已經(jīng)轉(zhuǎn)發(fā)的Interest包，當(dāng)對(duì)同一內(nèi)容有多個(gè)請(qǐng)求時(shí)，它將多余的請(qǐng)求記錄在一個(gè)條目中，并只向數(shù)據(jù)源發(fā)送一條請(qǐng)求。當(dāng)Data包返回時(shí)，它會(huì)根據(jù)PIT中記錄的條目將數(shù)據(jù)發(fā)送給相應(yīng)的請(qǐng)求源。

3.1 Interest包的處理

當(dāng)一個(gè)Interest包到達(dá)一個(gè)節(jié)點(diǎn)的接口之后，節(jié)點(diǎn)將會(huì)對(duì)其進(jìn)行最長(zhǎng)前綴匹配來(lái)驗(yàn)證它所需求的內(nèi)容是否已經(jīng)存儲(chǔ)在CS中。如果需求的內(nèi)容已經(jīng)存儲(chǔ)在節(jié)點(diǎn)的CS中，那么此節(jié)點(diǎn)將立刻向請(qǐng)求者發(fā)送Data包。由于請(qǐng)求已經(jīng)被滿足，所以此Interest包將會(huì)被丟棄。

如果在CS中并沒有找到需求的內(nèi)容，那么接著將會(huì)校驗(yàn)PIT中的條目。如果和PIT中的條目相匹配，則在PIT的請(qǐng)求接口表中添加相應(yīng)的條目并刪除此Interest包。如果后來(lái)的請(qǐng)求是對(duì)先前已經(jīng)請(qǐng)求內(nèi)容的請(qǐng)求，節(jié)點(diǎn)并不會(huì)因此而轉(zhuǎn)發(fā)多個(gè)Interest包。對(duì)于相同內(nèi)容的請(qǐng)求，一個(gè)節(jié)點(diǎn)只會(huì)轉(zhuǎn)發(fā)一個(gè)Interest包。

如果在PIT中也沒有匹配到相應(yīng)的條目，那么此Interest包將會(huì)根據(jù)FIB中的條目進(jìn)行轉(zhuǎn)發(fā)。假定FIB知道所有內(nèi)容的源服務(wù)器，因此它能夠有效地轉(zhuǎn)發(fā)Interest包來(lái)獲取相應(yīng)的內(nèi)容。

3.2 Data包的處理

相比于Interest包，Data包的處理過(guò)程比較簡(jiǎn)單。當(dāng)Data包到達(dá)一個(gè)節(jié)點(diǎn)的接口時(shí)，Data包的內(nèi)容名將進(jìn)行最長(zhǎng)前綴匹配。如果此內(nèi)容名和CS中的條目相匹配，說(shuō)明此內(nèi)容已經(jīng)存儲(chǔ)在CS中，那么此內(nèi)容將會(huì)被丟棄。如果和FIB中的條目相匹配，則表明該內(nèi)容名在PIT中沒有相匹配的條目，也就是說(shuō)該內(nèi)容并沒有被請(qǐng)求過(guò)，此內(nèi)容也會(huì)被丟棄。如果和PIT中的條目形成了匹配，則表明此節(jié)點(diǎn)確實(shí)發(fā)送過(guò)請(qǐng)求此內(nèi)容的Interest包。接著將會(huì)進(jìn)行內(nèi)容驗(yàn)證并把此內(nèi)容存于CS中，最后依據(jù)PIT中匹配的條目創(chuàng)建一個(gè)請(qǐng)求接口表，并根據(jù)此表將Data包發(fā)送給每一個(gè)請(qǐng)求者。

4 CCN相關(guān)的緩存算法

CCN的緩存策略大致可以分為兩類。一類是緩存決策策略，即選擇網(wǎng)絡(luò)中最合適的節(jié)點(diǎn)去緩存相應(yīng)的內(nèi)容。另一類是緩存替換策略，即當(dāng)節(jié)點(diǎn)緩存空間已滿時(shí)選擇丟棄哪個(gè)內(nèi)容來(lái)為新的內(nèi)容騰出空間[7]。

CCN有以下三種典型的緩存決策策略：

(1)Leave Copy Everywhere (LCE)[8]:這是CCN默認(rèn)的緩存決策策略。其核心思想是將內(nèi)容存儲(chǔ)在沿著需求路徑的每一個(gè)路由器上，但是LCE有較大的數(shù)據(jù)冗余度，造成緩存空間的大量浪費(fèi)。

(2)Leave Copy Down (LCD)[9]:當(dāng)緩存命中時(shí)，僅在命中節(jié)點(diǎn)的下游節(jié)點(diǎn)緩存該內(nèi)容，這種策略減少了需求路徑上重復(fù)內(nèi)容的數(shù)量，但降低了緩存的命中率。

(3)Probabilistic Caching (ProbCache)[10]:其核心思想是節(jié)點(diǎn)越靠近用戶其緩存概率越大，這種策略能將內(nèi)容快速地緩存到網(wǎng)絡(luò)邊緣，但是并未考慮內(nèi)容的流行度問(wèn)題，會(huì)增加不同內(nèi)容在邊緣節(jié)點(diǎn)的競(jìng)爭(zhēng)。

CCN中的緩存替換策略大多使用最近最少使用置換算法(Least Recently Used，LRU)[11]和最不經(jīng)常使用置換算法(Least Frequently Used，LFU)[12]來(lái)最大限度地存儲(chǔ)內(nèi)容。

目前，研究者們大多致力于對(duì)緩存決策策略的研究。文中主要介紹并分析以下幾種具有代表性的緩存決策策略。

4.1 基于節(jié)點(diǎn)緩存容量的緩存策略

這種算法在緩存決策時(shí)考慮到了節(jié)點(diǎn)的緩存容量[13]，把它作為選擇緩存節(jié)點(diǎn)時(shí)的一個(gè)參數(shù)。這里的緩存容量表示網(wǎng)絡(luò)節(jié)點(diǎn)的CS中還能存儲(chǔ)多少內(nèi)容。為了記錄這個(gè)緩存容量，在Interest包中添加了Cache Capacity Value (CCV)域。當(dāng)節(jié)點(diǎn)收到一個(gè)Interest包后，如果在其CS中沒有找到需求的內(nèi)容，它將會(huì)把自己的緩存容量添加到CCV域中并轉(zhuǎn)發(fā)Interest包。當(dāng)下一個(gè)節(jié)點(diǎn)收到這個(gè)Interest包后，如果在它的CS中也沒有找到這個(gè)內(nèi)容，那么它將會(huì)把自己的CCV值和Interest包中的CCV值進(jìn)行比較。如果它的CCV值小于Interest包中的CCV值，那么它會(huì)直接轉(zhuǎn)發(fā)此Interest包。如果大于，它將會(huì)用自己的CCV值替換Interest包中的CCV值并轉(zhuǎn)發(fā)此Interest包。當(dāng)Interest包到達(dá)存有內(nèi)容的服務(wù)器之后，服務(wù)器會(huì)根據(jù)最大的CCV值分配轉(zhuǎn)發(fā)路徑中相應(yīng)的節(jié)點(diǎn)去緩存Data包中的內(nèi)容。

這種算法在通常流量和突發(fā)流量情況下都有很好的表現(xiàn)。大部分緩存算法中都沒有考慮突發(fā)流量的情況，但在實(shí)際情況中，突發(fā)流量是很有可能出現(xiàn)的。因此考慮突發(fā)流量情況是該算法的一個(gè)優(yōu)點(diǎn)。

現(xiàn)在假設(shè)有六個(gè)Interest包，每個(gè)包請(qǐng)求10 MB的數(shù)據(jù)。當(dāng)這六個(gè)Interest包到達(dá)一個(gè)CCV值是50 MB的節(jié)點(diǎn)后，認(rèn)定這個(gè)節(jié)點(diǎn)是傳輸路徑中擁有最大CCV值的節(jié)點(diǎn)。因此當(dāng)Data包返回時(shí)前五個(gè)內(nèi)容將會(huì)被緩存到此節(jié)點(diǎn)中。而當(dāng)?shù)诹鶄€(gè)Data包到達(dá)時(shí)，由于緩存空間已滿，此時(shí)節(jié)點(diǎn)必須執(zhí)行緩存替換策略來(lái)為第六個(gè)內(nèi)容騰出緩存空間。如果這種情況大量發(fā)生，那么節(jié)點(diǎn)將會(huì)忙于執(zhí)行替換策略，這會(huì)降低網(wǎng)絡(luò)整體的性能。

4.2 基于節(jié)點(diǎn)核心值的緩存策略

文獻(xiàn)[14]采用節(jié)點(diǎn)的核心值作為一個(gè)參數(shù)來(lái)選擇緩存內(nèi)容的節(jié)點(diǎn)。核心值用來(lái)衡量一個(gè)節(jié)點(diǎn)在通信模式中的重要性。一個(gè)節(jié)點(diǎn)出現(xiàn)在內(nèi)容傳輸路徑的次數(shù)越多，其核心值越高。

假設(shè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖3所示。

圖3 路由器的核心值

用戶A發(fā)送一個(gè)Interest包，此Interest包將會(huì)到達(dá)服務(wù)器S1，服務(wù)器S1將會(huì)沿路徑S1-V1-V2-V3-V4-V5發(fā)送Data包。根據(jù)文獻(xiàn)[15]可知，V4的核心值最高。根據(jù)文獻(xiàn)[14]中的算法，選擇V4作為緩存內(nèi)容的節(jié)點(diǎn)。

這種算法選擇了在傳輸路徑中出現(xiàn)次數(shù)最多的節(jié)點(diǎn)作為緩存內(nèi)容的節(jié)點(diǎn)。由于此節(jié)點(diǎn)很靠近網(wǎng)絡(luò)邊緣，因此它能夠?yàn)榇蠖鄶?shù)的請(qǐng)求提供服務(wù)。同時(shí)僅選擇一個(gè)節(jié)點(diǎn)來(lái)緩存內(nèi)容使得資源的利用率很高。

不過(guò)這種算法并沒有考慮突發(fā)流量的情況，當(dāng)突發(fā)流量發(fā)生時(shí)，緩存內(nèi)容的節(jié)點(diǎn)負(fù)載會(huì)劇增，從而影響服務(wù)質(zhì)量。不僅如此，該算法對(duì)于緩存節(jié)點(diǎn)的選擇僅依據(jù)節(jié)點(diǎn)在拓?fù)渲械奈恢枚]有考慮內(nèi)容的流行度問(wèn)題，因此在緩存節(jié)點(diǎn)中，流行的內(nèi)容很可能被不流行的內(nèi)容替換掉，從而使流行的內(nèi)容無(wú)法被充分利用。

4.3 基于內(nèi)容流行度的緩存策略

文獻(xiàn)[16]提出一種思路，每個(gè)節(jié)點(diǎn)記錄對(duì)每個(gè)內(nèi)容的需求次數(shù)，然后以成對(duì)的形式把內(nèi)容名和流行值記錄到一個(gè)流行度表(Popularity Table)中。一旦一個(gè)內(nèi)容的流行度達(dá)到流行度臨界值之后，這個(gè)內(nèi)容將會(huì)被標(biāo)記為流行的。

如果某個(gè)節(jié)點(diǎn)擁有這個(gè)內(nèi)容，它將會(huì)通過(guò)一條建議信息(Suggestion)去建議它的鄰節(jié)點(diǎn)緩存這個(gè)內(nèi)容。在發(fā)送建議信息之后該節(jié)點(diǎn)將會(huì)重置該內(nèi)容的流行度，防止重復(fù)地將該內(nèi)容發(fā)送給鄰節(jié)點(diǎn)。MPC緩存的示例如圖4所示。

圖4 MPC緩存示例

假設(shè)A，B，C節(jié)點(diǎn)請(qǐng)求內(nèi)容d1，A節(jié)點(diǎn)請(qǐng)求內(nèi)容e1，每次請(qǐng)求使得相關(guān)內(nèi)容的流行度增加1，并假設(shè)流行度臨界值為3。此時(shí)D節(jié)點(diǎn)中內(nèi)容d1的流行度達(dá)到3，達(dá)到了臨界值，這時(shí)D節(jié)點(diǎn)將建議其鄰節(jié)點(diǎn)C和E對(duì)d1進(jìn)行緩存。

這種算法依據(jù)流行度對(duì)內(nèi)容進(jìn)行緩存，由于流行度高的內(nèi)容被存儲(chǔ)在了更多的節(jié)點(diǎn)中，因此算法的緩存命中率相比傳統(tǒng)的LCE算法有很大提升。此外，由于緩存內(nèi)容的減少(僅緩存流行度高的內(nèi)容)，節(jié)約了節(jié)點(diǎn)的緩存空間并減少了緩存的操作次數(shù)。但也因此使得網(wǎng)絡(luò)中內(nèi)容的多樣性有所下降。

4.4 核心協(xié)作緩存策略

文獻(xiàn)[17]的主要思想是，通過(guò)構(gòu)造支配集來(lái)構(gòu)建一個(gè)虛擬骨干網(wǎng)絡(luò)。文獻(xiàn)[18]介紹了如何構(gòu)造一個(gè)連接的支配集(Connected Dominating Set，CDS)。核心節(jié)點(diǎn)是構(gòu)成CDS的主要部分，其余節(jié)點(diǎn)被稱為常規(guī)節(jié)點(diǎn)。每個(gè)核心節(jié)點(diǎn)為一個(gè)或者幾個(gè)常規(guī)節(jié)點(diǎn)提供服務(wù)。流行度高的內(nèi)容被存儲(chǔ)在核心節(jié)點(diǎn)，因此減少了內(nèi)容的冗余度。同時(shí)，常規(guī)節(jié)點(diǎn)不允許緩存內(nèi)容。當(dāng)核心節(jié)點(diǎn)的緩存空間已滿時(shí)，被刪除的內(nèi)容將發(fā)送給其服務(wù)的常規(guī)節(jié)點(diǎn)。核心節(jié)點(diǎn)每刪除一個(gè)內(nèi)容將相應(yīng)地增加一個(gè)條目。

算法中并不是所有節(jié)點(diǎn)都需要緩存內(nèi)容，大部分的運(yùn)算都集中在核心節(jié)點(diǎn)。由于只有少部分的節(jié)點(diǎn)需要進(jìn)行運(yùn)算，因此網(wǎng)絡(luò)的資源利用率得到了提高。同時(shí)該算法考慮了內(nèi)容的流行度問(wèn)題。

構(gòu)建虛擬骨干網(wǎng)絡(luò)的過(guò)程十分復(fù)雜，這正是該算法的瓶頸所在。如果一個(gè)核心節(jié)點(diǎn)失去連接，那么與之相連的其他核心節(jié)點(diǎn)也會(huì)失去連接，這將導(dǎo)致網(wǎng)絡(luò)中斷。

4.5 基于Modulo hashing的分布式協(xié)作緩存策略

文獻(xiàn)[19]針對(duì)大視頻文件，提出了一種基于Modulo hashing的協(xié)同緩存策略[20]。當(dāng)某個(gè)內(nèi)容塊到達(dá)一個(gè)緩存節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)將通過(guò)一個(gè)Modulo hashing函數(shù)計(jì)算出該內(nèi)容塊應(yīng)該由哪個(gè)鄰居節(jié)點(diǎn)或者自身來(lái)緩存。

如圖5所示，將需求的視頻內(nèi)容分為很多內(nèi)容塊，每一個(gè)節(jié)點(diǎn)并不緩存全部的內(nèi)容塊，而是分別緩存部分內(nèi)容塊，由k個(gè)節(jié)點(diǎn)共同協(xié)作緩存全部的內(nèi)容塊。規(guī)定，每個(gè)節(jié)點(diǎn)都擁有一個(gè)標(biāo)簽，該標(biāo)簽是一個(gè)小于固定整數(shù)k的自然數(shù)。每個(gè)節(jié)點(diǎn)只對(duì)符合一定緩存規(guī)則的內(nèi)容塊進(jìn)行緩存。若內(nèi)容塊標(biāo)號(hào)對(duì)k取余的結(jié)果與該節(jié)點(diǎn)的標(biāo)簽相等，則節(jié)點(diǎn)緩存此內(nèi)容塊。如圖所示，假設(shè)總塊數(shù)為21(內(nèi)容塊0到內(nèi)容塊20)且k=3，那么每個(gè)節(jié)點(diǎn)(路由器)ri的標(biāo)簽為i(0，1，2)。路由器r0緩存的內(nèi)容為內(nèi)容塊{0，3，6，…，18}，也就是連續(xù)10個(gè)其標(biāo)號(hào)對(duì)3取余為0的內(nèi)容塊。

圖5 基于Modulo hashing的協(xié)同緩存策略

這種算法使用了Modulohashing使得一個(gè)節(jié)點(diǎn)與其k-1個(gè)鄰節(jié)點(diǎn)共同協(xié)作完成對(duì)內(nèi)容的緩存。由于將內(nèi)容切分并存儲(chǔ)在不同的網(wǎng)絡(luò)節(jié)點(diǎn)中，因此網(wǎng)絡(luò)中內(nèi)容的多樣性得到了很大提升，從而許多對(duì)于內(nèi)容的請(qǐng)求不再需要源服務(wù)器來(lái)提供服務(wù)，這有效地減少了服務(wù)器的負(fù)載。但由于這是一種基于Modulohashing的算法，當(dāng)網(wǎng)絡(luò)中增加或者移除一個(gè)路由器時(shí)，先前的模值將會(huì)發(fā)生變化，之前緩存的內(nèi)容的位置也必將隨之更改。同時(shí)網(wǎng)絡(luò)將會(huì)出現(xiàn)負(fù)載均衡的問(wèn)題，使得某些路由器負(fù)載過(guò)大。

4.6 基于Consistent hashing的分布式協(xié)作緩存策略

這種算法是一種基于Consistent hashing的協(xié)同緩存算法[21]。首先在一組路由器中根據(jù)路由器緩存容量的大小分配不同個(gè)數(shù)的Keys，容量越大分配的Keys個(gè)數(shù)越多，Keys的范圍為0到n并由這些Keys組成一個(gè)Hash環(huán)。

如圖6所示，假設(shè)路由器1擁有5個(gè)Keys，分別是2，6，7，12，13(根據(jù)容量隨機(jī)分配)，路由器2擁有4個(gè)Keys，分別是1，5，8，10，路由器3擁有0，4，9，路由器4擁有3，11。當(dāng)一個(gè)內(nèi)容塊到達(dá)路由器時(shí)，首先計(jì)算其hash值并根據(jù)它的歷史和當(dāng)前請(qǐng)求頻率計(jì)算出它的流行度。接著用其hash值和該路由器擁有的Keys值進(jìn)行匹配，如果相匹配且其流行度大于臨界值則緩存該內(nèi)容，否則不緩存。例如，路由器1將只緩存hash值為2，6，7，12，13且流行度大于臨界值的內(nèi)容塊。

圖6 基于Consistent hashing的協(xié)同緩存策略

這種算法考慮了路由器容量的大小問(wèn)題，這在實(shí)際情況中非常值得考慮。同時(shí)算法還將流行度納入為決策的要素，有效地提高了緩存的命中率，減少了服務(wù)器的負(fù)載。同時(shí)算法還利用Consistenthashing有效降低了增加或者移除路由器時(shí)造成的影響。

但Consistenthashing對(duì)內(nèi)容塊進(jìn)行分布式緩存，網(wǎng)絡(luò)邊緣節(jié)點(diǎn)并不能夠緩存流行度最高的內(nèi)容，這會(huì)導(dǎo)致命中距離的提升。而且算法綜合考慮了多方面的因素，也因此使其復(fù)雜度大大提升，這將使節(jié)點(diǎn)需要大量的資源去進(jìn)行計(jì)算，降低了網(wǎng)絡(luò)的整體性能。

5 結(jié)束語(yǔ)

隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)，新興業(yè)務(wù)的不斷出現(xiàn)，以及用戶對(duì)服務(wù)的需求越來(lái)越多樣化，傳統(tǒng)的IP網(wǎng)絡(luò)基礎(chǔ)架構(gòu)已經(jīng)不堪重負(fù)，成為了網(wǎng)絡(luò)進(jìn)一步發(fā)展的瓶頸。為了解決這個(gè)問(wèn)題，提出了很多關(guān)于未來(lái)網(wǎng)絡(luò)方面的研究。文中涉及的CCN是未來(lái)網(wǎng)絡(luò)發(fā)展方向之一。其以用戶需求為中心，支持網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)的緩存，有效提高了內(nèi)容的傳播效率，從而克服了IP結(jié)構(gòu)效率低的問(wèn)題，使得用戶能夠更便捷地獲取他們想要的內(nèi)容。其眾多優(yōu)點(diǎn)使得它很有可能在不久的將來(lái)取代IP的主體地位，也因此使得它成為當(dāng)前對(duì)未來(lái)網(wǎng)絡(luò)方面研究的重點(diǎn)。

圍繞內(nèi)容中心網(wǎng)絡(luò)重點(diǎn)介紹并討論了幾種具有代表性的緩存決策策略，詳細(xì)分析了各自的優(yōu)缺點(diǎn)。諸如，基于節(jié)點(diǎn)緩存容量的緩存策略考慮到了節(jié)點(diǎn)的緩存容量，提升了突發(fā)流量下的緩存性能，卻容易因?yàn)轭l繁執(zhí)行替換策略而降低了網(wǎng)絡(luò)的整體性能；基于節(jié)點(diǎn)核心值的緩存策略提高了網(wǎng)絡(luò)資源的利用率，卻沒有考慮內(nèi)容流行度的問(wèn)題；基于內(nèi)容流行度的緩存策略，顯著改善了緩存命中率，但也降低了網(wǎng)絡(luò)內(nèi)容的多樣性；核心協(xié)作緩存策略考慮了內(nèi)容流行度的同時(shí)提高了資源利用率，但核心節(jié)點(diǎn)失去連接時(shí)將會(huì)導(dǎo)致網(wǎng)絡(luò)中斷；基于Modulohashing的分布式協(xié)作緩存策略提高了緩存內(nèi)容的多樣性，減少了服務(wù)器的負(fù)載，但增加或者移除一個(gè)路由器時(shí)會(huì)對(duì)算法造成影響；基于Consistenthashing的分布式協(xié)作緩存策略有效降低了增加或者移除路由器時(shí)造成的影響，卻使得算法的復(fù)雜度大幅提升，從而降低了網(wǎng)絡(luò)的整體性能。綜上所述，CCN仍有諸多理論和技術(shù)問(wèn)題有待解決，需要深入的研究。

[1]XylomenosG,VerveridisCN,SirisV,etal.Asurveyofinformation-centricnetworkingresearch[J].IEEECommunicationsSurveys&Tutorials,2014,16(2):1024-1049.

[2]JacobsonV,SmettersDK,ThorntonJD,etal.Networkingnamedcontent[C]//Internationalconferenceonemergingnetworkingexperiments&technologies.[s.l.]:ACM,2011:1-12.

[3] 胡 騫,武穆清,郭 嵩.以內(nèi)容為中心的未來(lái)通信網(wǎng)絡(luò)研究綜述[J].電信科學(xué),2012,28(9):74-80.

[4] 夏春梅,徐明偉.信息中心網(wǎng)絡(luò)研究綜述[J].計(jì)算機(jī)科學(xué)與探索,2013,7(6):481-493.

[5]NewmanM.ParetodistributionsandZipf'sLaw[J].ContemporaryPhysics,2004,46(5):323-351.

[6] 閔二龍,陳 震,許宏峰,等.內(nèi)容中心網(wǎng)絡(luò)CCN研究進(jìn)展探析[J].信息網(wǎng)絡(luò)安全,2012(2):6-10.

[7] 張國(guó)強(qiáng),李 楊,林 濤,等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報(bào),2014,25(1):154-175.

[8]JiangA,BruckJ.Optimalcontentplacementforen-routewebcaching[C]//IEEEinternationalsymposiumonnetworkcomputing&applications.[s.l.]:IEEEComputerSociety,2003.

[9]LaoutarisN,SyntilaS,StavrakakisI.Metaalgorithmsforhierarchicalwebcaches[C]//IEEEinternationalconferenceonperformance,computing,andcommunications.[s.l.]:IEEE,2004:445-452.

[10]PsarasI,ChaiWK,PavlouG.Probabilisticin-networkcachingforinformation-centricnetworks[C]//Proceedingsofthesecondeditionoftheworkshoponinformation-centricnetworking.[s.l.]:ACM,2012:55-60.

[11]MegiddoN,ModhaDS.OutperformingLRUwithanadaptivereplacementcachealgorithm[J].Computer,2004,37(4):58-65.

[12]PetevPG,WintergerstM.Leastfrequentlyusedevictionimplementation:U.S.,7 552 284[P].2009-06-23.

[13]KimD,LeeSW,KoYB,etal.Cachecapacity-awarecontentcentricnetworkingunderflashcrowds[J].JournalofNetwork&ComputerApplications,2015,50(C):101-113.

[14]ChaiWK,HeDiliang,PsarasI,etal.Cache“l(fā)essformore”ininformation-centricnetworks(extendedversion)[J].ComputerCommunications,2013,36(7):758-770.

[15]WassermannS,FaustK.Socialnetworkanalysis:methodsandapplications[M].Cambridge:CambridgeUniversityPress,1994.

[16]BernardiniC,SilverstonT,FestorO.MPC:popularity-basedcachingstrategyforcontentcentricnetworks[C]//IEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2013:3619-3623.

[17]XuY,LiY,LinT,etal.Adominatingset-basedcollaborativecachingwithrequestroutingincontentcentricnetworking[C]//IEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2013:3624-3628.

[18]GuhaS,KhullerS.Approximationalgorithmsforconnecteddominatingsets[J].Algorithmica,1998,20(4):374-387.

[19]LiZ,SimonG.Time-shiftedTVincontentcentricnetworks:thecaseforcooperativein-networkcaching[C]//IEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2011:1-6.

[20] 劉外喜,余順爭(zhēng),蔡 君,等.ICN中的一種協(xié)作緩存機(jī)制[J].軟件學(xué)報(bào),2013,24(8):1947-1962.

[21]TharK,OoTZ,PhamC,etal.Efficientforwardingandpopularitybasedcachingforcontentcentricnetwork[C]//Internationalconferenceoninformationnetworking.[s.l.]:IEEE,2015:330-335.

Research on Content Centric Networking and Its Caching Strategies

DUAN Lian,YANG Long-xiang,REN Mei-cui

(College of Communication and Information Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Use of Internet in today’s world has evolved to be dominated by distribution and retrieval of content,while currently used IP architecture cannot meet this demand.Content Centric Networking (CCN) breaks the traditional “host to host” communication mode,making content in the core position is one of the research hotspots.CCN decouples content from host and stores the content in every node.Any node can act as host and serve client if the requested content has been cached in it.Thus,CCN can deliver content efficiently.These advantages are mainly based on that CCN supports in-network caching,so it can be concluded that caching is backbone of CCN.The performance of the caching strategies directly affects the performance of CCN.The difference between the CCN and IP is summarized in brief,and then the key concepts and working mechanism of CCN are introduced.Finally,some proposed caching strategies have also been covered along with analyzing their advantages and disadvantages.

content centric networking;future network;network architecture;caching algorithm

2016-04-22

2016-08-10

時(shí)間：2017-02-17

國(guó)家自然科學(xué)基金資助項(xiàng)目(61372124);國(guó)家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2013CB329104)

段 煉(1991-)，男，碩士，研究方向?yàn)橐苿?dòng)通信與無(wú)線技術(shù);楊龍祥，教授，博士生導(dǎo)師，研究方向?yàn)橐苿?dòng)無(wú)線通信系統(tǒng)和物聯(lián)網(wǎng)。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1628.036.html

TP31

A

1673-629X(2017)03-0075-06

10.3969/j.issn.1673-629X.2017.03.016