《电子技术应用》

一种基于网内缓存协助的缓存机制研究

2017年电子技术应用第5期 作者:刘 胜1,王江涛2
2017/6/21 13:02:00

刘  胜1,王江涛2

(1.四川中医药高等专科学校 信息中心,四川 绵阳621000;2.重庆邮电大学 软件工程学院,重庆400065)


    摘  要: 移动数据网络流量的大幅增长导致终端用户无法接受的延迟和移动运营商传输成本的大幅增长。为此,提出了基于网内缓存协助的eNodeB缓存机制,提高其缓存性能,以实现eNodeB在缓存中的高效应用的方法。通过网内缓存的信息优化eNodeB的本地缓存决策。通过从实际网络中采集到的真实流量数据,对所提出的缓存策略进行了实验验证。结果显示该机制能显著降低网络延迟和带宽消耗。

    关键词: 网内缓存;eNodeB;移动数据网络

    中图分类号: TN915;TP393

    文献标识码: 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),最后实施了基于真实流量数据的模拟和实验来验证本文提出的方法。

tx4-t1.gif

1 缓存分析

    针对eNodeB缓存数据的成本结构进行建模,从带宽和延迟两个角度对问题进行分析。

1.1 eNodeB缓存收益——带宽角度

1.1.1 传输成本

    令N代表eNodeB的总数,nj代表到达第j个eNodeB的请求;q为请求的内容对象的平均大小(即内容的字节数);成本要素R、G和T分別为:从用户设备到eNodeB每字节的传输成本、从eNodeB到PDN网关每字节的传输成本、移动运营商支付给其上游供应商网络的每字节的中转成本。

    请求服务的总成本为:

    tx4-gs1.gif

1.1.2 缓存收益

    以n作为在第j个eNodeB缓存中的内容对象数量,以U表示eNodeB中缓存对象的单位字节成本(如:CPU/系统总线使用花费、存储设备费用等)。由于eNodeB缓存的存在,移动运营商服务请求的成本的总和为以下三项相加:(1)所请求的对象从源服务器时的传输成本;(2)从UE到缓存eNodeB的网络路径所产生的成本;(3)在eNodeB上缓存对象的额外成本。当eNodeB缓存存在时,网络传输的成本为:

     tx4-gs2-4.gif

    现将式(4)进行简化,以便对eNodeB缓存的收益进行更直观的理解。假定T=10U,由缓存带来的费用节省占总费用的百分比变成以下两个参数的函数:

    (1)R/U,无线链路成本与缓存成本之比;

    (2)G/U,从eNodeB到PGW的链路成本与缓存成本之比。

    将不同的取值赋予上述两个参数时,缓存成本的节省百分比的变化如表1所示。

tx4-b1.gif

    以上结果表明,在这些研究案例中,从经济学角度讲,如果无线链路成本不占主导地位,那么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可以选择具有最小延迟的一个。

tx4-gs5-6.gif

    于是优化问题可表述为,当系统中存在网内缓存时,给定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

     tx4-4-s1.gif

    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为网络直径。

tx4-b2.gif

4.2 模拟结果

    首先观测在eNodeB具有不同的缓存大小时上述策略的性能。通过改变总对象大小,观察在单个eNodeB缓存从总内容大小的10%增长到60%的过程中,上述策略的性能变化。分别在真实场景和合成场景中随机选取了7台和30台协作路由器,通过固定缓存大小及改变协作路由器比例从0%增长到100%的过程,研究不同策略的性能。进行20次相互独立的模拟测试,将这20次模拟结果的平均值作为最终的评估结果。

    (1)延迟降低量

    图2显示了在不同缓存大小下的延迟降低量。总的来说,IAECM性能最佳,显著地降低了系统延迟。在存在网内缓存的条件下,IAECM的性能优于LRU。这是因为网络越大,缓存性能的累计差距越明显。因此,推断IAECM在大规模网络下会有相当好的性能。

tx4-t2.gif

    (2)带宽节省量

    图3显示了PGW接收到的平均请求数。可以看出,IAECM显著地节省了网络带宽。例如,当eNodeB的缓存大小为30%时,IAECM降低了 PGW 端收到的60%的对象请求数量。从带宽角度看来,LRU要比IAECM的性能稍微好一点。因此,IAECM可能选择缓存能够显著降低延迟却对节省带宽并非最优选择的对象。考虑到整体性能,认为IAECM是更好的选择。

tx4-t3.gif

    (3)协作路由器数量的影响

    图4显示了协作路由器数量将如何影响IAECM的性能。首先,协作路由器越多,IAECM的性能就越好。当协作路由器数量从0增长到100时,延迟降低提高了29%。其次,少量的协作路由器会比较显著地提高eNodeB的缓存性能。

tx4-t4.gif

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.

继续阅读>>