0 引言

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

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

1 緩存分析

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

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

1.1.1 傳輸成本

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

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

1.1.2 緩存收益

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

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

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

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

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

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

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

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

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

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

    首先建立問題的形式化描述。假設(shè)系統(tǒng)中有M個內(nèi)容，分別為C₁，C₂，…，C_M，其大小分別為s₁，s₂，…，s_M。假設(shè)網(wǎng)絡(luò)中包括N個eNodeB，分別為eNodeB₁，eNodeB₂，…，eNodeB_N，定義以上eNodeB所對應(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ò)中有多個路由器均保存有內(nèi)容的副本，那么eNodeB可以選擇具有最小延遲的一個。

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

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

    使用算法1作為算法組成單元，并將其與傳統(tǒng)的LRU結(jié)合起來以建立IAECM緩存策略。對每一個內(nèi)容對象設(shè)置了一個緩存收益值(BV)。在IAECM中，對其定義進行擴展。如果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維持一個LRU隊列。

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

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

    (2)算法2：IAECM

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

4 性能評估

4.1 評估方法

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

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

4.2 模擬結(jié)果

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

    (1)延遲降低量

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

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

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

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

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

5 結(jié)論

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

參考文獻

[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信號檢測的研究與實現(xiàn)[J].電子技術(shù)應(yīng)用，2016，42(6)：74-76，80.

作者信息:

劉  勝1，王江濤2

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