0 引言

随着信息技术的飞速发展，网络应用的主体逐步向内容获取和信息服务演进。命名数据网络(Named Data Networking,NDN)^[1]作为典型的信息中心网络体系结构范例，采用“接收者驱动”的方式，节点的内容缓存(Content Cache)驻留了转发过的内容副本，以便以最短时延响应内容请求，减少服务器的响应负载和网络流量。然而，NDN的最初设计缺乏对业务特征的考虑，对于所有业务均采用泛滥式的全部缓存策略、机械式的一对一内容请求模式、盲目式的路由转发方式，不仅降低了缓存的命中率，增大了请求响应时延，而且难以保证业务的差异化服务需求。

目前NDN对于如何保证多样化业务的服务需求这一内容传输问题并没有给出成熟的解决方案。在文献[2-3]中，作者分析了信息中心网络(Information-Centric Networking, ICN)支持多媒体业务传输的优势和不足，对现有方案进行了对比分析，指出了目前存在的问题和下一步的研究方向。文献[4]依据可靠性和实时性指标，将内容划分为不同业务类型，设计了差异化的内容请求模式；但是该方案缺乏对于缓存决策和路由算法的考虑，且只给出了理论分析，缺乏实验验证。文献[5]将业务划分为实时业务和非实时业务，针对实时业务，采用一对多(one-request-n-packets)的请求方式“有效实时业务支持策略”(More Efficient Real-time Traffic Support, MERTS)，通过发送特殊兴趣包(Special Interest, SI)完成n个数据单元的同时请求。但是，该方案对于实时业务采用的仍旧是“所有内容普遍缓存”(Cache Everything Everywhere, CE²)的泛滥式缓存方式。文献[6]提出了一种支持快速和正常转发的双模式传输策略(Dual-Mode):对于共享内容，采用内容中心网络(Content-Centric Networking, CCN)原有的缓存和请求模式；对于私有内容，直接依据转发信息库(Forward Information dataBase,FIB)实现快速的路由转发，提高报文处理速度。Chanda等^[7]提出了一种基于软件定义网络(Software Defined Network,SDN)的信息中心网络内容管理层架构。在国内学者的研究方面，胡骞等在文献[8-9]中指出面向内容的网络未来研究的难点和发展方向之一就是对端到端业务的支持。例如基于互联网协议的视频会议业务、话音业务(Voice over IP, VoIP)、电子邮件(E-mail)业务等端到端业务，其重要性仍然不可取代，在未来网络中应当得到较好的支持。目前以内容为中心的网络架构主要着眼于内容分发的需求，对传统的端到端业务并没有提供差异化的服务并实现良好支持。葛国栋等^[10]提出了基于业务类型的多样化内容分发机制(Diverse Content Delivery Scheme based on traffic types, DCDS)，针对三种业务制定了差异化的内容请求和缓存方式，该方案在缓存命中率和平均请求时延方面性能优于已有算法，但方案未考虑差异化路由对多样化业务的影响，且未给出一种普适性的面向业务类型的差异化内容分发模型。

针对上述不足，本文认为研究业务请求特征驱动的差异化内容分发策略，需要在缓存、路由和内容请求的层面，设计和实现内容传递对业务类型的匹配和差异化服务，提升网络整体的服务效率和质量。为此，本文提出NDN中多态路由承载的内容分发模型(Content Delivery Model based on Polymorphic Routing,CDMPR)。借鉴网络重构^[11-12] 概念，将参与内容请求与数据转发的基础网络控制功能分解为四种类型的功能单元，包括内容请求类、内容查找类、路由计算类和数据缓存类。针对不同特征需求的业务类型，匹配不同的模块组合来承载，提供差异化服务。对于内容请求和数据缓存类的模块功能，文献[10]已有涉及，本文在此基础上，详细讨论路由计算类的模块实例，为不同业务类型匹配不同的多态路由计算实例，产生不同的数据存储结构，对应不同的内容查找流程，实现面向业务类型的差异化内容分发。

1 多态路由承载的内容分发模型CDMPR

本文不详细讨论具体的业务类型划分，借鉴文献[10]中对典型业务的定义，具体讨论三种业务：

1) 实时业务(业务类型1) 。内容后续共享程度小，私有性强，对于请求时延要求严格。

2) 非实时的流媒体业务(业务类型2) 。后续共享程度高，连续内容请求之间具有强相关性，对于带宽资源要求大。

3) 用户自产生内容(业务类型3) 。业务内容文件小，内容数量大，不同请求之间没有明显的相关性，对于时延和带宽没有明显要求。

针对业务特征的差异性，结合内容分发服务需求特点，本文提出重构模块的概念，将网络基础控制功能分解为细粒度的服务单元，完成内容请求、内容查找、路由计算和数据缓存四种类型的基础服务，称之为重构模块，用集合C表示，该集合是封闭的且元素有限。通过对控制平面和数据平面不同重构模块的组合实现个性化定制业务承载机制的派生，使得网络具有动态调整适应多样化业务的服务功能。重构模块作为基础网络控制功能单元，提供四类基础服务，如图 1所示。具体可将内容请求、内容查找、路由计算、数据缓存的每类功能进行功能抽象，包括逐一内容请求、相关并行预测请求、持久兴趣请求、渐进式缓存、边缘缓存、不缓存、捷径路由、循迹路由、蚁群路由等。重构模块的引入，不仅可以对集合中模块实例进行动态组合以实现多种业务类型的区分式服务，也可以向集合中添加新型的模块实例以实现网络功能的快速扩展，增强新型业务的个性化支持能力。

就重构模块的具体实例而言，内容请求类和数据缓存类模块的实例由文献[10]中的DCDS算法给出，这里不再详细讨论。本文将在此基础上，详细讨论路由计算类的模块实例，为不同业务类型匹配不同的多态路由计算实例。多态路由^[13]问题，即由基本路由功能派生出功能特定或服务质量(Quality of Service,QoS)特定等多模态特性的多态路由机制，是基于多样化应用的业务特征要求和网络动态行为驱动构建的，基于基态路由模型进行实例特化以满足具体应用所需的各种约束属性服务路径的路由机制。基态路由的建立和派生过程在文献[13]中已有讨论，本文采用查询匹配报文字段的方式，实现多种路由算法的共生和切换。

为实现对业务类型的区分和查询匹配，在CCN原有兴趣包和数据包中添加业务类型(Type of Service, ToS)字段，为实现后续业务类型扩展功能，该字段定义为8 bit；另外，添加报文类型(Type of Packet, ToP)字段，用于标识不同业务的请求和应答报文。后续参与转发的沿途节点依据ToS和ToP字段取值，执行多态路由实例映射，通过模块组合串的动态组合，实现面向多种业务类型的差异化区分承载，如图 2所示。

对于实时业务(业务类型1) 而言，为满足时延、带宽等QoS约束，引入改进蚁群路由算法实例，求解多约束最优路径，生成蚁群路由表(Ant colony Routing Table,ART)。在响应兴趣请求时，优先查询ART表项，当蚁群路由失效时，再查询传统路由算法生成的FIB表。对于非实时流媒体业务(业务类型2) ，采用循迹路由算法，生成数据包轨迹表(Data Trace Table, DTT)。当查询内容存储器(Content Store,CS)和未决兴趣表(Pending Interest Table,PIT)失败时，优先查询DTT表项在新近转发的历史数据中寻求所需数据内容。对于用户自产生内容(业务类型3) ，采用导向性副本通告的捷径路由，生成捷径路由表(Shortcut Routing Table, SRT)，充分利用附近邻居节点的暂态缓存数据。当查找CS、PIT表项失败时，优先利用SRT表项进行路由。

2 基于改进蚁群优化算法的路由转发方式

首先对面向QoS需求的实时业务传输进行建模。NDN用无向赋权图G=(V,E)表示。其中：V为网络节点集合，E为链路集合；F={F₁,F₂,…,F_N}为网络中的内容集合。对于内容请求者节点C和内容f∈F，存在m_f个内容提供节点(content provider)，其节点集合为P={p₁,p₂,…,p_mf}。 p(C,P_f)表示从consumer至provider的传输路径，C(p)、D(p)、Bw(p)、L(P_f)分别表示路径p的花费代价、路径时延、路径带宽和路径丢包率。

定义1 时延、带宽、丢包率约束最短路径p(C,P_f)。给定网络G=(V,E)，实时业务传输的时延上限Δ_d、带宽下限Δ_Bw、丢包率上限Δ_L，若路径p(C,P_f)满足:

$C(p)=\min \sum\limits_{e\in p(C,{{P}_{f}})}{C(e)}$

(1)

$\eqalign{ & {\rm{s}}{\rm{.t}}{\rm{.}}\quad D\left( {p\left( {C,{P_f}} \right)} \right) = \{ \sum\limits_{e \in p(C,{P_f})} {D\left( e \right)} \} \le {\Delta _d},\forall {P_f} \in P \cr & \quad \quad Bw\left( {p\left( {C,{P_f}} \right)} \right) = \min \{ Bw(e),e \in p(C,{P_f})\} \ge {\Delta _{Bw}}, \cr & \quad \quad \quad \forall {P_f} \in P \cr & \quad \quad L(p(C,{P_f})) = \{ 1 - \prod\limits_{e \in p(C,{P_f})} {[1 - L(e)} ]\} \le {\Delta _L}, \cr & \quad \quad \quad \forall {P_f} \in P \cr} $

则p(C,P_f)称为时延、带宽、丢包率约束最短路径。

文献[14]已经证明求解两个及以上约束条件的QoS路由问题是 “NP-完全”问题。本文研究利用改进的蚁群算法来提高求解速度。蚁群算法^[15]是一种智能启发式算法，通过模拟自然界中蚁群协同合作觅食的行为，实现多约束满足问题的最短路径求解。其基本原理是通过不断迭代计算从当前节点i到邻居节点j的状态转移概率实现下一跳端口选择。从蚁群优化算法的基本原理可以看出，这种模拟进化算法的正反馈机制使其具有许多优良性质，然而算法仍存在一些缺陷，如初期收敛速度慢、容易陷入局部最优值等，本文主要从信息素更新策略和状态转移规则进行改进。

2.1 信息素更新策略

定义2 收敛度Con。网络节点i的FIB表中对应某具体内容名字为c的可转发接口个数为N_i^c，每个接口j对应的信息素为τ_ij^c(x)，归一化后其信息素总和为1。则节点i内容c的信息素收敛度定义为：

$Con_i^c(x) = \sqrt {\sum\limits_{j = 1}^{N_i^c} {{{\left[ {{1 \over {N_i^c}}\sum\limits_{j = 1}^{N_i^c} {\tau _{ij}^c(x)} - \tau _{ij}^c(x)} \right]}^2}} } $

(2)

当内容c对应所有接口的信息素相等时，收敛度为0；当转发接口只有一个时，其收敛度达到最大$\sqrt{1-1/N_{i}^{\text{c}}}$。在算法执行初始阶段，收敛度值较小，而随着蚁群信息素的不断更新，收敛度逐渐增大。为加速算法的计算进程，同时避免陷入局部最优解，信息素更新策略为：

$\tau _{ij}^{n}(x)=\tau _{ij}^{n}(x)+{{\Delta }_{x}}(1-\tau _{ij}^{n}(x))$

(3)

${{\Delta }_{x}}=-(x-1)\exp (x)(1-Con_{i}^{\text{c}})$

(4)

信息素的更新原则是在当前信息素的基础上累加信息素的增量值。由上述信息素定义可知信息素增量应与时延、丢包率成反比。同时，Δ_x与收敛度Con_i^c成反比，收敛度较小时，信息素增量应该较大，增大信息素的增加速度以加快收敛；而收敛度较大时，就应减小信息素的增量避免早熟现象的发生。

2.2 参数调节

由文献[16]中分析可知，对于参数α和的β选择，做同样幅度的调节时，β的调节效率更高。当β很大时，算法会迅速收敛于信息素浓度高的路径，在算法执行后期，算法会迅速收敛于局部最优解路径。这里给出β的取值方式如下：

$\begin{align} & \beta =\frac{1}{Con_{i}^{c}(x)+\varepsilon }= \\ & {{\left\{ \varepsilon +\sqrt{\sum\limits_{j=1}^{N_{i}^{c}}{{{\left[ \frac{1}{N_{i}^{c}}\sum\limits_{j=1}^{N_{i}^{c}}{\tau _{ij}^{c}(x)}-\tau _{ij}^{c}(x) \right]}^{2}}}} \right\}}^{-1}} \\ \end{align}$

(5)

其中:ε为接近0的小数，避免Con_i^c(x)为0时作为除数的情况发生。从搜索的全局过程来看，初期时Con_i^c(x)为0，β的取值充分大，可以用很小的计算量就加速收敛进程，排除不可能解；随着搜索过程的进行，收敛度Con_i^c(x)逐渐增大，β值减小，避免算法收敛于局部最优解。

引入蚁群路由算法后，NDN节点在原有的FIB之外，增加了状态信息表，记录内容对应的转发接口的信息素值和相应的转发概率。

3 循迹路由策略 3.1 算法思路

由于业务特点的不同，CCN算法不能很好地支持流媒体业务，表现在三个方面：1) 流媒体业务内容共享度高，可以被后续反复请求，沿途节点对于该类数据的缓存可以有效提高后续请求的就近响应，然而泛滥式缓存导致大量的同质内容冗余。2) 业务内容文件大，对于带宽资源要求高。如果内容请求都发送至内容源处进行响应，将消耗大量的网络带宽资源。3) 文件内容一般包含多个数据块单元，用户需要连续发送多个兴趣请求，分别等待响应。

文献[10]提出了边缘缓存和并行预测请求模式，解决了同质内容冗余问题，缩短了响应等待时间。然而，缓存在边缘节点的数据内容只能响应本地的用户请求，未得到最大限度的利用，为此本文提出循迹路由算法，充分发现网络边缘节点缓存的内容数据块，利用循迹路由对内容请求进行响应，减小核心网络和内容源服务器的负载压力。除了CCN中已有的CS、PIT和FIB外，增加新的数据结构——数据包轨迹表，将内容请求路由至其他边缘节点，充分利用转发过的数据包历史信息。如图 3所示，在C向Content Server请求过Data之后，根据缓存策略将之存储在路由器C的CS中，之后D也请求该数据。依照原有路由规则，因为B本地未存储Data副本，只能将兴趣包沿Path1路由。然而引入数据包寻迹路由策略后，每个节点都保留了已转发过的数据信息，B可将该请求沿Path2转发至C处。为防止缓存替换引起的缓存命中失效，在DTT表项中引入生存时间参数，超过生存时间的数据包轨迹将不再保留。

3.2 路由表项设计

每个DTT条目包含4个表项：Name表示命名内容的前缀；To表示转发的数据包的去向端口，也作为后续相同内容请求的转发端口；From表示数据包的来向，用于撤销无效路由时的端口比对和路由回溯；Lifetime表示该条目的生存时间。DTT表项的建立和利用过程如图 4，该策略区别于原有策略的处理方式为图中虚线方框内部分。

如图 4所示，当数据包到达后，查询PIT条目根据相应端口转发数据包，并建立DTT的表项。当兴趣包到达时，首先查询CS是否缓存内容，失败后查询PIT表，当查询PIT条目失败后，再查询DTT表，如果命中，则根据DTT条目的To端口转发内容；如果失败，则查询FIB并据此路由。需要指出的是，由于PIT表项的汇聚作用，数据包会转发至多个端口，并在To表项中留下多个端口的轨迹记录，在利用DTT转发时，只依据端口繁忙程度选择最轻闲的端口转发。定义端口繁忙程度为节点在PIT所有条目中出现的总和，以S_k表示。如果一个PIT条目包含端口k，S_k的值将被加1；如果一个PIT条目被删除，其所属的端口的值将被减1。单径转发是避免多径引起的流量冗余，选择最轻闲端口作为下一跳，也是避免后续路径中的节点缓存命中失效。如果某一端口在不同的PIT条目中频繁出现，则说明与此端口相关联的下一个节点将有更多的内容返回，导致更多的机会来触发缓存替换，缓存的变化将会较其他节点频繁。所以，转发端口应选择对应PIT条目中值最小的端口，其关联节点的缓存替换概率相对最低。

4 基于导向性副本通告的捷径路由机制

与实时业务、点播流媒体等业务不同，网络中的用户自产生内容(User Generated Content, UGC)^[17-18]也拥有庞大的数量，包括静态图片、文本信息共享等。然而针对该类业务设计路由决策的研究还少有文献涉及。为利用渐进式缓存方式在网络核心存储的内容副本，并控制通告代价，本文提出一种导向性副本通告机制。通过分析节点间的兴趣相似性(Interest Similarity)，将网络划分为若干兴趣社区(Community)。节点只在Community内部实现导向性的缓存通告，不属于同一Community的节点之间不具备相互通告权限。在获知通告内容的基础上，建立到达内容副本的捷径路由(shortcut routing)。

整体流程包括：兴趣社区构建、导向性副本通告和捷径路由构建。其中兴趣社区构建是基于离线的共同兴趣统计结果，是大尺度的时间范畴；社区内副本通告是社区内缓存副本变化触发的，满足通告条件的缓存副本删除或者更新时，才将该消息通告社区内各节点；捷径路由构建基于缓存副本通告的结果，结合源服务器路由的代价，给出最小代价路由作为捷径路由。

4.1 兴趣社区构建

路由节点中的兴趣内容是各用户兴趣的叠加综合，内容需求极其广泛，需选择节点中访问频次最多的活跃内容作为节点的代表兴趣。节点间共同的代表兴趣越多，则两者之间相似度越高。将两者划分为同一兴趣社区后，共享内容的成功率越高。对于给定的两个节点i和j，它们的兴趣集合为S(i)和S(j)，那么共同兴趣为I_c=S(i)∩S(j)。

定义3 相似度系数(Similarity Coefficient)。若节点i对内容c的访问次数为N_c,i，那么共同兴趣的相似度系数为$\varphi (i,j)=\sum\limits_{\text{c}\in {{I}_{\text{c}}}}{\frac{{{N}_{c,i}}+{{N}_{c,j}}}{\left| {{N}_{\text{c},i}}-{{N}_{c,j}} \right|+\delta }}$，其中δ为正数。

定义4 社区管理员权重 (Community Principal Weight)。对于节点i，其社区管理员权重定义为节点i和邻居相似度系数之和$\omega (i)=\sum\limits_{j\in Neighbor(i)}{\varphi (i,j)}$。

定义5 投票等待时延(Voting Delay Time)。对于节点i，其投票选择社区管理员的等待时延为τ(i)=1/ω(i)。

节点的社区管理员权重越大，与邻居节点的兴趣相似度越高。若该节点被选为社区管理员，则总的收益越大。每个节点通告自身ω(i)前需等待τ(i)时间。自身的ω(i)越大，成为社区管理员的可能性越大，需要等待的时间越短，则越可能在社区管理员选取中争得先机。节点收到比自身ω(i)大的投票时，为了避免冗余流量，将较大的ω(i)通告出去，自身的ω(i)不再通告。

以下是兴趣相似性社区(Interest Similarity Community,ISC)构建具体算法流程。

算法1 兴趣相似性社区构建算法(Constructing Algorithm for ISC)。

输入 网络拓扑G(V,E)，内容请求分布：N_c,i，TTL。

输出 兴趣相似度社区G(ISC)，社区管理员M(ISC)。

1) 对于节点i计算自身的社区管理员权重ω(i)；

2) 计算节点自身的投票等待时间τ(i)，并等待时间τ(i)；

3) 在τ(i)内没有收到投票消息，则发送自身ω(i)，并设置TTL。

4) 节点τ(i)内收到ω(j)，如果TTL≥1，且自身ω(i)>ω(j)，则将i加入M(ISC)，将i和j加入G(ISC)，自身的ω(i)通过投票消息发给邻居节点，TTL减1。

5) 如果收到的ω(j)>ω(i)，将j加入M(ISC)，将i和j加入G(ISC)，将ω(i)通过投票消息发给邻居节点，TTL减1。

6) 重复上面的操作直到TTL=0。

4.2 导向性副本通告

由于节点缓存内容频繁更替，为了避免内容更替触发新的内容通告，进而导致消息膨胀，通告报文只选择缓存中部分“稳定”内容进行通告。首先节点缓存内部依据缓存策略——最近最少使用(Least Recently Used, LRU)策略或者最不经常使用(Least Frequently Used, LFU)策略进行排序，其次选择排在前列的若干比例x的副本条目在社区内通告。由于节点内部的缓存更替，当通告的缓存副本条目发生变化时，则触发新一次的副本通告，避免路由时的内容缺失。

在完成兴趣社区构建的基础上，节点已划分到具体的兴趣社区。当满足通告触发条件时，执行副本通告，初始化操作为：节点i设定自身所属的社区Community和当前时间戳TS_new，构造本地缓存内容前x%的副本通告报文(初始代价为Cost₀)，并向社区内的所有邻居发送该通告。假设邻居节点j已记录了内容c的路由表项为{C, Face_old，TS_old，Cost_old}(若没有内容c的记录则时间戳TS_old=0) ，在收到通告报文时，新的表项为{C, Face_new，TS_new，Cost₀}，执行下述操作：

步骤1 判断Community字段是否相同:如果不是，说明不属于同一兴趣社区，丢弃该报文，算法结束；否则，执行步骤2。

步骤2 判断TS字段:若TS_new>TS_old，则执行步骤3；否则，丢弃该通告报文，通告结束。

步骤3 计算接收报文的Cost值：Cost_new←Cost₀+Cost(i,j)。若TS_new=TS_old，判断Cost_new与原有代价Cost_old的关系，若Cost_new≥Cost_old，则丢弃该报文，执行步骤5；否则执行步骤4。

步骤4 将Cost_new填入通告报文的代价域，转发给节点j的邻居节点。

步骤5 通告结束。

4.3 捷径路由建立

在兴趣相似性社区内完成缓存条目通告后，节点j会收到其所在社区关于内容c的通告报文，表明节点j可以在有限跳数的社区范围获得内容c，则节点j需执行的操作是：提取内容名字c、到达接口Face和到达此副本的代价C_Copy，据此计算捷径路由，步骤如下：

步骤1 判断捷径路由的代价是否最优。如果C_Copy>C_Server(C_Server为FIB中到内容源服务器的代价)，则该捷径路由代价太高，删除该条目；否则在捷径路由表中创建到达内容c的路由条目，代价为C_Copy。

步骤2 当有多个内容副本的代价C_Copy都比服务器代价C_Server小时，则${{C}_{\text{Copy}}}=\underset{i}{\mathop{\min }}\,{{C}_{\text{Copy}}}\left( i \right)$，选择其中最小代价的Face作为捷径路由。

5 仿真与性能分析 5.1 仿真环境与参数设置

由于ndnSIM^[19]工具提供了开放的源码和运行实例，并实现了CCN的基本数据结构单元和路由转发流程，本文采用该工具进行仿真。节点个数为50，连接概率为0.3的网络拓扑由GT-ITM下的Locality模型随机生成，在NS-3python下的可视化显示如图 5所示。在网络中分别设置4个与上述三种业务相关的内容服务器，其中2个服务器分别与节点14和40直接相连，负责实时业务(业务1) 内容集的存储和数据产生，另外2个服务器分别与23和30直接相连，分别负责非实时流媒体(业务2) 和用户自产生内容(业务3) 类业务内容集的存储、数据发布和响应。边缘节点作为用户接入节点，发布内容请求。为了模拟上述业务流，借鉴文献[20]的构造方法，将对速率有较高要求的业务1由相应的内容服务器产生恒定数据流，发送速率设为γ；对于业务2请求，将非实时流媒体内容设为2 000(以1~2 000编号)，每个内容划分为10个chunk，大小设为10 KB，请求概率服从Zipf分布，第i个内容的推送概率为：$p\left( i \right)=c/{{i}^{\alpha }},C={{\left( \sum\limits_{i=1}^{2000}{\frac{1}{{{i}^{\alpha }}}} \right)}^{-1}},\alpha =1.2$^[20]；对于业务3请求，将内容对象总数设为8 000(2 001~10 000) ，每个内容只含有1个chunk，请求概率服从Zipf分布(α=0.8^[20])。假设节点缓存容量一致，设为20 MB，初始缓存状态为空；仿真时间设为500 s，内容请求到达速率λ=100个/s，采样周期T=5 s。

5.2 性能分析

为了对CDMPR的性能进行评价，本文选取CCN^[1]、MERTS^[5]和DCDS^[10]算法进行对比分析。具体的评价指标和性能对比如下：

1) 平均响应时延(Average Response Delay, ARD)。内容请求者发送Interest Packet到接收到Data Packet为止的时间间隔，定义为平均响应延迟ARD。图 6分别给出了γ=800 kb/s，预测参数ρ_cor=0.90^[10]和γ=1 600 kb/s，ρ_cor=0.95时，各业务的ARD对比。对于业务1而言，CCN算法对于所有业务内容不加区分地进行缓存，浪费了实时业务的内容查找时间，其ARD最大;CDMPR算法对于实时业务内容的缓存和查找功能作了优化，其ARD性能有所提高，随着改进蚁群算法最优路径搜索的执行，收敛后的算法性能进一步提升。对于业务2而言，由于初始节点缓存为空，随着CCN算法执行，节点缓存内容响应率逐渐增加，ARD逐渐减小；随着发送速率增加，节点缓存实时业务内容的比例增加，使得业务2的缓存命中率降低，故而γ=800 kb/s的ARD性能优于γ=1 600 kb/s的性能；CDMPR将业务2内容推送到网络边缘缓存，故而随着缓存资源逐渐发挥作用，加之循迹路由算法有效利用网络边缘缓存，其ARD性能得到提升，发送速率越高，算法提升越明显。对于业务3，CCN算法性能与业务2类似，比业务1的ARD性能有所提高；CDMPR算法将业务3的内容缓存在网络核心节点，捷径路由算法可有效利用附近兴趣社区的缓存资源，有效降低了ARD。

2) 缓存命中率(Cache Hit Ratio, CHR)。兴趣请求由路由节点的缓存CS进行响应的比例，定义为缓存命中率CHR。网络中节点缓存内容响应兴趣包请求的概率越高，平均响应时延也越小。图 7给出了γ=800 kb/s，ρ_cor=0.90时在仿真时间500 s内各节点业务2和业务3的缓存命中率。

CCN算法中节点CE²缓存方式使内容重复冗余较大，无论对于业务2还是业务3，节点缓存命中率普遍偏低；MERTS机制将实时业务内容排除在缓存内容之外，为其他两类业务留出了更多的缓存空间，有效提升了缓存命中率；DCDS算法将业务2和业务3在缓存存储位置上加以区分，使业务2以更大概率缓存在网络边缘，业务3缓存在网络核心，使节点缓存资源的整体利用率得以提高；CDMPR算法不仅使得缓存分布更为合理，有效减小了重复的缓存冗余和频繁内容替换导致的缺失率，还利用了不同的路由机制将缓存内容进行有效利用，循迹路由增大了业务2的缓存命中率，捷径路由增加了业务3的CHR，在DCDS的基础上各节点的命中率又得以进一步提升。

5.3 代价开销对比

1) 业务控制开销(C_C)。将控制开销C_C定义为额外控制字段或报文的长度与其传输路由跳数(H_hop)的乘积，单位为：bit·hop。

${{C}_{\text{C}}}=({{C}_{\text{R}}}+{{C}_{\text{A}}}+{{C}_{\text{P}}})\cdot {{H}_{\text{hop}}}$

(6)

2) 节点存储开销(C_S)。CDMPR方案引入的额外存储开销包括：蚁群路由计算过程中的状态信息表ART；循迹路由增加的循迹路由表DTT；捷径路由表SRT。代价单位为：bit。

${{C}_{\text{S}}}={{C}_{\text{ART}}}+{{C}_{\text{DTT}}}+{{C}_{\text{SRT}}}$

(7)

${{C}_{\text{ART}}}=\sum\limits_{i=1}^{l}{\{{{L}^{n}}_{i}}+[\sum\limits_{j=1}^{m}{({{L}^{f}}_{i,j}}+\sum\limits_{k=1}^{n}{{{L}^{p}}_{i,j,k})}]\}$

(8)

${{C}_{\text{DTT}}}=\sum\limits_{i=1}^{w}{L_{i}^{n}}+\sum\limits_{j=1}^{u}{L_{j}^{f}}+\sum\limits_{k=1}^{v}{L_{k}^{t}}+\sum\limits_{p=1}^{x}{L_{P}^{L}}$

(9)

${{C}_{\text{SRT}}}=\sum\limits_{i=1}^{a}{L_{i}^{n}}+\sum\limits_{j=1}^{b}{L_{j}^{f}}+\sum\limits_{k=1}^{d}{L_{k}^{d}}$

(10)

其中:Lⁿ、L^f、L^p、L^L和L^d分别表示内容名字、接口信息、信息素值、生存时间和路由代价的字段长度；l,m,n,w,u,v,x,a,b,d分别为对应的存储数量。

3) 内容传输开销(C_T)。其定义为请求响应过程中，内容请求兴趣包和应答数据包报文长度分别与其传输距离的乘积之和，代价单位为：bit·hop。

${{C}_{\text{T}}}=({{P}_{\text{Int}}}+{{P}_{\text{Dat}}})\cdot {{H}_{\text{hop}}}$

(11)

其中:P_Int、P_Dat分别表示兴趣包和数据包的报文长度；H_hop为对应的路由跳数。

表 1给出了在仿真时间为5 s，ρ_cor=0.95，γ取值分别为800 kb/s和1 600 kb/s, Zipf分布指数α分别为1.2、0.8和1.4、1.0时，各方案对应的控制、存储和传输代价开销对比。CCN算法采用逐一内容请求模式，不引入额外的控制开销，C_C=0，但其传输开销最大；DCDS已在MERTS机制基础上通过有限的控制开销大幅降低了传输开销；CDMPR方案不仅增加了控制开销，还引入了存储开销，但其传输开销较DCDS有明显降低(约33.5%)。还可以看出，当指数α增大后，两种业务对应的内容请求分布更加集中，CDMPR对应的内容请求开销C_T和控制开销C_C都不同程度地降低。

5.4 复杂度分析

报文头部控制开销:设命名数据网络支持的业务类型为S种，每种业务类型对应的报文种类为M_i(i=1,2,…,S)，则支持元模块承载的差异化服务需付出的额外报文头部开销(单位bit)为:

${{C}_{\text{p}}}=\operatorname{lb}\left( S \right)+\operatorname{l}\text{b}\left( \max \left( {{M}_{i}} \right) \right)$

(12)

缓存通告开销:引入兴趣社区构建和相似性报文通告的额外开销，定义为缓存通告报文CAP与其传输距离的乘积，大小取决于通告报文长度、通告频率和路由传输跳数(单位bit·hop)。

${{C}_{\text{A}}}={{f}_{\text{CAP}}}\cdot (S_{\text{CAP}}^{1}\cdot {{d}_{1}}+S_{\text{CAP}}^{2}\cdot {{d}_{2}}+...+S_{\text{CAP}}^{\max }\cdot {{d}_{\text{max}}})$

(13)

其中:f_CAP为CAP报文通告频率，max表示兴趣相似性社区的最大规模，S_CAPⁱ表示兴趣相似性社区i中缓存通告消息长度，d_i为通告跳数。

相比CCN, CDMPR中循迹路由未引入新的计算，缓存内容通告过程不引入新的计算，只有改进蚁群路由算法在时间复杂度和空间复杂度上有所增长，其时间复杂度为T(n)=O(N_it·n²·m)，其中N_it为迭代次数，n为节点数目，m为蚁群中蚂蚁数目。

空间开销用于蚁群信息素的存储和更新，以及状态转移概率的存储，空间复杂度为S(n)=O(n²)+O(n·m)。因为改进蚁群路由是在原有FIB路由的基础上引入蚁群优化算法探测最优路由，其计算过程可与数据转发同步进行，在算法迭代计算完成后，将最优转发接口写入FIB，故而改进蚁群路由算法的额外计算开销不会影响节点的正常转发。

6 结语

本文针对NDN在支持多样化业务内容请求与传输方面的不足，提出了多态路由承载的内容分发模型(CDMPR)。该模型将基础网络控制功能单元分为内容请求、路由计算、内容查表和内容缓存四种类型，通过匹配不同的重构模块组合实例来承载不同特征需求的业务类型；并详细设计了面向三种业务的多态路由算法。仿真结果表明，相比DCDS算法，CDMPR方案以有限的控制和存储代价，提高了4.45%~13.8%的平均缓存命中率，降低了实时业务、非实时流媒体业务和用户自产生业务的平均响应时延。