0 引言

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

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

1 緩存分析

    針對eNodeB緩存數據的成本結構進行建模，從帶寬和延遲兩個角度對問題進行分析。

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

1.1.1 傳輸成本

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

    請求服務的總成本為：

1.1.2 緩存收益

    以n作為在第j個eNodeB緩存中的內容對象數量，以U表示eNodeB中緩存對象的單位字節成本(如：CPU/系統總線使用花費、存儲設備費用等)。由于eNodeB緩存的存在，移動運營商服務請求的成本的總和為以下三項相加：(1)所請求的對象從源服務器時的傳輸成本；(2)從UE到緩存eNodeB的網絡路徑所產生的成本；(3)在eNodeB上緩存對象的額外成本。當eNodeB緩存存在時，網絡傳輸的成本為：

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

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

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

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

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

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

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

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

2 基于網內緩存輔助的eNodeB緩存

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

    于是優化問題可表述為，當系統中存在網內緩存時，給定eNodeB_j的緩存能力B_j，指定x_ij以實現式(6)中BF值的最大化。

3 網內緩存輔助的eNodeB緩存（IAECM）

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

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

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

    (2)算法2：IAECM

    IAECM具有以下特點：①若沒有任何網內緩存信息，IAECM就簡化為常規的LRU算法；②在有完整的網內緩存信息的情況下，IAECM轉化為算法1；③在eNodeB只能獲得部分網內緩存信息的情況下，IAECM可以獲得比LRU顯著優越的性能。

4 性能評估

4.1 評估方法

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

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

4.2 模擬結果

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

    (1)延遲降低量

    圖2顯示了在不同緩存大小下的延遲降低量?？偟膩碚f，IAECM性能最佳，顯著地降低了系統延遲。在存在網內緩存的條件下，IAECM的性能優于LRU。這是因為網絡越大，緩存性能的累計差距越明顯。因此，推斷IAECM在大規模網絡下會有相當好的性能。

    (2)帶寬節省量

    圖3顯示了PGW接收到的平均請求數?？梢钥闯?，IAECM顯著地節省了網絡帶寬。例如，當eNodeB的緩存大小為30%時，IAECM降低了 PGW 端收到的60%的對象請求數量。從帶寬角度看來，LRU要比IAECM的性能稍微好一點。因此，IAECM可能選擇緩存能夠顯著降低延遲卻對節省帶寬并非最優選擇的對象。考慮到整體性能，認為IAECM是更好的選擇。

    (3)協作路由器數量的影響

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

5 結論

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

參考文獻

[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系統中PRACH信號檢測的研究與實現[J].電子技術應用，2016，42(6)：74-76，80.

作者信息:

劉  勝1，王江濤2

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