基于內容遷移的ICN 緩存負載均衡機制

李 惟，孫 鵬，韓 銳

（1.中國科學院聲學研究所國家網絡新媒體工程技術研究中心，北京 100190；2.中國科學院大學，北京 100049）

信息中心網絡（ICN）是未來網絡研究的主要方向。目前的互聯網架構以主機為中心，依賴發送者驅動的端到端通信模式[1]?；ヂ摼W技術和應用不斷發展，互聯網用戶數量和多媒體應用流量成指數級增長，用戶對網絡的主要需求已經轉變為對海量內容的訪問。ICN 采用獨立于位置的內容命名、請求-響應模型和網內緩存來實現有效和可靠的內容分發[2]，很好地應對這一轉變。常見的ICN 網絡架構有DONA[3]、NDN[4]、PURSUIT[5]、NetInf[6]。

網內緩存是ICN的重要內容，ICN 路由器通過配置額外的存儲器來緩存途經內容，從而可以響應用戶的請求，這大大降低了內容訪問延遲和帶寬利用。然而由于緩存節點的緩存空間有限，高效地利用緩存資源是提高緩存網絡系統性能的主要研究方向。LCE（Leave Copy Everywhere）是許多ICN 網絡架構的默認緩存策略，但內容返回時沿途所有緩存節點都會緩存該內容，這種激進的緩存方式會造成大量的緩存冗余、節點緩存替換頻繁、緩存性能較低。LCD（Leave Copy Down）試圖解決LCE的緩存冗余問題[7]，LCD 在命中節點的下游節點緩存該內容，潛在地考慮了內容的流行度，隨著請求次數的增加被復制到用戶邊緣，但如果用戶頻繁請求流行度較高的內容，會出現緩存節點服務負載過重的性能瓶頸，網絡局部陷入擁塞。文獻[8]提出了基于節點中心性的緩存放置算法，內容被緩存在返回路徑上中心性最大的節點上，但是這種機制會造成節點間負載分布的不均衡，內容緩存和響應集中在中心性大的節點上，而其他緩存節點的緩存資源沒有得到充分利用。

針對上述緩存機制造成負載分布不均、從而大大降低了網絡資源利用率的問題，文中提出了基于內容遷移的負載均衡機制。首先將節點負載區分為服務負載和緩存負載，針對兩種情況，分別設計了負載的衡量方式以及負載均衡機制的觸發條件，其次設計了遷移內容和遷移節點選擇機制，實現高效的內容遷移，充分利用網絡緩存資源實現負載均衡。

1 相關研究

文獻[9]在傳統網絡負載均衡研究的基礎上，從負載均衡決策指標、功能位置等分析了負載均衡在ICN 中的挑戰。當負載均衡機制實現在網絡全局控制器中時，主要分為基于請求的負載均衡和基于隊列的負載均衡兩種類型?；谡埱蟮呢撦d均衡試圖將請求分配給最適合節點，如輪詢調度算法[10]和Scheduling-based 算法[11-12]，基于隊列的負載均衡試圖將作業從一個隊列遷移到另一個隊列來平衡副本的作業隊列，如啟發式負載均衡[13]。兩種類型都依賴于服務能力、副本占用率等指標作出決策。

當負載均衡機制實現在緩存節點中，文獻[14]提出了一種基于蟻群分工啟發的ICN 負載均衡機制，定期預測路由器和鏈路負載并設計了蟻后表、雄蟻和工蟻包，通過分工協作將部分待處理數據包遷移至輕載節點或鏈路。文獻[15]針對現有緩存機制造成緩存負載分布不均的情況，將內容遷移與緩存策略結合，提出基于內容遷移的協作緩存機制，當緩存壓力過大時選擇合適的鄰居節點進行緩存內容的轉移，實現負載分擔。文獻[16]面向邊緣節點的緩存冗余問題，提出一種基于內容遷移的路徑內外協作緩存機制，該機制戰略性放置一路徑外緩存節點支持額外的緩存級別，用來緩存路徑內緩存節點卸載的內容。

2 負載均衡機制

文中設計的負載均衡機制流程如圖1 所示。

圖1 負載均衡機制流程

負載均衡機制分為以下兩個過程：

1）緩存節點周期性監控?t時間內的負載狀況，并根據鄰居狀態表判斷節點是否重載。

2）重載的節點觸發負載均衡機制，從緩存內容中選擇遷移內容，從鄰居狀態表中選擇遷移節點進行內容遷移。

2.1 負載監控和負載均衡機制觸發

在該文負載均衡機制中，節點的負載被區分為服務負載和緩存負載。服務負載過重表示由于用戶的請求不均衡，造成節點間服務請求的負載不均衡的情況，應當考慮利用網絡內其他節點的服務能力，遷移相應內容均衡過重節點的服務請求。緩存負載表示由于緩存策略的缺陷，內容的放置集中在某些重要的節點上，發生頻繁的緩存替換，應當考慮利用網絡內其他節點的緩存資源，遷移相應內容充分利用網絡資源提高網絡性能。

服務負載和緩存負載對應的統計指標分別為緩存利用率和緩存替換率。首先引入緩存利用率，記為，將其定義為單位采樣時間內節點v中命中內容的大小與總緩存容量大小的比值，作為服務負載的評價指標。緩存替換率記為，將其定義為單位采樣時間內節點v替換內容大小與總緩存容量大小的比值，作為緩存負載的評價指標。

為每個緩存節點增添一張鄰居狀態表，鄰居狀態表的作用是記錄緩存節點兩跳半徑內鄰居節點的負載情況，通過這些記錄可以計算局部的平均負載，鄰居狀態表的結構如表1 所示。

表1 鄰居狀態表結構

定義鄰居節點集合為R={Ri,i=1,2,…n}，鄰居節點周期性地向緩存節點報告負載情況，緩存節點會更新鄰居狀態表。根據鄰居狀態表計算局部的平均緩存利用率和緩存替換率。

采用閾值觸發機制，當緩存節點的負載情況超過閾值時，觸發相應的負載均衡機制。將服務負載閾值和緩存負載閾值分別設置為局部負載平均值UAaverage和RPaverage，對于緩存節點v，當UA(v)>UAaverage或RP(v)>RPaverage時，節點觸發負載均衡機制，選擇相應的緩存內容和鄰居節點進行內容遷移。

2.2 遷移內容和遷移節點選擇

為了實現有效的負載均衡，需要選擇合適的內容進行遷移。根據兩種重載的情況，選擇遷移內容時需要考量內容的流行度。當服務負載過重時，緩存節點提供過多的請求服務，節點性能下降，應當選擇流行的內容進行遷移，實現熱門內容在鄰域的擴散，均衡節點的服務請求；當緩存負載過重時，緩存節點內容替換頻率極高，內容可用性下降，應當將流行內容保留在自己的緩存中，選擇較冷門的內容遷移到鄰居節點，充分利用緩存資源。

為了實現上述思想，對緩存內容采用二級LRU隊列進行管理，兼顧緩存內容的請求頻率和新近性，如圖2 所示。

圖2 二級LRU隊

將緩存空間分成二段LRU，當新內容被緩存時，它被置于二級LRU的頭部，命中內容被提升到一級LRU的頭部，一級LRU 替換的內容被降級到二級LRU的頭部，二級LRU 替換的內容被刪除。當服務負載過重時，從一級LRU 頭部位置選擇遷移內容，而當緩存負載過重時，從二級LRU 尾部位置選擇遷移內容。

當緩存節點服務負載過重時，內容遷移的主要目的是利用鄰居節點的服務能力均衡節點的服務請求，分散網絡局部擁塞的流量；當緩存負載過重時，內容遷移的主要目的之一是利用鄰居節點的緩存內容來延長內容在網絡中緩存的時間。為了選擇合適的遷移節點，根據鄰居狀態表記錄的信息設計遷移節點選擇機制。

給定鄰居節點集合R={Ri,i=1,2,…,n}，根據緩存替換率RP(i)是否為0，將R劃分為RRP=0={Ri,i=0,…,m}和RRP>0={Ri,i=1,…,(n-m)} 兩個集合。服務負載過重的情況下，若存在RRP=0，從RRP=0中選擇緩存利用率最低的節點作為遷移節點，若不存在RRP=0，從RRP>0中選擇緩存利用率最低的節點作為遷移節點；緩存負載過重的情況下，若存在RRP=0，從RRP=0中選擇緩存利用率最低的節點作為緩存節點，若不存在RRP=0，從RRP>0中選擇緩存替換率最低的節點作為遷移節點。具體過程如算法1所示。

算法1：遷移節點選擇

緩存替換率為0的鄰居節點集合：RRP=0={Ri,i=0,…m}

緩存替換率大于0的鄰居節點集合：RRP>0={Ri,i=1,…(n-m)}

遷移節點：j

3 性能分析

3.1 實驗環境

為了驗證負載均衡機制的緩存性能，基于Icarus緩存模擬器展開仿真實驗。選擇LCE、CL4M[8]和為兩種緩存機制增加負載均衡機制的LCE_2、CL4M_2進行對比，對于LCE和CL4M 采用LRU 作為緩存替換策略。實驗中的仿真拓撲選擇GEANT（歐洲學術網絡），其中節點度為1的節點被設置為客戶端，結構如圖3 所示。

圖3 實驗拓撲結構

實驗參數設置如表2 所示。內容總數為3×105，正式測試開始前用3×105的請求進行環境預熱，用于測試的請求數為6×105，用戶請求到達服從泊松分布，請求速率為10 次/s。每個節點的緩存大小相同，緩存大小比率是網絡緩存大小和內容總數的占比，其默認值為0.01，變化范圍為[0.001，0.002，0.004，0.01]。內容請求服從Zipf 流行度分布，參數α默認值為0.6，變化范圍為[0.2，0.4，0.6，0.8，1.0]。主要采用的性能評價指標為：1）緩存命中率：用戶請求被緩存響應的概率。2）緩存負載分布：各節點被選中為緩存節點的次數[16]。

表2 參數設置

3.2 實驗結果

3.2.1 緩存命中率

該小節首先研究4 種緩存機制下不同網絡參數對緩存命中率的影響。由圖4（a）所示，隨著Zipf 參數的增加，各種緩存機制的緩存命中率也得到提高。更高的α表明用戶對流行內容請求的偏向性更高，各機制下緩存放置策略和緩存替換策略均傾向于流行內容的緩存，內容熱度差異越大，緩存的效果越明顯。其中，增加負載均衡機制的LCE_2和CL4M_2 在不同Zipf 參數下的緩存命中率均高于對應的LCE和CL4M。由圖4（b）可知，隨著緩存容量的增加，緩存節點可以緩存更多的內容，各種緩存機制的緩存命中率隨之增加。其中，由于提出的負載均衡機制通過內容遷移，有效地利用了鄰居節點的緩存資源，提高了緩存資源的利用率，LCE_2和CL4M_在不同緩存大小比率下的緩存命中率均高于對應的LCE和CL4M。

圖4 不同參數對緩存命中率的影響

3.2.2 緩存負載分布

該小節研究4 種緩存機制下緩存負載分布的情況，通過統計節點的累積緩存數量來分析負載均衡機制對負載分布均衡性的影響。在該文負載均衡機制中，緩存節點監控自身負載狀況，如果高于節點鄰域的平均情況，選擇內容進行遷移。由圖5（a）和圖5（c）所示，LCE和CL4M 均存在負載分布不均衡的情況，CL4M選擇傳輸路徑上中心性最大的節點來緩存內容，負載分布不均衡的情況更為明顯。如圖5（b）和圖5（d）所示，采用負載均衡機制后，LCE_2和CL4M_的負載分布更為均勻，并有效地利用了所有節點的緩存資源。

圖5 不同機制下緩存負載分布

4 結論

針對現有ICN緩存機制會造成節點間負載分布不均衡的問題，提出了基于內容遷移的負載均衡機制。該機制對節點的服務負載和緩存負載進行監控，并維護節點鄰居的負載狀態，當負載過重時，根據緩存利用率、緩存替換率等信息選擇適合的鄰居節點進行內容遷移，充分利用緩存資源實現負載均衡。仿真結果顯示，采用負載機制在緩存命中率、網絡資源利用方面有良好的表現。在未來的工作中，將驗證其在真實網絡環境下的性能并優化相關算法、完善研究內容。