褚伟波,王丽芳,蒋泽军,范刚龙

(1.西北工业大学计算机学院,710072,西安; 2.洛阳师范学院电子商务学院,471934,河南洛阳;3.洛阳师范学院河南省电子商务大数据处理与分析重点实验室,471934,河南洛阳)

随着各类社交网络以及在线视频网站等应用的流行,网络流量呈现出爆炸式增长趋势[1-2]。未来几年内,以图片、视频、音频等为代表的多媒体内容传输引起的流量还将持续快速增长[3],从而给现有互联网带来前所未有的压力。

网络缓存是解决大规模内容传输性能瓶颈的重要手段。当前普遍采用的内容分发网络(CDN)[4-5]通过在网络边缘部署大量内容缓存服务器把内容就近推送给用户,避开影响数据传输速度和稳定性的瓶颈。近些年提出的内容中心网络(ICN)[6-8]更是将缓存作为网络基础设施的一部分,通过在路由器、交换机上直接部署大容量高速缓存来减轻网络负载和内容服务器的压力,提高终端用户体验。

作为一种重要的基础资源,网络缓存在提升网络性能方面发挥着重要作用。如同IP网络中针对用户的带宽资源分配和管理对于现有互联网的基础作用一样,网络缓存资源的分配与管理是未来网络研究中的一个基础问题。本文对网络边缘TTL(time-to-live)缓存的计费模型与存储策略进行了研究,提出了基于内容文件缓存命中速率以及内容文件缓存逗留时间的2种TTL缓存计费模型。将TTL缓存的定价与存储策略问题建模成一个2层的Stackelberg博弈模型[9],并在文件请求到达过程为泊松过程的情况下,分别求解在均一定价和差异定价策略下系统的最优缓存价格以及对应的内容文件缓存时间。利用仿真实验进一步对比了在不同定价策略和计费模型下缓存服务提供商获得的投资回报以及内容提供商产生的收益,得到了一些重要结论。提出的模型和得到的结果对于规范网络缓存市场、激励缓存服务提供商、提升网络服务质量以及确保用户和应用的公平性等多方面具有重要意义。

1 TTL缓存性能分析

网络缓存通常可以分为内容替换型(replacement-based)缓存和基于TTL缓存2种。内容替换型缓存在一个新的文件到达而又无空余空间时,依据一定的策略(例如LRU、FIFO、RANDOM等)将现有缓存中的文件替换出去;TTL缓存则为每个新到达的内容文件设定一个缓存时间,当缓存时间用完再将内容替换出去。与内容替换型缓存比较,TTL缓存通过对单个内容文件的缓存时间进行设置,不仅可以更加细粒度地控制内容的访问行为,同时也极大地方便了对缓存性能进行数学分析。

TTL缓存在实现时又可以分成2类。一类是Non-reset TTL缓存,如图1所示。在这类缓存中,每个内容文件的TTL值在缓存期间保持不变。任何在文件缓存期间到达的请求都会产生一次缓存命中(cache hit),否则产生一次缓存命中失败(cache miss)。另外一类是Reset TTL缓存,这类缓存中每个文件Fi的TTL值Ti会在每次缓存命中时被重新设置,如图2所示。对于TTL缓存,通常关注任意文件Fi的如下性能指标:①缓存命中概率(hit probability),表示每一次Fi的请求到来时文件Fi正好存在于缓存中的概率,记为Hi;②文件缓存概率(file occupancy),表示任意时刻Fi存在于缓存中的概率,记为Oi;③缓存逗留时间(sojourn time),表示每一次文件Fi被缓存后存在于缓存中的时间,记为Qi。在Reset TTL缓存中,Qi为一随机变量,用E[Qi]表示平均逗留时间。

图1 Non-reset TTL缓存示意图(单个文件Fi缓存过程)

图2 Reset TTL缓存示意图(单个文件Fi缓存过程)

对于TTL缓存,若文件之间相互独立且每个文件的请求到达过程为泊松过程,有如下关系成立[10-12]

Hi=Oi

(1)

(2)

式中:Ti表示文件Fi的TTL值;λi为Fi请求到达速率。以上公式表明,若已知文件Fi的缓存命中概率Hi,则可以根据式(2)求得Fi在不同类型缓存中的TTL值Ti,本文就是通过求取文件的缓存命中概率来设置它们对应的缓存时间。

2 问题描述和系统建模

2.1 问题描述

考虑一个在网络边缘部署了容量为C(可容纳内容文件数)的TTL高速缓存的自治系统,该缓存被系统中所有用户共享。记用户访问的内容文件集合为F={F1,F2,…,FN},Fi代表一个内容文件。用户对于单个文件的请求会先到达TTL高速缓存,若请求文件在缓存中,则产生一次缓存命中,这时目标文件直接从缓存返回给用户;否则,产生一次缓存命中失败,目标文件从远端内容服务器取回,然后再返回给用户。为了使用缓存服务来提高内容传输性能,视频、社交网络等内容提供商需要向缓存服务提供商支付一定的缓存使用费用。一般情况下,缓存服务提供商可以向内容提供商发布其缓存服务的价格,由内容提供商决定每个内容文件的缓存时间,缓存服务提供商按照一定标准向内容提供商收取费用。在这样的模型下,需要解决以下3个问题:①计费机制,即缓存服务提供商对其缓存服务计费的标准或依据是什么?②定价问题,即缓存服务的价格是多少?③存储策略,即内容提供商每个内容文件的缓存时间是多少?

针对上述问题中的第1个问题,本文提出基于内容文件缓存命中速率和内容文件缓存逗留时间的缓存服务计费机制。内容文件缓存命中速率刻画了单位时间内用户访问一个内容文件产生的缓存命中次数,它从流量(或带宽)的角度刻画了资源占用情况;内容文件缓存逗留时间刻画了一个内容文件在缓存中存在时间的长短,它从存储空间利用的角度描述了资源占用情况。显然,这是2种基于实际资源使用的计费标准。对于包括互联网带宽在内的多项经济学研究[13-15]表明,对于服务提供商来说,基于实际资源使用状况的计费策略往往能够达到更高的资源利用效率以及投资回报。

2.2 系统建模

为简化分析,作如下假设:每个内容文件的大小相同,实际中若内容文件大小不一,则可将其分割成多个固定大小的基本文件块,把每个文件块当作一个内容文件;与内容文件的缓存时间相比,目标文件从远端内容服务器下载所需时间可忽略不计;用户访问每个内容文件的请求过程为一泊松过程。

由于请求过程为泊松过程,可知Hi=Oi。λiHi为文件Fi的缓存命中速率。此外,假定内容提供商关于每个文件Fi的效益函数是一个关于其缓存命中速率λiHi的连续凹增长函数Ui(λiHi)=wiln(1+λiHi),其中wi为权重系数,反映文件Fi的重要性。在资源分配和管理中,广泛使用log函数表示效用[16]。

将TTL缓存服务计费与存储策略问题建模成一个2层的Stackelberg博弈模型[9]:在高层,缓存服务提供商设定一定的缓存价格,使其回报最大;在底层,假定内容提供商是理性的,其根据缓存服务提供商设定的价格设置相应的文件缓存时间,使得自己的收益最大。在Stackelberg博弈模型中,上层参与者具有领导权,因此整个博弈的目标就是使得缓存服务提供商的回报最大化。下面,分别对2种缓存服务计费机制和存储策略在差异定价和均一定价的情况下进行讨论。差异定价指缓存服务提供商可以对不同文件发布不同的缓存价格,而均一定价指所有文件具有相同的缓存价格。

3 TTL缓存服务计费机制与存储策略

3.1 基于内容文件缓存命中速率的计费机制和存储策略

(3)

缓存服务提供商获得的回报是内容提供商使用缓存的费用,因此它的决策问题可建模成以下优化问题②

(4)

定理1给定缓存价格,内容提供商的决策问题具有唯一的全局最优解。

证明显然,问题①的目标函数是其决策变量Hi的凹函数。由于Oi=Hi,问题①的约束表明其决策变量空间是一凸集。因此,问题①是一个凸优化问题,存在唯一的全局最优解。

以上结论在泊松请求到达过程的假设下,对于基于缓存命中速率的均一定价策略以及基于缓存逗留时间的均一定价和差异定价策略下均成立,后面将不再赘述。

采用文献[17]中Stackelberg模型的求解方法,可以得到如下定理。

(5)

(6)

内容提供商关于文件Fi的最优缓存命中概率为

(7)

定理2揭示了以下物理意义:在基于缓存命中速率的差异定价策略下,若文件Fi的请求速率λi越大,则其最优缓存命中概率也越大(见式(7)),对应需要的缓存时间也越多。这意味着TTL缓存倾向于存储那些热度比较大的文件。若文件的请求速率一定,Fi的最优缓存价格与其权重系数wi成正比(见式(5),即缓存服务提供商应该对重要的文件收取较高的费用。

3.1.2 均一定价 在均一定价策略下,所有文件具有相同的单位缓存命中速率价格,用Kh表示。内容提供商的决策问题可描述为如下优化问题③

(8)

缓存服务提供商的决策问题④描述如下

(9)

考察内容提供商关于任意文件Fi的收益函数wiln(1+λiHi)-KhλiHi。该函数为凹函数,令Hi(Kh)为使该函数最大化时Hi的取值,得到以下结果

(10)

步骤1将区间(0,wmax]等分成M份,由此得到一系列Kh可能的取值区间,其中M为一较大正整数;

步骤2对于第i个区间[xi,xi+1],计算缓存服务提供商获得的回报Rh,u(xi)和Rh,u(xi+1);

步骤4比较所有区间上下界,选择最大回报可能位于的区间,再将这些选择的区间进行细分;

对比基于缓存命中速率的2种定价策略,发现在差异定价策略下,内容提供商关于文件Fi的最优缓存命中概率只与文件请求速率相关(见式(7)),而在均一定价策略下权重系数wi会影响到文件Fi的最优缓存命中速率。此外,由于实际应用中文件的缓存逗留时间只能在缓存端进行测量,而缓存命中速率可以在用户端直接测量,因此在相同或相近投资回报的情况下,缓存服务提供商应优先采用基于内容文件缓存命中速率的计费机制。

3.2 基于缓存逗留时间的计费机制和存储策略

3.2.1 差异定价 假定Ki,s为缓存服务提供商发布的关于文件Fi的单位缓存逗留时间价格。由于只有当请求命中失败时,文件才会被重新缓存(见图1和图2),因此,文件Fi的缓存费用为Ki,sλi(1-Hi)E[Qi]。根据律特法则(Little’s law)[6]可知,Oi=λi(1-Hi)E[Qi]。内容提供商的决策问题⑤可描述如下

(11)

缓存服务提供商决策问题变为以下优化问题⑥

(12)

证明已知Oi=Hi。对比问题①②和问题⑤⑥,若再令Ki,s=Ki,hλi,则2个问题完全重合。因此,它们具有相同的最优解。

定理3揭示了如下物理意义:在泊松请求到达的情况下,对于缓存服务提供商来说,基于缓存逗留时间的差异定价策略与基于缓存命中速率的差异定价策略两者在投资回报和存储策略方面没有任何差别,因此考虑缓存命中速率在用户端容易测量的原因,缓存服务提供商在差异定价策略下,应优先采用基于缓存命中速率的计费机制。

3.2.2 均一定价 假定Ks为缓存服务提供商发布的关于内容文件的单位缓存逗留时间价格。内容提供商的决策问题⑦可描述如下

(13)

缓存服务提供商的决策问题⑧描述如下

(14)

采用与基于内容文件缓存命中速率的均一定价策略相同的分析方法和类似求解方法,可以求解内容文件的最优单位缓存逗留时间价格和缓存服务提供商获得的最优投资回报,具体分析过程和算法不再赘述。

4 实验验证

利用计算机仿真方法对本文模型和策略的有效性进行验证,并对不同模型和策略进行对比。采用Mosek优化软件求解在均一定价策略下内容提供商的决策问题③和⑦,并根据求解结果设置不同文件需要的缓存时间。采用定理2中的解析结果选取差异定价策略下的缓存价格和对应的文件缓存时间。实验过程中假定内容提供商可供访问的文件数为1 000个,用户对于这些文件的访问请求为一速率为105s-1的泊松过程,文件热度服从参数为0.8的Zipf分布。此外,设置网络边缘TTL缓存大小为50(即可容纳5%的文件数)。实验过程中同时记录缓存服务提供商得到的回报以及内容提供商获得的收益。

表1给出了缓存系统在文件权重系数相同的条件下(w1=w2=…=wN=1),不同策略的实验结果,从中可以看出:①在权重系数相同的条件下,基于缓存命中速率、缓存逗留时间的差异定价策略性能优于基于缓存命中速率、缓存逗留时间的均一定价策略,反映出差异定价策略能更好地利用文件在访问请求热度方面的差异来提升系统性能;②在基于缓存命中速率、缓存逗留时间的差异定价策略以及基于缓存逗留时间均一定价策略下,内容提供商获得的收益显著大于缓存服务提供商得到的回报,而在基于缓存命中速率的均一定价策略下,缓存服务提供商得到的回报高于内容提供商获得的收益;③对于缓存服务提供商来说,基于缓存命中速率的均一定价策略相比较基于缓存逗留时间均一定价策略能带来更多的回报,而对于内容提供商来说,基于缓存逗留时间的均一定价策略则比基于缓存命中速率均一定价策略能带来更多的收益;④由于获得的收益和回报均为正值,在实际应用中内容提供商和缓存服务提供商都会有采纳这些策略的动机和意愿。考虑到缓存命中速率能够在用户端进行测量而缓存逗留时间只能在缓存中测量,缓存服务提供商和内容提供商应优先采用基于缓存命中速率的差异定价策略。

实验中同时考察了文件权重系数不同情况下的系统性能。为此,假定内容提供商的文件按照其重要性随机分成重要、一般、不重要3类,相应权重赋值为3、2、1,实验结果见表2。从表2中可以得到和表1一致的结论。此外,对比表1和表2还可以发现,在文件权重系数不同的情况下,差异定价策略相比均一定价策略对于系统性能的提升更为明显。这也间接反映出差异定价策略能够非常好地体现文件之间的重要性区别,并更好地利用文件异构性来提升系统性能。在实验过程中发现,缓存类型对于系统性能几乎没有影响。

表1 文件权重相同情况下缓存服务提供商得到的回报和内容提供商获得的收益

表2 文件权重不同情况下缓存服务提供商得到的回报和内容提供商获得的收益

5 结 论

缓存是解决互联网大数据传输性能瓶颈的重要技术。本文研究了网络边缘TTL高速缓存的计费机制与存储策略,提出了基于内容文件缓存命中速率以及内容文件缓存逗留时间的两种计费模型。采用Stackelberg博弈模型对研究问题进行建模,求解了其在均一定价和差异定价策略下缓存服务提供商的最优价格和对应文件的TTL值。仿真实验进一步对比了在不同定价策略下缓存服务提供商得到的回报和内容提供商获得的收益,结果表明,本文的模型和策略能够有效激励缓存服务提供商和内容提供商,在现实中具有很强的操作性。

参考文献:

[1] Sandvine. Global internet phenomena report 2H 2012 [EB/OL]. (2012-11-22)[2017-09-26]. https: //www.sandvine.com/hubfs/downloads/archive/2012-2h-global-internet-phenomena-report.pdf.

[2] SHAMMA D A,FRIEDLAND G,ELIZALDE B,et al. YFCC100M: the new data in multimedia research [J]. Communications of the ACM,2016,59(2): 64-73.

[3] Cisco. Cisco visual networking index: forecast and methodology,2014-2019 [EB/OL]. (2015-05-27)[2017-09-26]. http: //s2.q4cdn.com/230918913/files /doc_downloads/report_2014/white_paper_c11-481360.pdf.

[4] Wikipedia. Content delivery network [EB/OL]. (2017 -09-01)[2017-09-26]. https: //en.wikipedia.org/wiki/Content_delivery_network.

[5] PALLIS G,VAKALI A. Insight and perspectives for content delivery networks [J]. Communications of the ACM,2006,49(1): 101-106.

[6] JACOBSON V,SMETTERS D K,THORNTON J D,et al. Networking named content [C]//Proceedings of the International Conference on Emerging Networking Experiments and Technologies. New York,USA: ACM,2009: 1-12.

[7] CHOI J,HAN J,CHO E,et al. A survey on content-oriented networking for efficient content delivery [J]. Communications Magazine IEEE,2011,49(3): 121-127.

[8] 吴超,张尧学,周悦芝,等. 信息中心网络发展研究综述 [J]. 计算机学报,2015,38(3): 455-471.

WU Chao,ZHANG Yaoxue,ZHOU Yuezhi,et al. A survey for the development of information-centric networking [J]. Chinese Journal of Computers,2015,38(3): 455-471.

[9] Wikipedia. Stackelberg competition. [EB/OL]. (2017 -01-23)[2017-09-26]. https: //en.wikipedia. org/wiki/Stackelberg_competition.

[10] BERGER D S,GLAND P,SINGLA S,et al. Exact analysis of TTL cache networks [J]. Performance Evaluation,2014,79: 2-23.

[11] FOFACK N C,DEHGHAN M,TOWSLEY D,et al. On the performance of general cache networks [C]//Proceedings of the 8th International Conference on Performance Evaluation Methodologies and Tools. New York,USA: ACM,2014: 106-113.

[12] DEHGHAN M,MASSOULIE L,TOWSLEY D,et al. A utility optimization approach to network cache design [C]//Proceedings of the 2016 IEEE INFOCOM. Piscataway,NJ,USA: IEEE,2016: 1-9.

[13] HONIG M L,STEIGLITZ K. Usage-based pricing of packet data generated by a heterogeneous user population [C]// Proceedings of the 14th Joint Conference of the IEEE Computer and Communication Societies. Piscataway,NJ,USA: IEEE,1995: 867-874.

[14] NEVO A,TURNER J L,WILLIAMS J W,et al. Usage-based pricing and demand for residential broadband [J]. Econometrica,2016,84(2): 411-443.

[15] MA R T. Usage-based pricing and competition in congestible network service markets [J]. IEEE ACM Transactions on Networking,2016,24(5): 3084-3097.

[16] SHEN H,BASAR T. Optimal nonlinear pricing for a monopolistic network service provider with complete and incomplete information [J]. IEEE Journal on Selected Areas in Communications,2007,25(6): 1216-1223.

[17] ZEKRI M,HADJI M,JOUABER B,et al. A Nash Stackelberg approach for network pricing,revenue maximization and vertical handover decision making [C]//Proceedings of the 36th IEEE Conference on Local Computer Networks. Piscataway,NJ,USA: IEEE,2011: 622-629.