面向ICN的软件定义遗传蚁群融合路由策略

王 晶,周金和

(北京信息科技大学 信息与通信工程学院，北京 100101)

0 引言

如今，随着互联网的快速发展，网络应用日益多样化，网络流量大幅度增加。根据思科的最新统计预测，到2022年，全球年度IP流量将达到每年4.8 ZB[1]。随着网络规模的不断扩大和用户需求的不断增加，传统的TCP/IP体系架构逐渐暴露出传输效率低、安全性差、移动性差、网络资源利用率低等弊端。为了彻底解决传统网络存在的弊端，信息中心网络(information-centric network,ICN)应运而生[2-3]。目前，ICN的研究项目有CCN/NDN[4-5]、DONA[6]、4WARD-Netlnf[7]等。ICN体系架构利用内容路由和缓存来分离内容请求者。内容路由将兴趣包传递到用户，内容提供者通过数据包将内容返回给内容请求者。缓存的目的是通过缓存用户频繁使用的内容副本来快速响应用户兴趣请求，从而减少带宽使用和延迟，提高路由效率。

目前ICN面对的主要挑战是如何设计高效合理的路由和缓存策略，从而使内容请求者得到更好的服务体验。Vasilakos 等[8]提出了一种全转发的路由机制，但全转发机制会造成网络产生大量的冗余流量。Eum 等[9]提出一种基于势场的ICN路由策略(PBR)，在这种策略下，兴趣包可以根据邻居节点的场强大小选择最佳的请求路径。蚁群算法也被应用于ICN路由优化[10-11]。其中，Shanbhag等[10]提出了一种SoCCeR蚁群路由算法，将兴趣包路由定向到负载较轻的转发端口。但是其存在前期收敛速度慢的问题。李昕冉等[12]提出一种基于果蝇算法的能效路由策略和缓存策略。该策略能够有效减少网络能耗并迅速获取网络内缓存情况，避免大量的网络内容冗余，降低由网络设备管理引起的能耗。

近年来，软件定义网络(software defined networks，SDN)[13]是网络领域的一个研究热点。SDN可以将控制层面和数据转发层面解耦分离，且可以提供灵活的可编程性以及高度的可控制性。这些特点使得SDN能够很好地适应各类新型的网络架构和协议。结合SDN和ICN[14-16]，既可以利用SDN的集中控制和全局视图功能，又可以很好地利用ICN在内容获取方面的优势，使路由更加智能，在一定程度上节省了网络带宽，减少了用户访问延迟，提高了路由效率。

如今大多数对ICN的研究都是将路由策略和缓存策略分开来讨论的，而且绝大多数ICN都是采用最简单的最短路由策略，把侧重点放在了缓存研究上。此外，当前对ICN的研究绝大多数依据局部信息，结合全局信息的研究少之又少。针对以上问题，本文提出了一种面向ICN的软件定义遗传蚁群融合(software-defined combination of genetic algorithm and ant colony optimization，SDGAAC)路由策略。SDGAAC利用控制器的集中控制和全局视图功能，通过将综合考虑链路延迟、链路利用率和节点畅通程度的遗传蚁群路由算法，与基于节点流行度和内容流行度的邻居协作缓存策略相结合，达到减少内容在网络中的传输延迟、提高缓存命中率、均衡网络中节点负载的效果。

1 SDGAAC系统模型

1.1 系统架构

SDGAAC系统架构如图1所示，其主要由控制平面和数据转发平面两部分构成。

图1 SDGAAC系统架构

控制平面负责域内的路由决策和缓存决策，主要由4个模块构成。其中内容管理模块能够收集域内所有内容的位置信息和兴趣包的请求信息，以供控制器做出决策；拓扑信息管理模块能够实时收集域内的网络拓扑信息，以供路由决策模块和缓存管理模块制定路由和缓存策略；路由决策模块通过内容管理模块和拓扑信息管理模块提供的链路状态信息和内容信息，制定高效的路由转发机制；缓存管理模块可以利用控制平面感知的拓扑信息和网络缓存状态，制定合理的缓存策略，减少网络缓存冗余，优化网络资源分配。数据转发平面主要由内容路由器构成，负责兴趣包和数据包的转发。

1.2 网络模型

本文将ICN网络拓扑建模为一个有n个节点和m条边的无向连通图，记为G=(V,E)，其中V={v1,v2，…,vn}代表网络中的内容路由器集合；E={e1,e2，…,em}代表网络中的链路集合。另外，如果内容路由器节点vi与vj相邻，则vi与vj之间的边也被表示为eij∈E。eij的链路利用率表示为uij，其值越大，则说明当前链路的已使用带宽越多，可以利用的带宽越少。

网络中每个内容路由器由内容存储表(content store，CS)、待决兴趣表(pending interest table，PIT)和转发信息表(forwarding information base，FIB)组成。其中，CS作为本地缓存，用于缓存网络内转发的内容副本；PIT用于记录兴趣包到达接口以及对应的请求内容名称，实现对相同内容请求的聚合，避免网络内请求信息的冗余；FIB用于将内容名称映射到输出端口，并通过这些端口将兴趣包转发至合适的内容提供者。

2 SDGAAC路由策略

本文提出的SDGAAC路由策略的关键，是在遗传蚁群融合(genetic algorithm and ant colony optimization，GAAC)算法的基础上，利用SDN控制器全局视图和数控分离等特点制定个性化的缓存策略和路由转发机制。

2.1 GAAC算法的基本思想

2.1.1 GAAC算法中的遗传算法

1) 编码

对于遗传算法而言，编码的方式很大程度上决定了算法的效率。其中最常用的两种方法是二进制编码和符号编码。对于路由问题，符号编码更为适用，可以使用节点编号作为基因编码，既易于理解又减少了解码的步骤。一条染色体包括一系列的编号，这些编号包括路由过程中经过的节点。由于路径有不同的中间节点，因此染色体是可以变长的，但是不会超过网络中的总节点数目n。

2) 种群初始化

为了保证种群的多样性和随机性，根据指定的种群规模，随机生成指定规模的个体，其中每个个体代表一个解，而编码方式采用的是符号编码。因此，编码序列的首尾分别为网络请求的源节点和目标节点。在每次选择下一节点时，采用随机选择的方法，随机选择一个未被访问过而且相邻的节点，重复此操作。若下一节点为目的节点，则停止循环；如果无法找到下一节点，则采取回溯机制。

3) 适应度函数

适应度函数衡量染色体的质量。当染色体的适应度高于其他染色体时，其值比较高。考虑到链路的状态，适应度函数被定义为：

(1)

D(p)≤D

(2)

B(p)≥B

(3)

DJ(p)≤DJ

(4)

式中：D(p)、U(p)、B(p)、DJ(p)分别为路径p的总延迟、最大链路利用率、瓶颈带宽和时延抖动；t1和t2分别为时延和最大链路利用率的权重值；D、B、DJ分别为内容请求者对带宽、时延和时延抖动的需求。路径p的总延迟越小，最大链路利用率越小，则在后续操作中保留的概率越大。

4) 选择，交叉，突变

选择的目的是提高种群的平均质量，使高质量的染色体有更多的机会被复制到下一代。在遗传算法中使用轮盘赌选择法。染色体被选中的概率和适应度的值成正比。本文遗传算法中采用单点交叉的方法，交叉概率为pc。突变保持了种群基因的多样性，突变概率为pm。

2.1.2 GAAC算法中的蚁群算法

1) 信息素初始化

蚁群算法利用遗传算法输出路径集合的前20%对信息素浓度进行初始化。蚂蚁初始种群数量为M,初始化的信息素值如式(5)所示。

(5)

2) 转发概率

ICN路由节点在数据转发中起着关键作用，路由器的性能影响着兴趣包转发的效率。若路由节点的缓存空间不足，当兴趣包到达而无法及时处理，则有可能造成丢包频繁等问题，降低网络服务质量。因此，对兴趣包计算转发路径时，为了避免路由器节点过载而造成丢包的问题，不仅需要考虑链路延迟和链路利用率，同时也需要将路由器节点的畅通程度考虑在内。蚂蚁k在选择下一跳时的概率为

(6)

式中：Vk指的是蚂蚁k在vi处可以选择的下一跳集合；α、β、γ为调节因子，α用于调节转发概率对信息素浓度值的依赖程度，β用于调节转发概率对链路延迟和链路利用率的依赖程度,γ用于调节转发概率对节点畅通程度的依赖程度。ηij(t)的定义如下：

(7)

其中，dij(t)和uij(t)分别为eij上的链路延迟和链路利用率，dij(t)和uij(t)越小，则ηij(t)越大。φj(t)的定义如下：

(8)

其中：cj和qj(t)分别为vj的节点处理能力和兴趣包缓存队列。φj(t)用来评价节点的畅通程度，其值越大，代表节点越畅通。通过将τij(t)、ηij(t)和φj(t)相乘，有助于挑选链路延迟和链路利用率更小、节点更畅通的下一跳。

3) 信息素更新规则

信息素更新规则如下：

τij(t)=(1-ρ)τij(t)+ρΔτij(t)

(9)

(10)

其中：Q为常数值；Lk为蚂蚁k在t次迭代中走过的路径程度。

蚁群算法经过多次迭代后，得到最优路径。

2.2 缓存策略

在数据包返回过程中根据缓存管理器执行的缓存策略进行主动缓存。传统的缓存策略有LCE[4]、ProbCache[17]等。LCE会在内容返回过程中经过的每一个点缓存内容，造成大量的缓存冗余；ProbCache把缓存节点与用户之间的距离作为主要考虑因素，却忽视内容本身的特性。针对目前缓存策略不足而导致的缓存冗余过多的问题，本文综合权衡节点流行度、内容流行度、节点到内容请求者的距离、缓存剩余容量等因素来确定内容的缓存位置。各因素定义如下：

节点流行度Pi：指在T时间段内用户的兴趣请求经过当前节点的数量Ni占兴趣请求总量Nsum的比值，用于衡量节点在网络中的重要程度。

(11)

内容流行度Pc：指T时间段内用户对内容c的兴趣请求数量Nc占兴趣请求总量Nsum的比值，用于衡量内容的流行程度。

(12)

节点到内容请求者距离比Hi：指当前节点到内容源节点距离hi与用户到内容源节点距离Hl的比值，比值越大，则缓存的内容距离用户越近，缓存概率越大。

(13)

CS剩余容量比χi:是指当前节点可用缓存容量C(i,a)占缓存总容量C(i,total)的比值。

(14)

一般来说，用户希望将内容流行度高的内容缓存到网络中距离用户近、缓存容量充裕的重要节点。因此数据包原路返回过程中在节点vi缓存内容c的概率为

P(i,c)=Pi·Pc·Hi

(15)

如果经过计算选择节点vi进行缓存，则首先判断vi节点缓存空间是否充足，若是，则直接将内容缓存在该节点；若缓存空间不足，则判断内容流行度是否为前10%，若是，则执行最近最少使用(least recently used，LRU)缓存替换策略进行内容替换，否则，在节点vi的邻居节点(不包含返回路径上的节点)选择A(i,c)最大，即选择节点流行度高且缓存容量充裕的邻居节点进行缓存，这样可以充分利用网络中的缓存空间。

A(i,c)=Pi·χi

(16)

2.3 路由转发流程

2.3.1 兴趣包转发流程

兴趣包的转发流程如图2所示。当内容路由器收到兴趣包时，首先检查其CS中是否有与之匹配的内容。如果在CS中找到与兴趣包匹配的内容，则将包含对应内容的数据包沿着兴趣包传入接口原路返回；如果没有，则检查PIT中的条目，如果PIT中存在与兴趣包内容匹配的条目，则将兴趣包传入接口添加至PIT中，否则，继续查询FIB；如果FIB中存在匹配的条目，则按照对应接口来转发兴趣包；如果没有，则兴趣包被转发到控制器。当路由器将兴趣包的信息发送到控制器时，控制器首先查找本地内容管理表(local content management tables，LCMT)，检查域内是否存在所请求的内容，如果存在，则根据接收到的Packet-In消息和全局网络信息，通过GAAC路由算法计算兴趣包的转发规则，以流表的形式下发到ICN节点；否则，将兴趣包回溯或者丢弃。

图2 兴趣包转发流程

2.3.2 数据包转发流程

数据包的转发流程如图3所示。当内容路由器收到数据包时，首先查找PIT，如果存在匹配的PIT条目，内容路由器会将数据包发送到其接收兴趣包的接口，并删除该PIT条目，然后询问控制器是否缓存当前内容，控制器依据2.2节制定的缓存策略在该节点以及周围节点缓存该内容；如果PIT中不存在匹配项，则丢弃该数据包。另外，数据包与兴趣包采用相同的转发路径，但方向相反。每个兴趣包都具有内容请求者设置的生存周期，如果兴趣包在其生存周期结束之前没有得到满足，则删除对应的PIT条目。

图3 数据包路由过程

3 算法验证及分析

由于互联网满足无标度特性，本文采用NetworkX库构建BA无标度网络对ICN进行建模。网络中包含100个ICN节点，在网络拓扑生成过程中每次增加两条边，网络拓扑结构如图4所示。网络中其他仿真参数如下：每个节点的兴趣包处理能力c=10，用户请求速率R=50，网络随机选取用户进行请求，并且用户请求服从Zipf分布，将反映内容请求集中度的Zipf分布参数δ设置为1(0.7～1.1)，t1=1，t2=10，pc=0.6，pm=0.05，M=10，α=1，β=1，γ=1，ρ=0.2，Q=100。

图4 网络拓扑结构

为了证明本文所提的SDGAAC路由策略优于其他ICN策略，将本文算法与SPF路由策略[18]、ACO路由策略[10]分别从平均路由延迟、缓存命中率、节点负载3个方面进行对比。由于本文路由策略考虑了数据包转发流程中的缓存阶段，为了更加合理地对比，为SPF路由策略和ACO路由策略分别添加LCE和ProbCache缓存策略，如表1所示。

表1 策略对比

平均请求延迟定义为生成兴趣请求与返回相关内容或失败时的时间差。图5展示了在不同的兴趣请求数量下，不同策略所对应的平均请求延迟。从图中可以看出，在初始阶段，3种策略的平均请求延迟相差不大，SDGAAC策略较其他两种策略延迟稍大。这是由于兴趣请求的记录比较少，对应FIB条目也比较少；并且网络中除了内容源节点，其他内容路由器节点缓存备份为空，所有的兴趣请求都需要上传到控制器获取转发路径，从内容源节点获取所需内容。随着兴趣请求数量的增加，3种策略的平均请求延迟都逐渐下降，在网络达到稳态后变化趋势逐渐平缓。在此阶段，本文提出的SDGAAC路由策略在平均请求延迟上优于其他两种路由策略。这是由于SDGAAC可以综合考虑链路时延、链路利用率和节点的通畅程度，使得兴趣包优先选择通畅的路径，前往距离用户较近的缓存备份节点获取所需内容；同时将内容流行度高的内容缓存在距离用户节点近的重要节点，缩短了后续的兴趣请求获取内容的时间。

图5 平均请求延迟

缓存命中率即网络中节点响应兴趣请求数量占兴趣请求总数的比例。图6给出了Zipf参数设定为0.7～1.1时3种策略缓存命中率的对比。SPF采用处处缓存的方式导致了缓存冗余，且有较高的缓存替换率，降低了缓存的可用性，使得缓存命中率最低；ACO使用的缓存策略把缓存节点与请求节点之间的距离作为主要考虑因素，但是未考虑各个节点的状态，虽然在一定程度上提高了缓存命中率，但是效果有限。SDGAAC综合考虑了节点状态和内容的流行度，并与邻居协作缓存，使得缓存可用性相对较高，故缓存命中率优于上述两种策略。

图6 缓存命中率

节点负载的分布情况能够直观地展示不同路由策略平衡负载的能力。图7中展示了3种策略节点负载的分布情况，由图可知SPF的节点负载分布在10%～80%，ACO的节点负载分布在12%～40%，而SDGAAC的节点负载分布在12%～34%。SDGAAC节点负载的分布较其他两种策略相对均匀，这是因为，SDGAAC综合考虑了兴趣请求的缓存队列长度和节点处理请求能力来均衡负载，从而在转发兴趣请求时可以有效地提高网络中路由器节点队列空间的利用率，能够优化兴趣包的传输，有效均衡网络中节点负载。

图7 节点负载

4 结束语

信息中心网络是未来网络领域研究的热点。本文提出了一种面向ICN的软件定义遗传蚁群融合路由(SDGAAC)策略。该策略利用控制器集中控制和全局视图功能，通过将遗传算法和蚁群算法相结合，根据链路状态和节点畅通程度寻找最优转发路径，并根据节点特征和内容流行度与邻居协作做出缓存决策。实验仿真结果表明，本文所提策略可以在保证用户QoS的前提下一定程度上降低平均请求延迟，提高缓存命中率，均衡网络节点负载。本文虽然考虑了用户QoS需求，但没有区分不同内容的业务类型，可以在未来的工作中继续研究。