劉 濤，程?hào)|年，田 銘

(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 4 50002)

基于副本通告的內(nèi)容中心網(wǎng)絡(luò)快捷路由機(jī)制

劉 濤，程?hào)|年，田 銘

(國(guó)家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，鄭州 4 50002)

內(nèi)容中心網(wǎng)絡(luò)是一種新的網(wǎng)絡(luò)體系結(jié)構(gòu)，采用以名字為標(biāo)識(shí)的內(nèi)容路由。然而，基本的內(nèi)容中心網(wǎng)絡(luò)路由機(jī)制僅對(duì)服務(wù)器的內(nèi)容建立路由表項(xiàng)，缺少到達(dá)節(jié)點(diǎn)上緩存的內(nèi)容副本路由，導(dǎo)致節(jié)點(diǎn)緩存資源利用率低，產(chǎn)生較大的內(nèi)容訪問(wèn)時(shí)延。針對(duì)該問(wèn)題，通過(guò)將節(jié)點(diǎn)緩存的副本向其他節(jié)點(diǎn)進(jìn)行通告，提出一種快捷路由機(jī)制，使得節(jié)點(diǎn)能夠感知鄰居節(jié)點(diǎn)的內(nèi)容副本，從而選擇最優(yōu)內(nèi)容源以獲取內(nèi)容。仿真結(jié)果表明，相比不考慮節(jié)點(diǎn)副本路由的機(jī)制，快捷路由機(jī)制可明顯減少用戶請(qǐng)求的平均時(shí)延，在節(jié)點(diǎn)緩存容量為60個(gè)內(nèi)容對(duì)象時(shí)，減少了43%的服務(wù)器負(fù)載。

內(nèi)容中心網(wǎng)絡(luò)；快捷路由；內(nèi)容活躍度；命名數(shù)據(jù)網(wǎng)絡(luò)；馬爾可夫鏈；副本

1 概述

網(wǎng)絡(luò)音視頻等多媒體業(yè)務(wù)的發(fā)展，使得互聯(lián)網(wǎng)的功能從端到端的主機(jī)通信變成了內(nèi)容的分發(fā)，用戶更關(guān)注于內(nèi)容而不是內(nèi)容的存儲(chǔ)位置。為此，研究人員提出以內(nèi)容為中心的網(wǎng)絡(luò)體系，即內(nèi)容中心網(wǎng)絡(luò)(Content Centric Network, CCN)[1]，其核心思想是通過(guò)對(duì)內(nèi)容的直接命名和基于內(nèi)容名字的路由來(lái)進(jìn)行內(nèi)容的獲取和分發(fā)。CCN通常是扁平的拓?fù)浣Y(jié)構(gòu)，類似于現(xiàn)有的IP網(wǎng)絡(luò)。在CCN中，節(jié)點(diǎn)除了傳統(tǒng)的路由和轉(zhuǎn)發(fā)功能之外，還具備內(nèi)容緩存能力。與基于IP地址的路由方式相比，CCN基于名字進(jìn)行路由，不需要知道內(nèi)容的位置或主機(jī)。

CCN的網(wǎng)絡(luò)實(shí)體能夠緩存臨時(shí)的內(nèi)容(即內(nèi)容副本)，以備將來(lái)訪問(wèn)，副本緩存時(shí)間從數(shù)分鐘到數(shù)天不等，并且受內(nèi)容流行度、緩存策略以及請(qǐng)求轉(zhuǎn)發(fā)策略所影響。為了利用這些副本資源，理想的內(nèi)容路由方式是設(shè)計(jì)一種路由和轉(zhuǎn)發(fā)機(jī)制，對(duì)所有臨時(shí)的內(nèi)容副本都能夠進(jìn)行尋址，以使得用戶請(qǐng)求能夠被轉(zhuǎn)發(fā)到“最優(yōu)”(例如，最近的)的可用副本。然而，這種理想的方式在CCN中存在實(shí)現(xiàn)上的困難，原因如下：

(1)網(wǎng)絡(luò)規(guī)模。CCN設(shè)計(jì)適應(yīng)多種應(yīng)用需求，不僅在小規(guī)模的有限網(wǎng)絡(luò)區(qū)域，也在整個(gè)網(wǎng)絡(luò)范圍內(nèi)對(duì)內(nèi)容副本進(jìn)行尋址和路由，這將導(dǎo)致極大的控制開銷。

(2)時(shí)間因素。存儲(chǔ)在網(wǎng)絡(luò)節(jié)點(diǎn)上的副本不停地加入和刪除，存在高度的動(dòng)態(tài)性和時(shí)變性，對(duì)這些副本進(jìn)行路由更新導(dǎo)致極大的信令開銷[2]。

針對(duì)節(jié)點(diǎn)副本路由問(wèn)題，文獻(xiàn)[3]的研究只考慮對(duì)內(nèi)容源服務(wù)器的內(nèi)容進(jìn)行通告，內(nèi)容請(qǐng)求在向源服務(wù)器轉(zhuǎn)發(fā)的過(guò)程中檢查各個(gè)節(jié)點(diǎn)上是否存在所請(qǐng)求的內(nèi)容，這種路徑緩存“檢查”的方式使得不在路徑上的內(nèi)容副本無(wú)法被利用。文獻(xiàn)[4]將以服務(wù)為中心的網(wǎng)絡(luò)體系和以內(nèi)容為中心的網(wǎng)絡(luò)體系結(jié)合在一起，提出了一種服務(wù)路由方法SoCCeR，旨在解決服務(wù)選取問(wèn)題，但是仍然缺少對(duì)節(jié)點(diǎn)副本內(nèi)容的路由機(jī)制。文獻(xiàn)[2]比較了2種不同的內(nèi)容路由機(jī)制：exploitation和exploration，并且提出一種混合的路由方法，即對(duì)源服務(wù)器的內(nèi)容原本建立路由表，而對(duì)節(jié)點(diǎn)緩存的內(nèi)容副本進(jìn)行探測(cè)，但其主要目標(biāo)是減少路由條目數(shù)量。文獻(xiàn)[5]提出一種鄰居緩存路由策略NCE，通過(guò)探測(cè)鄰居節(jié)點(diǎn)緩存的內(nèi)容，構(gòu)建鄰居緩存表，從而利用鄰居節(jié)點(diǎn)提供服務(wù)。由于CCN網(wǎng)絡(luò)中的內(nèi)容數(shù)量巨大，上述探測(cè)的方式存在實(shí)現(xiàn)上的困難，而且導(dǎo)致內(nèi)容請(qǐng)求的響應(yīng)時(shí)間增加。文獻(xiàn)[6]將基于勢(shì)能的路由應(yīng)用于CCN，設(shè)計(jì)緩存感知目標(biāo)識(shí)別路由方法CATT，然而，CATT方法在請(qǐng)求通過(guò)勢(shì)能路由之前采用隨機(jī)轉(zhuǎn)發(fā)的方式，限制了其應(yīng)用。文獻(xiàn)[7]對(duì)節(jié)點(diǎn)副本通告的必要性和可行性進(jìn)行了定性分析，除了通過(guò)布魯姆濾波器進(jìn)行路由表聚合外，缺乏對(duì)緩存特性的定量分析和具體的實(shí)現(xiàn)。此外，上述研究都未考慮節(jié)點(diǎn)上緩存網(wǎng)絡(luò)的動(dòng)態(tài)性和不同內(nèi)容副本的差異性。

對(duì)節(jié)點(diǎn)副本進(jìn)行路由的難點(diǎn)在于CCN緩存節(jié)點(diǎn)上內(nèi)容的動(dòng)態(tài)性和揮發(fā)性，路由到的緩存節(jié)點(diǎn)并不一定包含所請(qǐng)求的內(nèi)容。因此，最大限度地減少這種不確定性成為本文研究的出發(fā)點(diǎn)。借鑒文獻(xiàn)[8-9]對(duì)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中建立快捷鏈接的思想，提出一種基于副本通告的快捷路由(Short-cut Routing, SCR)機(jī)制，解決CCN節(jié)點(diǎn)上副本的路由構(gòu)建問(wèn)題?？旖萋酚蓹C(jī)制對(duì)LRU(Least Recently Used)[10]緩存策略下節(jié)點(diǎn)上副本的有效性進(jìn)行評(píng)估，節(jié)點(diǎn)有選擇地通告，并限定通告范圍，減少了副本路由導(dǎo)致的緩存缺失。與已有研究相比，快捷路由考慮了不同節(jié)點(diǎn)上內(nèi)容命中率的差異性，以此實(shí)現(xiàn)轉(zhuǎn)發(fā)。

2 快捷路由原理

在CCN中，數(shù)據(jù)在內(nèi)容源到請(qǐng)求用戶的路徑上沿途緩存，使得副本分布在多個(gè)節(jié)點(diǎn)。由于網(wǎng)絡(luò)中的內(nèi)容對(duì)象數(shù)量巨大，并且內(nèi)容分布動(dòng)態(tài)變化，如果將節(jié)點(diǎn)緩存的所有內(nèi)容向網(wǎng)絡(luò)進(jìn)行洪泛通告，就會(huì)導(dǎo)致路由表膨脹，帶來(lái)非常大的網(wǎng)絡(luò)開銷。與之相比，快捷路由將緩存與路由緊密地結(jié)合在一起，只將節(jié)點(diǎn)上部分駐留時(shí)間較長(zhǎng)的內(nèi)容進(jìn)行通告。

研究表明，互聯(lián)網(wǎng)存在小世界特性，并且距離相近的地區(qū)，用戶訪問(wèn)具有相似性[11]。因此，快捷路由機(jī)制對(duì)內(nèi)容的通告限于鄰居節(jié)點(diǎn)，從而減少通信開銷，即在局部構(gòu)建了小跳數(shù)環(huán)境。

根據(jù)以上描述，快捷路由的基本思想可以概括為：

(1)副本選擇性通告。緩存節(jié)點(diǎn)將自己緩存的比較活躍的內(nèi)容副本向其鄰居進(jìn)行通告，使得在節(jié)點(diǎn)上緩存的內(nèi)容可以被周邊節(jié)點(diǎn)所“感知”，從而使得副本的覆蓋范圍擴(kuò)大。另一方面，限定副本通告的范圍，即只向特定跳數(shù)之內(nèi)的節(jié)點(diǎn)通告。

(2)選取最優(yōu)內(nèi)容源。節(jié)點(diǎn)在收到副本通告之后，建立內(nèi)容的“局部地圖”，即到達(dá)副本的快捷表項(xiàng)(short-cut entry)，使得節(jié)點(diǎn)知曉內(nèi)容的“存儲(chǔ)位置”，從而選擇最優(yōu)的存儲(chǔ)節(jié)點(diǎn)獲取內(nèi)容。

3 副本通告

對(duì)于任意的CCN節(jié)點(diǎn)a，假定節(jié)點(diǎn)a緩存了內(nèi)容i，a向其n跳內(nèi)的所有鄰居節(jié)點(diǎn)發(fā)送通告消息，通告消息包含內(nèi)容名字、活躍度等，圖1(a)和圖1(b)分別是1跳和2跳內(nèi)容通告示意圖，其中，灰色節(jié)點(diǎn)a是發(fā)送通告消息的節(jié)點(diǎn)；斜紋節(jié)點(diǎn)是灰色節(jié)點(diǎn)a的1跳或2跳鄰居節(jié)點(diǎn)；白色節(jié)點(diǎn)為灰色節(jié)點(diǎn)a 2跳之外的節(jié)點(diǎn)；無(wú)箭頭線條表示節(jié)點(diǎn)之間的鏈路；帶箭頭線條表示通告消息傳輸鏈路。

圖1 內(nèi)容通告示意圖

在內(nèi)容副本信息通告中，需要考慮不同內(nèi)容副本的差異性。內(nèi)容副本在緩存中是動(dòng)態(tài)變化的，由于用戶對(duì)內(nèi)容的請(qǐng)求服從冪律分布，大部分請(qǐng)求訪問(wèn)的是部分熱點(diǎn)內(nèi)容。在特定的時(shí)間段內(nèi)，不同內(nèi)容副本在緩存中駐留的時(shí)間是不同的。

3.1 通告內(nèi)容選取

緩存節(jié)點(diǎn)選取哪些副本向鄰居通告是快捷路由的一個(gè)重要問(wèn)題，直觀的理解是根據(jù)副本在緩存中的持續(xù)時(shí)間長(zhǎng)短來(lái)決定選取哪些副本，然而持續(xù)時(shí)間不容易獲取。根據(jù)緩存的特性，內(nèi)容訪問(wèn)的活躍程度或頻繁程度決定了緩存時(shí)間的長(zhǎng)短，并與具體的緩存策略相關(guān)，現(xiàn)有路由器緩存算法大多采用LRU策略。本節(jié)對(duì)LRU緩存策略下的通告內(nèi)容選取問(wèn)題進(jìn)行分析。

對(duì)于任意的單個(gè)緩存節(jié)點(diǎn)a，M為總的內(nèi)容對(duì)象個(gè)數(shù)，N為節(jié)點(diǎn)a的緩存容量，即節(jié)點(diǎn)a可以緩存的內(nèi)容對(duì)象個(gè)數(shù)為N。圖2為L(zhǎng)RU緩存策略下CCN單個(gè)節(jié)點(diǎn)的緩存模型，Ci表示第i個(gè)內(nèi)容對(duì)象，i=1,2,…,M，l=1,2,…,N表示內(nèi)容對(duì)象在緩存中的位置。在LRU策略下，新加入的內(nèi)容放置在位置N，而位置1的內(nèi)容被淘汰出緩存。在通告副本的選取上，一個(gè)簡(jiǎn)單的策略是選擇緩存位置最高的部分內(nèi)容，然而，LRU策略沒(méi)有考慮內(nèi)容被訪問(wèn)的頻率，因此，緩存位置并不能反映內(nèi)容的“熱度”。相比之下，緩存節(jié)點(diǎn)上內(nèi)容的命中概率能夠更精確地表示從此節(jié)點(diǎn)獲取內(nèi)容的概率。因此，通過(guò)對(duì)LRU緩存模型的分析，獲取內(nèi)容的命中概率，來(lái)指導(dǎo)通告內(nèi)容的選取。

圖2 CCN節(jié)點(diǎn)緩存模型

對(duì)于節(jié)點(diǎn)a上任意的內(nèi)容i，以內(nèi)容i在緩存中的位置為馬爾可夫鏈的狀態(tài)(內(nèi)容i不在緩存中的狀態(tài)為0)，建立馬爾可夫鏈模型，對(duì)緩存特性進(jìn)行分析。假定λ為內(nèi)容i的請(qǐng)求速率，μ為使得內(nèi)容i的緩存位置降低的其他內(nèi)容的請(qǐng)求速率，r為內(nèi)容i移出內(nèi)容緩存器的速率，內(nèi)容請(qǐng)求到達(dá)服從泊松過(guò)程，則內(nèi)容i的狀態(tài)轉(zhuǎn)移如圖3所示。

圖3 CCN節(jié)點(diǎn)緩存馬爾可夫鏈模型

根據(jù)馬爾可夫鏈定義，此鏈為齊次馬爾可夫鏈，其狀態(tài)轉(zhuǎn)移矩陣為：

根據(jù)狀態(tài)轉(zhuǎn)移矩陣Q，計(jì)算出平穩(wěn)分布矢量π=(π0, π1,…,πN)如下：

平穩(wěn)分布π反映了節(jié)點(diǎn)a上內(nèi)容i在各個(gè)緩存位置駐留的概率，特別地，π0表示內(nèi)容不在緩存中的概率，即內(nèi)容i的緩存缺失概率，對(duì)應(yīng)地，內(nèi)容i的命中概率為hi, a= 1-π0。

在式(2)中，λ為內(nèi)容i的請(qǐng)求速率，μ為使得內(nèi)容i的緩存位置降低的其他內(nèi)容的請(qǐng)求速率。文獻(xiàn)[12]分析證明，假定節(jié)點(diǎn)上所有內(nèi)容的請(qǐng)求只有一小部分請(qǐng)求的內(nèi)容位于緩存中，則μ可以近似為節(jié)點(diǎn)上除內(nèi)容i外其他所有內(nèi)容的請(qǐng)求速率。本文利用上述近似得到λ和μ的值，進(jìn)而獲得節(jié)點(diǎn)上各個(gè)內(nèi)容副本的命中概率hi, a，以此指導(dǎo)通告內(nèi)容的選取。

根據(jù)以上分析，節(jié)點(diǎn)計(jì)算出各個(gè)緩存位置上內(nèi)容副本的命中概率，并且設(shè)定閾值φ。對(duì)于任意的內(nèi)容i，只有當(dāng)其命中率hi, a＞φ時(shí)，才通告內(nèi)容i，避免在緩存上存在時(shí)間很短的內(nèi)容被通告出去。

3.2 副本通告范圍設(shè)定

副本通告范圍n的設(shè)定是另一個(gè)需要研究的問(wèn)題。節(jié)點(diǎn)上緩存的內(nèi)容副本不需要洪泛通告到整個(gè)網(wǎng)絡(luò)，n越大，節(jié)點(diǎn)上的路由表項(xiàng)越多，導(dǎo)致快捷路由表膨脹，并且網(wǎng)絡(luò)的控制流量開銷太高。n的設(shè)定需要考慮代價(jià)與收益的權(quán)衡，然而，代價(jià)與收益的計(jì)算依賴于特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，難以通過(guò)統(tǒng)一的方式進(jìn)行分析。為此，快捷路由機(jī)制僅給出確定通告范圍n的3個(gè)主要原則和可行的取值。

原則1 副本通告應(yīng)限定在域內(nèi)。其假定副本的覆蓋范圍主要是域內(nèi)的用戶。

原則2 副本通告產(chǎn)生的控制流量應(yīng)限定在一定程度內(nèi)。以網(wǎng)絡(luò)中副本通告報(bào)文與數(shù)據(jù)報(bào)文(Data Packet)的數(shù)量之比ρ為指標(biāo)，則ρ＜ρ0，其中，ρ0為預(yù)設(shè)的ρ的閾值。

原則3 根據(jù)副本通告建立的快捷路由表的平均條目數(shù)量應(yīng)限定在一定上限內(nèi)。為了減少重復(fù)，節(jié)點(diǎn)在根據(jù)副本通告構(gòu)建快捷表時(shí)可以檢查本地緩存，如果通告的內(nèi)容在本地緩存并且其命中概率較高，則不建立此內(nèi)容的快捷路由表項(xiàng)。

一個(gè)可行的方式是將n設(shè)定為緩存節(jié)點(diǎn)到內(nèi)容服務(wù)器的距離(跳數(shù))n0，其假定為各個(gè)節(jié)點(diǎn)到服務(wù)器的距離近似相等。當(dāng)內(nèi)容的請(qǐng)求節(jié)點(diǎn)到緩存節(jié)點(diǎn)的距離大于到服務(wù)器的距離時(shí)，請(qǐng)求被轉(zhuǎn)發(fā)到服務(wù)器節(jié)點(diǎn)獲取所需內(nèi)容，因此，緩存節(jié)點(diǎn)的內(nèi)容通告范圍大于n0不會(huì)帶來(lái)更大的收益。

為了實(shí)現(xiàn)內(nèi)容副本信息的通告，在CCN中，設(shè)計(jì)針對(duì)快捷路由的副本通告報(bào)文，格式如圖4所示。

圖4 內(nèi)容副本通告報(bào)文格式

類型字段表示報(bào)文的類型，隨機(jī)數(shù)字段為隨機(jī)數(shù)，時(shí)間戳字段用來(lái)記錄報(bào)文的發(fā)送時(shí)間，跳數(shù)字段用來(lái)記錄內(nèi)容通告節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的跳數(shù)。內(nèi)容名字和范圍分別為需要通告的內(nèi)容的名字和通告范圍。

內(nèi)容通告報(bào)文可以一次通告多個(gè)內(nèi)容副本，比如對(duì)相同緩存等級(jí)的所有內(nèi)容名字只發(fā)送一個(gè)通告報(bào)文。為了對(duì)多個(gè)內(nèi)容名字進(jìn)行壓縮，采用布魯姆濾波器對(duì)名字列表進(jìn)行壓縮，并作為內(nèi)容副本通告報(bào)文的內(nèi)容名字域。節(jié)點(diǎn)收到副本通告報(bào)文后，建立快捷路由表。不失一般性，本文后續(xù)部分，仍以內(nèi)容名字作為路由表項(xiàng)。

4 快捷路由表構(gòu)建

節(jié)點(diǎn)在收到鄰居關(guān)于內(nèi)容的通告后，根據(jù)內(nèi)容名字、到達(dá)接口和到達(dá)此鄰居的跳數(shù)，創(chuàng)建如表1所示的快捷路由表(short-cut table)。

表1 快捷路由表

當(dāng)同一個(gè)內(nèi)容存在多個(gè)轉(zhuǎn)發(fā)接口時(shí)，則選擇跳數(shù)最小的接口轉(zhuǎn)發(fā)興趣包。由于快捷路由轉(zhuǎn)發(fā)到的節(jié)點(diǎn)并不保證一定存在所需的內(nèi)容，即存在內(nèi)容缺失，因此建立類似于文獻(xiàn)[7]中的回退機(jī)制，當(dāng)請(qǐng)求的內(nèi)容缺失時(shí)，可以回退到請(qǐng)求包的來(lái)源節(jié)點(diǎn)選擇其他的接口轉(zhuǎn)發(fā)。

5 工作流程

快捷路由可以分為以下階段：快捷路由構(gòu)建階段和內(nèi)容傳遞階段。

快捷路由構(gòu)建階段主要進(jìn)行內(nèi)容的通告和快捷路由表的構(gòu)建，其步驟如下：

Step1 內(nèi)容緩存節(jié)點(diǎn)根據(jù)當(dāng)前緩存表中的內(nèi)容及其活躍度，構(gòu)造某個(gè)或某些內(nèi)容的內(nèi)容通告報(bào)文，設(shè)定需要通告的范圍并向所有接口進(jìn)行轉(zhuǎn)發(fā)。

Step2 當(dāng)前節(jié)點(diǎn)在收到內(nèi)容通告報(bào)文后，判斷當(dāng)前收到的內(nèi)容通告報(bào)文是否已存在，即報(bào)文內(nèi)容和隨機(jī)數(shù)是否都相同，如果相同則丟棄該通告報(bào)文，否則執(zhí)行Step3。

Step3 節(jié)點(diǎn)在收到內(nèi)容通告報(bào)文后，更新范圍值。節(jié)點(diǎn)檢查快捷表，如果存在此報(bào)文中內(nèi)容名字對(duì)應(yīng)的表項(xiàng)，則更新表項(xiàng)信息，否則創(chuàng)建快捷路由條目，然后根據(jù)范圍值的大小決定是否轉(zhuǎn)發(fā)此內(nèi)容通告。

Step4 當(dāng)緩存節(jié)點(diǎn)的所有內(nèi)容變化達(dá)到一定程度或經(jīng)過(guò)時(shí)間間隔T后，重復(fù)Step1～Step3，重新進(jìn)行內(nèi)容通告，并且更新快捷路由表。

快捷路由表構(gòu)建完成后，節(jié)點(diǎn)收到內(nèi)容請(qǐng)求即興趣包后，按照內(nèi)容緩存表、快捷路由表和轉(zhuǎn)發(fā)信息表的順序查表，執(zhí)行相應(yīng)的轉(zhuǎn)發(fā)操作。興趣包在節(jié)點(diǎn)內(nèi)的轉(zhuǎn)發(fā)過(guò)程如圖5所示，其中，C表示內(nèi)容緩存表；P表示PIT表；S表示快捷路由表；F表示FIB表。

圖5 節(jié)點(diǎn)內(nèi)興趣包轉(zhuǎn)發(fā)過(guò)程

6 仿真實(shí)驗(yàn)與分析

本節(jié)對(duì)快捷路由在CCN中的性能進(jìn)行仿真驗(yàn)證。實(shí)驗(yàn)使用GT-ITM工具產(chǎn)生網(wǎng)絡(luò)拓?fù)洌⑹褂肰C++2008和Matlab2010工具進(jìn)行仿真。

仿真參數(shù)描述如下：網(wǎng)絡(luò)包含30節(jié)點(diǎn)，任意節(jié)點(diǎn)之間以0.3的概率相連。鏈路帶寬為100 Mb/s。在邊緣節(jié)點(diǎn)中，隨機(jī)選取1個(gè)節(jié)點(diǎn)作為內(nèi)容源服務(wù)器，負(fù)責(zé)內(nèi)容原本的發(fā)布和服務(wù)，其容量足夠存儲(chǔ)所有內(nèi)容對(duì)象，其余節(jié)點(diǎn)為普通的CCN路由節(jié)點(diǎn)，并且與用戶直接相連，緩存容量為B(假定內(nèi)容對(duì)象大小相同，則B表示節(jié)點(diǎn)可以緩存的內(nèi)容個(gè)數(shù))，緩存策略為L(zhǎng)RU。網(wǎng)絡(luò)中內(nèi)容個(gè)數(shù)為N=2 000個(gè)，假定內(nèi)容大小相等，設(shè)為128 KB。內(nèi)容對(duì)象的流行度服從Zipf-Mandelbrot分布[13]，即第k個(gè)內(nèi)容對(duì)象的流行度為Pk=H-1(σ, q, N)/(q+k)σ，其中，σ為形狀參數(shù)，q為移動(dòng)參數(shù)，取σ=0.4，q=10；H(σ, q, N)為歸一化系數(shù)。

用戶請(qǐng)求到達(dá)服從到達(dá)速率λ=4個(gè)/s的泊松過(guò)程，并且在各個(gè)路由節(jié)點(diǎn)隨機(jī)到達(dá)；節(jié)點(diǎn)內(nèi)容通告間隔為δ。仿真實(shí)驗(yàn)的硬件環(huán)境如下：處理器主頻為雙核2.37 GHz，2 GB內(nèi)存，Windows7操作系統(tǒng)。

為了對(duì)快捷路由的性能進(jìn)行驗(yàn)證，以用戶請(qǐng)求平均時(shí)延和內(nèi)容源服務(wù)器負(fù)載為性能指標(biāo)進(jìn)行對(duì)比。源服務(wù)器負(fù)載定義為單位時(shí)間內(nèi)收到的請(qǐng)求包個(gè)數(shù)，在仿真中將單位時(shí)間取為仿真程序運(yùn)行時(shí)間，因此，源服務(wù)器負(fù)載可以表示為仿真期間源服務(wù)器收到的請(qǐng)求包個(gè)數(shù)。

仿真的目標(biāo)路由算法為：(1)基本的CCN路由[3]，不考慮節(jié)點(diǎn)副本的路由，記為BasicCCN；(2)鄰居緩存探測(cè)策略NCE；(3)文獻(xiàn)[7]提出的通告緩存副本的路由方式，記為ACC；(4)本文提出的快捷路由SCR，內(nèi)容通告閾值φ=0.4，通告范圍取節(jié)點(diǎn)到服務(wù)器的跳數(shù)。除了BasicCCN之外，假定其余4種方法中鄰居緩存節(jié)點(diǎn)內(nèi)容缺失時(shí)，直接將請(qǐng)求包轉(zhuǎn)發(fā)到服務(wù)器獲取內(nèi)容。

6.1 用戶請(qǐng)求平均時(shí)延

設(shè)置節(jié)點(diǎn)內(nèi)容通告間隔為δ=4 s。在仿真過(guò)程中共產(chǎn)生2 000個(gè)內(nèi)容請(qǐng)求，記節(jié)點(diǎn)從內(nèi)容請(qǐng)求發(fā)出到收到所請(qǐng)求的數(shù)據(jù)的時(shí)延為單個(gè)請(qǐng)求時(shí)延，則所有內(nèi)容請(qǐng)求的平均時(shí)延仿真結(jié)果如圖6所示。

圖6 用戶請(qǐng)求平均時(shí)延

由圖6可以看出，BasicCCN路由算法不考慮節(jié)點(diǎn)上內(nèi)容副本的路由，導(dǎo)致時(shí)延最大。NCE和ACC都建立了到達(dá)鄰居節(jié)點(diǎn)副本的路由表，但是不考慮鄰居節(jié)點(diǎn)上內(nèi)容的命中概率的差異性，請(qǐng)求被轉(zhuǎn)發(fā)到的節(jié)點(diǎn)存在內(nèi)容缺失的情況，導(dǎo)致這些請(qǐng)求的時(shí)延增加。相比之下，快捷路由考慮了緩存節(jié)點(diǎn)內(nèi)容的命中概率，減少了緩存缺失導(dǎo)致重新獲取內(nèi)容的情況，所有請(qǐng)求的平均時(shí)延最小。與基本的CCN路由算法相比，在緩存容量從10增加到100時(shí)，當(dāng)緩存容量為10時(shí)，相比BasicCCN，快捷路由減少了約9%的用戶請(qǐng)求平均時(shí)延；當(dāng)緩存容量為100時(shí)，可以得到，快捷路由比BasicCCN減少約17%的用戶請(qǐng)求平均時(shí)延。

6.2 內(nèi)容源服務(wù)器負(fù)載

取固定的緩存容量B=60、內(nèi)容請(qǐng)求數(shù)Nq=2 000個(gè)、節(jié)點(diǎn)內(nèi)容通告間隔為δ=4 s。以內(nèi)容服務(wù)器收到的用戶請(qǐng)求即興趣包的個(gè)數(shù)作為其負(fù)載指標(biāo)，則服務(wù)器負(fù)載性能的仿真結(jié)果如圖7所示。

圖7 內(nèi)容源服務(wù)器負(fù)載

由圖7可見，在總的內(nèi)容請(qǐng)求數(shù)為2 0 00的情況下，BasicCCN只將請(qǐng)求路由到確定的服務(wù)器，因而不會(huì)產(chǎn)生額外的請(qǐng)求包，其他3種算法都會(huì)產(chǎn)生額外的請(qǐng)求包，這是因?yàn)榭紤]了緩存內(nèi)容缺失導(dǎo)致重新產(chǎn)生請(qǐng)求包。在服務(wù)器收到的請(qǐng)求包數(shù)量上，BasicCCN最多，因?yàn)槠渲荒芾棉D(zhuǎn)發(fā)路徑上的部分緩存的內(nèi)容，而ACE、NCE和快捷路由利用了緩存節(jié)點(diǎn)的副本資源，有效地減少了內(nèi)容服務(wù)器的負(fù)載。快捷路由相對(duì)于BasicCCN，在服務(wù)器負(fù)載上減少了約43%。

6.3 內(nèi)容通告比例對(duì)性能的影響

在快捷路由機(jī)制中，CCN網(wǎng)絡(luò)中的緩存節(jié)點(diǎn)根據(jù)緩存內(nèi)容的命中概率大小，將命中概率最高的比例為x(0＜x＜1)的內(nèi)容向鄰居節(jié)點(diǎn)進(jìn)行通告，內(nèi)容通告比例x的選取是一個(gè)需要考慮的問(wèn)題。取緩存容量B=60，總的請(qǐng)求數(shù)Nq= 2 000個(gè)，節(jié)點(diǎn)內(nèi)容通告間隔為δ=4 s。以內(nèi)容通告比例x為變量對(duì)快捷路由時(shí)延性能進(jìn)行仿真，結(jié)果如圖8所示。

圖8 內(nèi)容通告比例對(duì)性能的影響

由圖8可看出，隨著內(nèi)容通告比例x增加，用戶請(qǐng)求平均時(shí)延減少。然而，當(dāng)x＞0.8時(shí)，平均時(shí)延反而有所增加，這是因?yàn)榫彺嬷械膬?nèi)容存在動(dòng)態(tài)性，將部分命中概率低的內(nèi)容通告出去，導(dǎo)致請(qǐng)求被轉(zhuǎn)發(fā)到的節(jié)點(diǎn)內(nèi)容已被淘汰，造成緩存缺失，重新從其他節(jié)點(diǎn)獲取內(nèi)容使得時(shí)延增加。

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

本文在CCN內(nèi)容路由基礎(chǔ)上，針對(duì)其無(wú)法利用節(jié)點(diǎn)緩存的內(nèi)容副本的缺陷，在分析常用的LRU緩存策略的基礎(chǔ)上，提出一種基于副本通告的快捷路由機(jī)制，以解決內(nèi)容中心網(wǎng)絡(luò)中內(nèi)容副本的路由問(wèn)題。下一步工作是將快捷路由應(yīng)用到實(shí)際網(wǎng)絡(luò)環(huán)境中進(jìn)一步驗(yàn)證其性能。

[1] Jacobson V, Mosk o M, Smetters D, et al. Content-centric Networking[EB/OL]. (2007-02-18). http://w ww.ietf.org/proceedings/65/slides/DTNRG-12.pdf.

[2] Chiocchetti R, Rossi D, Rossini G, et al. Exploit the Known or Explore the Unknown?[C]//Proceedings of the 2nd Edition of the ICN Workshop on Infor mation-centric Networking. Helsinki, Finland: ACM Press, 2012: 7-12.

[3] Zhang Lixia, Estrin D, Burke J, et al. Named Data Networking Project[R]. PARC, Tech. Rep.: ndn-0001, 2010.

[4] Shanbhag S, Schwan N, Rimac I, et al. SoCCeR: Services over Content-centric Routing[C]//Proceedings of ACM SIGCOMM Workshop o n Information-centric Networking. T oronto, Canada: ACM Press, 2011: 62-67.

[5] 葉潤(rùn)生, 徐明偉. 命名數(shù)據(jù)網(wǎng)絡(luò)中的鄰居緩存路由策略[J].計(jì)算機(jī)科學(xué)與探索, 2012, 6(7): 593-601.

[6] Eum S, Nakauchi K, Murata M, et al. CATT: Potential Based Routing with Content Caching for ICN[C]//Proceedings of ACM SIGCOMM Workshop on Information-centric Networking. Helsinki, Finland: ACM Press, 2012: 49-54.

[7] Wang Yaogong, Lee K. Adv ertising Cached Contents in the Control Plane: Necessity and Feasibility[C]//Proceedings of 2012 I EEE Conference o n Computer Comm unications Workshops. Orlando, USA: [s. n.], 2012: 1045-1053.

[8] Sripanidkulchai K, Maggs B. Efficient Content Location Using Interest-based Locality in Peer-to-Peer Systems[C]// Proceedings of I EEE INFOCOM’03. Sa n Fran cisco, USA: [s. n.], 2003: 364-372.

[9] Pireddo L, Nascimento M A. Taxonomy-based Routing Indices for Peer-to-Peer Networks[C]//Proceedings of Workshop o n Peer-to-Peer Inf ormation Retrieva l. S heffield, UK: [s. n.], 2004: 321-328.

[10] Seung W, Ki Y, Jo ng S. LRU Based Sm all Latency First Replacement(SLFR) Algorithm for the Proxy Cache[C]// Proceedings of IEEE International Conference on Web Intelligence. Daejon, South Korea: [s. n.], 2003: 499-502.

[11] Fonsecaf R, Almeida V, Crovella M. Lo cality in a Web of Stream[J]. Communications of the ACM, 2003, 48(1): 82-88.

[12] Psaras I, Cle gg R G, Landa R, et al. Modeling and Evaluation of CCN-caching Trees[C]//Proceedings of the 10th International IFIP TC 6 Conference on Networking. Heidelberg, Germany: Springer, 2011: 78-91.

[13] 蔡青松, 李子木, 胡建平. Internet上的流媒體特性及用戶訪問(wèn)行為研究[J]. 北京航空航天大學(xué)學(xué)報(bào), 2005, 31(1): 25-30.

編輯 陸燕菲

Short-cut Routing Mechanism in Content Centric Network Based on Replicas Notification

LIU Tao, CHENG Dong-nian, TIAN Ming

(National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China)

Content Centric Network(CCN) is a novel paradigm for content distribution with name-based routing. However, the basic CCN routing mechanism only creates routing entries to server c ontents and lacks routing to cache contents on nodes, leading to low cache resource utilization and large content access latency. To solve this problem, a Short-cut Routing(SCR) is presented, based on the notification of cache content replicas, which enables nodes to perceive neighbor’s cache information and retrieve contents from the best routing content source. Simulation results show that the SCR significantly reduces the average delay compared to the basic routing m echanism which does not take into account routing to cache contents, gives the cache capacity of the 60 content objects, and SCR reduces the server load by 43%.

Content Centric Network(CCN); Short-cut Routing(SCR); content activeness; Named Data Network(NDN); Markov chain; replicas

10.3969/j.issn.1000-3428.2014.05.014

國(guó)家“973”計(jì)劃基金資助項(xiàng)目(2012CB315901)；國(guó)家“863”計(jì)劃基金資助項(xiàng)目(2011AA01A101, 2011AA01A103)；國(guó)家科技支撐計(jì)劃基金資助項(xiàng)目(2011BAH19B01)。

劉 濤(1985－)，男，碩士研究生，主研方向：寬帶信息網(wǎng)絡(luò)，網(wǎng)絡(luò)體系結(jié)構(gòu)；程?hào)|年，教授；田 銘，博士研究生。

2013-03-22

2013-05-15E-mail：liutaota168@163.com

1000-3428(2014)05-0062-06

A

TP393