杜傳震，蘭巨龍，田 銘

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

1 引言

隨著互聯(lián)網(wǎng)技術(shù)與應(yīng)用的飛速發(fā)展以及互聯(lián)網(wǎng)用戶數(shù)量的快速增長(zhǎng)，傳統(tǒng)IP網(wǎng)絡(luò)中的地址既表示節(jié)點(diǎn)位置信息又表示身份信息的方式混淆了位置和標(biāo)識(shí)的功能界限，在支持內(nèi)容分發(fā)業(yè)務(wù)方面的局限性越來越明顯。針對(duì)該問題，近年來提出的一種將內(nèi)容與主機(jī)在網(wǎng)絡(luò)層分離的創(chuàng)新思想引起了廣泛關(guān)注。以內(nèi)容為中心的網(wǎng)絡(luò)成為未來網(wǎng)絡(luò)的一種重要模式和發(fā)展趨勢(shì)。

命名數(shù)據(jù)網(wǎng)絡(luò)（named data networking，NDN）是一個(gè)全新的網(wǎng)絡(luò)架構(gòu)，使用層次化的數(shù)據(jù)名字而不是IP地址進(jìn)行數(shù)據(jù)傳遞，讓數(shù)據(jù)本身成為互聯(lián)網(wǎng)架構(gòu)中的核心要素[1～3]。該架構(gòu)采用“興趣分組”的形式以通告的方式實(shí)現(xiàn)點(diǎn)到多點(diǎn)的內(nèi)容獲取和分發(fā)；“數(shù)據(jù)分組”沿著“興趣分組”到達(dá)的反向路徑傳遞給內(nèi)容的請(qǐng)求者，實(shí)現(xiàn)了基于跳的流量平衡，并試圖在路徑節(jié)點(diǎn)上以“緩存”的形式駐留熱度較高的服務(wù)內(nèi)容，盡可能地以最短傳輸路徑抵近請(qǐng)求用戶。NDN路由與轉(zhuǎn)發(fā)模型如圖1所示。

圖1 NDN路由與轉(zhuǎn)發(fā)模型

命名數(shù)據(jù)網(wǎng)絡(luò)直接基于名字的路由和轉(zhuǎn)發(fā)方式，有效地解決了IP網(wǎng)絡(luò)中地址空間耗盡、移動(dòng)性與可擴(kuò)展性差等問題。NDN路由器負(fù)責(zé)發(fā)布名字前綴公告，并通過路由協(xié)議在網(wǎng)絡(luò)中傳播，每個(gè)接收到公告的路由器建立自己的轉(zhuǎn)發(fā)信息庫(kù)（forwarding information base，F(xiàn)IB）。當(dāng)有多個(gè)興趣分組同時(shí)請(qǐng)求相同數(shù)據(jù)時(shí)，路由器只會(huì)轉(zhuǎn)發(fā)收到的第一個(gè)興趣分組，并將這些請(qǐng)求存儲(chǔ)在未決興趣表（pending interest table，PIT）中。當(dāng)數(shù)據(jù)分組傳回時(shí)，路由器會(huì)在PIT中找到與之匹配的條目，并根據(jù)條目中顯示的接口列表，分別向這些接口轉(zhuǎn)發(fā)數(shù)據(jù)分組。轉(zhuǎn)發(fā)完成后，路由器會(huì)刪除相應(yīng)的PIT條目，并將數(shù)據(jù)分組存儲(chǔ)在內(nèi)容緩存（content store，CS）中。CS是路由器的緩沖存儲(chǔ)器，使用某種緩沖替代策略。

命名數(shù)據(jù)網(wǎng)絡(luò)采用針對(duì)內(nèi)容的路由方式:節(jié)點(diǎn)興趣分組直接面向內(nèi)容源服務(wù)器進(jìn)行轉(zhuǎn)發(fā)，在轉(zhuǎn)發(fā)過程中探知所經(jīng)各節(jié)點(diǎn)是否緩存所請(qǐng)求的內(nèi)容，以達(dá)到最短時(shí)間返回?cái)?shù)據(jù)的目的。雖然相較于IP網(wǎng)絡(luò)，命名數(shù)據(jù)網(wǎng)絡(luò)的內(nèi)容路由方式提高了返回?cái)?shù)據(jù)分組的效率，但是這種路徑緩存方式使不在路徑上的鄰近緩存內(nèi)容無法被充分利用。如圖2所示，用戶周圍的路由節(jié)點(diǎn)存儲(chǔ)著相應(yīng)的數(shù)據(jù)，但不能得到有效利用，這種現(xiàn)象導(dǎo)致訪問數(shù)據(jù)路徑過長(zhǎng)。

圖2 命名數(shù)據(jù)網(wǎng)絡(luò)中內(nèi)容獲取過程

針對(duì)命名數(shù)據(jù)網(wǎng)絡(luò)中內(nèi)容路由節(jié)點(diǎn)的緩存利用率問題，相關(guān)研究已經(jīng)取得了一定的進(jìn)展和成果。Shanbhag S等人提出了一種服務(wù)路由方法SoCCeR （services over content-centric routing），將內(nèi)容路由問題歸結(jié)為服務(wù)選取問題，實(shí)現(xiàn)了對(duì)沿途節(jié)點(diǎn)緩存的充分利用，但仍未考慮對(duì)鄰近節(jié)點(diǎn)緩存的內(nèi)容[5]。參考文獻(xiàn)[3]比較了exploitation（開發(fā)）和exploration（探測(cè)）兩種不同的內(nèi)容路由機(jī)制，并且提出了一種混合的路由方法，即對(duì)源服務(wù)器的內(nèi)容建立路由，而對(duì)節(jié)點(diǎn)緩存的內(nèi)容副本進(jìn)行探測(cè)，但其出發(fā)點(diǎn)是減少路由條目數(shù)量和網(wǎng)絡(luò)代價(jià)。參考文獻(xiàn)[6]將基于勢(shì)能的路由應(yīng)用于內(nèi)容網(wǎng)絡(luò)，設(shè)計(jì)了緩存感知目標(biāo)識(shí)別 （cache aware target identification,CATT）路由方法。然而，CATT路由方法在請(qǐng)求通過勢(shì)能路由之前采用隨機(jī)轉(zhuǎn)發(fā)的方式，其路由性能取決于隨機(jī)轉(zhuǎn)發(fā)的初始值設(shè)置，可能會(huì)導(dǎo)致較長(zhǎng)的路徑時(shí)延。參考文獻(xiàn)[7]提出了通過探測(cè)鄰居節(jié)點(diǎn)緩存的內(nèi)容，構(gòu)建鄰居緩存表的NCE路由策略，從而充分利用鄰居節(jié)點(diǎn)資源。但考慮到NDN中的內(nèi)容數(shù)量巨大，該探測(cè)方式存在實(shí)現(xiàn)上的困難，會(huì)導(dǎo)致內(nèi)容請(qǐng)求的平均響應(yīng)時(shí)間增加。參考文獻(xiàn)[8]對(duì)節(jié)點(diǎn)副本通告的必要性和可行性進(jìn)行了定性分析，雖提出利用布魯姆濾波器進(jìn)行路由表聚合，仍缺乏對(duì)路由機(jī)制的定量分析和具體實(shí)現(xiàn)方式。此外，上述研究都未考慮節(jié)點(diǎn)上緩存內(nèi)容的根據(jù)熱度的動(dòng)態(tài)更新以及不同內(nèi)容緩存之間的差異性。

本文借鑒參考文獻(xiàn)[9]和參考文獻(xiàn)[10]中對(duì)非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中建立快捷鏈接的思想，提出一種面向鄰近緩存的導(dǎo)向式便捷路由（fast content routing，F(xiàn)CR）機(jī)制，解決了命名數(shù)據(jù)網(wǎng)絡(luò)中鄰近緩存路由構(gòu)建的問題。

2 便捷路由定義

內(nèi)容源服務(wù)器路徑為用戶節(jié)點(diǎn)S發(fā)送興趣分組到達(dá)內(nèi)容源服務(wù)器D的最短路徑，期間經(jīng)過的節(jié)點(diǎn)集合為S={Na，Nb，…，Nm}，響應(yīng)跳數(shù)為 H1。

定義 1 （便捷路由路徑（fast content path，F(xiàn)CP））將用戶節(jié)點(diǎn)S到存儲(chǔ)所需內(nèi)容的最近鄰近緩存節(jié)點(diǎn)N（N埸S）的最短路徑定義為用戶S的便捷路由路徑，期間轉(zhuǎn)發(fā)節(jié)點(diǎn)集合為 SFCP={NA，NB，…，NM}，響應(yīng)跳數(shù)為 H2，如圖 3 所示。

圖3 請(qǐng)求節(jié)點(diǎn)的便捷路由路徑

定理 路由節(jié)點(diǎn)N作為到用戶節(jié)點(diǎn)S最近的緩存節(jié)點(diǎn)，必然使得H2≤H1，否則內(nèi)容源作為最近緩存與定義相矛盾。若用戶 S存在 FCP，則SFCP∩S≠○/。

證明 用反證法。假設(shè)SFCP∩S≠○/，接入網(wǎng)絡(luò)的路由節(jié)點(diǎn)為N0。由網(wǎng)絡(luò)中內(nèi)容源路徑必然存在，則N0∈S且N0埸SFCP，則S的接入點(diǎn)N0與路由節(jié)點(diǎn)N不連通，則FCP不存在，與已知矛盾，故而假設(shè)不成立。

根據(jù)便捷路由路徑與服務(wù)器路徑至少具有一個(gè)相交點(diǎn)的原理，為了尋找構(gòu)建 FCP，只需由 S={Na，Nb，…，Nm}獲知其他近鄰節(jié)點(diǎn)N對(duì)應(yīng)內(nèi)容C的存儲(chǔ)內(nèi)容且計(jì)算相應(yīng)路由。

3 緩存通告及代價(jià)

節(jié)點(diǎn)周圍的緩存分布情況主要可以由探測(cè)與主動(dòng)通告兩種方式獲得。探測(cè)雖然可以針對(duì)具體內(nèi)容進(jìn)行精確定位，但是產(chǎn)生的流量是雙向的，網(wǎng)絡(luò)代價(jià)太高，難以大規(guī)模部署。相較于探測(cè)的方式，主動(dòng)通告方式的流量是單向的。在合理控制通告范圍的情況下，批量分發(fā)自身的緩存內(nèi)容條目可以將網(wǎng)絡(luò)代價(jià)降至最低。

設(shè)網(wǎng)絡(luò)拓?fù)溆蒅={V，E}表示，V是節(jié)點(diǎn)的集合，E為鏈路的集合，網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為|V|。通告數(shù)據(jù)分組大小為B，節(jié)點(diǎn)平均連接度為m，命名數(shù)據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的緩存根據(jù)內(nèi)容熱度不斷發(fā)生變化，間隔為T。在網(wǎng)絡(luò)G中時(shí)間T內(nèi)至少產(chǎn)生|V|次緩存變化，需要通過N（N為不小于logm|V|的整數(shù)）次通告，才能將一次緩存內(nèi)容更新發(fā)送至網(wǎng)絡(luò)中所有節(jié)點(diǎn)。那么產(chǎn)生的流量代價(jià)為:

由于內(nèi)容節(jié)點(diǎn)緩存更新時(shí)間最短的只有數(shù)秒，單位時(shí)間內(nèi)的流量代價(jià)為C/T≥|V|2·B/T。

為了減少緩存內(nèi)容通告代價(jià)，本文提出的引導(dǎo)式便捷路由通告機(jī)制的主要原理包含3個(gè)方面。

（1）設(shè)定面向鄰近緩存內(nèi)容的合理通告范圍|V|

互聯(lián)網(wǎng)存在小世界特性，距離相近的地區(qū)訪問與緩存的內(nèi)容具有相似性[11]。由于同一個(gè)集群節(jié)點(diǎn)對(duì)同一類內(nèi)容感興趣的概率很大，提出基于興趣關(guān)聯(lián)度的標(biāo)準(zhǔn)來構(gòu)建節(jié)點(diǎn)興趣集群。因此，在整個(gè)網(wǎng)絡(luò)中通告節(jié)點(diǎn)緩存消息是繁瑣而且沒有必要的，將通告范圍縮小在興趣集群內(nèi)可以提高通告內(nèi)容利用率?；诖送普?，本文提出一種引導(dǎo)式的便捷內(nèi)容路由通告機(jī)制，克服洪泛法通告產(chǎn)生的巨大流量代價(jià)。

（2）選取熱度較高的內(nèi)容延長(zhǎng)通告時(shí)間間隔T

NDN中的內(nèi)容路由查找伴隨著節(jié)點(diǎn)緩存的頻繁更新，具有動(dòng)態(tài)性與揮發(fā)性。節(jié)點(diǎn)內(nèi)更替頻繁的緩存條目對(duì)于捷徑路由沒有指導(dǎo)意義，可能會(huì)造成路由振蕩，故本文提出只通告節(jié)點(diǎn)緩存中熱度較高，即長(zhǎng)期處于穩(wěn)態(tài)的部分存儲(chǔ)數(shù)據(jù)。由于節(jié)點(diǎn)內(nèi)更替頻繁的緩存信息不向外通告，使得通告時(shí)間間隔延長(zhǎng)，也確保網(wǎng)絡(luò)中的節(jié)點(diǎn)緩存內(nèi)容的穩(wěn)定性。

（3）設(shè)計(jì)獨(dú)特的通告報(bào)文結(jié)構(gòu)以減少通告報(bào)文的大小B

通告內(nèi)容通常包含節(jié)點(diǎn)緩存中的副本信息的名字。本文擬借鑒布魯姆過濾器的研究成果，提出一種光譜布魯姆過濾器的高效數(shù)據(jù)結(jié)構(gòu)，減少通告報(bào)文的大小。

4 引導(dǎo)式便捷內(nèi)容路由機(jī)制

4.1 基本思想

本文提出的引導(dǎo)式鄰近緩存通告機(jī)制首先依據(jù)節(jié)點(diǎn)緩存熱度與需求的相似性，將網(wǎng)絡(luò)節(jié)點(diǎn)劃分為若干興趣節(jié)點(diǎn)集群。集群節(jié)點(diǎn)只在內(nèi)部通告熱度較高的緩存內(nèi)容，不屬于同一集群的節(jié)點(diǎn)之間不進(jìn)行緩存通告。便捷內(nèi)容路由的構(gòu)建大致分為3個(gè)步驟:集群構(gòu)建、緩存通告以及便捷路由建立。便捷路由表構(gòu)建完成后，節(jié)點(diǎn)若收到內(nèi)容請(qǐng)求，按照內(nèi)容緩存表、未決興趣表、便捷路由表和轉(zhuǎn)發(fā)信息表的順序查表，執(zhí)行相應(yīng)的轉(zhuǎn)發(fā)操作。

4.2 節(jié)點(diǎn)興趣集群的構(gòu)建

在NDN中，給定內(nèi)容需求節(jié)點(diǎn)i與j，興趣內(nèi)容集合分 別 為 Cinterest（i）、Cinterest（j），則 它 們 共 同 的 興 趣 集 合 為 PC=Cinterest（i）∩Cinterest（j）。若節(jié)點(diǎn) i在過去的時(shí)間段 T 內(nèi)對(duì)內(nèi)容的需求次數(shù)為MC，i，那么節(jié)點(diǎn)i與節(jié)點(diǎn)j的興趣關(guān)聯(lián)系數(shù)（interest relevancy coefficient）則定義為:

MC，j與 MC，j分別表示節(jié)點(diǎn) i、j對(duì)內(nèi)容 C 在過去時(shí)間段T 內(nèi)的需求次數(shù)。MC，j與 MC，j的值越接近，則對(duì) θ（i，j）的影響越大，說明節(jié)點(diǎn)i、j兩節(jié)點(diǎn)對(duì)內(nèi)容C的興趣關(guān)聯(lián)度越大。反之，則關(guān)聯(lián)度越小。由于 MC，j與 MC，j不排除為 0的可能性，正數(shù)d確保除數(shù)不為0。

4.2.1 核心節(jié)點(diǎn)的選取

節(jié)點(diǎn)興趣集群的構(gòu)建不是無序的，選取興趣相關(guān)度最高的核心節(jié)點(diǎn)（leader node）構(gòu)建興趣集群，可以使得集群的收益提高。定義節(jié)點(diǎn)i的關(guān)聯(lián)度ηi為該節(jié)點(diǎn)與其鄰居節(jié)點(diǎn) 的 興 趣 關(guān) 聯(lián) 系 數(shù) 之 和θ（i，j），作 為 選 取核節(jié)點(diǎn)的標(biāo)準(zhǔn)。選取的核節(jié)點(diǎn)關(guān)聯(lián)度越高，該集群收益越大。

在興趣集群中，對(duì)興趣節(jié)點(diǎn)進(jìn)行統(tǒng)計(jì)比較，可以將節(jié)點(diǎn)的關(guān)聯(lián)系數(shù)ηi作為該節(jié)點(diǎn)選取優(yōu)先值。興趣節(jié)點(diǎn)對(duì)鄰近節(jié)點(diǎn)進(jìn)行范圍通告。為了減少核心節(jié)點(diǎn)選取導(dǎo)致的流量冗余，興趣節(jié)點(diǎn)的ηi越大，則等待的時(shí)間越短。節(jié)點(diǎn)收到比自身優(yōu)先值大的通告時(shí)，不再通告自身的ηi，而是將具備較大優(yōu)先值的節(jié)點(diǎn)信息通告出去。

4.2.2 興趣集群范圍確定

為了體現(xiàn)鄰近節(jié)點(diǎn)緩存的優(yōu)勢(shì)，提高便捷路由的效率，命名數(shù)據(jù)網(wǎng)絡(luò)中的請(qǐng)求節(jié)點(diǎn)所在集群的范圍設(shè)定不宜過大（即H2≤H1）。參考文獻(xiàn)[7]對(duì)內(nèi)容網(wǎng)絡(luò)的范圍通告進(jìn)行了詳細(xì)的研究，指出通告范圍scope為2的網(wǎng)絡(luò)集群平均時(shí)延僅僅比scope為1的網(wǎng)絡(luò)集群減少3%。對(duì)于具備緩存能力的內(nèi)容網(wǎng)絡(luò)，絕大多數(shù)內(nèi)容需求都可以在請(qǐng)求節(jié)點(diǎn)的鄰近1～2的節(jié)點(diǎn)范圍內(nèi)得到滿足（即3跳范圍）?？紤]到雙向傳輸?shù)臅r(shí)延疊加，在參考文獻(xiàn)[7]的基礎(chǔ)上，將本文的網(wǎng)絡(luò)通告范圍的上限設(shè)定為6跳，即scope=6，在后面章節(jié)通過仿真實(shí)驗(yàn)，對(duì)通告范圍的最優(yōu)值進(jìn)行討論。

4.2.3 興趣集群構(gòu)建算法

根據(jù)興趣關(guān)聯(lián)度的集群構(gòu)建需要考慮緩存內(nèi)容及其熱度，只通告部分長(zhǎng)期處于穩(wěn)態(tài)的緩存數(shù)據(jù)。構(gòu)建流程如下。

步驟1 內(nèi)容緩存節(jié)點(diǎn)根據(jù)當(dāng)前緩存表中的內(nèi)容及其熱度，計(jì)算該節(jié)點(diǎn)的興趣關(guān)聯(lián)度ηi，構(gòu)造某種或某些內(nèi)容的通告報(bào)文。

步驟2在等待T時(shí)間之后，將該節(jié)點(diǎn)的內(nèi)容關(guān)聯(lián)度通告給鄰近節(jié)點(diǎn)，設(shè)定需要的通告范圍scope和hop值并向所有接口進(jìn)行轉(zhuǎn)發(fā)。

步驟3 在時(shí)間T內(nèi)，對(duì)節(jié)點(diǎn)接收到的報(bào)文進(jìn)行比較，計(jì)算比較節(jié)點(diǎn)優(yōu)先值，將具備較大優(yōu)先值的信息通告出去。

步驟4 當(dāng)前節(jié)點(diǎn)在收到內(nèi)容通告報(bào)文后，將收到的ηi和自身的ηi進(jìn)行比較，若收到的節(jié)點(diǎn)通告興趣關(guān)聯(lián)度較大，則節(jié)點(diǎn)更新集群的范圍與構(gòu)建，并將該通告節(jié)點(diǎn)設(shè)定為集群的核心節(jié)點(diǎn)，將scope減1，同時(shí)將該節(jié)點(diǎn)通告出去。否則，丟棄該通告報(bào)文。

步驟5 將集群范圍內(nèi)的具備最大ηi的節(jié)點(diǎn)設(shè)定為集群核心節(jié)點(diǎn)，它在集群內(nèi)發(fā)送確認(rèn)消息，完成集群的構(gòu)建。

步驟6 當(dāng)緩存節(jié)點(diǎn)的所有內(nèi)容達(dá)到一定程度或經(jīng)過時(shí)間間隔T后，重新進(jìn)行內(nèi)容通告。

4.3 引導(dǎo)式鄰近緩存通告

4.3.1 通告報(bào)文設(shè)計(jì)

為了實(shí)現(xiàn)鄰近緩存的內(nèi)容通告，在網(wǎng)絡(luò)中設(shè)計(jì)引導(dǎo)式緩存通告報(bào)文如圖4所示。

圖4 引導(dǎo)式緩存通告報(bào)文格式

其中，type字段用來表示報(bào)文的類型，cluster字段記錄當(dāng)前節(jié)點(diǎn)所在集群的編號(hào)。timestamp字段用來記錄報(bào)文的發(fā)送時(shí)間，判別通告內(nèi)容的最新版本。hop字段用來記錄內(nèi)容通告節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的跳數(shù)，作為通告的路由代價(jià)，用于便捷路由計(jì)算的依據(jù)。URL與scope分別為需要通告的內(nèi)容名字（NDN中的命名機(jī)制采用URL形式）和通告范圍（跳數(shù)）。每通告1跳，hop字段加1，scope字段減1，直到為0。鄰居節(jié)點(diǎn)根據(jù)scope字段是否為0來決定是否繼續(xù)通告，如果為scope字段為0，則不再進(jìn)行內(nèi)容通告。

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

為了避免緩存內(nèi)頻繁的內(nèi)容更替造成通告消息膨脹，通告內(nèi)容只選擇緩存中相對(duì)穩(wěn)定的 （也就是熱度值較高的）部分內(nèi)容進(jìn)行通告。首先節(jié)點(diǎn)緩存按照所采用的緩存策略對(duì)內(nèi)容進(jìn)行排序，選擇熱度較高的前x%個(gè)副本條目進(jìn)行通告。如節(jié)點(diǎn)內(nèi)采用LRU（least recently used）策略，則把新近壓入緩存隊(duì)列的x%通告鄰居節(jié)點(diǎn)，如圖5所示。

圖5 節(jié)點(diǎn)緩存的熱度列表

過度頻繁的更新可能會(huì)造成路由時(shí)內(nèi)容條目缺失，如果當(dāng)前通告的副本條目中有任意一個(gè)被節(jié)點(diǎn)刪除，則觸發(fā)新一次的緩存通告，將當(dāng)前時(shí)刻排序在前x%的節(jié)點(diǎn)緩存信息發(fā)送給興趣集群內(nèi)所有節(jié)點(diǎn)。

4.3.3 引導(dǎo)式鄰近緩存通告算法

完成節(jié)點(diǎn)集群建立后，節(jié)點(diǎn)都已劃分在各個(gè)集群中。便捷路由構(gòu)建可以分為兩個(gè)階段:引導(dǎo)式緩存通告構(gòu)建階段與內(nèi)容傳遞階段。便捷路由構(gòu)建階段主要進(jìn)行內(nèi)容的通告和便捷內(nèi)容路由表（fast content table，F(xiàn)CT）的建立。首先，集群中的緩存節(jié)點(diǎn)進(jìn)行通告之前的初始化操作:節(jié)點(diǎn)i設(shè)定自身所屬的集群數(shù)值和通告內(nèi)容時(shí)間戳TSnew以及通告范圍scope，根據(jù)內(nèi)容熱度構(gòu)造緩存內(nèi)容前x%的緩存內(nèi)容條目并向所有接口轉(zhuǎn)發(fā)。設(shè)定鄰居節(jié)點(diǎn)j在接受通告之前的通告結(jié)果為，其中，nameC為路由條目名字，face表示其通告接口。沒有內(nèi)容C的記錄時(shí)，時(shí)間戳TSold=0。當(dāng)節(jié)點(diǎn)j接收到來自節(jié)點(diǎn)i的通告后，執(zhí)行以下步驟。

步驟1 節(jié)點(diǎn)j判斷與節(jié)點(diǎn)i是否屬于相同的集群；如果是，執(zhí)行步驟2，否則丟棄該通告報(bào)文，執(zhí)行步驟5。

步驟2 判斷當(dāng)前收到的內(nèi)容通告報(bào)文是否為最新。若TSnew

步驟3 若TSnew≥TSold，該內(nèi)容通告為最新條目。接收通告報(bào)文，并計(jì)算接收?qǐng)?bào)文的hop值作為路由代價(jià):hopnew←hop0+hop（i，j）。若 hopnew≥hop0，說明路由代價(jià)過高，丟棄報(bào)文，執(zhí)行步驟 5；否則執(zhí)行步驟 4。

步驟4 查詢FCRT，更新URL對(duì)應(yīng)表項(xiàng)信息，將hopnew填入轉(zhuǎn)發(fā)信息表中的路由代價(jià)域，然后根據(jù)scope值的大小決定是否轉(zhuǎn)發(fā)此內(nèi)容通告給下一節(jié)點(diǎn)。

步驟5 通告結(jié)束。

便捷路由表構(gòu)建完成后，節(jié)點(diǎn)收到內(nèi)容請(qǐng)求即興趣分組后，對(duì)比當(dāng)前便捷路由代價(jià)與轉(zhuǎn)發(fā)信息表中的服務(wù)器路徑代價(jià)，若便捷路由代價(jià)較小則在便捷路由表中處理該條目并創(chuàng)建轉(zhuǎn)發(fā)信息表，即按照內(nèi)容緩存表、便捷路由表和轉(zhuǎn)發(fā)信息表的順序查表，執(zhí)行相應(yīng)的轉(zhuǎn)發(fā)操作。興趣分組在節(jié)點(diǎn)內(nèi)的轉(zhuǎn)發(fā)過程如圖6所示。

圖6 節(jié)點(diǎn)內(nèi)興趣分組轉(zhuǎn)發(fā)過程

4.4 便捷內(nèi)容路由算法

節(jié)點(diǎn)j在收到鄰居i關(guān)于內(nèi)容C的通告后，記錄內(nèi)容名字、到達(dá)接口和到達(dá)此緩存內(nèi)容的代價(jià)，按如下步驟執(zhí)行便捷內(nèi)容路由算法。

步驟1 對(duì)比當(dāng)前便捷路由的hop與轉(zhuǎn)發(fā)信息表中到內(nèi)容源服務(wù)器的代價(jià)，若便捷路由hop較小，則在便捷路由表中創(chuàng)建該條目；否則刪除該路由內(nèi)容條目對(duì)應(yīng)的便捷路由。

步驟2 同一個(gè)內(nèi)容存在多個(gè)便捷路由轉(zhuǎn)發(fā)接口時(shí)，優(yōu)先選擇最小代價(jià)的接口作為下一跳。

由上述算法創(chuàng)建的便捷路由表格式見表1。

表1 便捷內(nèi)容路由表

5 仿真實(shí)驗(yàn)與結(jié)果

5.1 實(shí)驗(yàn)設(shè)置

采用C++及MATLAB語(yǔ)言模擬NDN運(yùn)行過程拓?fù)鋱D并進(jìn)行相關(guān)性能仿真。實(shí)驗(yàn)環(huán)境為4 GHz英特爾酷睿2雙核處理器Windows 7操作系統(tǒng)的PC。根據(jù)命名數(shù)據(jù)網(wǎng)絡(luò)特點(diǎn)構(gòu)建路由節(jié)點(diǎn)，由GT-ITM拓?fù)渖晒ぞ呱梢粋€(gè)路由節(jié)點(diǎn)數(shù)為30的平面隨機(jī)網(wǎng)絡(luò)拓?fù)?，其中任意兩個(gè)路由節(jié)點(diǎn)之間存在直接相連接路徑的概率為0.3。從邊緣節(jié)點(diǎn)中隨機(jī)選取1個(gè)節(jié)點(diǎn)作為服務(wù)器節(jié)點(diǎn)為整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)提供內(nèi)容的發(fā)布與服務(wù)，其容量足夠存儲(chǔ)所有內(nèi)容對(duì)象。剩下的節(jié)點(diǎn)作為普通的內(nèi)容路由節(jié)點(diǎn)與用戶直接相連，緩存容量為B（假定內(nèi)容對(duì)象大小相同，則B表示節(jié)點(diǎn)可以緩存的內(nèi)容個(gè)數(shù)）。為了便于分析，相鄰節(jié)點(diǎn)之間的時(shí)延設(shè)為10 ms。

為方便測(cè)量，設(shè)定內(nèi)容源服務(wù)器中內(nèi)容對(duì)象數(shù)量N=2000個(gè)，假定URL路由條目大小相等[13]，設(shè)為 128 KB。內(nèi)容對(duì)象的流行度服從Zipf-Mandelbrot分布，即第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ù)。內(nèi)容路由節(jié)點(diǎn)與用戶主機(jī)直接相連，由用戶發(fā)送興趣分組（數(shù)據(jù)請(qǐng)求分組）至相關(guān)聯(lián)的內(nèi)容節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)。在模擬用戶發(fā)送數(shù)據(jù)分組時(shí)使其滿足泊松到達(dá)特性[20]（λ=4個(gè)/s），并且在各個(gè)路由節(jié)點(diǎn)隨機(jī)到達(dá)。仿真拓?fù)淙鐖D7所示，圓點(diǎn)表示路由器，線段表示鏈路，鏈路帶寬為100 Mbit/s。

圖7 仿真拓?fù)?/p>

為了有效地評(píng)估實(shí)驗(yàn)效果，在對(duì)便捷路由機(jī)制進(jìn)行仿真的同時(shí)，對(duì)前人提出的幾種方法進(jìn)行仿真對(duì)比。首先是基本的NDN內(nèi)容路由機(jī)制，不考慮節(jié)點(diǎn)鄰近緩存，直接將請(qǐng)求分組轉(zhuǎn)發(fā)到內(nèi)容源服務(wù)器獲取內(nèi)容[6]，記為SCR（simple content routing）。其次為參考文獻(xiàn)[7]提出的鄰居緩存探測(cè)（NCE）策略。參考文獻(xiàn)[14]提出的通告緩存副本的路由方式，記為ACC。這3種方法中鄰近緩存節(jié)點(diǎn)內(nèi)容缺失時(shí)，直接將請(qǐng)求分組轉(zhuǎn)發(fā)給內(nèi)容源。最后，對(duì)本文提出的基于節(jié)點(diǎn)興趣集群的引導(dǎo)式便捷路由機(jī)制FCR進(jìn)行仿真比較。

為了對(duì)引導(dǎo)式鄰近便捷路由機(jī)制的性能進(jìn)行驗(yàn)證，以用戶請(qǐng)求平均時(shí)延和內(nèi)容源服務(wù)器負(fù)載為性能指標(biāo)進(jìn)行對(duì)比。源服務(wù)器負(fù)載定義為仿真期間源服務(wù)器收到的請(qǐng)求分組個(gè)數(shù)。

5.2 最佳興趣集群的構(gòu)建

為了確定最佳的興趣集群范圍，指導(dǎo)緩存信息通告范圍scope，針對(duì)上述網(wǎng)絡(luò)拓?fù)?，分別對(duì)不同范圍的興趣集群進(jìn)行仿真。結(jié)果如圖8所示，分別給出了scope不同值時(shí)的興趣集群構(gòu)建示意。實(shí)驗(yàn)表明，scope值越小，興趣集群數(shù)量越多，集群內(nèi)的成員越少。

5.3 最佳興趣集群范圍

圖9給出了在上述興趣集群構(gòu)建圖中不同通告范圍對(duì)平均時(shí)延和通告代價(jià)的影響。結(jié)合上述對(duì)通告內(nèi)容比例的仿真，取通告內(nèi)容比例為60%。隨著集群范圍的增大，便捷路由的時(shí)延逐漸減小。引導(dǎo)式通告報(bào)文數(shù)量亦隨集群范圍的增大而增大。從圖中發(fā)現(xiàn)，當(dāng)興趣集群范圍超過6跳時(shí)，時(shí)延發(fā)生了回轉(zhuǎn)現(xiàn)象，主要是因?yàn)橥ǜ娣秶^大，逐漸接近內(nèi)容源路由路徑長(zhǎng)度，導(dǎo)致路徑時(shí)延開始回升。綜合考慮對(duì)性能與代價(jià)的影響，最佳集群范圍為5跳。

5.4 內(nèi)容緩存通告比例

取緩存容量B=60，總的請(qǐng)求數(shù)Nq=2000個(gè)。以內(nèi)容通告比例x%為變量對(duì)捷徑路由時(shí)延性能進(jìn)行仿真，結(jié)果如圖10所示。隨著通告比例的增加，時(shí)延性能逐漸改善，然而當(dāng)通告比例超過80%后，平均時(shí)延反而有所增加，這是因?yàn)榫彺嬷械膬?nèi)容存在動(dòng)態(tài)性，將部分頻繁更替的內(nèi)容通告出去，導(dǎo)致節(jié)點(diǎn)將請(qǐng)求轉(zhuǎn)發(fā)到這些內(nèi)容已經(jīng)被刪除的節(jié)點(diǎn)，造成緩存缺失，重新從其他節(jié)點(diǎn)獲取內(nèi)容使得時(shí)延增加。另外，隨著通告范圍的擴(kuò)大，這種時(shí)延增加的現(xiàn)象愈加明顯。

圖8 不同范圍節(jié)點(diǎn)興趣集群的構(gòu)建

圖9 興趣集群范圍對(duì)時(shí)延與通告報(bào)文數(shù)的影響

圖10 緩存內(nèi)容通告比例對(duì)性能影響

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

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

仿真過程中共產(chǎn)生2000個(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é)果如圖11所示。

由圖11可以看出，基本的NDN內(nèi)容路由方式，不考慮節(jié)點(diǎn)上內(nèi)容副本的路由，時(shí)延最大。NCE和ACC方法都建立了到達(dá)鄰居節(jié)點(diǎn)副本的路由表，但未考慮鄰居節(jié)點(diǎn)上內(nèi)容的熱度差異和命中概率，內(nèi)容缺失情況較為突出，需要從其他資源處重新獲取，導(dǎo)致請(qǐng)求時(shí)延增加。相比之下，捷徑路由考慮了緩存節(jié)點(diǎn)內(nèi)容的更新刪除，一旦通告的緩存內(nèi)容被替換，則進(jìn)行通告更新，提高了請(qǐng)求的命中概率，其請(qǐng)求的平均時(shí)延最小。

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

取緩存容量B=60個(gè)，內(nèi)容請(qǐng)求數(shù)Nq=2000個(gè)。以內(nèi)容服務(wù)器收到的興趣分組的個(gè)數(shù)作為其性能指標(biāo)，則服務(wù)器負(fù)載性能的仿真結(jié)果如圖12所示。

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

由圖12可見，在總的內(nèi)容請(qǐng)求數(shù)為2000的情況下，原始的NDN路由方式只將請(qǐng)求路由到確定的服務(wù)器，因而不會(huì)產(chǎn)生額外的請(qǐng)求分組，ACE和NCE都存在內(nèi)容缺失導(dǎo)致重新請(qǐng)求的現(xiàn)象，會(huì)產(chǎn)生額外的請(qǐng)求分組。FCR會(huì)將通告內(nèi)容的更新及時(shí)發(fā)布給興趣集群內(nèi)的鄰居節(jié)點(diǎn)，所以不存在重路由現(xiàn)象。在服務(wù)器收到的請(qǐng)求分組數(shù)量上，SCR最多，因?yàn)槠渲荒芾棉D(zhuǎn)發(fā)路徑上的部分緩存的內(nèi)容，而ACE、NCE和捷徑路由利用了緩存節(jié)點(diǎn)的內(nèi)容資源，有效地減少了內(nèi)容服務(wù)器的負(fù)載。便捷路由相對(duì)于SCR，在服務(wù)器負(fù)載上減少了約30%。

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

命名數(shù)據(jù)網(wǎng)絡(luò)中直接面向內(nèi)容源服務(wù)器的路由方式提高了返回?cái)?shù)據(jù)分組的效率，但不在發(fā)送路徑上的鄰近緩存內(nèi)容無法充分利用。為解決此問題，提出基于興趣集群的面向鄰近緩存的引導(dǎo)式便捷路由機(jī)制FCR。依據(jù)互聯(lián)網(wǎng)小世界特性，針對(duì)小區(qū)域內(nèi)鄰近節(jié)點(diǎn)興趣相似度不同，設(shè)計(jì)引導(dǎo)式的緩存內(nèi)容通告機(jī)制，最后設(shè)計(jì)獨(dú)特的通告報(bào)文結(jié)構(gòu)和合理的通告范圍實(shí)現(xiàn)便捷路由機(jī)制。理論分析與實(shí)驗(yàn)結(jié)果表明，該方法減少了用戶請(qǐng)求的平均時(shí)延，有效地降低了內(nèi)容源服務(wù)器的負(fù)載。由于內(nèi)容節(jié)點(diǎn)的頻繁更新，這種便捷路由機(jī)制可能導(dǎo)致節(jié)點(diǎn)路由表項(xiàng)的膨脹，如何聚合壓縮路由表中轉(zhuǎn)發(fā)信息條目是下一步研究和探索的重點(diǎn)。

1 Muscariello L,Carofiglio G,Gallo M.Bandwidth and storage sharing performance in information centric networking.Proceedings of ACM SIGCOMM ICN Workshop,Toronto,ON,Canada,2011:26～31

2 Tsilopoulos C,Xylomenos G.Supporting diverse traffic types in information centric networks.Proceedings of ACM SIGCOMM ICN Workshop,Toronto,ON,Canada,2011:13～18

3 Zhang L X,Estrin D,Burke J,et al.Named data networking(NDN)project.http://named-data.net/techreports.html,2013

4 Shanbhag S,Schwan N,Rimac I,et al.SoCCeR:services over content-centric routing. Proceedings of ACM SIGCOMM Workshop on Information-Centric Networking,Toronto,Canada,2011:62～67

5 Chiocchetti R,Rossi D,Carofiglio G,et al.Exploit the known or explore the unknown?Hamlet-like doubts in ICN.Proceedings of ACM SIGCOMM ICN Workshop,Helsinki,Finland,2012:7～12

6 Eum S,Nakauchi K,Murata M,et al.CATT:potential based routing with content caching for ICN.Proceedings of ACM SIGCOMM Workshop on Information-Centric Networking,Helsinki,Finland,2012:49～54

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

8 Wang Y,Lee K,Venkataraman B,et al.Advertising cached contents in the control plane: necessity and feasibility.Proceedings of IEEE INFOCOM,NOMEN Workshop,Orlando,Florida,USA,2012:286～291

9 Sripanidkulchai K,Maggs B,Zhang H.Efficient content location using interest-based locality in peer-to-peer systems.Proceedings of IEEE INFOCOM,San Franciso,CA,USA,April 2003

10 Pireddo L,Nascimento M A.Taxonomy-based routing indices for peer-to-peer networks.Proceedings of the SIGIR Workshop on Peer-to-Peer Information Retrieval,the 27th Annual International ACM SIGIR Conference,Sheffield,UK,July 2004

11 Mcpherson M,Lovin L,Cook J.Birds of a feather:homophily in social networks.Annual Review of Sociology,2001,27(1):415～444

12 Zhang Y,Zhao J,Cao G H,et al.On interest locality in content-based routing for large-scale MANETs.Proceedings of IEEE 6th International Conference on Mobile Ad Hoc and Sensor Systems(MASS'09),Macao,China,2009

13 Berners-Lee T,Fielding R T,Masinter L.Uniform Resource Identifier(URI):Generic Syntax.RFC3986,2005