互联网设计之初, 用户主要的需求是联通性和资源共享.经过近50年的发展, 以视频分发、文件下载等为代表的内容获取服务已成为互联网中的主流应用需求, 用户对内容本身的关注胜于对内容位置的关注.为满足新的网络需求, 提出了信息中心型网络(information centric neworking, 简称ICN)^[1], 将内容名字作为网络路由和传输的标识, 当用户请求某一内容时, 任何缓存该内容的节点都可以做出响应, 从而显著提升内容传输效率.Named Data Networking(NDN)/Content-Centric Networking(CCN)^[2], Data-Oriented Network Architecture (DONA)^[3], Network of Information(NetInf)^[4]和ContentMediator architecture for content-aware nETworks (COMET)^[5]等是典型的ICN类型的网络架构.

网内缓存是ICN的重要特征.虽然缓存理论及相关技术已经在P2P, CDN和Web等领域中得到了较为广泛和深入的研究和应用, 但是它们并不适用于ICN架构体系, 主要原因是:ICN中的内容基于全网统一命名, 具有缓存透明化的特征, 可服务于不同类型的网络流量, 而采用私有协议的P2P, 基于域自主命名的Web, 相同的内容很难被统一命名, 难以被全网共享, 且服务对象单一; ICN的缓存具有泛在化特性, 任何节点都可缓存任意内容, 任何内容都可缓存在任意节点上, 而且节点上缓存的内容存在被不断替换的可能, 这导致缓存拓扑结构具有动态变化的特征^[6-8], 而Web和CDN缓存点的位置一般是确定的, 缓存拓扑结构较为规则, 因此需要探索和研究新的机制与策略.

适用于ICN的缓存机制与策略首先要解决内容部署问题.ICN的网内缓存是作为一种基础设施服务提供给网络的, 需要缓存大量内容, 而路由节点的存储空间相对而言非常有限.为了充分利用有限的节点缓存资源, 已经提出了一些新的缓存算法.这些算法大致可以分为3类:一类是基于节点数据的算法, 根据节点在拓扑结构中的位置、节点的性能等, 为内容选择缓存节点; 一类是基于内容数据的算法, 根据内容流行度选择要缓存的内容.这两类算法虽然可改善网内缓存性能, 但由于节点和内容之间缺乏相互感知, 前一类算法无法探知不同流行度的内容对缓存资源的不同需求, 后一类算法缺乏获取网络性能的手段, 不能对网内缓存资源进行有效控制.因此提出了结合节点数据和内容数据的又一类算法, 根据节点和内容之间相互影响的关系, 确定内容与节点的匹配关系, 进行自适应的缓存.

由于ICN具有动态特性, 不同时期的网络特性不同, 节点状态不同, 且ICN网络具有泛在缓存的特征, 任何节点都可以缓存任意内容, 同时, 任何内容都可以缓存在任意的节点上, 因此节点和内容均衍生出了海量的数据信息, 而以上文献所建立的自适应数学模型与算法均未涉及对海量数据的处理与分析.已有研究表明:利用网内大数据获取的数据关联性, 可更高效地分配网络资源并获得最大化的收益^{[9, 10]}, 这说明大数据方法可以作为分析ICN网络中海量的节点和内容间感知信息的技术手段, 通过对不同阶段感知信息关联性的分析, 可挖掘出节点和内容匹配关系的演变规律, 并利用该规律进行自适应的缓存.鉴于此, 本文提出将ICN中节点和内容的状态数据流作为网络资源, 利用从中获得的节点和内容的多属性数据, 挖掘出缓存决策与各属性间的依赖关系.在挖掘过程中, 根据当前节点和内容的状态数据流, 采用集成分类算法Adaboost^[11]对已观测到的节点和缓存内容样本进行分析, 寻找其中的规律.这个规律就是当前阶段数据流所定义的概念(concept), 然后利用这个规律或概念对未知节点和内容的关系进行预测.然而随着时间的推移, 数据流中定义的概念也随时可能发生变化, 例如, 内容从发布阶段进入到流行阶段, 即产生概念漂移^[12], 因此需要训练新的分类器以适应新到的概念.特别是, 有时某些概念会在数据流中重复出现.例如:当流行期可达几个月之久的YOUTUBE音乐视频文件^[13]和流行期相对较短的Olympic视频文件^[14]的流行期冲突时, 音乐视频流所对应的概念将发生漂移; 而当Olympic视频文件流行期结束后, 音乐视频流所对应的新概念可能会与Olympic视频文件发布前的概念相似或者重复.当概念重现时, 本文将历史概念加入到对新样本的分类计算中, 在提高缓存决策准确性的同时, 降低分类器的学习代价.

本文提出的基于概念学习的自适应缓存策略, 利用感知的节点数据和内容数据为驱动, 实现自适应缓存的目标, 主要贡献如下.

(1)   提出大数据驱动的节点和内容的多属性表达模型, 用来识别并标准化节点、内容的实时状态;

(2)   提出一种基于信息熵的概念漂移识别算法, 根据节点、内容的实时状态的熵变, 检测概念漂移, 不需要对缓存状态进行实时标记;

(3)   提出一种基于概念重现的缓存算法, 根据概念漂移结果更新分类器, 重新定义多维状态属性与缓存匹配之间的函数映射关系, 并在更新的过程中, 考虑了概念重现的情况.

1 相关工作

网内缓存是ICN的重要特征, 因此, 如何选择合适的节点部署恰当的内容、最大化利用有限的缓存资源是研究的重点.ICN提出之初, 采用CEE(cache everything everywhere)泛在缓存策略^[15], 大量冗余内容存在于网络, 缓存资源浪费严重.为了提高缓存资源的利用率, 一些研究提出了基于节点数据的方法.例如将命中节点的下游节点^[16]或介数最大的下游节点^[17]作为缓存节点.文献[18]提出一种基于网络全局节点重要度的缓存节点选择算法.文献[19]提出一种基于网络社团特性的缓存节点选择算法.文献[20]提出一种基于边缘优先逐级反馈的缓存协作策略, 上游缓存节点的选择需要参考下游节点的缓存决策信息和统计信息.文献[21]提出一种综合考虑节点紧密中心性、介数中心性和度中心性等中心性指标的缓存机制.

一些研究在选择缓存节点的过程中引入了概率机制.文献[22]提出一种节点以概率p缓存内容的算法Prob (copy with PROBability).在文献[23, 24]中, 缓存概率参考了缓存节点与源节点之间的距离以及缓存容量等因素.文献[25]中提出的缓存概率因子反比于请求者与源服务器间的距离.文献[26]提出的MBP(max-benefit probability-based caching)策略, 缓存概率因子考虑的是节点的替换代价.这些研究主要考虑节点的属性, 把节点的位置和缓存容量等作为缓存选择的主要依据, 内容在空间上的分布没有变得更加均匀和合理.

基于内容数据的网内缓存算法主要关注的是内容流行度的特性.文献[27]提出了一种基于流行度的缓存内容选择方法, 流行度计算的是基于本地流行度进行加权求得的全局流行度.文献[28]提出了一种启发式概率缓存方法, 基于缓存收益和内容热度等因素计算内容的被缓存概率.另外, 还有一些研究工作关注的是内容的使用效率, 例如, 文献[29, 30]将内容的使用效率作为是否缓存的判断依据.文献[31]提出的StreamCache策略从流的角度出发, 将流细分为不同的内容块, 通过统计不同内容块的使用效率, 选择需要缓存的内容块.基于内容数据的缓存算法虽然考虑了缓存内容的选择问题, 但由于缺少对网络环境、节点状态的考虑, 可能造成对节点缓存资源利用的不合理问题.例如, 高流行度的内容可能被缓存在高访问频率、高负载率的节点, 这将导致该内容在节点上被替换的概率也较高.

为了研究内容与节点的自适应缓存问题, 实现内容资源和节点缓存资源的合理配置, 部分研究采用结合节点数据和内容数据的方法, 在节点和内容状态相互感知的情况下进行节点和内容的匹配.对内容状态的度量主要是使用流行度, 对节点状态的刻画则不尽相同, 例如, 文献[32, 33]将缓存容量作为研究节点状态的主要参考因素, 文献[34, 35]是将缓存节点与源节点之间的跳数作为节点的主要特性, 其中, 文献[34]中的MAGIC(max-gain in- network caching)算法考虑的是跳数的减少率, 而文献[35]中的OPP(opportunistic on-path)算法计算的是缓存节点至源节点的跳数与路径总跳数的比值, 文献[36, 37]中的节点状态主要是基于其在拓扑结构中的位置, 文献[38]考虑的则是节点的路径跳数和缓存容量.这些算法虽然从不同角度综合考虑了内容数据与节点数据, 但是它们缺乏网络整体的视角, 没有从全网的角度深层次地挖掘和分析节点数据和内容数据的关联性, 也没有进一步考虑不同时间阶段, 即不同概念间的相互影响关系.

上述成果为基于概念学习的缓存研究提供了基础.本文所提出的缓存机制与策略, 在节点数据和内容数据相互感知的基础上, 通过对不同环境下概念的挖掘与学习, 自适应地实现在不同概念下的缓存匹配.

2 基于概念漂移学习的缓存策略 2.1 多维状态属性数据的定义

为了实现缓存内容与网络节点的匹配, 将适当的内容部署在恰当的节点上, 缓存策略不仅需要考虑节点的当前状态, 还需要考虑内容的当前属性.因此, 缓存策略所需的数据应是能描述节点特性和内容属性等内容的多维数据.本文从数据分析的角度出发, 按照以下两个维度进行数据提取^[39].

(1)   在节点的维度上, 计算节点的缓存率及缓存替换率;

(2)   在内容的维度上, 定义内容在节点上的流行度及请求内容权重, 刻画出内容热度与节点的相关性.

2.1.1 节点维度

不同位置的节点在不同的时期具有不同的访问热度, 热度的变化可以通过节点缓存负载的变化来描述.节点维度就是通过缓存率和缓存替换率来分别描述节点在不同时期的负载状态.

定义节点缓存率为CR:

$CR = \frac{{\sum\nolimits_{i = 0}^n {CC{S_i}} }}{{CCS(v)}},$

其中, CCS(v)为节点v的缓存容量, CCS_i则表示该节点在单位时间内被缓存的第i个内容的大小.缓存率可有效地描述轻载时的缓存负载率.

定义节点缓存替换率为RR:

$RR = \frac{{\sum\nolimits_{i = 0}^{n'} {RC{S_i}} }}{{CCS(v)}},$

其中, RCS_i表示该节点在单位时间内被替换的第i个内容的大小.假设网络进入稳定状态后, 大多数节点缓存空间被占满, 此时, 缓存替换率可以有效地描述节点的负载和缓存状态, 并能反映出不同内容在节点的时效性^[40].节点缓存率与节点缓存替换率的结合构成了对节点完整状态的描述.

2.1.2 内容维度

任何流行内容在时间上都会经历上升期、流行高峰到最后衰减的动态变化过程, 而且内容的流行程度也受到地域位置因素的影响, 同一内容在不同节点上的流行程度也不尽相同.内容维度就是分析内容流行程度与时间和空间的相关性, 流行度描述了内容的流行程度随时间的动态变化趋势, 本文提出的请求内容权重则是在借鉴IDF(逆文档频率)概念^[41]的基础上分析内容与节点的空间相关性.

定义节点内容的流行度为LP_vi:

$L{P_{vi}} = \frac{{IR{N_{vi}}}}{{\sum\nolimits_{i = 1}^{n''} {IR{N_{vi}}} }},$

其中, IRN_vi计算的是单位时间内用户在节点v上对内容i的请求量, $\sum\nolimits_{i = 1}^{n''} {IR{N_{vi}}} $统计的是用户对该节点的总请求量.

定义请求内容权重为RW_vi:

$R{W_{vi}} = \lg \frac{m}{{m(i)}},$

其中, m(i)为请求内容i的节点数量, m为节点总量.$\lg \frac{m}{{m(i)}}$是关于节点集合范围的全局因子, 只关注节点数量, 不关注具体的节点.通过分析可知, 当较少的节点请求内容i时, 权重值较大, 表明节点v与内容i有着较强的相关性, 因此, 利用该权重值可区分出不同内容间的相对重要性.

2.2 匹配值的定义

内容与节点是否匹配可建模为二分类问题, 匹配值对应的就是分类结果.

TF-IDF(词频-逆文档频率)^[41]算法可以有效地评估一个词对一个语料库中一篇文档的重要程度, 而缓存黏度也用于评估内容的重要性, 因此在借鉴TF-IDF思想的基础上, 定义内容的缓存黏度为CV_vi:

$C{V_{vi}} = CR{N_{vi}} \times \lg \frac{m}{{m'(i)}},$

其中, m'(i)为缓存内容i的节点数量; $CR{N_{vi}} = \frac{{cr{n_{vi}}}}{{\sum\nolimits_{i = 1}^n {cr{n_{vi}}} }}$, crn_vi计算的是单位时间内用户对缓存在节点v上的内容i的访问量, $\sum\nolimits_{i = 1}^n {cr{n_{vi}}} $统计的是单位时间内用户对该节点上所有缓存内容的总访问量.缓存黏度正比于用户对节点上缓存内容的访问率, 而反比于缓存节点数量.通过缓存黏度的计算可以获得节点与被缓存内容的匹配程度, 值越大, 意味着节点v与缓存内容i的匹配度越大, 缓存越适宜.

定义匹配度的门限值TH, 当缓存黏度CV_vi≥TH时, 表明当前内容与节点具有较高的匹配度, 适宜缓存, 则令匹配值为1;否则, 令匹配值为-1.TH根据第1次采集到的缓存黏度集合的中位值来确定.采用中位值主要是为了避免极端缓存黏度值对匹配判断的影响, 并避免训练样本分布不均匀导致训练的不准确.

2.3 训练集与测试集的定义

训练集与测试集的符号描述借鉴文献[39]中的部分定义, 其中,

定义属性向量${a_{vi}} = (C{R_{vi}},R{R_{vi}},L{P_{vi}},R{W_{vi}}) = (a_{vi}^1,a_{vi}^2,a_{vi}^3,a_{vi}^4)$, 向量元素对应节点v与内容i的各状态属性.

定义数据集A_vi=(a₁₁, a₁₂, …, a_vi)为t时刻的标记数据集.为简化数据集的表示方式, 令A_vi=X_l=(x₁, x₂, …, x_l), 其中, x₁=a₁₁.

定义数据集Y_l=(y₁, y₂, …, y_l)为类别标记集合, 其中, y_q∈{1, -1}, 类别标记与匹配值相对应, 若标记值y_q=1, 则意味着该节点与内容匹配度较高, 缓存; 否则, 不缓存.

定义测试数据集X_u=(x_l+1, x_l+2, …, x_l+u)是时间序列t+Δt上需要计算的未标记数据集, 对应的类别标记集合定义为Y_u=(y_l+1, y_l+2, …, y_l+u).若计算结果为y_u=1, 则该节点上应缓存当前内容; 若y_u=-1, 则不缓存.

2.4 基于概念漂移学习的缓存算法

ICN网络中存在着海量的数据包在高速传输, 这些数据包构成了一种典型的数据流应用.由于网络流的分布随着网络环境动态变化, 因而任何内容在一定的空间区域内, 其流行程度在时间维度上都会经历从上升、流行高峰到最后衰减的过程, 这个过程的变化, 即概念的变化, 将对流量分布造成较大的影响, 因此, 本文提出一种面向不同概念进行自适应学习的方法来求解缓存匹配问题.

2.4.1 网络概念漂移的识别算法

针对概念漂移的识别, 很多研究主要是通过分析分类的准确率来识别是否发生了概念漂移, 但基于准确率的判断需要实时地对样本类别进行标记.然而标记样本需要大量的时间和资源作为代价, 因此本文提出了一种基于熵值检测的无标记概念漂移识别算法.定义两个由m×n个基窗口组成的滑动窗口, 一个记录历史数据, 一个记录当前数据, 通过滑动窗口机制不断比较两个窗口的熵值来分析其差异, 并根据差异性来识别是否发生漂移.其中, m是节点数量, n是流行度为前20%的内容的数量(由于ICN中内容的访问次数与其流行度满足Zipf-Like定律, 流行度排名为前20%的访问量约占网络总访问量的80%, 因此以排名为前20%的流行内容为研究对象), m×n个基窗口即是对当前网络环境下节点和内容状态属性的较完整描述.

定义在时刻t, 当前数据窗口的形式化表达为NW=(x₁, x₂, …, x_mn), 如果未发生概念漂移, 则该窗口中的状态属性数据将不断地被更新, 其中, mn=l.

定义在时刻t, 历史数据窗口的形式化表达为$OW = \{ x_1^o,x_2^o,...,x_{mn}^o\} .$

定义j是属性向量, 即窗口x_q中第j个元素, j∈{1, 4}, q∈{1, mn}.

定义b是元素的分支.将x_q中每个元素的值都进行归一化处理, 并将处理后仍位于[0, 1]之外的数据赋值为0或者1, 然后将1分为10等分, 比较归一化后的数值属于哪个区间, 对应的区间值则为1.例如, 当前数据为0.32, 则[0.3~0.4]区间的值为1.

定义窗口x_q中元素j在分支b上出现的次数为r_qjb:

${r_{qjb}} = {r_{(q - 1)jb}} + \left\{ {\begin{array}{*{20}{l}} {1,{\rm{ }}数据属于该分支}\\ {0,{\rm{ }}数据不属于该分支} \end{array}} \right.\;\;\;\;\;\;\;\;.$

定义窗口x_q的元素j在分支b上的熵为H_qjb=-P_qjblog₂(P_qjb), P_qjb=r_qjb/mn, 表示元素j在分支b上的概率.

定义窗口x_q的熵为

${H_q} = \frac{1}{4}\sum\limits_{j = 1}^4 {\sum\limits_{b = 0}^9 {{H_{qjb}}} } .$

定义前q个窗口的熵为

$H = \sum\nolimits_q {{H_q}} .$

定义历史数据的熵为$H_q^o$, 当前数据的熵为$H_q^N$, 当$\Delta H = (H_q^N - H_q^o)/q > \varepsilon $时, 则认为检测到第q个窗口时发生了概念漂移.这说明在某些情况下, 只需要对ICN中部分节点和内容的状态属性信息进行分析, 就可识别出概念漂移.漂移识别门限值ε的设置是依据Hoeffding边界^[42]来确定的.Hoeffding边界描述如下.

随机变量R的M个独立样本的均值和真实平均值的误差不超过ε的概率为1-δ, 则:

$\varepsilon = \sqrt {\frac{{{R^2}\ln (1/\delta )}}{{2M}}} $

(1)

Hoeffding边界默认δ=10^-7, 二分类问题的随机变量R=log₂2=1, 文中样本数M为1 600, 计算得到ε的值为0.07.

算法 1  描述了概念漂移的识别方法.算法实际上执行的是q次独立的运算, 每次运算都围绕一个三元组$(H_q^N,H_q^o,\Delta H)$展开.OW是历史数据窗口, 记录的是从检测到概念漂移后开始的m×n个状态属性样本.通过窗口的不断向前滑动, 检测是否ΔH > ε:如果是, 则识别出概念漂移, 用依次到来的两组数据分别更新OW和NM中的内容, 然后重复整个过程.

算法 1.   概念漂移识别算法.

1  Initialize: t=0, slidesize=constant

2     for q=1 to m×n do

3         slide OW and NM by slidesize points, and compute ΔH

4         if ΔH > ε then

5             t=current_time

6             report concept drift at time t and update OW and NM

7         else goto step 3

8         end if

9     end for

2.4.2 基于集成学习的缓存算法

当ICN的缓存环境发生概念漂移时, 根据先前概念训练的分类器对新样本空间的适用性将逐步减弱, 导致分类模型的分辨能力下降.因此, 需要在漂移点引入对新概念的重新学习, 更新分类器.为了避免单一分类器在不同问题上泛化表现的不同, 减少因分类器选择不当导致的泛化性能不佳的风险, 本文采用经典的Adaboost (adaptive boosting)集成学习算法生成缓存匹配决策的集成分类器, 通过对多种分类器的集成, 提高了分类结果的准确性.

集成学习的前提是:在检测到漂移点后, 需更新历史数据窗口OW的内容, 还需要对OW的内容进行标记, 并生成训练集{(x_q, y_q), q=1, 2, …, m×n}.Adaboost算法对训练集进行迭代学习, 每次迭代生成的弱分类器的分类结果都与标记进行比较, 然后根据降低分类正确样本的权重, 调高分类错误样本的权重的规则来更新样本的分布, 并将新样本作为下一轮学习器的输入进行新的弱分类器的学习, 若干个弱分类器的加权组合就是最终的集成分类器.弱分类器选用线性分类器.用集成分类器对后续时间序列上的状态属性值X_u=(x_m×n+1, x_m×n+2, …, x_m×n+u)进行预测, 即对不断更新的当前数据窗口NM中的数据进行预测, 预测结果Y_u=(y_m×n+1, y_m×n+2, …, y_m×n+u)就是对应的缓存匹配值.

2.4.3 基于概念重现的缓存学习算法

集成分类算法可以在检测到概念漂移时对分类器进行动态调整, 以适应新出现的概念, 即适应当前的ICN网络环境.但需注意的是:有时, 某些概念会在ICN网络运行中重复出现.当概念重现时, 如果能够将相同概念的历史分类算法迁移到当前的分类算法中, 这将有效地减少分类器的学习代价, 提高分类的准确率.

定义历史样本特征集合为HS={hs₁, hs₂, …, hs_k}, hs_k中存储的是当第k次检测到漂移点后的新的OW窗口中内容对应的标记.

定义历史样本特征的哈希值集合为HHS={hhs₁, hhs₂, …, hhs_k}, hh_k记录的是对hs进行β次哈希计算后得到的β个最小哈希值.

定义历史概念集合为HC={hc₁, hc₂, …, hc_k}里面存储的是每次概念漂移后由集成学习算法Adaboost生成的集成分类器, 与HHS表相对应.

设漂移后根据Adaboost算法生成的分类器为hc_k+1, 将其定义为主分类器mhc, 为了将从历史概念上学习到的知识迁移到当前概念中, 需从HC中选择一个与当前概念最为相似的概念作为辅助分类器.为从HC中选择最相似的分类器, 每次发现新概念后, 都通过minhash^[43]算法对当前的hs进行降维, 使用β个哈希函数对hs求哈希值, 得到β个最小哈希值hhs, 并将hs和hhs分别存入历史样本特征集合HS和历史样本特征的哈希值集合HHS, 然后基于LSH(局部敏感哈希)^[44]算法, 将已知的hhs中对应的哈希值进行聚类, 将相似的哈希值聚集到一起, 为后续的查找节约时间.计算当前概念下样本对应β的个最小哈希值, 并将当前概念下生成的哈希值分别与相似集中的每一个hs生成的哈希值hhs行相似度比较, 即计算最小哈希值相同元素的个数与总元素个数之间的比值τ, 比值越大, 越相似.选取相似度最大的hs对应的hc作为辅助分类器ahc, 则基于概念重现的分类学习算法的表达式为

$ f:y = sign({w_1}\left( {ahc\left( x \right)} \right) + {w_2}\left( {mhc\left( x \right)} \right)) $

(2)

其中, ω₁和ω₂分别为辅助分类器和主分类器的权重系数.若相似度大于阈值, 则令ω₁=ω₂=1/2, 说明是概念的重现, 预测的结果将是主、辅分类器共同作用的结果.假设主分类器mhc的预测准确率为δ, 辅助分类器ahc的准确率为$ \vartheta $, 显然, f的准确率是大于δ和$ \vartheta $中的最大值, 因而提高了算法的准确率.若相似度小于阈值HTH, 则令ω₁=0, ω₂=1, 这说明是一个新生成的概念, 并将该概念对应的哈希值和分类器分别加入HHS和HC.详细描述见算法2.

算法 2.   概念重现的分类学习算法.

1   Initialize HHS, HC, OW , HTH

2   detect concept drift at time t, compute mhc by Adaboost algorithm and hhs_k+1 by minhash algorithm;

3   for r=1 to length (HHS);

4   compute J(hhs_k+1, hhs_r) by LSH algorithm;

5   end for

6   J'=min(J(hhs_k+1, hhs_r));

7  if J'≥HTH,

8       ahc=HC[r], ω₁=ω₂=1/2

9   else ω₁=0, ω₂=1 and update HHS and HC

10  end if

11  compute prediction value by f=sign(ω₁(ahc(x))+ω₂(mhc(x)))

算法执行过程中, 相似度阈值HTH由中位值计算确定.由于每次识别出漂移后都需从历史概念集合中选择一个与当前概念最为相似的概念作为辅助分类器, 即计算当前概念与历史概念的相似度, 因此任意两个历史概念间都对应有一个相似度值, 从历史相似度中取中位值, 可有效避免极端相似度的影响, 而且算法简单.

2.5 缓存资源管理系统

缓存资源管理系统结构如图 1所示:每一个路由节点通过对Data数据包的统计分析, 可以计算出节点维度所需的原始参数, 如单位时间内节点上被缓存的内容数量或被替换的内容数量; 通过对Interest数据包的分析, 可以获得内容维度计算所需的原始参数, 如单位时间内对不同内容的请求次数, 也可统计出对已缓存内容的请求次数.这些原始参数作为附加内容, 随着Interest包转发给缓存资源管理服务器节点.为了便于对旧概念学习算法模型的快速调用, 在资源管理服务器中定义了一张存储历史概念的表, 表结构见表 1.该服务器节点通过对获得的多维数据进行挖掘、学习, 并将学习后的匹配结果通过Data数据包转发到各个节点上, 各节点根据匹配关系缓存相应的内容, 实现缓存内容的差异化.

2.6 基于概念漂移学习的缓存策略描述

缓存策略的基本思想就是:通过对感知获得的关于节点和内容的历史数据, 如缓存率、替换率、内容流行度、请求内容权重等状态特征进行分析挖掘, 并利用挖掘出的状态特征与缓存匹配值之间的函数映射关系, 对未来时期内的节点与内容间的匹配关系进行预测.预测方法整体流程描述如下.

首先, 采用高斯方法对多维状态属性的历史数据进行归一化处理, 以避免因为多维数据取值范围的不同对特征挖掘可能造成的影响.具体步骤如下.

●    首先, 根据公式计算各属性值$a_{vi}^j$, j∈(1, 4), 归一值定义为$a_{vi}^{rj}$, 表达式如下:

$a_{vi}^{rp} = 0.5 + \frac{{a_{vi}^j - \tilde a_{vi}^j}}{{2 \times 3\sigma _{vi}^j}}$

(3)

其中, $\tilde a_{vi}^j$是节点v中第j个属性的历史平均值, $\sigma _{vi}^j$是节点v中第j个属性历史值的标准差.

●    然后, 将归一后仍位于[0, 1]之外的数据赋值为0或者1, 公式如下:

$a_{v}^{r j}=\left\{\begin{array}{l}{0, a_{v i}^{r j}<0} \\ {1, \quad a_{v i}^{r j}>0}\end{array}\right.$

(4)

在归一化处理的基础上, 确定各属性值属于的分支区间.

然后, 采用自适应的概念重现学习算法, 利用多维状态属性值与缓存匹配值之间的函数映射关系, 预测未来时期的对应关系, 具体描述如算法3所示.

●    第1行、第2行是算法的初始化阶段;

●    第3行~第9行是当概念发生漂移后, 分类算法对OW中的状态属性值所定义的概念的学习过程, 包含对重现概念的迁移学习;

●    第10行~第36行是对随后到来的NW窗口中数据的处理过程, 其中,

➢    第10行~第17行描述的是利用OW窗口中学习到的概念对NW窗口中数据的关系进行预测, 即预测节点与内容的匹配关系;

➢    第18行~第23行描述的是与预测同时进行的概念漂移的识别过程, 其中, 行18描述的是漂移识别的算法, 行19描述的是当识别到概念漂移后进行重新学习的过程;

➢    第20行~第30行描述的是当服务器在进行重学习时, 内容与节点的匹配关系仍然按照漂移前的算法进行计算;

➢    第31行则说明:当重学习过程结束时, 将立即采用新的学习算法预测后续内容与节点的匹配关系;

➢    第32行、第33行描述的是若未识别到概念漂移的处理动作:若未识别到概念漂移, 则继续采用当前分类算法进行学习, 如第32行所示; 若对NW窗口中所有数据都已识别完成, 仍未有漂移产生, 则重新更新NW窗口中的数据, 再进行学习和识别, 如第33行所示.

算法 3.   自适应的概念学习算法.

Input: State attribute value $\{ {x_q}\} _{q = 1}^{mn}$ and $\{ {x_u}\} _{mn + 1}^{mn + u}$, cache viscosity $\{ C{V_q}\} _{q = 1}^{mn}$, threshold value TH, relationship value $\{ {y_q}\} _{q = 1}^{mn}$, entropy threshold ε, sampling numbers of OW T₀, sampling numbers of NW T_N;

Output: Relationship value $\{ {y_u}\} _{mn + 1}^{mn + u}$.

1   ω₁=0, ω₂=0, T_o=0, T_N=0;

2   OW=Ø, NW=Ø;

3     when T_o=T_o+1, update OW;

4         for q=1 to m×n in OW

5             if CV_q≥TH then y_q=1;

6             else y_q=-1;

7             end if

8     end for

9     Build classifier f=sign(ω₁(ahc(x))+ω₂(mhc(x))) by algorithm 2

10     set T_N=T_N+1, update NW

11     for q=1 to m×n in NW{ QUOTE brrhzimage:6:erhhz brrhzimage:7:erhhz

12         Y_u=sign(ω₁(ahc(x))+ω₂(mhc(x)));

13             if y_u=1, then

14                 cache the content i in the node v;

15             else

16                 do not cache the content i in the node v;

17             end if

18         compute $\Delta H = H_q^N - H_q^o$ by algorithm 1;

19         if ΔH > ε, detect concept drift, set T_o=T_o+1, goto step 3;

20             while (step 9 hasn’t done)

21                 {

22                 set T_N=T_N+1, update NW

23                     for q=1 to m×n in NW;

24                         Y_u=sign(ω₁(ahc(x))+ω₂(mhc(x))), where Y_u is the lastest hc

25                         if y_u=1, then

26                             cache the content i in the node v;

27                     else

28                         do not cache content i in the node v;

29                     end if

30                 }

31                 do step 10

32             else if q < mn, goto step 12;

33             else if q=mn, don’t detect concept drift, goto step 10;

34             end if

35         end for

36     end

3 仿真实验与分析 3.1 评价指标

缓存是ICN网络的重要特性之一, 其目的主要是为了降低网络运行成本和提高用户的体验质量, 使用户能快速就近获取内容.为量化上述缓存目标, 针对网络和用户分别引入不同的评价指标.在分析网络运行成本时, 定义了网络链路平均利用率(所有链路单位时间利用率的平均值)、服务器负载率(网络中所有服务器单位时间接收的请求次数与用户发出的请求总次数的比值)、缓存替换数(单位时间内所有节点替换内容数量的均值)、节点负载的Gini系数^[45](节点负载指的是节点上所有被缓存内容的总访问量, Gini系数定义为所有节点间负载的差值之和与负载均值之比再除以节点数量平方值的2倍); 在分析用户体验质量时, 定义了访问缓存命中率(兴趣包被缓存响应的数量与用户发送的兴趣包数量的比值)、访问延时(从发出兴趣包至接收到对应的数据包所需要的时间)、访问跳数减少率(利用缓存算法获得所需内容而经过的跳数与到服务器端获取内容的跳数相比而减少的比值)、内容差异率(节点缓存的内容种类数量与网络中服务器所产生的所有内容数量的比值)等指标.在实验过程中, 又分别分析了缓存容量及用户请求速率对网络运行成本及用户体验质量的影响.

在CDL算法性能评价方面, 针对算法的准确率, 定义了误报率(真实值为-1, 而预测值为1的概率)和漏报率(真实值为1, 而预测值为-1的概率)这两个评价指标.

3.2 实验参数设置

本文的仿真实验采用真实的域间拓扑结构AS-1755, 假设内容请求到达过程服从泊松分布, 用户对内容的请求模式遵循Zipf分布.用户的平均请求速率为100个兴趣包/s, Zipf参数设为0.7.网络中的内容数量共有71 000个.每个内容缓存时需要占用一个缓存单位, 网内缓存总容量范围为0.25GB~1.5GB.实验初始时, 每个节点的缓存内容量为0.本文将CDL策略与CEE策略^[15]、LCD策略^[16]、prob0.5策略^[22]和OPP^[35]策略的性能进行对比分析.针对OPP策略, 由于其考虑了内容流行度因素但没有考虑概念漂移对流行度的影响, 因此本文分析了两种场景下OPP策略的缓存效果:场景1是流行度的统计时间包含了概念漂移前与漂移后的两段时间, 实验结果在图中用符号OPPNC表示; 场景2是流行度的计算只基于概念漂移后的数据进行统计, 实验结果用符号OPPC表示.

3.3 实验结果

1.  对网络运行成本的影响

●    性能指标参数随缓存容量的变化情况

图 2为6种缓存策略的网络链路平均利用率随缓存容量的变化情况.可以看出, 链路利用率随着缓存容量的增加而减小.这是因为随着缓存容量的增大, 可缓存内容的数量也随即增多, 用户可在中间缓存节点获取所需内容的概率增大, 减少了缓存节点到服务器节点间链路的流量, 因此链路平均利用率降低.进一步分析发现, CDL的性能优于其他5种.例如:当容量为1GB时, CDL与LCD相比, 链路平均利用率降低了约10%, 与OPPC相比降低了约2%.产生这一结果的原因是:CEE, LCD和prob0.5在节点中缓存内容时并没有考虑节点缓存容量和转发差异性等因素, 只是较盲目地进行缓存, 当缓存的内容不能满足用户需求时, 用户仍然需要向服务器发出请求.在这三者中, CEE由于在节点上缓存所有内容, 网络中缓存的内容量最大, 用户从中间节点读取内容的概率最高, 因此链路平均利用率优于另两种策略.OPPNC与OPPC均考虑了内容流行度与节点位置的匹配关系, 但由于在计算内容流行度的过程中, OPPNC没有主动消弭概念漂移前的数据对流行度计算产生不良影响的手段, 因此, OPPNC对流行度的评估不如OPPC的准确, 最终导致对链路平均利用率的优化效果不如OPPC.而CDL通过不断捕捉网络概念的漂移, 并从漂移点进行新概念的学习, 然后利用学习的结果确定内容与节点的匹配关系, 同OPPC策略相比, 其对内容与节点的匹配关系的预测及评估更加准确, 因此链路平均利用率的优化效果更佳.

图 3为6种缓存策略下服务器负载率随缓存容量的变化情况.可以看出, 服务器负载率均随着缓存容量的增大而减少.这是因为, 随着缓存容量的增大, 节点上缓存内容的总量随即增多, 满足用户请求的概率相应增大, 用户到服务器直接请求内容的概率相应减少.当容量为1GB时, CDL与LCD相比, 服务器负载率降低了约10%, 与OPPC相比降低了约2%.

图 4为6种缓存策略下缓存替换数随缓存容量的变化情况.可以看出, 缓存替换数均随着缓存容量的增大而减少.进一步分析可知:CEE策略中被替换的内容数量最多, prob0.5策略替换数量最少.这是因为CEE策略的泛在缓存, 节点缓存了大量的冗余内容, 有效缓存容量最少, 新内容的缓存将产生较多的替换操作, 因此替换数量最多; prob0.5策略基于概率缓存, 缓存内容总量最少, 有效缓存容量相对较多, 因此当有内容缓存时, 需要替换的数量最少.CDL策略通过内容与节点的匹配计算, 有效地减少了缓存替换数量, 因此由缓存替换导致的节点存储操作开销也较少.

图 5为6种缓存策略下节点负载Gini系数随缓存容量的变化情况.负载的Gini系数是一个用于衡量概率分布不均匀程度的测度, 系数越小, 说明均衡性越好.从图中可知, CDL的Gini系数最小.这是因为在内容维度中定义了请求内容权重, 该权重与请求节点集合密切相关; 而在内容的缓存黏度的定义中也引入了缓存节点集合这一参数, 因此CDL策略不仅只是局限于追求某个内容与节点的缓存匹配效果, 还兼顾了节点集合的整体诉求, 将内容较均衡地分配给缓存节点, 网络流量则被较均衡地引导到缓存节点上, 降低了网络拥塞节点出现的概率, 可有效减少网络运行的维护成本.

●    性能指标参数随用户请求速率的变化情况

图 6~图 9分别为6种缓存策略下网络链路平均利用率、服务器负载率、缓存替换数、节点负载Gini系数随用户请求速率的变化趋势.此时, 缓存容量为1GB, 速率的变化范围是每个请求节点每秒发送50~250个请求.从图中可以看出:随着用户请求速率的增长, 这6种策略在链路平均利用率、服务器负载率、缓存替换数、节点负载系数等方面没有明显变化, 但是CDL策略的指标优于其余5种策略.

2.  对用户体验质量的影响

●    性能指标参数随缓存容量的变化情况

图 10为6种缓存策略下命中率随缓存容量的变化情况.可以看出, 命中率均随着缓存容量的增大而增加.这是因为随着缓存容量的增大, 中间路由器节点为用户提供的可访问内容相应增加, 从而缓存命中率提升.进一步分析表明, CDL的性能优于其他5种.例如:当容量为1GB时, CDL与LCD相比, 命中率提升了约20%, 与OPP相比提高了约3%.产生这一结果的原因是:CEE, LCD和prob0.5对内容的重复冗余缓存导致节点缓存内容频繁更新, 影响了命中率; OPP增加了流行度高的内容在靠近用户节点处的缓存概率, 提高了网内缓存命中率; CDL在时间上分析了网络的当前概念, 然后在空间上把内容合理地分布在网络中不同的节点上, 因而更有效地提高了网内缓存命中率.

图 11为6种缓存策略下, 访问跳数减少率随缓存容量的变化情况.可以看出, 访问跳数减少率均随缓存容量的增大而增加.当容量为1GB时, CDL与LCD相比, 访问跳数减少率降低了约30%, 与OPP相比降低了约2%.这是因为随缓存命中率的增加, 用户易从更近的节点获取所需内容, 访问跳数减少, 从而访问跳数减少率降低.

图 12为6种缓存策略下, 访问延时随缓存容量的变化情况.随着用户获取所需内容跳数的减少, 访问延时均减少.当容量为1GB时, CDL与LCD相比, 访问延时降低了约40%, 与OPP相比降低了约2%.

●    性能指标参数随用户请求速率的变化情况

图 13~图 15分别为6种缓存策略下命中率、跳数减少率、访问延时随用户请求速率的变化趋势.此时, 缓存容量为1GB, 速率的变化范围是每个请求节点每秒发送50~250个请求.从图中可以看出:随着用户请求速率的增长, 这6种策略在命中率、跳数减少率、访问延时等方面没有明显变化, 但是CDL策略的指标优于其余5种策略.

图 16是内容差异率的情况, 横坐标表示的是缓存内容的类别数量与内容类别总量比值的累积分布, 纵坐标表示的是节点的数量占总节点的比例.图 16(a)描述的是当缓存容量为0.75时, 在不同的缓存策略下, 内容差异率分布的变化趋势.CDL下内容差异率小于25%的节点数量约占30%, 差异率小于50%的节点数约为80%, 几乎所有节点的差异率均小于75%.图 16(b)描述的是在CDL下, 内容差异率分布的变化趋势与缓存容量间的关系.当缓存容量大于0.75GB时, CDL的内容差异率分布的变化趋势大体相同, 这是因为节点能够提供足够的空间缓存匹配的内容, 特定的节点缓存特定的内容, 不需要其他节点的协作; 而当缓存容量为0.25GB时, 一些节点的缓存容量不足以提供满足内容存储的空间, 需要缓存在其他节点, 因此内容差异率小于25%的节点数量约占15%, 差异率小于50%的节点数约为40%.

3.  算法准确率分析

CDL算法的误报率和漏报率的结果见表 2.

从表 2中可以看出:缓存容量的增长并未对误报率产生明显的影响, 而只是漏报率产生了小幅提升.这是因为, 由缓存黏度值的定义可知, 黏度值与节点上被缓存内容的访问量成正比.随着缓存容量的增加, 缓存替换数量减少, 这就意味着节点上的某个内容在被替换前可以被多次访问, 访问量增加, 因此黏度值相应地增加, 缓存匹配门限值变大, 因此漏报率增加; 但同时, 黏度值又与总访问量成反比, 当某一内容的访问量增加时, 总访问量也相应增加, 因此黏度的增长又受到总访问量的制约, 门限值的增长幅度受到限制, 漏报率增长并不十分明显.

4 结束语

如何将恰当的内容部署在合适的节点上从而提高ICN缓存资源利用率, 已经成为ICN缓存管理的研究重点之一.本文提出了一种基于概念漂移学习的缓存策略, 在对节点和内容等多维状态属性值和缓存匹配值的历史数据学习的基础上, 预测未来时期内的节点与内容间的关系.特别地, 本文提出了概念漂移识别算法和基于概念重现的缓存算法, 使内容能够根据当前网络环境对应的概念自适应地匹配到节点上.仿真实验结果表明:该策略不仅改善了用户体验质量, 而且降低了网络运行成本.

未来研究工作的重点拟基于软件定义网络的设计思想, 通过进一步感知网络实时状态信息, 在控制层挖掘出节点与内容的黏度关系, 确定出是否需要缓存, 进而在数据层执行这一决策, 从而进一步改善ICN性能.