基于t-SNE算法的ICN缓存容量分配机制

陈香伊， 王兴伟， 李 婕， 易 波， 黄 敏

(1.东北大学 计算机科学与工程学院 辽宁 沈阳 110169； 2.东北大学 信息科学与工程学院 辽宁 沈阳 110819)

0 引言

随着互联网数据的快速增长和网络应用的日趋丰富，用户需求逐渐从主机之间的通信演进为主机对网络信息的重复访问[1-2].与传统网络架构中以IP地址进行路由的方式不同，信息中心网络(information-centric networking，ICN)[3-4]通过唯一的内容名称对用户请求进行路由，且每个节点除了具有处理、转发的功能之外，还具有存储的功能[5].网内缓存作为ICN最大特点之一[6-7]，在提高用户服务质量、减少用户访问时延、减轻服务器负载上功不可没[8].ICN缓存领域中很多关键技术已有了阶段性的创新，但仍值得深入分析和研究[3].

在ICN众多研究项目中，最具代表性且最有发展前景的范例当属命名数据网络(named data networking，NDN)项目[9-10].文献[11]为了充分利用ICN的内置缓存，提出了一种基于内容空间分区和哈希路由的缓存机制，将内容缓存在指定的划分区域中，能够解决哈希路由引起的路径拉伸问题.文献[12]提出了一种新型智能资源管理系统，旨在分析请求模式，充分利用通用缓存内容.该系统能够根据用户需求变化实时高效地进行缓存资源分配.文献[13]通过在转发信息库中添加路由缓存，包括原子缓存和即时缓存，来缓解转发信息库的爆炸问题.目前国内外学者在ICN体系结构、路由算法、缓存决策等方面已经取得了一定的成果，但是却鲜有针对缓存容量分配机制的研究.

ICN缓存容量分配面临着巨大的缓存对象与有限的缓存空间之间的矛盾[14].绝大多数的ICN中都默认均匀部署路由器(即缓存容量相同).考虑到节点位置、网内流量分布以及用户请求特征不同，从根本上导致了节点负载不均衡.因此，如何将有限的总缓存容量适当地部署到更关键的位置，以平衡节点负载并提高缓存利用率尤为关键.

针对上述问题，本文在互联网主干网络的ICN网络架构下，分别从用户角度和节点角度对全局流量分布进行分析.首先分析网络拓扑属性以及流量特征信息，然后基于分析结果对网络节点进行聚类划分，并重新分配节点容量，旨在将有限的总缓存容量以最优的方式合理地分配给各节点，从而实现网络的负载均衡.

1 网络数据模型

1.1 拓扑信息

网络拓扑中的节点位置从根本上影响着该节点处理兴趣请求的概率，即位于网络中相对“枢纽”位置的节点可能需要处理更多的请求.因此，基于图论基础，选取了节点度数中心性C_d、节点介数中心性C_b、节点紧密中心性C_c3个中心性指标作为网络拓扑属性来区分节点的重要程度.

1.2 流量特征信息

流量特征信息能够很好地反映网络流量的分布情况，为区分节点的重要程度，本文从节点负载和用户偏好两方面共选取5个指标作为流量特征信息属性.在节点负载方面，选取接收兴趣包个数Rec_I、响应请求次数Res_I以及内容替换次数Rep_C3个指标.在用户偏好方面，选取兴趣聚合率Aggr和兴趣影响度Impact两个指标.其中，节点负载方面的3个指标可以通过采样单位时间段内的测量值累加统计得出.下面给出本文对兴趣聚合率和兴趣影响度的定义.

1.3 信息整合模型

本文将提出的3个拓扑参数和5个流量信息参数作为评价节点重要程度的指标.使用xi(t)表示，在单位取样时间段T内，节点vi收集到的流量特征信息的数据，如公式(1)，

xi(T)={Rec_Ii(T),Res_Ii(T),Rep_Ci(T),Aggri(T),Impacti(T)}，

(1)

其中：xi(T)是五维数据，简写为xi.单独收集一个时间段内的流量信息不能全面反映网内流量的变化情况，因此，总共需要选取T′个采样时间段进行流量信息的收集.用Xi表示在T′个采样时间段内节点vi收集到的数据集为

Xi={xi(T1),xi(T2),…,xi(T′T),C_di,C_bi,C_ci},i∈[0,n).

(2)

结合公式(1)，可将公式(2)中的Xi展开

Xi={Rec_Ii(T1),Res_Ii(T1),Rep_Ci(T1),Aggri(T1),Impacti(T1),…,Rec_Ii(T′T),Res_Ii(T′T),

Rep_Ci(T′T),Aggri(T′T),Impacti(T′T),C_di,C_bi,C_ci}，

其中：Xi是(5T′+3)维的数据.考虑到拓扑中共有n个节点，因此，本文收集的数据集为n个(5T′+3)维的数据.

2 缓存容量分配机制

2.1 基于改进t-SNE算法的数据集处理

本文所收集的数据呈现高维特征，且对于每个节点而言高维数据之间存在数据冗余、信息重叠的问题.本文将使用改进的t-SNE算法[15]对原数据进行降维，并通过VP树(vantage point tree)[16]构建K-近邻.在高维空间中，已知xi和xj为任意的两个数据点，xk为非xi的数据点，Neii为xi邻居集合，可通过对称化两个条件概率分布得到点对相似性的联合概率分布pij.而在本文收集的高维数据点中，两个相距较远的数据点的相似性概率pij非常小，因此取条件概率作为pij的近似.基于此，高维空间中数据点的点对相似性可定义为

(3)

高维数据是基于流形的[17]，在高维空间中如果直接使用欧式距离会存在误差，因此本文将以测地线距离代替欧式距离.但是，高维数据中的真实测地线距离难以获得.考虑到每个输入对象xi已有最近邻居集合Neii，本文将邻域内两个数据点间的最短路径计算值作为真实测地线距离的近似.xi邻域Neii内任意两个数据点间的欧式距离记为dX(xi,xj)，测地线距离记为dG(xi,xj)，两者关系如公式(4)，然后计算xi邻域Neii内任意两个数据点间的最短路径，如公式(5)，

(4)

dG(xi,xj)=min{dG(xi,xj),dG(xi,xk)+dG(xk,xj)}，k∈[0,n).

(5)

基于此，公式(3)可改进为

(6)

2.2 缓存容量分配

在通过构造K-近邻表征相似性的方式改进了t-SNE算法后，对收集到的高维数据进行处理，得到低维空间的嵌入结果Y(I).本文以该降维结果作为节点相似性的划分标准，根据节点重要程度不同，设置不同的权重，进而按权重为节点分配不同大小的容量空间.

假设低维嵌入结果Y(I)将节点划分为k_class类，numj表示类别j中包含的节点个数.令W表示类别对应的权重值，W={w1,w2,…,wk}，W中的变量按降序排列且满足公式(7)的约束，

(7)

假设整个网络拓扑的总缓存容量用Ctotal表示，在类别j中，节点的分配缓存大小用Cji表示，

Cji=Ctotal·wj/numj,j∈[1,k],i∈[1,numj).

(8)

缓存容量分配机制中，首先初始化参数并构建VP树；然后根据VP树构建K-近邻并计算点对之间的测地线距离；再计算高维空间联合概率分布；最后使用梯度下降法进行训练，得到低维嵌入的结果.通过构造K-近邻表征相似性的方式改进t-SNE算法，既考虑了高维数据的流形特征，也大大降低了高维空间点对相似性的计算量.

3 性能评价

3.1 拓扑用例

在进行仿真实现的过程中，本文使用了中国的cernet和美国的deltacom两种拓扑结构.cernet网络拓扑结构含有36个节点、49条链路，平均节点度数为2.72.deltacom网络拓扑结构含有113个节点、161条链路，平均节点度数为2.85.

3.2 评价指标

本文在Ubuntu下搭建基于NS-3的仿真模块NDNSIM并进行仿真实现，同时将搜集的历史流量数据导入到matlab软件中进行处理.

本文基于两种拓扑结构、采用多个性能指标对基于t-SNE算法的缓存容量分配机制进行性能评价，评价指标如下.

1) 缓存命中率. 缓存命中率的计算公式CacheHitRatio=NumcacheHit/Numsuccess，其中：NumcacheHit为从路由器节点的内容存储库(content store,CS)获得内容的兴趣请求数；Numsuccess为路由成功的兴趣请求数.缓存命中率能够在很大程度上表征缓存内容的利用率.

2) 路由成功率. 路由成功率的计算公式SuccessRatio=Numsuccess/Numtotal，其中：Numsuccess为路由成功的兴趣请求数；Numtotal为用户向网络中发起的兴趣请求总数. 路由成功率能够表征路由机制的效率.

3)缓存开销. 节点缓存开销的计算公式Overi=Rep_Ci·Volaver/ci，其中：Rep_Ci为节点内容替换次数；Volaver为内容平均大小；ci为节点缓存容量.缓存开销能够表征采样时间段内节点的负载情况.

3.3 性能评估

为验证本文设计的基于t-SNE算法的缓存容量分配机制，在全网发起了5 000次请求进行节点聚类，所有节点都能正常执行缓存替换机制(缓存空间已满)并收集50个采样时间段的流量特征信息.

在cernet拓扑下执行本文的缓存容量分配机制得到的二维嵌入结果如图1所示，其中每个数据点代表一个路由器节点.根据节点在网络中的相对位置可以发现，X值越大，Y值越小，节点在网络中越重要.由该图可见cernet的36个节点被聚簇为2类，含有重要节点8个，含有普通节点28个.在deltacom拓扑下执行本文的缓存容量分配机制得到的二维嵌入结果如图2所示. deltacom中的113个节点被聚簇为4类，其中节点个数分别为6、40、30、37.

图1 cernet拓扑下的低维嵌入结果Fig.1 The low dimension result in cernet

图2 deltacom拓扑下的低维嵌入结果Fig.2 The low dimension result in deltacom

为了验证本文提出的缓存容量分配机制的性能，选取LCE(leave copy everywhere)以及Betw[18]作为基准缓存决策机制.其中，LCE是ICN的默认缓存决策机制，它在数据包传输路径上的每个路由器节点都进行缓存；而Betw机制对LCE进行了改进，它将内容缓存在兴趣包转发路径上介数中心性最大的节点中.本文在cernet和deltacom两种网络拓扑下，将两种基准机制分别在默认等量分配和基于t-SNE算法的缓存容量分配(t-LCE、t-Betw)两种情况下进行仿真实验.在网内发起3 000个兴趣请求，并统计对应缓存命中率、路由成功率、缓存开销3个指标.实验结果如表1所示.

从表1中我们可以看出，在引入缓存容量分配机制后，t-LCE与t-Betw均在不同程度上提升了基准缓存机制的缓存命中率和路由成功率，且降低了网络平均缓存开销.本文提出的缓存容量分配机制基于低维嵌入的结果，为节点分配不同大小的缓存容量.cernet拓扑下，均匀分布时每个节点缓存容量为1 G，重要节点权重w1=0.6，普通节点权重w2=0.4，基于低维嵌入结果，每个重要节点需分配2.7 G容量，每个普通节点需分配0.5 G容量(2.7 G×8+0.5 G×28≈36 G).deltacom拓扑下，同样均匀分布时节点缓存容量为1 G，4类节点权重分别设为w1=0.4、w2=0.3、w3=0.2、w4=0.1.根据公式(8)可知，4类节点分别需要分配7.5 G、0.85 G、0.75 G、0.3 G容量(7.5 G×6+0.85 G×40+0.75 G×30+0.3 G×37≈113 G).

表1 Cernet与deltacom两种拓扑下对比实验结果Tab.1 Comparative experimental results over cernet and deltacom %

在两种拓扑下，本文提出的缓存容量分配机制与默认机制进行对比分析，缓存命中率提高了3%～4%，路由成功率基本维持在95%，其性能的提升与缓存决策机制本身有关.t-LCE机制对缓存命中率的提升更明显.因为从全网角度来看，尽管普通节点容量减少，但重要节点分配更多的容量后，不仅特别流行的内容副本数变化不大，还能够在重要节点缓存更多的流行内容，因此在缓存命中率指标上提升很多.t-Betw机制则在路由成功率提升方面更加明显，这是由于该机制在当前路径中的重要节点缓存内容，缓存容量分配机制为网络中相对重要的节点分配更多的缓存容量，这些节点能够响应更多的兴趣请求，因此极大提升了路由成功率.

从全网节点的平均缓存开销来看，cernet拓扑下t-LCE的平均缓存开销减少了6.3%，t-Betw的平均缓存开销减少了23.4%.deltacom拓扑下t-LCE的节点平均开销减少了13.5%，t-Betw的节点平均开销减少了17.4%.由此可见，本文提出的缓存容量分配机制在Betw上提升效果更明显，这是因为Betw对节点按照节点介数中心性进行划分，而不是像LCE机制那样对所有节点一视同仁.此外，本文提出的缓存容量分配机制，权衡了拓扑信息和流量分布，将节点按照重要程度进行划分，进而能够保证网络流量按照节点重要程度均匀分布在网内，不仅解决了部分节点负载过重的问题，还解决了少数节点缓存利用率不高的问题，从而降低了网络的整体缓存开销.

4 结束语

本文通过对现有缓存技术进行分析，提出了基于t-SNE算法的缓存容量分配机制.通过构造K-近邻表征相似性的方式改进t-SNE算法，对网络拓扑属性以及流量特征信息进行分析，基于聚类结果将有限的缓存空间合理分配给不同节点以达到平衡节点负载的目的.为验证本文方法的可行性和有效性，对算法进行了仿真实现，并与基准机制进行对比分析.从实验结果可以看出，本文设计的机制在缓存命中率、路由成功率以及缓存开销等方面具有一定的优势.下一步工作将对缓存分配机制的稳定性进行验证，进一步完善本文提出的机制.