常 珞，薛 念

（河南醫(yī)學(xué)高等專科學(xué)校 河南 鄭州451191）

概率緩存策略的網(wǎng)絡(luò)傳輸機(jī)制研究

常 珞，薛 念

（河南醫(yī)學(xué)高等?？茖W(xué)校 河南 鄭州451191）

針對網(wǎng)絡(luò)傳輸過程中數(shù)據(jù)資源以高流行度緩存在路由器內(nèi)，以提高資源獲取的傳輸效率和資源利用率的問題。本研究考慮網(wǎng)絡(luò)拓?fù)鋵彺娴挠绊?，利用網(wǎng)絡(luò)傳輸過程中固定時間段內(nèi)資源流行度的差異性，結(jié)合資源本身的收益因素，提出一種基于概率緩存策略PCS（Probabilistic Caching strategy）的網(wǎng)絡(luò)傳輸機(jī)制。通過該資源數(shù)據(jù)請求路徑進(jìn)行概率緩存，以提高網(wǎng)絡(luò)傳輸過程中的緩存性能。仿真表明該緩存策略有效地避免了非熱門內(nèi)容的不必要緩存，當(dāng)緩存容量5%時，平均命中率可達(dá)25%，平均跳數(shù)僅為3.42，有利于網(wǎng)絡(luò)傳輸整體性能的提升。

概率緩存；網(wǎng)絡(luò)傳輸；資源價值；流行度；緩存命中率；平均跳數(shù)

近年來，隨著網(wǎng)絡(luò)設(shè)備的普及，用戶對數(shù)據(jù)資源的使用需求日益增長[1]。與此同時，IP網(wǎng)絡(luò)規(guī)模指數(shù)式增長而帶來的對網(wǎng)絡(luò)管理和維護(hù)的迫切需求[2]，研究數(shù)據(jù)資源緩存是資源共享網(wǎng)絡(luò)傳輸研究中的一個關(guān)鍵技術(shù)[3]，也是面向未來網(wǎng)絡(luò)研究領(lǐng)域的熱點問題[4]。資源緩存是網(wǎng)絡(luò)傳輸中的重要特征，對于提升用戶訪問共享資源的性能具有重要影響[5]。共享資源下的網(wǎng)絡(luò)傳輸旨在利用內(nèi)置緩存提高資源獲取的傳輸效率和網(wǎng)絡(luò)資源的利用率[6]，在網(wǎng)絡(luò)傳輸過程中，通過分布式的內(nèi)容緩存機(jī)制[7]，允許節(jié)點路由器對傳輸?shù)馁Y源進(jìn)行緩存，這樣Interest請求就不會再被轉(zhuǎn)發(fā)到遠(yuǎn)處的數(shù)據(jù)資源[8]，從而不必每次都從源獲取資源，提高資源傳輸效率，使得網(wǎng)絡(luò)傳輸能夠有效地支持內(nèi)容業(yè)務(wù)。

本研究考慮網(wǎng)絡(luò)拓?fù)鋵彺娴挠绊懀镁W(wǎng)絡(luò)傳輸過程中固定時間段內(nèi)資源流行度的差異性，結(jié)合資源本身的收益因素，提出一種基于概率緩存策略PCS（Probabilistic Caching strategy）的網(wǎng)絡(luò)傳輸機(jī)制。在用戶發(fā)送資源請求沿原路徑返回時，由資源收益因素得到符合的高流行度資源，再由資源數(shù)據(jù)包沿請求路徑返回時進(jìn)行概率緩存，避免非流行資源的不必要緩存，因此，提高網(wǎng)絡(luò)傳輸過程中的緩存性能。

1 網(wǎng)絡(luò)傳輸?shù)馁Y源緩存與價值

1.1 資源緩存

在網(wǎng)絡(luò)傳輸過程中進(jìn)行資源緩存設(shè)計，需要遵循兩個基本原則：1）為了減小海量用戶的下載平均時延，需要將流行度高的內(nèi)容緩存到邊緣節(jié)點以提高網(wǎng)絡(luò)資源整體利用率[9]；2）為了盡量使得用戶請求由同一資源運營商提供的緩存節(jié)點，需要提高整個網(wǎng)絡(luò)緩存系統(tǒng)的緩存多樣性，從而大幅降低域間流量[10]。PCS在共享資源的基礎(chǔ)上，依據(jù)內(nèi)容的流行度，在內(nèi)容返回的路徑上，將滿足高流行度的共享資源價值約束條件下，概率地緩存在靠近邊緣的路由器上。通過有效地數(shù)據(jù)緩存，充分利用路由器的緩存空間，減小了網(wǎng)內(nèi)緩存冗余，提高的網(wǎng)絡(luò)傳輸效率[11]。

假設(shè)在網(wǎng)絡(luò)傳輸過程中緩存時間t0為0時，且緩存過程中節(jié)點V1至V7的緩存空間均為空。在一段時間T中，用戶A至D分別對資源f1進(jìn)行訪問請求操作，同時用戶B和C也對資源f2進(jìn)行了請求操作。假設(shè)資源f1和f2滿足共享資源條件，則資源f1和f2返回的路徑上進(jìn)行節(jié)點緩存。如何有效地將資源緩存到適當(dāng)?shù)穆酚善魃?，同時減少資源內(nèi)容的緩存冗余，是研究的關(guān)鍵問題。在資源返回的路徑上，節(jié)點V2和V4的介數(shù)最大，同時資源f1和f2分別緩存在V2和V4也最為合適。PCS結(jié)合了節(jié)點的介數(shù)和共享資源的流行度，通過預(yù)判路由器節(jié)點的介數(shù)，將流行度高的資源緩存在靠近用戶的邊緣節(jié)點上[12]。這種方法使得滿足共享資源價值約束條件的不同熱度的內(nèi)容以合理的概率緩存到不同的介數(shù)路由節(jié)點上，從而節(jié)省了路由器節(jié)點的緩存資源，高中介度節(jié)點的緩存次數(shù)減少，緩存副本在緩存中的存儲時間增大，命中率提高。拓?fù)浣Y(jié)構(gòu)如圖1所示的。

圖1 網(wǎng)絡(luò)緩存的傳輸拓?fù)淠Ｐ?/p>

1.2 共享資源價值

PCS在網(wǎng)絡(luò)傳輸過程中，資源緩存與否的先決條件是該內(nèi)容是否滿足資源共享價值因素[13]。資源的流行度越高，代表了對該資源請求的用戶越多，對此從該內(nèi)容獲取的價值因素也就越大，同時路由器緩存該資源的概率也就越大。PCS聯(lián)合考慮了資源訪問請求價值和資源存儲成本進(jìn)行了價值因素的設(shè)計。

假設(shè)資源k首次與第Tik次經(jīng)過路由器vi的時間分別為Ti0（k）與Ti1（k）。資源k自Ti0（k）以來經(jīng)過路由器vi的總次數(shù)為fik，即資源k被用戶訪問請求的總次數(shù)。當(dāng)路由器效益等于緩存成本時，得到用戶資源請求總次數(shù)的閥值，然后路由器根據(jù)這個閥值來決定是否緩存該資源，在Ti0（k）到 Ti1（k）時間內(nèi)，路由器vi緩存資源k的成本Cik如下[14]：

其中，Dk經(jīng)過路由器的資源k的大小，路由器vi每秒緩存每比特資源的成本為pic，表示用戶每次下載緩存資源k時，路由器vi獲得的效益，則效益Sik為：

其中，當(dāng)Sik=Cik時，路由器vi決定是否緩存該資源k：

當(dāng)請求資源k的總次數(shù)fik滿足（3）式時k，路由器緩存資源，否則不緩存。

2 概率緩存策略（PCS）

2.1 概率緩存

在一段時間T內(nèi)，PCS是用戶對資源訪問請求的統(tǒng)計，得到滿足共享資源訪問條件的高流行度資源，從而進(jìn)行重要路由節(jié)點的概率緩存[15]。即多個用戶發(fā)送資源k的訪問請求，對資源i請求經(jīng)過節(jié)點時，進(jìn)行次數(shù)統(tǒng)計和資源價值評估，當(dāng)資源i滿總價值提升標(biāo)準(zhǔn)時，記錄當(dāng)前節(jié)點在請求路徑L上的位置vik，并添加到訪問請求記錄中，同時將訪問請求記錄中的變量cnt加1，初始值為0。當(dāng)再次得到滿足價值條件的節(jié)點時，和上次操作一樣將該節(jié)點的位置添加到訪問請求記錄中，并使cnt加1。

訪問請求記錄命中緩存節(jié)點時，將訪問請求中所記錄的節(jié)點位置和變量cnt依次添加到數(shù)據(jù)包中。當(dāng)數(shù)據(jù)包經(jīng)過滿足收益需求的節(jié)點時，以概率P進(jìn)行內(nèi)容緩存，同時將該節(jié)點的位置信息從數(shù)據(jù)包剔除。

其中i為一個計數(shù)器，每當(dāng)經(jīng)過一個滿足收益標(biāo)準(zhǔn)的節(jié)點是，i值加1。因此，高流行度的內(nèi)容以更高的概率緩存至用戶邊緣節(jié)點。

2.2 性能評價

文中的緩存目標(biāo)是為了提高用戶請求資源的命中率和網(wǎng)絡(luò)的傳輸效率，為了更好的反映PCS的性能，需要測量緩存命中率和平均跳數(shù)作為性能評價指標(biāo)。

平均跳數(shù)反映了內(nèi)容緩存的節(jié)點與用戶節(jié)點之間接近程度，平均跳數(shù)值越小，反映資源緩存的節(jié)點越接近用戶節(jié)點，大量的用戶請求可以靠近邊緣獲取資源，減輕了資源服務(wù)器的負(fù)載，與之相應(yīng)的的網(wǎng)絡(luò)傳輸開銷較小，帶寬消耗降低，有利于提高網(wǎng)絡(luò)傳輸資源的利用率。假設(shè)hi（t）表示時間t-1到時間t內(nèi)用戶資源訪問請求到資源節(jié)點的路由跳數(shù)。則平均跳數(shù)為：

3 仿真和性能分析

3.1 仿真環(huán)境

為了驗證概率緩存在網(wǎng)絡(luò)傳輸過程中是否能夠達(dá)到預(yù)期的效果，利用ndnSIM仿真平臺進(jìn)行了資源中心網(wǎng)絡(luò)仿真環(huán)境的搭建，對提出的策略進(jìn)行了仿真驗證。同時參考現(xiàn)有網(wǎng)絡(luò)傳輸中的LCE緩存策略和Prob緩存策略，結(jié)合LRU緩存替換策略[16]，在ndnSIM仿真平臺中，對上述策略的緩存性能進(jìn)行了比較評估。

由于真實環(huán)境中的網(wǎng)絡(luò)拓?fù)涫遣灰?guī)則的，因此，文中采用ER隨機(jī)拓?fù)鋱D，網(wǎng)絡(luò)節(jié)點數(shù)量為100個，節(jié)點均具備緩存能力。節(jié)點分為3類：用戶節(jié)點、服務(wù)器節(jié)點和中間節(jié)點。為了便于仿真，網(wǎng)絡(luò)傳輸過程中假設(shè)所有的節(jié)點都使用相同介質(zhì)SSD，即路由器緩存資源的成本為Pic=0.003。網(wǎng)絡(luò)傳輸過程中總的內(nèi)容文件數(shù)M=1 000個，資源熱門度模型滿足參數(shù)α=0.8的Zipf分布。資源訪問請求由用戶節(jié)點發(fā)出，節(jié)點請求的頻率服從λ=10req/s的泊松分布。為了便于性能分析，文中采用單徑路由進(jìn)行緩存策略仿真。

3.2 仿真結(jié)果

網(wǎng)絡(luò)傳輸仿真中，所有路由器的CS總?cè)萘渴侨績?nèi)容大小的1%，2%，3%，4%，5%，請求轉(zhuǎn)發(fā)方式選擇洪泛模式。每個CS都執(zhí)行PC、LCE和Prob（0.8）存儲策略的比較。當(dāng)緩存空間已滿時，使用平臺自帶的LRU替換策略，仿真時間為200 s。平均命中率如圖2所示。

圖2 平均命中率

在圖2中可以出，3種緩存策略的系統(tǒng)性能均隨著網(wǎng)絡(luò)節(jié)點緩存資源的增大而上升。在緩存資源較小時，節(jié)點緩存的內(nèi)容較少，用戶請求必須到源服務(wù)器才內(nèi)容發(fā)生命中，故節(jié)點 的命中率較低。隨著緩存資源美女的增大，路由器節(jié)點緩存的資源種類越多，因此服務(wù)器緩存節(jié)點的請求命中率增高。文中PCS呈現(xiàn)出比LCE與Prob（0.8）更加優(yōu)越的性能，LCE策略處處緩存造成網(wǎng)絡(luò)的緩存冗余度過高，Prob（0.8）緩存沒有考慮到資源的流行度，造成不流行的資源被緩存了。PCS緩存策略提高了高流行度資源模塊的緩存命中率，當(dāng)網(wǎng)內(nèi)緩存資源占資源總數(shù)的3%時，3種方案的命中率最高，這是因為PCS避免了LCE策略中高流行度資源的頻繁替換，保證了高流行度的資源緩存至離用戶最近的路由節(jié)點，從而大量減少源服 務(wù)器的負(fù)載和平均訪問跳數(shù)，平均跳數(shù)如圖3所示。

可從圖3顯示出，與LCE和prob（p）方案相比，PCS機(jī)制減少了用戶獲取資源的距離，保證了用戶請求能夠較快的獲取獲取，減小了用戶獲取資源的平均時延，有利于提高用戶的滿意度。同時，也符合了網(wǎng)絡(luò)傳輸將流行度高的資源推送至用戶邊緣區(qū)域的準(zhǔn)則，提高了網(wǎng)絡(luò)傳輸?shù)木彺嫘阅堋?/p>

4 結(jié)束語

本研究提出一種基于概率緩存策略（PCS）的網(wǎng)絡(luò)傳輸機(jī)制，實現(xiàn)了路由節(jié)點的緩存資源優(yōu)化配置，結(jié)合網(wǎng)絡(luò)拓?fù)涞牟町愋裕瑢⒏吡餍卸鹊馁Y源緩存至用戶接近的邊緣節(jié)點上，有效地減少資源在網(wǎng)絡(luò)傳輸過程中緩存冗余，提高了網(wǎng)絡(luò)傳輸過程中的緩存性能。仿真結(jié)果表明，該概率緩存策略可以有效的降低用戶訪問資源的平均時延，且避免非流行資源的不必要緩存，因此，提高網(wǎng)絡(luò)傳輸過程中的緩存性能。

圖3 平均跳數(shù)

[1]郁峰.軟件定義網(wǎng)絡(luò)架構(gòu)下的安全問題綜述[J].現(xiàn)代計算機(jī)，2014（16）:13-20.

[2]劉瓊，劉珍，黃敏.基于機(jī)器學(xué)習(xí)的IP流量分類研究[J].計算機(jī)科學(xué)，2010，37（12）:35-40.

[3]姚金成，張世棟，史玉良，等.基于Chunk Folding的多租戶數(shù)據(jù)庫緩存管理機(jī)制 [J].計算機(jī)學(xué)報，2011，34（12）:2319-2331.

[4]史玉良，王捷.一種多租戶云數(shù)據(jù)存儲緩存管理機(jī)制[J].計算機(jī)研究與發(fā)展，2014，51（11）:2528-2537.

[5]楊茂林，雷航，廖勇.一種共享資源敏感的實時任務(wù)分配算法[J].計算機(jī)學(xué)報，2014，37（7）:1455-1465.

[6]張國強(qiáng)，李楊，林濤，等.信息中心網(wǎng)絡(luò)中的內(nèi)置緩存技術(shù)研究[J].軟件學(xué)報，2014，25（1）:154-175.

[7]秦秀磊，張文博，魏峻，等.云計算環(huán)境下分布式緩存技術(shù)的現(xiàn)狀與挑戰(zhàn) [J].軟件學(xué)報，2013，24（1）:50-66.

[8]何智聰，谷光昭，王新，等.基于可重構(gòu)路由器上緩存的流媒體協(xié)作分發(fā)策略[J].通信學(xué)報，2012，33（6）:82-90.

[9]姜艷，曾學(xué)文，孫鵬.基于資源緩存的應(yīng)用快速切換技術(shù)[J].網(wǎng)絡(luò)新媒體技術(shù)，2013，2（4）:33-38.

[10]張全明，張新有.基于會話劫持的HTTP資源緩存系統(tǒng)設(shè)計[J].成都信息工程學(xué)院學(xué)報，2013，2（4）: 33-38.

[11]朱軼，糜正琨，王文鼐.一種基于內(nèi)容流行度的內(nèi)容中心網(wǎng)絡(luò)緩存概率置換策略[J].電子與信息學(xué)報，2013（6）:1305-1310.

[12]王道誼，周文安，劉元安.內(nèi)容分發(fā)網(wǎng)絡(luò)中內(nèi)容流行度集中性的研究[J].計算機(jī)工程與應(yīng)用，2011，47（6）:102-104.

[13]霍如，劉江，黃韜，等.基于相關(guān)性概率的信息中心網(wǎng)絡(luò)協(xié)作緩存策略[J].北京郵電大學(xué)學(xué)報，2015（1）:16-20.

[14]王家堯，王桂玲，張鵬.基于緩存的復(fù)合數(shù)據(jù)服務(wù)更新優(yōu)化方法 [J].微電子學(xué)與計算機(jī)，2013，30（3）:80-84.

[15]吳大鵬，張普寧，王汝言.帶有消息投遞概率估計的機(jī)會網(wǎng)絡(luò)自適應(yīng)緩存管理策略[J].電子與信息學(xué)報，2014（2）:390-395.

[16]曲樺，王偉萍，趙季紅.內(nèi)容中心網(wǎng)絡(luò)中一種改進(jìn)型緩存機(jī)制[J].計算機(jī)工程，2015（3）:41-46.

Research network transport mechanism based on probability caching strategy

CHANG Luo，XUE Nian
（Henan Medical College，Zhengzhou 451191，China）

For network transfer data cache resources to high popularity in the router，access to resources in order to improve the problem of transmission efficiency and resource utilization.In this study，to consider the impact of network topology cache，the use of network resources during transmission fixed period of popularity differences， combined with profit and the resource itself proposed network transmission scheme based on probability caching policy PCS（Probabilistic Caching strategy）of.By request of the resource data path probability cache to improve network transfer performance cache.The simulation shows that the cache policy effectively avoid unnecessary cache non-popular content，when the cache capacity is 5%，the average hit rate of 25%，the average number of hops is only 3.42，in favor of the overall performance of the transmission network upgrade.

probability cache；network transmission；resource value；popularity；cache hit ratio；the average number

TN393

：A

：1674-6236（2017）02-0159-04

2016-04-07稿件編號：201604073

國家自然科學(xué)基金（61372180）

常 珞（1975—），男，河南杞縣人，講師。研究方向：計算機(jī)科技。