基于资源区域聚集度的虚拟网映射算法

毛宇星 郭云飞 王志明 扈红超



基于资源区域聚集度的虚拟网映射算法

毛宇星*①郭云飞②王志明②扈红超②

①(解放军理工大学指挥信息系统学院 南京 210007)②(国家数字交换系统工程技术研究中心 郑州 450002)

虚拟网映射是网络虚拟化研究中亟待解决的问题，针对已有映射算法中存在的对于网络拓扑信息利用不足的现状，该文提出了基于资源区域聚集度的虚拟网映射算法(RCI-VNE)。在映射预处理阶段，根据局部拓扑信息和区域资源聚集度提出节点区域资源聚集评价算法。在节点映射阶段，提出一种基于节点区域资源聚集排名的2-近邻聚集映射算法，该算法将虚拟网节点集中映射到底层网络中可用资源丰富的区域，减小承载链路的长度。实验结果表明，该算法降低了虚拟网映射开销，且具有较高的虚拟网请求接受率和较低的平均执行时间。

网络虚拟化；网络虚拟化映射；拓扑信息；区域资源聚集指数

1 引言

网络僵化问题[1]是当前互联网发展所面临的一个巨大挑战，网络虚拟化技术[2]由于能够有效地解决互联网在技术创新上面临的瓶颈而受到了学术界和产业界的广泛关注。网络虚拟化是指通过虚拟化技术在共同的底层物理设施上同时运行多个虚拟网，不同的虚拟网使用不同的路由策略和网络协议。单个虚拟网络是根据需求由一组虚拟节点和虚拟链路连接而成的一个服务切面，虚拟网映射主要完成如何将这些虚拟节点和虚拟链路对应匹配到底层物理网络中的节点和链路上的任务，是网络虚拟化研究的关键内容。

由于存在多个目标和约束，虚拟网映射问题已经被证明为NP-hard[3]问题，通常使用基于启发式算法的方法求解，如文献[4]提出的节点/链路负载均衡的启发式算法，文献[5]提出的基于链路可分割的多商品流映射算法，文献[6]提出了一种分布式的虚拟网映射算法，底层网络节点之间传递资源信息并将虚拟网分为若干星型拓扑结构。上述算法将虚拟网映射问题分成节点映射和链路映射两个阶段，各个阶段分别依据自身的目标函数和约束条件进行求解。文献[7,8]使用整数规划方法将节点映射和链路映射统一进行求解，在节点映射阶段就考虑了负载均衡和最大化映射利润，但是该方法在本质上仍然是两阶段的映射方法。两阶段映射算法的优点在于缩小了解空间，能够获得较快的执行速度，但算法的成功率和对底层网络的资源利用情况还有待提高。文献[9]提出了一种基于子图同型检测的一阶段虚拟网映射算法，该算法使用回溯机制统一进行节点和链路映射。一阶段方法在整个解空间进行搜索，能够取得较好的映射方案，但是也造成了算法复杂度高、执行速度慢的问题。文献[10]提出了一种支持接入控制的虚拟网映射近似算法，能够提高物理网资源的负载均衡度和利用率。文献[11]提出了一种基于人工鱼群的网络虚拟化映射算法，该算法根据虚拟网络请求与底层网络节点和链路之间的约束关系建立二进制组合优化模型，能够有效降低底层网络的开销和求解时间。文献[12]研究了分布式环境下的虚拟网映射方法，提出了基于多节点协商的映射机制，实验表明该算法能够降低资源和通信开销。

为了在映射方案的效果和算法复杂度之间取得平衡，近年来的研究倾向于在节点映射阶段就考虑链路映射的限制条件，利用节点的拓扑信息将虚拟网请求映射到底层网络中可用资源丰富的位置，提高映射的成功率和底层网络资源的利用率。文献[13~17]利用节点在网络中位置的全局拓扑信息设计虚拟网映射算法，在一定程度上避免了上述问题，但仍然存在以下不足：(1)评价节点重要性时依赖全局信息，增加了算法的复杂度，并且忽视了被评价节点附近其他节点之间的连接关系对该节点重要性造成的影响；(2)没有设计将虚拟节点集中映射到底层网络某个区域的机制，承载物理节点的间距无法控制，增加映射开销。

为了解决上述问题，本文首先提出一种基于局部拓扑信息和区域资源聚集度的节点区域资源聚集评价算法，该算法根据目标节点与其两层邻居的可用资源数量以及该区域节点之间连接的紧密程度对目标节点的重要性进行评价。其次，本文提出基于节点区域资源聚集排名的2-近邻聚集虚拟网映射算法RCI-VNE，该算法将虚拟网节点集中映射到底层网络中可用资源数量较多的区域，降低了虚拟网映射开销，且具有较高的虚拟网请求接受率和较低的平均执行时间。

2 问题分析

2.1网络模型

虚拟网映射问题的网络模型如图1所示。

图1 虚拟网映射模型解析

3 基于节点区域资源聚集度的虚拟网映射

3.1 节点区域资源聚集程度评价方法

在复杂网络中为了衡量节点的重要性，需要对节点的拓扑信息加以考虑。文献[18]提出了一种利用半局部信息的节点重要性排序方法，该方法利用节点二阶邻居信息对节点的重要性进行评价，并指出该方法的时间复杂度随网络规模线性增长，实验显示，该方法能够取得优于PageRank和LeaderRank算法的结果。但是该算法只考虑了节点之间链路的权值，没有对节点本身的可用资源数量进行评价，无法直接应用在虚拟网映射问题上。本文对该方法进行改进，考虑了节点本身的可用资源数量，提出了节点区域资源因子。

定义1 节点区域资源因子：

节点的聚集因子[19]反映了节点与其邻居以及邻居节点之间连接的紧密程度，该因子越大则节点与周围的邻居以及邻居之间的连接越紧密，越小则连接越疏松。

定义2 节点区域聚集因子：

本文将节点区域资源因子与节点区域聚集因子相结合，提出了评价节点所在区域资源聚集程度的节点区域资源聚集指数。

定义3 节点区域资源聚集指数：

计算节点区域资源聚集指数的具体算法如表1所示，算法的复杂度为，其中为网络拓扑中节点的个数，为网络拓扑中节点的平均度数。

3.2 2-近邻聚集节点映射算法

为了充分利用底层物理网络中的CPU资源和带宽资源，本文提出了基于节点区域资源聚集指数的2-近邻聚集节点映射算法，该算法的特点是：(1)将对资源要求高的虚拟节点映射到区域资源聚集指数高的物理节点上，尽量提高节点映射和链路映射阶段的成功率。(2)将虚拟网请求映射在底层网络中资源聚集度高的区域，减少承载虚拟链路的物理链路的长度，降低映射开销。算法的基本思路为：将虚拟网请求中的节点和底层网络中的节点分别按照其节点区域资源聚集指数降序排列；将排名靠前的虚拟网请求节点映射到能够承载该节点且排名靠前的底层网络节点上；将映射成功的虚拟网请求节点的两层邻居节点映射到承载的物理节点的两层邻居节点中满足其资源约束的节点上。算法的具体流程如表2所示。

表1节点区域资源聚集指数算法

算法1 NRCI(Node Regional Resource Clustering Index)算法 输入：网络拓扑。 输出：节点区域资源聚集指数向量R。 (1);(2) for each do(3) ;(4) for each do(5) ;(6) for each do(7) if k==i(8) continue;(9) end if(10) ;(11) end for(12) ;(13) ;(14) end for

表2基于区域资源聚集度的虚拟网映射算法

算法2 RCI-VNE(Virtual Network Embedding algorithm based on Resource Clustering Index)算法 输入：。输出：节点映射方案。(1) 将虚拟网请求和底层网络中的节点列表和分别按照 其区域资源聚集指数分别降序排列； (2) 将中所有节点置为没有映射，中所有节点置为没有 承载；(3) while 存在没有映射成功的节点do(4) vNode中区域资源聚集指数最高的节点 (5) for each (6) if sNode已经承载了虚拟节点；(7) continue;(8) end if(9) else if (10) continue;(11) else(12) 将vNode映射到sNode上；(13) 设置vNode为已映射；设置sNode为已承 载；(14) Map_neighbour(vNode, sNode);(15) 将vNode节点从未映射成功的节点队列中 删除；(16) end if(17) end for(18) if vNode没有映射成功(19) return false;(20) end if(21) end while(22) return true

子程序Map_neighbour( )负责将映射成功的虚拟网请求节点的两层邻居节点映射在承载该虚拟网节点的底层网络节点的两层邻居节点上，映射方案见表3。该节点映射算法的时间复杂度为。

在链路映射阶段，如果底层网络的支持链路分割，就使用多商品流算法将虚拟网请求链路映射到底层网络的链路上。如果底层网络不支持链路分割则使用K-最短路径算法进行映射。K-最短路径算法和多商品流问题的时间复杂度在多项式时间之内。所以整个虚拟网映射算法的时间复杂度在多项式时间之内。

表3子程序Map_neighbour映射方案

PROCEDURE Map_neighbour(vNode, sNode):(1)unMapListvNode未映射的邻居节点列表；unUseList sNode未承载邻居节点列表；(2) for each (3) for each (4) if (5) 将vNei映射到sNei上；(6) 将vNei设置为已映射；将sNei.used设置为已承载；(7) 在unMapList上删除vNei；(8) 在unUseLists上删除Nei；(9) end if(10) end for(11) end for

4 实验评估

4.1 实验环境

本文实验使用配置为3.10 GHz Intel Core i7- 4600的计算平台，利用C++编程仿真虚拟网映射请求的到达和离开以及虚拟网映射过程。本文使用GT-ITM拓扑生成器[20]构建底层网络和虚拟请求拓扑。为了方便实验对比，与现有的文献[15,16]类似，本文实验生成具有100个节点的底层网络拓扑结构和2000个虚拟网请求。底层网络的节点CPU资源和链路带宽资源的取值服从[50,100]内的均匀分布，底层网络节点的连接概率为0.2。虚拟网请求的节点个数服从[2,20]内的均匀分布，虚拟网请求的节点连接概率为0.5。虚拟网请求的节点和链路资源取值在[0,50]内服从均匀分布。虚拟网请求的到达过程服从到达率为平均100个时间单位到达4个请求的泊松过程，生命周期服从期望为1000个时间单位的指数分布。此外，设置RCI-VNE算法中的参数为0.8,-最短路径算法中的为10。

4.2 评价指标

与现有文献[14~16]类似，本文使用如下4个评价指标对本文提出的映射算法以及现有的映射算法进行评价。

(1)虚拟网请求接受率：该指标用来衡量在给定的时间间隔之内底层物理网络接受的虚拟网请求占全部到达虚拟网请求的比例。

(2)底层网络的长期平均收益：该指标衡量了虚拟网映射算法给底层网络带来的长期平均收益情况。

(3)长期利润成本比：该指标用于衡量映射算法产生单位利润所花费的资源开销。

(4)映射算法平均执行时间：该指标衡量了映射算法执行的平均时间。

本文使用上述指标比较了本文提出的RCI- VNE算法和现有的其他5种虚拟网映射算法(GRC- VNE[13], R-ViNE-SP[7], VNE-B[9], Hybrid-VNE[15], G-SP[4])的性能。

图2所示为不同虚拟网映射算法的接受率，从图2中可以看出，在映射开始阶段由于底层物理网络可用资源较为充足，各个映射算法都有着较高的请求接受率。随着时间的推移，各个映射算法的接受率不断下降，平最终达到稳定。其中RCI-VNE算法的接受率最高，稳定接受率保持在54.19%, GRC-VNE, VNE-B, R-ViNE-SP, Hybrid-VNE算法的稳定接受率分别保持在47.23%, 39.74%, 33.13%和23.09%, G-SP算法的接受率最低，稳定接受率保持在18.35%。该指标主要与底层网络的资源使用情况有关。实验结果显示，本文提出的RCI- VNE算法和文献[13]提出的GRC-VNE算法能够较好的在物理网络和虚拟网请求中对节点的资源情况进行评价，GRC-VNE算法在评价某个节点的资源能力时考虑了整个物理网络中的节点信息，忽略了底层网络拓扑远大于虚拟网请求拓扑的事实，使得算法的针对性下降，而且该算法在节点映射时没有考虑到承载节点之间的距离，这也造成对底层网络资源的过度使用。Hybrid-VNE算法将虚拟网请求中的节点进行了K-core分解，考虑了节点的拓扑属性，但是没有考虑到底层网络中节点的可用资源情况，其他算法都没有考虑节点的拓扑属性。

图3，图4所示分别是不同虚拟网映射算法的长期平均收益和利润成本比，由于本文提出的映射算法在节点映射阶段将节点集中映射在物理网络中可用集中的区域，使得承载虚拟链路的物理链路的距离更短，降低了承载虚拟网请求的开销，获得比其他算法更高的利润成本比。其他算法在节点映射时基本都只考虑了底层网络节点的资源丰富程度，这就造成了承载节点之间的距离可能很大，导致较高的链路映射开销。从图3和图4可以看出，本文算法在这两项指标上都有优于其他算法的表现。

图2 虚拟网请求接受率

图5所示为本文进行比较的虚拟网映射算法在同一仿真环境下映射2000个虚拟网请求的算法平均执行时间和标准差。从图中可以看出本文提出的RCI-VNE算法在评价节点的承载能力时，只依赖于被评价节点两层邻居的信息，能够获得比依赖于全局拓扑信息的GRC-VNE映射算法更短的执行时间。VNE-B映射算法由于将节点映射和链路映射结合起来，需要的回溯操作较多，算法的执行时间相对较长。

由实验结果可知，本文提出的基于节点区域资源聚集指数的RCI-VNE虚拟网映射算法在上述3个评价指标上具有明显优势，能够有效地提高虚拟网请求接受率和利润成本比，并最终提高底层网络的长期平均收益。

5 结束语

本文基于复杂网络中节点重要性排名的半局部中心拓扑属性和区域聚集因子提出了节点区域资源聚集指数，该指数能够评价以节点为中心的两层邻居范围内的可用节点资源以及该范围内节点之间可用链路资源的水平，并基于该指数提出了RCI-VNE虚拟网映射算法，该算法将虚拟网请求集中映射到底层网络中区域可用资源丰富的位置，有效地提高了虚拟网请求的接受率和利润成本比，最终提高底层网络的长期平均收益。此外与基于节点全局拓扑属性的算法相比，该算法具有更低的时间复杂度和平均映射时间。

图3 长期平均利润 图4 利润成本比

图5 虚拟网映射算法平均执行时间和标准差

[1] Turner J S and Taylor D. Diversifying the Internet[C]. Proceedings of IEEE Conference on Global Telecommunications, St. Louis, 2005: 755-760.

[2] Anderson T, Peterson L, Shenker S,.. Overcoming the Internet impasse through virtualization[J]., 2005, 38(4): 34-41.

[3] Andersen D G. Theoretical Approaches to Node Assignment [M]. New York: Computer Science Department, 2002: 86-123.

[4] Zhang Y, Ammar M,.. Algorithm for assigning substrate network resources to virtual network components[C]. Proceedings of IEEE INFOCOM, Barcelona, 2006: 1-12.

[5] Yu M, Yi Y, Rexford J,.. Rethinking virtual network embedding: substrate support for path splitting and migration[J]., 2008, 38(2): 17-29.

[6] Houidi I, Louati W,.. A distributed virtual network mapping algorithm[C]. IEEE International Conference on Communication, Beijing, 2008: 5634-5640.

[7] Chowdhury M, Rahman M,.. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping[J]./, 2012, 20(1): 206-219.

[8] Melo M, Sargento S, Killat U,.. Optimal virtual network embedding: node-link formulation[J]., 2013, 10(4): 356-368.

[9] Lischka J, Karl H,.. A virtual network mapping algorithm based on subgraph isomorphism detection[C]. Proceedings of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures, Barcelona, 2009: 81-88.

[10] 余建军, 吴春明. 支持接入控制的虚拟网映射近似算法[J]. 电子与信息学报, 2014, 36(5): 1235-1241.

Yu Jian-jun and Wu Chun-ming. Virtual network mapping approximation algorithm with admission control[J].&, 2014, 36(5):1235-1241.

[11] 朱强, 王慧强, 等. VNE-AFS: 基于人工鱼群的网络虚拟化映射算法[J]. 通信学报, 2012, 33(Z1): 170-177.

Zhu Q, Wang Hui-qiang,.. VNE-AFS: virtual network embedding based on artificial fish swarm[J]., 2012, 33(Z1): 170-177.

[12] 江逸茗, 兰巨龙, 程东年, 等. 分布式环境中基于协商的虚拟网映射算法[J]. 通信学报, 2014, 35(12): 62-69.

Jiang Yi-ming, Lan Ju-long, Cheng Dong-nian,.. Virtual network embedding algorithm based on negotiation in distributed environment[J]., 2014, 35(12): 62-69.

[13] Gong L, Wen Y, Zhu Z,.. Toward profit-seeking virtual network embedding algorithm via global resource capacity[C]. Proceedings of IEEE INFOCOM, Toronto, 2014: 1-9.

[14] Cui H, Gao W, Liu J,.. A virtual network embedding algorithm based on virtual topology connection feature[C]. IEEE 16th International Symposium on Wireless Personal Multimedia Communications, Atlantic City, 2013: 1-5.

[15] Qing S, Liao J, Zhu X,.. Hybrid virtual network embedding with K-core decomposition and time-oriented priority[C]. IEEE International Conference on Communications, Ottawa, Canada, 2012: 2695-2699.

[16] Huang T, Liu J, Chen J,.. A topology-cognitive algorithm framework for virtual network embedding problem [J].,, 2014, 11(4): 73-84.

[17] Cui H, Tang S, Huang X,.. A novel method of virtual network embedding based on topology convergence-degree[C]. IEEE International Conference on Communications Workshops, Budapest, 2013: 246-250.

[18] Chen D, Lü L, Shang M S,.. Identifying influential nodes in complex networks[J]., 2012, 391(4): 1777-1787.

[19] Fagiolo G. Clustering in complex directed networks[J]., 2007, 76(2): 470-475.

[20] Zegura E, Calvert K, and Bhattacharjee S. How to model an Internetwork[C]. Proceedings of IEEE INFOCOM, Philadelphia, 1996: 594-602.

Virtual Network Embedding Algorithm Based on Regional Resource Clustering Index

Mao Yu-xing①Guo Yun-fei②Wang Zhi-ming②Hu Hong-chao②

①(,,210007,)②(&,450002,)

Virtual network embedding is a critical issue in network virtualization. To overcome the ignorance of network local topology information in existing literatures, a Virtual Network Embedding (VNE) algorithm based on regional Resource Clustering Index (RCI-VNE), is proposed. In embedding preprocessing stage, a node regional resource clustering index evaluation algorithm is proposed, which considers local topology information and resource aggregation extent. In node embedding stage, a 2-adjacent aggregation node embedding algorithm based on the regional resource clustering index is also proposed. The algorithm embeds virtual nodes intensively to the location of abundant resources in substrate network and decreases embedding cost. Simulation results show that the algorithm improves virtual network request acceptance ratio, long-time average revenue and benefit-cost ratio compared with the existing embedding algorithms.

Network Virtualization; Virtualization Network Embedding (VNE); Topology Information; Regional Resource Clustering Index (RCI)

TP393.4

A

1009-5896(2015)10-2405-06

10.11999/JEIT150278

2015-03-09；改回日期：2015-06-16；

2015-07-27

毛宇星 myx_lgdx@163.com

国家自然科学基金(61309020)，国家973计划项目(2012CB315901, 2012CB315905)和国家863计划项目(2011AA 01A103)

The National Natural Science Foundation of China (61309020); The National 973 Program of China (2012CB 315901, 2012CB315905); The National 863 Program of China (2011AA01A103)

毛宇星： 男，1989年生，博士生，研究方向为宽带信息网络.

郭云飞： 男，1963年生，博士，教授，博士生导师，研究方向为下一代网络.

王志明： 男，1986年生，博士生，研究方向为下一代网络.

扈红超： 男，1982年生，博士，研究方向为高性能路由交换技术.