基于SRv6的信息中心网络路由选择策略研究

厉瑞宣,周金和

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

0 引言

信息中心网络(information-centric network，ICN)发展的初始阶段，Vasilakos等提出了洪泛路由模式[1-3]，即请求节点根据转发信息表(forwarding information base，FIB)不加选择地进行全转发。文献[4]提出了一种基于距离原件的缓存策略，路由器仅在内容的原点与本身之间的跳距大于或等于给定的缓存阈值时高速缓存内容。文献[5]针对ICN路由问题，参考传统蚁群觅食的行为，提出基于蚁群觅食行为的启发式智能算法。文献[6]提出了一种基于兴趣域划分的 ICN 路由机制，采用蜂群启发式智能算法将节点划分为不同的兴趣域以便于节点路由查询，并利用多播路由算法进行数据包转发。

从最初的洪泛路由，到最短路径路由、随机路由以及启发式路由，和将机器学习用于流行度、路径等预测中，研究者们针对路由提出了各种优化方案。但这些路由方案大多是从局部出发，考虑因素比较单一或者适用范围比较小。在 ICN 中引入软件定义网络(software defined network，SDN)可以制定更高效的网络架构和ICN 路由策略[7-8]。而SRv6是基于IPv6数据平面实现的段路由(segment routing，SR)[9-13]，支持在头节点插入转发指令和网络功能指令指导数据包的转发和其他网络功能行为。本文分析当前ICN转发机制存在的问题，使IP与ICN共存[14]，利用SDN控制器和SRv6源路由的结合提出了一种基于SDN的SRv6-ICN新型网络模型，通过提出的基于跳数约束的K-means分簇路由算法，实现该网络架构的路由转发，从而提高网络性能。

1 基于SDN-SRv6的ICN网络架构

SRv6工作原理类似于计算机编程，即将网络承载的业务需求翻译成沿途经过的设备执行指令，由设备执行，达到网络业务灵活编排和按需定制的目的，并将网络功能指令化且嵌入128 bit的IPv6地址中。

根据SRv6和SDN的特点和工作原理，本文提出一种基于SDN-SRv6的ICN路由模型，将SDN和SRv6二者融入ICN中发挥其优势，使得网络性能更加高效，实现ICN网络的高效缓存和路由。SDN控制器通过收集网络拓扑情况，根据终端用户的需求做出路由决策，通过SRv6执行。在SDN控制平面，通过北向接口与应用层相连，用于接收数据包的请求，而在控制层面的缓存决策和路由决策通过南向接口下发给ICN进行缓存和路由。SDN-SRv6的ICN架构如图1所示。

图1 SDN-SRv6下的ICN架构

控制层面由请求处理单元、路由管理单元、缓存决策单元和路由决策单元构成，请求处理单元通过北向接口与应用层相连，用于请求数据包的接收。缓存决策管理单元用于封装缓存算法，判断数据是否缓存以及缓存在哪里，并生成缓存指令传递给SRH的Function。路由决策单元封装路由算法，用于计算转发的路径，并生成节点标识，压入Segment List中。路由管理单元维护和更新路由节点内容聚类表，以及Segment List，并与数据平面进行交互，将Segment List通过南向接口下发给数据平面。数据平面由具有ICN功能的SRv6组成。SRv6具有兼容性，如果考虑初始成本，可兼容IPv6路由器，原有的数据平面只具有转发功能。融合了SRv6的特性之后，可以根据功能指令表，执行本地指令。

2 改进的K-means路由分簇算法

2.1 基于跳数约束的K-means路由分簇

在本文所提出的网络架构中，寻找目标网络中从内容所在节点到请求节点的最佳转发路径，是完成内容传输的重要工作。只有当控制器找到了最佳路径，才能生成路由表和功能指令下发给源路由节点，进行后续的传输和功能行为，因此需要制定合适高效的路由算法计算最佳转发路径。综合考虑路由节点的兴趣偏好以及路由传输特点，改进K-means分簇算法，提出基于跳数约束的K-means路由分簇算法。

假设时间周期TN={t1,t2,…,tN}由N个时隙组成，路由节点有n个，路由集合V={v1,v2,…,vn}，在ICN中，根据路由节点的历史请求经验可以将请求内容分为娱乐、体育、教育等，每个类别对应一个兴趣标签。统计时间间隙t1内节点1、节点2和节点3请求每个兴趣标签的个数，如表1所示。

表1 节点请求兴趣个数表

(1)

如表1所示，可以根据节点1的特征属性建立矩阵：A=[1 0 0 1]，节点2的特征属性矩阵：B=[1 1/6 0 1/2]；两个向量可以根据余弦距离得到其相似度：

(2)

式中Ai和Bi分别代表向量A和B的各分量。

将每个节点的请求内容划分为k类，{c1,c2,…,ck}，每个请求内容必须属于某一类，定义k个簇中心为：{μ1,μ2,…,μk}(μj∈V)，有

(3)

(4)

其中式(4)为路由节点距离簇中心的余弦相似度。

s.t.C1∶Cw

C2∶Rw

(5)

式中：Γ为簇内节点vi所能到达的簇内节点的集合；Li为节点vi到达其他簇内所有能够达到节点的平均距离，平均距离越小，节点与其他节点距离越近；dij为两路由节点vi和vj的最短距离，即vi和vj需要经过的最短跳数，若vi需要经过一个中间路由到达vj，则dij=2；Cw为待处理数据的大小，Ci为节点vi的容量，CM为每个节点的最大容量；Rw为待处理数据所需要的数据处理能力；Ri为节点vi的数据处理能力；RM为每个节点的最大处理能力。

K-means根据路由节点的类别偏好相似度进行分簇，但如果两节点之间具有较多的跳数，那么这两节点便不适合划分在一个簇内。基于ICN跳数约束的K-means路由分簇算法步骤如下：

1)确定要聚类的类别数目k，选择k个中心点。

2)针对每个样本点，找到与其最近的中心点请求类别最接近的点，计算样本点与各个中心点的余弦距离，并按余弦距离进行降序排序。

3)依次判断各个中心点到样本点是否满足跳数约束，选择满足跳数约束的最近点。

4)判断聚类前后样本点类别情况是否相同，相同则终止算法，否则进入5)。

5)针对每个类别中的样本点，计算这些样本点的中心点，判断该聚类内是否存在该中心点，存在则选取其为中心点，否则选取与该中心点最近的点当作该类的新的中心点，继续2)。

如何选择初始中心点对聚类的影响较大，初始中心点的选择步骤为：

1)计算网络节点中紧密度最大的点c1，计算不在跳数约束范围内节点Γ的紧密度，与紧密度最大的节点最远点(相似度最低的点)c2。

2)计算Γ内节点与c2的相似度，选取不在c2跳数约束范围的最低相似度与介数最大的节点c3。

3)依次计算出满足簇中心个数的节点数。终止。

这是一个双目标优化问题，约束其中一个，极值化另一个，选出适合的中心点：

(6)

2.2 基于分簇的路由转发机制

利用提出的基于跳数约束的分簇路由算法，结合ICN兴趣包和数据包的转发机制，将提出的算法运用到SDN-SRv6的ICN网络架构中。首先获得节点对于文件的偏好程度，对节点进行K-means内容分簇，将相似的节点划分到一个簇集合。在节点请求阶段，相似的路由节点大概率请求相同的内容，这样不仅能降低请求节点的检索时间，也能降低系统的消耗。而SDN-SRv6架构，可以为提出的算法提供更好的帮助：利用SDN进行网络拓扑和网络服务的定制，将智能化决策放在控制器上，然后生成相应的指令列表，具有缓存功能和本地化编程的路由节点依据SDN下发的列表进行转发和执行功能指令。基于K-means的SRv6-ICN路由内容请求流程如图2所示。

图2 网络内容请求流程

内容请求阶段：

1)根据网络节点的历史请求偏好，利用K-means算法对网络系统进行K-means分簇，将大概率请求相同内容的节点划分到一个簇内。

2)当兴趣包到达某个路由节点以后，会先查询自身CS内容库是否存在请求内容。如果存在，则返回数据包，并丢弃兴趣包；若是没有，则会查找PIT表，检索路由节点是否存在已请求的该类兴趣包。如果可以检索到，则将请求接口添加至PIT；如果不存在进入步骤3)。

3)根据路由偏好查询请求节点所在簇内是否存在请求内容。如果存在，则根据Segment List返回请求内容，并添加条目至PIT；如果簇内未检索到请求条目，则继续步骤4)。

4)依据偏好路由查询其他簇是否存在请求节点请求内容。如果存在，则依据最短路径转发至请求节点所在的簇内节点，返回步骤1)；如果不存在，继续步骤5)。

5)判断数据服务器是否存在该请求节点的请求内容。存在，则下发给请求节点，丢弃兴趣包；不存在，则直接丢弃兴趣包。

2.3 评价指标

平均请求时延，定义为单位时间内请求节点收到数据包的个数占请求兴趣包的个数的比例，用来衡量节点成功获得数据包的效率，衡量网络的响应速度。平均请求时延为

(7)

式中：Ii的取值为{1，0}，当取值为1时表示节点Vi在该时刻间隙访问了该兴趣；Di的取值为{1，0}，当取值为1时表示节点成功地获取到了兴趣包。

丢失率定义为时间间隙Δt内请求节点收到丢失兴趣包个数占请求兴趣包的个数的比例：

Lloss=∑Ιloss/∑Ιsum

(8)

定义节点请求文件的系统成本φ(t)为

(9)

式中：φa为节点从簇内节点获得文件的开销；φb为节点从其他簇获得文件的开销；φc为节点从数据服务器获得文件的开销，且φa<φb<φc。

3 算法仿真及结果分析

互联网符合无标度特性，本文采用无标度网络模型对ICN进行仿真建模，参考文献[5]，选取节点数目N=100,设备路由节点每经过一跳的能耗值Ecost，所需时间值τ，每个数据包的最大等待时间τMax,仿真参数设置如表2所示。

表2 SRv6-ICN下K-means算法参数设置

网络中使用的数据包的大小为60 Byte，每个节点的数据包处理能力c=10 kpps。网络中的数据请求符合Zipf分布。Zipf 分布被大量应用于移动网络的缓存研究中，且被认为能很好地描述用户的文件偏好或者文件流行度(每个文件被用户请求的概率分布)[15]等，因此本文用 Zipf 分布来对用户请求每类文件的经验概率分布进行拟合。Zipf 概率分布为

(10)

式中：Pc为节点请求在其偏好中排名第c的类别文件的概率；rank(c)∈{1,2,…,C}为第c类文件的流行度排名；s为zipf分布的参数，描述节点偏好的偏斜度；C为类别总数。对式(10)两边取对数并整理[16]：

(11)

网络中数据包的最大等待时长5 s，即当一个节点排队处理的数据包个数超过50的时候，第51个数据包将会丢失。网络各节点的数据包由SRv6源路由节点从服务器获取，并由控制器下发路由表和缓存表。利用此网络模型来检验此算法的性能。经过多次仿真以后比较最短路径(OSPF)、随机路由算法(RA)以及本文提出的K-means算法的性能，比较在不同请求文件速率下运用这3个算法的请求数据包在网络中请求的平均数据包丢失率、系统开销以及平均执行时间的好坏程度。

聚类中心k的选择会影响聚类结果，采用误差平方和(sum of squared error，SSE)来评价聚类的好坏。样本集合V={v1,v2,…,vN}，k个类别的样本集合为C={C1,C2,…,Ck}。簇的中心点为

(12)

误差平方和为

(13)

式中o为cj中的点。

图3为误差平方和与聚类中心k的关系，误差平方和由簇内所有点与中心点的余弦距离和求得。一般情况下，k越大，SSE越小。假设聚类中心数与样本个数相等，每个点自成一类，每个类的中心点为这个类中的唯一的点，则SSE为0，由图3可以看到，k=5之后，SSE的下降变得很缓慢，因此最佳的k值为5。

图3 误差平方和与聚类中心k的关系

图4为系统开销与请求文件速率的关系。初始阶段，网络的请求数据包比较少，此时，网络的开销也比较小，而且比较起来，最短路径算法(OSPF)和随机算法(RP)的系统开销要小于K-means算法的开销，因为此时网络处于流通状态，且每个节点的队列数也比较小，采用最短路径算法往往是最有效果的。但随着数据包的请求数据增加，节点的处理能力跟不上数据包的产生速率，此时节点如果采用最短路径算法和随机算法便会造成拥塞，消耗网络成本。而K-means算法由于其根据节点的内容进行分簇，无需查询全网的节点便可以得到数据包，所以其消耗较少。

图4 系统开销与请求文件速率的关系

图5为数据包丢失率与请求文件速率的关系。当网络的数据包产生速率低于节点处理能力的时候，数据包几乎不会丢失，但当数据包产生的速率高于节点的处理能力时，节点的数据包会因为排队等候时间过长而丢失，数据包的丢失率会随着数据包发送速率的增加而增高，由于最短路径最先发生拥塞，所以OSPF算法丢失率是最高的，RP算法次之，K-means算法丢失率相对较低。

图5 数据包丢失率与请求文件速率的关系

图6为平均延迟与请求文件速率的关系，在网络初始阶段，由于系统处于流畅阶段，所以，此时算法的数据包延迟都比较低，而随着请求文件的速率的增加，OSPF最先造成拥塞，网络延迟比较高，RP次之，而K-means由于聚类的效果，往往只需要在自己簇内就可以命中自己的请求内容，不需要向全网发送请求文件需求，而这恰好提升了整个网络节点的处理能力，故在3种算法中，其网络延迟最低。

图6 平均延迟与请求文件速率的关系

4 结束语

本文提出了基于SDN-SRv6的ICN网络架构，较之单纯的ICN网络架构，增加了网络决策层和功能指令。提出一种具有跳数约束的K-means分簇路由算法，通过对相似路由更可能请求同样的内容的认知，将相似度高的路由节点划分到一个簇，往往通过簇内节点便可获得所请求的文件，而不必全网查询，以此来降低网络的查询时间，提高网络的响应速度。仿真结果显示，无论是请求时延，还是丢失率和网络成本，K-means分簇路由算法都优于最短路径算法和随机选择算法。

随着SRv6的技术越来越成熟，将其运用在ICN路由中，更能适应复杂的网络。特别是海量用户接入，网络负载加重时，运用本文提出的路由算法可以改善网络环境的拥塞，降低时延，且可以降低网络中能源的消耗，节约网络成本，降低系统开销。本文所提出的网络架构可以为未来网络架构提供参考，也为将智能算法应用到新型网络架构提供了思路。