摘要：网络功能虚拟化（networkfunctionvirtualization，NFV）旨在以软件的方式实现网络功能从而替代传统网络中的专有硬件设备．为了应对日益增长的资源密集型需求，面向软件的网络功能虚拟化带来了如虚拟网络功能的管理、低延迟的调度和虚拟网络资源分配等问题．虚拟网络功能调度问题本身为NP‐hard，在虚拟网络功能资源调度延迟的特定问题上，为保证良好的用户体验，需要确保网络资源被合理地分配和协调以防止资源的过度供应和保持端到端低延迟．针对网络资源调度的延时问题建立了以最小化资源调度总体服务延迟为目标的整数线性规划模型．此外，为了满足网络动态性较高的特性，设计了一种基于贪婪的启发式算法，此算法首先构建辅助图，然后根据考虑到网络传播时延影响的不同业务链之间的时延影响分析来选择资源调度方案，并且对很多点处理功能采用了多路传输的方式．最终的实验结果表明：所提算法可以有效地指导模型的求解，在降低网络总体服务延时方面比之前相关研究有５％～１５％的性能提升．
关键词：网络功能虚拟化,软件定义网络,服务链,资源调度,多路传输
现有的网络功能例如防火墙（FW）、入侵检测系统（IDS）、网络地址转换器（NAT）和负载平衡器（LB）等，通常部署在价格昂贵的专用硬件（Middlebox）上用以满足网络吞吐或者安全等方面的特殊需求．网络功能虚拟化（networkfunctionvirtualization，NFV）的概念是由服务提供商组织提出，目的是在已有的商用设备上通过虚拟化技术以软件的方式实现特定网络功能（networkfunctions，NFs），从而取代传统网络中的专用设备的方式［１］；而软件定义网络（software‐definednetworking，SDN）起源于校园网络，广泛应用与数据中心，SDN的特点是分离了传统网络格局的控制平面与转发平面，在这种架构下，网络具备较高的灵活性并且易于部署和管理［２‐３］．NFV和SDN作为未来网络创新的两个重要角色，都有着通过网络创新的方式以打破当前网络僵化与臃肿格局的目标．
NFV如今作为业界与学术界的热点，它支持NFs的快速创建、撤销或迁移，依托着虚拟技术降低了网络成本从而得以迅速发展．由于安全或者性能的需求，网络操作者往往要求数据流以特定的序列通过多个NFs（例如数据包需要经过防火墙，然后经过入侵检测系统，最后经过负载均衡器），即通常所称的服务链（servicechaining）［４‐５］．网络功能虚拟化的主要挑战之一是根据服务链规则执行所需服务时，实现快速和动态的网络功能资源分配，因此虚拟网络功能资源调度优化得到了研究者们的关注．
根据应用或者用户的需求不同，虚拟网络功能资源调度有着不同的优化目标，比如，对于电信服务商来说，他们的长远目标是实现最大化所接受服务请求的经济收益，这就要求网络功能虚拟化在分配与调度资源的时候提高对服务请求的接受率；但是对于提供语音IP网络服务商来说，一定程度的带宽和低延迟保证是首先需要考虑的，此外类似的优化目标包括容错能力、负载均衡和能源消耗［６］等．近些年来，由于互联网络和网络应用的发展，使得如今网络具有更大的带宽和存储容量，但是包括移动应用、在线交互或者交易等新业务模型的激增，对于业务延迟的需求越来越高．比如，包括监控系统、在线金融分析、算法交易等对实时性要求较高的应用场景［７］；包括高清晰度、低延迟视频流、远程手术触觉互联网、虚拟或增强现实等在内的应用场景［８］．现有的一些延迟保证的研究实例包括：在５G系统中为了处理和传达用户的上下文信息，系统需要充分保证低的或者可预测的数据传输延迟来收集和共享上下文信息，并以及时和自动的方式执行服务［９］；“双十一”期间对网络延迟敏感的在线交易；移动端或者电脑端的在线游戏［１０］；计算机辅助协同的设计与工程［１１］和基于网络的电子学习［１２］以及视频会议等．对于服务提供商来说为了给用户提供良好的服务体验就需要保证服务延迟在用户可接受范围内．
面临着基于延迟保证的业务激增的现状，在应对用户网络功能请求的时候，需要按照不同的服务链顺序在网络中多个功能节点处执行对应的请求功能，因为网络资源是有限的，这样以来就会带来不可忽视的服务延迟，而过高的服务延迟将会降低整体的网络性能和用户体验．对于网络中包含大量的服务延迟敏感型业务需求，NFV在资源部署中就需要考虑到服务延迟对系统性能的影响，合理的节点资源分配可以大大减少节点端的处理延迟，但由于在网络功能服务需要网络中特定序列的服务链，网络延迟同样成为实现网络功能服务中低延时高质量体验的主要障碍［１３］．因此在虚拟网络功能资源调度中存在的挑战包括：１）确定流路径，以正确的顺序遍历合适的处理节点，以满足给定服务链的需求；２）在通过现有的虚拟网络功能节点时考虑节点负载和其他动态特征．为实现有效的服务协调和管理，解决如何快速合理地分配和调度网络资源的问题，目前一些研究文献［１４‐１６］等在功能节点处理延迟上取得了瞩目的成果，比如文献［１４］考虑到虚拟网络功能的位置不确定情况下嵌入移动核心虚拟网络功能（VNF）的顺序，文献［１５］提高了节点利用率并减少处理节点对请求的响应延迟．不同于之前的研究，本研究首先以降低资源调度中总体服务延迟作为目标，然后结合具体网络提供动态性较高的调度算法，其现实意义在于使得服务商能够满足更为严格的延迟约束服务，从而可以为更多的客户提供良好服务．
考虑到在软件定义的网络和网络功能虚拟化共存的背景下，NFV在创建服务方面更为动态灵活，通过SDN与NFV结合还可以轻易操纵网络流经过指定节点从而实现各种复杂的网络功能以及灵活的服务链规则［１７］．更为具体的解释即为：SDN控制器借助全网视图的优势可下发细粒度的规则到网络转发设备，网络转发设备根据规则执行对网络流的操作，通过这种方式运营商或者用户引导网络流按照正确的顺序经过NFs．因此在这项工作中，基于SDN与NFV结合的研究背景，我们将借助SDN与NFV的优势，同时考虑影响网络功能总体服务延时的多个因素，通过采用构建辅助图和多路技术等方式为用户选择NFV的有序序列和连接它们的数据传递路径，以最小化延迟来最大程度地保证整体服务质量，具体内容将在第２节和第３节中详细介绍.
1相关工作
为了解决虚拟网络功能资源调度的延迟问题，目前一些研究在网络功能节点端的资源调度方面取得了丰富的成果．其中文献［１４］在延迟限定情况下对移动核心网络功能虚拟化映射问题做了研究，它考虑到虚拟网络功能的位置不确定情况下嵌入移动核心虚拟网络功能（VNF）的顺序，其延时限定包括处理、排队和传播引起的延迟．另外为提高节点利用率并减少处理节点对请求的响应延迟，文献［１５］提出了基于服务优先级的加权服务链放置算法和基于组合优化的请求调度算法．文献［９］认为如今虚拟网络功能通常分布式地部署在网络边缘，在５G系统中，动态的服务需要在分布式和虚拟化的资源设施中灵活地配置并完成异构服务，在他们的工作中通过组合优化选择虚拟网络功能节点从而达到最小化的网络与处理延迟．文献［１８］通过整数线性规划模型有效地放置虚拟网络功能和部署服务功能链，研究内容包括虚拟功能节点数目，优化目标包括CPU和带宽资源消耗以及端到端延迟等．文献［１９］考虑虚拟网络功能的传输和处理延迟，在这里作者探讨了动态虚拟链路带宽分配的好处，作者对到达的业务通过遗传算法的带宽分配的决策处理作为提高网络性能的有效手段．在文献［２０］中，研究者们针对网络功能虚拟化服务商为用户提供动态灵活的虚拟网络功能服务中面临的服务流波动问题，作者采用主动预测流的方式最小化预测产生的错误，并且采用自适应的调整策略，降低虚拟网络功能的部署成本．文献［２１］设计实现了NFV‐RT系统，此系统的目的是：在云计算环境中满足服务链时间限定的前提下最大化所接受的服务链请求数目．文献［２２］通过测量不同类型的虚拟网络功能间协作干扰，研究不同VNF因竞争资源对性能产生的影响，并根据测量结果给出了更加有效的VNF放置方法，对于虚拟网络功能的研究和应用有着显著的现实意义．此外，在虚拟网络功能负载均衡对性能的影响方面，文献［２３］首次提出主要控制荷载（dominantload）的概念作为衡量节点负载的标准，研究中提出的解决NFV中多资源负载均衡问题的优化算法比传统的标准算法更加快捷和高效．
但是，这些调度方法没有考虑到如下问题：当网络存在多个相同功能点的时候，采用多点处理方式会进一步降低系统的总体服务延迟，但前提在多点处理的时候必须考虑到路径不对等带来的延迟差异，所以此问题需要结合具体拓扑讨论，之上的研究中也没有考虑到网络拓扑问题；另外，由于如今网络动态性较高，需要提供一种计算复杂度和运行时间较低的算法．本研究提出了一种提前构建辅助图，根据不同服务链间延时影响分析确定调度顺序而且采用多路传输的资源调度方案，最后设计了一种基于贪婪的启发式算法，以提高虚拟网络资源调度中保障时效性的能力．
2网络与问题模型
2．1网络模型
在问题模型中，我们用S来表示网络服务集，模型中的｜S｜代表服务集S的数量，［１，｜S｜］表示１～｜S｜的整数集合，其他类似表示以此类推；si表示对应网络服务i的服务链，其中i∈［１，｜S｜］．每条服务链si对应着一系列需要按规定顺序经过的网络功能，在此用F表示网络功能fj的集合，fij表示网络服务i所对应的虚拟网络功能fj，（i∈［１，｜S｜］，j∈［１，｜Fi｜］）．在研究中用G＝（N，E）来表示节点集为N、边集为E的网络．此外，不论处理网络功能虚拟化虚拟机是位于服务器还是交换机，在这里统一为物理机，因此都用网络节点N来表示．不同的虚拟机节点可能配备不同的虚拟网络功能，因此我们定义虚拟机集合V＝｛v１，v２，⋯，vv｝中各虚拟机所配备的功能为虚拟网络功能F＝｛f１，f２，⋯｝的子集比如，如果表示节点vk的网络功能为｛f１，f５，f８｝，意思就是在虚拟机vk上只能处理网络功能f１，f５和f８.
在我们的虚拟网络功能资源分配优化的研究中，使用延迟作为成本度量，因此在网络模型中需要包含节点部分延迟和节点之间通信的延迟．虽然之前有部分的研究，如文献［１４‐１６，１８］等，在NFV节点资源调度带来的处理时延上取得显著的成果，也有个别的工作考虑了NFV节点资源调度带来的传输时延问题［２４］．在本研究中同时考虑了网络时延和处理时延，所谓的网络时延就是在资源分配与调度时带来的传输时延和传播时延．传输时延主要由包的大小和链路的传输能力决定，如果把某虚拟链路传输速率表示为bl、某网络服务si需要传输的数据包大小表示为Di，传输延迟就可以很容易通过Di÷bl算出．而传播时延就是在资源调度时对源点与目的节点的路径选择带来的延迟，具体的延迟是由对应的网络拓扑和传输方式决定．如果细分的话网络服务总体延迟还需要包含队列时延，队列时延主要由输出接口链路负载、调度策略以及队列模型（比如经典的M∕M∕１模型［２５］）和缓存区的大小［１９］影响，关于队列已经有了很成熟的研究，不属于本研究的范畴．为了简化，本研究遵循文献［１８，２４］的设定，即服务链已知情况下，每个虚拟节点最多只能同时处理一种网络功能并且在转发完一条服务流之后才能转发下一条网络服务流．
2．2问题描述
虚拟网络功能的调度与路由问题的约束有２个方面：１）维持提供服务的服务链顺序；２）以最小的代价找到从源到目的地的路径，在此项研究中的代价将由延迟来表示．具体来说，给定网络服务集，每项服务是由特定的序列构成，在网络资源限定的条件之下构建模型，根据规则序列为所有的用户流选择总体服务时间最短的网络功能实例和传输路径，通过最小化延迟来保证网络的整体服务质量．为了更好地描述问题，在此以图１所示的方式表示在虚拟网络功能调度中不同的调度方案对最终服务延迟的影响．在图１中，存在VM１，VM２，VM３三个不同的虚拟机，椭圆表示每个虚拟机所配置的网络功能，另外还有３种网络功能服务链，每种服务链对应不同的网络功能．
在图１（a）中，表示时间轴的箭头下方为一种网络功能资源调度方案，此方案中首先由VM１的服务链１中的f１，紧接着是服务链２中的f２，然后经过４t的传输时间服务链１接受VM２的f５功能处理，在此期间服务链２必须等待至时间４t才能得到所需服务，其他服务以此类推，最终完成所有服务总体所耗费时间为１１t（由图２（a）中的VM３‐１得到）但是如果采用箭头上方所示的另外一种方案，也就是在VM１处理完f１和f２时，调度的时候首先选择传输服务链２中f２至VM３，最终可以得到总体所需服务时间为１０.５t（由图２（a）中的VM２得到），由此可知通过控制器对网络功能资源合理调度就能减少网络的总体服务时延．另外网络中还存在的常见情形就是在网络中具备多个相同功能的服务节点（比如有多个代理服务器的情况），或者下一个服务功能点同时受到多个上游功能节点制约（比如文献［１７］中的防火墙与监听器并行处理对应着下个序列的负载均衡器）．如图１（b）所示，f７同时受到f６与f３制约，VM１与VM２同时具备网络服务功能f６，通过计算选择VM１与VM２同时处理服务链３中所需的网络功能f６，即使存在传输时延，但通过VM２‐１与VM２‐２的服务结束时间对比可得，总体服务时延由１０.５t降为１０.１t，采用上面的调度方式，网络的服务延迟会降低，进而提升用户的体验．
表１表示的是每个服务链所需网络功能的服务时间，我们用时间片t来表示，除了服务链１的f１→f５虚拟传输时延为４t以及服务链２的f２→f４和服务链３的f６→f７的传输时延为２t之外，其他的网络功能跳转切换虚拟机的传输时延均为t，比如在服务链２中，VM１处理网络功能f１之后跳转到VM２处理网络功能f４，所需传输时延为时间t．以上虽然是为了在图例中清晰表述而做出的设定，但在实际情况中这些都是可以由控制器计算得出．
直观上来说，如果存在一个合理的网络功能调度方案使得对用户的服务延迟最小，在网络传播的时候选择，把延迟作为权重，选择最短路径算法（比如Dijkstra），用户就能得到总体最小延迟．但是如上所述，当网络中存在多个相同功能的网络功能节点时，不对等的路径就会带来额外的延迟．在此我们使用图２所示的例子来解释这些问题，其中实线的箭头表示从源s到目的地d的路径，虚线代表路径节点的其他可用链接下一跳．比如图２中选择源点s到目的地d的一条路径为｛s→u→w→y→d｝，其中y为用户所需服务节点．但是网络中若存在与y节点功能相同的另外节点x，如果因为链路负载或者多路传输减少服务延迟等原因使x作为网络功能服务节点，就会存在途径x的另一条路径x．比如现在与网络功能虚拟化相关的部分研究成果文献［１８］和文献［２４］，作者根据自己的研究目标提到在实现过程中可以考虑采用多路传输的方式．虽然多路传输的方式可以一定程度降低网络的总体服务延迟，但是如果路径x与路径y延迟不等就有可能带来额外延迟，所以在虚拟网络资源调度时，如果存在多路传输的情况，需要把传播延迟也要考虑其中．
通过２．１和２．２节的描述，为保证网络服务在处理功能请求时所调度资源满足现有网络条件，限定条件由式（２）～（６）表示．值得注意的是，服务器硬件资源容量约束（CPU、内存等）、网络带宽约束等和延迟相关的其他约束都可以在计算处理延迟或者传输延迟的时候隐式地处理．在限定条件式（２）中，τij－１表示第j－１项功能节点开始转发服务流si的时间，αij表示第j项功能处理的开始时间，Mfij为具备si的fij功能的节点集，式（２）是为了保证服务链上的下一功能节点处理开始时间必须在上游节点传输与网络传播完成之后；条件式（３）是为了保证服务流si在传输之前满足j项功能所需的处理时间；在源节点处，如果选择单路径，则输出链路的数量减去输入链路的数量应该等于１，限定条件式（４）表示服务流si对应的源节点；式（５）表示为目的节点输出链路的数量与输入链路的数量关系；式（６）是为了保证所选择路径无环，其中定义ziuv为服务si所选路径上的边对应的顺序编号，如果所选边不存在或者（u，v）不是所选路径上的边，则yiuv＝０，ziuv＝０，Nsp为所选路径节点集合Np的子集，２≤h＜｜Np｜，h为整数．
3算法设计
3．1算法描述
事实上，在虚拟网络功能调度与路由问题中，想获得最佳的资源调度是一个组合难题．在基于延迟的虚拟网络资源调度问题中，需要考虑到给定的服务器或者其他硬件资源的限制，同时还要服从于虚拟网络功能的服务链顺序限定，必须为不同的网络服务找到对应的网络功能，并且根据已知的源与目的节点选取延迟最小的功能执行时隙和路径延迟，根据已有的研究结果可得出，此组合问题为NP难问题［１９，２５‐２７］．由于网络功能资源调度问题的复杂度，实际中寻求最优结果的组合在计算复杂度和应用时间上是不现实的，本研究中我们选择采用启发式贪婪算法作为算法设计的基础思想．
一般来说，贪婪算法的基本思想是迭代选择每一步的最佳解决方案，这样有可能使得最终结果陷入局部最优，但是比起禁忌搜索和遗传算法等启发式算法来说贪婪算法的好处是运算时间较短，较为适合用户请求动态性比较高的网络场景．我们算法设计主要想法是首先将网络转换为分步骤处理的辅助图，然后通过保证延迟的多路径传输算法解决虚拟网络功能资源分配的延迟问题．如图３所示，目标是找到原点到D的最短延迟路径，首先我们先构造与图３类似的辅助图层，其中实线代表遵循服务顺序的最短路径，虚线代表其他路径或者其他功能节点路径．比如图３中VM１与VM２同时具备网络功能fn，VM３配置的网络功能为fn－１，则服务链s２（fn→fn－１）所对应的辅助图即为S２→S３→S１０→D和S２→S７→S１０→D，辅助图边上的权重由网络传播延迟计算可以得出．通过构建辅助图层的方式，加上节点的处理延迟和传输延迟以及等限定，问题就可以转化为在多个服务流共存的情况下找到总体延迟最短的路径．
3．2虚拟网络功能延迟服务算法
算法1．延时感知的资源调度算法（AGM）．
输入：网络图G＝（N，E）、网络服务请求集S、网络功能节点集合Mfij、xijk＝１即为服务si网络功能fij对应的功能节点k；
步骤１．预处理生成辅助图形．根据请求服务集S中循环获取服务si及其对应的服务功能fij集合，并根据fij对应的功能节点集Mfij由Dijkstra算法寻找最短路径生成si的辅助图．
步骤２．根据构建的辅助图，循环计算出各功能节点所需处理的服务链时延之和，按照递减排序为Mr．
步骤３．如果首次循环找出其中辅助图上游节点为源节点的所有Mr项，非首次循环选取Mfij的Mr第１项，判断上游节点是否是已经分配节点或者源节点，否则选取下一项Mr，从中找出所需时延之和最小的si项和第２小的sj项．
步骤４．对比si和sj，如果上游节点存在多路传输的情况，选取该项，跳转到步骤５；否则对si和sj项做交叉对比处理时延和传输时延的差值，选取绝对值最小的服务项，若下游节点存在多个可选功能节点对网络服务功能流进分解，跳转到步骤５．
步骤５．多路传输处理，若存在多个可选功能节点，根据服务延时和路径时延计算比例函数，然后根据比例函数θj分别进行传输，θj由下式算出：
4实验结果与分析
在本节中，我们对本研究中虚拟网络功能调度和资源分配方法在延迟方面的性能进行了数值评估，通过与资源调度中的先来先服务方案对比得到延时性能提升比例，证明本研究方案的可行性和优越性．
4．1实验设置与案例分析
在实验中我们使用与文献［１８］和文献［２０］相同的处理延时和传输延时设定，首先设定每个功能的处理时间随机选择区间为１０～２０ms，对应的传输时延从５～２０ms中随机选择，并且保证每个网络功能至少配置在一个VM节点中．
在第１个实验案例中，采用了图３的例子对研究方案性能进行分析，在图３的３个VM节点中一共随机设定了５种网络功能，并且保证有２个节点存在相同的网络功能；然后进行了１０００次的循环实验，每次实验中都随机生成４０条服务链请求并随机选择具备重复功能的节点；最后得到图４所示结果．图４中圆点代表我们的调度方案与随机的先来先服务调度方案在延时性能的提升比值（用AGM表示），可以看出在这些实验室中性能比例提升大部分都落在０.２～０.４的区间内，也就是２０％～４０％；星号点代表采用多路传输来同时处理相同网络功能在延时性能提升方面所占的比例（用MR表示），观察得出提升比率在５％～１５％的区间．另外在文献［２０］中提到，在资源调度中，对于一个５个节点的小型网络（对应的遗传算法运行时间为０.４５s），解决这个问题的最优解运行时间高达１０００s，而我们的算法平均执行时间为０.１６s；而在具有２个网络服务的１０个节点网络中，模型运行时获得最佳解决方案是按小时进行的．综上可以看出，我们基于贪婪的算法设计能更好地适应于网络的动态性需求．
在图５所示的第２个实验案例中，采用了文献［２８］中具备８８个节点和１６１条链接的真实拓扑，网络传播时延也来自于真实数据．在１０００次实验中，每次随机生成１６０～２００条服务链请求，随机生成的６个VM节点配备了１０种网络功能，其中３～５个功能节点配置有相同的网络功能．在本案例中增加了对文献［１６］H算法的对比实验，H算法即：对于每个VNF链，首先将资源要求最高的VNF放在剩余资源容量最大的节点中处理，然后尝试将该服务链的其他VNF放置在尽可能多的同一个节点上，因为默认每个节点处理能力相同，在此选择剩余资源容量最大的节点为需要等待服务时间最小的节点．通过观察实验结果，可以发现其中多路传输的多点处理方式性能提升空间大部分在５％～１７％之间，总体提升比例大部分在０.３３～０.４５之间，比起H算法仍有１０％左右的性能提升．不足为奇的是，随着拓扑节点和请求的增加，我们可以获得更好的性能（例如：较多比例的提升空间）．这是因为有了更多的可调度服务链和功能处理节点，使得选择变得更加灵活，从而导致服务延迟更短．另外在图６的１００次实验中采用了文献［１９］中的带宽方案，设定每个功能节点传输延迟选择Dibl或Di４bl，对应着方案中｛１，４｝Mbps的带宽设定．在图６中，底部的带星号的曲线表示不考虑网络传播延时的总调度延时（用NDS表示）；顶部的虚线代表文献［１９］中的方案（用DBS表示），即对于每个服务链如果功能节点中负载较大，则选择传输延迟为Di４bl的带宽分配方案，反之选择Dibl，功能节点之间的路径选择采用最短路径；中间的直线表示考虑网络传播延时如果存在多点处理则采用多路传输的方案（用DMS表示）．从图６中首先可以看出网络的传播延时对总体服务延时有着较大影响，然后即使采用了文献［１９］中的带宽优化方案并且路径最短路径，我们的方案仍能体现出更好的性能提升效果．
5结束语
本文针对网络功能虚拟化资源分配与调度过程中任务的调度顺序和传输方式影响网络总体服务延时的问题，本研究根据对服务链之间调度造成的延迟影响转移到其他能够降低该延迟的服务链顺序和多个处理节点之上的思路，提出创建辅助图与多点处理的策略，然后借助辅助图的简洁性设计了满足网络动态需求的启发式算法，实现对虚拟网络资源的合理调度并采用了多路传输方式进一步减少资源调度对总体服务延迟的影响．最后，通过模拟实验结果显示，本研究能够有效提高虚拟化网络功能时效性的能力，减少虚拟网络功能服务系统的总体服务延迟．
立即询价
