面向容错的网络虚拟化资源管理与映射算法

， ， ，

(1.北京信息科技大学 计算中心 北京 100192； 2.河南财政金融学院(龙子湖校区)信息技术系 河南 郑州 450014； 3.北京邮电大学 电子工程系 北京 100876)

0 引言

随着移动通信和互联网技术的快速发展，数据信息处理方法变得多种多样，这导致了多种业务类型(如互联网应用服务、云平台租用等)并存的异构通信网络的产生.针对异构网络融合，多是采用在现有互联网架构上进行修补的方式，致使当前互联网变得非常臃肿复杂，为了改善这一现象，网络虚拟化[1]的思路应运而生，其中软件定义网络(software-defined network，SDN)技术的诞生[2]，为网络虚拟化的实施提供了方法.

面向容错的虚拟网络映射是指在发生网络故障时，虚拟网络仍然能够保持正常工作的一种物理网络资源分配方式[3-4].网络故障恢复对于用户来说是透明的，用户感知不到网络资源的切换.可生存性的虚拟网络映射一般采用为节点和链路分配冗余资源的方式来应对网络故障问题，这给网络供应商带来了额外的花销，并且当网络不发生故障时，为虚拟链路提供1∶1的冗余资源无疑是一种巨大的浪费.所以，相对于专用备份，一些备份资源共享的方案被提出.文献[5]提出按需共享和预分配共享两种共享方案，这两种方式均支持用于故障恢复的带宽共享，但是用于业务的主用带宽相互独立.为了提高备份资源的利用率，提高虚拟网络(virtual networks，VN)的接受率，一种支持节点迁移的生存性映射方案被提出.在发生网络单节点故障后，可以将受影响的虚拟节点迁移和映射至备份物理节点，或者各个虚拟节点在VN范围内进行内部迁移，以减少备份带宽，实现VN自身内的带宽资源共享.但是,现在关于无线网络的研究还较少，尤其是视频业务的急剧增加，用户对无线网络的要求越来越高[4]，因此无线网的性能优化问题也亟待解决.文献[5]从应用层面、云层面、频谱层面和合作层面服务于特定的用户，通过业务切片实现无线网络的虚拟化管理.文献[6]对于无线传感网络虚拟化进行了研究，并利用虚拟化技术实现对设备的灵活管理.文献[7]基于5G提出了一种以网络切片管理为核心的管理方案，借助网络功能虚拟化技术实现网络切片创建与修改的完全自动化.文献[8]通过分析无线虚拟网络的相关特性，提出一种针对链路可靠性的映射算法，并且通过引入Q因子解决了因为拓扑分配效率低而造成的虚拟请求接受率低的问题.文献[9]提出了一种改进的基于Q-learning算法的虚拟演进分析核心网的功能部署方法，与传统虚拟化网络功能部署方法相比，该方法在降低网络时延的同时，可提高虚拟化网络功能部署的受益和请求接受率.文献[10]提出了一种在SDN下保证小流时延的QoS机制，降低了小流时延的传输时延.文献[11]设计了一个利用聚类分析算法进行虚拟网络划分的方法，用于提高SDN资源的利用效率.上述文献多数从IP层或应用层对网络性能进行改善，由于多个虚拟网络共享底层设施，随机失效就会导致大量的虚拟网络崩溃，将会使租用虚拟网络的网络服务提供商蒙受巨大经济损失[12-15].

本文给出了一种面向容错的网络虚拟化资源管理与映射算法，首先将无线设备纳入虚拟化架构中，然后基于最小割集理论，在路径选择过程中考虑备用路径，提高映射的可靠性，最后给出仿真结果和分析.

1 虚拟资源抽象模型

1.1 虚拟化网络资源抽象

对于链路资源，主要考虑的是链路上的带宽资源.当有用户发出虚拟请求，只需考虑底层物理链路带宽是否满足请求虚拟带宽.若链路映射支持路径分割，则一条虚拟路径可以映射到两点间的多条路径，只需带宽和满足虚拟请求带宽.链路剩余资源定义为

其中：B和W分别为有线和无线链路带宽资源，当链路为有线时，λ=1，当链路为无线时，λ=0；γ为无线物理链路带宽扩张因子，与该物理链路长度、信道质量有关.

1.2 虚拟网络映射问题描述

本文借助备份路由的思路来分析虚拟映射网络的容错.由于路径选择算法有较高的算法复杂度，在进行故障链路重映射时会有较高的时延，从而造成用户数据的丢失.在虚拟请求到达之前，采用路径选择算法为每一条底层链路计算一组备份路径，可以缩短重映射时延.路径选择算法可以是k条最短路径算法或者是列生成算法和原始对偶方法.本文中采用的是k条最短路径算法.这样，对于每一条底层链路来说，都有一组备份路径相对应，可以用备份链路集来表示.底层链路与备份路径具有相同的起始节点和终止节点，在故障发生时，可以从备份链路集中选择合适的备份链路进行链路重映射.当一个底层链路发生故障时，必须为其选择一条备份路径，该路径与故障链路具有相同的起始节点和终止节点.由于网络的连接性，一条链路l拥有多条可供选择的备份路径x.在底层网络中，跳数每增加一个，将会造成更多的带宽花费和引入更多的时延，所以在本文中将跳数作为衡量备份路径优劣的指标.为了提高备份路由集的质量，将符合跳数标准的路径纳入到备份路由集之中.

定义一个函数P(Gs,l,h)={xhop(x)=h,h≥1},该函数返回与链路l的起始节点相同的跳数为h的路径的集合Px.图1中，P(Gs,AB,2)={ADB,ACB}，链路AB的跳数为2的备份路径的集合为ADB和ACB两条路径.

图1 备份链路Fig.1 Backup chains

另外，定义一个函数Cov(Gs,l,h)，该函数返回链路l的跳数小于等于h的路径的集合Covx，其中h为大于等于1的整数.例如，链路AB跳数大于2的备份路径集合Cov(Gs,AB,2)={AB,ADB,ACB}.那么，如果定义了性能指标h,则满足条件的备份链路集可以表示为C(Gs,l,h)=Cov(Gs,l,h)-P(Gs,l,1).如图1所示，当h=3时，链路AB的备份链路集为Cov(Gs,AB,3),其值为跳数小于等于3的以A和B为节点的路径的集合减去路径AB本身，一共有3组，分别为ACB、ADB和ACDB.当链路AB发生故障时，AB所承载的流量可由3组中的任意一条路径承载.

2 面向容错的虚拟映射算法

2.1 鲁棒性虚拟映射算法描述

当底层链路发生故障时，能否成功进行链路的重映射取决于底层链路备份路由集合的资源状态.如果备份路由集合的路径拥有足够的可用资源，并且处于良好的工作状态，那么当链路发生故障时，重映射成功的概率比较高.如果备份路由集合没有足够的资源为底层链路提供流量的重路由，那么底层链路重映射成功的概率比较低.所以，在进行链路映射时，将关键链路映射至具有良好资源状态的备份路由集的底层链路上，将会提高链路故障的恢复率.针对系统的鲁棒性，具有容错能力的映射过程方法如下.

1) 节点映射阶段

(1)

≥2,

(2)

δ(na,nb)=1.

(3)

式(1)为虚拟节点映射的目标函数，首先根据用户位置选择覆盖范围内若干备选节点，然后根据节点的映射能力为虚拟请求分配最佳节点;式(2)表示物理节点a、b之间的路径数大于1条，即路径ab有备选路径;式(3)表示物理节点a、b属于统一社区.

2) 链路映射阶段

目标函数为

MaximizeR/C.

(4)

约束条件为

(5)

(6)

(7)

(8)

式(4)为虚拟映射的目标函数，该式表示了物理网络接受虚拟请求，并且完成一次虚拟映射时的收益与成本的关系，反映了虚拟映射对于物理资源的使用效率；式(5)为链路带宽资源约束条件；式(6)为连接性约束条件；式(7)表示链路的二进制约束；式(8)为鲁棒性约束，表示该约束下虚拟映射具有鲁棒性.

2.2 依概率选择的鲁棒性提升

定义链路生存概率S(l)来表示如果链路发生故障时，能够通过重映射来恢复的概率.在进行链路映射时，通过计算链路生存概率S(l)来选择生存概率较高的路径，从而提高虚拟网络映射的链路可生存性.S(l)的大小取决于链路l的备份路由集合可承载的流量A(l)与l已承载流量U(l)之间的关系，如果U(l)远远大于A(l)，那么当l发生故障时，其备份路由集可以满足l的重路由需求，即链路生存概率S(l)值较高.A(l)和U(l)的值可由以下公式计算获得,

3 仿真结果

在本节仿真中，对于底层物理网络，我们在25*25的范围内随机生成100个节点，节点的CPU资源和链路的带宽资源都是100到150的均匀分布，每对节点的连接概率是0.3.而相对于虚拟请求，每个虚拟拓扑的节点数量是一个[5,15]的整数均匀分布，它们抵达底层网络的时间间隔服从泊松分布，其均值为每10个单位时间内有一个请求，并且虚拟请求的被服务时间是一个均值为1 000个单位时间的指数分布.对于每一个虚拟请求，它的虚拟节点的CPU资源服从均匀分布，其范围为(0,20],链路也服从均匀分布，范围是(0,50]，并且每两个节点间的连接概率均为0.5.

图2 基于收益成本比的虚拟网络映射Fig.2 Virtual net mapping based on ratio of cost and benefit

如图2所示，收入支出比R/C表示了虚拟请求的收益和成本之比，是虚拟映射算法的重要评价指标.通过仿真可以看出，当请求数目固定的情况下，随着每个请求的节点个数的增多，虚拟网络的收益和成本之比是下降的.网络映射平均数反映了节点压力，拓扑识别有效利用底层网络资源，虽然备用路径的选择增加了物理实体网络的资源耗损，当节点压力增大后，收益和成本之比却没有大幅度增加，且压力越大算法越稳定.由此可以看出鲁棒性映射算法更加高效.

如图3所示，由观测收入支出比R/C可以看出，随着虚拟请求平均节点数目的增加，即虚拟请求规模的增大，改进后的鲁棒性算法与改进前相比，具有更好的资源利用率.在相同的虚拟请求下，鲁棒性虚拟映射算法得出的映射方案占用底层资源更少，意味着其占用的底层链路资源更少，这样当底层链路发生故障时，受影响的虚拟链路会更少，其容错性相比改进前虚拟映射算法也更高.

如图4所示，随着底层物理网络故障率的增大，改进前和改进后收入支出比均在下降，说明随着链路故障增多，底层物理网络节点的连接度越来越小，映射一个虚拟请求需要的底层资源越来越多，因此R/C是呈下降状态.同时从图中可以看出，改进后的鲁棒性算法与改进前相比收入支出比更高，说明鲁棒性虚拟映射算法对故障的容忍度更高，对于网络中的突发故障，具有更高的容错性能.

图3 不同虚拟映射压力下的鲁棒性虚拟映射算法Fig.3 Virtual mapping algorithm of robust in different pressures of virtual mapping

图4 不同容错故障下的鲁棒性虚拟映射算法Fig.4 Virtual mapping algorithm of robust for different fault tolerance

4 结束语

为了提高网络的容错性，本文将连通性作为判定指标，从理论上分析了随机网络下的连通性判定问题，从容错的角度全面分析了虚拟路由通信安全问题.仿真验证表明，在节点压力较大、容错故障率较高的情况下，改进后的算法具有更高的虚拟请求成功率和更低的资源占用率.