一种虚拟化分配资源算法的研究

陈南岳

摘要：互联网技术为人们的日常生活及工作提供了方便，使人们获取信息及交换信息更加方便，在互联网技术不断发展的过程中伴随着一系列的挑战。因为互联网体系结构具有多种缺点，并且由多个运营商同时提供，导致互联网体系结构的改革步伐缓慢，互联网的发展也处于瓶颈时期。要想解决互联网发展瓶颈问题，能够通过网络虚拟化实现，其能够支持多种网络体系结构、业务及实验，网络虚拟化解决的基本问题就是资源分配，能够提高基础设备的使用效率，并且降低资源使用成本，设计基于虚拟化的分配资源算法具有重要的现实意义。

关键词：虚拟化；分配资源；算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）13-0007-03

互联网在信息传播中有着重要的作用，在长时间的发展过程中，其已经被广泛应用到社会各行各业中。但是由于互联网的规模不断扩大，用户的数量也在不断的上升，其缺点也越来越突出。在物联网及云计算等全新的技术出现之后，互联网架构的发展也受到了阻碍，比如传统IP网络的可扩展性较差，全新的技术无法在目前网络结构中部署。为了能够创建全新的网络架构，网络虚拟化技术就产生了，其能够有效提高资源的使用效率，所以也称为下代网络发展的主要技术。

1浅析资源分配

1.1资源分配的概念

网络虚拟化包括两种方式，分别为纵向和横向。纵向虚拟化主要是将一个物理设备虚拟成为多个不同的小设备，每个小设备能够独立使用物理资源，彼此不影响；横向虚拟化主要是多个物理设备相互联合虚拟成为一个大设备，其能够调度内部的物理设备。这两种方式的关键问题就是资源分配，如果分配资源算法优秀，那么能够有效提高物理资源的使用效率及网络性能，还能够降低资源分配的成本，提高网络的收益。

要想使虚拟网络能够使用一个底层物理资源，就要通过资源的分配进行，也就是通过先进的资源映射算法实现虚拟资源到物力资源的映射。资源映射指的是虚拟服务供应商从基础设备供应商中得到有效资源创建虚拟网络的过程。虚拟化的资源分配主要包括资源抽象、资源发现、资源映射及协调管理，详见图1。

1.2资源分配的目的及特点

资源分配的主要目的是能够降低物理资源使用率，并且提高虚拟网络请求。简单来说，也就是实现降低物理资源使用的同时，提供给众多虚拟网络服务。目前，在网络虚拟化中，资源分配是重要的问题，其能够满足虚拟请求及物理资源映射，也是供应商和用户的桥梁，其主要特点包括：

其一，虚拟网络请求的差异化。不同虚拟网络请求具有不同的服务特点，那么网络结构及协议也不同；

其二，异构网络技术共存。网络虚拟化为不同的网络架构和技术提供了共存平台，所以其能够支持不同网络架构及技术，提高网络的整体灵活性及可用性；

其三，物理资源的共享。网络虚拟化中的虚拟网络都是一起使用底层物理资源，资源的分配不仅要最小化物理资源，还要使虚拟请求最大化。

2基于虚拟化的资源分配

2.1虚拟化的资源分配

虚拟化的资源分配指的是InPs在接受SPS服务请求Reg之后创建的虚拟网络拓扑结构及资源约束条件，在InPs物理网络中选择科学的虚拟资源创建虚拟网络，此过程就是虚拟化资源分配。详见图2：

其中式（1）表示为InPs的物理网络，V^S为物理节点的集合，E^S为物理链路的集合，R^S_n（i）为在t时间中，物理节点空间的资源，R^S_l（t为在t時间中，物理链路的空闲资源。其中式（2）表示为在i次Req请求时候创建的虚拟网络，Vv（i）为虚拟网络的节点集合，Ev（i）为虚拟网络的链路集合，Rvn（i）为虚拟节点的资源需求总和，Rvl（i）为虚拟链路的资源需求总和。资源分配的整个过程从形式方面分析，可以分为两个过程，分别为虚拟链路资源及虚拟节点资源两种分配。在实际的资源分配过程中，这两种分配过程并不是相互独立的，如果使整个资源分配问题分为节点资源及链路资源两种分配，进行先后的解决，得到的结果并不是最优的。

2.2资源分配的典型算法

2.2.1集中式资源分配

集中式资源分配的算法是对虚拟网络初始资源分配之后的生命周期中，不对分配资源进行改变，其主要特点就是配置一次，能够终身使用。如果虚拟网络资源的需求发生变化，其分配的资源不会发生变化。如果初始资源分配较多的话，会导致出现资源浪费，相反，就会对虚拟网络的使用产生影响。所以初始资源的分配要以虚拟网络资源的需求为基础。

链路及节点协调的资源分配的算法指的是以InPs分配给SPS虚拟网络的成本为基础，创建资源分配目标函数，之后对物理网络进行拓展，从而改变资源分配，使其成为混合整数规划。由于混合整数规划的计算较为复杂，所以对整数并没有较大的约束，以此可以使用确定四舍五入及随机四舍五入的技术。

但是此算法具有多种问题：首先，在算法平衡的过程中，还提高了资源分配成本；其次，因为算法中的多商品流算法执行了两次，那么算法时间较长。

2.2.2分布式资源分配

分布式虚拟化资源分配算法能够实现分布资源分配通信协议，此算法能够通过相关的通信协议使其中的物理节点实现资源信息的交互及分配，通过资源信息的交互，物理节点能够有效掌握其他节点的没有用的空间信息，从而决定自身的分配任务。所有物理节点都要实现虚拟网络拓扑的星型分割，资源较大的物理节点要实现分割的资源分配，并且将结果通过通信协议为其他物理节点所告知，以此使所有物理节点都能够掌握资源的使用及分配的进度。

3启发式的虚拟化分配资源算法

为了能够有效解决网络资源分配的负载及算法效率问题，本文就提出了启发式的虚拟化分配资源算法——HVNE，此算法通过虚拟节点和链路的桥梁——虚拟网络拓扑（VN），能够统一节点及链路的映射过程，有效完善了映射算法性能较差的问题。另外，其还能够使同个虚拟请求的多个节点在同个物理节点中映射，有效节约了物理链路资源。虚拟化分配资源算法其实就是传统拓扑分割及无向图K区域划分两者的理论结合，从而提出了虚拟拓扑的关联因子，有效完善了传统的星型分割，使其能够满足现代网络的需求。

3.1启发式虚拟化分配资源的网络模型

3.1.1物理网络模型

物理网络的表示为无向带权图G^S=（N^S，L^S），N^S为物理网络节点集合，L^S为物理网络链路集合。在链路分配的过程中，具有一条虚拟链路在多条集合中映射的情况，那么物理节点s到d的路径就通过P^S（s，d）表示，此路径不仅能够作为单一链路，还能够作为多链路集合。

3.1.2虚拟请求网络模型

虚拟请求网络模型和物理网络模型有多种共同点，都是通过无向带权图表示虚拟请求，两者的不同之处在于，虚拟请求网络模型中的虚拟请求只有一个P^V，其表示为虚拟请求分配影响物理网络负载的情况。因为虚拟请求具有不同的特点，网络延迟较为敏感，所以就能够调整P^V，以此能够对虚拟节点和物理节点映射的密度进行改变，从而节省网络宽带，有效提高了网络的使用效率。

3.1.3网络资源的分配流程

在某个虚拟请求到达的时候，物理网络就要决定是否接受，如果接受，那么物理网络就要从节点和链路中选择满足虚拟请求的路径和节点，在虚拟请求消失的时候，其占据的资源就会释放。

3.1.4网络能力因子

通过虚拟请求的特有属性PV限制网络负载，使网络负载能够平衡，并且提高资源的使用效率，所以要设计网络能力因子表示节点和链路之间的关系。

首先，节点资源能力和能力率。节点资源能力指的是物理节点的剩余计算能力，也就是节点的能力因子，公式（5）能够表示。节点资源的能利率为节点资源能力及物理节点资源能力的最大比值，其能够反映出节点资源能力的所有排名，公式（61能够表示，其中0≤Radio^Cpt（n^S）≤1。

（5）

（6）

其次，节点通信能力及通信率。因为虚拟节点映射到节点中的时候，物理节点会和其中的物理节点连接，那么节点的通信能力值得就是节点相互连接的物理链路能够使用的宽带和，表示了节点的通信能力，公式（7）能够表示。

（7）

最后，路径能力。路径能力指的是物理路径的能力，通过路径能力和跳数的结合组成，能够通过公式（8）表示。（8）

3.2启发式虚拟化分配资源的算法

3.2.1启发式虚拟化分配资源的算法

启发式虚拟化分配资源的算法一共有八个步骤，图3为启发式虚拟化分配资源的算法流程。

（1）在虚拟请求到达的时候，物理网络要检查是否具有满足虚拟请求的链路和节点资源。如果满足，那么就接受虚拟请求，进行下一个步骤；如果不满足，就要将虚拟请求当人到队列的末尾，等待其他资源；

（2）生成虚拟请求已经映射的节点列表NodeList及路径分类列表PathList，使其能够存储已经映射的虚拟节点和链路之间的最短路径；根据虚拟请求的节点需求能力，实现虚拟请求的降序排列，以此得到VnNodeList，寻找能够被节点使用的资源比节点需求要大的物理节点，以此形成能够使用的物理节点列表，之后降序排列；在VnNodeLise中设置虚拟节点序号（i=-[i﹤number]），进入下一个步骤；

（3）根据步骤2得到的分配节点序号i的邻居节点列表及映射节点列表和路径分裂列表的交际，得出i的邻居节点列表MapedNeighborNodeList，如果其不是空集，那么就能够根据MapedNeighborNodeList生成需求的映射链路列表，根据映射链路列表的宽带需求，实现MapedNeighborNodeList的降序排序，设置分配节点序号i的邻居节点序号（j=0[i﹤number]），进入下一个步骤；否则，就要对物理节点序号进行设置（k=0[k﹤num-ber]），进入第七个步骤；

（4）判断i的映射物理节点（map（i））是否能够承载i，如果能承载，就进入下一步；如果不能承载，就要使i=j+1；

（5）判断i在map（i）映射的前后负载及网络复杂的差异是否比虚拟资源的PV要大，如果大于，那么就是j=j+1，返回上一步；如果不大于，就进入的下一步；

（6）通过k最短路径算法，判断map（i）链路资源是否能够承载链路映射列表中的链路，如果可以，那么就使i映射到map（i）中，得到链路映射列表中链路的映射路径，存人到路径分类列表中；如果不能，就使j=i+1，返回到第四个步骤；

（7）求出物理节点的综合能力，判断其是否为最大的，如果是，那么就要将i映射到物理节点中，更新物理节点列表，通过k最短路径算法，得到链路映射列表的最短路径，进人下一步；否则就要使物理节点（k）=k+1；

（8）通过链路映射列表，在路径分类列表中找到相應的映射路径，实现链路的映射。之后使i=i+1，判断i能够成为虚拟节点的最后，如果是，那么虚拟资源的映射就是成功的；如果不是，就要返回第三个步骤。

4结束语

资源的分配是网络虚拟化要面临的重要任务，资源分配的有效性关乎到物理网络的负载是否均衡，是否能够有效提高物理网络资源的使用效率，并且还能够提高物理网络中虚拟网络的数量，降低了资源实用的成本。基于此，本文就主要研究了网络虚拟化资源分配的问题，并且介绍了资源分配的典型算法，最后提出了一种启发式虚拟化分配资源的算法，并且对其进行了模型创建及描述，使其能够有效处理网络中的故障问题，保持网络运行的稳定性。