蔡凌¹, 汪晋宽², 王兴伟³, 韩来权⁴
1. 东北大学秦皇岛分校 控制工程学院, 河北 秦皇岛066004;
2. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
3. 东北大学 软件学院, 辽宁 沈阳 110169;
4. 东北大学秦皇岛分校 计算机与通信工程学院, 河北 秦皇岛 066004
收稿日期：2016-08-10
基金项目：国家杰出青年科学基金资助项目(61225012，71325002)；河北省高等学校科学技术研究项目(QN2014327)。
作者简介：蔡凌(1980-), 女, 湖南武冈人, 东北大学秦皇岛分校讲师, 博士;
汪晋宽(1957-), 男, 辽宁沈阳人，东北大学教授，博士生导师;
王兴伟(1968-), 男, 辽宁盖州人，东北大学教授，博士生导师。

摘要：网络化缓存策略影响ICN网络的传输性能, 考虑到缓存执行时的开销不仅包含访问缓存节点时的路径代价, 还应包含替换旧信息的替换代价, 因此提出一种基于路径访问代价和节点替换代价的缓存协作策略(path and node cost based cooperative caching strategy, 简称PNC3S).该策略对两种代价进行整体考虑, 将代价总量作为是否进行信息与节点匹配缓存的依据, 对提出的策略模型进行优化分析, 将最优解作为缓存部署方案.实验结果表明, 与CEE, LCD策略相比, PNC3S可以改善网络的信息缓存率、服务器的负载率、网络链路平均利用率, 以及访问跳数减少率.
关键词：信息中心网络缓存网络缓存开销缓存策略优化算法
Cooperative Caching Strategy Based on Cache Cost for Information-Centric Networking
CAI Ling¹, WANG Jin-kuan², WANG Xing-wei³, HAN Lai-quan⁴
1. School of Control Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China;
2. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
3. School of Software, Northeastern University, Shenyang 110169, China;
4. School of Computer and Communication Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
Corresponding author: CAI Ling, E-mail: cailing9852@126.com
Abstract: In-network caching is one of the core issues in information-centric networking (ICN) which will directly restrict the data dissemination performance of the network. Considering the cache cost contains not only the path cost raised by accessing a cache node on the path but also the replacement cost of old information, a path and node cost based cooperative caching strategy (PNC3S) is proposed. The PNC3S considers the path cost and replacement cost comprehensively, and whether information matches a node or not depends on the total cost. Then the optimization algorithm is introduced into the proposed strategy to make caching decision. The simulation experiments demonstrate that the proposed PNC3S, compared with CEE (cache everything everywhere) and LCD (leave copy down), improves such performance as cached information ratio, server load ratio, average link utilization ratio and hop reduction ratio.
Key Words: information-centric networking (ICN)caching networkcache costcaching strategyoptimization algorithm
随着互联网应用模式由端到端通信向海量信息获取的转变, 学者提出了一种以信息为中心的网络架构(information centric networking, ICN)^[1].在ICN中, 缓存是作为一种基础设施服务提供给网络的, 因此, 提高缓存利用率, 将不同的信息缓存在不同的匹配节点上, 在最大化利用有限的缓存资源的同时实现缓存开销最小, 是缓存研究的核心问题.
ICN网络化缓存机制可分为显式协作和隐式协作两类.显式协作通过节点间相互通告各自缓存的信息来实现缓存决策, 因而伴随大量的通告开销, 如文献[2-4].与显式协作不同, 基于隐式协作的缓存决策中, 每个缓存节点无需知道其他节点的信息或仅需交互很少的信息, 如ICN原始提案中的处处缓存策略CEE(cache everything everywhere)^[5].为了提高缓存资源的利用率, 文献[6]设计了LCD(leave copy down)方案, 当缓存命中时, 仅在命中节点的下游节点缓存信息.文献[7]从网络的社团特性出发, 把信息缓存于社团内和社团外用户容易访问的节点处.文献[8]提出的基于加权概率的缓存机制, 认为信息的缓存概率与节点和请求者的距离成反比.文献[9]提出的CRCache缓存策略, 在最重要的路由节点缓存流行度高的信息.文献[10]提出的缓存策略, 通过在边缘路由器提前缓存流行的信息来减少用户感知信息的延时.
这些文献着重强调节点位置对缓存决策的重要性, 但由于节点上缓存的信息不同, 替换操作所产生的代价也不尽相同.假如在某一节点上缓存信息时需要替换掉一个或若干个更能提升系统收益的信息时, 代价可能大于收益.通过分析可知, 替换数量可反映出当前节点的负载和缓存状态, 对替换信息的分析可以获得信息在节点的时效性^[11].因此本文引入节点替换代价, 将其作为缓存部署的重要参考因素, 提出了基于路径访问代价和节点替换代价的缓存协作策略PNC3S, 以访问代价和节点替换代价总量最小为依据, 将信息缓存在匹配的节点上.
1 PNC3S缓存策略1.1 PNC3S运行机制假设路径访问代价和节点替换代价等信息会跟随Interest包转发到原始信息服务器OCS, OCS根据这些信息计算出缓存部署方案, 确定出路径上节点与信息的匹配关系, 然后将该关系随Data包转发到相应节点, 实现缓存信息的差异化部署.
1.2 路径代价图 1显示了一条数据访问路径.假设从节点u到节点v的路径上需要依次经过n个节点, 令节点u的编号为0, 节点v的编号为n, 则路径代价描述了不同信息在不同节点上缓存时用户的访问代价.
图 1(Fig. 1)

图 1 ICN中的信息访问示意图Fig.1 Information access schematic in ICN

定义RR_i^c表示单位时间内在节点i处观察到的对信息c的请求次数, 称为请求率.由图 1可知, 请求来自两个方向:①来源于上一跳节点转发的请求, 定义访问次数为RRL_i^c; ②来源于访问路径外的其余节点的请求(包括节点i产生的请求), 定义访问次数为RRO_i^c, 则

(1)

当i=0时, 令RRO_i^c=RR_i^c; 当i < 0时, 令RR_i^c=0.
定义HP_i^c为节点i到距其最近的有缓存信息c的节点y的跳数, 则节点i访问信息c时的路径代价可表示为

(2)

由于到达节点i的请求必然经过节点i－1, 则在整个访问路径上, 所有节点对信息c的访问总代价可表示为

(3)

当y位于不同位置时, 如图 2所示, HP_i^c的计算方法不尽相同, 需分别研究其路径访问代价.
图 2(Fig. 2)

图 2 信息的访问开销Fig.2 Access cost of the information (a)—信息缓存在上游节点处；(b)—信息缓存在下游节点处.

1) 假设信息c缓存在请求者的上游节点y处, 如图 2a所示, 所有从i到y的访问请求均由节点y响应, 则请求节点i到节点y的跳数HP_i^c=y－i, 路径访问代价为

(4)

2) 假设信息c缓存在请求者的下游节点y处, 请求者将基于就近原则从y处或服务器处获取信息, 则路径访问代价为

(5)

1.3 节点代价若信息c想缓存在节点y，而节点y的缓存空间已被占满时, 需进行替换操作.
定义RV^c_j为被替换信息c_j的黏度, 描述不同信息间的相对重要性：

(6)

式中n(c_j)是缓存有信息c_j的节点数量.从式(6)可以看出, 黏度值是节点集合范围的一种全局因子, 只与节点集合相关, 与具体节点无关, 描述的是不同信息间的相对重要性；获得相同请求的节点越多, 该值越小, 即信息和节点相关性越低.
定义RC^c_j是信息c_j的流行度：

(7)

式中：统计的是单位时间内整条路径上对信息c_j的访问次数；统计的是单位时间内整条路径上对所有信息的访问次数；n是节点数量；m是信息的集合.
定义NC_y^c是在节点y处缓存信息c时的节点代价, 假设被替换的信息集合为R, 则节点代价表达式为

(8)

1.4 缓存部署的目标函数定义一个二维变量a(c, y), 当节点i请求的信息c缓存在节点y处时, 令a(c, y)=1, 否则a(c, y)=0.由于缓存策略的目标是，追求在最大化利用有限的缓存资源的同时，实现缓存开销最小, 因此, 定义缓存代价为

(9)

其中φ为均衡系数.
为消除路径访问代价和节点替换代价数量级差异对优化准确性的影响, 采用高斯法对TPC和NC分别进行归一化处理, 得到NTPC和NNC.将数据映射到[0, 1]区间，则式(9)转化为

(10)

由于从节点i发出的对每一个信息的请求最少可以在一个缓存节点处得到响应, 因此需满足的约束条件是

(11)

在缓存的过程中, 还需考虑链路容量的限制, 避免缓存节点不能提供足够的链路带宽来满足其余节点对其访问时产生的流量.定义满足链路容量的限制条件的表达式如下:

(12)

式中LC(y)为节点y入口链路容量.
最终的目标函数表达式如下:

(13)

在对缓存部署优化问题进行求解的过程中, 本文设计了一种离散粒子群优化算法.
1.5 离散粒子群优化算法粒子群算法(particle swarm optimization，PSO)是一种源于鸟群运动模型的搜索算法.PSO最初被应用于连续论域中搜索函数的最优值, 但本文将缓存问题归纳为一个离散优化问题, 因此提出一种基于二进制编码方式的粒子群算法, 用于指导适应度函数的演化过程.
1.5.1 编码假设对全网的n个节点和m个信息进行匹配选择, 记a_cy=a(c, y), 则匹配关系的集合为{a₁₁, …, a_1n, a₂₁, …, a_mn}, 为简化表达, 对每一个匹配关系进行顺序标号, 依次为1, 2, …, m×n.则一个粒子就代表缓存部署的一个可行解, 粒子在某时刻的位置可表示成一个m×n元的一维向量, 例如, 粒子k在时刻t的位置可表示为X_k^t=(x_k1^t, x_k2^t, …, x_{k, m×n}^t), 其中x_kl^t(l∈[1, m×n])表示顺序编号为l时所对应的节点和信息的匹配关系, x_kl^t=1表示将当前信息缓存在该节点上, x_kl^t=0表示不缓存当前信息.粒子k在时刻t的个体极值记为PB_k^t, 群体极值记为GB_k^t.
1.5.2 参数的更新为了避免在搜索过程中出现不可行解的情况, 在编码方式的基础上引入交叉和变异策略, 保证粒子在位置更新后依然可行.粒子位置中的每一个元素都可成为交叉点, 在所有交叉点中, 随机选取两个交叉点即可将粒子分为3个部分.粒子的新位置就是从粒子当前位置、个体极值和群体极值中随机选取一部分进行的重新组合, 更新公式如下:

(14)

其中, ?表示交叉操作.
从粒子的更新过程可以看出, 粒子易陷入局部最优化, 且不易跳出.因此借鉴变异的思想, 对局部最优解进行变异操作, 使粒子跳出局部最优解空间, 去寻找新的解空间.
定义粒子k+i和k+j位置的相似度Δ_{k+i, k+j}:

(15)

式中：div(X_k+i^t, X_k+j^t)计算的是粒子k+i和k+j的位置向量中不同元素的个数；N是粒子向量的维数.如果Δ_{k+i, k+j}等于1, 则所有元素均不同, 如果Δ_{k+i, k+j}等于0, 所有元素均相同.
粒子个体的进化度e_k是指粒子k与个体极值与群体极值的相异程度:

(16)

如果e_k等于0, 三者完全不同, 如果e_k等于1, 三者相同.
当粒子个体进化到一定程度后, 由式(14)可知, 其自身进化能力将十分有限, 只有依赖其余粒子对全体极值的更新, 粒子的进化能力才能恢复.所以, 当粒子的个体进化度到达阈值时, 采用遗传算法中的变异操作, 即在X_k^t中执行单位置变异.为了提高粒子的收敛速度, 在粒子初始化时已经随机令多个元素的值为1；因此在变异之前, 先检查该粒子中值为1的元素个数是否等于1, 如果等于1且选定的变异点的元素值为1的话, 则需重新选择其他的变异点, 否则正常变异.通过变异操作, 可以给群体引入新的信息, 增加群体的多样性, 扩大粒子的搜索空间, 抑制算法的早熟收敛.
1.5.3 基于缓存开销的协作缓存部署算法输入:节点间的拓扑关系、访问率、已缓存的信息位置
输出:匹配特征序列
步骤1 ?计算路径代价与节点代价;
步骤2 ?随机产生初始群体, 保证粒子中至少有一个位置的值不为0, 为每个粒子生成随机初始速度, 设置粒子的个体极值PB和群体极值GB;
步骤3 ?按照式(14)更新粒子的位置;
步骤4 ?判断粒子个体的进化度, 若大于阈值, 进行变异操作, 否则保持更新值;
步骤5 ?根据式(13)评价每个粒子的适应值;
步骤6 ?对每个粒子, 将适应值与个体极值PB进行比较, 如果优于PB, 则将其作为当前的个体极值;
步骤7 ?对每个粒子, 将适应值与群体极值GB进行比较, 如果优于GB, 则将其作为当前的群体极值;
步骤8 ?如果迭代次数达到最大, 转步骤9;否则转步骤3;
步骤9 ?将群体最优位置作为一条匹配规则并输出.
2 结果与讨论2.1 评价指标为评价ICN的缓存性能, 在分析网络运行开销时, 定义了信息缓存率、服务器的负载率、网络链路平均利用率; 在分析用户体验质量时, 定义了访问跳数减少率等指标.
2.2 实验参数设置本文的实验拓扑结构如图 3所示, 信息的请求过程服从泊松分布, 同时假设用户对信息的请求模式遵循Zipf分布, 且用户的平均请求速率为每秒200个兴趣包.网络中的信息数量共有10 000个，网络的缓存总容量为0.3~0.8 GB, 实验初始时每个节点的缓存信息量为0.本文将PNC3S策略与CEE策略和LCD策略的性能进行比较分析, 这些策略的缓存替换算法选用的都是LFU.为了进一步比较不同的替换算法对PNC3S的影响, 分析了当采用LRU替换时的PNC3S缓存效果.
图 3(Fig. 3)

图 3 仿真实验拓扑结构示意图Fig.3 The simulation topology diagram

2.3 实验结果图 4为3种缓存策略在单位时间内缓存率随缓存容量的变化情况：3种缓存策略在单位时间内缓存率随着容量的增加而逐渐减少.通过对CEE和LCD策略的定义分析可知, CEE的缓存率将高于不断地在命中节点的下游节点缓存信息的LCD策略.而PNC3S策略将不同的信息定向缓存在不同的节点, 无需冗余的缓存操作, 因此, 在单位时间内, 缓存率的平均值最低.进一步分析可知, LRU替换的是最近利用率最低的信息, LFU替换的是访问次数最少的信息, 而文中流行度的定义强调的是单位时间内对信息访问的热度, 因此LRU替换算法更为适用, 缓存率稍微高于LFU算法.
图 4(Fig. 4)

图 4 缓存率随缓存容量的变化Fig.4 Cache rate vs cache capacity

图 5为3种缓存策略单位时间内服务器的负载率.这3种缓存策略的服务器的负载率分别随着缓存容量的增大而减少.这是因为, 随着缓存容量的增大, 可缓存信息的数量增多, 用户在缓存节点获取所需信息的概率加大, 因此到服务器节点进行请求的概率降低, 负载率相应减少.进一步分析可知, PNC3S策略用较低的缓存率获得了与CEE近似相同的对服务器的访问率.
图 5(Fig. 5)

图 5 服务器负载率随缓存容量的变化Fig.5 Sever load rate vs cache capacity

图 6为3种缓存策略的网络链路平均利用率随缓存容量的变化情况.从图中可以看出, 这3种链路利用率随着缓存容量的增加而减小.由于LCD服务器的负载率最高, 意味着有很多的请求被转发到了服务器, 因此链路的利用率最高.
图 6(Fig. 6)

图 6 链路利用率随缓存容量的变化Fig.6 Link utilization rate vs cache capacity

图 7为3种缓存策略的访问跳数减少率随缓存容量的变化情况.可以看出, 这3种缓存策略的访问跳数减少率分别随着缓存容量的增大而增加.
图 7(Fig. 7)

图 7 跳数减少率随缓存容量的变化Fig.7 Hop reduction rate vs cache capacity

3 结语为了合理利用ICN有限的缓存空间, 在优化缓存部署时实现缓存开销最小, 提出了一种在分布式缓存中嵌入中心式缓存的机制, 即基于路径访问代价和节点信息替换代价的缓存协作策略.通过在服务器节点进行缓存的优化部署计算, 并依据计算结果指导缓存的部署.实验结果表明, 该策略不但降低了网络的运行开销，还提高了用户的体验质量.
参考文献

[1]	Jacobson V, Smetters D K, Thornton J D, et al. Networking named content[J].Communications of the ACM, 2012, 55(1): 117–124.
[2]	Saino L, Psaras I, Pavlou G. Hashing routing schemes for information-centric networking[C]//ACM SIGCOMM Workshop on Information-Centric Networking. New York: ACM, 2013: 27-32.
[3]	Wang S, Bi J, Wu J. Collaborative caching based on hash-routing for information-centric networking[J].ACM SIGCOMM Computer Communication Review, 2013, 43(4): 535–536.DOI:10.1145/2534169
[4]	Wang J, Zhang J, Bensaou B. Intra-AS cooperative caching for content-centric networks[C]//ACM SIGCOMM Workshop on Information-Centric Networking. New York: ACM, 2013: 61-66.
[5]	Ghodsi A, Shenker S, Koponen T. Information-centric networking: seeing the forest for the trees[C]//HotNets-X Proceedings of the 10th ACM Workshop on Hot Topics in Networks. New York: ACM, 2011: 483-510.
[6]	Chai W, He D, Psaras I. Cache"less for more"in information-centric networks[J].Computer Communications, 2013, 36(7): 758–770.DOI:10.1016/j.comcom.2013.01.007
[7]	蔡君, 余顺争, 刘外喜. 基于节点社团重要度的ICN缓存策略[J].通信学报, 2015, 36(6): 1–10. ( Cai Jun, Yu Shun-zheng, Liu Wai-xi. Caching strategy based on node's importance to community in information-centric networks[J].Journal on Communication, 2015, 36(6): 1–10.DOI:10.11959/j.issn.1000-436x.2015126)
[8]	Psaras I, Chai W, Pavlou G. Probabilistic in-network caching for information-centric networks[C]//ICN Workshop on Information-Centric Networking. New York: ACM, 2012: 55-60.
[9]	Wang W, Yi S, Yang G, et al. CRCache: exploiting the correlation between content popularity and network topology for ICN caching[C]//IEEE International Conference on Communications. Sydney: IEEE, 2014: 3191-3196.
[10]	Lim S H, Ko Y B, Jung G H, et al. Inter-chunk popularity-based edge-first caching in content-centric networking[J].IEEE Communications Letters, 2014, 18(8): 1331–1334.DOI:10.1109/LCOMM.2014.2329482
[11]	崔现东, 刘江, 黄韬, 等. 基于节点介数和替换率的内容中心网络网内缓存策略[J].电子与信息学报, 2014, 36(1): 1–7. ( Cui Xian-dong, Liu Jiang, Huang Tao, et al. A novel in-network caching scheme based on betweenness and replacement rate in content centric networking[J].Journal of Electronics & Information Technology, 2014, 36(1): 1–7.)