基于負(fù)載狀態(tài)的ICN 緩存替換算法研究

曾 理，倪 宏，韓 銳

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

泛在化緩存[1]決定了ICN（Information Centric Networking，信息中心網(wǎng)絡(luò)）的性能優(yōu)勢(shì)，其可有效減少冗余數(shù)據(jù)的傳輸，緩解網(wǎng)絡(luò)帶寬的壓力，降低傳輸時(shí)延[2]。緩存替換在ICN 路由器內(nèi)部時(shí)刻都在發(fā)生，每一次替換過(guò)程都會(huì)對(duì)網(wǎng)絡(luò)性能產(chǎn)生影響[3]。目前，ICN 緩存替換算法的研究集中在對(duì)內(nèi)容未來(lái)流行度的預(yù)測(cè)[4-6]，或是根據(jù)拓?fù)湫畔⒑袜従庸?jié)點(diǎn)緩存信息來(lái)優(yōu)化緩存空間[7-9]，但這些研究在帶來(lái)額外計(jì)算開銷或控制開銷的同時(shí)，相較于傳統(tǒng)LRU（Least Recently Used,最近最少使用）替換算法，其性能并未得到明顯改善[10]。

隨著節(jié)點(diǎn)緩存容量和計(jì)算能力的限制被打破[11]，不同類型的流量競(jìng)爭(zhēng)有限的帶寬資源已成為ICN 路由器發(fā)生擁塞的主要原因之一[12]。針對(duì)這一問(wèn)題，為了避免節(jié)點(diǎn)因高緩存命中率引發(fā)嚴(yán)重帶寬競(jìng)爭(zhēng)，該文提出一種基于節(jié)點(diǎn)負(fù)載狀態(tài)的緩存替換算法，監(jiān)測(cè)節(jié)點(diǎn)是否長(zhǎng)期處于帶寬競(jìng)爭(zhēng)狀態(tài)，并采用自適應(yīng)替換窗口將一些較為流行的內(nèi)容主動(dòng)替換，減少帶寬競(jìng)爭(zhēng)的發(fā)生頻率和持續(xù)時(shí)間，降低節(jié)點(diǎn)丟包率。

1 ICN路由器的帶寬競(jìng)爭(zhēng)

文獻(xiàn)[12]認(rèn)為ICN 中擁塞發(fā)生的原因除緩沖區(qū)溢出外，還可以進(jìn)一步歸納為過(guò)度的帶寬資源競(jìng)爭(zhēng)。具體來(lái)說(shuō)，假設(shè)請(qǐng)求報(bào)文以速率γ抵達(dá)路由器，τc是緩存服務(wù)所需的吞吐量(γ≤τc)，而對(duì)于ICN 路由器的實(shí)時(shí)轉(zhuǎn)發(fā)吞吐量τf，某時(shí)刻很有可能出現(xiàn)來(lái)自外部流量的轉(zhuǎn)發(fā)吞吐量與來(lái)自內(nèi)部流量的緩存服務(wù)吞吐量之和大于端口帶寬B，從而造成擁塞丟包，即τf+τc＞B。ICN 中每個(gè)數(shù)據(jù)報(bào)文都需要通過(guò)一個(gè)請(qǐng)求報(bào)文“拉”給用戶[13]，因此可以通過(guò)來(lái)預(yù)測(cè)帶寬競(jìng)爭(zhēng)的發(fā)生（是數(shù)據(jù)報(bào)文的平均尺寸）。

2 算法設(shè)計(jì)與建模

2.1 算法設(shè)計(jì)

如果ICN 路由器在一段時(shí)間內(nèi)持續(xù)處于帶寬競(jìng)爭(zhēng)狀態(tài)，則可以認(rèn)為節(jié)點(diǎn)應(yīng)該主動(dòng)替換一些流行度較高的內(nèi)容，從而減少帶寬競(jìng)爭(zhēng)發(fā)生的頻率和持續(xù)的時(shí)間。

節(jié)點(diǎn)帶寬競(jìng)爭(zhēng)狀態(tài)隨網(wǎng)絡(luò)波動(dòng)而動(dòng)態(tài)變化，為了準(zhǔn)確加以檢測(cè)，算法采用時(shí)間間隔為T的開關(guān)信號(hào)對(duì)其進(jìn)行采樣。如圖1 所示，如果采樣時(shí)刻節(jié)點(diǎn)帶寬競(jìng)爭(zhēng)發(fā)生且請(qǐng)求到達(dá)速率高于閾值，則用1表示；如果采樣時(shí)路由器尚有空閑的帶寬，則用0 表示。由于固定時(shí)間窗偏移的方法容易忽視抽樣信號(hào)前后窗口的相關(guān)性而造成誤判，算法采用長(zhǎng)度為W的滑動(dòng)時(shí)間窗口（如圖中W1,W2,…,Wn）來(lái)跟蹤統(tǒng)計(jì)離散時(shí)間下的節(jié)點(diǎn)狀態(tài)，W的值根據(jù)RTT（Round-Trip Time，往返時(shí)延）、路由器排隊(duì)時(shí)延來(lái)決定。如果時(shí)間窗內(nèi)帶寬競(jìng)爭(zhēng)出現(xiàn)次數(shù)大于，算法則判斷節(jié)點(diǎn)處于持續(xù)的帶寬競(jìng)爭(zhēng)?；瑒?dòng)窗口監(jiān)測(cè)考慮了請(qǐng)求報(bào)文之間的相關(guān)性，能夠做出更精準(zhǔn)的判斷，但代價(jià)是增加了管理開銷。

圖1 基于滑動(dòng)窗口抽樣檢測(cè)帶寬競(jìng)爭(zhēng)

對(duì)于內(nèi)容流行度的評(píng)估，在最新的研究中，無(wú)論是通過(guò)多元線性回歸方法[14]，還是通過(guò)數(shù)據(jù)塊間的相關(guān)性[15]對(duì)內(nèi)容未來(lái)請(qǐng)求規(guī)律進(jìn)行預(yù)測(cè)，文獻(xiàn)[10]都已經(jīng)證明基于流行度的替換算法相比起LRU 替換算法的性能提升并不明顯。因此所提算法仍使用LRU隊(duì)列來(lái)篩選流行內(nèi)容。

當(dāng)檢測(cè)到帶寬競(jìng)爭(zhēng)持續(xù)發(fā)生時(shí)，算法通過(guò)變長(zhǎng)窗口替換隊(duì)列首部的熱門數(shù)據(jù)，這在一定程度上解決了LRU 時(shí)間新近性的問(wèn)題?？紤]到現(xiàn)實(shí)路由器中有多個(gè)端口，為了更精準(zhǔn)地替換導(dǎo)致節(jié)點(diǎn)擁塞的數(shù)據(jù)塊，算法將記錄每個(gè)數(shù)據(jù)塊被請(qǐng)求次數(shù)和請(qǐng)求報(bào)文到達(dá)端口的映射，當(dāng)某個(gè)端口Bp被檢測(cè)到帶寬競(jìng)爭(zhēng)持續(xù)發(fā)生，變長(zhǎng)窗口僅會(huì)替換請(qǐng)求曾從該端口抵達(dá)的數(shù)據(jù)。如圖2 所示，若端口1 持續(xù)發(fā)生帶寬競(jìng)爭(zhēng)，LRU 隊(duì)列上僅第2、3、5、6 的數(shù)據(jù)被替換，第1 和4數(shù)據(jù)塊的請(qǐng)求因未曾抵達(dá)過(guò)端口1 而被保留。假設(shè)替換窗口長(zhǎng)度用L表示，當(dāng)檢測(cè)到帶寬競(jìng)爭(zhēng)發(fā)生時(shí)，替換窗口增加固定值a。當(dāng)帶寬競(jìng)爭(zhēng)狀態(tài)持續(xù)了Q個(gè)檢測(cè)窗口，替換窗口將會(huì)成倍增長(zhǎng)。a與Q的取值由路由器緩存容量（LRU 隊(duì)列長(zhǎng)度）來(lái)決定。

圖2 可變窗口選擇熱門數(shù)據(jù)

2.2 替換窗口長(zhǎng)度變化規(guī)則建模

基于帶寬競(jìng)爭(zhēng)監(jiān)測(cè)的替換算法中，替換窗口長(zhǎng)度變化的行為可以用一個(gè)離散馬爾科夫過(guò)程來(lái)建模。

如圖3 所示，S0代表窗口長(zhǎng)度為0 的初始狀態(tài)，此時(shí)不需要主動(dòng)對(duì)流行內(nèi)容進(jìn)行替換；當(dāng)監(jiān)測(cè)到帶寬競(jìng)爭(zhēng)持續(xù)發(fā)生時(shí)，替換窗口長(zhǎng)度將會(huì)增加固定值a并處于S1態(tài)；S2態(tài)代表帶寬競(jìng)爭(zhēng)狀態(tài)持續(xù)了Q個(gè)時(shí)間窗口以上，窗口長(zhǎng)度將會(huì)翻倍。因此可以看出，帶寬競(jìng)爭(zhēng)狀態(tài)持續(xù)時(shí)間對(duì)于各狀態(tài)之間的轉(zhuǎn)換起著至關(guān)重要的作用。為了清晰地表達(dá)轉(zhuǎn)移概率，首先定義函數(shù)f如式（1）所示：

圖3 可變窗口的馬爾科夫建模

因此，可以得到如式（2）的狀態(tài)概率轉(zhuǎn)移矩陣：

其中，p(n)是n時(shí)刻路由器抽樣檢測(cè)到帶寬持續(xù)競(jìng)爭(zhēng)的概率。

替換窗口變化過(guò)程可通過(guò)式（3）來(lái)建模：

n時(shí)刻LRU 隊(duì)列的長(zhǎng)度可以表示為：

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證該文提出的緩存替換算法的性能，仿真實(shí)驗(yàn)采用Icarus 模擬器在GEANT 網(wǎng)絡(luò)拓?fù)湎屡c另外兩種傳統(tǒng)的替換算法LRU、FIFO（First Input First Output，先入先出）進(jìn)行對(duì)比實(shí)驗(yàn)。Icarus 是一個(gè)輕量級(jí)的仿真軟件，可以允許用戶輕易地測(cè)試定制的ICN 緩存和路由策略。GEANT 是面向研究和教育團(tuán)體的一個(gè)泛歐洲數(shù)據(jù)網(wǎng)絡(luò)，總共包含40 個(gè)節(jié)點(diǎn)，其中8 個(gè)邊緣請(qǐng)求者，13 個(gè)內(nèi)容提供者，19 個(gè)ICN 路由器。仿真實(shí)驗(yàn)的各項(xiàng)設(shè)置參數(shù)如下：1）請(qǐng)求到達(dá)速率符合泊松分布；2）內(nèi)容流行度符合α=0.8 的ZiPf分布；3）內(nèi)容數(shù)據(jù)塊總數(shù)量為1×105個(gè)；4）預(yù)熱ICN緩存網(wǎng)絡(luò)的請(qǐng)求數(shù)目為1×105個(gè)；5）實(shí)際用于測(cè)量統(tǒng)計(jì)的請(qǐng)求數(shù)目為2×105個(gè)；6）請(qǐng)求者發(fā)送請(qǐng)求的速率為80～100 個(gè)/s；7）節(jié)點(diǎn)采用的緩存策略：LCE（Leave Copy Everywhere，處處緩存）和一種基于介數(shù)中心性的緩存策略[16]；8）窗口持續(xù)閾值n=5。

假設(shè)路由器每個(gè)端口的處理能力為每秒處理150 個(gè)數(shù)據(jù)塊，并且路由器為每個(gè)端口維護(hù)一條轉(zhuǎn)發(fā)隊(duì)列queuef和緩存響應(yīng)隊(duì)列queuec，當(dāng)兩條隊(duì)列排隊(duì)的待處理的數(shù)據(jù)塊數(shù)目超過(guò)端口處理能力（帶寬）時(shí)，則視為帶寬競(jìng)爭(zhēng)發(fā)生。抽樣間隔T為0.2 s，監(jiān)控窗口時(shí)長(zhǎng)為2 s，當(dāng)窗口中帶寬競(jìng)爭(zhēng)次數(shù)超過(guò)6 次時(shí)，視為一次持續(xù)帶寬競(jìng)爭(zhēng)。

ICN路由器緩存容量S作為變量參與實(shí)驗(yàn)對(duì)比，其取值為500、1 000、1 500、2 000、2 500、3 000、3 500、4 000，其中替換窗口每次增加的固定值a為0.002×S。實(shí)驗(yàn)中，ICN 傳輸協(xié)議將會(huì)在檢測(cè)到用戶請(qǐng)求超時(shí)后重新發(fā)出請(qǐng)求。同一場(chǎng)景下的各個(gè)實(shí)驗(yàn)獨(dú)立運(yùn)行5次，并以95%的置信區(qū)間對(duì)結(jié)果進(jìn)行分析。

3.2 仿真結(jié)果分析

圖4 顯示了不同替換算法在部署了不同緩存策略的緩存系統(tǒng)中的平均緩存命中率。很明顯，比起基于介數(shù)中心性的緩存策略，LCE 能幫助系統(tǒng)獲得較高的緩存命中率。對(duì)于緩存替換算法，由于FIFO算法完全不考慮內(nèi)容流行度，LRU 能獲得較好的緩存命中率。在部署了基于介數(shù)中心性策略的緩存系統(tǒng)中，LRU 的性能表現(xiàn)最差，甚至與FIFO 接近，這是由于部分介數(shù)較高的節(jié)點(diǎn)承擔(dān)了大量轉(zhuǎn)發(fā)任務(wù)的同時(shí)，較高的緩存命中率使得請(qǐng)求并發(fā)響應(yīng)增多，從而導(dǎo)致帶寬競(jìng)爭(zhēng)狀態(tài)持續(xù)存在，丟包率上升，降低了整個(gè)系統(tǒng)的平均命中率。

圖4 不同緩存策略系統(tǒng)采用不同替換算法的緩存命中率對(duì)比

另外，隨著節(jié)點(diǎn)緩存容量的提高，采用LRU 算法的緩存命中率先是急劇提升，然后增速降緩。這說(shuō)明單純提高節(jié)點(diǎn)緩存容量對(duì)整體網(wǎng)絡(luò)的性能改善有限。從圖中可以看出，與LRU 相比，該文的優(yōu)化算法有明顯的性能改善，在采用基于介數(shù)中心性策略的緩存系統(tǒng)中提升最明顯，緩存命中率最高能夠提高14.3%。這是因?yàn)樗崽鎿Q算法使介數(shù)較高的“中心節(jié)點(diǎn)”減少了帶寬競(jìng)爭(zhēng)持續(xù)時(shí)間，從而減少了丟包率。

為了進(jìn)一步分析帶寬競(jìng)爭(zhēng)對(duì)網(wǎng)絡(luò)性能的影響，實(shí)驗(yàn)觀察了不同緩存系統(tǒng)中介數(shù)最高節(jié)點(diǎn)的丟包率（S=3 000）以及系統(tǒng)的瓶頸重傳概率，結(jié)果如圖5、6 所示；平均重傳概率是用戶發(fā)出的請(qǐng)求總數(shù)（包含重傳請(qǐng)求）與測(cè)試請(qǐng)求數(shù)（200 000）的比值，其能在一定程度描述網(wǎng)絡(luò)的擁塞情況。結(jié)果顯示無(wú)論部署什么緩存策略，介數(shù)最高的路由器丟包率都要高于系統(tǒng)的平均重傳概率，這證明在考慮帶寬資源受限的約束下，“中心”路由器是網(wǎng)絡(luò)性能的瓶頸。

圖5 不同緩存策略系統(tǒng)中介數(shù)最高節(jié)點(diǎn)采用不同緩存替換算法的丟包率對(duì)比

而該文的替換算法極大改善了部署基于介數(shù)中心性策略的緩存系統(tǒng)中“中心節(jié)點(diǎn)”的丟包率，但在部署LCE 的緩存系統(tǒng)中改善卻不明顯，這是因?yàn)長(zhǎng)CE 策略使得緩存系統(tǒng)的“中心”節(jié)點(diǎn)帶寬競(jìng)爭(zhēng)產(chǎn)生的主要原因是轉(zhuǎn)發(fā)流量過(guò)多。

如圖6 所示，LRU 算法總是能在系統(tǒng)中產(chǎn)生最高的重傳概率，性能表現(xiàn)最差。與LRU 相比，該文的替換算法既有較好的緩存命中率，同時(shí)系統(tǒng)平均重傳概率也比LRU 低，在基于介數(shù)中心性策略的系統(tǒng)中性能改善最高能達(dá)到34.9%，這是因?yàn)樵撍惴p少了帶寬競(jìng)爭(zhēng)，進(jìn)而減少了因丟包造成重傳。

圖6 不同緩存策略系統(tǒng)采用不同替換算法的重傳概率對(duì)比

圖7 對(duì)比了不同替換算法在不同緩存策略系統(tǒng)中用戶內(nèi)容下載時(shí)延。隨著節(jié)點(diǎn)緩存容量增加、系統(tǒng)平均命中率的提高，用戶下載時(shí)延在不斷減少。對(duì)比其他兩種緩存替換算法，該文的替換算法性能表現(xiàn)最好，這是因?yàn)槠溆行б种屏寺酚善鲙捀?jìng)爭(zhēng)持續(xù)的時(shí)間導(dǎo)致節(jié)點(diǎn)丟包率和重傳概率減少，從而大幅度降低了用戶內(nèi)容下載平均時(shí)延。在基于介數(shù)中心性策略的系統(tǒng)中，與LRU 算法相比，內(nèi)容下載時(shí)延最多可節(jié)省11.3%。

圖7 不同緩存策略系統(tǒng)采用不同替換算法的內(nèi)容下載時(shí)延對(duì)比

4 結(jié)論

該文針對(duì)ICN 緩存節(jié)點(diǎn)因持續(xù)處于帶寬資源競(jìng)爭(zhēng)狀態(tài)導(dǎo)致網(wǎng)絡(luò)擁塞加重的問(wèn)題，提出了一種基于路由器負(fù)載狀態(tài)的緩存替換算法。該算法通過(guò)監(jiān)控持續(xù)帶寬競(jìng)爭(zhēng)狀態(tài)來(lái)改善LRU 的性能，并在采用不同的策略（LCE，基于介數(shù)中心性的策略）的緩存系統(tǒng)中進(jìn)行性能對(duì)比。實(shí)驗(yàn)結(jié)果表明，所提優(yōu)化算法能夠有效地改善LRU 算法的不足，并在內(nèi)容下載時(shí)延、平均緩存命中率、重傳率上都獲得了較好的性能提升。