內容中心網絡中自集結協同緩存方法
2023-05-16 07:32:36 1
內容中心網絡中自集結協同緩存方法
【專利摘要】本發明涉及一種內容中心網絡中路由器緩存節點的內容獲取和請求動態路由的方法，該方法包括：內容中心網絡包括內容伺服器、接入路由節點和多個中間路由節點，接入路由節點包括競爭域和緩存域兩個部分；接入路由節點接收用戶的內容請求；根據內容請求，通過多個路由節點從內容伺服器或者緩存節點獲取所請求的內容；在競爭域緩存請求的內容，在一個測試期內測試和統計內容請求的頻率，將內容請求的頻率加在請求的內容的頻率包頭域中；根據近期最少使用緩存淘汰LFU算法，將內容請求的頻率大於最小訪問頻率的內容緩存於緩存域；沿著路由表所指示的返回內容伺服器的路徑，從接入路由節點向中間路由節點上推頻率小於最小訪問頻率的內容。
【專利說明】內容中心網絡中自集結協同緩存方法
【技術領域】
[0001]本發明涉及內容中心網絡中路由器內嵌緩存【技術領域】，具體涉及一種內容中心網絡中路由器緩存節點的內容獲取和請求動態路由的方法。
【背景技術】
[0002]網際網路應用正在經歷從面向主機的點到點通信模式到以內容為中心的通信模式轉變。網際網路應用主要圍繞內容的分發和檢索，即更加關心內容的本身。為此，內容中心網絡(Content Centric Network, CCN)專注於探索以信息或內容為中心的未來網絡架構。CCN中內嵌緩存(In-network Caching)是每個路由器的基本設施。路由器按照一定的策略對經過它的數據包進行緩存，為後續到來的請求提供服務。
[0003]網絡內嵌緩存的基本思想是緩存設備以固有設備在每個路由器節點部署，當一個路由器節點收到用戶的請求時，首先查找本地的存儲空間，判斷請求是否能在本地得到滿足，如果請求在本地命中，則將請求的內容返回，反之則查找路由表將請求轉發。CCN內嵌緩存的設計使請求可以在去往伺服器的路途中被沿途的節點滿足。
[0004]協同緩存是對網絡緩存性能的優化，指統籌各個節點的信息，從整體考慮每個節點的內容放置，從而提高網絡的整體性能。協同緩存策略按照協同的節點之間是否顯式的交互信息可以分為顯示協同和隱式協同。在CCN中，緩存節點不再是固定的，緩存的流量類型是多樣化的，緩存的操作要求是線速的，因此顯式協同決策算法由於其複雜度高、通信需求大而不適用於CCN。CCN需要研究簡單的隱式協同策略。
[0005]LCE (Leave Copy Everywhere)是CCN默認的緩存決策策略，即當對象返回時,沿途的所有節點都緩存該對象的副本，但這種方式容易造成緩存冗餘，即相同的對象在多個節點同時存有副本，降低了緩存系統所能緩存內容的多樣性。為了降低緩存冗餘、提高系統的緩存多樣性，需要緩存節點之間進行協同。Breadcrumbs是一種隱式協同策略，該策略設計沿途轉發對象的每一個節點都緩存對象副本，並且為每個途經的對象建立一個trail，利用歷史記錄的trail信息指導後續請求的路由，即利用內容的放置信息指導請求的路由轉發，從而達到快速查找內容，降低網絡時延的目的。
[0006]CLS (Cachintg Location and Searching Scheme)是一種按頻率自適應放置內容的緩存協同策略，內容塊每被請求一次就向用戶側拉近一次，即從命中節點移除而緩存到靠近用戶側的下一跳路由節點，而內容塊被某個緩存節點刪除(根據LRU替換策略)時就推回上一級節點，即緩存到遠離用戶側的上一跳路由節點。當系統達到穩態時，熱門內容將被拉到靠近用戶的網絡邊緣，而冷門內容將被緩存在遠離用戶的伺服器側，形成內容按頻率的自適應放置。同時，該策略也沿途建立類似Breadcrumbs中的trail信息，以方便內容就近獲取。
[0007]ProbCache是一個概率隱式協同策略，對象返迴路徑中沿途節點緩存對象的概率與節點和請求者之間的距離成反比，即節點距離請求者越近，對象被緩存的概率越高，反之概率越低。該方法在減少對象複製次數的同時，試圖快速地將對象複製到距離請求者更近的網絡邊緣。
[0008]如圖1為以上三種緩存方案對比圖。
【發明內容】
[0009]本發明的目的是針對現有技術的不足，提供一種內容中心網絡中自集結協同緩存方法，從而減小緩存冗餘，提高緩存的利用率。
[0010]為實現上述目的，本發明設計了一種內容中心網絡中路由器緩存節點的內容獲取方法，該方法包括:內容中心網絡包括內容伺服器、接入路由節點和多個中間路由節點，接入路由節點包括競爭域和緩存域兩個部分；
[0011]接入路由節點接收用戶的內容請求；
[0012]根據內容請求，通過多個路由節點從內容伺服器或者緩存節點獲取所請求的內容；
[0013]在競爭域緩存新請求內容一個測試期，在測試期內測試和統計請求內容的頻率，將頻率加在請求內容的頻率包頭域中；
[0014]獲取所述緩存域中存儲內容的最小訪問頻率；
[0015]根據近期最少使用緩存淘汰(Least Frequently Used, LFU)算法,將所述內容請求的頻率大於所述最小訪問頻率的請求的內容緩存於所述緩存域；
[0016]沿著路由表所指示的返回內容伺服器的路徑，從接入路由節點向多個中間路由節點上推頻率小於所述最小訪問頻率的內容。
[0017]本發明還設計了 一種內容中心網絡中路由節點對內容請求動態路由方法，該方法包括:內容中心網絡包括內容伺服器、接入路由節點、和多個中間路由節點；
[0018]路由節點接收來自用戶的內容請求；
[0019]判斷本節點是否緩存有所請求內容，如果有則直接返回給用戶；如果沒有則判斷本節點是否有痕跡信息的內容標識指向該請求所針對的內容副本；痕跡信息包括內容標識、下一級接口、到緩存節點的距離；
[0020]在確定內容標識符合請求的內容時，將請求按痕跡信息發送給緩存節點；
[0021]路由節點接收內容副本並且將內容副本發送給用戶。
[0022]優選地，路由節點向用戶發送內容副本，並在與緩存命中節點或內容伺服器相比較離用戶更近的路由節點為請求的內容創建痕跡信息。
[0023]優選地，路由節點接收到內容副本移動的信息，根據內容副本移動情況更改本節點的痕跡信息。
[0024]優選地，路由節點接收因刪除被推回的內容副本，刪除痕跡信息。
[0025]本發明的優點在於通過接入路由器的劃分提供了一種簡單，民主的局部頻率檢測方法，每個內容的頻率由其服務的用戶的訪問行為決定；放置策略可以實現內容按頻率的自動分布，從而減小了緩存冗餘和用戶平均下載時延。利用內容放置信息對請求路由的指弓丨，使用戶的請求就近得到滿足，減小了網絡的整體流量開銷，提高了緩存的利用率。並且痕跡信息只在部分節點創建，降低了構建痕跡信息產生的開銷。
【專利附圖】
【附圖說明】[0026]圖1為現有技術的三種緩存方案對比；
[0027]圖2為本
【發明內容】
中心網絡中路由器緩存節點的內容獲取流程圖；
[0028]圖3為本
【發明內容】
中心網絡中路由節點對內容請求動態路由流程圖；
[0029]圖4為本發明實施例中接入路由器節點中緩存空間劃分；
[0030]圖5為本發明實施例中路由節點的拓撲結構；
[0031]圖6為本發明實施例中路由節點的內容的下拉和上推過程示意圖；
[0032]圖7為本發明實施例中內容中心網絡中動態路由策略圖；
[0033]圖8為本發明實例中不同方法的命中率性能比較示意圖；
[0034]圖9為本發明實例中不同方法的命中距離性能比較示意圖。
【具體實施方式】
[0035]為使本發明實施例的技術方案以及優點表達的更清楚，下面通過附圖和實施例，對本發明的技術方案做進一步的詳細描述。
[0036]本發明設計了 一種內容中心網絡中路由器緩存節點的內容獲取方法，該方法包括:內容中心網絡包括內容伺服器、接入路由節點和多個中間路由節點，接入路由節點包括競爭域和緩存域兩個部分；
[0037]接入路由節點接收用戶的內容請求；
[0038]根據內容請求，通過多個路由節點從內容伺服器或者緩存節點獲取所請求的內容；
[0039]在競爭域緩存新請求內容一個測試期，在測試期內測試和統計請求內容的頻率，將頻率加在請求內容的頻率包頭域中；
[0040]獲取所述緩存域中存儲內容的最小訪問頻率；
[0041]根據近期最少使用緩存淘汰LFU算法，將所述內容請求的頻率大於所述最小訪問頻率的請求的內容緩存於所述緩存域；
[0042]沿著路由表所指示的返回內容伺服器的路徑，從接入路由節點向多個中間路由節點上推頻率小於所述最小訪問頻率的內容。
[0043]圖2為本
【發明內容】
中心網絡中路由器緩存節點的內容獲取流程圖，如圖所示，本實施例具體包括如下步驟:
[0044]步驟101、接入路由節點接收用戶的內容請求；
[0045]步驟102、根據內容請求，如果請求的內容在內容伺服器命中，則通過多個路由節點從內容伺服器獲取所請求的內容；
[0046]步驟103、根據內容請求，如果請求的內容在路由器緩存節點命中，則從緩存節點獲取所請求的內容；
[0047]步驟104、在接入路由節點的競爭域緩存新請求內容一個測試期；
[0048]具體地，如圖4所示為本實施例中接入路由器節點中緩存空間劃分，在自集結協同緩存機制中，用戶的接入路由器(最後一跳)中的緩存空間分為大小不等的兩個部分，其中大的緩存空間部分叫做競爭域(competitive domain),用來存儲每個新請求的內容,並且對於該內容緩存一個測試期。在測試期內，該內容將被計算請求頻率(即頻率)。整個測試期內，不管其頻率有多低，該內容將一直保留而不被替換。測試器之後，頻率高的內容將被緩存到小的緩存空間部分叫做緩存域(caching domain),以便滿足後續對該熱內容的請求。
[0049]步驟105、在步驟104中的測試期內測試和統計請求內容的頻率；
[0050]步驟106、將頻率加在請求內容的頻率包頭域中；
[0051]具體地，如圖5所示為本實施例中路由節點的拓撲結構，每個路由器需要記錄每個內容塊的訪問頻率，以及所有內容塊的平均訪問頻率。
[0052]步驟107、運行近期最少使用緩存淘汰算法(LFU算法)；
[0053]步驟108、如果步驟105中請求內容測試的頻率大於接入路由節點緩存域頻率最小的內容，則將請求內容緩存於接入路由節點的緩存域；
[0054]步驟109、如果步驟105中請求內容測試的頻率小於接入路由節點緩存域頻率最小的內容，或者步驟108中頻率最小的內容，都沿著FIB所指示的返回內容伺服器的路徑，從接入路由節點向上遊路由器緩存節點上推冷門內容。
[0055]本發明還設計了 一種內容中心網絡中路由節點對內容請求動態路由方法，該方法包括:內容中心網絡包括內容伺服器、接入路由節點、和多個中間路由節點；
[0056]路由節點接收來自用戶的內容請求；
[0057]判斷本節點是否緩存有所請求內容，如果有則直接返回給用戶；如果沒有則判斷本節點是否有痕跡信息的內容標識指向該請求所針對的內容副本；痕跡信息包括內容標識、下一級接口、到緩存節點的距離；
[0058]在確定內容標識符合請求的內容時，將請求按痕跡信息發送給緩存節點；
[0059]路由節點接收內容副本並且將內容副本發送給用戶。
[0060]優選地，路由節點向用戶發送內容副本，並在與緩存命中節點或內容伺服器相比較離用戶更近的路由節點為請求的內容創建痕跡信息。
[0061]優選地，路由節點接收到內容副本移動的信息，根據內容副本移動情況更改本節點的痕跡信息。
[0062]優選地，路由節點接收因刪除被推回的內容副本，刪除痕跡信息。
[0063]圖3為本
【發明內容】
中心網絡中路由節點的內容拉推流程圖，如圖所示，本實施例具體包括如下步驟:
[0064]步驟201、路由節點接收來自用戶的內容請求；
[0065]步驟202、判斷本節點是否緩存有所述請求內容；
[0066]步驟203、如果是則直接將所述請求的內容返回給用戶；
[0067]步驟204、如果沒有所述請求內容則判斷本節點是否有痕跡信息的內容標識指向該請求所針對的內容副本；痕跡信息包括內容標識、下一級接口、到緩存節點的距離；
[0068]步驟205、如果沒有痕跡信息(trail)的內容標識指向該請求所針對的內容副本，則該路由節點從內容伺服器獲取請求內容；
[0069]步驟206、在確定內容標識符合請求的內容時，將請求按痕跡信息發送緩存節點；
[0070]步驟207、路由節點接收來自緩存節點的內容副本並且將內容副本發送給用戶。
[0071]如圖6所示為內容中心網絡中路由節點的內容的下拉和上推過程的示意圖，每一級路由節點對內容都做下拉和上推的處理，逐漸地，一個冷門內容被一級一級的向上推，直到伺服器。除了推回到伺服器，凡是被請求過的內容，就會在從伺服器到用戶的路徑上保留至少一份副本，該副本可以就近為其他用戶請求提供服務，因此可以減小用戶下載時延和伺服器負荷。
[0072]內容中心網絡中路由節點的內容拉推方法也是內容自集結緩存的策略(SAC)，該方法可以根據用戶的訪問行為，自動的將最熱門內容放在離用戶最近的接入路由器，次熱的內容放在第二層，以此類推。
[0073]圖7為本發明實施例中內容中心網絡中動態路由策略圖；
[0074]首先，我們借用現有技術ProbCache中的路徑長度監測方法,在每個request包頭中添加一個TSI (Time Since Inception)域,在每個content包頭中添加一個TSI和TSB (Time Since Birth)域,具體如圖5所示。TSI的初始值為O,當request每經過一個路由器，其值增加I，它代表request在找到所請求內容之前所走過的跳數。當請求內容在中間路由器或者伺服器命中，該request中攜帶的TSI值將複製到content包頭中TSI域中。因此，TSB的初始值也為0，從命中處開始到返回到用戶的途中，每經過一個路由器，其值增加1，它代表該內容經過TSB跳回到用戶。例如，圖5中，用戶I從E點請求內容Cl，該請求在伺服器S處命中，當Cl返回用戶I時，TSI=6，TSB=5 ;而用戶2從Dl點請求內容c2，該請求在路由器B處命中，當c2返回用戶2時，TSI=3, TSB=2。
[0075]優選地，路由節點向用戶發送內容副本，並在與緩存命中節點或內容伺服器相比較離用戶更近的路由節點為請求的內容創建痕跡信息。
[0076]具體地,如圖7 (a)所示為痕跡信息的創建,在內容下載路徑的一些中間節點上需要建立為該內容trail信息。該trail由(ID, out, h)三元組組成，由內容塊ID標識，out是指內容塊傳輸到下一跳的接口，h是指該節點力請求用戶的距離，值為h= (TS1-1) -TSB。SAC中trail與現有技術CLS/Breadcrumbs中trail的主要差別在於後者在內容下載路徑沿途的所有節點都創建，而前者只在與伺服器相比較離接入路由器更近的節點處創建，即h〈(TS1-l)/2處。所以SAC方案比CLS方案的開銷更小。另外，緩存節點由於自身已經存有該內容，所以也不需要創建trail。
[0077]舉例如圖7(a)所示，用戶I從節點E處請求內容cl，cl緩存在節點E同時節點C和D創建trail信息。之後用戶3從節點Cl處請求內容cl，cl緩存在節點Cl同時節點B創建trail信息。
[0078]根據創建的痕跡信息，路由節點可以對收到的內容請求進行動態路由。
[0079]優選地，路由節點接收到內容副本移動的信息，根據內容副本移動情況更改本節點的痕跡信息。
[0080]具體地,如圖7 (b)所示為動態路由，SAC的基本思想是使中間路由節點緩存的內容可以滿足其附近的請求，從而提高緩存利用率和用戶體驗。這也是CCN與IP網絡的根本區別所在。
[0081]多個路由節點含有內容的trail信息就意味著沿著trail所指的方向有一個該內容的副本，更重要的是這個副本離用戶比路由器要更近。因此，當一個請求在某個路由器中發現了所請求內容的trail時，該請求就被動態路由到trail所指的路徑上，而不再按照默認路由到伺服器上獲取。
[0082]舉例如圖7(b)所示，用戶2從節點Dl處請求內容Cl，Cl緩存在伺服器和節點E。當請求到達路由節點C的時候，由於節點C含有Cl的trail(說明trail所指的副本比伺服器更近)，所以該請求將被動態路由到節點E。當請求內容返回到用戶2之後，根據SAC放置策略內容處Cl將被緩存到D1，同時在節點C處創建關於內容Cl的又一個trail (cl, Dl, I)信息。這樣一來，節點C包含關於內容Cl的2條trail信息，分別指向距離不同的緩存節點，根據h值的不同，往往優先考慮距離較近的緩存副本。
[0083]優選地，路由節點接收因刪除被推回的內容副本，刪除痕跡信息。
[0084]具體地，如圖7 (C)所示為痕跡信息的刪除，如果緩存的內容被上推回去，trail信息將被刪除。例如，緩存在節點E處的內容Cl如果被上推回節點D，則節點D處的trail被刪除。同理，緩存在節點Dl處的內容Cl如果被上推回節點C，則節點C處的trail被刪除。從這裡也可以看出，與現有技術Breadcrumbs不同，SAC的trail信息可以保證所指的內容副本一定存在，而Breadcrumbs中的trail只有在其timeout時才會刪除，不管其內容副本是否被移除。
[0085]另外，中間節點收到被上推回來的副本時，如果自身含有該內容的其他trail信息，為了減小緩存冗餘，則刪除被上推回來的副本。例如，緩存在節點Dl處的內容Cl如果被上推回節點C，因為節點C仍然含有一條trail信息指向Cl，說明節點C的附近已經含有Cl的副本，則刪除被上推回來的副本Cl。
[0086]在一實例中，該實例為一個5層的二叉樹，根節點為伺服器，包含全部的內容。靠近伺服器的多個路由節點的緩存空間小，而靠近用戶的多個路由節點的緩存空間大。為測試不同大小的內容存儲空間對本方案的影響，本實例分別設置總的網絡內容存儲空間為全部內容大小的10%，20%，30%，40%，50% (橫坐標)。以500個內容為例，每個內容被分割為同等大小的chunk，內容的平均大小為50KB，每個chunk為4kB。內容的頻率服從Zipf分布，為了驗證本方案在不同內容頻率分布的情況下同樣有效，本實例共測試了兩種內容頻率分布情況，令Zipf分布的α參數分別為I和2。請求隨機的來自最下兩層節點，服從泊松分布，速率為每秒5個請求。為了驗證本發明的性能，本實驗在仿真平臺上同時實現了現有技術Psaras等人提出的ProbCache方法和現有技術CLS,將本發明與ProbCache和CLS方法做比較，測試的結果如下:
[0087]如圖8所示為α參數分別為I和2時的不同方法的命中率性能比較示意圖。命中率定義為節點處滿足的請求數量與到達的請求數量的比值。命中率為網絡所有節點的請求命中率平均值。命中率越大表明越多的請求在向源伺服器的路徑中被滿足，從而減小了源服務的負荷。即命中率越大越好。從圖8可以看出，本發明的命中率在不同網絡緩存容量大小的條件下都比ProbCache方法和CLS方法好。
[0088]如圖9所示為α參數分別為I和2時的不同方法的命中距離性能比較示意圖。命中距離指請求被命中時實際走的跳數。因此命中距離越小，表示請求在越靠近用戶端得到滿足，節約了網絡的流量開銷。從圖9看出，本發明的平均命中距離在不同網絡緩存容量大小的條件下都優於ProbCache方法和CLS方法。原因就在於SAC方案是根據頻率將內容自動分布在網絡合適的位置且保持較少的內容副本，這樣可以有效減小緩存內容冗餘和平均下載時延，同時動態路由可以大大提高網絡中緩存內容的利用率。
[0089]綜上所述，本發明將接入路由器分成競爭域和緩存域兩個部分，將所有新請求的內容一次拉倒接入路由器中接受頻率的檢測。在一定的測試期後，將頻率高的內容保留，將頻率低的內容刪除。在本發明的放置策略中，每個節點統計其所有緩存內容的訪問頻率，每個緩存內容在被刪除時移至上一層節點，同時攜帶其自身訪問頻率信息，通過比較訪問頻率來決定內容放置位置。通過建立trail索引信息，把內容的放置和路由策略一起緊耦合地考慮，用內容放置的歷史信息指導請求的路由。
[0090]本發明的優點在於通過接入路由器的劃分提供了一種簡單，民主的局部頻率檢測方法，每個內容的頻率由其服務的用戶的訪問行為決定；放置策略可以實現內容按頻率的自動分布，從而減小了緩存冗餘和用戶平均下載時延。利用內容放置信息對請求路由的指弓丨，使用戶的請求就近得到滿足，減小了網絡的整體流量開銷，提高了緩存的利用率。並且痕跡信息只在部分節點創建，降低了構建痕跡信息產生的開銷。
[0091]以上所述的【具體實施方式】，對本發明的目的、技術方案和有益效果進行了進一步詳細說明，所應理解的是，以上所述僅為本發明的【具體實施方式】而已，並不用於限定本發明的保護範圍，凡在本發明的精神和原則之內，所做的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
【權利要求】
1.一種內容中心網絡中路由器緩存節點的內容獲取方法，其特徵在於，內容中心網絡包括內容伺服器、接入路由節點和多個中間路由節點，接入路由節點包括競爭域和緩存域兩個部分； 接入路由節點接收用戶的內容請求； 根據內容請求，通過多個路由節點從內容伺服器或者緩存節點獲取所請求的內容； 在所述競爭域緩存所述請求的內容，在一個測試期內測試和統計所述內容請求的頻率，將所述內容請求的頻率加在所述請求的內容的頻率包頭域中； 獲取所述緩存域中存儲內容的最小訪問頻率； 根據近期最少使用緩存淘汰LFU算法，將所述內容請求的頻率大於所述最小訪問頻率的請求的內容緩存於所述緩存域； 沿著路由表所指示的返回內容伺服器的路徑，從接入路由節點向中間路由節點上推頻率小於所述最小訪問頻率的內容。
2.一種內容中心網絡中路由節點對內容請求動態路由方法，其特徵在於，內容中心網絡包括內容伺服器、接入路由節點、和多個中間路由節點； 所述路由節點接收來自用戶的內容請求； 判斷本節點是否緩存有所述請求內容，如果有則將所述請求的內容返回給用戶；如果沒有則判斷本節點是否有痕跡信息的內容標識指向該請求所針對的內容副本；痕跡信息包括內容標識、下一級接口、到緩存節點的距離； 在確定內容標識符合請求的內容時，將所述請求按痕跡信息發送給緩存節點； 所述路由節點接收內容副本並且將所述內容副本發送給用戶。
3.根據權利要求2所述的方法，其特徵在於，所述路由節點向用戶發送所述內容副本，並在與緩存命中節點或內容伺服器相比較離用戶更近的路由節點為請求的內容創建痕跡信息。
4.根據權利要求2所述的方法，其特徵在於，所述路由節點接收到所述內容副本移動的信息，根據所述內容副本移動情況更改本節點的痕跡信息。
5.根據權利要求2所述的方法，其特徵在於，所述路由節點接收因刪除被推回的所述內容副本，刪除痕跡信息。
【文檔編號】H04L12/861GK103716254SQ201310741198
【公開日】2014年4月9日 申請日期:2013年12月27日 優先權日:2013年12月27日
【發明者】李楊, 徐月梅, 林濤, 趙志軍, 慈松 申請人:中國科學院聲學研究所