一種內容請求率的聚合及緩存放置方法
2023-10-18 09:33:19
一種內容請求率的聚合及緩存放置方法
【專利摘要】本發明提供了一種內容請求率的聚合方法，包括如下步驟：將網絡劃分為若干個簇，每個簇包括一個支配節點和若干個非支配節點；每個接入路由器節點建立請求向量RV(Ok)；每個簇的簇頭建立請求向量RV(Ok)；接入路由器節收到請求Ok，更新其請求向量RV(Ok)；對於請求Ok，通過解析請求名稱獲得到達網關的最短路徑；請求Ok與RV(Ok)傳入最短路徑的每個路由器節點；並依次更新每個節點所在簇頭的RV(Ok)，直至請求Ok與RV(Ok)到達最短路徑中的最後一個路由器節點。基於上述內容請求率的聚合方法，本發明還提供了一種緩存放置方法。本發明的方法可以減少網絡緩存冗餘，增加緩存多樣性，提高了網絡的整體資源利用率。
【專利說明】一種內容請求率的聚合及緩存放置方法
【技術領域】
[0001] 本發明涉及未來網絡緩存【技術領域】，具體涉及一種內容請求率的聚合及緩存放置 方法。
【背景技術】
[0002] 隨著網際網路應用的普及，內容服務已經成為網絡服務的主體，對於用戶來說，內容 共享是網際網路最主要的一個功能。用戶並不關心信息承載在哪臺計算機上，也不關心某個 視頻是哪個主機提供的，關心的是內容傳送過來的速度、質量以及是否安全。但是，在目前 的網際網路架構下，仍然是根據主機地址進行內容的檢索和傳送，這種方式已無法適應上層 應用的變化。
[0003] 為了解決上述問題，內容中心網絡（Content Centric Network, CCN)這一革命式 的網絡架構應運而生，該架構通過基於名稱的路由和網內緩存，實現從面向主機的點到點 通信模式到以內容為中心的通信模式轉變。在CCN中，用戶想要獲取內容時，首先發送一個 興趣包，路由器收到這個興趣包後會檢查本地的存儲空間是否有匹配的內容，如果有，則直 接將匹配的數據包沿原路返回給用戶，如果沒有，則繼續以基於名稱的路由方式向伺服器 轉發。這樣，用戶的請求能夠在中間節點得到響應，而不需要像IP網絡需要穿過整個網絡 到伺服器才滿足，從而優化帶寬使用效率，提高用戶內容獲取性能。
[0004] 因此，CCN的一個重要特徵是如何管理網內緩存節點，包括緩存決策和替換策略。 LCE (Leave Copy Everywhere)是CCN默認的緩存決策策略，也稱ALWAYS策略，即當對象返 回時，沿途的所有節點都緩存該對象的副本，但這種方式容易造成緩存冗餘，即相同的對象 在多個節點同時存有副本，降低了緩存系統所能緩存內容的多樣性。
[0005] C esar Bernardini等提出了 MPC策略，該策略只緩存流行的內容，每個節點統 計本地計算用戶對內容的請求數目，並以〈內容名稱；流行度計數〉對的形式存儲到流行度 表中，如果某個內容達到了流行度門限，那麼該內容會被標記為流行的，持有該內容的節點 會像其鄰居節點發送一個消息，建議鄰居節點也緩存該內容，鄰居節點根據自己的本地策 略來決定是否採納該建議消息。MPC策略在提高緩存性能的同時降低了資源浪費。
[0006] 如圖1 (a)所示，節點A、B、C會請求一個存儲在節點D的流行的內容dl，節點A還 會請求一個存儲在節點E的不流行的內容el。圖1(b)採用MPC策略，當節點A發送對內 容el的興趣包時，沿著路徑A-C-D-E的每個節點的流行度表中el的流行度都會增加，例如 在節點A、C、D、E中el的流行度設為1。相似地，B發送對內容dl的興趣包後，沿著路徑 B-C-D的節點中dl流行度設為1，在A和C也發送對dl的興趣包後，節點C和D中dl的流 行度變為3。假設此時只有節點D持有內容dl，而且dl的流行度達到了流行度門限，節點D 會向它的鄰居C和E發送建議信息，C和E因此緩存內容dl，並對後續的請求進行相應，顯 然MPC策略節約了存儲和帶寬資源，減少緩存操作次數，而且由於dl是流行的內容，節點E 也可能受到後續對dl請求，提高了請求命中率。
[0007] HaoWu等提出了 EMC緩存策略，該策略充分利用全局流行度信息，每個節點本地進 行緩存決策，以致儘可能多的在Intennet服務提供商（ISP)域內響應請求，從而降低ISP 域間流量，減少骨幹網的壓力。每個接入路由器周期性地在本地向量RV中記錄每個內容的 請求率，並將RV沿著轉發路徑向網關傳播。中間節點會對從其子節點收到的相同內容的 請求率進行聚合，沿路節點檢查每個內容的請求率，如果請求率低於閾值，那麼對該內容加 上LOW標籤，該標籤也隨之向上傳播。從網關路由器到接入路由器依次向下進行緩存決策， 首先路由器查看其收到的RV，根據請求率進行降序排列，然後依次進行存儲，直至存儲空間 滿。如果內容在一個節點緩存了，那麼其子節點的RV和緩存都刪除其內容，以降低緩存冗 餘；如果內容在一個網關緩存了，那麼其他網關也不再需要緩存該內容。
[0008] MPC策略只緩存最流行的內容，採用本地節點統計內容請求數目的方式，以內容的 請求數目反映其流行度情況。但該方式僅僅得到局部的流行度，而無法得到全局的內容流 行度，且忽略了"過濾"影響，即只有低層緩存沒有命中的請求才會被轉發給高層緩存節點， 這樣高層緩存節點統計的請求數目更加隨機，實際上不能很好地代表內容的流行度分布。
[0009] EMC策略的目標是降低ISP域間的流量，因此其緩存放置的結果是在ISP域內緩存 命中率越高越好，流行度高的內容放置到了網關處，而邊緣節點放置的是流行度相對較低 的內容，但這樣的結果是同層節點之間產生冗餘。如圖2所示，中間節點&和1?4都緩存了 內容〇3，而馬和1?4實際上彼此相鄰，即導致了很多相鄰的節點緩存了相同的內容，緩存多樣 性下降。除此之外，EMC策略要求網絡是樹狀拓撲，這與CCN任意網絡拓撲的初衷不符。
【發明內容】
[0010] 本發明的目的在於克服目前內容中心網絡緩存策略存在的上述問題，按照連通支 配集的概念將網絡劃分為若干個簇，在此基礎上，提出了一種內容請求率的聚合方法，並按 照內容請求率的排序，提出了 一種緩存放置方法。
[0011] 為了實現上述目的，本發明提供了一種內容請求率的聚合方法，包括如下步驟：
[0012] 步驟101)將網絡劃分為若干個簇，每個簇包括一個支配節點和若干個非支配節 點；每個接入路由器節點建立RV(Ok);每個簇的簇頭建立RV(Ok);
[0013] 步驟102)接入路由器節點收到請求0k，更新其請求向量RV(Ok);
[0014] 步驟103)對於請求0k，通過解析請求名稱獲得到達網關的最短路徑；
[0015] 步驟104)請求0k與請求向量RV(Ok)傳入最短路徑的下一個路由器節點；
[0016] 步驟105)判斷接收到請求向量RV(Ok)的節點是否為支配節點，如果判斷結果是 肯定的，轉入步驟107);否則轉入步驟106);
[0017] 步驟106)將請求0k與請求向量RV(Ok)傳到該節點所在簇的支配節點；
[0018] 步驟107)更新支配節點的請求向量RV(Ok);並給內容請求率小於最低門限值的 請求向量RV(Ok)添加一個LOW的標籤；
[0019] 步驟108)判斷此節點是否為最短路徑的最後一個節點，如果判斷結果是肯定的； 流程結束；否則，轉入步驟104)。
[0020] 上述技術方案中，所述請求向量RV (0k)的數據格式為：{請求0k，內容名稱0IDk，內 容請求率〇Ratek}。
[0021] 上述技術方案中，所述步驟101)進一步包括：
[0022] 步驟101-1)將網絡劃分為若干個簇，每個簇包括一個支配節點和若干個非支配 節點；
[0023] 步驟101-2)每個接入路由器節點統計內容請求率，並記錄到對應的請求向量 _k)中；
[0024] 步驟101-3)每個簇的簇頭將所有接收到的請求向量RV(Ok)的內容請求率相加， 並記錄到該簇頭的請求向量RV(Ok)中。
[0025] 上述技術方案中，所述步驟101-3)中的請求向量RV(Ok)不僅來自本簇的非支配 節點發送的，還有來自轉發路徑上其它簇發送的。
[0026] 上述技術方案中，所述步驟102)中更新其請求向量RV(Ok)為：將請求向量RV(O k) 中的ORatek加1。
[0027] 基於上述內容請求率的聚合方法，本發明還提供了一種緩存放置方法，包括如下 步驟：
[0028] 步驟201)在每個簇的簇頭建立一個請求向量表；將所有請求向量按照其內容請 求率降序排列順序存入請求向量表；對於標記了 LOW的請求向量，將其向後移動到請求向 量表的末端；
[0029] 步驟202)按照請求向量表從前至後的順序選擇對應的請求內容，放置在簇頭的 緩存空間中直至放滿；
[0030] 步驟203)從簇內其他節點隨機選擇一個節點繼續緩存請求向量表中的內容，直 至簇內所有節點的緩存空間都被佔用；
[0031] 步驟204)每個簇的簇頭會維護一個節點目錄，該目錄記錄請求內容的緩存節點。
[0032] 本發明的優點在於：
[0033] 1、本發明的方法利用連通支配集的概念，將網絡劃分為規則的簇層次結構；採用 簇內的緩存協同放置策略，減少冗餘，增加了緩存多樣性，提高了網絡的整體資源利用率；
[0034] 2、本發明的方法基於接入路由器統計內容請求率並沿著轉發路徑向網關傳播的 方式，提出了一種全局的內容流行度統計的方式；同時，通過LOW標籤標記局部流行度過低 的內容，使得內容在按照流行度從網關向邊緣放置時充分考慮了全局和局部冷熱不均的情 況；
[0035] 3、本發明的方法使簇內無冗餘協同放置，簇間按照上下遊關係按照內容流行度對 內容進行放置，增加了域內緩存內容數量；同時在進行緩存放置時考慮了內容全局和局部 的流行度，減小了網絡出口流量。
【專利附圖】
【附圖說明】
[0036] 圖1 (a)為CCN中緩存節點示意圖；
[0037] 圖1 (b)為現有技術中MPC策略緩存節點示意圖；
[0038] 圖2為現有技術中EMC策略緩存節點示意圖；
[0039] 圖3為本發明的內容請求率的聚合方法的流程圖；
[0040] 圖4為仿真實現中的網絡拓撲結構圖；
[0041] 圖5為將圖3按照本發明方法進行網絡分簇的示意圖；
[0042] 圖6為對表1中的內容請求率分布情況使用本發明的方法後的緩存結果圖；
[0043] 圖7為對表2中的內容請求率分布情況使用本發明的方法後的緩存結果圖。
【具體實施方式】
[0044] 本發明的應用平臺為：一個網絡拓撲結構，包含一個網關和若干個路由器節點。
[0045] 下面結合附圖和具體實施例對本發明做進一步的說明。
[0046] 如圖3所示，一種內容請求率的聚合方法，包括如下步驟：
[0047] 步驟101)將網絡劃分為若干個簇，每個簇包括一個支配節點和若干個非支配節 點；每個接入路由器節點建立RV(Ok);每個簇的簇頭建立RV(Ok);
[0048] 請求向量RV(Ok)的數據格式為：{請求Ok，內容名稱OID k，內容請求率ORatek};內 容請求率〇Ratek越大，表明該內容熱度越高。
[0049] 所述步驟101)包括：
[0050] 步驟101-1)將網絡劃分為若干個簇，每個簇包括一個支配節點和若干個非支配 節點；
[0051] 引用連通支配集的概念將網絡劃分為若干個簇，每個簇內只包含一個支配節點， 該支配節點作為簇頭；每個非支配節點的一跳距離都至少有一個支配節點，因此，簇內其餘 節點為與該支配節點相鄰的非支配節點。簇內的非支配節點受支配節點管理；簇間形成從 邊緣到網關的分層結構。
[0052] 步驟101-2)每個接入路由器節點統計內容請求率，並記錄到對應的請求向量 _k)中；
[0053] 步驟101-3)每個簇的簇頭將所有接收到的請求向量RV(Ok)的內容請求率相加， 並記錄到該簇頭的請求向量RV(Ok)中。
[0054] 每個簇的簇頭接收到的請求向量RV (Ok)，不僅來自本簇的非支配節點發送的，還 有來自轉發路徑上其它簇發送的。
[0055] 步驟102)接入路由器節收到請求Ok，更新其請求向量RV(Ok);
[0056] 所述更新請求向量RV (Ok)為：將請求向量RV (Ok)中的ORatek加1。
[0057] 步驟103)對於請求Ok，通過解析請求名稱獲得到達網關的最短路徑；
[0058] 步驟104)請求Ok與請求向量RV(Ok)傳入最短路徑的下一個路由器節點；
[0059] 步驟105)判斷接收到請求向量RV(Ok)的節點是否為支配節點，如果判斷結果是 肯定的，轉入步驟107);否則轉入步驟106);
[0060] 步驟106)將請求Ok與請求向量RV(Ok)傳到該節點所在簇的支配節點；
[0061] 步驟107)更新支配節點的請求向量RV(Ok);並給內容請求率小於最低門限值的 請求向量RV(Ok)添加一個LOW的標籤；
[0062] 所述最低門限值通過經驗和統計規律優選獲得，設置最低門限值的目的是過濾出 不流行的內容，從而降低網絡和存儲開銷。
[0063] 如果請求0k有LOW標籤，說明該請求內容在局部不流行。LOW標籤也會沿著轉發 路徑向網關傳播，即只要請求〇k在某一簇內被添上了 LOW標籤，那麼該請求的上遊簇一定 有LOW標籤；
[0064] 步驟108)判斷此節點是否為最短路徑的最後一個節點，如果判斷結果是肯定的； 流程結束；否則，轉入步驟104)。
[0065] 基於上述內容請求率的聚合方法，本發明還提供了一種緩存放置方法，包括：
[0066] 步驟201)在每個簇的簇頭建立一個請求向量表；將所有請求向量按照其內容請 求率降序排列順序存入請求向量表；對於標記了 LOW的請求向量，將其向後移動到請求向 量表的末端；
[0067] 步驟202)按照請求向量表從前至後的順序選擇對應的請求內容，放置在簇頭的 緩存空間中直至放滿；
[0068] 步驟203)從簇內其他節點隨機選擇一個節點繼續緩存請求向量表中的內容，直 至簇內所有節點的緩存空間都被佔用；
[0069] 步驟204)每個簇的簇頭會維護一個節點目錄，該目錄記錄請求內容的緩存節點。
[0070] 當有請求〇k到達簇m的簇頭時，如果簇頭沒有響應，那麼會查詢該簇的節點目錄， 判斷能否在簇m內找到該請求內容，如果簇m內其他節點都沒有緩存該請求內容，繼續向上 遊簇轉發該請求；如果在上遊簇內能找到該請求，則將簇m的RV(Ok)刪掉，這樣，請求0k的 轉發路徑上的簇m將不會緩存請求0,避免了上下遊簇中的內容冗餘。
[0071] 下面對現有的方法和本發明的方法進行仿真實現。
[0072] 如圖4所示，網絡拓撲結構中包括一個網關（GW)和10個路由器節點。
[0073] 假設每個路由器只能緩存一個內容。表1給出了各個接入路由器收到的請求內容 及其請求率，其中，#R代表接入路由器編號，〇k代表第k個內容。假設請求率的最低門限為 11，內容〇6, 〇7和〇 8的請求率都低於門限，因此都會被標記為LOW。
[0074] 表 1
[0075]
【權利要求】
1. 一種內容請求率的聚合方法，包括如下步驟： 步驟101)將網絡劃分為若干個簇，每個簇包括一個支配節點和若干個非支配節點；每 個接入路由器節點建立RV(Ok);每個簇的簇頭建立RV(Ok); 步驟102)接入路由器節點收到請求Ok，更新其請求向量RV(Ok); 步驟103)對於請求Ok，通過解析請求名稱獲得到達網關的最短路徑； 步驟104)請求Ok與請求向量RV(Ok)傳入最短路徑的下一個路由器節點； 步驟105)判斷接收到請求向量RV(Ok)的節點是否為支配節點，如果判斷結果是肯定 的，轉入步驟107);否則轉入步驟106); 步驟106)將請求Ok與請求向量RV(Ok)傳到該節點所在簇的支配節點； 步驟107)更新支配節點的請求向量RV(Ok);並給內容請求率小於最低門限值的請求 向量RV(Ok)添加一個LOW的標籤； 步驟108)判斷此節點是否為最短路徑的最後一個節點，如果判斷結果是肯定的；流程 結束；否則，轉入步驟104)。
2. 根據權利要求1所述的內容請求率的聚合方法，其特徵在於，請求向量RV(Ok)的數 據格式為：{請求〇k，內容名稱〇IDk，內容請求率0Ratek}。
3. 根據權利要求2所述的內容請求率的聚合方法，其特徵在於，所述步驟101)進一步 包括： 步驟101-1)將網絡劃分為若干個簇，每個簇包括一個支配節點和若干個非支配節點； 步驟101-2)每個接入路由器節點統計內容請求率，並記錄到對應的請求向量RV(Ok) 中； 步驟101-3)每個簇的簇頭將所有接收到的請求向量RV(Ok)的內容請求率相加，並記 錄到該簇頭的請求向量RV (0k)中。
4. 根據權利要求3所述的內容請求率的聚合方法，其特徵在於，所述步驟101-3)中的 請求向量RV (0k)不僅來自本簇的非支配節點發送的，還有來自轉發路徑上其它簇發送的。
5. 根據權利要求2所述的內容請求率的聚合方法，其特徵在於，所述步驟102)中更新 其請求向量RV(Ok)為：將請求向量RV(Ok)中的0Ratek加1。
6. -種緩存放置方法，基於權利要求1-5之一所述的內容請求率的聚合方法實現，該 方法包括如下步驟： 步驟201)在每個簇的簇頭建立一個請求向量表；將所有請求向量按照其內容請求率 降序排列順序存入請求向量表；對於標記了 LOW的請求向量，將其向後移動到請求向量表 的末端； 步驟202)按照請求向量表從前至後的順序選擇對應的請求內容，放置在簇頭的緩存 空間中直至放滿； 步驟203)從簇內其他節點隨機選擇一個節點繼續緩存請求向量表中的內容，直至簇 內所有節點的緩存空間都被佔用； 步驟204)每個簇的簇頭會維護一個節點目錄，該目錄記錄請求內容的緩存節點。
【文檔編號】H04L12/861GK104506432SQ201410833944
【公開日】2015年4月8日 申請日期:2014年12月26日 優先權日:2014年12月26日
【發明者】李唯源, 李楊, 林濤, 趙志軍 申請人:中國科學院聲學研究所