文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2017.05.029
中文引用格式： 劉勝，王江濤. 一種基于網內緩存協助的緩存機制研究[J].電子技術應用，2017，43(5)：119-122.
英文引用格式： Liu Sheng，Wang Jiangtao. Research on cache mechanism based on in-network cache assist[J].Application of Electronic Technique，2017，43(5)：119-122.
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的總數，nj代表到達第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個內容，分別為C1，C2，…，CM，其大小分別為s1，s2，…，sM。假設網絡中包括N個eNodeB，分別為eNodeB1，eNodeB2，…，eNodeBN，定義以上eNodeB所對應的緩存的大小(單位為MB)分別為B1，B2，…，Bn。令dj(ci)表示傳輸Ci的延遲值，其路徑為從Ci的位置(網內緩存或是Ci提供者)到eNodeBj。需要注意的是，框架內的eNodeB可以獲取路由器緩存狀態和路由器延遲。因此，eNodeB可以推斷出dj(ci)。如果在網絡中有多個路由器均保存有內容的副本，那么eNodeB可以選擇具有最小延遲的一個。
于是優化問題可表述為，當系統中存在網內緩存時，給定eNodeBj的緩存能力Bj，指定xij以實現式(6)中BF值的最大化。
3 網內緩存輔助的eNodeB緩存（IAECM）
使用算法1作為算法組成單元，并將其與傳統的LRU結合起來以建立IAECM緩存策略。對每一個內容對象設置了一個緩存收益值(BV)。在IAECM中，對其定義進行擴展。如果eNodeBj有內容ci的網內緩存信息，則BVj(ci)=dj(ci)pj(ci)/s。算法2使用偽代碼的方式描述eNodeB維持一個LRU隊列。
(1)算法1：離線貪心算法
當一個沒有被緩存的內容對象ci到達eNodeB時，eNodeB計算其單位收益值。如果ci的單位收益值大于當前在eNodeB緩存中的具有最小單位收益值的內容的單位收益值(假設為cj)，且移除cj后緩存中有足夠的空間存儲ci應立即存儲，則使用ci替換掉cj。
(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顯示了在不同緩存大小下的延遲降低量。總的來說，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）