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显示了在不同缓存大小下的延迟降低量。总的来说，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）