曾 理，倪 宏，韓 銳

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

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

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

1 ICN路由器的帶寬競爭

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

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

2.1 算法設(shè)計

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

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

圖1 基于滑動窗口抽樣檢測帶寬競爭

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

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

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

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

基于帶寬競爭監(jiān)測的替換算法中，替換窗口長度變化的行為可以用一個離散馬爾科夫過程來建模。

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

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

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

其中，p(n)是n時刻路由器抽樣檢測到帶寬持續(xù)競爭的概率。

替換窗口變化過程可通過式（3）來建模：

n時刻LRU 隊列的長度可以表示為：

3 實驗與分析

3.1 實驗設(shè)置

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

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

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

3.2 仿真結(jié)果分析

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

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

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

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

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

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

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

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

圖7 對比了不同替換算法在不同緩存策略系統(tǒng)中用戶內(nèi)容下載時延。隨著節(jié)點緩存容量增加、系統(tǒng)平均命中率的提高，用戶下載時延在不斷減少。對比其他兩種緩存替換算法，該文的替換算法性能表現(xiàn)最好，這是因為其有效抑制了路由器帶寬競爭持續(xù)的時間導(dǎo)致節(jié)點丟包率和重傳概率減少，從而大幅度降低了用戶內(nèi)容下載平均時延。在基于介數(shù)中心性策略的系統(tǒng)中，與LRU 算法相比，內(nèi)容下載時延最多可節(jié)省11.3%。

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

4 結(jié)論

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