信息中心網絡中一種基于內容熱度的分區緩存替換方法

李遠航，王勁林，韓 銳

（1.中國科學院聲學研究所，北京 100190；2.中國科學院大學，北京 100049）

信息中心網絡（ICN）[1-2]架構致力于解決網絡流量暴增的問題，并且能夠適應各種新興技術（如物聯網技術[3]和5G 技術[4]）。網內緩存是ICN 的核心功能，可以降低內容的傳輸時延，減輕源服務器的負載[5-6]。在緩存空間有限的前提下設計高效的緩存替換算法，從而提高緩存命中率，是保障信息中心網絡緩存性能的關鍵[7]。

目前的緩存替換方法難以持久緩存熱門內容，對緩存性能提升有限。針對上述問題，該文提出了一種基于內容熱度的分區緩存替換方法，將緩存空間進行分段，并根據內容的訪問情況放置于不同的段中，以保存流行的內容和替換冷門的內容。仿真結果顯示，該方法能夠持續緩存熱門的內容，提升緩存的性能。

1 相關工作

LRU 是ICN 緩存中最常采用的替換方法，它使用一個鏈表結構維護所緩存的內容。當內容在緩存中被命中，或者新內容加入緩存時，將內容加入到鏈表首部；當緩存空間已滿，則從鏈表尾部選出被替換的內容。FIFO 是另一種常見的緩存替換方法，通過維護一個先進先出的列表，新內容加入列表首部，優先替換列表尾部的內容，但是FIFO 不能避免流行的內容被替換。隨機替換方法（RR）通過隨機選擇某一內容進行替換，由于隨機選取替換目標，導致該方法的性能不穩定?；趦热荽笮〉木彺嫣鎿Q方法（SIZE）在緩存空間已滿時，每次都選擇占用空間最大的內容進行替換，當被替換的內容是流行的內容時，反而導致緩存命中率的降低。LFU 方法選擇訪問頻率最低的內容進行替換，但是由于需要頻繁更新內容的訪問頻率，消耗了額外的計算資源和空間資源。

部分研究人員嘗試在上述經典替換算法的基礎上，提出進一步的改進和優化。Ooka 等人提出了一種低開銷的緩存替換方法[8]，采用環形鏈表而不是雙鏈表管理內容，通過只使用比傳統替換方法（例如LRU）少一半以上的內存，達到了與之相接近的網絡性能。Sun 等人提出了一種優化的緩存替換方法[9]，計算每個內容的權重，緩存權重高的內容并替換權重低的內容。這種方法需要實時計算并比較內容的權重，需要消耗更多的計算資源。

2 基于內容熱度的分區緩存替換方法

傳統LRU 算法用鏈表結構維護緩存的內容，并默認將最新被訪問的內容放到鏈表頭部。當大量不流行的內容在近期被集中訪問或者緩存時，會將之前流行的內容替換出去，從而導致緩存性能的下降。對于LRU 替換方法，最理想的狀態是從鏈表頭部到鏈表尾部，其記錄內容的熱度依次下降，可是LRU 無法保證流行的內容不被替換。在該文中，利用緩存路由器計算的內容熱度信息，提出了一種基于內容熱度的分區緩存替換方法，可以更好地保存流行的內容，替換不流行的內容。

傳統LRU 緩存算法可以分為三種操作：1）插入新內容索引；2）更新內容索引；3）刪除內容索引，其示意圖如圖1 所示。

圖1 傳統LRU緩存方法

在LRU 中，當緩存路由器緩存一個新內容時，會觸發操作1；而當緩存空間已滿時，執行操作1 會觸發操作3；當內容的請求在緩存路由器的緩存中命中時，會觸發操作2。對于操作1，由于不知道新緩存的內容是否在接下來是流行的，所以直接將內容索引添加到鏈表首部是不合適的。此外，LRU 此前已經緩存了部分內容，并且鏈表的索引順序已經反應了一定的內容熱度趨勢，需要根據新緩存的內容的熱度確定插入鏈表的具體位置。基于如上兩個原因，執行操作1 時，應該根據新內容的熱度信息來選擇添加到緩存空間的位置，這就需要考慮對原有的緩存空間進行分區處理。對于操作2，傳統LRU 算法會將被命中的內容索引移動到鏈表首部，而不考慮內容索引之前的狀態信息，而由于在鏈表中的不同位置體現了內容索引不同的熱度情況，所以可以根據鏈表位置的不同，對被命中的內容索引執行不同的操作。對于操作3，為了避免流行的內容被刪除而不流行的內容被保留，可以在一個小的區間內根據內容的熱度信息，選擇熱度低的內容進行替換。

根據上述傳統LRU 的三個步驟進行優化，提出了基于內容熱度的分區緩存替換方法，其示意圖如圖2 所示。

圖2 基于內容熱度的分區緩存替換方法

所提出的替換方法，其本質是讓熱門的內容盡量保存在緩存中，并且在發生緩存替換時，優先替換冷門的內容。首先，在LRU 的鏈表結構的基礎上，進一步分為相同大小的三段區域，依次稱為熱門區、中間區和冷門區，分別對應LRU 的鏈表首部、中部、尾部區域。將鏈表進行分區有幾個明顯的好處：首先，可以利用內容的熱度信息，對內容進行分區管理。對于熱門的內容，希望它能保存在熱門區，而對于冷門的內容則反之。其次，在刪除內容時可以在冷門區內進行檢索，以刪除合適的內容，并且減輕了全局搜索導致的開銷。最后，內容索引的位置更新可以根據所在位置進行不同的操作，而不是不論內容是否流行都將其放到鏈表首部。

進行如上操作需要緩存路由器統計緩存內容的熱度，并且在緩存路由器緩存新內容時需要知道新內容的熱度。緩存路由器可以通過記錄內容的被請求數目，以此表示內容的熱度。根據不同場景的需要，也可以采用更精確的熱度預測算法[10-11]。當內容在緩存路由器被命中時，這個內容在傳輸時可以攜帶熱度信息，交由路徑上的緩存路由器緩存時使用；當內容在源服務器中被命中時，認為這類內容具有一個預先設置的初始熱度。通過這種方式，緩存路由器之間進行了隱式的路徑協同，下游從上游獲取了傳輸內容的熱度信息。

基于上述分析，提出了基于內容熱度的分區緩存替換方法。為了簡便，在下文中稱呼所提出的基于內容熱度的分區緩存替換方法為PB-S（Popularitybased-Segmented）。當緩存路由器收到一個新的內容，不同于LRU 直接將內容索引放置在鏈表首部的操作，PB-S 將比較該內容的熱度和原有緩存內容的熱度，根據比較結果確定將新內容放置在熱門區、中間區或者冷門區。在該文中，記錄當前狀態下，熱門區末端和中間區末端內容的熱度。若新內容的熱度高于熱門區末端內容的熱度，則將新內容插入到熱門區首部；若新內容的熱度低于熱門區末端內容的熱度但高于中間區末端內容的熱度，則將新內容插入到中間區首部；若兩次比較結果中新內容的熱度都更低，則直接插入冷門區的首部。當內容索引在緩存中被請求命中時，根據內容所在的不同位置進行不同的操作：當內容索引在冷門區被命中時，PBS 將該內容移到中間區的首部；當內容索引在熱門區或者中間區被命中時，PB-S 將該內容索引直接移到熱門區的首部。當緩存空間已滿需要逐出內容時，PB-S 從冷門區選擇熱度低的內容進行替換。

目前的ICN 路由器架構中，為了滿足線速轉發要求與大容量數據緩存的功能，多采用DRAM+SSD+HDD 的分級緩存系統。如何合理利用不同傳輸速度的存儲介質也需要進一步考慮。通常情況下，緩存內容的索引信息會保存在DRAM 中，以便于快速檢索和管理。而流行的內容應該存儲在高傳輸速度的存儲介質中，以便于快速提供內容服務。因此在提出的分區緩存替換方法中，可以讓熱門區的內容存儲在DRAM 和SSD 中，讓中間區和冷門區的內容存儲在HDD中，以此來減少內容服務的緩存響應時延。

3 仿真實驗與分析

3.1 仿真實驗與參數

采用Icarus[12]模擬器通過仿真實驗進一步測試所提出的緩存替換方法的性能。Icarus 是一個基于Python 的ICN 緩存模擬器，專門用于模擬評估ICN 緩存場景下的緩存性能。采用Zipf 分布模擬請求數據流，根據文獻[13-14]對于web 內容熱度的分析，Zipf分布的α值取值為0.4～1.0 是合理的。內容的數量設置為1 000，并且緩存空間比率（網絡緩存空間與內容數量的比例）設置為從0.1～1。設置前10 000 次內容請求作為系統的預熱，并在之后的20 000 次請求開始正式測量。緩存策略采用LCE。網絡拓撲采用了面向研究和教育團體的泛歐洲數據網絡GEANT。

3.2 評價指標

此次仿真實驗采用緩存命中率以及內容平均獲取時延進行性能評價，具體評價指標定義如下：

1）內容替換比率是內容進入緩存后最終被替換的比率?？梢远x為EvictedRadio=NumEvictedCached，其中，NumEvicted為某一內容從緩存中被替換的次數；NumCached為某一內容被緩存的次數。為了提升網絡性能，對于流行的內容，希望其更持久地存在于緩存中，即希望流行內容的替換比率更低。

2）緩存命中率是由緩存提供內容服務的比例?？梢远x為CacheHitRatio=Numcachehit，其中，Numcachehit為從緩存路由器中獲得內容的用戶請求數；Num為用戶總請求總數。緩存命中率越高，代表緩存的資源利用率越高，源服務器的負載也越低。

3）網絡平均時延是用戶從發出請求到收到內容的平均時間。網絡平均時延越低，用戶體驗越好。

3.3 仿真結果分析

1）熱度機制有效性分析

在上一節中，分析了在新內容插入以及內容替換時可以利用熱度信息。具體來說，在新內容插入時，PB-S 利用新內容的熱度判斷新內容插入熱門區、中間區還是冷門區；在內容替換時，PB-S 搜索冷門區的內容，選擇熱度最低的內容進行替換。為了評價這兩部分使用的熱度信息是否有幫助，以及驗證所提出方法中對應步驟的有效性，首先進行了對比實驗，結果如圖3 所示。

圖3 在緩存替換中使用熱度信息分析的仿真結果

圖3(a)、(b)分別表示Zipf 分布參數變化時網絡的緩存命中率和網絡平均時延的變化情況，圖3(c)、(d)分別表示緩存空間比率變化時網絡的緩存命中率和網絡平均時延的變化情況。其中，PB-S 是上文提出的緩存替換方法，PB-S(1)在插入新內容時直接插入到整個鏈表首部（即熱門區首部），其他步驟與PB-S 一致；PB-S(2)在發生內容替換時直接替換掉整個鏈表尾部的內容（即冷門區尾部內容），其他步驟與PB-S 一致。實驗結果表明，在不同的Zipf 分布參數、不同的緩存空間比率下，PB-S(2)比PB-S(1)的緩存命中率略高，網絡平均時延略低，這代表選擇熱度低的內容進行替換帶來了更大的好處。而PB-S 在兩個步驟都使用了熱度信息，給網絡性能帶來了更明顯的提升。

2）內容排名與內容替換比率的關系

為了驗證所提方法能否持久緩存熱門的內容，分析不同排名內容的替換比率。內容的排名越高，則更為熱門，具有更高的熱度。如果一個內容具有較低的替換比率，則意味著這個內容具有更高的概率持續留在緩存中。因此可以分析采用不同的緩存替換方法，對應的內容排名和內容替換比率的關系。理想的緩存替換方法，內容的排名越高，其替換比率應該越低。在仿真實驗中，將內容Zipf 分布參數α固定為0.7，將緩存空間比率固定為0.5，分析不同緩存替換方法下，內容的排名與內容替換比率的關系。在內容集里，將內容根據熱度降序排列，得到內容的排名，排名為1 的內容熱度最高。統計了不同緩存替換方法下，排名前1 000 內容的替換比率，最終得到如圖4 所示的仿真結果。

圖4 內容的排名與內容替換比率的關系

從圖4 可以看出，在PB-S 中，排名處于前列的內容具有明顯更低的內容替換比率，并且隨著內容的排名增加，其替換比率的增加幅度逐漸減小，可以看作是沿橫坐標軸鏡像的Zipf 分布曲線。因此PB-S較好地實現了將流行的內容保存在緩存中，并且將不流行的內容替換掉。相比之下，在LRU、FIFO 和RR 中，內容替換比率隨著內容排名的改變的變化不大。在LRU 中，對于最為流行的內容，其內容替換比率有些微的下降，但未與排名靠后的內容的替換比率有明顯的區分，可能是因為LRU 會默認將新緩存的內容插入在鏈表首部，增大了流行的內容移動到鏈表尾部并被替換掉的概率。

3）不同緩存替換方法的性能對比

分別進行兩組參數設置：首先將內容的緩存空間比率固定為0.5，改變Zipf 分布參數α；之后將內容的Zipf 分布參數α固定為0.7，改變緩存空間比率，最終得到的仿真結果如圖5 所示。其中，圖5(a)表示緩存命中率隨α變化的關系，圖5(b)表示網絡平均時延隨α變化的關系。圖5(c)表示緩存命中率隨緩存空間比率變化的關系，圖5(d)表示網絡平均時延隨緩存空間比率變化的關系。

圖5 不同緩存替換方法的網絡性能對比實驗結果

根據圖5(a)，α增加時，所有的緩存替換方法都能得到更高的緩存命中率，這是因為請求都集中于少數流行的內容，而不同的替換方法都能夠在一定程度內保留這些內容在緩存中。四種替換方法的變化趨勢比較相似，而相對于其他方法，PB-S 在不同的α值下都保持了更高的緩存命中率，體現了PB-S的有效性。

通過圖5(b)可以發現，隨著α增加，不同替換方法的網絡平均時延都得到了下降。PB-S 的平均時延明顯低于其他緩存替換方法，因為PB-S 通過分區的方式，可以更好地避免流行的內容被不流行的內容替換，持久地將流行內容保留在緩存中。三種對比方法的平均時延比較接近，其中LRU 在α更大時的優勢更明顯。

從圖5(c)可以得到，當緩存空間比率增大時，所有的緩存替換方法的緩存命中率都得到了提升。這是因為緩存路由器配備了更大的緩存空間，因而緩存了更多的內容，最終使得更多請求在緩存內部被命中。而對比不同的緩存替換方法，PB-S 都具有更高的緩存命中率，且比其他緩存替換方法高0.1 左右。從這里能夠看出來，基于內容熱度的分區緩存替換方法對不同區間的內容執行不同的操作，能夠更好地保存流行的內容，并替換掉不流行的內容。LRU 與隨機替換（RR）的效果類似，并略好于FIFO，這是隨著更多新內容被緩存，之前流行的內容即使被多次命中，也必然隨著入隊的順序出隊。

根據圖5(d)的結果，當緩存空間比率增大時，所有緩存替換方法的平均時延都得到了下降。PB-S相對于其他方法，保持了約15 ms 的優勢，這意味著用戶可以從更近的緩存路由器中獲取內容。當緩存空間更大時，RR 能夠帶來比LRU 更低的平均時延。

通過分析比較不同的Zipf 分布參數下以及不同的緩存空間比率各緩存替換方法的性能可以發現，PB-S 能帶來更高的緩存命中率和更低的網絡平均時延。這主要是由于PB-S 通過分區的方式，將新緩存內容的索引根據熱度放置在不同分區，而不是整個鏈表的首部，能避免不流行的內容將流行的內容擠出熱門區，造成不流行的內容被緩存而流行的內容被替換。此外，PB-S 選擇熱度低的內容進行替換，進一步保障了熱度高的內容留在緩存中。綜上所述，PB-S 作為一個輕量級的緩存替換方法，適合部署于ICN 實際場景中。

4 結論

該文針對ICN 網內緩存場景中的緩存替換問題，首先對比分析幾種ICN 緩存替換方法的優缺點，根據LRU 存在的問題，提出了一種基于內容熱度的分區緩存替換方法。通過仿真實驗，分析了利用熱度信息進行緩存替換的有效性，并將提出的緩存替換方法與LRU、FIFO、RR 進行了對比。實驗結果表明，該文所提出的緩存替換方法能夠緩存流行的內容，替換不流行的內容。在不同的內容熱度分布、緩存空間配置的場景下，該文所提出的緩存替換方法都具有更高的緩存命中率和更低的內容獲取時延。在之后的工作中，會進一步分析更多維度的信息，如網絡拓撲信息[15-19]、轉發流量信息等，應用于緩存替換方法中。