張康寧，張珊，羅洪斌

北京航空航天大學(xué)，北京 100191

引 言

信息中心網(wǎng)絡(luò)（Information-Centric Networking，ICN）[1-2]采用以信息為中心的通信方式替代現(xiàn)有的以端為中心的通信方式，能較好地滿足人們對以信息為中心的通訊方式的需求，具有高效性、高安全性并支持客戶端移動等特點。ICN 摒棄了傳統(tǒng)的以IP 為細(xì)腰的協(xié)議棧結(jié)構(gòu)，改為采用以信息名稱為核心的網(wǎng)絡(luò)協(xié)議棧，把信息名稱作為網(wǎng)絡(luò)傳輸?shù)臉?biāo)識。

ICN 的內(nèi)容名字通告策略主要是由其路由系統(tǒng)類型決定的，對于如CCN（Content-Centric Networking）[3]、NDN（Named Data Networking）[4]、TRIAD（Translating Relaying Internet Architecture integrating active Directories）[5]等采用無層次路由結(jié)構(gòu)的ICN 架構(gòu)，其名字通告通常采用基于洪范的方式，如下圖1（a）所示，其中名字通告從A 節(jié)點不斷向其他節(jié)點泛洪傳播；而對于DONA（Data-Oriented Network Architecture）[6]等采用樹形層次路由結(jié)構(gòu)的ICN 架構(gòu)，其名字通告通常是沿其樹形結(jié)構(gòu)逐級傳播，如圖1（b）所示，其中底層RH 節(jié)點的名字通告是沿樹形結(jié)構(gòu)向上級傳遞的。

ICN 的數(shù)據(jù)轉(zhuǎn)發(fā)策略和傳統(tǒng)TCP/IP 網(wǎng)絡(luò)有所不同，ICN 的每個路由器都需要維護三個數(shù)據(jù)結(jié)構(gòu)：待定請求表（Pending Interest Table，PIT）、前向轉(zhuǎn)發(fā)表（Forwarding Information Base，F(xiàn)IB）和內(nèi)容存儲器（Content Store，CS）。其中PIT 負(fù)責(zé)對每個通過本路由器的請求包進(jìn)行記錄，并在內(nèi)容包傳回時找到對應(yīng)請求包來時的端口進(jìn)行轉(zhuǎn)發(fā)；FIB 負(fù)責(zé)將請求包轉(zhuǎn)發(fā)到目的端所在的端口；CS 則負(fù)責(zé)ICN 中路由器的數(shù)據(jù)緩存。

基于上述3 種數(shù)據(jù)結(jié)構(gòu)，ICN 中的請求數(shù)據(jù)包轉(zhuǎn)發(fā)主要分為兩個步驟：（1）如果接收到請求包，則先在CS 中匹配內(nèi)容緩存，如果有則直接返回相關(guān)內(nèi)容，沒有則進(jìn)一步查詢PIT；（2）如果PIT 中能找到相應(yīng)的記錄，則將請求包來時端口添加到該記錄中，如果PIT 中沒有相應(yīng)記錄，則查詢FIB 并將該請求包轉(zhuǎn)發(fā)至目標(biāo)端口，同時將其記錄在PIT 中。而ICN 中的內(nèi)容數(shù)據(jù)包轉(zhuǎn)發(fā)則是查詢路由器的PIT，如果沒有匹配記錄則丟棄該包，如果有則根據(jù)匹配記錄將其轉(zhuǎn)發(fā)到一個或多個請求端口處，同時根據(jù)策略進(jìn)行數(shù)據(jù)緩存并刪除該PIT 記錄。

這里以CCN[3]為例說明ICN 的數(shù)據(jù)轉(zhuǎn)發(fā)流程，如圖2所示，其中A、B、C、D、E 均為路由節(jié)點，C1、C2 為請求內(nèi)容端，S 為服務(wù)提供端。在剛開始的時候S 通過基于洪泛的通告方式向網(wǎng)絡(luò)所有節(jié)點通過其提供的服務(wù)，路由節(jié)點A-E 收到泛洪信息后計算并建立到S 的FIB 路由表。當(dāng)C1、C2 先后向S 請求同一個服務(wù)時：（1）C1 向S 發(fā)出一個請求包，該請求包通過C 節(jié)點時首先查詢CS 和PIT 無果，然后查詢FIB 表決定下一跳為D 節(jié)點，同時在PIT 表中插入該請求及其源端口記錄，其他路由節(jié)點執(zhí)行相同動作直到請求包成功到達(dá)S；（2）S 收到請求包1 后向C1 發(fā)送一個內(nèi)容包，當(dāng)該內(nèi)容包經(jīng)過C節(jié)點時在節(jié)點的PIT 表匹配到對應(yīng)的請求記錄，在CS 中存儲該內(nèi)容包作為緩存后向?qū)?yīng)請求記錄的源端口轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)后刪除該PIT 記錄，其他路由節(jié)點執(zhí)行相同動作直到內(nèi)容包成功返回C1；（3）C2 向S發(fā)出一個請求包，當(dāng)請求包經(jīng)過C 節(jié)點時首先查詢CS 并發(fā)現(xiàn)成功匹配，然后C 節(jié)點直接從CS 中取出并發(fā)送之前緩存的內(nèi)容包給C2。

圖1 ICN 中不同路由結(jié)構(gòu)下的名字通告策略示意圖Fig.1 Schematic diagram of name advertisement strategy under different routing structures in ICN

圖2 ICN 中數(shù)據(jù)轉(zhuǎn)發(fā)示意圖Fig.2 Data forwarding diagram in ICN

從上面描述可以看出：在信息中心網(wǎng)絡(luò)中，用戶每次發(fā)送一個請求，只能返回該請求對應(yīng)的內(nèi)容（塊），而不一定是一個完整的文件。對一個較大的文件而言，需要分成多個內(nèi)容塊，每個內(nèi)容塊都有一個獨立的名字和相應(yīng)的大小。我們定義命名粒度即對網(wǎng)絡(luò)中發(fā)布內(nèi)容進(jìn)行命名的單個塊的大小上限，即如果一個發(fā)布內(nèi)容大于這個值則會據(jù)此先對其進(jìn)行切分再命名。顯然，命名粒度越小，一個大文件就可能被分成更多的內(nèi)容塊，也就會產(chǎn)生更多的內(nèi)容名字。例如，一個80KB 的文件，當(dāng)內(nèi)容命名粒度為4KB 時，被分成20 個內(nèi)容塊，對應(yīng)20 個內(nèi)容名字；而當(dāng)命名粒度為32KB 時，則被分成3 個內(nèi)容塊（如大小分別為：32 KB、32KB、16KB），只需3 個內(nèi)容名字；若命名粒度為100KB，則該文件不用分塊，只用一個名字即可。因此，內(nèi)容命名粒度對內(nèi)容名字的數(shù)量有重要影響，這個影響在ICN 的總體轉(zhuǎn)發(fā)效率中占據(jù)了非常重要的地位。因為ICN 是以名字來作為轉(zhuǎn)發(fā)標(biāo)識的，相應(yīng)的網(wǎng)絡(luò)中名字的數(shù)量規(guī)模很大程度上決定了網(wǎng)絡(luò)中路由器的條目規(guī)模，以及路由器之間進(jìn)行名字路由通告等的通信開銷，故而命名粒度對路由器的查表轉(zhuǎn)發(fā)效率會造成非常巨大的影響；同時，由于一個請求僅包含一個內(nèi)容名字（也就是說只請求一個內(nèi)容塊），因而有多少個內(nèi)容名字，就需要多少個內(nèi)容請求，相應(yīng)的命名粒度會影響網(wǎng)絡(luò)中用戶需要發(fā)送的請求數(shù)量，進(jìn)而影響ICN 的總體轉(zhuǎn)發(fā)效率。然而目前針對命名粒度對ICN 效率的研究還主要集中在命名粒度對緩存機制影響上，本文則嘗試從命名粒度對ICN 轉(zhuǎn)發(fā)效率的影響進(jìn)行探究。

因此，本文旨在回答以下四個問題：

（1）命名粒度如何影響名字?jǐn)?shù)量：通過計算分析知道隨著命名粒度呈倍數(shù)上升，在粒度較小時名字?jǐn)?shù)量呈倍數(shù)下降，在粒度較大時名字?jǐn)?shù)量下降趨勢減緩并最終趨于文件數(shù)量；

（2）命名粒度如何影響請求數(shù)量：由分析可知請求數(shù)量隨命名粒度變化的趨勢和名字?jǐn)?shù)量隨命名粒度變化的趨勢是一致的；

（3）命名粒度如何影響路由表規(guī)模：對于層次化命名，其路由表規(guī)模僅和文件數(shù)量和聚合度相關(guān)；對于扁平化命名，其路由表規(guī)模的變化趨勢和由命名粒度變化所導(dǎo)致的名字?jǐn)?shù)量的變化趨勢一致；

（4）命名粒度如何影響查表效率：命名粒度主要通過影響路由表規(guī)模來影響單次查表效率，通過影響單次查表效率和請求數(shù)量來影響綜合查表效率。

本文組織結(jié)構(gòu)如下：第1 節(jié)簡述相關(guān)工作；第2 節(jié)探索命名粒度對名字?jǐn)?shù)量的影響；第3 節(jié)探索命名粒度對請求數(shù)量的影響；第4 節(jié)探索命名粒度對路由表大小的影響；第5 節(jié)探索命名粒度對路由查表效率的影響。

1 相關(guān)工作

目前信息中心網(wǎng)絡(luò)主要有兩種命名方式，一種是以CCN/NDN 為代表的層次化命名方式[3-5]，這種命名給每個內(nèi)容單元賦予了URL 一樣具有語義和可聚合性的名字，有利于網(wǎng)絡(luò)規(guī)模擴展；另一種是以DONA 為代表的扁平化命名方式[6]，這種命名給每個內(nèi)容單元賦予了不可讀且不可聚合的扁平化名字，該名字一般由發(fā)布者公鑰的哈希值和內(nèi)容的哈希值組合而成，具有自驗證和信息隱藏等特點。關(guān)于命名方案，目前主流的信息中心網(wǎng)絡(luò)主要對網(wǎng)絡(luò)中的命名方式作了相關(guān)規(guī)定，但是對命名粒度則只是給一個大概的取值范圍，而沒有闡述這樣取值的原因，也沒有深入探究命名粒度變化可能對網(wǎng)絡(luò)效率造成的影響。

目前關(guān)于命名粒度如何影響信息中心網(wǎng)絡(luò)效率的研究總體還是比較稀缺，且現(xiàn)有研究基本集中在命名粒度如何對網(wǎng)絡(luò)緩存性能造成影響上[7-8]。本文則嘗試采取一種新的研究思路來探究命名粒度對信息中心網(wǎng)絡(luò)性能的影響，從命名粒度與名字?jǐn)?shù)量、請求數(shù)量、路由查表效率這三者的關(guān)系來進(jìn)行探究。

2 命名粒度對名字?jǐn)?shù)量的影響

由于命名粒度通過改變名字規(guī)模來影響路由轉(zhuǎn)發(fā)效率，因此在分析請求次數(shù)、條目規(guī)模和路由轉(zhuǎn)發(fā)效率之間的關(guān)系之前，需要先簡要分析命名粒度和名字規(guī)模之間的變化關(guān)系。令n表示網(wǎng)絡(luò)中的文件數(shù)量，Si表示第i（1≤i≤n）個文件的大小，表示網(wǎng)絡(luò)中所有文件的大小之和，s表示內(nèi)容命名粒度，則網(wǎng)絡(luò)中的名字?jǐn)?shù)量N 可以用式（1）給出：

由于名字?jǐn)?shù)量受到每個文件大小的影響，因此還需要考慮網(wǎng)絡(luò)中文件大小的分布情況，即不同的文件大小在網(wǎng)絡(luò)中所占的比例。參考現(xiàn)有工作中關(guān)于網(wǎng)絡(luò)內(nèi)容分發(fā)狀態(tài)的研究[9-10]以及網(wǎng)絡(luò)仿真實驗的模型與參數(shù)設(shè)置[11-12]，可以認(rèn)為網(wǎng)絡(luò)內(nèi)容的大小分布總體遵循帕累托分布（Pareto distribution），即一種典型的重尾分布。假設(shè)隨機變量X服從帕累托分布，則X的概率分布如下式（2）所示：

其中xmin＞0 是X的最小值，是取值為正的參數(shù)，x表示任意X的取值。

假設(shè)網(wǎng)絡(luò)中有1 000 000 個待分發(fā)文件，其大小分布遵循上述的帕累托分布，取分布模型參數(shù)α=1.1，xmin=(133)KB[12]，由帕累托分布模型隨機生成的隨機文件大小序列的分布情況的互補累積分布函數(shù)（CCDF）如圖3所示，其中橫坐標(biāo)為文件大小，單位為KB，縱坐標(biāo)為當(dāng)前網(wǎng)絡(luò)中隨機取一個文件的大小大于該文件大小的概率值。

由圖3可以看出生成的隨機文件大小序列呈現(xiàn)典型的重尾特征。在根據(jù)帕累托分布生成分布如上圖所示的隨機文件大小序列時，假設(shè)現(xiàn)在的命名粒度為4 KB，則我們根據(jù)（1）式計算可得總名字?jǐn)?shù)量為353 868 223。后面的實驗將采用同樣的計算方法，在不同的條件下根據(jù)帕累托分布生成一定數(shù)量的文件大小序列，然后在不同粒度下進(jìn)行計算并將結(jié)果進(jìn)行匯總分析。為了方便下文分析，這里引入平均名字?jǐn)?shù)量K，該值的計算如公式（3）所示：

式中Ni表示當(dāng)命名粒度為i時網(wǎng)絡(luò)的總名字?jǐn)?shù)量，n表示文件數(shù)量，則Ki表示命名粒度為i時網(wǎng)絡(luò)中每個文件所擁有的平均名字?jǐn)?shù)量。拿上面的例子來說，可用公式（3）計算其K值為353.868。這里引用K值來衡量名字規(guī)模大小，是因為分析名字?jǐn)?shù)量規(guī)模時我們相較于確切的絕對名字?jǐn)?shù)量更關(guān)心名字?jǐn)?shù)量的變化趨勢，因此相對數(shù)量K是一個比較好的選擇。

下面將利用根據(jù)帕累托分布生成的隨機文件大小序列來探究命名粒度和名字規(guī)模之間的關(guān)系，為了能更全面地評估命名粒度對名字?jǐn)?shù)量的影響，文本假設(shè)命名粒度取[2, 4, 8, 16, 32, 64, 128, 256, 512,1024, 2048, 4096, 8192]，單位為KB，并采用（1）式計算名字?jǐn)?shù)量。下面設(shè)置了三組不同條件的對照實驗，每組實驗將控制不同的變量來討論不同網(wǎng)絡(luò)變化情況下命名粒度和名字規(guī)模間的數(shù)量變化趨勢，每組實驗將測試三次并取均值：

圖3 關(guān)于文件大小的CCDF 圖Fig.3 CCDF of file size

圖4 情況一下不同帕累托分布參數(shù)下的K 值Fig.4 K value under different Pareto distribution parameters in case 1

（1）保持文件數(shù)量n和文件內(nèi)容總大小S不變，采用不同的α和xmin值。它表示維持網(wǎng)絡(luò)總體量不變，但是通過改變帕累托參數(shù)來改變文件大小分布情況。這里設(shè)置文件數(shù)量n為1 000 000，參數(shù)α分別設(shè)置為1， 2， 3，通過計算參數(shù)的取值來維持文件內(nèi)容總大小S不變。得到的K值如圖4所示，其中橫坐標(biāo)為命名粒度，縱坐標(biāo)為該粒度下的K值，縱坐標(biāo)采用以10 為底的對數(shù)刻度。

由圖4可以清晰地看到，在命名粒度呈倍數(shù)增加的時候網(wǎng)絡(luò)中的K值會明顯下降，這和前文的理論分析結(jié)論是吻合的。且通過對比實驗結(jié)果，可以得知不同α值下K值的曲線是重合的，這說明在控制文件數(shù)量及內(nèi)容總大小不變的情況下，不同α取值情況下的K值基本相同，變化趨勢也是基本一致的，以此可以看出文件大小分布情況對K值基本沒有影響。分析K值變化趨勢可以發(fā)現(xiàn)在命名粒度呈二的冪次增長時，在粒度較小時K值也是成冪次下降的，但是在命名粒度增長到比較大的時候K值的下降趨勢減少并趨于不變，這是因為當(dāng)命名粒度較大時比該粒度小的文件本來就不能被進(jìn)一步分片，因此粒度再變大也不會顯著讓K值減??；而當(dāng)命名粒度增長至大于當(dāng)前所有文件時，即使命名粒度再變大文件也不會產(chǎn)生新的分片，故此時K值會等于文件數(shù)量而不再下降。

（2）控制參數(shù)α和參數(shù)xmin相同，采用不同的文件數(shù)量n和文件內(nèi)容總大小S。它表示維持文件大小分布情況不變，通過增減文件數(shù)量來擴大或收縮網(wǎng)絡(luò)總體量。這里參數(shù)α設(shè)置為1，xmin設(shè)置為133，文件數(shù)量n分別設(shè)為1 000 000,10 000 000,50 000 000。其中由于沒有進(jìn)行文件內(nèi)容總大小控制，因此會有一定的隨機性，故這里每組試驗均進(jìn)行三次實驗并取平均值。得到的K值如圖5所示，其中橫坐標(biāo)為命名粒度，縱坐標(biāo)為該粒度下的K值，縱坐標(biāo)采用以10 為底的對數(shù)刻度。

如圖5所示，同樣可以發(fā)現(xiàn)在命名粒度呈倍數(shù)增加的時候網(wǎng)絡(luò)中的K值會成倍數(shù)的下降，其變化趨勢與前述情況（1）基本一致。且對比實驗結(jié)果可以得知不同文件數(shù)量下K值的曲線是基本重合的，這說明在控制拓?fù)渖蓞?shù)α值和xmin值不變的情況下，不同文件數(shù)量規(guī)模下的K值基本相同，變化趨勢也是基本一致的，由此可以看出文件數(shù)量規(guī)模雖然會影響總名字?jǐn)?shù)量的大小，但對相對數(shù)量K的取值基本沒有影響。

（3）控制文件內(nèi)容總大小S和參數(shù)α相同，采用不同的文件數(shù)量n和xmin值。它表示維持網(wǎng)絡(luò)總體量不變，文件大小分布基本不變，但是通過參數(shù)xmin來改變文件的平均大小。這里參數(shù)α設(shè)置為1，文件數(shù)量分別設(shè)為1 000 000,10 000 000,50 000 000，通過計算參數(shù)xmin的取值來維持文件內(nèi)容總大小S不變。得到的K值示意圖如圖6所示，其中橫坐標(biāo)為命名粒度，縱坐標(biāo)為該粒度下的K值，縱坐標(biāo)采用以10為底的對數(shù)刻度。

如圖6所示，同樣可以發(fā)現(xiàn)在命名粒度呈倍數(shù)增加時網(wǎng)絡(luò)中的K值會成倍數(shù)的下降。但是和前述情況（2）不同的是，控制文件總內(nèi)容大小與α不變的情況下，不同的文件數(shù)量取到的K值有較大差異，且文件數(shù)量越多則K值越小。這是因為在網(wǎng)絡(luò)總大小不變時，文件數(shù)量越多意味著每個文件平均分到的內(nèi)容就越小，因此每個文件平均擁有的名字?jǐn)?shù)量（即K值）也越少。

由圖6同時可以看出不同文件數(shù)量下K值隨命名粒度變化的趨勢和前述情況（1）（2）基本一致，不過隨著文件數(shù)量變大，變化趨勢曲線整體向左平移。這是因為當(dāng)文件數(shù)量變大時文件平均大小變小，這會導(dǎo)致文件在前期粒度不大時就已經(jīng)不能被進(jìn)一步切分，從而使K值變化提前達(dá)到變化趨勢后期的變化平緩期。

綜合上述三種情況的實驗結(jié)果，可以得出兩個主要結(jié)論：（1）隨著命名粒度呈倍數(shù)增加，在粒度較小時K值會呈相應(yīng)倍數(shù)減少，而在命名粒度較大時則減速放緩并使K值最終趨于1，且在不同網(wǎng)絡(luò)場景下這個K值變化的趨勢都是成立的；（2）文件大小分布情況和總體網(wǎng)絡(luò)規(guī)模對K值的影響都是非常小的，真正能顯著影響K值的其實還是平均文件大小，這里可以粗略表述為總內(nèi)容大小與文件數(shù)量的比值。

圖5 情況二中不同文件數(shù)量時的K 值Fig.5 K value for different scales of files in case 2

圖6 情況三中不同文件數(shù)量時的K 值Fig.6 K value for different scales of files in case 3

3 命名粒度對請求數(shù)量的影響

如前所述，因為當(dāng)接收方請求某個文件時，如果該文件在命名時被分割為若干部分，那接收方至少需要請求的數(shù)量等于該文件所擁有的名字?jǐn)?shù)量。因為前述K 值的定義為網(wǎng)絡(luò)中每個文件平均所擁有的名字?jǐn)?shù)量，因此在這里可以將K 值看作是網(wǎng)絡(luò)中獲取一個文件平均需要的請求次數(shù)。那么依據(jù)第二部分的實驗結(jié)論，這里同樣可以得出兩個結(jié)論，一是隨著命名粒度呈倍數(shù)上升，網(wǎng)絡(luò)中平均請求數(shù)量呈倍數(shù)下降，且在粒度較大時下降幅度減緩，直至最后等于文件數(shù)量；二是文件分布情況和總體網(wǎng)絡(luò)規(guī)模對網(wǎng)絡(luò)平均請求次數(shù)的影響不大，網(wǎng)絡(luò)平均文件大小才是影響平均請求次數(shù)的主要因素。

4 命名粒度對路由表規(guī)模大小的影響

接下來分析命名粒度變化對路由表規(guī)模大小變化的影響，由于這個影響很大程度上被命名方式所左右，因此我們將分別對層次化命名方式和扁平化命名方式進(jìn)行討論。

4.1 層次化命名方式

層次化命名對命名空間內(nèi)部各個部分賦予了語義也添加了相應(yīng)的可選約束，這種方式雖然可能會暴露一定的信息，但是可以利用語義與約束來進(jìn)行名字聚合——對于層次化命名方式而言，由于層次化的名字空間中的很多名字都共享相同的前綴，故路由器可以利用該特點對大量路由條目進(jìn)行名字聚合，這樣會導(dǎo)致該命名方式下的路由表具有兩個特點：

（1）路由表中的條目數(shù)量遠(yuǎn)遠(yuǎn)小于其所覆蓋的名字空間的名字?jǐn)?shù)量，例如AS65000 的路由條目報告[13]所稱的目前核心路由表項數(shù)量是827009，其覆蓋的總名字空間大小為2853207852，計算名字聚合的優(yōu)化比例為：

該結(jié)果足以說明層次化命名下名字聚合的效率是非常高的。

（2）路由表可以屏蔽由于命名粒度變化導(dǎo)致的名字?jǐn)?shù)量變化對核心路由表規(guī)模的影響，比如對于某視頻切片可能擁有名字為buaa.edu.cn/video/20200326/s1，而其對應(yīng)的路由表項可能為buaa.edu.cn/video/20200326，現(xiàn)在由于命名粒度變化導(dǎo)致該切片被繼續(xù)分割為16 個小塊進(jìn)行命名，其名字變?yōu)閎uaa.edu.cn/video/20200326/s1/a1～buaa.edu.cn/video/20200326/s1/a16，名字?jǐn)?shù)量變?yōu)樵瓉?6 倍，但是為其轉(zhuǎn)發(fā)的路由表則可以維持buaa.edu.cn/video/20200326 一個表項不變。

以上例子說明在層次化的命名方式下，命名粒度變化所導(dǎo)致的名字?jǐn)?shù)量的變化對路由表項規(guī)模的影響是非常小的，特別是在我們比較關(guān)注的、名字聚合度非常高的核心網(wǎng)中，這種影響完全是可以忽略的。因此，后面的分析將以網(wǎng)絡(luò)總文件數(shù)量n作為其路由表最大條目數(shù)量，在此基礎(chǔ)上引入聚合度λ，然后將二者的乘積λn作為聚合后的條目數(shù)量，這里λ可以取0.1、0.01、0.001 等。

4.2 扁平化命名方式

扁平化命名主要指命名空間內(nèi)部各個部分的取值是沒有語義和相互約束的，這意味著很難利用語義進(jìn)行名字聚合，同時也因為語義的缺失而提高了安全性。由于扁平化命名方式缺乏層次化命名方式的名字聚合手段，因此在該命名方式下，路由表中的條目數(shù)量等于其所覆蓋的名字空間的名字?jǐn)?shù)量，而且不能屏蔽命名粒度變化所導(dǎo)致的名字?jǐn)?shù)量的變化對路由表項規(guī)模的影響。因此可以認(rèn)為扁平化命名方式下的條目數(shù)量正比于名字?jǐn)?shù)量，且條目數(shù)量的變化趨勢和由命名粒度變化所導(dǎo)致的名字?jǐn)?shù)量的變化趨勢是一致的。

利用前面第2 節(jié)的分析結(jié)果可以得到名字?jǐn)?shù)量關(guān)于命名粒度的數(shù)量變化趨勢，而且數(shù)據(jù)分析表明這個數(shù)量變化趨勢在不同網(wǎng)絡(luò)條件下都是基本成立的，其曲線僅隨著平均文件大小左右平移。由此就可以利用該數(shù)量變化趨勢得到扁平化命名方式下在不同網(wǎng)絡(luò)環(huán)境都較為可信的條目數(shù)量。

綜上分析，取文件數(shù)量n=1 000 000，分布模型參數(shù)α=1.1，xmin=(133)KB 得到名字?jǐn)?shù)量后再經(jīng)過適當(dāng)放縮，就可以得到扁平化命名方式下的條目數(shù)量，對其文件數(shù)量同樣放縮后乘以不同的聚合度λ 就可以得到層次化命名方式下的條目數(shù)量，最終匯總得到的不同命名方式下條目數(shù)量示意圖到圖7所示，其中橫坐標(biāo)為命名粒度，單位為KB，縱坐標(biāo)為條目數(shù)量，縱坐標(biāo)采用以10 為底的對數(shù)刻度。在扁平化命名方式下，路由表條目數(shù)量比文件數(shù)量多，且總體變化趨勢為隨著命名粒度增大而減少；在層次化命名方式下，路由表條目數(shù)量比文件數(shù)量少，其具體大小取決于聚合度的大小。

圖7 不同命名方式下的條目數(shù)量Fig.7 Number of entries under different naming methods

5 命名粒度對查找效率的影響

綜合上述分析，命名粒度主要是通過改變網(wǎng)絡(luò)中的名字?jǐn)?shù)量來影響文件平均請求數(shù)量以及路由表規(guī)模，進(jìn)而影響路由查表效率的。下面將兩部分討論命名粒度對查找效率的影響，第一部分將探究單次路由查找的效率，第二部分將探究總查找效率。

5.1 單次路由查找效率

要考慮命名粒度對單次路由查表效率的影響，就要考慮路由查表算法在其中的作用。路由查表算法主要指的是路由器用來組織、儲存路由表項并在包轉(zhuǎn)發(fā)時用來進(jìn)行匹配查詢的算法。因為命名粒度變化主要是通過影響路由條目規(guī)模來影響路由查表效率的，而不同的路由查表算法效率和條目規(guī)模之間的效率關(guān)系是不一樣的，這種效率關(guān)系決定了路由算法對條目規(guī)模變化的耐受程度，而且不同命名方式下路由查找算法和條目規(guī)模的效率關(guān)系也可能是不同的，因此是不同命名方式下粒度變化影響路由查表效率的關(guān)鍵因素。

本部分將在扁平化和層次化這兩種命名方式下，分別在不同的條目數(shù)量規(guī)模下測試不同路由查表算法的查表效率，以此來探尋不同命名方式下不同路由查表算法的效率隨表項規(guī)模變化的數(shù)量關(guān)系，進(jìn)而找到不同命名方式下粒度對查表效率的影響。因此，本實驗主要考慮條目數(shù)量、命名方式和路由查表算法這三方面：

（1）條目數(shù)量方面，由前面分析，可以直接利用第四小節(jié)內(nèi)容命名粒度和條目數(shù)量規(guī)模的數(shù)量關(guān)系的探究結(jié)果，即取圖7不同命名方式下的條目規(guī)模作為測試時的條目規(guī)模。

（2）命名方式方面，除了條目數(shù)量上的區(qū)別，實驗中不同的命名方式主要體現(xiàn)在生成測試數(shù)據(jù)集時使用的不同的生成方法，扁平化的命名方式直接每個字節(jié)隨機填入即可，而層次化的命名方式則需要在生成測試數(shù)據(jù)集的時候用多層循環(huán)來嵌套生成測試數(shù)據(jù)，以此用遞進(jìn)的公共前綴來保證命名空間之間的層次約束性，這里需要注意的是在生成多個大小規(guī)模的測試數(shù)據(jù)集時要保證不同層間比例的一致性。

（3）路由查表算法方面，這里擬對在路由查表中較具有代表性的Hash 查表算法、ByteTrie 查表算法[14]和NPT[15]算法進(jìn)行條目規(guī)模與查表效率的測試。Hash 查表算法采用Hash 表的方式存儲和查找路由條目，為了使結(jié)果更具典型性，這里采取了經(jīng)典的拉鏈哈希法；ByteTrie 算法采用多叉樹結(jié)構(gòu)存儲和查找路由條目，其中還對單子樹節(jié)點進(jìn)行了樹結(jié)構(gòu)的壓縮優(yōu)化；NPT 算法則是利用一個多叉四層結(jié)構(gòu)樹來存儲和查找路由條目，層級之間用Hash 方法來進(jìn)行跳轉(zhuǎn)，主要針對層次化命名方式。

測試中生成測試數(shù)據(jù)和測試查表效率的程序均采用C 語言實現(xiàn)，實驗環(huán)境為筆記本電腦，處理器為Intel Core i7-4510U 四核CPU，內(nèi)存為8GB。在實驗時根據(jù)命名方式的不同隨機生成并插入對應(yīng)數(shù)量的路由條目，然后測試不同路由查表算法的查表耗時，其中每組查表次數(shù)為1000 萬次，反復(fù)進(jìn)行3組測試取均值。

測試結(jié)果如圖8和圖9所示。圖8的橫坐標(biāo)是內(nèi)容命名粒度大小，縱坐標(biāo)是查表時間，單位為毫秒，且測試中的層次化命名的聚合度λ 取0.1。由圖8的實驗結(jié)果可以得出不同內(nèi)容命名粒度下不同查表算法的單次查表耗時t，并可以得到結(jié)論及分析如下：

（1）在查表算法效率方面，Hash 算法> Trie 算法> NPT 算法，這是因為Hash 算法因查找時只需進(jìn)行一次哈希運算而非常高效，而Trie 算法由于引入了相對靈活的樹結(jié)構(gòu)壓縮優(yōu)化機制而比嚴(yán)格進(jìn)行四層哈希跳轉(zhuǎn)的NPT 算法更為高效。

（2）同一內(nèi)容命名粒度下，就同一查表算法而言，層次化命名方式下的路由查表效率比扁平化命名方式高，其中Trie 算法下兩種命名方式的效率差別是最大的，NPT 算法的效率差別也很顯著，這不僅因為層次化命名方式可以進(jìn)行路由聚合優(yōu)化縮減表項數(shù)量，還因為該方式下命名空間中各部分取值具有一定的邏輯約束性，因此擁有公共前綴的路由條目的數(shù)量遠(yuǎn)大于完全隨機的扁平化命名方式，故對Trie 算法來說顯著減少了查找空間（即查找深度和平均子分支），大大提高了路由查找效率，而對NPT 算法來說則因為大量存在的公共前綴減少了查找過程在上層哈希碰撞的概率，因此也在一定程度上提高了其路由查表效率。

圖9 層次命名下不同聚合度的查表效率Fig.9 Efficiency of looking up tables with different degrees of aggregation under hierarchical naming

（3）在內(nèi)容命名粒度不斷增大時，扁平化命名方式下所有路由查表算法的效率都在提高，其中以Trie 算法查表效率提高的效果最為明顯，NPT 算法和Hash 算法則幾乎沒有什么變化，這是因為Trie 算法的查找時間復(fù)雜度大概是O（log(n)），因此對內(nèi)容命名粒度改變引起的路由條目規(guī)模變化還是相對敏感的，而Hash 算法和NPT 算法的查表時間復(fù)雜度都是近似于O（1），因此這兩種算法的路由查表效率對路由條目規(guī)模的變化不是很敏感，當(dāng)然由路由條目減少而導(dǎo)致的Hash 碰撞減少還是會使查表效率有非常細(xì)微的提升的。

圖9的橫坐標(biāo)是層次命名方式下的聚合度λ，縱坐標(biāo)是查表時間，單位為毫秒。圖9的實驗結(jié)果可以得出層次化命名下不同聚合度的查表耗時情況，分析可知三種查表算法的效率都隨著聚合度的減小而上升，其中Trie 算法的效率提升是最明顯的，且在聚合度λ 較高時Trie 算法的效率甚至?xí)哂贖ash 算法。

5.2 總查找效率

在得出單次查表效率以后，想要得到綜合查表效率這里還需要考慮接收方想請求一個文件所需要發(fā)送請求包的次數(shù)，因為內(nèi)容命名粒度除了影響單次查表效率以外，還會直接影響請求一個文件所需的平均請求次數(shù)。這里根據(jù)第3 節(jié)的分析結(jié)果，可以將前面引入的K 值作為網(wǎng)絡(luò)中請求一個文件平均需要的請求次數(shù)。因為在不同網(wǎng)絡(luò)環(huán)境下K值的變化趨勢都是一致的，故這里采用圖4的K 值數(shù)據(jù)作為隨命名粒度變化的平均請求次數(shù)。

綜合不同內(nèi)容命名方式、各個內(nèi)容命名粒度下的單次查表耗時和平均請求數(shù)量，可以計算得到綜合查表耗時。計算方法如式（4）所示，其中Ki表示內(nèi)容命名粒度為i時的平均請求數(shù)量，ti表示粒度為i時的單次轉(zhuǎn)發(fā)效率，Ti即為內(nèi)容命名粒度為i時的綜合查表耗時。

綜上所述，利用前述第2 節(jié)關(guān)于K值的計算數(shù)據(jù)和本節(jié)關(guān)于單次查表效率的測試數(shù)據(jù)，再綜合式（4）即可以計算得到綜合查表耗時結(jié)果如圖10 所示，圖中橫坐標(biāo)為內(nèi)容命名粒度，縱坐標(biāo)為綜合查表耗時，單位為毫秒，縱坐標(biāo)采用以10 為底的對數(shù)刻度，層次化命名方式的聚合度λ取0.1。由圖10 可以得到相關(guān)結(jié)論及分析如下所示：

（1）分析算法之間的綜合查表效率同樣可以看出Hash 算法 > Trie 算法 > NPT 算法；

（2）同一內(nèi)容命名粒度下，就同一算法來而言，層次化命名方式的綜合查表耗時同樣小于扁平化命名方式；

圖10 綜合查表耗時結(jié)果Fig.10 Time consuming result of comprehensive table lookup

（3）隨著內(nèi)容命名粒度變大，綜合查表耗時都會變小，即請求一個文件平均所需的查表耗時更小，這是因為如前分析所示隨著粒度變大平均查表耗時和平均請求數(shù)量都在減小，故總體而言效率自然變高，而且變化的幅度比單次查表耗時更明顯；

（4）不同命名方式、不同查表算法間由內(nèi)容命名粒度變化而引起的綜合查表耗時變化的幅度差異不大，這是因為現(xiàn)在平均請求數(shù)量變化遠(yuǎn)大于體現(xiàn)命名方式、查表算法特點的平均查表耗時變化，因此平均請求數(shù)量成為綜合查表耗時變化幅度中的主要影響因素。

6 展望與下一步工作

本文通過逐步推進(jìn)分析探究了信息中心網(wǎng)絡(luò)中不同命名方式下內(nèi)容命名粒度對路由查表效率的影響，先從內(nèi)容命名粒度對名字?jǐn)?shù)量的影響出發(fā)，在找到名字?jǐn)?shù)量關(guān)于命名粒度變化的數(shù)量規(guī)律后再據(jù)此分析網(wǎng)絡(luò)請求數(shù)量和不同命名方式下路由表的條目規(guī)模，最后在分析結(jié)果的基礎(chǔ)之上以實驗來具體測試、分析了不同命名方式下條目數(shù)量規(guī)模和路由查表效率之間的關(guān)系，進(jìn)而揭示了信息中心網(wǎng)絡(luò)中不同命名方式下內(nèi)容命名粒度對路由查表效率的影響。但是，本文的工作主要還是基于理論分析和本地測試，而缺乏實際網(wǎng)絡(luò)測試結(jié)果的支撐。因此，在下一步工作中，將在本文實驗分析的基礎(chǔ)上，利用軟件路由技術(shù)在服務(wù)器集群上搭建信息中心網(wǎng)絡(luò)測試環(huán)境，然后在真實的物理場景下進(jìn)行大規(guī)模的路由轉(zhuǎn)發(fā)測試來得到更可靠、詳細(xì)的實驗數(shù)據(jù)來對本文結(jié)果進(jìn)行進(jìn)一步的物理驗證。

利益沖突聲明

所有作者聲明不存在利益沖突關(guān)系。