具有社團(tuán)感知緩存策略的信息中心網(wǎng)絡(luò)分析*

王麗麗

（廣東省工商高級技工學(xué)校 韶關(guān) 512200）

1 引言

當(dāng)前，各類新應(yīng)用被大量開發(fā)，在一定程度上也因此改變了流量的產(chǎn)生與傳輸形式，有很大比例的流量都是受用戶驅(qū)動(dòng)影響而形成的獲取類應(yīng)用，這對建立在端到端通信基礎(chǔ)上的TCP/IP網(wǎng)絡(luò)架構(gòu)造成了明顯挑戰(zhàn)。為滿足用戶需求并更好地適應(yīng)各類應(yīng)用的發(fā)展，需要進(jìn)一步提高互聯(lián)網(wǎng)架構(gòu)運(yùn)行安全性、移動(dòng)性并提高可擴(kuò)展性。例如，有學(xué)者通過研究構(gòu)建了以信息內(nèi)容作為核心要素的新型網(wǎng)絡(luò)架構(gòu)［1～4］，因此可以將這類架構(gòu)統(tǒng)一看成是建立在信息數(shù)據(jù)基礎(chǔ)上的網(wǎng)絡(luò)結(jié)構(gòu)（ICN）［5～7］。考慮到隨著網(wǎng)絡(luò)流量的大幅上升，網(wǎng)絡(luò)帶寬需要承受的壓力將會(huì)持續(xù)增加，ICN可以為各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)配備緩存功能，使用戶更加貼近內(nèi)容，從而顯著降低網(wǎng)絡(luò)流量。采取不同的緩存策略時(shí)，網(wǎng)絡(luò)中的內(nèi)容分布狀態(tài)也會(huì)存在明顯差異，最終反映為網(wǎng)絡(luò)流量的變化。在ICN中所采用的最初緩存策略為LCE，在這種情況下網(wǎng)絡(luò)所有節(jié)點(diǎn)都將緩存從外部接收到的數(shù)據(jù)，從而引起緩存冗余的顯著增加。針對這一缺陷，國內(nèi)外的許多學(xué)者分別給出了不同的緩存機(jī)制［8～10］。當(dāng)前所采用的緩存機(jī)制面臨著下述問題：從緩存的位置層面分析可以發(fā)現(xiàn)，通常是對全局角度進(jìn)行研究，采取緩存的策略可以更好地適應(yīng)局部用戶所需滿足的要求；同時(shí)，各節(jié)點(diǎn)使用同樣的替換策略則會(huì)引起緩存內(nèi)容的同質(zhì)化問題。相關(guān)研究結(jié)果顯示［11～13］，Internet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有明顯的社團(tuán)特征，對于某一社團(tuán)而言，具有更大重要度的節(jié)點(diǎn)一方面更易被社團(tuán)中其他節(jié)點(diǎn)訪問到，同時(shí)也更易被社團(tuán)外部節(jié)點(diǎn)訪問［14～15］。在此基礎(chǔ)上，本文給出了關(guān)于社團(tuán)感知的緩存以及對應(yīng)的緩存替換策略（SCCNC），各種流行度的內(nèi)容可以在網(wǎng)絡(luò)中形成更為合理的分布狀態(tài)。本文選擇以編碼替代移除的緩存替換策略，在保持原先節(jié)點(diǎn)緩存空間的前提下，進(jìn)一步增加緩存內(nèi)容的多樣性并提高緩存的命中率。

2 SCCNC緩存策略

2.1 節(jié)點(diǎn)社團(tuán)重要度

本文利用節(jié)點(diǎn)社團(tuán)重要度來獲得ICN網(wǎng)絡(luò)內(nèi)各個(gè)數(shù)據(jù)的緩存位置。在此網(wǎng)絡(luò)鄰接矩陣中總共含有c個(gè)比其它特征值更大的特征值，可將其視為對網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)進(jìn)行量化的關(guān)鍵指標(biāo)。可以把網(wǎng)絡(luò)社團(tuán)強(qiáng)度表示成kcP=lgΠk-1λ。再通過攝動(dòng)理論求解出節(jié)點(diǎn)社團(tuán)重要度的近似解Pk：

式（1）的c代表網(wǎng)絡(luò)社團(tuán)的數(shù)量，vi代表以網(wǎng)絡(luò)路由器作為節(jié)點(diǎn)，以物理鏈路作為邊組成的鄰接矩陣對應(yīng)的第i個(gè)特征向量，其中，vik是特征向量vi所包含的第k個(gè)元素。當(dāng)Pk越大時(shí)，表示節(jié)點(diǎn)k的重要性越高，因此其它節(jié)點(diǎn)就越易訪問上述節(jié)點(diǎn)。當(dāng)網(wǎng)絡(luò)包含的節(jié)點(diǎn)數(shù)為n以及社團(tuán)數(shù)為c的情況下，跟式（1）應(yīng)先計(jì)算各節(jié)點(diǎn)社團(tuán)重要度，此時(shí)只需求解代表網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)系的鄰接矩陣特征向量與特征值便可。考慮到實(shí)際情況下的大多數(shù)網(wǎng)絡(luò)都屬于稀疏網(wǎng)絡(luò)，因此可以通過Lanczos與QL算法來求解得到稀疏對稱矩陣的特征向量與特征解對應(yīng)的時(shí)間復(fù)雜度是O（nm），此處n代表網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)，m代表邊數(shù)，所需的計(jì)算量不大，可以進(jìn)行實(shí)際應(yīng)用。

2.2 網(wǎng)絡(luò)編碼緩存替換策略

使用SCCNC時(shí)，應(yīng)選擇社團(tuán)作為單位，并且按照每個(gè)節(jié)點(diǎn)各自的社團(tuán)重要度采取相應(yīng)的緩存替換策略。當(dāng)節(jié)點(diǎn)的社團(tuán)重要度越高，緩存流行度越低時(shí)，就越易被替換，從而使緩存可以在時(shí)間與空間層面上都形成合理的分布狀態(tài)。

令社團(tuán)i中的Nj節(jié)點(diǎn)對應(yīng)的社團(tuán)重要度是Iij，該社團(tuán)的平均節(jié)點(diǎn)重要度等于Ici。在緩存被全部占用之后，先通過LRU算法完實(shí)現(xiàn)緩存內(nèi)容的排序過程，同時(shí)建立對應(yīng)的緩存序列。轉(zhuǎn)移第k個(gè)內(nèi)容的概率是

上式的α是歸一化因子，應(yīng)滿足下述條件：

在緩存被替換之后，假定內(nèi)容p為等待后續(xù)移除的內(nèi)容，當(dāng)緩存含有的原始塊數(shù)量為n時(shí)，采用隨機(jī)網(wǎng)絡(luò)編碼的方式處理這些原始塊，同時(shí)產(chǎn)生1個(gè)編碼塊并對其進(jìn)行緩存，之后將n個(gè)原始塊全部移除。通過這種方式可以釋放出由n-1個(gè)塊所占據(jù)的緩存空間，并且還可以繼續(xù)保留所有內(nèi)容塊的原始信息。

3 仿真測試

本實(shí)驗(yàn)進(jìn)行仿真測試的網(wǎng)絡(luò)拓?fù)渫ㄟ^BRITE拓?fù)渖善鞯玫?，該網(wǎng)絡(luò)總共含有的節(jié)點(diǎn)數(shù)為100個(gè)，鏈路的帶寬等于1Gb/s，節(jié)點(diǎn)度平均值等于4。先利用BRITE生成不同的網(wǎng)絡(luò)拓?fù)?，之后再開展仿真測試獲得相近的結(jié)果。此網(wǎng)絡(luò)使用的路由機(jī)制是Dijkstra算法，首先對內(nèi)容服務(wù)器存入4000個(gè)1 Gb的數(shù)據(jù)內(nèi)容，把各內(nèi)容依次劃分為100個(gè)內(nèi)容塊，并以10個(gè)內(nèi)容組成一代。選擇代內(nèi)隨機(jī)線性網(wǎng)絡(luò)編碼的方式，編碼與解碼都只出現(xiàn)在同代內(nèi)容塊中。數(shù)據(jù)內(nèi)容的流行度符合Zipf分布規(guī)律，并且用戶請求內(nèi)容屬于一種泊松分布規(guī)律。

1）平均下載時(shí)間。指的是各用戶在發(fā)送出首個(gè)Interest至此用戶完成最后1個(gè)內(nèi)容塊的接收時(shí)所經(jīng)歷的時(shí)間。

2）緩存命中率。指的是緩存響應(yīng)Interest的概率，可將其作為評價(jià)緩存性能的關(guān)鍵指標(biāo)。當(dāng)緩存的命中率增大時(shí)，則表示網(wǎng)絡(luò)具備更高的緩存效率。

4）下載跳數(shù)減少率β(t)。此處的hi（t）代表內(nèi)容塊i在緩存命中節(jié)點(diǎn)后至請求者所經(jīng)歷的所有跳數(shù)之和，Hi（t）代表內(nèi)容塊i由內(nèi)容服務(wù)器至請求者的總跳數(shù)。當(dāng)內(nèi)容塊i請求取決于內(nèi)容服務(wù)器響應(yīng)時(shí)，存在hi（t）=Hi（t）。

5）傳輸流量。指的是從首個(gè)用戶發(fā)送Interest開始至最終用戶接收到最后內(nèi)容塊時(shí)在網(wǎng)絡(luò)中傳輸?shù)乃蠨ata包內(nèi)容。從圖1中可以看到各種參數(shù)條件下所選擇的四種緩存方案得到的平均下載時(shí)間。可以明顯看到，上述各種機(jī)制對應(yīng)的平均下載時(shí)間在α增大后都出現(xiàn)了減小的現(xiàn)象，如圖1（a）所示。出現(xiàn)這一情況的原因是當(dāng)α增大后，用戶將會(huì)形成更加集中的偏好性，此時(shí)用戶將會(huì)把發(fā)送的各項(xiàng)請求全都集中于某一特定內(nèi)容，導(dǎo)致此類內(nèi)容占據(jù)的網(wǎng)絡(luò)緩存不斷增加，從而更加靠近用戶。隨著用戶請求的增加，同樣會(huì)引起網(wǎng)絡(luò)緩存的上升，因此，各種機(jī)制對應(yīng)的平均下載時(shí)間都將隨用戶請求數(shù)的上升而下降，結(jié)果如圖1（b）所示。根據(jù)圖1可知：SCCNC機(jī)制具備較大的優(yōu)勢，此優(yōu)勢對于小的α參數(shù)以及用戶數(shù)比較少的情況將會(huì)表現(xiàn)得更加明顯。對于SCCNC而言，當(dāng)把原始塊緩存到可具有較高社團(tuán)重要度的節(jié)點(diǎn)上時(shí)，將會(huì)導(dǎo)致此類節(jié)點(diǎn)更易被別的節(jié)點(diǎn)進(jìn)行訪問。

圖1 四種緩存方案平均下載時(shí)間對比

從圖2中可以看到各緩存方案對應(yīng)的跳數(shù)減少率?？梢悦黠@發(fā)現(xiàn)，SCCNC表現(xiàn)出了比其他方案更優(yōu)的跳數(shù)減少率。這是由于，SCCNC的所有節(jié)點(diǎn)都可以按照各自節(jié)點(diǎn)重要度不同采取相應(yīng)的緩存替換策略。當(dāng)緩存被全部使用后，可以通過編碼代替移除來實(shí)現(xiàn)緩存空間的釋放，并保留原先的內(nèi)容塊數(shù)據(jù)。

圖2 4種緩存方案跳數(shù)減少率對比

4 結(jié)語

1）本文提出了一種具有社團(tuán)感知緩存策略（SCCNC）的信息中心網(wǎng)絡(luò)，選擇以編碼替代移除的緩存替換策略，在保持原先節(jié)點(diǎn)緩存空間的前提下，進(jìn)一步增加緩存內(nèi)容的多樣性并提高緩存的命中率。

2）SCCNC機(jī)制對于小的α參數(shù)以及用戶數(shù)比較少的情況將會(huì)表現(xiàn)得更加明顯。當(dāng)把原始塊緩存到可具有較高社團(tuán)重要度的節(jié)點(diǎn)上時(shí)，將會(huì)導(dǎo)致此類節(jié)點(diǎn)更易被別的節(jié)點(diǎn)進(jìn)行訪問。SCCNC表現(xiàn)出了比其他方案更優(yōu)的跳數(shù)減少率。