李 惟，孫 鵬，韓 銳

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

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

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

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

1 相關(guān)研究

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

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

2 負(fù)載均衡機(jī)制

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

圖1 負(fù)載均衡機(jī)制流程

負(fù)載均衡機(jī)制分為以下兩個(gè)過程：

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

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

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

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

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

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

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

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

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

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

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

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

圖2 二級(jí)LRU隊(duì)

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

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

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

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

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

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

遷移節(jié)點(diǎn)：j

3 性能分析

3.1 實(shí)驗(yàn)環(huán)境

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

圖3 實(shí)驗(yàn)拓?fù)浣Y(jié)構(gòu)

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

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

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 緩存命中率

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

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

3.2.2 緩存負(fù)載分布

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

圖5 不同機(jī)制下緩存負(fù)載分布

4 結(jié)論

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