基于內(nèi)容遷移的ICN 緩存負載均衡機制

李 惟，孫 鵬，韓 銳

（1.中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190；2.中國科學(xué)院大學(xué)，北京 100049）

信息中心網(wǎng)絡(luò)（ICN）是未來網(wǎng)絡(luò)研究的主要方向。目前的互聯(lián)網(wǎng)架構(gòu)以主機為中心，依賴發(fā)送者驅(qū)動的端到端通信模式[1]。互聯(lián)網(wǎng)技術(shù)和應(yīng)用不斷發(fā)展，互聯(lián)網(wǎng)用戶數(shù)量和多媒體應(yīng)用流量成指數(shù)級增長，用戶對網(wǎng)絡(luò)的主要需求已經(jīng)轉(zhuǎn)變?yōu)閷Ａ績?nèi)容的訪問。ICN 采用獨立于位置的內(nèi)容命名、請求-響應(yīng)模型和網(wǎng)內(nèi)緩存來實現(xiàn)有效和可靠的內(nèi)容分發(fā)[2]，很好地應(yīng)對這一轉(zhuǎn)變。常見的ICN 網(wǎng)絡(luò)架構(gòu)有DONA[3]、NDN[4]、PURSUIT[5]、NetInf[6]。

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

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

1 相關(guān)研究

文獻[9]在傳統(tǒng)網(wǎng)絡(luò)負載均衡研究的基礎(chǔ)上，從負載均衡決策指標(biāo)、功能位置等分析了負載均衡在ICN 中的挑戰(zhàn)。當(dāng)負載均衡機制實現(xiàn)在網(wǎng)絡(luò)全局控制器中時，主要分為基于請求的負載均衡和基于隊列的負載均衡兩種類型。基于請求的負載均衡試圖將請求分配給最適合節(jié)點，如輪詢調(diào)度算法[10]和Scheduling-based 算法[11-12]，基于隊列的負載均衡試圖將作業(yè)從一個隊列遷移到另一個隊列來平衡副本的作業(yè)隊列，如啟發(fā)式負載均衡[13]。兩種類型都依賴于服務(wù)能力、副本占用率等指標(biāo)作出決策。

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

2 負載均衡機制

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

圖1 負載均衡機制流程

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

1）緩存節(jié)點周期性監(jiān)控?t時間內(nèi)的負載狀況，并根據(jù)鄰居狀態(tài)表判斷節(jié)點是否重載。

2）重載的節(jié)點觸發(fā)負載均衡機制，從緩存內(nèi)容中選擇遷移內(nèi)容，從鄰居狀態(tài)表中選擇遷移節(jié)點進行內(nèi)容遷移。

2.1 負載監(jiān)控和負載均衡機制觸發(fā)

在該文負載均衡機制中，節(jié)點的負載被區(qū)分為服務(wù)負載和緩存負載。服務(wù)負載過重表示由于用戶的請求不均衡，造成節(jié)點間服務(wù)請求的負載不均衡的情況，應(yīng)當(dāng)考慮利用網(wǎng)絡(luò)內(nèi)其他節(jié)點的服務(wù)能力，遷移相應(yīng)內(nèi)容均衡過重節(jié)點的服務(wù)請求。緩存負載表示由于緩存策略的缺陷，內(nèi)容的放置集中在某些重要的節(jié)點上，發(fā)生頻繁的緩存替換，應(yīng)當(dāng)考慮利用網(wǎng)絡(luò)內(nèi)其他節(jié)點的緩存資源，遷移相應(yīng)內(nèi)容充分利用網(wǎng)絡(luò)資源提高網(wǎng)絡(luò)性能。

服務(wù)負載和緩存負載對應(yīng)的統(tǒng)計指標(biāo)分別為緩存利用率和緩存替換率。首先引入緩存利用率，記為，將其定義為單位采樣時間內(nèi)節(jié)點v中命中內(nèi)容的大小與總緩存容量大小的比值，作為服務(wù)負載的評價指標(biāo)。緩存替換率記為，將其定義為單位采樣時間內(nèi)節(jié)點v替換內(nèi)容大小與總緩存容量大小的比值，作為緩存負載的評價指標(biāo)。

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

表1 鄰居狀態(tài)表結(jié)構(gòu)

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

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

2.2 遷移內(nèi)容和遷移節(jié)點選擇

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

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

圖2 二級LRU隊

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

當(dāng)緩存節(jié)點服務(wù)負載過重時，內(nèi)容遷移的主要目的是利用鄰居節(jié)點的服務(wù)能力均衡節(jié)點的服務(wù)請求，分散網(wǎng)絡(luò)局部擁塞的流量；當(dāng)緩存負載過重時，內(nèi)容遷移的主要目的之一是利用鄰居節(jié)點的緩存內(nèi)容來延長內(nèi)容在網(wǎng)絡(luò)中緩存的時間。為了選擇合適的遷移節(jié)點，根據(jù)鄰居狀態(tài)表記錄的信息設(shè)計遷移節(jié)點選擇機制。

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

算法1：遷移節(jié)點選擇

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

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

遷移節(jié)點：j

3 性能分析

3.1 實驗環(huán)境

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

圖3 實驗拓撲結(jié)構(gòu)

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

表2 參數(shù)設(shè)置

3.2 實驗結(jié)果

3.2.1 緩存命中率

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

圖4 不同參數(shù)對緩存命中率的影響

3.2.2 緩存負載分布

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

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

4 結(jié)論

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