面向多业务需求的NFV和SDN融合的资源优化算法

朱晓荣，张倩



面向多业务需求的NFV和SDN融合的资源优化算法

朱晓荣，张倩

（南京邮电大学通信与信息工程学院，江苏 南京 210003）

物联网的多种业务需要灵活的网络部署来保障其服务质量。针对物联网服务功能链部署问题，将网络功能虚拟化（NFV, network function virtualization）与软件定义网络（SDN, software defined networking）相结合，综合考虑转发成本以及流量平衡情况，给出了虚拟网络功能放置与服务功能链路由的联合优化模型，该优化模型是NP-Hard问题。为了求解该问题，提出两种启发式算法：一种是先路由后放置（FRTP, first routing then placing）的服务链部署算法，另一种是基于节点优先级的先放置后路由（PFBR, placing followed by routing）的服务链部署算法。仿真结果表明，与其他算法相比，提出的FRTP和PFBR算法能显著平衡网络中的流量负载，改善链路拥塞情况，从而提高服务功能链请求接受率。

物联网；虚拟网络功能；服务功能链部署；节点优先级；负载均衡

1 引言

随着物联网的发展，各种各样的业务对网络的需求日益多样化[1]。例如，车联网中的通信对时间的敏感度高；工业制造中要求低分组丢失率和低时延；而移动视频监控网络可以容忍适度的误码率和时延，但需要高带宽。现有的专用硬件网络系统架构面临着诸多严重缺陷，例如，网络体系架构僵硬、网络升级维护困难、功能平面划分不合理等，难以应对日新月异的物联网业务需求。

SDN通过数据平面与控制平面的分离，并借助开放的接口，为形式各异的网络应用提供灵活的承载服务。NFV使用虚拟化技术以消除对专用硬件的依赖[2]，并使很多不同的网络设备类型合并到行业标准高容量服务器、交换机及存储器上，通过灵活的部署策略来提高网络基础设施的资源利用率和服务质量[3]。

虽然SDN和NFV技术的应用有望满足物联网多样化的业务对网络灵活组网的需求，但是NFV技术对网络服务重新抽象和细粒度分解，使其组成成分更加复杂，关键的挑战在于服务功能链（SFC, service function chain）的部署。由于巨大的服务规模以及高动态的网络负载，物联网复杂业务驱动的动态服务网络构建机制无论对当前还是未来都是一个挑战。

Wang等在文献[4]中，针对NFV资源分配问题，提出一种综合的成本模型，在满足用户需求的基础上实现最低成本的资源分配目标。Hendrik Moens和Filip De Turck考虑了物理网络功能（PNF, physical network function）和虚拟网络功能（VNF, virtualized network function）共存的场景，决定网络中功能的正确放置位置，可以较为充分地利用物理和虚拟资源[5]，以实现服务功能链部署的扩展性和灵活性。Kanizo等[6]用图论来解决NFV的资源分配问题，将虚拟网络功能和服务器（具有多个虚拟机）看作二分图中两个互不相交的子集，侧重于解决节点功能失效时，由支持该功能的服务器进行恢复，从而使故障功能恢复的可能性最大。

Mohammadkhan等[7]将关注点聚焦于网络功能的放置以及业务流路由的均衡问题。为了给特定的服务功能链分配资源，Leivadeas等[8]在放置VNF和为功能链选路的同时，用加权系数对资源利用率和带宽利用率进行权衡，以实现网络中负载平衡，从而有效提高资源利用率。Lopez等[9]提出了一个根据网络拓扑放置虚拟网络功能并构建功能链的方案，并给出了几种启发式算法，但更加侧重于功能放置构建服务功能链的方法。

Seliuchenko等[10]提出扩展的多商品流模型（multi-commodity flow model），使用服务质量标准来平衡负载，业务流的路由问题可以根据分类进一步细化。Pham等[11]对NFV多径路由的负载平衡问题进行了分析，研究了基于NFV的网络系统用户需求的变化，提高响应能力，从而优化网络性能。

Nam等[12]将NFV服务功能链引入无线接入网，使移动边缘计算（MEC, mobile edge computing）功能可以分配给附近的基站，从而使业务接入用户设备获得更低的时延体验。为了实现NFV的全部潜力，NFV扩展到无线接入部分[13]，其缺点在于每个SFC需求的功能只能部署一次，而且每个功能需要放置在不同的节点上，这在一定程度上会引入链路时延。

Bari等[14]定位在企业网络，致力于降低部署网络功能的总成本。为了实现服务链部署，Sun等[15]考虑在服务链之间共享虚拟网络功能，并在相同的节点中，部署相邻的虚拟网络功能以避免带宽消耗。Hirwe等[16]针对VNF的放置影响交换机负载和带宽利用效率等问题，提出一种高效的算法——LightChain，以消除乒乓流量。针对多个服务功能链的VNF共享，Savi等[17]考虑到升级成本和上下文转移成本的影响，以最小化NFV激活节点作为优化目标。Beck等[18]考虑的是物理网络的节点与链路出现故障时，如何进行资源合理分配的问题。如果某些节点失效，则需要将部署在该节点处的网络功能进行合理的迁移或由备份的VNF实现，以保障弹性和扩展性。

针对VNF链如何最佳地协调分配到网络基础设施上，Beck等[19]提出一种启发式方法—— CoordVNF，旨在合理的运行时间内最大限度地降低带宽利用率。Liu等[20]试图确定放置中间件的最佳位置，以便优化服务链性能，并提出两种启发式算法——贪婪算法和模拟退火算法来获得次优解，结果表明，其可以减少22％的端到端时延，平均节省38％的带宽消耗。Bouet等[21]出于对网络安全的考虑，将vDPI（virtual deep packet inspection）部署在网络中，以成本最小化为目标建立模型，结果证明提出的基于中心的贪婪算法很好地趋近最优解。Mijumbi等[22]针对VNF部署问题，侧重于提出虚拟网络功能的映射与调度算法，其提出的3种贪婪算法以及基于禁忌搜索的启发式算法中，后者表现出稍许的优势。

虽然目前已有很多文献对NFV资源分配和SDN路由策略进行了研究，但是仍存在着很多不足。例如，大多数文献中构成功能链的VNF，其占用资源单一，几乎没有考虑同时需要计算、存储等多维资源需求的场景。另外，有些文献仅从NFV资源分配或SDN路由策略某一个方面重点考虑，容易陷入局部最优解，如何协调二者之间的关系，值得深入研究。

在这种背景下，本文研究动态服务网络的NFV和SDN融合的资源优化算法，根据网络状态的动态变化、业务特性提出联合优化模型，确定业务驱动的最优传输性能的资源优化方法，从而有效保障用户QoS，并实现网络性能优化。为了方便求解优化模型，本文根据VNF放置与业务流选路的顺序提出了两种启发式算法——FRTP算法和PFBR算法。FRTP算法侧重从用户角度出发，使大量的数据分组在数据平面快速转发，提高用户体验；基于节点优先级的PFBR算法，能有效地平衡网络中的流量负载，提高服务链请求接受率。

2 系统模型

NFV技术将用户的请求转化为VNF构成的服务功能链，SDN将流量管理与流量转发分离，实现集中控制。在控制平面，SDN控制器管理网络资源并控制全局网络流量。基于网络状态信息，控制器可相对于服务功能链的QoS需求，确定通信路径，从而做出灵活的流量控制决策，经由OpenFlow南向API，数据平面硬件用于转发数据分组，优化整个网络的运行。本文将服务功能链部署问题分为两个阶段。根据服务功能链的源节点、目的节点以及VNF次序，将服务功能链所需的一系列VNF放置在网络上的NFV节点，以满足用户定制的网络服务需求；SDN控制器根据服务功能链的需求，为其选择一条最佳路径，直至构成一条完整的端到端路径。

图1给出了一条服务功能链的资源分配与链路映射示意，该条服务功能链共有5个虚拟网络功能， SDN控制器以及VNF管理编排器（MANO, management and orchestration）依据SFC请求以及当前网络状态，实时地将服务功能链所需的VNF分配在物理节点1、物理节点2、物理节点2、物理节点5、物理节点3处，另一方面，SDN控制器为该条服务功能链规划的路径为(s,1)→(1,2)→(2,3)→(3,5)→(5,4)→(4,3)→(3,)。

图1 服务功能链资源分配与链路映射示意

3 NFV和SDN融合的资源优化模型

本文提出的NFV和SDN融合的资源优化模型分别如式(4)~式(12)所示。

4 算法描述

众所周知，NP-Hard问题难以在多项式时间内求解，因此，本文根据VNF放置与业务流选路的顺序提出了两种启发式算法求解NFV和SDN融合的资源优化模型。一种是对SFC先进行灵活的路由决策，然后在该路径上依次顺序地放置所需的VNF，称为先路由后放置的服务链部署算法；另一种则刚好相反，先将服务功能链所需的VNF放置在优先级最高的节点上，继而遍历源节点、该节点以及目的节点，形成一条完整的路径，称为先放置后路由的服务链部署算法。

4.1 先路由后放置的服务链部署算法

算法1 先路由后放置的服务链部署算法

步骤1 根据该阶段所有服务功能链的速率需求降序排序，标注优先级，向SDN控制器请求更新所有节点的可用资源以及网络链路的剩余带宽。

步骤3 为该条服务功能链选择从源节点至目的节点的最短路径作为最佳路径。

步骤4 为该条服务功能链选择从源节点至目的节点的前条最短路径中剩余带宽最大的一条作为最佳路径。

步骤5 判断该条最佳路径的最小链路剩余带宽是否大于速率需求，若是，转向步骤6；否则，转向步骤8。

步骤7 对选择的路径依次经过的节点顺序地放置VNF，直至放置完成，结束。

步骤8 继续搜索从源节点到目的节点的次佳路径，重复步骤5~步骤7，若均不满足，则结束，即拒绝该条服务功能链。

步骤9 重复步骤2~步骤8，直至所有的服务功能链均被部署或拒绝。

4.2 先放置后路由的服务链部署算法

算法2 先放置后路由的服务功能链部署算法

步骤1 根据该阶段所有服务功能链的速率需求降序排序，标注优先级，并依次为服务功能链进行VNF的放置。

步骤2 对物理网络中能够承载虚拟网络功能的节点进行优先级降序排序，排序的标准由式(14)所示，节点的优先级由该节点的可用资源以及选择该节点引入的跳数共同决定。

步骤3 对于每条服务功能链，其每一跳的放置依据为选择优先级最大的节点作为当前的最佳位置，判断当前选中的节点是否有足够的资源承载VNF，即是否满足资源需求式(13)，若满足，转向步骤4；否则转向步骤5。

步骤4 将该条服务链所需的VNF贪婪地放置在该节点上，动态更新节点的可用资源。

步骤5 继续搜索节点优先级次高的节点作为当前最佳节点，直到能够放置VNF，否则视为拒绝该服务功能链。

步骤7 在该条服务功能链的源节点、VNF的放置节点以及目的节点之间的每一跳，都采用最短路径，形成首尾相连的完整路径。

步骤8 判断选择的路径的最小链路剩余带宽是否大于速率需求，若大于，则该条服务功能链部署成功；否则转步骤9。

步骤9 在该条服务功能链的源节点、VNF的放置节点以及目的节点之间的每一跳，对其进行条最短路径搜索，得到剩余带宽最大的路径。

步骤10 判断选择的路径链路可用带宽是否大于SFC速率需求，若大于，则该条服务功能链部署成功；否则视为拒绝该服务功能链。

步骤11 重复步骤2~步骤10，直至所有的服务功能链均被部署或拒绝。

4.3 算法复杂度分析

5 实验结果及性能分析

为了对本文提出的FRTP和PFBR算法进行评估，将提出的启发式算法重点在总转发成本、负载均衡度、平均运行时间以及服务功能链请求接受率等方面与基于最短路径的服务功能链部署算法（其中VNF放置策略与FRTP算法相同）以及NAaP算法和AaP算法[15]进行对比。NAaP算法和AaP算法在路由阶段均优先采用最短路径，进行VNF的放置时采用贪心算法，二者的区别在于后者将源节点与目的节点相同的SFC进行融合，其中，带宽需求叠加，相同的VNF可以共享。

表1 6节点网络拓扑的算法结果

5.1 实验环境和参数设置

由于本文提出的服务功能链部署算法，可以分为两个阶段，既包含VNF放置阶段的算法，也包括服务链路由的算法。其中，VNF放置阶段的算法运行在Matlab 2015a环境中；FRTP和PFBR算法中的服务功能链路由算法部分写入Ryu控制器（SDN控制器），利用Mininet仿真工具生成网络拓扑，在Ubuntu系统里进行验证。

网络中的节点具有承载VNF的能力，节点数量越多，其具有的VNF所需的各类资源越多，服务功能链部署成功的概率越大，请求被接受的越多。因此，本文在设置仿真实验时，将服务功能链数量与网络节点数量进行相应的调节。

本文实验在初始阶段采用6个节点、8条链路的拓扑，每个节点具有3种资源类型，资源总量服从均值为100、方差为31.8的均匀分布，链路带宽为200 unit。SFC的数量为50~100，VNF种类共有7种，服务功能链所需的VNF为2~4种，对3种类型的资源需求均为0.2~1 unit，服务功能链的速率需求为1~5 unit，各种算法的对比结果如表1所示。然后，将网络规模扩展为20~100节点的随机网络，VNF的种类共有9种，每条服务功能链所需的VNF为3~6种，SFC数量由200条逐渐增加到1 000条。

5.2 性能分析

在较小网络规模下，服务功能链的数量由50递增至100，由表1可知，FRTP算法和PFBR算法在总带宽成本以及流量负载均衡这两个方面“势均力敌”，并未表现出太多的差异。FRTP算法和PFBR算法与基于最短路径的算法以及NAaP算法和AaP算法相比，总转发成本略高一些，而负载均衡度得到了降低，这是由于后者总是优先以最短路径进行业务流的转发，因此，总转发成本相对较低，相应地，负载均衡度会急剧升高。FRTP算法的时间开销略高于PFBR算法，其原因在于，在网络规模较小的情况下，FRTP算法先确定转发路径，继而依次顺序（相对平均地）将VNF放置在选定的路径经过的节点上，其主要复杂度在于对每一条SFC中的VNF所需资源与节点资源总量进行比对；而PFBR算法由于对服务功能链选择优先级最大的节点进行VNF贪婪的放置方法，因此，在网络规模较小时，运行时间更短一些。但是，与最短路径算法、NAaP算法、AaP算法相比，本文提出的两种算法由于复杂度更高，平均运行时间相对更长。AaP算法由于对SFC进行融合，相比逐条部署SFC，算法复杂度更低，其部署速度更快。

图2显示了网络拓扑节点数目为50时的随机网络中服务功能链数量与转发成本的关系。总体而言，转发成本随着服务功能链数量的增大而增大，FRTP算法的转发成本低于PFBR算法，由于总转发成本与选择的路径长度呈正相关，因此，二者的转发成本均高于最短路径算法、NAaP算法、AaP算法。

图2 总转发成本与SFC数量的关系

但仅考虑如何降低转发成本是非常片面的，容易造成网络中流量负载分布不均，有些链路异常拥塞，而有些链路非常空闲的情况。图3展示了随着SFC数量的增加网络中负载均衡度的变化。FRTP算法的负载均衡效果稍微逊色于PFBR算法，但这两种算法与最短路径算法、NAaP算法、AaP算法相比，在负载均衡方面表现出更强的优势。

图3 网络中负载均衡度与SFC数量的关系

在网络规模逐渐增大时，服务功能链的数量固定为500条，总转发成本并未随着节点的增大而呈现较大差异，这是由于生成的随机网络的平均距离大致相同，选择的路径长度也差别不大，因此，FRTP算法、PFBR算法的总转发成本相差不大。但是，网络中负载均衡度却有着较为明显的差别，图4描述了在网络规模逐渐增大时负载均衡度的变化趋势。整体而言，PFBR算法的负载均衡效果优于FRTP算法，而最短路径算法、NAaP算法、AaP算法明显劣于本文提出的两种算法，由此可见，FRTP算法、PFBR算法在路由阶段的优化起到了至关重要的作用。

图4 网络中负载均衡度与网络节点数量的关系

当网络拓扑固定为50个节点的随机网络时，算法的平均运行时间随着服务功能链数量的增大而增大，如图5所示。基于最短路径的算法与NAaP算法、AaP算法的时间开销相差不大，而本文提出的算法寻求带宽剩余量较多的空闲链路以平衡流量负载，其代价是更长的时间开销。FRTP算法的时间开销低于PFBR算法，与网络规模较小时的结论看似相反，实际由于FRTP算法的服务链部署算法选择的路径长度几乎不可能超过节点的数量，因此，PFBR的服务链部署算法在对每一条SFC计算节点优先级时需花费更多的时间。图6描述了网络规模逐渐增大时，各算法的时间开销，与SFC数量增多时的结论无异。

图5 算法时间开销与SFC数量的关系

图6 算法时间开销与网络节点数量的关系

本文实验还设置了一组仿真，在节点为20的随机网络中，将链路带宽上限设为100 unit，服务功能链的速率需求约为4~10 unit，验证不同服务请求的接收率。图7展示了在不同服务功能链请求强度下，各种算法的服务功能链请求接受率。AaP算法比最短路径算法、NAaP算法的接受率略高，这是由于在带宽和节点资源一定的情况下，AaP算法能够通过在多条SFC之间共享相同的VNF，从而降低由于节点资源不足以承载VNF导致服务链部署失败的概率。与最短路径算法、NAaP算法、AaP算法相比，本文提出的服务链部署算法表现出了显著的优势。其中，由于PFBR算法相比FRTP算法能够较好地平衡网络中的资源流量负载，因此，网络的资源能够得到更加充分的利用，服务功能链请求接受率相比其他算法有明显的提高。

图7 不同服务功能链请求强度与接受率的关系

综上，本文提出的FRTP算法、PFBR算法与最短路径算法、NAaP算法、AaP算法相比，在牺牲一部分转发成本的基础上，获取了更多的链路可用资源，能更有效地平衡网络中的流量负载，且提升服务功能链请求接受率。但FRTP算法与PFBR算法相比，更侧重于降低总转发成本，使大量的数据流在网络中快速转发，在一定程度上可降低服务功能链响应速度，提高用户体验，其也可以作为在线算法，实时地部署服务功能链。另一方面，基于PFBR的服务链部署算法在中、大规模网络以及SFC数量较多时可以更加有效地平衡网络中的负载，从而提高网络中整体的链路利用率，提升服务功能链请求接受率，其优势用于离线算法中更为明显。

6 结束语

本文主要研究了物联网环境下服务功能链的部署问题，根据网络状态的动态变化、业务特性，提出NFV和SDN融合的虚拟网络功能放置与服务链路由的联合优化模型。为了方便求解优化模型，本文提出了两种启发式算法，经仿真验证，与其他算法相比，FRTP和PFBR算法能显著平衡网络中的流量负载，提高请求接受率。就本文提出的算法而言，FRTP算法作为在线算法，在实时部署服务功能链方面，能够使大量的数据分组在数据平面快速转发，提高用户体验；而PFBR算法可作为离线算法，虽然其在降低总转发成本方面略显逊色，但在负载均衡方面优势凸显，使服务功能链请求接受率得到显著提高。两种算法的有益结合能够更好地部署服务功能链。在大规模网络和业务请求非常多的场景中，本文提出的两种算法虽能有效平衡网络流量负载，但时间开销增加很快。因此，在今后的工作中，期望研究更优化的启发式算法，在兼顾负载平衡的同时，尽可能地降低时间开销。

[1] BIZANIS N, KUIPERS F A. SDN and virtualization solutions for the Internet of Things: a survey[J]. IEEE Access, 2016, 4(99): 5591-5606.

[2] MECHTRI M, GHRIBI C, SOUALAH O, et al. NFV orchestration framework addressing SFC challenges[J]. IEEE Communications Magazine, 2017, 55(6):16-23.

[3] 袁泉, 汤红波, 黄开枝, 等. 基于Q-learning算法的vEPC虚拟网络功能部署方法[J]. 通信学报, 2017, 38(8): 172-182.

YUAN Q, TANG H B, HUANG K Z, et al. Deployment method for vEPC virtualized network function via Q-learning[J]. Journal on Communications, 2017, 38(8): 172-182.

[4] WANG L H, LU Z M, WEN X M, et al. Joint optimization of service function chaining and resource allocation in network function virtualization[J]. IEEE Access, 2016, 4: 8084-8094.

[5] MOENS H, TURCK F D. Customizable function chains: managing service chain variability in Hybrid NFV networks[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 711-724.

[6] KANIZO Y, ROTTENSTREICH O, SEGALL I, et al. Optimizing virtual backup allocation for middleboxes[J]. IEEE Journals & Magazines, 2017, 25(5): 2759-2772.

[7] MOHAMMADKHAN A, GHAPANI S, LIU G, et al. Virtual function placement and traffic steering in flexible and dynamic software defined networks[C]//The 21st IEEE International Workshop on Local and Metropolitan Area Networks. 2015: 1-6.

[8] LEIVADEAS A, FALKNER M, LAMBADARIS I, et al. Resource management and orchestration for a dynamic service chain steering model[C]//2016 IEEE Global Communications Conference (GLOBECOM). 2016.

[9] LOPEZ M A, MATTOS D M F, DUARTE O C M B. Evaluating allocation heuristics for an efficient virtual Network Function chaining[C]//2016 7th International Conference on the Network of the Future (NOF). 2016.

[10] SELIUCHENKO M, LAVRIV O, PANCHENKO O, et al. Enhanced multi-commodity flow model for QoS-aware routing in SDN[C]//2016 International Conference Radio Electronics & Info Communications (UkrMiCo). 2016.

[11] PHAM T M, PHAM L M. Load balancing using multipath routing in network functions virtualization[C]//2016 IEEE RIVF International Conference on Computing & Communication Technologies, Research, Innovation, and Vision for the Future (RIVF).2016: 85-90.

[12] NAM Y, SONG S, CHUNG J M. Clustered NFV service chaining optimization in mobile edge clouds[J]. IEEE Communications Letters, 2017, 21(2): 350-353.

[13] RIGGIO R, BRADAI A, HARUTYUNYAN D, et al. Schedulingwireless virtual networks functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(2): 240-252.

[14] BARI M F, CHOWDHURY S R, AHAMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 725-739.

[15] SUN Q Y, LU P, LU W, et al. Forecast-assisted NFV service chain deployment based on affiliation-aware vNF placement[C]//2016 IEEE Global Communications Conference (GLOBECOM). 2016.

[16] HIRWE A, KATAOKA K. LightChain: A lightweight optimization of VNF placement for service chaining in NFV[C]//2016 IEEE NetSoft Conference and Workshops (NetSoft). 2016, 33-37.

[17] SAVI M, TOMATORE M, VERTICALE G. Impact of processing costs on service chain placement in network functions virtualization[C]//2015 IEEE Conference on Network Function Virtualization and Software Defined Network (NFV-SDN). 2015: 191-197.

[18] BECK M T, BOTERO J F, SAMELIN K. Resilient allocation of service function chains[C]//2016 IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN). 2016: 128 - 133.

[19] BECK M T, BOTERO J F. Coordinated allocation of service function chains[C]//2015 IEEE Global Communications Conference (GLOBECOM). 2015: 1-7.

[20] LIU J, LI Y, ZHANG Y, et, al. Improve service chaining performance with optimized middlebox placement[J]. IEEE Transactions on Services Computing, 2017, 10(4): 560-573.

[21] BOUET M, LEGUAY J, CONAN V. Cost-based placement of vDPI functions in NFV infrastructures[C]//The 2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-9.

[22] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]//The 2015 1st IEEE Conference on Network Softwarization (NetSoft). 2015: 1-9.

[23] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. New York: W H Freeman & Company. 1979.

Resource optimization algorithm of combination of NFV and SDN for application of multiple services

ZHU Xiaorong, ZHANG Qian

College of Communications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China

Various services of internet of things (IoT) require flexible network deployment to guarantee different quality of service (QoS). Aiming at the problem of IoT service function chain deployment, network function virtualization (NFV) and software defined networking (SDN) were combined to optimize resources. Considering forwarding cost and traffic load balance, a joint optimization model of virtual network function placement and service function chain routing was given and was proved to be NP-Hard. In order to solve this model, two heuristic algorithms were proposed. One was the service chain deployment algorithm of first routing then placing (FRTP) and the other was the placing followed by routing (PFBR) based on node priority. Simulation results demonstrate that FRTP and PFBR algorithm can significantly balance network traffic load while alleviating congestion and improving the acceptance ratio of the chain requests compared with other algorithms.

internet of things, VNF, service function chain deployment, node priority, load balance

TN915.81

A

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

朱晓荣（1977–），女，山东临沂人，南京邮电大学教授、博士生导师，主要研究方向为5G通信系统、异构网络、物联网等关键技术及系统研发。

张倩（1994–），女，江苏徐州人，南京邮电大学硕士生，主要研究方向为网络功能虚拟化、软件定义网络等。

2018−01−29；

2018−05−10

朱晓荣，xrzhu@njupt.edu.cn

国家自然科学基金资助项目（No.61871237）；江苏省高校自然科学研究重大项目基金资助项目（No.16KJA510005）；江苏省研究生科研与实践创新计划基金资助项目（No.KYCX17_0767）

The National Natural Science Foundation of China (No.61871237), The Natural Science Foundation of the Higher Education Institutions of Jiangsu Province (No.16KJA510005), Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX17_0767)