基于软件定义网络的可靠性虚拟网络映射保障机制

赵季红，吴豆豆，曲 桦，殷振宇

（1. 西安邮电大学通信与信息工程学院，西安710121； 2. 西安交通大学电子与信息工程学院，西安710049）

（*通信作者电子邮箱:630611797@qq.com）

0 引言

软件定义网络（Software Defined Network，SDN）［1］具有控制和转发分离、网络集中管控、直接可编程和灵活配置等特性，实现了网络控制平面与转发平面的分离。根据其天然优势为网络虚拟化技术［2］提供了新的架构方案。两者的结合，可以更方便地为网络租户提供定制化和私有化的网络服务，通过虚拟网络映射（Virtual Network Embedding，VNE)［3］方法，可以完成从用户需求到底层资源切片的映射。高效、可靠的虚拟网络映射算法，可以减少租户和基础设施提供商（Infrastructure Provider，InP）的故障损失。当底层网络元素失效时，保证网络切片上运行业务的可靠性也是非常有必要的。

可靠性虚拟网络映射，也称生存性虚拟网络映射（Survivable Virtual Network Embedding，SVNE）算法［4］，主要研究物理网络元素失效时，尽可能保障虚拟网络的业务不受影响，属于NP-hard问题［5］。

对于SVNE 问题的解决方案，主要可以分为先验式保护和后验式恢复两种。文献［6］通过合理映射其他虚拟链路，降低节点故障的影响，提出了一种基于网络子图的SVNE 算法。属于后验式恢复方式，对于资源需求很大的虚拟网络（Virtual Network，VN）节点或者物理网络（Substrate Network，SN）负载较大的情况，故障恢复率较低。文献［7］提出了一种基于位置约束的节点备份SVNE 算法，为每个虚拟节点预留地理位置接近的备份节点，该算法可以保证很高的节点故障恢复率，但是对于资源消耗较大，冗余过多。文献［8］通过对虚拟链路实现虚拟网络级别的备份，提出了一种联合备用资源分配和映射的算法。该算法实现闲置资源的最大化利用，提高了链路的可靠性，但在虚拟请求数量巨大情况下，公共备份路径的可靠性是更需要考虑的问题。另外该算法没有考虑节点的故障问题，链路选择算法时间复杂度过高，不适用于大规模底层网络的情况。文献［9］提出了一种基于资源衡量的SVNE 算法，通过联合先验式和后验式的方式，尽可能地为虚拟网络提供备份资源，在物理网络不满足资源需求时，利用后验式恢复保障可靠性，该算法对资源需求较小虚拟节点和链路预留了备份资源，而实际中，这些资源需求较少的网络元素发生故障时，通过后验式进行故障恢复是很容易的，因此这种备份方式会预留很多无效冗余。

本文提出了基于SDN 的可靠性虚拟网络映射（Deterministic Survivable Virtual Network Embedding，D-SViNE）保障机制，采用联合先验式保护和后验式恢复的方式。在先验式保护阶段，对虚拟节点考虑可行域内节点资源感知和预测，对域内相对剩余资源减少的虚拟节点预留备份虚拟节点和相关虚拟链路，将扩展VN 通过可靠性虚拟网络映射（Deterministic Virtual Network Embedding，D-ViNE）算法［10］进行映射。对已经进行先验保护的虚拟节点和相关链路，在发生故障时，采用迁移工作节点和相关链路的方式完成故障恢复；对于没有预留备份资源的网络元素发生故障，采用后验式故障恢复算法，当节点故障时，采用贪婪算法重映射故障节点；当链路故障时，利用最短路径算法重路由以迅速找到可恢复路径。实验表明，该保护机制提高了节点故障恢复率以及虚拟请求接受率。

1 问题描述和定义

为保证虚拟网络映射（VNE）的可靠性，采用联合先验式保护和后验式恢复的方式。其中，先验式保护机制部署在虚拟请求接受之前，属于虚拟网络级别的保护，即根据物理节点和链路的剩余资源变化趋势，设定是否预留备份。后验式故障恢复机制是部署在虚拟请求映射成功之后，当发生故障时根据剩余资源进行故障的恢复，对节点和链路故障分别采用节点迁移和链路重路由的方式。

1.1 先验式保护

在SDN 网络环境中，对于任意虚拟网络GV=(NV，LV，)和物理网络GS=(NS，LS，)，在VNE 时需要构建工作拓扑和备份拓扑。其中工作拓扑包括工作节点M()∈NS和工作路径Ω()∈PS；备份拓扑包括备份节点bp()∈NS和备份路径bp()∈PS。对任意虚拟节点∈NV，设置备份标记BF()定义如下:

其中:PS表示物理节点之间的物理路径。同样地，对于虚拟链路∈LV，设置备份标记BF（）为:

虚拟链路到物理路径的映射关系表示为:

其中:M表示VNE 的链路映射，lv（ni，nj）表示节点ni和nj之间的虚拟链路，VN 节点ni和nj分别映射到SN 节点ns和nt，Ps（ns，nt）表示SN 节点之间的物理路径；BP表示备份链路的映射，bps（ns，nt）表示ns和nt之间的备份路径。

1.2 后验式故障恢复

后验式故障恢复是在故障发生时，分离受故障影响的虚拟网络元素，然后对每个网络元素逐个进行虚拟级别的故障恢复。对于单物理节点故障情况，对同一个虚拟请求，单个物理节点故障最多会导致单个虚拟节点失效，但是，可能同时会导致多条虚拟链路的失效，因此要分别考虑受影响虚拟网络的多个网络元素。

对于单个链路发生故障，该物理链路上可能承载多个虚拟网络的多条虚拟链路，也可能承载同一虚拟网络的多条虚拟链路，因此需要分离该物理链路上承载的每条虚拟链路。故障分离如图1所示。

图1 故障分离示意图Fig. 1 Schematic diagram of fault separation

4 仿真与分析

本文中由GT-ITM［12］生成设定的网络拓扑，通过NS2［13］中的Tk 工具生成可视化的网络拓扑图，结合Java 作为仿真工具，对该保障机制以及几种可靠性保证方法进行仿真，通过虚拟请求接受率、算法时间、虚拟节点级别的故障恢复率以及物理级别节点故障恢复率验证该算法的性能。

4.1 仿真环境与参数设计

本次实验通过GT-ITM 模拟物理节点故障发生的情形，并生成了1 000个虚拟网络和1个物理网络。实验参数［14-17］如表1 所示（U 表示均匀分布；P 表示泊松分布；E 表示指数分布）。其中，故障的发生服从泊松分布，平均每次记录时间单元内发生4 次物理节点的故障，实验总时间为20 000 个时间单元，每1 000 个时间单元记录一次节点的故障恢复情况和虚拟网络接受情况，实验共随机生成80个物理节点故障。

表1 实验参数Tab. 1 Test parameters

4.2 对比方案

在可靠性保障阶段，采用的对比方案是两种关SDN 可靠性映射保障的方法:一种方法为基于位置受限的生存性虚拟网络映射（Location Constrained Survivable Virtual Network Embedding，LC-SVNE）算法［7］，其属于全备份可靠性保障；另一种方法为基于SDN 的生存性虚拟网络映射（SDNSurvivable Virtual Network Embedding，SDN-SVNE）算法［9］，其属于尽可能的备份方式。三种算法的对比如表2所示。

表2 SVNE对比算法Tab. 2 SVNE contrast algorithms

4.3 性能分析

1）虚拟请求接受率。

图3 表示不同算法的虚拟请求接受率。从图中可以得出，三种算法初始阶段接受率都很高，随着虚拟网络的到达和离开接受率会趋于稳定。D-SViNE 算法相比较高的原因在于该算法属于部分备份方式，并且尽可能地降低了备份资源的消耗，因此在后期仍有着较高的虚拟网络请求接受率。而LC-SVNE 算法是对所有的虚拟节点都进行备份，备份节点会占用很多底层资源，导致虚拟网络接受率最低。SDN-SVNE算法初始接近全备份的方式，会使得映射备份消耗资源过多，底层网络资源很快会耗尽，后期无法对资源消耗较大的元素进行映射，导致虚拟请求的拒绝，所以该算法虚拟请求接受率会很快降低。

图3 虚拟请求接受率Fig. 3 Virtual request acceptance rate

2）算法时间性能。

图4 表示不同算法的实验时间。其中，实验一对前500个虚拟网络进行先验保护；实验二为映射1 000个扩展虚拟网络。从图中可以得出，在虚拟网络较少时，算法的映射时间很接近。随着物理网络负载的增大，D-SViNE 算法运行时间增长幅度介于SDN-SVNE 和LC-SVNE 算法之间。其中，相比于LC-SVNE 算法，SDN-SVNE 算法的运行时间减少了20%。其原因在于LC-SVNE 算法基于链路的可分裂方式，增加了链路映射的运行时间。在实验一中，D-SViNE 算法在时间效率上优于SDN-SVNE 算法，因为D-SViNE 算法在映射时，计算节点SPR 值排序结果，相比于SDN-SVNE 的节点随机映射会花费更少的时间，此外，由于初始时底层网络剩余资源充足，SDNSVNE设置的备份资源更多，备份映射会消耗更多的时间。而实验二中，两者时间消耗接近，因为SDN-SVNE 底层负载较大时，会选择部分备份或不备份的方式，因此算法运行时间相对D-SViNE较小。

图4 不同算法运行时间对比Fig. 4 Running time of different algorithms

3）虚拟节点级别的故障恢复率。

图5 表示虚拟级别故障恢复率，当故障到来时先进行故障的恢复。从图中可以看出，初始阶段虚拟级别故障恢复率都为1，主要因为此时随机节点故障可能没有影响虚拟网络，而且当底层资源充足，三种算法初始都有节点的主动备份，因此可以基本全部恢复。随着时间推移，随机节点故障越来越多，虚拟节点的故障恢复率趋于稳定的值。

LC-SVNE 算法节点的故障恢复率最高，稳定状态下可以达到80%。因为LC-SVNE 采用全备份的方式，节点的故障只能通过预留的备份节点资源完成故障的恢复。链路采用可分裂的路径映射方式，一旦备份路路径的链路点发生故障，则可能同时影响工作路径和备份路径导致故障的恢复失败。

D-SViNE 算法属于感知型备份方式，对资源需求较小的虚拟网络元素进行了冗余备份，而实际中这部分网络元素即使发生故障也很容易故障恢复，因此该算法无效备份较多，其故障恢复成功率在稳定状态下约为68.7%。

SDN-SVNE 算法的故障恢复率最低，主要因为该算法牺牲物理资源，以提高虚拟请求接受率。后期故障发生时，采用随机映射方式，重映射故障虚拟节点；相关故障链路的重映射，采用最短路径的方式，这种方式对资源需求较少的故障节点和链路效果较好，但对资源需求较大的情况，故障恢复率较低。

图5 虚拟级别故障恢复率Fig. 5 Virtual level failure recovery rate

4）物理级别节点故障恢复率。

图6表示物理级别节点故障恢复率。从图中可以看出DSViNE 算法和SDN-SVNE 算法在物理级别节点故障恢复率方面明显优于LC-SVNE 算法，因为LC-SVNE 没有设置节点故障的后验故障恢复机制，同一个物理节点可以在不同的虚拟请求中，承载不同的虚拟网络元素，发生故障时，仅靠预留的备份节点和相关链路，不足以恢复故障节点承载的所有虚拟网络。相比于SDN-SVNE 算法，D-SViNE 算法的物理级别恢复率相较于SDN-SVNE 提高约10 个百分点，这是因为SDNSVNE只对资源需求较少的虚拟网络元素进行先验保护，对资源需求较大的网络元素只进行故障后验恢复，而资源需求较大的网络元素，在网络负载很大时，很难恢复成功，因此SDNSVNE 的无效备份资源较多，物理级别故障恢复率较低。而D-SViNE 算法可以更好地感知底层网络剩余资源的变化，针对部分关键节点预留备份资源，可以降低冗余并且减少无效的备份。

图6 物理级别故障恢复率Fig. 6 Physical level failure recovery rate

5 结语

本文针对SDN 网络底层资源发生故障的问题，提出了一种基于SDN 的可靠性VNE 保障机制。首先对虚拟网络的关键节点映射域内剩余资源进行感知，提出了先验式保护算法；然后通过D-ViNE算法完成对虚拟扩展网络的映射，并设计后验式恢复机制。故障恢复时，采用联合先验式保护和后验式恢复的方式。仿真结果表明，该可靠性保障机制，在虚拟请求接受率、虚拟级别以及物理级别节点故障恢复率方面都优于现有算法。此外，在随机故障模型和区域性故障模型中，先验式备份的作用很小，所以设计更加合理的可靠性保障机制可作为后续的研究方向。