0 引言

    近年來，移動(dòng)數(shù)據(jù)網(wǎng)絡(luò)經(jīng)歷了飛速發(fā)展。有預(yù)測(cè)表明，無線移動(dòng)數(shù)據(jù)流量在未來有望比現(xiàn)在增漲40倍^[1]。這雖然帶來了巨大的商機(jī)，但是也帶來了一些嚴(yán)峻的問題^[2-3]：(1)對(duì)終端用戶造成無法接受的延遲；(2)對(duì)移動(dòng)運(yùn)營(yíng)商造成爆炸式增長(zhǎng)的傳輸成本。

    本文提出了一種網(wǎng)內(nèi)緩存協(xié)助的eNodeB的緩存機(jī)制(In-network Assisted eNodeB Caching Mechanism，IAECM)，以應(yīng)對(duì)LTE網(wǎng)絡(luò)中的流量問題^[4-5]。目標(biāo)是為移動(dòng)運(yùn)營(yíng)商節(jié)省帶寬成本，并為終端用戶縮短網(wǎng)絡(luò)延遲^[6-7]。圖1提供了一種有效的網(wǎng)內(nèi)緩存協(xié)助的eNodeB緩存框架?；谔岢龅目蚣?，本文將eNodeB緩存問題進(jìn)行形式化，設(shè)計(jì)了一種能夠應(yīng)用于實(shí)際網(wǎng)絡(luò)的在線網(wǎng)內(nèi)緩存協(xié)助eNodeB的緩存算法（IAECM)，最后實(shí)施了基于真實(shí)流量數(shù)據(jù)的模擬和實(shí)驗(yàn)來驗(yàn)證本文提出的方法。

1 緩存分析

    針對(duì)eNodeB緩存數(shù)據(jù)的成本結(jié)構(gòu)進(jìn)行建模，從帶寬和延遲兩個(gè)角度對(duì)問題進(jìn)行分析。

1.1 eNodeB緩存收益——帶寬角度

1.1.1 傳輸成本

    令N代表eNodeB的總數(shù)，n_j代表到達(dá)第j個(gè)eNodeB的請(qǐng)求；q為請(qǐng)求的內(nèi)容對(duì)象的平均大小(即內(nèi)容的字節(jié)數(shù))；成本要素R、G和T分別為：從用戶設(shè)備到eNodeB每字節(jié)的傳輸成本、從eNodeB到PDN網(wǎng)關(guān)每字節(jié)的傳輸成本、移動(dòng)運(yùn)營(yíng)商支付給其上游供應(yīng)商網(wǎng)絡(luò)的每字節(jié)的中轉(zhuǎn)成本。

    請(qǐng)求服務(wù)的總成本為：

1.1.2 緩存收益

    以n作為在第j個(gè)eNodeB緩存中的內(nèi)容對(duì)象數(shù)量，以U表示eNodeB中緩存對(duì)象的單位字節(jié)成本(如：CPU/系統(tǒng)總線使用花費(fèi)、存儲(chǔ)設(shè)備費(fèi)用等)。由于eNodeB緩存的存在，移動(dòng)運(yùn)營(yíng)商服務(wù)請(qǐng)求的成本的總和為以下三項(xiàng)相加：(1)所請(qǐng)求的對(duì)象從源服務(wù)器時(shí)的傳輸成本；(2)從UE到緩存eNodeB的網(wǎng)絡(luò)路徑所產(chǎn)生的成本；(3)在eNodeB上緩存對(duì)象的額外成本。當(dāng)eNodeB緩存存在時(shí)，網(wǎng)絡(luò)傳輸?shù)某杀緸椋?/p>

    現(xiàn)將式(4)進(jìn)行簡(jiǎn)化，以便對(duì)eNodeB緩存的收益進(jìn)行更直觀的理解。假定T=10U，由緩存帶來的費(fèi)用節(jié)省占總費(fèi)用的百分比變成以下兩個(gè)參數(shù)的函數(shù)：

    (1)R/U，無線鏈路成本與緩存成本之比；

    (2)G/U，從eNodeB到PGW的鏈路成本與緩存成本之比。

    將不同的取值賦予上述兩個(gè)參數(shù)時(shí)，緩存成本的節(jié)省百分比的變化如表1所示。

    以上結(jié)果表明，在這些研究案例中，從經(jīng)濟(jì)學(xué)角度講，如果無線鏈路成本不占主導(dǎo)地位，那么eNodeB緩存會(huì)帶來良好的經(jīng)濟(jì)收益。

1.2 eNodeB緩存收益——延遲角度

    eNodeB緩存為網(wǎng)絡(luò)帶來的另一個(gè)好處是減小用戶端的延遲。延遲角度和帶寬角度主要存在以下2個(gè)不同點(diǎn)：(1)網(wǎng)絡(luò)上游傳輸成本并不會(huì)影響終端用戶的延遲；(2)PGW和網(wǎng)絡(luò)之間的延遲值應(yīng)該納入到緩存收益的評(píng)價(jià)系統(tǒng)中。

    通過eNodeB緩存得到的收益取決于從UE到內(nèi)容提供端的數(shù)據(jù)路徑的特性。假設(shè)無線鏈路和回程鏈路具有相同的延遲。假設(shè)從PGW到內(nèi)容的路徑延遲是無線鏈路的3倍。假設(shè)eNodeB的緩存率為40%。應(yīng)用1.1中相同的方法可以得出，相對(duì)于沒有緩存的情況，eNodeB能夠減少34%的延遲。

2 基于網(wǎng)內(nèi)緩存輔助的eNodeB緩存

    首先建立問題的形式化描述。假設(shè)系統(tǒng)中有M個(gè)內(nèi)容，分別為C₁，C₂，…，C_M，其大小分別為s₁，s₂，…，s_M。假設(shè)網(wǎng)絡(luò)中包括N個(gè)eNodeB，分別為eNodeB₁，eNodeB₂，…，eNodeB_N，定義以上eNodeB所對(duì)應(yīng)的緩存的大小(單位為MB)分別為B₁，B₂，…，B_n。令d_j(c_i)表示傳輸C_i的延遲值，其路徑為從C_i的位置(網(wǎng)內(nèi)緩存或是C_i提供者)到eNodeB_j。需要注意的是，框架內(nèi)的eNodeB可以獲取路由器緩存狀態(tài)和路由器延遲。因此，eNodeB可以推斷出d_j(c_i)。如果在網(wǎng)絡(luò)中有多個(gè)路由器均保存有內(nèi)容的副本，那么eNodeB可以選擇具有最小延遲的一個(gè)。

    于是優(yōu)化問題可表述為，當(dāng)系統(tǒng)中存在網(wǎng)內(nèi)緩存時(shí)，給定eNodeB_j的緩存能力B_j，指定x_ij以實(shí)現(xiàn)式(6)中BF值的最大化。

3 網(wǎng)內(nèi)緩存輔助的eNodeB緩存（IAECM）

    使用算法1作為算法組成單元，并將其與傳統(tǒng)的LRU結(jié)合起來以建立IAECM緩存策略。對(duì)每一個(gè)內(nèi)容對(duì)象設(shè)置了一個(gè)緩存收益值(BV)。在IAECM中，對(duì)其定義進(jìn)行擴(kuò)展。如果eNodeB_j有內(nèi)容c_i的網(wǎng)內(nèi)緩存信息，則BV_j(c_i)=d_j(c_i)p_j(c_i)/s。算法2使用偽代碼的方式描述eNodeB維持一個(gè)LRU隊(duì)列。

    (1)算法1：離線貪心算法

    當(dāng)一個(gè)沒有被緩存的內(nèi)容對(duì)象c_i到達(dá)eNodeB時(shí)，eNodeB計(jì)算其單位收益值。如果c_i的單位收益值大于當(dāng)前在eNodeB緩存中的具有最小單位收益值的內(nèi)容的單位收益值(假設(shè)為c_j)，且移除c_j后緩存中有足夠的空間存儲(chǔ)c_i應(yīng)立即存儲(chǔ)，則使用c_i替換掉c_j。

    (2)算法2：IAECM

    IAECM具有以下特點(diǎn)：①若沒有任何網(wǎng)內(nèi)緩存信息，IAECM就簡(jiǎn)化為常規(guī)的LRU算法；②在有完整的網(wǎng)內(nèi)緩存信息的情況下，IAECM轉(zhuǎn)化為算法1；③在eNodeB只能獲得部分網(wǎng)內(nèi)緩存信息的情況下，IAECM可以獲得比LRU顯著優(yōu)越的性能。

4 性能評(píng)估

4.1 評(píng)估方法

    本節(jié)運(yùn)用NS-3來進(jìn)行模擬評(píng)估。首先使用商業(yè)網(wǎng)絡(luò)的真實(shí)流量數(shù)據(jù)來評(píng)估IAECM的性能及不同參數(shù)設(shè)置帶來的影響。商業(yè)網(wǎng)絡(luò)的流量數(shù)據(jù)來自于從2016年的3月10日～3月16日的數(shù)據(jù)采集， 共包含來自620 324名用戶的1 324 741個(gè)網(wǎng)頁(yè)請(qǐng)求。網(wǎng)頁(yè)的流行程度呈Zipf分布，網(wǎng)頁(yè)的大小平均為1.87 MB，字節(jié)數(shù)達(dá)到2 477 GB。手機(jī)流量數(shù)據(jù)來自于中國(guó)移動(dòng)的一個(gè)省級(jí)4G網(wǎng)絡(luò)的NodeB，在該NodeB上進(jìn)行了2 h的數(shù)據(jù)采集。手機(jī)流量包括91 320個(gè)HTTP請(qǐng)求。

    使用兩個(gè)IP網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行模擬實(shí)驗(yàn)，分別為真實(shí)的網(wǎng)絡(luò)拓?fù)銫ERNET2和計(jì)算機(jī)生成的網(wǎng)絡(luò)拓?fù)洹Ｔ谟?jì)算機(jī)生成的拓?fù)浣Y(jié)構(gòu)中，采用了一個(gè)由BRITE生成的100節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)。路由器之間的鏈路延遲在10 ms～20 ms之間隨機(jī)分布。表2總結(jié)了兩個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)特征，其中E/V表示網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)間的鏈路數(shù)量比，D為網(wǎng)絡(luò)直徑。

4.2 模擬結(jié)果

    首先觀測(cè)在eNodeB具有不同的緩存大小時(shí)上述策略的性能。通過改變總對(duì)象大小，觀察在單個(gè)eNodeB緩存從總內(nèi)容大小的10%增長(zhǎng)到60%的過程中，上述策略的性能變化。分別在真實(shí)場(chǎng)景和合成場(chǎng)景中隨機(jī)選取了7臺(tái)和30臺(tái)協(xié)作路由器，通過固定緩存大小及改變協(xié)作路由器比例從0%增長(zhǎng)到100%的過程，研究不同策略的性能。進(jìn)行20次相互獨(dú)立的模擬測(cè)試，將這20次模擬結(jié)果的平均值作為最終的評(píng)估結(jié)果。

    (1)延遲降低量

    圖2顯示了在不同緩存大小下的延遲降低量。總的來說，IAECM性能最佳，顯著地降低了系統(tǒng)延遲。在存在網(wǎng)內(nèi)緩存的條件下，IAECM的性能優(yōu)于LRU。這是因?yàn)榫W(wǎng)絡(luò)越大，緩存性能的累計(jì)差距越明顯。因此，推斷IAECM在大規(guī)模網(wǎng)絡(luò)下會(huì)有相當(dāng)好的性能。

    (2)帶寬節(jié)省量

    圖3顯示了PGW接收到的平均請(qǐng)求數(shù)?？梢钥闯?，IAECM顯著地節(jié)省了網(wǎng)絡(luò)帶寬。例如，當(dāng)eNodeB的緩存大小為30%時(shí)，IAECM降低了 PGW 端收到的60%的對(duì)象請(qǐng)求數(shù)量。從帶寬角度看來，LRU要比IAECM的性能稍微好一點(diǎn)。因此，IAECM可能選擇緩存能夠顯著降低延遲卻對(duì)節(jié)省帶寬并非最優(yōu)選擇的對(duì)象。考慮到整體性能，認(rèn)為IAECM是更好的選擇。

    (3)協(xié)作路由器數(shù)量的影響

    圖4顯示了協(xié)作路由器數(shù)量將如何影響IAECM的性能。首先，協(xié)作路由器越多，IAECM的性能就越好。當(dāng)協(xié)作路由器數(shù)量從0增長(zhǎng)到100時(shí)，延遲降低提高了29%。其次，少量的協(xié)作路由器會(huì)比較顯著地提高eNodeB的緩存性能。

5 結(jié)論

    本文提出了一項(xiàng)網(wǎng)內(nèi)緩存協(xié)助下的eNodeB緩存機(jī)制。首先，提出了—個(gè)系統(tǒng)框架，在這個(gè)框架中eNodeB緩存的性能可通過接收來自網(wǎng)內(nèi)緩存的信息得以提升；然后，對(duì)問題進(jìn)行形式化描述并研究其復(fù)雜性；最后，設(shè)計(jì)了一種切實(shí)可行的網(wǎng)內(nèi)緩存協(xié)助的eNodeB緩存算法。本文使用真實(shí)的流量數(shù)據(jù)對(duì)算法的性能進(jìn)行了綜合評(píng)估，結(jié)果顯示本方法具有優(yōu)良的性能。

參考文獻(xiàn)

[1] CHLEBUS A，BRAZIER J.Nonstationary poisson mod eling of web browsing session arrivals[J].Information Processing Letters，2007，102(5)：187-190.

[2] ERMAN J，GERBER A，HAJIAGHAYI M T，et al.Cache or not to cache：The 3G case[J].IEEE Internet Computing，2011，15(6)：27-34.

[3] Che Hao，Wang Zhijung，Tung Ye.Analysis and design of hierarchical web caching systems[C].Proceedings of the IEEE INFOCOM，2011.

[4] NI J，TSANG D H K.Large-scale cooperative caching and application-level multicast in multimedia content delivery networks[J].IEEE Commun.Mag.，2015，23(5)：27-41.

[5] BAEV I D，RAJARAMAN R，SWAMY C.Approximation algorithms for data placement problems[J].SIAM J.Comput，2008，33(3)：1411-1429.

[6] SARKAR P，HARTMAN J H.Hint-based cooperative caching[J].ACM Trans.Comp.Syst.，2015，27(7)：2421-2429.

[7] 許虎，林藝輝，劉小剛.LTE-A系統(tǒng)中PRACH信號(hào)檢測(cè)的研究與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2016，42(6)：74-76，80.

作者信息:

劉  勝1，王江濤2

(1.四川中醫(yī)藥高等專科學(xué)校 信息中心，四川 綿陽(yáng)621000；2.重慶郵電大學(xué) 軟件工程學(xué)院，重慶400065）