基于t-SNE算法的ICN緩存容量分配機制

陳香伊， 王興偉， 李 婕， 易 波， 黃 敏

(1.東北大學(xué) 計算機科學(xué)與工程學(xué)院 遼寧 沈陽 110169； 2.東北大學(xué) 信息科學(xué)與工程學(xué)院 遼寧 沈陽 110819)

0 引言

隨著互聯(lián)網(wǎng)數(shù)據(jù)的快速增長和網(wǎng)絡(luò)應(yīng)用的日趨豐富，用戶需求逐漸從主機之間的通信演進(jìn)為主機對網(wǎng)絡(luò)信息的重復(fù)訪問[1-2].與傳統(tǒng)網(wǎng)絡(luò)架構(gòu)中以IP地址進(jìn)行路由的方式不同，信息中心網(wǎng)絡(luò)(information-centric networking，ICN)[3-4]通過唯一的內(nèi)容名稱對用戶請求進(jìn)行路由，且每個節(jié)點除了具有處理、轉(zhuǎn)發(fā)的功能之外，還具有存儲的功能[5].網(wǎng)內(nèi)緩存作為ICN最大特點之一[6-7]，在提高用戶服務(wù)質(zhì)量、減少用戶訪問時延、減輕服務(wù)器負(fù)載上功不可沒[8].ICN緩存領(lǐng)域中很多關(guān)鍵技術(shù)已有了階段性的創(chuàng)新，但仍值得深入分析和研究[3].

在ICN眾多研究項目中，最具代表性且最有發(fā)展前景的范例當(dāng)屬命名數(shù)據(jù)網(wǎng)絡(luò)(named data networking，NDN)項目[9-10].文獻(xiàn)[11]為了充分利用ICN的內(nèi)置緩存，提出了一種基于內(nèi)容空間分區(qū)和哈希路由的緩存機制，將內(nèi)容緩存在指定的劃分區(qū)域中，能夠解決哈希路由引起的路徑拉伸問題.文獻(xiàn)[12]提出了一種新型智能資源管理系統(tǒng)，旨在分析請求模式，充分利用通用緩存內(nèi)容.該系統(tǒng)能夠根據(jù)用戶需求變化實時高效地進(jìn)行緩存資源分配.文獻(xiàn)[13]通過在轉(zhuǎn)發(fā)信息庫中添加路由緩存，包括原子緩存和即時緩存，來緩解轉(zhuǎn)發(fā)信息庫的爆炸問題.目前國內(nèi)外學(xué)者在ICN體系結(jié)構(gòu)、路由算法、緩存決策等方面已經(jīng)取得了一定的成果，但是卻鮮有針對緩存容量分配機制的研究.

ICN緩存容量分配面臨著巨大的緩存對象與有限的緩存空間之間的矛盾[14].絕大多數(shù)的ICN中都默認(rèn)均勻部署路由器(即緩存容量相同).考慮到節(jié)點位置、網(wǎng)內(nèi)流量分布以及用戶請求特征不同，從根本上導(dǎo)致了節(jié)點負(fù)載不均衡.因此，如何將有限的總緩存容量適當(dāng)?shù)夭渴鸬礁P(guān)鍵的位置，以平衡節(jié)點負(fù)載并提高緩存利用率尤為關(guān)鍵.

針對上述問題，本文在互聯(lián)網(wǎng)主干網(wǎng)絡(luò)的ICN網(wǎng)絡(luò)架構(gòu)下，分別從用戶角度和節(jié)點角度對全局流量分布進(jìn)行分析.首先分析網(wǎng)絡(luò)拓?fù)鋵傩砸约傲髁刻卣餍畔?，然后基于分析結(jié)果對網(wǎng)絡(luò)節(jié)點進(jìn)行聚類劃分，并重新分配節(jié)點容量，旨在將有限的總緩存容量以最優(yōu)的方式合理地分配給各節(jié)點，從而實現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡.

1 網(wǎng)絡(luò)數(shù)據(jù)模型

1.1 拓?fù)湫畔?/h3>

網(wǎng)絡(luò)拓?fù)渲械墓?jié)點位置從根本上影響著該節(jié)點處理興趣請求的概率，即位于網(wǎng)絡(luò)中相對“樞紐”位置的節(jié)點可能需要處理更多的請求.因此，基于圖論基礎(chǔ)，選取了節(jié)點度數(shù)中心性C_d、節(jié)點介數(shù)中心性C_b、節(jié)點緊密中心性C_c3個中心性指標(biāo)作為網(wǎng)絡(luò)拓?fù)鋵傩詠韰^(qū)分節(jié)點的重要程度.

1.2 流量特征信息

流量特征信息能夠很好地反映網(wǎng)絡(luò)流量的分布情況，為區(qū)分節(jié)點的重要程度，本文從節(jié)點負(fù)載和用戶偏好兩方面共選取5個指標(biāo)作為流量特征信息屬性.在節(jié)點負(fù)載方面，選取接收興趣包個數(shù)Rec_I、響應(yīng)請求次數(shù)Res_I以及內(nèi)容替換次數(shù)Rep_C3個指標(biāo).在用戶偏好方面，選取興趣聚合率Aggr和興趣影響度Impact兩個指標(biāo).其中，節(jié)點負(fù)載方面的3個指標(biāo)可以通過采樣單位時間段內(nèi)的測量值累加統(tǒng)計得出.下面給出本文對興趣聚合率和興趣影響度的定義.

1.3 信息整合模型

本文將提出的3個拓?fù)鋮?shù)和5個流量信息參數(shù)作為評價節(jié)點重要程度的指標(biāo).使用xi(t)表示，在單位取樣時間段T內(nèi)，節(jié)點vi收集到的流量特征信息的數(shù)據(jù)，如公式(1)，

xi(T)={Rec_Ii(T),Res_Ii(T),Rep_Ci(T),Aggri(T),Impacti(T)}，

(1)

其中：xi(T)是五維數(shù)據(jù)，簡寫為xi.單獨收集一個時間段內(nèi)的流量信息不能全面反映網(wǎng)內(nèi)流量的變化情況，因此，總共需要選取T′個采樣時間段進(jìn)行流量信息的收集.用Xi表示在T′個采樣時間段內(nèi)節(jié)點vi收集到的數(shù)據(jù)集為

Xi={xi(T1),xi(T2),…,xi(T′T),C_di,C_bi,C_ci},i∈[0,n).

(2)

結(jié)合公式(1)，可將公式(2)中的Xi展開

Xi={Rec_Ii(T1),Res_Ii(T1),Rep_Ci(T1),Aggri(T1),Impacti(T1),…,Rec_Ii(T′T),Res_Ii(T′T),

Rep_Ci(T′T),Aggri(T′T),Impacti(T′T),C_di,C_bi,C_ci}，

其中：Xi是(5T′+3)維的數(shù)據(jù).考慮到拓?fù)渲泄灿衝個節(jié)點，因此，本文收集的數(shù)據(jù)集為n個(5T′+3)維的數(shù)據(jù).

2 緩存容量分配機制

2.1 基于改進(jìn)t-SNE算法的數(shù)據(jù)集處理

本文所收集的數(shù)據(jù)呈現(xiàn)高維特征，且對于每個節(jié)點而言高維數(shù)據(jù)之間存在數(shù)據(jù)冗余、信息重疊的問題.本文將使用改進(jìn)的t-SNE算法[15]對原數(shù)據(jù)進(jìn)行降維，并通過VP樹(vantage point tree)[16]構(gòu)建K-近鄰.在高維空間中，已知xi和xj為任意的兩個數(shù)據(jù)點，xk為非xi的數(shù)據(jù)點，Neii為xi鄰居集合，可通過對稱化兩個條件概率分布得到點對相似性的聯(lián)合概率分布pij.而在本文收集的高維數(shù)據(jù)點中，兩個相距較遠(yuǎn)的數(shù)據(jù)點的相似性概率pij非常小，因此取條件概率作為pij的近似.基于此，高維空間中數(shù)據(jù)點的點對相似性可定義為

(3)

高維數(shù)據(jù)是基于流形的[17]，在高維空間中如果直接使用歐式距離會存在誤差，因此本文將以測地線距離代替歐式距離.但是，高維數(shù)據(jù)中的真實測地線距離難以獲得.考慮到每個輸入對象xi已有最近鄰居集合Neii，本文將鄰域內(nèi)兩個數(shù)據(jù)點間的最短路徑計算值作為真實測地線距離的近似.xi鄰域Neii內(nèi)任意兩個數(shù)據(jù)點間的歐式距離記為dX(xi,xj)，測地線距離記為dG(xi,xj)，兩者關(guān)系如公式(4)，然后計算xi鄰域Neii內(nèi)任意兩個數(shù)據(jù)點間的最短路徑，如公式(5)，

(4)

dG(xi,xj)=min{dG(xi,xj),dG(xi,xk)+dG(xk,xj)}，k∈[0,n).

(5)

基于此，公式(3)可改進(jìn)為

(6)

2.2 緩存容量分配

在通過構(gòu)造K-近鄰表征相似性的方式改進(jìn)了t-SNE算法后，對收集到的高維數(shù)據(jù)進(jìn)行處理，得到低維空間的嵌入結(jié)果Y(I).本文以該降維結(jié)果作為節(jié)點相似性的劃分標(biāo)準(zhǔn)，根據(jù)節(jié)點重要程度不同，設(shè)置不同的權(quán)重，進(jìn)而按權(quán)重為節(jié)點分配不同大小的容量空間.

假設(shè)低維嵌入結(jié)果Y(I)將節(jié)點劃分為k_class類，numj表示類別j中包含的節(jié)點個數(shù).令W表示類別對應(yīng)的權(quán)重值，W={w1,w2,…,wk}，W中的變量按降序排列且滿足公式(7)的約束，

(7)

假設(shè)整個網(wǎng)絡(luò)拓?fù)涞目偩彺嫒萘坑肅total表示，在類別j中，節(jié)點的分配緩存大小用Cji表示，

Cji=Ctotal·wj/numj,j∈[1,k],i∈[1,numj).

(8)

緩存容量分配機制中，首先初始化參數(shù)并構(gòu)建VP樹；然后根據(jù)VP樹構(gòu)建K-近鄰并計算點對之間的測地線距離；再計算高維空間聯(lián)合概率分布；最后使用梯度下降法進(jìn)行訓(xùn)練，得到低維嵌入的結(jié)果.通過構(gòu)造K-近鄰表征相似性的方式改進(jìn)t-SNE算法，既考慮了高維數(shù)據(jù)的流形特征，也大大降低了高維空間點對相似性的計算量.

3 性能評價

3.1 拓?fù)溆美?/h3>

在進(jìn)行仿真實現(xiàn)的過程中，本文使用了中國的cernet和美國的deltacom兩種拓?fù)浣Y(jié)構(gòu).cernet網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)含有36個節(jié)點、49條鏈路，平均節(jié)點度數(shù)為2.72.deltacom網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)含有113個節(jié)點、161條鏈路，平均節(jié)點度數(shù)為2.85.

3.2 評價指標(biāo)

本文在Ubuntu下搭建基于NS-3的仿真模塊NDNSIM并進(jìn)行仿真實現(xiàn)，同時將搜集的歷史流量數(shù)據(jù)導(dǎo)入到matlab軟件中進(jìn)行處理.

本文基于兩種拓?fù)浣Y(jié)構(gòu)、采用多個性能指標(biāo)對基于t-SNE算法的緩存容量分配機制進(jìn)行性能評價，評價指標(biāo)如下.

1) 緩存命中率. 緩存命中率的計算公式CacheHitRatio=NumcacheHit/Numsuccess，其中：NumcacheHit為從路由器節(jié)點的內(nèi)容存儲庫(content store,CS)獲得內(nèi)容的興趣請求數(shù)；Numsuccess為路由成功的興趣請求數(shù).緩存命中率能夠在很大程度上表征緩存內(nèi)容的利用率.

2) 路由成功率. 路由成功率的計算公式SuccessRatio=Numsuccess/Numtotal，其中：Numsuccess為路由成功的興趣請求數(shù)；Numtotal為用戶向網(wǎng)絡(luò)中發(fā)起的興趣請求總數(shù). 路由成功率能夠表征路由機制的效率.

3)緩存開銷. 節(jié)點緩存開銷的計算公式Overi=Rep_Ci·Volaver/ci，其中：Rep_Ci為節(jié)點內(nèi)容替換次數(shù)；Volaver為內(nèi)容平均大?。籧i為節(jié)點緩存容量.緩存開銷能夠表征采樣時間段內(nèi)節(jié)點的負(fù)載情況.

3.3 性能評估

為驗證本文設(shè)計的基于t-SNE算法的緩存容量分配機制，在全網(wǎng)發(fā)起了5 000次請求進(jìn)行節(jié)點聚類，所有節(jié)點都能正常執(zhí)行緩存替換機制(緩存空間已滿)并收集50個采樣時間段的流量特征信息.

在cernet拓?fù)湎聢?zhí)行本文的緩存容量分配機制得到的二維嵌入結(jié)果如圖1所示，其中每個數(shù)據(jù)點代表一個路由器節(jié)點.根據(jù)節(jié)點在網(wǎng)絡(luò)中的相對位置可以發(fā)現(xiàn)，X值越大，Y值越小，節(jié)點在網(wǎng)絡(luò)中越重要.由該圖可見cernet的36個節(jié)點被聚簇為2類，含有重要節(jié)點8個，含有普通節(jié)點28個.在deltacom拓?fù)湎聢?zhí)行本文的緩存容量分配機制得到的二維嵌入結(jié)果如圖2所示. deltacom中的113個節(jié)點被聚簇為4類，其中節(jié)點個數(shù)分別為6、40、30、37.

圖1 cernet拓?fù)湎碌牡途S嵌入結(jié)果Fig.1 The low dimension result in cernet

圖2 deltacom拓?fù)湎碌牡途S嵌入結(jié)果Fig.2 The low dimension result in deltacom

為了驗證本文提出的緩存容量分配機制的性能，選取LCE(leave copy everywhere)以及Betw[18]作為基準(zhǔn)緩存決策機制.其中，LCE是ICN的默認(rèn)緩存決策機制，它在數(shù)據(jù)包傳輸路徑上的每個路由器節(jié)點都進(jìn)行緩存；而Betw機制對LCE進(jìn)行了改進(jìn)，它將內(nèi)容緩存在興趣包轉(zhuǎn)發(fā)路徑上介數(shù)中心性最大的節(jié)點中.本文在cernet和deltacom兩種網(wǎng)絡(luò)拓?fù)湎拢瑢煞N基準(zhǔn)機制分別在默認(rèn)等量分配和基于t-SNE算法的緩存容量分配(t-LCE、t-Betw)兩種情況下進(jìn)行仿真實驗.在網(wǎng)內(nèi)發(fā)起3 000個興趣請求，并統(tǒng)計對應(yīng)緩存命中率、路由成功率、緩存開銷3個指標(biāo).實驗結(jié)果如表1所示.

從表1中我們可以看出，在引入緩存容量分配機制后，t-LCE與t-Betw均在不同程度上提升了基準(zhǔn)緩存機制的緩存命中率和路由成功率，且降低了網(wǎng)絡(luò)平均緩存開銷.本文提出的緩存容量分配機制基于低維嵌入的結(jié)果，為節(jié)點分配不同大小的緩存容量.cernet拓?fù)湎拢鶆蚍植紩r每個節(jié)點緩存容量為1 G，重要節(jié)點權(quán)重w1=0.6，普通節(jié)點權(quán)重w2=0.4，基于低維嵌入結(jié)果，每個重要節(jié)點需分配2.7 G容量，每個普通節(jié)點需分配0.5 G容量(2.7 G×8+0.5 G×28≈36 G).deltacom拓?fù)湎?，同樣均勻分布時節(jié)點緩存容量為1 G，4類節(jié)點權(quán)重分別設(shè)為w1=0.4、w2=0.3、w3=0.2、w4=0.1.根據(jù)公式(8)可知，4類節(jié)點分別需要分配7.5 G、0.85 G、0.75 G、0.3 G容量(7.5 G×6+0.85 G×40+0.75 G×30+0.3 G×37≈113 G).

表1 Cernet與deltacom兩種拓?fù)湎聦Ρ葘嶒灲Y(jié)果Tab.1 Comparative experimental results over cernet and deltacom %

在兩種拓?fù)湎?，本文提出的緩存容量分配機制與默認(rèn)機制進(jìn)行對比分析，緩存命中率提高了3%～4%，路由成功率基本維持在95%，其性能的提升與緩存決策機制本身有關(guān).t-LCE機制對緩存命中率的提升更明顯.因為從全網(wǎng)角度來看，盡管普通節(jié)點容量減少，但重要節(jié)點分配更多的容量后，不僅特別流行的內(nèi)容副本數(shù)變化不大，還能夠在重要節(jié)點緩存更多的流行內(nèi)容，因此在緩存命中率指標(biāo)上提升很多.t-Betw機制則在路由成功率提升方面更加明顯，這是由于該機制在當(dāng)前路徑中的重要節(jié)點緩存內(nèi)容，緩存容量分配機制為網(wǎng)絡(luò)中相對重要的節(jié)點分配更多的緩存容量，這些節(jié)點能夠響應(yīng)更多的興趣請求，因此極大提升了路由成功率.

從全網(wǎng)節(jié)點的平均緩存開銷來看，cernet拓?fù)湎聇-LCE的平均緩存開銷減少了6.3%，t-Betw的平均緩存開銷減少了23.4%.deltacom拓?fù)湎聇-LCE的節(jié)點平均開銷減少了13.5%，t-Betw的節(jié)點平均開銷減少了17.4%.由此可見，本文提出的緩存容量分配機制在Betw上提升效果更明顯，這是因為Betw對節(jié)點按照節(jié)點介數(shù)中心性進(jìn)行劃分，而不是像LCE機制那樣對所有節(jié)點一視同仁.此外，本文提出的緩存容量分配機制，權(quán)衡了拓?fù)湫畔⒑土髁糠植迹瑢⒐?jié)點按照重要程度進(jìn)行劃分，進(jìn)而能夠保證網(wǎng)絡(luò)流量按照節(jié)點重要程度均勻分布在網(wǎng)內(nèi)，不僅解決了部分節(jié)點負(fù)載過重的問題，還解決了少數(shù)節(jié)點緩存利用率不高的問題，從而降低了網(wǎng)絡(luò)的整體緩存開銷.

4 結(jié)束語

本文通過對現(xiàn)有緩存技術(shù)進(jìn)行分析，提出了基于t-SNE算法的緩存容量分配機制.通過構(gòu)造K-近鄰表征相似性的方式改進(jìn)t-SNE算法，對網(wǎng)絡(luò)拓?fù)鋵傩砸约傲髁刻卣餍畔⑦M(jìn)行分析，基于聚類結(jié)果將有限的緩存空間合理分配給不同節(jié)點以達(dá)到平衡節(jié)點負(fù)載的目的.為驗證本文方法的可行性和有效性，對算法進(jìn)行了仿真實現(xiàn)，并與基準(zhǔn)機制進(jìn)行對比分析.從實驗結(jié)果可以看出，本文設(shè)計的機制在緩存命中率、路由成功率以及緩存開銷等方面具有一定的優(yōu)勢.下一步工作將對緩存分配機制的穩(wěn)定性進(jìn)行驗證，進(jìn)一步完善本文提出的機制.