基于拓扑结构感知的节点多属性网络映射算法

吴誉兰，舒建文

(1.南昌航空大学科技学院，江西南昌332020；2.南昌航空大学信息工程学院，江西南昌330063)

1 引言

节点多属性网络可以在底层的物理网络内，抽象出多个结构不一致且独立的网络，并且能够加快资源共享的速度[1]。在节点多属性网络内，基础设施供应商主要负责供给可用的物理资源，网络供应商主要负责把资源转化成网络资源，服务商则会通过网络资源为用户提供服务。所有网络资源都会经过多种链路和节点组成[2]。但因为不能无限供应资源，所以，在资源有限的情况下收取更多的网络请求、同时提升资源使用率，成为当前领域内较为热点研究话题。

文献[3]根据业务类型，粗化虚拟网络请求，计算请求优先级，初步确定虚拟网络映射顺序，考虑链路带宽资源需求，根据链路权重获取优先级，计算最佳映射路径。该算法缩短了虚拟网络请求等待时间，但该算法的平均链路映射长度较长。文献[4]通过管理和编排网络功能虚拟化及服务器，构建两级队列动态调度模型，感知并动态调度目前队列积压状态，并使其稳定为较小值，利用Lyapunov随机优化方法，完成映射与时延控制。该算法能够实现最优化资源调度，但网络请求接受率和收益开销较低。

针对上述问题，提出基于拓扑结构感知的节点多属性网络映射算法，通过构建拓扑结构与评价指标，挑选网络映射区域，依靠回溯型算法计算sumTR值，得到备选网络节点集合进行映射，实现节点多属性网络映射。

2 节点多属性网络映射问题描述

2.1 形式化定义

定义3：节点多属性网络映射问题即一种GV至Gs的映射过程，其能够描述成M:GV其中，需要满足与此外，RV与RE分别代表已经将底层资源分配至属性与节点中的数量。

在大多数状态下，节点多属性网络映射问题会通过节点映射节点与链接映射节点来构成。

1)节点映射节点即在满足CPU约束的基础上，把节点属性映射到底层节点中；

2)链路映射阶段即在满足带宽约束的基础上，把链接属性映射到底层路径中。

2.2 解决目标

接收节点多属性网络的GV在时间t的收益能够被拟定成

(1)

式中，CPU(vV)为节点vV需要的CPU，BW(eV)为链路eV需要的带宽[6]。考虑到CPU与带宽在不同应用程序的关键性，因此拟定成一种因子α来调整式(1)，一种节点多属性网络的接收收益能够拟定成

(2)

一种节点多属性网络的GV在时间t的接收代价能够描述成式(3)，其也能够用于拟定分配至底层路径的资源

(3)

网络的长期收益平均值能够拟定成

(4)

(5)

考虑访问控制机制[7]，在底层资源没有被有效地分配至一种新到达的节点多属性网络中时，会拒绝对该网络的访问。所以，拟定网络的接收比例，其能够描述成

(6)

式中，VNS为网络请求被接收的总量，而VN代表达到节点多属性网络的请求数量。

3 基于拓扑结构感知的网络模型与评测指标

3.1 网络模型

节点多属性网络映射过程如图1所示。

图1 节点多属性网络映射过程

在图1中，a，b，c代表属性节点，A，B，C，D，E，F代表物理节点，数字分别表示可用计算资源与节点计算资源，矩形框代表坐标约束，框中的物理节点为可用的映射节点。节点的映射结果为{a→A，b→B，c→F}，链路映射的结果为{(a，b)→(A，B)，(a，c)→(A，D，E，F)}。在节点多属性网络请求在底层物理网络中存在的时间达到Tv时，底层物理网络就会剔除被占用的资源。

3.2 评测指标

节点多属性网络映射评测指标如下所示

1)节点多属性网络的平均链路映射长度，其运算如式(7)所示

(7)

式中，h(ev)代表网络链路映射至物理网络中通过的跳数，|Ev|代表网络链路的总量。

2)节点多属性网络的请求接受率，在T时间中，其运算如式(8)所示

(8)

式中，VNrecv(T)代表实现映射的网络请求总量，VNrecv(T)代表网络请求的总量[8]，δ代表防止分母是0而拟定的无限接近于0的正数。

3)在t时刻，每映射一个网络请求所产生的收益开销能够拟定成

(9)

式中，参数α可以更改节点收益与链路收益权重，其取值是1。

4 节点多属性网络映射算法实现

4.1 挑选资源分配区域

回溯型算法的每次运算即实现一个节点分配资源[9]。第一个节点的宿主物理节点决定了该节点多属性网络在物理网络内的资源分配区域。优先使用资源较为丰富的子区域进行资源分配，可以有效地对物理网络的负载进行平衡，缩减瓶颈节点、链路与局部堵塞的出现[10]。因此，针对所有物理节点，运算以该节点作为中心，以GV平均尺寸的一半作为半径之中所有节点的和与sumTR值，挑选与值最大的物理节点作为第一个节点的宿主物理节点。

4.2 物理节点与网络节点的选择

本文算法中，网络节点的映射顺序与映射坐标对算法运行成功率与映射质量存在较大的干扰。算法每次运算首先获得该次运算的备选网络节点集合，随后从中挑选sumTR值最大的节点进行映射。每次映射的备选网络节点集合能够描述成：

为了提升网络链路的映射质量，对这些预选的物理节点进行排序时，除了需要考虑该节点的资源能力，还需要考虑目前被选取的网络节点存在直接通信关系与已经实现映射的网络节点所映射到的物理节点。拟定一种备选物理节点n，其优先级拟定成

(10)

4.3 节点多属性分析

紧密中心度较高的节点不一定是处于整体网络中心坐标的固定节点，但和网络内其它节点的链接性一定是最好的。链路映射取决于已经部署的物理节点，连接性较高的节点在链路部署的过程中存在更为丰富的选择[12]。所以，在节点映射的阶段，有限映射距离网络中其它节点链接性较好的物理节点，这样挑选的节点间的请求带宽需求会更加容易满足，缩减链路带宽的开销。

物理节点的度值就是节点邻接链路数，其能够描述成

(11)

其中，lS→nS代表物理链路和物理节点的链接，综合考虑物理节点的最短链接尺寸、可用资源与带宽资源的实时拓扑属性，构建物理节点的紧密中心度运算模型

(12)

拟定存在t种物理节点，x代表已经映射的物理节点总量，综合考虑C(nS)，E(nS)，DC(nS)，CC(nS)与已经映射节点的尺寸DI(nS)，其共存在k种评测指标，k=4+x，那么节点多属性评测指标矩阵MPS能够描述成

(13)

4.4 节点多属性网络映射

在对节点多属性分析的基础上，本文通过动态拓扑感知与资源属性组成了节点多属性网络映射方法，该方法能够分成两阶段：链路映射与节点映射。

首先放置网络节点，把该节点按照映射优先级EP(nV)进行排列，挑选出队列首位的节点。把该节点的备用物理节点按映射优先级EP(nS)降序排列。挑选EP(nS)值最大同时满足节点资源需求的底层节点进行部署。

在实现请求中所有节点的部署之后，以链路带宽资源作为权重，使用k-最短路径算法，挑选一条满足虚拟链路带宽，同时跳数最小的物理路径部署虚拟链路，实现链路映射，由此完成基于拓扑结构感知的节点多属性网络映射。

5 仿真分析

为了验证基于拓扑结构感知的节点多属性网络映射算法的有效性，在仿真平台MATLAB下进行对比实验。设置节点个数为200个，运行时间为40s，坐标约束为300、600和900。分别采用文献[3]算法、文献[4]算法和所提算法进行节点多属性网络映射，得到不同方法的平均链路映射长度如表1所示。

表1 不同方法的平均链路映射长度

根据表1中的数据可知，在不同坐标约束下，所提算法的平均链路映射长度均最小，文献[4]算法的平均链路映射长度次之，而文献[3]算法的平均链路映射长度最大，由此可知，所提算法能够有效缩短链路映射长度。

在此基础上对比不同方法的请求接受率结果如图2所示。

图2 不同方法的请求接受率对比结果

通过图2能够看出，当运行时间达到40s时，文献[3]算法的平均请求接受率为87%，文献[4]算法的平均请求接受率为83%，而所提算法的平均请求接受率高达93%。由此可知，所提算法的请求接受率较高，这是因为所提算法采用拓扑结构感知方法，受结构的影响，在选取链接路径时，将已经选取过的路径剔除，以防止路径资源消耗过度，从而有效提高了请求接受率。

进一步验证所提算法与文献[3]算法、文献[4]算法的链路映射收益开销比，对比结果如图3所示。

图3 不同方法的映射收益开销比对比结果

通过图3能够看出，当运行时间达到40s时，文献[3]算法的平均映射收益开销比为0.76，文献[4]算法的平均映射收益开销比为0.65，而所提算法的映射收益开销比为0.87。由此可知，所提算法的链路映射收益开销比相对较高，这是由于拓扑结构感知算法的资源浓度能够综合路径启发信息，以此来选取路径，使得资源的消耗更为均匀，接受资源需求高的网络几率更大，从而提高链路映射收益开销比。

6 结束语

为了提高网络请求接受率和收益开销，缩短平均链路映射长度，提出基于拓扑结构感知的节点多属性网络映射算法，该算法能够有效提高网络请求接受率和收益开销，缩短平均链路映射长度。但该方法通过拓扑结构感知模型依次计算节点与连接消耗大量的时间，导致映射效率下降。因此下一步的研究，在此基础上加以优化，进而提升计算效率。