基于副本通告的內容中心網絡快捷路由機制

劉 濤，程東年，田 銘

(國家數字交換系統工程技術研究中心，鄭州 4 50002)

基于副本通告的內容中心網絡快捷路由機制

劉 濤，程東年，田 銘

(國家數字交換系統工程技術研究中心，鄭州 4 50002)

內容中心網絡是一種新的網絡體系結構，采用以名字為標識的內容路由。然而，基本的內容中心網絡路由機制僅對服務器的內容建立路由表項，缺少到達節點上緩存的內容副本路由，導致節點緩存資源利用率低，產生較大的內容訪問時延。針對該問題，通過將節點緩存的副本向其他節點進行通告，提出一種快捷路由機制，使得節點能夠感知鄰居節點的內容副本，從而選擇最優內容源以獲取內容。仿真結果表明，相比不考慮節點副本路由的機制，快捷路由機制可明顯減少用戶請求的平均時延，在節點緩存容量為60個內容對象時，減少了43%的服務器負載。

內容中心網絡；快捷路由；內容活躍度；命名數據網絡；馬爾可夫鏈；副本

1 概述

網絡音視頻等多媒體業務的發展，使得互聯網的功能從端到端的主機通信變成了內容的分發，用戶更關注于內容而不是內容的存儲位置。為此，研究人員提出以內容為中心的網絡體系，即內容中心網絡(Content Centric Network, CCN)[1]，其核心思想是通過對內容的直接命名和基于內容名字的路由來進行內容的獲取和分發。CCN通常是扁平的拓撲結構，類似于現有的IP網絡。在CCN中，節點除了傳統的路由和轉發功能之外，還具備內容緩存能力。與基于IP地址的路由方式相比，CCN基于名字進行路由，不需要知道內容的位置或主機。

CCN的網絡實體能夠緩存臨時的內容(即內容副本)，以備將來訪問，副本緩存時間從數分鐘到數天不等，并且受內容流行度、緩存策略以及請求轉發策略所影響。為了利用這些副本資源，理想的內容路由方式是設計一種路由和轉發機制，對所有臨時的內容副本都能夠進行尋址，以使得用戶請求能夠被轉發到“最優”(例如，最近的)的可用副本。然而，這種理想的方式在CCN中存在實現上的困難，原因如下：

(1)網絡規模。CCN設計適應多種應用需求，不僅在小規模的有限網絡區域，也在整個網絡范圍內對內容副本進行尋址和路由，這將導致極大的控制開銷。

(2)時間因素。存儲在網絡節點上的副本不停地加入和刪除，存在高度的動態性和時變性，對這些副本進行路由更新導致極大的信令開銷[2]。

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

對節點副本進行路由的難點在于CCN緩存節點上內容的動態性和揮發性，路由到的緩存節點并不一定包含所請求的內容。因此，最大限度地減少這種不確定性成為本文研究的出發點。借鑒文獻[8-9]對非結構化P2P網絡中建立快捷鏈接的思想，提出一種基于副本通告的快捷路由(Short-cut Routing, SCR)機制，解決CCN節點上副本的路由構建問題。快捷路由機制對LRU(Least Recently Used)[10]緩存策略下節點上副本的有效性進行評估，節點有選擇地通告，并限定通告范圍，減少了副本路由導致的緩存缺失。與已有研究相比，快捷路由考慮了不同節點上內容命中率的差異性，以此實現轉發。

2 快捷路由原理

在CCN中，數據在內容源到請求用戶的路徑上沿途緩存，使得副本分布在多個節點。由于網絡中的內容對象數量巨大，并且內容分布動態變化，如果將節點緩存的所有內容向網絡進行洪泛通告，就會導致路由表膨脹，帶來非常大的網絡開銷。與之相比，快捷路由將緩存與路由緊密地結合在一起，只將節點上部分駐留時間較長的內容進行通告。

研究表明，互聯網存在小世界特性，并且距離相近的地區，用戶訪問具有相似性[11]。因此，快捷路由機制對內容的通告限于鄰居節點，從而減少通信開銷，即在局部構建了小跳數環境。

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

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

(2)選取最優內容源。節點在收到副本通告之后，建立內容的“局部地圖”，即到達副本的快捷表項(short-cut entry)，使得節點知曉內容的“存儲位置”，從而選擇最優的存儲節點獲取內容。

3 副本通告

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

圖1 內容通告示意圖

在內容副本信息通告中，需要考慮不同內容副本的差異性。內容副本在緩存中是動態變化的，由于用戶對內容的請求服從冪律分布，大部分請求訪問的是部分熱點內容。在特定的時間段內，不同內容副本在緩存中駐留的時間是不同的。

3.1 通告內容選取

緩存節點選取哪些副本向鄰居通告是快捷路由的一個重要問題，直觀的理解是根據副本在緩存中的持續時間長短來決定選取哪些副本，然而持續時間不容易獲取。根據緩存的特性，內容訪問的活躍程度或頻繁程度決定了緩存時間的長短，并與具體的緩存策略相關，現有路由器緩存算法大多采用LRU策略。本節對LRU緩存策略下的通告內容選取問題進行分析。

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

圖2 CCN節點緩存模型

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

圖3 CCN節點緩存馬爾可夫鏈模型

根據馬爾可夫鏈定義，此鏈為齊次馬爾可夫鏈，其狀態轉移矩陣為：

根據狀態轉移矩陣Q，計算出平穩分布矢量π=(π0, π1,…,πN)如下：

平穩分布π反映了節點a上內容i在各個緩存位置駐留的概率，特別地，π0表示內容不在緩存中的概率，即內容i的緩存缺失概率，對應地，內容i的命中概率為hi, a= 1-π0。

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

根據以上分析，節點計算出各個緩存位置上內容副本的命中概率，并且設定閾值φ。對于任意的內容i，只有當其命中率hi, a＞φ時，才通告內容i，避免在緩存上存在時間很短的內容被通告出去。

3.2 副本通告范圍設定

副本通告范圍n的設定是另一個需要研究的問題。節點上緩存的內容副本不需要洪泛通告到整個網絡，n越大，節點上的路由表項越多，導致快捷路由表膨脹，并且網絡的控制流量開銷太高。n的設定需要考慮代價與收益的權衡，然而，代價與收益的計算依賴于特定的網絡拓撲結構，難以通過統一的方式進行分析。為此，快捷路由機制僅給出確定通告范圍n的3個主要原則和可行的取值。

原則1 副本通告應限定在域內。其假定副本的覆蓋范圍主要是域內的用戶。

原則2 副本通告產生的控制流量應限定在一定程度內。以網絡中副本通告報文與數據報文(Data Packet)的數量之比ρ為指標，則ρ＜ρ0，其中，ρ0為預設的ρ的閾值。

原則3 根據副本通告建立的快捷路由表的平均條目數量應限定在一定上限內。為了減少重復，節點在根據副本通告構建快捷表時可以檢查本地緩存，如果通告的內容在本地緩存并且其命中概率較高，則不建立此內容的快捷路由表項。

一個可行的方式是將n設定為緩存節點到內容服務器的距離(跳數)n0，其假定為各個節點到服務器的距離近似相等。當內容的請求節點到緩存節點的距離大于到服務器的距離時，請求被轉發到服務器節點獲取所需內容，因此，緩存節點的內容通告范圍大于n0不會帶來更大的收益。

為了實現內容副本信息的通告，在CCN中，設計針對快捷路由的副本通告報文，格式如圖4所示。

圖4 內容副本通告報文格式

類型字段表示報文的類型，隨機數字段為隨機數，時間戳字段用來記錄報文的發送時間，跳數字段用來記錄內容通告節點到當前節點的跳數。內容名字和范圍分別為需要通告的內容的名字和通告范圍。

內容通告報文可以一次通告多個內容副本，比如對相同緩存等級的所有內容名字只發送一個通告報文。為了對多個內容名字進行壓縮，采用布魯姆濾波器對名字列表進行壓縮，并作為內容副本通告報文的內容名字域。節點收到副本通告報文后，建立快捷路由表。不失一般性，本文后續部分，仍以內容名字作為路由表項。

4 快捷路由表構建

節點在收到鄰居關于內容的通告后，根據內容名字、到達接口和到達此鄰居的跳數，創建如表1所示的快捷路由表(short-cut table)。

表1 快捷路由表

當同一個內容存在多個轉發接口時，則選擇跳數最小的接口轉發興趣包。由于快捷路由轉發到的節點并不保證一定存在所需的內容，即存在內容缺失，因此建立類似于文獻[7]中的回退機制，當請求的內容缺失時，可以回退到請求包的來源節點選擇其他的接口轉發。

5 工作流程

快捷路由可以分為以下階段：快捷路由構建階段和內容傳遞階段。

快捷路由構建階段主要進行內容的通告和快捷路由表的構建，其步驟如下：

Step1 內容緩存節點根據當前緩存表中的內容及其活躍度，構造某個或某些內容的內容通告報文，設定需要通告的范圍并向所有接口進行轉發。

Step2 當前節點在收到內容通告報文后，判斷當前收到的內容通告報文是否已存在，即報文內容和隨機數是否都相同，如果相同則丟棄該通告報文，否則執行Step3。

Step3 節點在收到內容通告報文后，更新范圍值。節點檢查快捷表，如果存在此報文中內容名字對應的表項，則更新表項信息，否則創建快捷路由條目，然后根據范圍值的大小決定是否轉發此內容通告。

Step4 當緩存節點的所有內容變化達到一定程度或經過時間間隔T后，重復Step1～Step3，重新進行內容通告，并且更新快捷路由表。

快捷路由表構建完成后，節點收到內容請求即興趣包后，按照內容緩存表、快捷路由表和轉發信息表的順序查表，執行相應的轉發操作。興趣包在節點內的轉發過程如圖5所示，其中，C表示內容緩存表；P表示PIT表；S表示快捷路由表；F表示FIB表。

圖5 節點內興趣包轉發過程

6 仿真實驗與分析

本節對快捷路由在CCN中的性能進行仿真驗證。實驗使用GT-ITM工具產生網絡拓撲，并使用VC++2008和Matlab2010工具進行仿真。

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

用戶請求到達服從到達速率λ=4個/s的泊松過程，并且在各個路由節點隨機到達；節點內容通告間隔為δ。仿真實驗的硬件環境如下：處理器主頻為雙核2.37 GHz，2 GB內存，Windows7操作系統。

為了對快捷路由的性能進行驗證，以用戶請求平均時延和內容源服務器負載為性能指標進行對比。源服務器負載定義為單位時間內收到的請求包個數，在仿真中將單位時間取為仿真程序運行時間，因此，源服務器負載可以表示為仿真期間源服務器收到的請求包個數。

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

6.1 用戶請求平均時延

設置節點內容通告間隔為δ=4 s。在仿真過程中共產生2 000個內容請求，記節點從內容請求發出到收到所請求的數據的時延為單個請求時延，則所有內容請求的平均時延仿真結果如圖6所示。

圖6 用戶請求平均時延

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

6.2 內容源服務器負載

取固定的緩存容量B=60、內容請求數Nq=2 000個、節點內容通告間隔為δ=4 s。以內容服務器收到的用戶請求即興趣包的個數作為其負載指標，則服務器負載性能的仿真結果如圖7所示。

圖7 內容源服務器負載

由圖7可見，在總的內容請求數為2 0 00的情況下，BasicCCN只將請求路由到確定的服務器，因而不會產生額外的請求包，其他3種算法都會產生額外的請求包，這是因為考慮了緩存內容缺失導致重新產生請求包。在服務器收到的請求包數量上，BasicCCN最多，因為其只能利用轉發路徑上的部分緩存的內容，而ACE、NCE和快捷路由利用了緩存節點的副本資源，有效地減少了內容服務器的負載。快捷路由相對于BasicCCN，在服務器負載上減少了約43%。

6.3 內容通告比例對性能的影響

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

圖8 內容通告比例對性能的影響

由圖8可看出，隨著內容通告比例x增加，用戶請求平均時延減少。然而，當x＞0.8時，平均時延反而有所增加，這是因為緩存中的內容存在動態性，將部分命中概率低的內容通告出去，導致請求被轉發到的節點內容已被淘汰，造成緩存缺失，重新從其他節點獲取內容使得時延增加。

7 結束語

本文在CCN內容路由基礎上，針對其無法利用節點緩存的內容副本的缺陷，在分析常用的LRU緩存策略的基礎上，提出一種基于副本通告的快捷路由機制，以解決內容中心網絡中內容副本的路由問題。下一步工作是將快捷路由應用到實際網絡環境中進一步驗證其性能。

[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] 葉潤生, 徐明偉. 命名數據網絡中的鄰居緩存路由策略[J].計算機科學與探索, 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上的流媒體特性及用戶訪問行為研究[J]. 北京航空航天大學學報, 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

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

劉 濤(1985－)，男，碩士研究生，主研方向：寬帶信息網絡，網絡體系結構；程東年，教授；田 銘，博士研究生。

2013-03-22

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

1000-3428(2014)05-0062-06

A

TP393