一种基于马尔可夫模型的加速ICN路径收敛性的方法

麻朴方，王劲林，尤佳莉

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京100190； 2.中国科学院大学，北京 100049)

0 引 言

5G网络将会在2020年前后大规模商用，5G的3大特性分别是超高带宽、超低时延和超高密度连接，因此它将会推动新的应用(比如AR/VR、物联网)的快速发展。传统IP网络主要解决端到端的通信，而现在的应用需求逐渐从端到端通信转移到用户到内容的获取，也即用户更在意如何快速获取内容而不是从何处获取内容。在此背景下，ICN(Information-Centric Networking)[1-2]被提出来。ICN放弃了原有的IP协议栈的细腰模型，使用内容名字作为协议栈的核心结构。ICN名字的命名规则主要分为层次化命名方式和扁平化命名方式。层次化命名方式，比如NDN(Named Data Networking)[3]和TRIAD[4]，由于名字具有聚合性，可以使用名字作为路由标识，在名字解析的过程中实现路由，也即耦合了名字解析和路由；而扁平化的命名方式，比如MobilityFirst[5]和DONA[6]，由于名字不可聚合，无法使用名字作为路由，所以还需要类似于IP地址的可聚合的网络地址进行路由，名字和网络地址通过解析系统实现映射。本文的研究内容主要针对MobilityFirst这种标识和地址分离的设计架构展开。这种设计方式解耦了主机的标识和网络地址，通过标识和地址解析系统能获得主机标识对应的最新地址，能够天然地支持移动性和多宿主。同时这种设计使得多宿主终端能够拥有多个网络地址，因此可以实现目的地址的“晚绑定”(late binding)，也即先在数据包中插入多个地址，在转发过程中根据网络动态进行地址的选择，从而提高传输的性能[1]。

文献[7]中介绍了多种基于IP的多宿主方案，主要集中在网络层和传输层。网络层实现多宿主主要通过位置和标识分离的方法或者核心与边缘分离的方法来实现，而传输层的方法主要通过建立多个TCP连接来实现。主要的网络层的多宿主方案包括LISP(Locator/ID Seperation Protocol)[8]和HIP(Host Identity Protocol)[9]。HIP实现多宿主是通过在网络层和传输层加入了新的协议层来标识主机，而网络层用于路由。LISP使用2种新的标记RLOCs(Routing Locators)和EIDs (Endpoint Identifiers)取代IP地址。RLOCs按拓扑结构分配给接入点，地址是容易聚合的，用于路由和转发；EIDs独立于网络的拓扑结构，用来标识设备。EIDs主要用于边缘网络，而RLOCs用于核心网络的路由。SCTP(Stream Control Transmission Protocol)[10]和MPTCP(Multi-Path TCP)[11]是基于TCP改进的传输层协议。SCTP建立多条路径连接，一条作为主路径，其余作为备用路径；而MPTCP则同时利用多条路径来提高传输速率。文献[12-13]是对SCTP方案的改进，通过协同使用多个路径提高传输的稳定性；文献[14-15]对MPTCP的默认路径调度器进行改进来提高传输效率。以上提到的多宿主方法不能在转发过程中根据网络的动态进行路径的调整，主要是在边缘选择地址，从而选择转发路径。这是由于当转发数据包时，路由器不能意识到只携带一个地址的数据包是发送给多宿主终端的，因此只能沿着路由表的最短路径进行转发，即使有更好的选择或者遇到链路拥塞，也不能提供更好的QoS。

基于此本文提出了ICN的多宿主场景下多地址路由方法，在该方法中，发往多宿主终端的数据包中携带多个目的地址，这样数据包可以根据网络的动态进行灵活的路径选择。该多宿主路由方法具体细节将在1.1节中介绍。由于数据包在每跳根据不同的目的地址进行转发，这就打破了根据路由表沿着最短路径进行转发的规则，带来充分利用网络的资源进行传输的好处，但也会增加数据包的转发跳数，造成数据包为了获得较好的传输性能而不能尽快地收敛到目的地。

目前有一些提高ICN路径收敛性的方法。在文献[16]中，研究者根据请求的需求和网络的状态使用动态规划的方法来计算最适合请求的路径。Vassilakis等人[17]根据网络的缓存能力来设计一种高效的内容分布方法，该内容分布可以使得路由充分利用这些缓存信息来从较近的节点获得内容，从而减少路径的跳数。目前的研究主要是通过路由转发方法将请求内容引导到最近的缓存节点，减少路径的跳数，进而提高路径的收敛性，与多地址场景下的路径收敛性有差异，因此需要针对多地址场景下的路径收敛性差的问题进行方案设计。

本文分析ICN多宿主场景下路径收敛慢的原因，并设计一种基于马尔可夫模型的多地址裁剪方法，该方法根据地址裁剪的历史信息和跳数来决策是否进行地址裁剪，从而能减少数据包的跳动，尽快收敛到目的地。实验结果表明该方法在保证传输性能的同时能使数据包尽快收敛到目的地。

1 ICN多宿主路由转发分析

1.1 基于协议无感知转发技术的ICN多宿主路由架构

ICN多宿主网络架构是基于协议无感知转发技术(Protocol-Oblivious Forwarding， POF)[18-19]，POF是SDN(Software-Defined Networking)[20]控制层和转发层的接口协议，它通过定义一套协议无感知的指令集实现网络的全可编程性，能够实现网络的灵活管理和自定义的数据包转发。文献[21]利用POF的协议无感知转发的特性来承载ICN，使得快速部署实现ICN变得可能。该架构基于ICN的标识和地址分离特性，通过解析系统获得主机标识对应的所有地址，从而更好地支持多宿主。图1描述的是基于协议无感知转发技术的多宿主网络架构，该架构中包括控制层和转发层，控制层和转发层通过POF协议通道进行通信，控制器通过制定转发表来指导数据包的转发，POF交换机通过流表来处理数据包。其中终端标识ID与网络地址NA(Network Address)解析在控制器上完成。发往多宿主终端的数据包携带多个目的地址，本文NA使用的是IPv4，其他的地址放入IPv4包头的“选项”域中，“头部长度”域可以标识含有的目的地址数目。

图1 基于POF的ICN网络多宿主场景架构

由于多目的地址的数据包在匹配转发表后，每个地址会获得一个对应的转发端口，故可能有多个转发端口供选择。为了实现根据状态选择转发端口，在除了拥有转发表外，该架构下的交换机中还拥有状态表，这个状态表根据网络的动态信息进行计算，以用于在多个转发端口之间选择满足数据包性能需求的路径。另外，数据包也需要在转发的过程中裁剪掉无用的目的地址，保证数据包到达终端时只携带一个地址。在获得多个转发端口的时候，根据状态表选择状态好的端口进行转发，状态好的端口对应的地址称为“优先”地址，而其余地址则是优先级低的地址，需要被裁剪掉。

1.2 ICN多宿主路由路径收敛性分析

数据包中携带多个目的地址是路径收敛慢的主要因素，或者说数据包携带了优先级低的地址，因为只携带一个地址的数据包将会沿着路由表的转发规则沿着最短路径进行转发，而多个目的地址使得在不同的跳根据不同的目的地址进行转发，从而打破了最短路径转发。这种打破最短路径转发的方法使得网络中的流量能利用网络中的空闲资源提高传输速率，但也带来收敛慢的问题。比如图2中，链路上标识的是路径状态值，值越大代表链路传输性能越好，多地址数据包从S1到H1，携带H1的地址IP1和IP2，从S1到IP1和IP2的最短路径分别是S1-R1-R2-R4-H1和S1-R1-R3-R5-H1。为了追求较好的传输性能，多地址数据包可能沿着S1-R1-R2-R3-R4-R5-H1的路径传输。这条路径虽然传输性能最好，但是跳数较多，有可能还会跨多个自治域，这就增加了时延和传输的代价。为了平衡这些利弊，需要适当的方法来对优先级低的目的地址进行裁剪。比如在R2上删除数据包中的地址IP2，从而避免将数据包转发到R3。

图2 路径收敛性分析

携带多个地址能提高传输的性能，因此地址裁剪的过程要能够平衡传输性能和路径收敛性。基于此提出以一定概率来进行地址裁剪，这个概率可以根据需要设定，这样能够在转发过程中逐渐减少地址的数目，从而提高收敛性。在第2章中将介绍使用马尔可夫模型来计算地址裁剪的概率。

2 基于马尔可夫模型的多地址裁剪

2.1 基于马尔可夫模型的地址裁剪方法描述

携带多个目的地址的数据包的地址表示为IPs={IP1,IP2,…,IPn}，匹配完转发表后获得对应转发端口ports={port1,port2,…,portm}，假定匹配状态表之后选择状态值最好的端口portk转发，该最优端口对应的目的地址组为addresses(portk)={IPk1,IPk2,…,IPkj}，其余不是最优端口对应的地址要被删除。同时，为了减少地址的数目，从而减少不必要的跳动，需要对最优端口对应的目的地址组addresses(portk)中的地址进行一定的裁剪。

地址裁剪要考虑前跳信息，根据前k跳的信息，以一定的概率删除地址。使用马尔可夫链模型来进行地址裁剪，Xk表示数据包在第k跳时连续未进行地址删除的跳数，则在第k+1跳数据包的状态Xk+1只与第k跳的状态Xk有关，如果在第k跳数据包进行地址删除，则第k+1跳数据包的状态Xk+1=0，如果第k跳数据包未进行地址删除，则第k+1跳数据包的状态Xk+1=Xk+1，因此状态Xk+1只与第k跳的状态Xk有关，故符合Markov过程的特性。又由于在m跳之内必须进行地址裁剪，所以Xk状态是有限的，而且是离散的，因此，问题可以描述为马尔可夫链模型。上述状态转移的概率P(Xk+1=0|Xk)可描述为在第k跳使用前跳信息进行地址删除的概率，与前跳状态Xk有关，因此这个概率是有记忆的。该问题的状态转移图如图3所示，如果在第k跳裁剪地址，则状态返回到0，否则转移到Xk+1=Xk+1，其中到达状态m时，意味着连续m跳未进行地址删除，则强制进行地址删除，也即状态返回到0。根据状态转移图可以获得对应的一步状态转移概率矩阵P，路由器可以根据状态转移概率矩阵进行地址删除决策。

图3 Xk状态转移图

2.2 状态转移概率矩阵

在2.1节中介绍了使用马尔可夫模型进行地址裁剪，其中状态转移概率矩阵将会决定地址裁剪的概率。根据图3将会获得对应的状态转移矩阵：

(1)

由图3的状态转移图可以获得状态转移矩阵满足以下特性：

pk，0>0

(2)

pk,k+1≥0, ∀0km

(3)

即在路由器上未进行地址删除时，状态变化为Xk+1=Xk+1。

pk，0+pk,k+1=1, ∀0k

(4)

其中，pi，j=0对于j≠0或j≠i+1，因为在第k跳只会发生地址删除或地址保留这2种情况。

状态转移矩阵的基本特性已经获得，接下来要设置对应的计算方法来合理地裁剪地址，从而提高路径的收敛性。首先根据不同的状态来设置地址删除的概率，其中，状态Xk=i值越大，则进行地址删除的概率pi,0越高，即满足如下特性：

pi,0≥pi-1,0≥…≥p0,0

(5)

Sigmoid函数y(x)=1/(1+e-x)满足式(2)和式(5)的基本特性，并且该函数的导数在x<0时随着x的增加而增加，意味着增长率逐渐增加。满足多地址裁剪的需求，即地址裁剪概率要快速增加，可以快速减少不必要的地址。因此，对Sigmoid函数进行改进得到对应的马尔可夫模型的地址裁剪概率函数，具体如式(6)所示：

(6)

式(6)描述的地址删除概率在状态值i<0.5×m时删除概率增加较快，其中m为Xk最大值，也即允许的最大连续地址未删除跳数。图4描述了马尔可夫模型地址裁剪函数的基本信息。

在式(6)中只考虑了前跳地址删除的状态作为地址删除的依据，但是随着数据包跳数的增加，希望地址裁剪的概率增加，这样裁剪的概率除了跟状态有关，还与数据包经过的路由器跳数有关。也即是状态转移矩阵P是与跳数有关的，可以表示为P(k)，pi，0(k)是第k步从状态i转移到0的概率，也即是删除地址的概率。其中pi，0(k)是随着k递增的，随着跳数增长而增加地址删除概率。也即满足：

pi,0(k+1)≥pi,0(k)

(7)

图4 地址裁剪概率计算函数

因此，对式(6)中的基于马尔可夫模型的地址裁剪概率函数进行改进，加入跳数的影响因素。改进的函数如式(8)：

(8)

其中，加入了因子β(k)，使得概率能在跳数增加的时候，对应的地址裁剪的概率也增加，为了满足这些特性和计算的方便，因子β(k)可以设置为：

(9)

因此，基于马尔可夫模型的地址裁剪概率函数可以表示为：

(10)

有了状态转移概率矩阵之后，路由器在收到多地址的数据包的时候，在选择完转发端口之后对地址进行裁剪，其中根据状态i和跳数利用式(10)来计算地址删除的概率，以此来对地址裁剪，从而保证在转发的过程中，保持数据包中地址持续较少，从而较少数据包的跳动，提高路径的收敛性。

2.3 状态转移概率矩阵

根据2.2节获得地址裁剪的概率，再根据概率来决策是否进行地址删除，但是删除哪些地址仍然是个问题。马尔可夫模型使用历史状态信息来判断是否进行地址裁剪，而裁剪哪些地址需要对未来状态做个预测。由于选择的最优端口对应的地址组具有相同的转发端口和状态值，唯一可能不同的是地址匹配转发表时的地址匹配长度。一般情况下，地址匹配长度越长，预示着距离目的地越近，这是因为IP地址具有聚合性，距离越远由于聚合的地址越多，相应的匹配长度越短。因此可以使用地址匹配长度作为预测未来路径跳数的依据，在判断需要进行地址裁剪的时候，从地址组中选择匹配长度较短的地址进行裁剪，保留匹配长度较长的地址。

3 实验对比分析

本章通过实验来验证基于马尔可夫模型的地址裁剪方法的路径收敛性。

3.1 实验平台介绍

使用的仿真平台Mininet[22]是SDN场景下主流的仿真平台，控制器和交换机是改进的POX控制器[23]和POFSwitch[24]交换机。为了模拟真实的网络环境，仿真拓扑选取的是Rocketfuel[25]拓扑数据集中的AS5660自治域，该自治域包含22个路由器和26条链路。由于仿真路由器和链路较多，受限于服务器资源，为了防止发生丢包等现象，链路带宽不宜设置过高，因此仿真链路带宽设置为10 Mbps，同时不会影响实验验证结果。实验指标是传输速率和跳数，使用主流的流量测试工具IPerf来测试传输速率。首先分析状态Xk最大值m对收敛性的影响，然后根据结果选取m，并与基准方法做对比，选择的对比方法是随跳数线性增加删除概率的地址删除方法。

3.2 状态最大值设置对收敛性的影响

图5 状态最大值设置对传输性能影响

在基于马尔可夫模型的地址裁剪概率函数中，状态Xk最大值m影响地址删除的概率的计算，因此首先比较不同m值的选取对收敛性的影响。由于仿真拓扑节点之间最短距离小于等于8，故选取m的范围为[1, 8]，实验结果比较了传输速率和数据包的平均跳数。从图5中可以看到，随着m的增加，传输速率增加，这是因为m越大，相对删除地址概率越小，保留的地址越多，而多地址可以使得数据包具有更多的路径选择，提高传输效率。但是相对的平均跳数也会增加，即路径收敛性也会变差，这是因为多地址会使得数据包不能尽快收敛到目的地。从图5中发现，在m=4附近时传输速率增加开始变缓，意味着m的增加对传输速率提升已不大，而相对应的跳数还在保持增加。可以设定m为4，此时传输速率和路径收敛性相对来说是比较均衡的。

3.3 基于马尔可夫模型地址裁剪对路径收敛性的影响

在3.2节中比较了状态最大值m的设置对传输速率和路径收敛性的影响，并选取合适的m值，在本节比较随跳数线性增加删除概率的地址删除方法的性能和基于马氏模型的地址删除方法。

图6 基于马尔可夫模型地址裁剪方法性能

实验中比较了随跳数线性增加删除概率的不同增加率，增加率从10%到30%。增加率表示逐跳增加删除概率的速率，比如增长率为10%，起始第一跳地址删除概率为10%，则第二跳增加到20%，以此类推。从图6中可以看到，随跳数线性增加删除概率模型随着增长率的增加，地址将会以较快的速度删除，所以传输速率会下降，相应的平均跳数会减少，即路径的收敛性会提高。基于马尔可夫模型的地址裁剪方法在传输速率方面的表现与20%增长率的线性概率增加方法在传输速率方面的表现几乎相同，相应的平均跳数减少约16%，也即在获取较好的传输的同时，路径收敛性也得到了提升。而线性删除增长率达到30%时，传输速率会比基于马尔可夫模型表现差，而收敛性并没有多大的提升，因此不是很有必要再比较大于30%的结果。从实验结果说明，与线性地址删除模型相比，基于马尔科夫模型的地址裁剪方法在传输性能和收敛性的表现更均衡，这是因为除了考虑跳数因素，该方法还加入了地址删除历史信息来加快数据包收敛到目的地。

4 结束语

本文针对ICN多宿主网络的路径收敛性差的问题，提出了基于马尔可夫模型的多地址裁剪方法，并设计了状态转移概率矩阵的计算方法，综合考虑了地址删除历史信息和数据包的跳数来进行地址删除，在保证传输性能的同时提高收敛性。实验结果表明，该方法与基于跳数增加地址删除概率的方法相比，能在保证传输速率的同时，减少平均跳数约16%，也即提高了路径的收敛性。后续工作将会考虑通过转发端口的选择使得数据包能尽快地到达目的地，减少跳动。