基于集中控制的命名数据网络流量调度方法

董谦，李俊，马宇翔,2



基于集中控制的命名数据网络流量调度方法

董谦1,2,3，李俊1，马宇翔1,2

（1. 中国科学院计算机网络信息中心，北京 100190；2. 中国科学院大学，北京 100049；3. 佛山科学技术学院电子信息工程学院，广东 佛山 528000）

针对命名数据网络流量全局性优化调度问题，分析已有工作，提出一种基于集中控制的方法。所提方法兼顾网络性能与通信开销，先选择合适节点作为E-NDN节点，再利用控制器根据网内缓存、Interest包聚合情况和热门内容的流量需求计算相应的多路径转发策略并下发至E-NDN节点，以达到全局性优化的目的。实验结果表明，所提方法可显著降低最大链路利用率，提高网络性能，同时优化代价较小，控制器与节点间的通信开销仅略有增加。

命名数据网络；集中控制；流量调度；混合网络；线性规划

1 引言

当今互联网以TCP/IP协议族为中心，但是以IP为细腰[1]的结构已经越来越难以满足互联网的发展趋势，而以内容为中心的需求使内容分发网络（CDN, content delivery network）和对等网络（P2P, peer-to-peer network）等技术[2]得以广泛应用。除此之外，各种全新设计的互联网架构也引起了研究者们的极大兴趣，其中，以信息中心网络（ICN, information centric network）为代表的未来互联网已被视为5G的关键技术之一[3]。ICN以信息为中心，替换原有的细腰即IP，它的代表性实例之一是命名数据网络（NDN, named data network）[4]。

当前，ICN及NDN的研究工作主要集中在体系结构、路由和转发控制、缓存、移动性、安全、应用等方面[5]。其中，路由与转发控制已有若干重要成果，如自适应转发面[6]、命名数据链路状态路由（NLSR, named-data link state route）[7]、双曲路由[8]等，每个路由器根据转发策略和相关信息决定将Interest包转发到哪个端口，自适应转发面维护转发状态。

同时，本文也注意到NDN中还有若干有待进一步研究的问题。在此，主要关注NDN中应如何调度流量，使全网流量更趋近于合理分布的状态，特别是在有多个消费者和多个生产者的情况下如何进行网络性能优化，如尽可能地最小化最大链路利用率、提高其吞吐量。尽管NDN支持多路径转发和负载均衡[5]，但Interest包的转发通常只由消费者或中间节点控制，难以实现全局性优化调度，制约了网络性能的提升。而若要对NDN流量做全局性优化调度则必须获取全网信息，因此集中控制的引入十分必要，特别是NDN如何与集中控制相结合，如何合理设计集中控制的整体架构，取得性能和开销的平衡。NDN结合集中控制成为混合网络即网络中存在不同功能的节点时，应考虑如何建立流量模型，选择合适的调度节点并通过这些节点调度流量以及如何快速计算流量分配。软件定义网络（SDN, software defined network）已取得极大成功，其核心思想是集中控制、控制面与数据面分离[9]，已有一些工作探讨如何将NDN与SDN相结合[10-16]。然而，NDN的名字空间相对IPv4来说要大得多，NDN的转发过程也完全不同于IPv4，如要借助集中控制对网络流量进行控制，必须充分考虑NDN本身的特点，并加以针对性设计。

为此，本文分析了已有的NDN多路径转发策略以及NDN与SDN结合的相关工作，提出了一种基于集中控制的命名数据网络流量调度方法，引入集中控制机制优化NDN中的流量转发，结合NDN的特点设计整体架构、建立流量模型。本文的主要贡献如下。

1) 分析已有工作，针对NDN中流量的全局性优化调度问题，提出一种基于集中控制的方法，设计整体架构和各类设备的功能。

2) 对NDN流量调度问题建模和分析，提出一种可行的算法，只在部分节点针对热门内容请求部署合适的转发策略，即可有效对流量进行全局性优化调度，也减轻了控制器与节点间的通信开销。

3) 考虑NDN中Interest包的作用和特点及网内缓存和Interest包聚合等因素，针对已建立的模型提出简便的处理方法。

2 NDN转发基本流程和相关工作

2.1 NDN转发基本流程

NDN中有2种不同类型的包：Interest和Data。这2种包都携带了内容的名字，用以确认和区分不同的内容。消费者向网络发送Interest包来请求相应的内容，一旦Interest包到达拥有该内容的节点，节点会沿反向路径将包含名字和内容的Data包返回给消费者，同时还携带有内容生产者的签名[5]。

每个NDN路由器都会维护3种数据结构：待定Interest表（PIT, pending Interest table）、转发信息库（FIB, forwarding information base）和内容存储（CS, content store）。同时，路由器还要维护转发策略模块，以决定Interest包如何转发。PIT存储了路由器已转发但还未返回相应Data包的所有Interest列表，PIT中的每个条目记录相应的数据名字和出入端口；而CS存储了本地缓存的所有内容，如果收到相应的Interest请求，则沿原端口返回相应内容，如果CS中未找到，则路由器检查PIT，如有相关记录则添加其端口，如无则继续查找FIB，并按相应策略转发，FIB中一个名字可对应多个接口；如果收到多个完全相同的Interest包，则只转发第一个Interest包，Interest包的聚合机制是NDN中防止环路及广播风暴特性的基础[5]。

反过来，对于Data包，情况就简单多了。当Data包抵达时，NDN路由器会查找PIT，按照其条目中的相应端口进行转发，并将内容存入CS，移除PIT相应条目，此时，相应Interest请求已经得到满足，Data包则沿着Interest的反向路径转发[5]。

显然，在NDN转发模型中，Interest包由消费者驱动，由于Data包的转发严格按照Interest包的反向路径，故NDN可通过控制Interest包的转发路径来管理Data包的转发路径，从流量调度的角度来看，Interest包不直接传递内容，可将其看作一种信令，它为流量调度和路径控制提供了简便的方式。

2.2 相关工作

NDN在路由和转发方面与传统网络非常不同，为此，研究者们进行了相关研究。Yi等[6]提出自适应转发机制，通过观察Interest和Data包的双向流量来检测网络问题、多路径和环路；Hoque等[7]提出了NLSR，使用Interest和Data包来传播路由更新，可对每个名字前缀生成转发选项的排序，以服务于自适应转发策略；Lehman等[8]尝试将双曲路由应用于NDN中，以解决路由可扩展性问题，虽然取得了和NLSR较为接近的效果，却极大降低了路由协议的开销；Posch等[17]提出了随机自适应转发来模仿水管系统，能够在无路由信息更新的情况下识别路径，避开链路故障和网络瓶颈。以上工作使NDN具备良好的多路径转发特性。

基于此，一系列工作研究了NDN中的多路径转发策略，主要是在多路径转发的情况下，如何使流量合理分配到不同的路径上，从而获取更好的网络性能。Carofiglio等[18]考虑最大限度提高用户吞吐量和最小化整体目标网络成本，从双重全局优化问题出发，提出分布式拥塞控制策略动态调整包的转发；Detti等[19]建模分析了ICN中的多路径转发策略，并介绍了与之相关的5种方案；Xin等[20]基于本地内容的流行度统计，对包进行调度以提高缓存效率和避免拥塞，提出缓存替换算法；Udugama等[21]针对服务质量（QoS, quality of service）需求，提出一种基于权重的轮转分配机制，只考虑不相交路径，发现路径并分配流量；Kerrouche等[22]同样针对服务质量需求，动态获取QoS参数并据此调整转发策略。表1总结了上述工作。

总之，上述工作通过不同方式获得多条路径上的相关参数，并依此调度流量请求；上述工作还表明，多路径转发对于网络性能的提升有重要作用，特别是将流量请求按照合适的方式分配到不同路径，能提高网络吞吐量、减少网络拥塞。

然而，上述工作都是在消费者或中间节点处对具体内容请求的多路径转发进行控制，均未引入集中控制，因此难以针对多个消费者和多个生产者同时存在需要对流量进行全局性优化调度的情况。虽然缓存是NDN的最重要特征之一，但部分工作在建模时并未考虑此因素。

表1 几种多路径转发策略比较

与此同时，一系列工作研究了集中控制机制和NDN的结合。

1) 从功能的角度，Torres等[10]首先提出基于控制器的NDN路由方案，控制器可获取拓扑及计算路由，存储命名数据的位置；Chanda等[11]设计了软件定义信息中心网络的框架，并简单讨论了在此框架上部署流量工程任务；Bacher等[12]使用控制器为未知内容Interest包计算路径，并在链路拥塞的情况下查找替代路径，根据用户需求提前部署相应热门内容以减轻核心网络负担；Gao等[13]针对软件定义ICN提出一种用于域内通信的可扩展区域分层架构以解决控制平面可扩展性问题，支持对网络资源和内容资源的感知，保证有效的兴趣匹配和资源适配。

2) 从部署的角度，Salsano等[14]在实验床进行测试，验证了基于SDN的ICN的可行性；Van等[15]提出的NDNFlow，实际上是以NDN客户端插件的形式将NDN功能部署在原有的SDN设备上；Mahmood等[16]为缓解控制器负担重的问题，使用有状态S/N-DN设备，在NDN中部署集中控制。

上述工作从不同角度讨论了集中控制与NDN的结合，此时控制器可采集和分发各类信息、下发动作等；若要实际部署，相关开销是必须考虑的问题。

然而，上述工作并未讨论如何基于集中控制方法在多路径转发的情况下对流量进行全局性优化调度；NDN相比IPv4大得多的命名空间也会显著增加控制器的负担，如果在所有节点部署SDN和NDN功能、控制所有流量，则网络的可扩展性难以提高。

3 整体架构

在通常的NDN中，Interest包的转发是由消费者或中间节点根据名字、转发表和转发策略决定的，过程上和传统网络中基于链路状态的路由协议相似。如相关工作所述，考虑多个消费者和多个生产者同时存在的情况，即考虑对流量进行全局性优化调度的需求，则有必要引入集中控制；NDN不同于IPv4，其与集中控制结合需考虑NDN本身的特点，还需考虑相关开销。因此，本文从多路径转发和集中控制的角度出发，结合NDN流量调度通过Interest包来实现的做法，在部分节点针对热门内容请求部署合适的转发策略，可有效对流量进行全局性优化调度，这也减轻了控制器与节点间的通信开销。本文提出一种基于集中控制的命名数据网络流量调度方法，控制器仅控制部分节点对部分内容请求的转发，其他内容仍然采用默认的转发机制，面向多个消费者和多个生产者，对网络性能如最大链路利用率进行全局性优化。

基于对中国科技网等实际网络架构、拓扑和业务部署情况的分析和抽象，对于汇聚各子网和终端用户，本文将其虚拟为若干个消费者，每个虚拟消费者对内容的请求可认为是相对应的所有终端用户的内容请求经过Interest包聚合过程后发送给其汇聚节点的内容请求汇总，因此每个虚拟消费者可用单条链路接入相应的汇聚节点；对于服务器等内容提供设备亦然，可虚拟为若干个生产者，如所有域外的服务器可通过相应链路接入域间互连节点，域内的服务器也可通过相应链路接入域内节点。上述方式处理实际拓扑以后，流量调度问题即可方便地表示为有向图中的多商品流（MCF, multi commodity flow）问题[23]。

根据文献[24]统计的网站访问热度以及内容请求服从类Zipf分布可知，多数流量产生自用户对热门内容的请求，如视频网站、门户网站、搜索引擎等，优化这部分前缀转发的效果较为明显，其他内容仍然依照默认的转发流程，这样不仅可降低采集相关信息的开销，也可大幅减少控制器下发规则或转发策略的数量。

整体架构示意如图1所示，主要由控制器、2类中间设备（普通NDN节点和增强NDN节点即E-NDN节点）和2类端设备（虚拟消费者和生产者）构成。

图1 整体架构示意

各类设备的主要功能介绍如下。

1) 控制器需与网内节点建立连接，其作用是获取全网拓扑，以一定时间间隔通过NETCONF[25]等南向接口协议周期性采集网内节点的信息，如FIB、流量情况、缓存命中率、待定Interest包数量等，并及时处理各E-NDN节点发送的流量调度需求，进行优化计算并将结果转换为转发规则或转发策略下发给相应E-NDN节点。

2) 普通NDN节点支持网内缓存，遵循NDN的转发流程，依照转发表和转发策略对Interest包进行转发。一般情况下，普通NDN节点的转发表和转发策略都比较固定，这也使网络拓扑未产生变化、链路未发生拥塞或故障时，Interest包的转发路径及与之对应的Data包转发路径是相对稳定的。控制器对普通NDN节点的操作可认为是只读的，而普通NDN节点需要根据控制器的采集需求，及时采集并发送相应信息。

3) E-NDN节点除了有普通NDN节点的功能以外，还应根据待定Interest包的数量，将较为热门内容的流量调度需求发送给控制器，控制器处理完毕后，接收控制器下发的转发规则或转发策略；有多个下一跳时，能将待优化转发的那部分Interest包按照控制器决定的方式分别转发到多条路径；转发后的处理流程和普通NDN节点相同，以保证返回的Data包沿着相应Interest包的反向路径转发。

4) 消费者主要产生对内容的请求即Interest包；生产者满足这些Interest包，返回相应内容的Data包。

4 模型建立与问题分析

4.1 模型建立

通常网络流量优化调度的目标是降低最大链路利用率。以此优化目标为例，本文首先建立一般化的流量模型，该模型也可推广用于同时存在其他优化目标和约束条件的情况，如全局最小费用等。

首先，在流量模型中需定义有向图=(,)，为所有节点的集合，为所有边的集合，每条边即2个节点间直连链路的权重集合为，容量集合为，对于节点到的直连链路可记为w和c，若节点到的直连链路为，亦可记为w和c。节点的直连节点即下一跳集合为NH，显然，节点的上一跳集合也为NH，从节点到节点的直连链路上的流量记为y，衡量单位时间内从节点传输到节点的数据量，显然有

式(1)是链路容量条件。针对多个消费者和多个生产者同时存在的情况即多商品流问题，将源节点和目的节点记为、，设所有流的源节点集合为，每个对应的所有目的节点集合为T，显然，、T都是的子集；节点、间的流量需求记为d，所有流量需求的集合以表示。为方便表达，记任意节点、间的流量需求为d，对应的目的节点集合表示为T，若不属于，则T为空集，有

式(2)和式(3)表明，除了节点、间以外，其余节点间没有流量需求。因此，不考虑环路时（形成环路的流量是无效流量，无助于满足流量需求）满足所有流量需求的网络总流量为

为了满足流量需求，建立完整的流量模型，还需要写出相应的流量平衡约束条件，然而处理NDN流量优化调度问题时，由于NDN网内缓存和Interest包聚合的特点，流量平衡约束条件较为复杂。考虑到d是从到的流量需求，流量平衡约束条件实际上体现在起点为终点为的路径上，且根据第3节，网络中只有部分节点可调度，因此，可预先计算好、间的可选路径，然后用合适方式表达以便求解如何将流量需求合理分担在各条可选路径上，还可预先排除存在环路的路径，这是因为存在环路的路径必然不是最优解。

为简化讨论，本文后续不考虑普通NDN节点支持等价多路径负载均衡时的情况，如果普通NDN节点作为均衡点有多条等价路径，计算时只取其中一条，也排除路径重复使用某条边的情况。设从到的路径分担的流量需求为x，边编号为，中对应的元素值为[]，显然[] = 0或1，且有

式(5)是由x的定义决定的，式(6)表明、间的流量需求得到满足，式(7)是满足所有流量需求时链路上的流量。

再定义链路利用率为λ，最大链路利用率为，显然0≤≤1，有

此时，式(1)变为

通常，对于多商品流问题的流量模型而言，主要优化目标是最大化和最小化即

对于式(11)，约束条件是式(1)~式(7)；若已知，则亦确定，此时，对于式(12)，约束条件是式(5)~式(7)和式(10)，且0 ≤≤ 1。

4.2 问题分析

模型建立过程说明处理此优化问题前需得出可用路径集合，一旦E-NDN节点确定，则相应的路径集合也可确定，因此需选择合适的节点作为E-NDN节点。NDN具有Data包与Interest包一一对应且Data包严格按照Interest包反向路径转发的特点，因此本文只讨论对Interest包流量的优化调度，对Interest包转发优化等效于对Data包转发优化。此时，节点可视为虚拟消费者单条链路接入的汇聚节点，节点为虚拟生产者接入的节点，假设每个虚拟消费者即相应的节点都需要一个E-NDN节点，用于调度此虚拟消费者的内容请求；NDN最重要的特点是网内缓存和Interest聚合，因此，需采取合适的做法将这2个因素反映到流量模型中；网络流量分为不可调度流量和可调度流量，需以前者为背景流量，考虑后者的调度问题。另外，本文还假设Data包中的内容实际上是请求内容的数据块即Chunk，每个Chunk大小相同。

4.2.1 E-NDN节点和可选路径选择

本文首先选取合适的候选路径数量，并用最短路径算法[27]对每个节点均求出其到T中所有节点的前条最短路径，输入为、、T、，输出为路径集合P-init，显然，P是其子集；然后用最短路径算法求得每一组、的最短路径，并对每个节点均求出其到T中所有节点最短路径中重合的部分，将这些重合的节点标记下来，显然，重合部分的节点至少包含一个节点即节点本身，调度节点内容请求的E-NDN节点将在这些节点中选择，原因在于节点到T中所有节点的流量默认情况下均要经过这些节点，如果E-NDN节点不在这些节点上选择则难以有效调度流量，在E-NDN节点之外，Interest包转发仍然按照最短路径方式。

考虑节点到T中所有节点的P-init，结合候选节点的NH，可针对NH中的每个节点在P-init中得到一条经过此节点的、间的最短路径，还应排除有环路的路径；对于所有候选节点，都按上述原则筛选P-init，得到可选路径P，然后由P计算此时节点到T中所有节点的总流量最大值Traffic-max()，对所有候选节点取计算结果最大者作为对应的E-NDN节点，若有多个则在其中取包括在内的离跳数最少者，相应的P即为后续计算使用的P，Traffic-max()最大值即为Traffic-max。

上述过程的算法如下所示。

算法1 E-NDN节点和P选择

1) 输入、、T、、

2) for each∈do

3) for each∈Tdo

4)最短路径计算得P-init；

5) 最短路径计算；

6) end for

7) 求到T中所有最短路径的重合节点；

8)Traffic-max← 0；

9) for each∈重合节点 do

10) 取NH并根据NH筛选P-init得P；

11) 根据P求Traffic-max()；

12) ifTraffic-max()>Traffic-maxthen

13)对应的E-NDN节点←；

14)P←P；

15) Traffic-max←Traffic-max()；

16) else if （Traffic-max()=Traffic-max）∧（比对应的E-NDN节点离跳数更少）then

17)对应的E-NDN节点←；

18)P←P；

19) else

20) end if

21) end for

22) end for

控制器采集网络相关信息后即可执行此算法，计算完成后如网络相关信息不发生变化则不需要重新计算，如发生变化则应重新执行。由于缓存情况相对其他信息来说变化更加频繁，为使计算结果稳定，上述过程一般不考虑缓存因素，此算法中也未体现；如需考虑缓存因素，则每次计算Traffic-max()前按照4.2.2节中的做法处理即可。

4.2.2 网内缓存与Interest聚合

NDN不同于传统网络的特点是网内缓存和Interest聚合。网内缓存有多种部署方式，其中一个重要指标是缓存命中率，通常缓存命中率分别在各个节点上统计，设节点上的缓存命中率为h，对于只是流经节点的Interest包，流出的流量是流入流量的1−h倍[28]；对于在此产生的Interest包，考虑到本文简化了场景，实际上节点是虚拟消费者单条链路接入的汇聚节点，因此也应考虑缓存的影响，由源节点产生的流量也应乘以1−h。

流量平衡约束条件体现在路径数组中，可根据缓存情况修正中相应元素的值以更好地反映实际情况，为了不改变P，对每一个可设置一个缓存系数数组q，其也是由个元素组成的一维数组，与一样对应中的所有边，其计算过程如下：首先，使q=，由于的非零元素值为1，对于q，此时只需将以为起点的路径上的边对应的数组元素值设为1−h，将以第二个节点为起点的路径上的边对应的数组元素值设为(1−h)(1−h)，依次类推，直到将以倒数第二个节点为起点的路径上的边对应的数组元素值设为(1−h)(1−h)…(1−h)为止。优化计算可使用q代替，如果缓存命中率发生变化则更新q的值。值得一提的是，对于等价多路径负载均衡的情况，计算前将其数组还原为相应的若干个等价且非零元素值为1的路径数组，然后按上述方法分别计算各自的缓存系数数组，再分别乘以相应路径的流量分担比例后相加，其结果即为这个数组对应的缓存系数数组。

上述过程的算法如下所示。

算法2 缓存系数数组q计算（以为例）

1) 输入、h

2)← 1；

3)q←；

4)←的起点；

5) for= 1 to中非零元素的数量do

6) 查找中起点为的路径上的边，其编号为，对应q第项，相应元素值表示为q[]；

7)q[] ←(1−h)；

8)←q[]；

9)← 这条边的终点；

10) end for

控制器采集各节点缓存命中率信息后，即可对路径数组执行此算法，如果各节点的缓存命中率发生变化，则应重新执行。

同样地，Interest包聚合也会影响流量平衡。当不同消费者的请求为独立事件时，通常难以对Interest包的聚合情况进行定量分析，只能确定聚合后的流量不大于聚合前的流量，可将其全部视为不聚合流量；当不同消费者同时请求同样内容且不调度时，Interest包的聚合情况是已知的，可对中所有节点的T求并集，以中所有节点为根，分别求其到对应的所有的最短路径树，也可由个元素组成的一维数组表示，由于聚合原因，中每个非零元素的值也为1，所有的集合为。如有必要考虑缓存因素，也可设置缓存系数数组q并按类似方法处理，对于树上除了根以外的节点，当计算以为起点的路径树上的边对应的数组元素值时，若是根对应的则设为1−h，若不是则先比较以为终点的所有路径树上的边对应的数组元素值之和与1的大小，再取较小者乘以1−h。

4.2.3 不可调度流量与可调度流量

不可调度流量在所有NDN节点均采用默认的转发路径，而可调度流量必须在E-NDN节点才能通过配置相应转发策略来改变其默认转发路径；Interest聚合要求不同消费者同时请求同样内容，这种情况在现实中很少出现且难以定量分析，因此除了视频会议等Interest聚合的典型应用以外，其他请求均可视为不聚合流量；本文只考虑调度不聚合流量，可聚合流量均不可调度。据此区分不聚合不可调度流量、可聚合不可调度流量、不聚合可调度流量如下：除Interest聚合应用外，不属于热门内容的内容请求可视为不聚合不可调度流量；Interest聚合应用的内容请求可视为可聚合不可调度流量；除Interest聚合应用外，热门内容可视为不聚合可调度流量。针对这3种情况，、间的流量需求d可分为不聚合不可调度流量需求d-I、可聚合不可调度流量需求d-II与不聚合可调度流量需求d-III。再将所有、间的最短路径表示为，所有的集合为，路径分担来自相对应消费者到生产者的不聚合不可调度流量需求为x，相应的缓存系数数组为q；路径树分担的来自相对应消费者到生产者的可聚合不可调度流量需求为x；路径分担的来自相对应消费者到生产者的不聚合可调度流量需求仍表示为x；显然d-I即为相对应的x，d-II即为相对应的x，式(6)中的d改写为d-III，而且有

计算时若考虑缓存因素，如前所述边的编号记为，则缓存系数数组中边对应的元素值为q[]、q[]、q[]，则式(7)中y改写为

最终，设定优化目标并计算完成后输出的结果为x。可给出主要优化目标为min时求解的算法如下所示。

算法3 主要优化目标为min时求解x

1) 输入d-I、d-II、d-III、q、q、q、、、T、、P、、

5) for= 1 to试探求解次数do

7) ifx有解then

11) else

14) end if

15) end for

其中，P使用算法1、使用最短路径算法、使用最短路径树算法得出，q、q、q按照4.2.2节中的做法得出，d-I、d-II、d-III由控制器处理完E-NDN节点发送的调度需求及控制器采集的相关信息后给出，最后x变为转发策略下发相关节点。

4.2.4 优化代价评估

本文还通过相应路径长度拉伸的程度（path stretch）评估优化代价，通常定义为路径的实际长度与最短路径长度的比值[29]。那么可设路径和对应的路径长度为z和z，、间的最短路径长度为z，由于可聚合流量不可调度，本文只考虑不聚合流量，包括不聚合可调度流量和不聚合不可调度流量，全网的不聚合流量路径长度拉伸的程度用表示，若不考虑缓存因素，则有理论值为

若要考虑缓存因素，则只能实际统计调度与未调度情况下的平均路径长度，其比值即为实测值。

4.2.5 控制器与节点间的通信开销

与SDN类似，控制器与节点间的通信开销主要有以下2类。

1) 周期性信息采集。此时，通信开销取决于信息采集周期、信息采集量、节点数量，若周期、采集量、节点数都固定，则此类开销也固定。

2) 流量调度需求发送和转发策略下发，用于计算的信息采集（如需要）。此时，通信开销取决于流量调度需求的个数、每个流量调度需求对应的转发策略、每个流量调度需求对应的信息采集量（若需要）。流量调度需求表现为相应前缀的流量调度需求，此类开销可认为正比于流量调度需求的个数，也即正比于各E-NDN节点上需调度的前缀数量。假设内容前缀总数为个，由于内容请求服从类Zipf[24]分布，前缀已在各E-NDN节点按照相应内容的热门程度即待定Interest数量从大到小排序，表示为Prefix，其中，序号= 1, 2, 3, …,，分布系数为，则每个Prefix被请求的概率为

若和确定，则CP()也确定。当需调度内容的流量需求占全部流量需求的比例为时，显然有0≤≤1；记需调度Prefix的序号集合为，则有

此类开销正比于中元素的数量，根据式(18)，当越小，CP()越大，因此如要减小此类开销，各E-NDN节点应优先请求调度流量需求较大的热门内容。

5 仿真实验

本文使用基于NS-3[30]的开源工具ndnSIM[31]进行仿真实验，版本是2.3。ndnSIM能部署消费者及生产者应用，配置相关前缀和路由，支持多种常见的缓存替换策略；自2.0版本起，ndnSIM的转发模块更新为已用于实际硬件开发的NFD（NDN forwarding daemon），这不仅使其能更好地支持最短路径、多播、NCC、客户端控制等转发策略，还使仿真结果更接近真实情况。

实验拓扑取自GÉANT，共23个汇聚层节点，它们之间的直连链路共37条，考虑双向则共有74条边；设定消费者3个，生产者2个，均为GÉANT中的节点，节点间的流量需求信息取自此拓扑的公开数据集[32]，共取4个时间段的流量情况分别作为4个场景进行仿真。根据第4节的讨论，仿真首先需设定一些前提：每个节点上部署缓存及相应的缓存替换策略；用户的一般内容请求即不聚合流量服从类Zipf分布，而聚合流量需采用恒定速率，这是为了满足Interest包聚合的条件；链路的权重均为1，带宽为100 Mbit/s，时延为10 ms；Data包的大小为1 024 B；每次实验进行150 s，前50 s为预热时间，采用后100 s的数据。另外，参考相关文献[28, 33]，基本参数配置如表2所示。

表2 实验参数

表3 各场景内容请求速率

4种场景中，消费者分别向生产者发起的内容请求速率如表3所示。

本文分别评估缓存的影响、与其他方法对比、不同场景下的效果和优化代价、有流量聚合时不同场景下的效果、控制器与节点间的通信开销。

1) 缓存的影响

当全部流量为不聚合流量时，针对场景1，改变Zipf分布的值，分别取0.8、0.9、1.0、1.1，值越大代表请求的内容越集中，特别是在LFU缓存替换策略下，缓存命中率相对其他策略在其他参数相同的情况下更高；此外，当值为1.0和1.1时，还在计算时分别考虑缓存和不考虑缓存；取不聚合流量中可调度流量比例为0.2、0.3、0.4、0.5、0.6、0.7、0.8，不可调度流量仍按照最短路径转发，按上述条件计算结果并仿真，统计其最大链路利用率，分别与相同参数下全部流量为不可调度流量即不聚合流量中可调度流量比例为0时的默认情况下最大链路利用率取比值，最后用不考虑缓存计算得出的理论值作为参照，结果如图2所示。

由图2可知，采用本文方法后最大链路利用率相对默认情况下的比值有不同程度的降低，可分为2个阶段：阶段1，在不聚合流量中可调度流量比例达到0.5以前，其比例越高则最大链路利用率相对默认情况下的比值降低幅度越大；阶段2，在不聚合流量中可调度流量比例达到0.5以后，最大链路利用率相对默认情况下的比值接近最优，即便再提高不聚合流量中的可调度流量比例，最大链路利用率相对默认情况下的比值降低幅度也不会有太大变化。值得注意的是，当值为1.0和1.1时，缓存起的作用相对明显，计算时不考虑缓存因素相对考虑缓存因素的仿真实验结果较差且不稳定。

图2 场景1不同Zipf分布α值下最大链路利用率比值

2) 与其他方法对比

作为对比，本文考察Detti等[19]建模分析的2种多路径转发策略UG和CF，全部流量为不聚合流量时，值取0.9，针对场景1，取不聚合流量中可调度流量比例为0.2、0.3、0.4、0.5、0.6、0.7、0.8，计算相应的多路径流量分配结果并仿真，统计其最大链路利用率，分别与相同参数下全部流量为不可调度流量即不聚合流量中可调度流量比例为0时的默认情况下最大链路利用率取比值，对比本文方法的结果如图3所示。

图3 α=0.9时，场景1下采用不同方法得到的最大链路利用率比值

由图3可知，本文方法相比UG、CF来说，流量调度效果较好，这主要是因为UG、CF虽然也是典型的多路径转发策略，却无全局优化，故难以在多个消费者和多个生产者的场景下取得最理想的结果。

3) 不同场景下的效果和优化代价评估

当全部流量为不聚合流量时，值取0.9，针对场景1~场景4，取不聚合流量中可调度流量比例为0.2、0.3、0.4、0.5、0.6、0.7、0.8，按上述条件计算结果并仿真，统计其最大链路利用率，分别与相同参数下全部流量为不可调度流量即不聚合流量中可调度流量比例为0时的默认情况下最大链路利用率取比值，结果如图4所示。

图4 α=0.9时，不同场景下最大链路利用率比值

由图4可知，在这4种场景下，本文方法都能获得较好的调度效果，与之对应的路径长度拉伸的程度分别根据仿真结果统计实测值及式(17)求理论值，如图5所示。

图5 α=0.9时，不同场景下路径长度拉伸的程度

由图5可知，通常情况下，可调度流量比例越大，其代价即路径长度拉伸的程度越高；尽管相同情况下的实测值比理论值大0.01~0.06，实测值和理论值随着可调度流量比例变化的趋势基本一致。因此如需优化代价尽量小，只需调度不聚合流量中50%~60%的流量，即可在代价相对较小的前提下取得较为理想的结果。

4) 有流量聚合时不同场景下的效果

当部分流量为可聚合不可调度流量时，取值为0.9，针对场景1~场景4，令各消费者到各生产者的可聚合不可调度流量请求速率为表3中各场景下内容请求速率总和的5%，分别为95、92、69、56个Interest包请求/秒，则可聚合不可调度流量请求总和占所有流量请求总和的30%，各消费者到各生产者的各类流量请求速率之和仍依照表3，取不聚合流量中可调度流量比例为0.2、0.3、0.4、0.5、0.6、0.7、0.8，按上述条件计算结果并仿真，统计其最大链路利用率，分别与相同参数下全部不聚合流量为不可调度流量即不聚合流量中可调度流量比例为0时的默认情况下最大链路利用率取比值，结果如图6所示。

图6 α=0.9且有聚合流量时，不同场景下最大链路利用率比值

由图6可知，此时的结果与不可聚合不可调度流量时的结果相似，不过受可聚合不可调度流量影响，不聚合流量中可调度流量比例需达到0.6左右时，最大链路利用率相对默认情况下的比值才接近最优。

5) 控制器与节点间的通信开销

先取可调度流量比例为0.2、0.3、0.4、0.5、0.6、0.7、0.8，改变Zipf分布的值，分别取0.8、0.9、1.0、1.1，根据4.2.5节的相关分析和式(18)、式(19)，当内容前缀总数=1 000个且优先调度热门内容的流量需求时，可计算出控制器与节点间除周期性信息采集外的通信开销最小值，以需调度的前缀数量来衡量，结果如图7所示；然后改变值，取可调度流量比例为0.5、0.6，改变值，分别取0.8、0.9、1.0、1.1，结果如图8所示。

图7 A=1 000个时控制器与节点间的通信开销最小值

图8 不同A值时控制器与节点间的通信开销最小值

由图7可知，当可调度流量比例相同时，越大，流量需求越集中于少数内容前缀，通信开销最小值就越小；若可调度流量比例增加，通信开销最小值以更快的速度增加。由图8可知，内容前缀总数增加也会使通信开销最小值随之增加；若只调度50%~60%的流量，通信开销最小值相对内容前缀总数的增长速度会缓慢得多，只是略有增加而已。

总之，根据实验仿真结果可知，当不聚合流量中可调度流量比例为0.5~0.6时，可在只付出较小的优化代价和略微增加控制器与节点间通信开销的前提下，将最大链路利用率相对默认情况下的比值降低40%以上。

以上仿真实验表明，本文方法相对默认情况和UG、CF等典型多路径转发策略能有效降低最大链路利用率，从而起到了均衡负载、提高网络吞吐量的作用；另一方面，也验证了本文所做的假设和设计的合理性，即只需在部分指定节点针对热门内容的流量需求部署合适的转发策略即可获得较好的效果，且优化代价较小，通信开销仅略有增加。

6 结束语

本文针对命名数据网络中流量的优化调度需求，提出将NDN与SDN相结合以解决此问题，设计整体架构和各类设备的功能。通过建模分析，考虑NDN中Interest包的作用和特点及网内缓存和Interest包聚合因素，提出一种可行的算法，在部分节点针对热门内容的流量需求部署合适的转发策略，进行全局性优化调度，此外还评估了优化代价，分析了控制器与节点间的通信开销。实验结果表明，在指定节点针对热门内容的流量需求依照本文方法进行调度，能在不产生大的优化代价及通信开销的前提下显著提高网络性能。

[1] JACOBSON V, SMETTERS D K, THORNTON J D, et al. Networking named content[C]//The 5th International Conference on Emerging Networking Experiments and Technologies. 2009: 1-12.

[2] PASSARELLA A. A survey on content-centric technologies for the current Internet: CDN and P2P solutions[J]. Computer Communications, 2012, 35(1): 1-32.

[3] RAVINDRAN R, CHAKRABORTI A, AMIN S O, et al. 5G-ICN: delivering ICN services over 5G using network slicing[J]. IEEE Communications Magazine, 2017, 55(5): 101-107.

[4] AHLGREN B, DANNEWITZ C, IMBRENDA C, et al. A survey of information-centric networking[J]. IEEE Communications Magazine, 2012, 50(7): 26-36.

[5] ZHANG L, AFANASYEV A, BURKE J, et al. Named data networking[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 66-73.

[6] YI C, AFANASYEV A, WANG L, et al. Adaptive forwarding in named data networking[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(3): 62-67.

[7] HOQUE A K M, AMIN S O, ALYYAN A, et al. NLSR: named-data link state routing protocol[C]//The 3rd ACM SIGCOMM Workshop on Information-Centric Networking. 2013: 15-20.

[8] LEHMAN V, GAWANDE A, ZHANG B, et al. An experimental investigation of hyperbolic routing with a smart forwarding plane in NDN[C]//The 24th IEEE/ACM International Symposium on Quality of Service. 2016: 1-10.

[9] KREUTZ D, RAMOS F M V, VERISSIMO P E, et al. Software-defined networking: a comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14-76.

[10] TORRES J, FERRAZ L, DUARTE O. Controller-based routing scheme for named data network[J]. Electrical Engineering Program, COPPE/UFRJ Tech Rep, 2012: 1-6.

[11] CHANDA A, WESTPHAL C, RAYCHAUDHURI D. Content based traffic engineering in software defined information centric networks[C]//IEEE Conference on Computer Communications Workshops. 2013: 357-362.

[12] BACHER F, RAINER B, HELLWAGNER H. Towards controller-aided multimedia dissemination in named data networking[C]// IEEE International Conference on Multimedia & Expo Workshops. 2015: 1-6.

[13] GAO S, ZENG Y, LUO H, et al. Scalable control plane for intra-domain communication in software defined information centric networking[J]. Future Generation Computer Systems, 2016, 56: 110-120.

[14] SALSANO S, BLEFARI-MELAZZI N, DETTI A, et al. Information centric networking over SDN and OpenFlow: architectural aspects and experiments on the OFELIA testbed[J]. Computer Networks, 2013, 57(16): 3207-3221.

[15] VAN A N L M, KUIPERS F A. NDNFlow: software-defined named data networking[C]//IEEE Conference on Network Softwarization. 2015: 1-5.

[16] MAHMOOD A, CASETTI C, CHIASSERINI C F, et al. Efficient caching through stateful SDN in named data networking[J]. Transactions on Emerging Telecommunications Technologies, 2018, 29(1): 1-21.

[17] POSCH D, RAINER B, HELLWAGNER H. Saf: stochastic adaptive forwarding in named data networking[J]. IEEE/ACM Transactions on Networking, 2017, 25(2): 1089-1102.

[18] CAROFIGLIO G, GALLO M, MUSCARIELLO L. Optimal multipath congestion control and request forwarding in information-centric networks: protocol design and experimentation[J]. Computer Networks, 2016, 110: 104-117.

[19] DETTI A, PISA C, MELAZZI N B. Modeling multipath forwarding strategies in information centric networks[C]//IEEE Conference on Computer Communications Workshops. 2015: 324-329.

[20] XIN Y, LI Y, WANG W, et al. Content aware multi-path forwarding strategy in information centric networking[C]//IEEE Symposium on Computers and Communications. 2016: 816-823.

[21] UDUGAMA A, ZHANG X, KULADINITHI K, et al. An on-demand multi-path interest forwarding strategy for content retrievals in CCN[C]//IEEE/IFIP Network Operations and Management Symposium. 2014: 1-6.

[22] KERROUCHE A, SENOUCI M R, MELLOUK A. QoS-FS: a new forwarding strategy with QoS for routing in named data networking[C]//IEEE International Conference on Communications. 2016: 1-7.

[23] GARG N, KOENEMANN J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems[J]. SIAM Journal on Computing, 2007, 37(2): 630-652.

[24] BRESLAU L, CAO P, FAN L, et al. Web caching and Zipf-like distributions: evidence and implications[C]//The Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. 1999: 126-134.

[25] ENNS R, BJORKLUND M, SCHOENWAELDER J. Network configuration protocol(NETCONF)[J]. IETF RFC 6241, 2011: 1-113.

[26] CHARALAMBOUS C, CONN A R. An efficient method to solve the minimax problem directly[J]. SIAM Journal on Numerical Analysis, 1978, 15(1): 162-187.

[27] YEN J Y. Finding theshortest loopless paths in a network[J]. Management Science, 1971, 17(11): 712-716.

[28] 智江, 李俊, 吴海博, 等. 基于边缘优先的ICN缓存协作策略[J]. 通信学报, 2017, 38(3): 53-64.

ZHI J, LI J, WU H B, et al. Edge-first-based cooperative caching strategy in information centric networking[J]. Journal on Communications, 2017, 38(3): 53-64.

[29] 唐明董, 张国清, 杨景, 等. 互联网可扩展路由[J]. 软件学报, 2010, 21(10): 2524-2541.

TANG M D, ZHANG G Q, YANG J, et al. Scalable routing for the Internet[J]. Journal of Software, 2010, 21(10): 2524-2541.

[30] HENDERSON T R, LACAGE M, RILEY G F, et al. Network simulations with the NS-3 simulator[J]. ACM SIGCOMM Demonstration, 2008, 14(14): 527.

[31] MASTORAKIS S, AFANASYEV A, ZHANG L. On the evolution of NDNSIM: an open-source simulator for NDN experimentation[J]. ACM SIGCOMM Computer Communication Review, 2017, 47(3): 19-33.

[32] UHLIG S, QUOITIN B, LEPROPRE J, et al. Providing public intradomain traffic matrices to the research community[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(1): 83-86.

[33] WANG Y, LI Z, TYSON G, et al. Optimal cache allocation for content-centric networking[C]//The 21st IEEE International Conference on Network Protocols. 2013: 1-10.

Traffic scheduling method based on centralized control in named data networking

DONG Qian1,2,3, LI Jun1, MA Yuxiang1,2

1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China 2. University of Chinese Academy of Sciences, Beijing 100049, China 3. Department of Electronic and Information Engineering, Foshan University, Foshan 528000, China

In order to address the global optimization problem for traffic scheduling in named data networking, related works were analyzed, a method based on centralized control was proposed. The proposed method took network performance and communication overhead into account. In the proposed scheme, appropriate nodes would be selected as E-NDN nodes, then the controller calculated the corresponding multi-path forwarding policies and sent them to E-NDN nodes according to the in-network cache, the aggregation of Interest packets, and the traffic demands of popular contents to achieve global optimization. The evaluation results indicate that the proposed method can significantly reduce the maximum link utilization and improve network performance. Simultaneously, the proposed method will not cause a large optimization cost, and communication overhead between the controller and nodes will increase slightly.

named data networking, centralized control, traffic scheduling, hybrid network, linear programming

TP393

A

10.11959/j.issn.1000−436x.2018121

2017−10−19；

2018−06−05

李俊，lijun@cnic.cn

国家重点研发计划基金资助项目（No.2017YFB1401500）；国家自然科学基金资助项目（No.61672490）

The National Key Research and Development Program of China (No.2017YFB1401500), The National Natural Science Foundation of China (No.61672490)

董谦（1986−），男，湖北咸宁人，中国科学院计算机网络信息中心博士生，佛山科学技术学院讲师，主要研究方向为未来互联网、软件定义网络、流量工程等。

李俊（1968−），男，安徽桐城人，博士，中国科学院计算机网络信息中心研究员、副总工程师、博士生导师，主要研究方向为未来互联网、网络安全等。

马宇翔（1991−），男，河南开封人，中国科学院计算机网络信息中心博士生，主要研究方向为网络体系结构、网络安全等。