网络虚拟化技术^[1]是解决当前互联网结构僵化问题^[2]的新型网络技术能支持多个异构的网络架构共享物理基础设施，从而构建出多个不同需求的虚拟网络(VN, virtual network)^[3]. VN具有差别较大的生命周期，当VN请求离开时，物理网络负载分布会发生较大改变.当新的VN请求到达时，底层物理网络负载分布不均将会使某些节点或链路成为瓶颈，降低后续VN请求的接受率，因此，需要应用VNR机制实现虚拟节点和虚拟链路的迁移，均衡物理网络负载分布，提高VN请求接受率.

文献[4-5]提出了周期性选择关键VN进行重配置的方法.文献[6]周期性地计算整个网络资源的占用情况，通过制定的协议实现资源之间的动态调整，需要引入新的控制协议并且实现方法非常复杂.然而上述方法都存在以下2个缺陷：① 依据物理节点的资源使用量是否超出一定的阈值，判断其为物理资源瓶颈节点；② 在确定某物理节点为资源瓶颈节点后，将其上的所有虚拟节点均迁移到目标物理节点，造成底层网络其他节点的负载不均衡，导致目标物理节点成为新的瓶颈节点，出现“跷跷板”现象.最终导致VN请求接受率降低、物理网络资源利用率降低，VNR开销增大.

为了解决上述问题，笔者提出一种基于最小代价的VNR方法(LC-VNR，least cost virtual network reconfiguration).该方法首先定义重配置改善度参数判断网络重配置机制的效果；其次提出重配置节点查找方法，确定需要迁移的虚拟节点所在物理节点；然后以基于最小代价为约束条件选择目标物理节点；最后将虚拟节点迁移到目标物理节点上，实现VNR机制.本文将所提方法LC-VNR与文献[4]所提的VNR方法进行对比，实验结果表明所提出的LC-VNR使得物理网络负载分布更均衡，比VNR方法拥有更高的资源利用率和VN请求接受率，且随着VN请求的增加，重配置开销相对更小.

跷跷板是一种两人或两人以上参与的游戏，游戏双方分别坐在跷跷板的两端，一方上去，一方下来.在VNR过程中，将某个物理资源瓶颈节点上的虚拟节点迁移到目标物理节点上，造成目标节点成为新的资源瓶颈节点的现象称为“跷跷板”现象. “跷跷板”现象并不能改善物理网络负载分布不均的现象，也不能减少物理网络中的瓶颈节点数，从而造成VNR失效，增加VNR开销.

使用无向带权图G^S=(N^S, E^S)表示物理网络，其中：N^S为物理节点集合，E^S为物理链路集合.用c_Ni^S表示物理节点的CPU计算能力资源，b_Ei^S表示物理链路的带宽.

使用无向带权图G^V=(N^V, E^V)表示VN，其中N^V为虚拟节点集合，E^V为虚拟链路集合.用c_Ni^V表示虚拟节点的CPU资源请求，b_Ei^V表示虚拟链路的带宽资源请求.

1) 物理节点的剩余资源定义为

(1)

其中N_u^V↑N_i^S表示将虚拟节点N_u^V映射到物理节点N_i^S上.

2) 物理节点的平均剩余资源定义为：

(2)

3) 资源差值定义为单个物理节点剩余资源与平均剩余资源的差值，即

(3)

4) 资源绝对差值定义为单个物理节点剩余资源与平均剩余资源绝对的差值：

(4)

5) 重配置物理节点集合为

(5)

6) 重映射虚拟节点集合为

(6)

7) 目标物理节点集合为

(7)

LC-VNR方法的目标是以最小的VNR开销(用重映射虚拟节点数表示)，实现物理网络资源分布均衡.其需通过以下几点实现：

1) 均衡考虑整体网络查找需重配置的物理节点；

2) 在重配置的物理节点之上通过虚拟节点重映射方法选择出需要重配置的虚拟节点；

3) 在虚拟节点重映射过程中，定义重配置改善度参数δ，衡量该动作对物理网络资源分布不均现象的改善程度. δ表示为

(8)

其中：节点N_i^S是重映射虚拟节点在重映射之前所映射的物理节点，节点N_j^S是某个备选目标物理节点，|D_N(N_i^S)|+|D_N(N_j^S)|表示重配置之前物理节点N_i^S的资源绝对差值和物理节点N_j^S资源绝对差值的和；表示如果将物理节点N_i^S上的所有需要重映射的虚拟节点重映射后，且将当前虚拟节点映射在物理节点N_j^S上后，物理节点N_i^S的资源绝对差值和物理节点N_j^S资源绝对差值的和.重配置改善度参数δ的值越小，表明本次重配置结果越有利于网络资源的均衡分布；相反，δ的值越大表明重配置的结果越不理想.

笔者以最小代价为约束，通过重配置物理节点查找方法、重映射虚拟节点查找方法、虚拟节点重映射方法，实现虚拟节点的重映射，再应用最短路径方法计算物理路径，将虚拟链路映射到物理路径上，实现VNR，其流程如下：

1) 启动资源重配置方法;

2)

3)

由2.2可知，首先判定算法的启动时刻.本文通过历史经验数据选择固定的时间间隔来启动.

基于网络负载均衡，通过遍历所有物理节点，选择需要重配置的物理节点，基于以下3个条件：

1) 剩余资源小于平均剩余资源；

2) 剩余资源小于一定比例的资源总量；

3) 该物理节点资源与平均剩余资源的绝对差值大于一定比例的资源总量.

算法流程如下：

① 计算网络中所有物理节点的D_N(N_i^S)和；

其中：α为剩余资源比例参数，β称为资源差值比例参数.在实际方法运行过程中，α、β是一个设定的常量，一般可取在10%~30%的范围内.

③ 得到需要重配置的物理节点集合A^S.

重映射虚拟节点查找方法的核心思想是选择尽可能少的虚拟节点进行重映射，且选出的虚拟节点的资源和最为接近该物理节点剩余资源与平均剩余资源的差值，达到改善网络资源分布均衡的效果.

假设映射到物理节点(N_i^S∈N^S)上的虚拟节点有L个，则重映射虚拟节点查找方法的流程如下：

① 对映射在物理节点上虚拟节点占用的资源大小进行排序，得到的结果如下：c_N1^S, c_N2^S, …, c_NL^S.

② for(j=1; j < =L; j++) {

if((1-γ)|D_N(N_i^S)|≤c_Nj^V&&c_Nj^V≤(1+γ)×|D_N(N_i^S)|)

       N^V={N₁^V，…, N_i^V, …，N_L^V}

}

其中γ为设定的冗余常量，表示虚拟节点占用资源和在资源差值的附近，γ的取值范围为0~100%，过大会降低方法的准确性，过小会增加虚拟节点的查找难度，可能会造成方法运行失败，一般取20%.

③ 如果遍历完所有虚拟节点，均不满足条件，表明单个虚拟节点的重配置无法满足网络负载均衡化的要求，需要迁移出多个虚拟节点.为此，从大到小遍历计算每2个虚拟节点占用资源量的和，如果某2个虚拟节点占用资源量的和满足(1-γ)|D_N(N_i^S)|≤∑c_Nj^V(1+γ)|D_N(N_i^S)|，表明这2个虚拟节点即是要重映射的虚拟节点，重配置虚拟节点查找过程结束.如果两个虚拟节点仍无法满足需求，则逐渐遍历更多的虚拟节点，直到找到满足条件的虚拟节点.

④ 得到需要重映射的虚拟节点集合A^V.

选择重映射目标物理节点有以下4个原则：

1) 重映射虚拟节点不能重新映射到原物理节点上.

2) 同一虚拟网络中任意两个虚拟节点不能映射到同一个物理节点上(仿真中的物理节点不考虑虚拟节点之间的通道).

3) 重映射目标物理节点不能是重配置虚拟节点所对应的物理节点.

4) 要防止“跷跷板”现象的发生.

根据原则1) 和2) 得到虚拟节点N_j^S重映射的备选目标物理节点集合B^S.

所提方法的输入包括A^S和A^V.需要重配置的物理节点可能是多个，且每个重配置物理节点上需要重映射的虚拟节点也可能是多个.

所提VN重映射方法流程如下：

① 将集合A^V中所有虚拟节点占用的资源按照从大到小的顺序进行排序;

② 对于A^V集合中的每个虚拟节点A_j^V，其重映射目标物理节点集合包含物理网络中的每个节点，即B^S={B₁^S, B₂^S，…, B_n^S};

③ 根据原则1)，将重映射虚拟节点A_j^V对应的物理节点从集合B^S删除；

④ 根据原则2)，对于重映射虚拟节点A_j^V，需要查找虚拟节点A_j^V所在VN的其他虚拟节点所映射的物理节点，假设其对应的物理节点为N_p^S，N_q^S，则集合B^S也要将元素A_p^S，A_q^S从中删除;

⑤ 根据原则3) 将集合A^S中的所有物理节点从集合B_j^S中删除；

⑥ 根据原则4) 计算该虚拟节点A_j^V与集合B^S中所有元素的δ值；

⑦ 选择δ值最小的一个物理节点作为目的物理节点；

⑧ 当一个虚拟节点重映射完成后，更新网络的资源状态，转到② 继续下一个虚拟节点的映射，直到集合A^V中所有的虚拟节点均重映射完毕.

虚拟节点重映射完成之后，根据虚拟链路在映射了虚拟节点的物理节点之间应用最短路径方法计算最短物理路径，实现虚拟链路重映射，完成VN重映射.

设计离散事件仿真系统，以不同的VN请求间隔时间和持续时间模拟网络负载情况，分析所提方法的性能.

设计50个节点的物理网络拓扑，节点和链路资源服从50单位到100单位的均匀分布；VN请求中虚拟节点的数目服从5~10的均衡分布，节点和链路的请求资源服从0单位到50单位的均匀分布；每对虚拟节点或者物理节点之间是否连接的概率为0.5，VN中仿真过程中产生10⁶次VN请求，保证其中虚拟节点资源请求与虚拟链路资源请求相差3倍以上.离散事件仿真系统中VN请求的时间间隔服从参数为λ的泊松分布，成功映射到物理网络中的虚拟网络请求的持续时间服从参数为μ的负指数分布.

通过VN请求接受率、资源利用率方差、重配置开销比较所提方法LC-VNR与文献[4]所提方法VNR的性能.用NS-VNE表示没有采用资源重配置方法的映射过程，用NS-VNE+LC-VNR表示采用了基于最小代价的虚拟网络重配置方法后的映射过程，用NS-VNE+VNR表示采用文献[4]的资源重配置方法后的映射过程.取α=20%，β=20%，γ=20%，算法启动时刻以接收到100个VN请求为一个时间周期.

1) VN请求接受率分析如图 1所示.

图 1

图 1

图 1 VN请求接受率

从图 1中可以看出，2种不同重配置方法都对虚拟网络请求接受率有一定的提高.随着μ/λ的增大，网络中同时存在的VN的个数也越来越多，尽管VNR有效地避免了瓶颈问题，物理网络也难以容纳更多的VN，因此VN请求接受率也会出现一定程度的下降.由于VNR方法是对负载过大物理节点的所有虚拟节点都进行重映射，故重配置行为有可能造成其他节点的负载过高，因而随着物理网络中接纳的VN越来越多，所提的LC-VNR对VN请求接受率提高的也越多.

2) 物理网络负载分布情况分析如图 2和图 3所示.

图 2

图 2

图 2 物理网络节点利用率方差

图 3

图 3

图 3 物理网络链路利用率方差

应用物理节点平均资源利用率标准方差和物理链路平均资源利用率标准方差描述网络资源分布是否均衡，标准方差越小，表示网络资源分布越均衡.从图 2和图 3中可以看出，由于VNR方法对所有负载大的物理节点上的所有虚拟节点都进行重映射，反而增大了节点和链路利用率的方差；LC-VNR方法考虑到了“跷跷板”现象，从而使物理网络负载分布更加均衡，节点和链路利用率的方差相比较于没有重配置的VN映射和采用VNR方法重配置的VN映射过程都减小了很多.此外，由于链路数量远大于节点数量，链路利用率的标准方差要远大于节点利用率标准方差.

3) VNR方法的开销如图 4所示.

图 4

图 4

图 4 VNR方法的开销

由图 4可以看出，LC-VNR方法下虚拟节点重映射的个数要比VNR方法少很多.尤其是当物理网络中容纳的VN越来越多时，物理网络中负载过大的物理节点也将越来越多，满足重配置要求的物理节点越来越多，VNR方法将这些物理节点上的所有虚拟节点都进行重映射，带来的代价也会增加很多.

为了提高VN请求接受率，减少VNR的开销，提出了LC-VNR方法.首先分析了“跷跷板”现象发生的原因；其次定义了重配置改善度参数，衡量VNR动作的效果；再次以最小代价为约束，提出重配置物理节点查找方法、重映射虚拟节点查找方法和虚拟节点重映射方法，将虚拟节点映射到目标物理节点上；最后应用最短路径方法计算物理路径，将虚拟链路重映射到计算所得物理路径上，实现VNR.仿真实验结果证明，所提方法能够使网络资源分布更均衡，提高虚拟网络请求接受率，减少虚拟网络重配置花销.