信息中心网络缓存节点位置选择算法*

王兴伟，王子健，李福亮，黄 敏

(1. 东北大学 软件学院， 辽宁 沈阳 110004； 2. 东北大学 计算机科学与工程学院， 辽宁 沈阳 110004；3. 东北大学 信息科学与工程学院， 辽宁 沈阳 110004)

信息中心网络(Information-Centric Networking, ICN)被认为是一个能够较好地满足用户对信息传递的需求的新型网络体系结构[1]。在众多的ICN架构中，命名数据网络(Named Data Networking, NDN)[2]成为研究热点。NDN来源于更早期的项目——内容中心网络 (Content-Centric Networking, CCN)[3]，由Van Jacobson在2006年首次提出，NDN架构延续了CCN架构的设计理念与原则。

在ICN中，网内缓存已经成为提高网络整体性能的核心特性之一。ICN的缓存策略根据数据缓存位置可以分为路径缓存(on-path)与非路径缓存(off-path)[4]。on-path的存储方式将数据沿途存储在请求来时的路径中，因此其命名解析与数据路由是同步的。这种策略虽然很简单，但导致了网内数据副本数量过高。而off-path的存储方式可以将数据存储在请求路径以外的缓存节点中，因此其命名解析与数据路由可以同步或者异步。这种方式虽然很灵活，但需要一种缓存感知的机制来使路由器能够感知周围节点的缓存信息。ICN的缓存具有透明、泛在、细粒度三大特性[5]，由于“泛在缓存”的特性，ICN网络中数据冗余的现象频频出现，导致其数据副本率过高，缓存空间不能被充分利用。除此之外，部署如此规模的缓存空间也是一种浪费，并且高昂的开销与所获取的收益不成正比。

国内外许多学者已经对ICN中的网内缓存进行了广泛的研究。文献[6]倡导“less for more”的理念，即针对某一请求路径，选取在一些比较合适的节点缓存数据，提出了一种基于介数中心性的缓存策略，每次在缓存数据时都进行决策。文献[7]提出了，一种基于内容空间划分与Hash路由的协作式网内缓存模式，有效地提高了网络整体的缓存命中率。文献[8]关注于缓存的一致性问题，提出了一种具有高性价比基于流行度的缓存一致性机制。该机制能够在缓存一致性与相关代价中做出权衡，保证了ICN路由器中所缓存内容的新鲜度。文献[9]通过一个统一的方法紧密地集成了缓存与拥塞控制，利用由拥塞控制反馈出的可用拥塞定价来引导在每个内容路由器上的缓存决策，提高了网络的吞吐量并且减少了网络拥塞。文献[10]提出了一种流行内容分布的分析框架，基于博弈论的思想制定了ICN中的缓存与定价策略。

以上工作侧重于对缓存策略的研究，即在哪些节点或对哪些内容进行缓存所获得的收益更高，并未涉及其前置工作——缓存空间的部署分配问题。目前，在缓存空间部署分配问题上的研究还较少[11]。文献[12]研究了如何在一个给定存储预算的网络中为路由器分配存储空间，通过建立数学模型分析求解得出网络拓扑、网络规模、内容流行度等都对缓存分配产生一定的影响，不存在一体适用的策略。文献[13]首次研究了CCN中的缓存空间分配问题，采用了节点中心性的一些度量，比如度中心性、介数中心性、接近中心性，根据中心性的不同按相应比例异构地分配缓存空间。文献[14]从经济的角度出发，建立优化模型来研究在预算限制的情境下ICN的迁移问题。文献[15]是研究缓存空间分配的开篇之作，但其针对的是传统网络，目的在于选取合适的缓存位置来降低网络流量。这也对之后ICN中缓存空间放置问题的研究打下了坚实的基础。

然而，寻求一种高效的缓存策略是毋庸置疑的，但这个问题是由ICN缓存“普遍存在”的特性引起的，因此寻求一种高效的缓存空间分配策略才是解决问题的根本。而上述缓存空间分配方面的工作并未综合考虑网络中不同角色的利益(文献[14]仅仅进行了经济层面的考虑)，本文将从用户、网络运营商、服务提供商三者的角度出发，在网络性能与经济中做出权衡，在网络中选择适宜的节点开辟缓存空间，使三方都能够最大限度地从中受益，从而在根本上对ICN缓存进行优化。

因此，本文基于on-path缓存策略，建立基于用户-服务提供商的缓存位置模型和基于网络运营商的缓存位置模型，进而将其结合成为多目标优化模型，并通过算法求解得出最优缓存节点位置集合。本文的贡献与创新点如下：

1)缓存节点的选择充分考虑了网络中用户、服务提供商、网络运营商三方的利益，从三方不同的利益角度出发进行建模；

2)采用帕累托模型进行求解，从而得到对于网络中各方都比较均衡的解集，使三方能够最大限度地从中受益；

3)对ICN原生的缓存空间放置策略进行了优化，这对未来ICN的实际部署有着一定的参考价值。

1 问题描述

缓存节点位置选择可归结为资源分配问题，该类问题也是云环境下研究的重点问题[16-17],即在资源有限的环境下，如何合理地分配资源，提高资源利用率，并最大限度地改善系统性能。而在ICN中选择合适的位置开辟缓存空间受多重因素的影响，不存在通用的策略。除此之外，不同的角色对于开辟缓存空间所需要获得的收益也是不同的。处于用户的视角，看重的是响应时间；处于网络运营商的视角，应从经济的角度出发，以最小的成本获取最大的利益；而处于服务提供商的视角，降低服务器的负载，提高效率才是最主要的。但无论从哪一方的角度出发，开辟合适的缓存空间最终目的还是为了提高网络整体性能，使三方都从中受益。

1.1 网络模型

将网络建模成为一个无向连接图G=(V,E)，其中V为网络中的节点集合，E为网络中的链路集合。将网络中的所有节点分为三种类型：用户节点vc∈C、路由器节点vr∈R、服务器节点vs∈S(C、R、S分别为用户节点集、路由器节点集、服务器节点集)，且V=(C∪R∪S)。

1.2 数学模型

在建立模型之前，首先给出模型的假设：

1)不考虑路由器负载；

2)路由最短路径是唯一的；

3)传输中以内容大小近似代替数据包的大小。

1.2.1 基于用户-服务提供商的缓存位置模型

用户关注的是响应时间，即用户请求能够在短时间内被响应；而服务提供商关注的是服务器的负载。在ICN中，数据包转发给某一路由器时会首先检查内容存储器(Content Store, CS)中是否有所需要的数据，如果命中则直接将数据路由给用户，不需要访问目标服务器。假设用户请求的内容都会在中间节点上被满足，且该节点离用户只有一跳的距离，此时用户的响应时间和服务器的负载都会得到极大的提升。因此，该位置的选取应该离用户越近越好，而离服务器越远越好。

基于以上思想，给出模型中消耗的定义。最优位置集合Xp={v1,v2,…,vp}⊆R(其他符号定义见表1)，则在R中选择位置p开辟缓存空间时，用户c请求内容oi的消耗如式(1)所示。

表1 符号说明

(1-hoi)·[d(vc,vp)+d(vp,s(oi))]+

(1)

目标函数：

[ωp·d(vc,s(oi))]}

(2)

约束条件：

vp∈R∩{Path(vc,s(oi))},vc∈C,s(oi)∈S

(3)

(4)

(5)

(6)

式(3)限制了位置p应从c到s路由的最短路径上选取，并假设该路径是唯一的。式(4)考虑到用户不可能对所有内容都感兴趣，因此用二进制变量来表示用户是否有请求某个内容的需求。在数据路由方面采用与命名解析耦合的方式，其意味着请求路径与数据路由路径是对称的，即d(vp,s(oi))=d(s(oi),vp)。式(5)的意义是为了让其满足on-path策略。式(6)限制了开辟缓存的总预算不多于BM。

将式(2)进一步化简可得：

(7)

由式(7)可得出在请求某一缓存命中率较大的内容时(该内容在网络中较为流行)，请求数据量与用户到缓存路由器距离的乘积越小且请求数据量与服务器到缓存路由器距离的乘积越大，则目标函数值越小。

1.2.2 基于网络运营商的缓存位置模型

在网络运营商的角度，所需要考虑的是经济问题，即用最少的钱做更多的事。针对该问题，考虑网络中传输所有流量的费用与开辟缓存空间的费用，建立模型。

目标函数：

(8)

进一步细化公式：

(9)

约束条件：

vp∈R∩{Path(vc,s(o))},vc∈C,s(oi)∈S

(10)

pi,j>0,∀i,j∈E

(11)

(12)

(13)

(14)

式(8)中只考虑请求路径的费用消耗，而不考虑数据路由路径的费用消耗，这是因为采取的是数据路由与命名解析耦合方式，请求路径与数据路由路径是对称的。 式(9)中的koi是代表内容对象大小，虽然用户请求时发出兴趣包的大小并不等同于该请求内容大小，但在该模型中用内容对象大小近似地代替请求包的大小，以便体现出用户请求不同内容的差异性。 式(10)、式(12)～(14)中的约束定义与基于用户-服务提供商的缓存位置模型中一致。 式(11)则限定了链路传输单元流量的费用应为正数。 该模型中将缓存预算进行了限制，而对于网络中传输流量的费用并未限制，因为这部分费用是运营商必须要支付的，用来满足用户数据传输的需求。

将式(9)进一步化简可得：

(15)

从式(15)可以看出，内容对象的缓存命中率越大，并且在缓存路由器到服务器的链路上传输该内容所支付的费用越高，则该目标函数值越小。

1.2.3 多目标优化模型

以上给出了两个基于不同角度的单目标优化模型：基于用户-服务提供商的缓存位置模型和基于网络运营商的缓存位置模型。对于多目标优化问题来说，单个目标最优并不能保证其他目标也是最优的，因此需要一种折中方案。在这里引入多目标优化模型中的经典模型——帕累托模型[19]，并以帕累托优胜的概念来衡量解的优劣，以此得到最终的帕累托最优解集合，即对于两个目标而言都比较均衡的解集。

2 信息中心网络缓存节点位置选择算法

基于帕累托模型求解方法中数学规划法的思想设计了信息中心网络缓存节点位置选择算法。

2.1 缓存节点位置选择算法主流程

帕累托模型的求解方法主要有三种：两两比较法、数学规划法和基于进化算法求解[19]。考虑到帕累托模型的解空间一般来说都相对较大，采用数学规划法进行求解。该方法的解空间相对来说较小，求解难度适中。下面给出基于数学规划法的缓存节点位置选择算法主流程。在该算法流程中，目标一为基于用户-服务提供商的缓存位置模型的优化目标，目标二为基于网络运营商的缓存位置模型的优化目标。求解时首先忽略目标二，仅考虑目标一，并采用基于用户-服务提供商的缓存位置选择算法来求解得到L个最优解，进而计算出这L个最优解分别对应的目标一与目标二的值，并通过帕累托选择得到帕累托优胜解集；接着忽略目标一，仅考虑目标二，并采用基于网络运营商的缓存位置选择算法来求解得到L个最优解，进而计算出这L个最优解分别对应的目标一与目标二的值，并通过帕累托选择得到帕累托优胜解集；最后根据以上得到的所有解集进行帕累托选择得到最终解集。

帕累托解的优劣很大程度由L决定，当L取值较大时，能够得到较多的候选解集，相对来说解更优，但这会增大算法的复杂度和运行时间；而当L取值较小时，尽管能提高效率降低运行时间，但由于所得到的帕累托候选解太少会影响解的优劣。因此对于L参数的选择需要在运行时间与解的优劣上进行权衡。

此外，在路由算法上采用基于任意两点间最短路径算法Floyd算法[20]。

2.2 基于用户-服务提供商的缓存位置选择算法

本节主要针对基于用户-服务提供商的缓存位置模型的求解算法进行设计，该模型可归结为线性整数规划模型，对于此类问题可采取确定式求解与启发式求解，启发式求解是一种近似求解，其又可以分为传统启发式(贪心算法等)与元启发式(蚁群算法[21-22]等)。考虑到确定式求解算法的开销十分巨大，而元启发式算法的复杂度较高，收敛速度较慢。因此，本节设计了一种基于随机贪心启发策略的传统启发式算法来进行求解，算法具体步骤参见算法1。

算法1 基于用户-服务提供商的缓存位置选择算法

2.3 基于网络运营商的缓存位置选择算法

基于网络运营商的缓存位置模型与0-1背包模型类似，因此解决此类多阶段决策问题采用动态规划法[23](Dynamic Programming, DP)求解最为适宜。

2.3.1 动态规划子问题定义

根据动态规划思想需要将该问题拆分成多个阶段，每个阶段有相应的子问题。

子问题F[i][j]：在剩余预算j的限制下，在前i个路由器中选取若干个开辟缓存空间所能得到的最大收益。

该类问题存在一个特点就是第i时刻的状态只与第i-1时刻的状态有关，因此处于空间复杂度的考虑可采取一维数组来存储求解过程中的状态，即只存储F[i][j]中第二维的信息，第一维默认是第i-1时刻的状态，故不需要进行存储。定义F[j]的状态转移方程为：

F[j]=Max{F[j]，不在第i个路由器开辟缓存

F[j-C[i]]+V[i](j≥C[i]) ，在第i个路由器开辟缓存}

(16)

式中，C[i]为路由器i开辟缓存空间的费用，V[i]为在第i个路由器开辟缓存空间所得到的收益。

2.3.2 算法描述

接下来给出基于网络运营商的缓存位置选择算法，算法具体步骤参见算法2。

算法2 基于网络运营商的缓存位置选择算法

3 性能评价

3.1 评价基准与指标

评价基准方面，以所提ICN最优位置选择(ICN Optimal Cache Location Selection， ICN OCLS)算法与ICN的原生特性(Native Feature， NF)即默认在所有节点都开辟缓存空间进行对比。

主要有以下四个评价指标：

1)网络消耗值(Network Consumption Value， NCV)。网络消耗值刻画了网络中的全局流量消耗。其定义如式(17)所示。

NCV=TC

(17)

式中，TC为网络中全局流量消耗。

2)网络费用开销(Network Expense， NE)。网络费用开销描述了当前网络状况下网络运营商所需支付的费用。其定义如式(18)所示。

NE=TE+CE

(18)

式中，TE为网络传输流量的费用开销，CE为开辟缓存的费用开销。

3)流量性价比(Traffic Cost-Effective， TCE)。流量性价比描述了每台缓存路由器在流量方面所带来的平均收益值，故该性价比越高越好，其定义如(19)所示。

(19)

式中，0_traffic为网络中不存在缓存路由器时的全局流量，x_traffic为网络中存在x台缓存路由器时的全局流量，amount为网络中缓存路由器的数量。

4)网络费用开销比(Network Expense Ratio, NER)。网络费用开销比刻画了随着缓存路由器数量的增加，网络费用开销相对于无缓存网络的变化情况，其定义如式(20)所示。

(20)

式中，x_expense为存在x台缓存路由器时网络的费用开销，0_expense为不存在缓存路由器时网络的费用开销。

3.2 实验拓扑与参数设置

实验部分采用东北大学校园网拓扑，如图1所示。其中存在2台服务器与12台路由器。14个用户(教学楼与宿舍楼)并未给出，其均匀分布在图一的最底层。

图1 东北大学校园网拓扑图Fig.1 Northeastern University campus network topology

针对该问题采用Zipf分布[24]产生内容集，并简单地认为该内容越流行、越重要，其缓存命中率也会越大，以此来确定缓存命中率。在用户请求内容方面，根据2/8原则思想，认为某个内容越重要则用户请求该内容所花费的流量也就越多，对总流量按比例进行划分以得出用户请求不同内容所消耗的流量。传输单元流量的费用参照Amazon CloudFront的定价[25]，由于其在不同的地区收费不同，在这里取其平均值折合为人民币大约为0.57元/GB。为每台路由器选择开辟1TB High-Speed SSD的缓存空间，其所需要支付的费用大约为20万元[26]。在建立基于用户-服务提供商的缓存位置模型时，是用数据量与距离的乘积来定义消耗，而本实验利用的是实际网络流量数据，所以在本实验中将该模型的消耗式(1)重新定义为流量消耗。

(21)

式中，trafficc,p表示节点c与节点p之间的流量。而对于基于网络运营商的缓存位置模型来说，只需要将式(9)中的内容大小koi替换为请求该内容实际的流量即可。

3.3 实验结果

本实验中默认的参数设置如表2所示。

表2 实验默认参数设置

3.3.1 缓存路由器数量的影响

实验结果如图2所示。由图2(a)与(b)可知，在ICN OCLS策略中随着缓存路由器数量的增加，流量性价比呈下降趋势，网络费用开销比先下降后上升。在部署1台缓存路由器时，流量性价比和网络费用开销比都是最优的。因为选择在拓扑图中的16节点开辟缓存空间，而该节点位于网络中的“核心”，是两个校区流量进出口的枢纽，所以在该节点部署缓存空间会使用户都能从中受益。从图2(a)中可看出，部署3～9台缓存路由器时ICN OCLS的网络费用开销比相对较低，且要优于ICN NF，即网络运营商会从中获益更多。从图2(b)中可看出，ICN OCLS随着缓存路由器数量的增加，流量性价比逐渐降低最终与ICN NF的一致，这说明了部署过多的缓存路由器会使每台缓存路由器的平均收益值降低。而且，在缓存路由器数量为1～5时其效果最好，即用户和服务提供商会从中获益更多。因此，综合三方利益来看，缓存路由器数量在3～5范围内会使三方最大限度地从中受益。

3.3.2 Zipf分布α参数的影响

在ICN OCLS算法中缓存路由器数量设置为6，其他参数见表2。由图2(c)可知，随着参数的增大，两种策略所对应的流量性价比也随之增大，并且ICN OCLS的性价比要一直优于ICN NF，因此在Zipf分布α参数较大的网络中ICN OCLS带来的流量性价比更高。

由图2(d)与(e)可知，随着α参数的增大，两种策略在两图中都呈下降趋势。这是因为α参数越大，内容分布的“重尾现象”会越严重，意味着网络中流行的内容数量会越来越少，只有少数流行度较高的内容才会被用户请求，因此缓存路由器通过缓存这些少数的重要内容来满足用户的请求，大多数的用户请求都会被网内缓存满足，这样不但降低了网络全局流量，而且降低了网络运营商传输流量的费用。

(a) 不同缓存路由器数量下的网络费用开销比(a) Network expense ratio for the different number of cache routers

(b) 不同缓存路由器数量下的流量性价比(b) Traffic cost-effective for the different number of cache routers

(c) 不同α下的流量性价比(c) Traffic cost-effective for different α

(d) 不同α下的网络费用开销(d) Network expense for different α

(e) 不同α下的网络消耗值(e) Network consumption value for different α

(f) 不同内容数量下的流量性价比(f) Traffic cost-effective for the different number of contents

(g) 不同内容数量下的网络费用开销(g) Network expense for the different number of contents

(h) 不同内容数量下的网络消耗值(h) Network consumption value for the different number of contents图2 实验结果Fig.2 Experimental results

3.3.3 内容数量的影响

在ICN OCLS算法中缓存路由器数量设置为6，其他参数见表2。从图2(f)、(g)、(h)可知，内容对象数对两种策略是基本没有影响的，这是因为该实验中利用的流量数据是东北大学校园网的年平均流量数据，网络中的总流量是恒定的，内容数量的增多仅仅会造成用户请求的多样化，而其分布规律是不变的(Zipf分布α参数不变)。因此，图中指标几乎不会受到影响。

4 结论

本文通过考虑网络中多方角色的利益，基于不同角度建立了数学模型，并将其结合为多目标优化模型，基于帕累托求解方法中数学规划法的思想设计了缓存节点位置选择算法来解决ICN中过度的缓存冗余问题。实验结果表明，在流量性价比方面，所提出的最优缓存位置选择算法要完全优于ICN原生特性；而在网络费用开销方面，所提出的算法更适用于只有少数内容较为流行(Zipf分布α参数较大)的网络中，而对于所有内容都流行(Zipf分布α参数较小)的网络中，ICN原生特性更为适宜。

此外，本文解决ICN中过度的缓存冗余问题的方法，仅仅是从开辟缓存空间的角度进行研究的，而这只是解决该问题策略中的一部分，更为完备的解决方案是：选择节点开辟缓存空间→为已开辟缓存空间的节点分配存储容量→对内容的放置进行决策。该方案能够更加全面、更加完备地解决ICN中过度的缓存冗余问题，这也将是本文未来所要研究的重点内容。