基于SDN的虚拟网络映射问题研究综述

张 鑫，贾莹莹，王晓璇

(1.南京邮电大学 宽带无线通信与传感器技术教育部重点实验室，江苏 南京 210003；2.江苏省无线通信点实验室，江苏 南京 210003)

基于SDN的虚拟网络映射问题研究综述

张 鑫1,2，贾莹莹1,2，王晓璇1,2

(1.南京邮电大学 宽带无线通信与传感器技术教育部重点实验室，江苏 南京210003；2.江苏省无线通信点实验室，江苏 南京210003)

传统IP网络架构越来越不适应日益增长的网络业务与应用，一种新型的网络架构应运而生，即软件定义网络。它实现数据面和控制面相分离，同时具有集中控制、开放接口、可编程等特性。研究了基于该网络架构的虚拟网络映射问题，即如何将带有约束条件的虚拟网络请求映射到由传统电信商提供的底层物理网络中。首先给出虚拟网络映射问题的定义及目标，然后对现有的多种经典映射算法进行分类，并同时对比与分析，最后在此基础上对未来虚拟网络映射算法提出一些建议与改进思路。

软件定义网络；虚拟网络映射；网络虚拟化；映射算法

0 引言

目前传统互联网的架构难以应对日益复杂和多样的社会发展，尤其是处在大数据和云计算时代，面对各种纷繁的用户需求与业务，现有的网络体系面临着巨大的压力与挑战。针对这种情况，研究学者们提出一种新型的网络架构——软件定义网络(Software Defined Network,SDN)及OpenFlow[1-2]协议，将网络分为基础设施层、控制层、应用层，使得网络扁平化，更好地适应未来网络的发展趋势。由于SDN是将底层数据平面分离出一个逻辑的集中控制平面，而网络虚拟化[3-5]是将物理网络抽象成一个个虚拟网络，两者的相似使得新型网络下的网络虚拟化变得更加灵活高效，可以更好地为用户提供服务与应用。SDN网络架构图如图1所示。

图1 SDN网络架构图

1 虚拟网络映射问题模型

虚拟网络映射问题就是将带有条件约束的虚拟网络映射到底层物理网络中。虚拟网络映射又分为节点映射和链路映射，但因节点资源属性众多，在映射过程中物理网络都要满足，这便成为NP-hard问题。其中映射目标函数的选择、节点与链路的匹配原则都是虚网映射中需要解决的问题。

1.1底层网络

1.2虚拟网络

1.3虚拟网络映射问题描述

MN:∀nv∈Nv,MN(nv)∈NS(C(nv)lt;RN(MN(nv)))

(1)

链路映射可表示为：

ML:对∀lv=(mv,nv)∈Lv,ML(lv)⊆PS(MN(mv),

MN(nv))

constraints:b(lv)≤RL(P),∀P∈ML(lv)

(2)

虚拟网络映射模型如图2所示。

图2 虚拟网络映射模型

1.4虚网映射算法的主要评价标准

虚拟网络映射的主要目标是充分利用物理网络资源，接受更多的虚拟网络请求，提高底层网络的运营收益。评价标准相关函数具体定义如下。

(1)收益函数

所有成功映射的虚拟网络所请求的节点CPU资源和链路带宽资源总和决定虚拟网络收益，t时刻映射一个虚拟网络收益可表示为:

(3)

(2)开销函数

映射开销即底层网络为满足虚网的节点及链路资源约束而消耗的物理资源，可表示为：

(4)

(3)底层网络平均收益函数

(5)

(4)虚拟网络请求接受率函数

虚网请求接受率是指在某个时间段内虚拟网络请求成功映射的个数，定义为：

(6)

其中，式(6)中分子部分表示0～T时刻内成功映射虚拟网络请求个数，式(6)中分母部分表示0～T时刻内虚拟网络请求总个数。

综合以上，选择不同的评价标准会产生不同的结果，在实际问题中要根据不同应用场景，选择合适的度量函数，以求获得最大收益和资源的利用率。

2 虚拟网络映射算法分类

从各种因素考虑，根据资源约束、接入控制、虚网请求处理方式、虚网映射的计算方式、映射类型、拓扑信息等方面比较了最近10年一些经典虚拟网络映射算法[6-12]，如表1所示。

由于受节点CPU、链路带宽条件约束，而且存在虚拟网络请求的时间等是不可知的，因此使得虚拟网络映射研究变得复杂，一些采用忽略节点资源约束、忽略接入控制、假设预先已知虚拟网络请求信息(离线)等限制地址位置的方式寻求虚拟网络映射的解决方案；另一些则从扩大问题空间的角度出发，研究贴近实际生活的映射算法。最终可将已有的虚网映射算法分为两大类：限制地理位置的映射算法[6-7]和不限制地理位置的映射算法[8-12]。

2.1限制地理位置的虚网映射算法

文献[6]在忽略节点资源约束、假设所有的虚网请求事先已知等限制地理位置的条件下，提出了一种QoSMap机制，该机制在建立虚拟网络时着重考虑了虚网的QoS与拓扑弹性问题。通过选择高质量保证的物理链路满足虚网的QoS要求，并利用一跳中继路由节点构建后备路由路径以提供虚拟链路映射的弹性保障。该算法虽能获得更优的服务质量和弹性保证，但其资源利用率低，计算开销大。

表1 虚拟网络映射算法比较

文献[7]在离线且未考虑节点映射阶段，提出将隐藏跳数(虚拟链路映射到的底层路径经过的中间物理节点)纳入到链路映射阶段，链路映射后作为中间节点的物理节点也要消耗CPU资源。算法将虚拟网络请求分成有特定资源请求和无明确资源请求两类，先处理有特定需求的请求，目的是在成功映射每个虚拟网络请求后使得剩余资源尽可能地大(即开销尽可能小)，再处理资源请求不明确的虚拟网络请求，对它们进行资源的平均分配。该算法中间节点的资源消耗更接近实际，但不适合于大规模虚网请求，对于支持链路可分流的情况计算复杂度比较高。

2.2不限制地理位置的虚网映射算法

不限制地理位置的虚网映射算法，又可根据是否考虑拓扑特性，细分为同时考虑拓扑信息的虚网映射算法[10-12]和未考虑拓扑信息的虚网络映射算法[8-9]。

(1)考虑拓扑信息的虚网映射算法

文献[10]从已有的算法平等地对待底层网络的节点和链路资源，实际上这些物理资源中某些资源相比其他的资源更重要，这些关键资源的耗尽会对未来的请求接受率有较大的影响。因此根据物理网络节点和链路的剩余可用容量和在底层网络中的重要程度分配不同的权重，拓扑感知映射在已有算法的成本函数中引入比例因子，对资源进行区分。同时，新的虚拟网络到达和已有的虚拟网络服务终止使得底层网络可用资源的分布变得零散，底层网络资源利用率降低，请求接受率下降。解决方案是引入重优化机制，周期性的重优化机制不适用于实际的网络，文献中提出当有虚拟网络请求被拒绝时执行重优化算法，有效地均衡负载。

文献[11]在节点映射阶段引入网络拓扑属性，即在考虑CPU和带宽的同时考虑节点的度(度是节点最基本和最重要的拓扑属性，可衡量在拓扑结构中节点的相对影响和相对重要性，反映了与网络剩余部分的连接程度，节点的度等于其与邻居节点的直接链路数)以增强节点与其他节点联系能力的影响，从而提高虚拟网络接受率、长期平均收益和底层资源利用率。

文献[12]从马尔可夫随机游动模型出发，利用K-核分解技术将虚拟网络划分为核心网络和边缘网络两大部分，同时优先考虑生存时间最短的虚拟网络请求(区别于以收入为导向的调度策略)。在映射过程中，首先采用RW-MM-SP算法映射核心网络，然后采用RW-BFS算法映射边缘网络，其中核心网络中与边缘网络直接相连的节点称为星节点。

(2)未考虑拓扑信息的虚网映射算法

文献[8]中，在不限制地理位置的条件下，底层物理网络支持路径迁移与路径分裂特性，节点映射按照贪心算法来映射，链路映射采用基于商品流链路映射，从而提高虚拟网络请求接受率，但由于节点属性是节点CPU与邻接链路带宽之和的乘积，容易导致任意一个值的变化，从而导致链路映射失败。

文献[9]中，为应对底层资源浪费大的问题，将虚网的资源请求划分为两部分：基本子请求和可变子请求，提出了一种新的ORS(Opportunistic Resource Sharing)映射框架，包括宏观层面的虚网映射和微观层面的虚网映射。宏观层面的虚网映射，采用传统的贪婪算法，为基本子请求分配固定的专用时隙。微观层面的虚网映射，由于可变子请求以小于1的概率发生，因此共享时隙可节约底层资源，其映射问题即可转化为如何为可变子请求分配底层时隙的问题。文献[9]定义冲突阈值以代表底层时隙的量，继而提出了冲突概率的第一拟合算法(First-Fit by Collision Probability，CFF)和指标和的第一拟合期望算法(First-Fit Expectation of Indicators Sum,EFF)两种共享时隙的映射算法。CFF将可变子请求映射到率先满足冲突概率不大于冲突阈值的底层时隙上，直到分配给可变子请求的时隙数满足要求为止。EFF是对CFF的改进，减少了冲突概率的计算量，比CFF运行得快。

3 虚拟网络映射算法的改进思路与方向

尽管现有的虚拟网络映射算法取得了一些进展与突破，但是仍然面临着以下一些问题：

(1)目前绝大多数映射算法的假设条件都是由单个电信运营商提供底层物理资源，但是在实际应用中会面临着由多个提供商提供的网络，如何在多个底层网络中进行选择和映射，这将是未来研究的重点与热点。

(2)虚拟网络映射过程遇到因某种原因突然出现节点和链路失效，从而使得映射失败，导致虚网映射可靠性降低，例如可以考虑为虚拟网络分配冗余资源，或者为节点、链路建立资源备份池，当该节点或者链路失效时，可以及时切换到其他节点和链路上，确保网络可以继续运行下去。

(3)网络安全也应该成为未来虚拟网络映射潜在的研究点，考虑虚拟网络映射过程中引入身份认证机制，使得虚拟网络变得更加安全与可靠。

(4)同时虚拟网络映射过程中会消耗一定的能量，可以考虑将能耗这一因素纳入映射算法的衡量指标中，使得未来的映射变得更加绿色和节能。

(5)电信运营商为了利益最大化，优先接受收益大的虚网请求，即收益为导向的调度策略，一些虚拟映射算法中采用以时间为导向的调度策略，率先映射生存周期短的虚拟网络，为未来的VNR预留更多的剩余资源，提高了虚网的接受率，进一步增加了收益。因此，从虚拟网络请求排队机制的优先级出发，寻找更高效的虚拟网络映射算法。

4 结论

SDN网络的特性与网络虚拟化技术相契合，为未来网络的发展提供基础，同时也有利于网络技术的革新和用户业务的发展。虚拟网络映射过程中，不仅需要考虑虚拟网络请求的链路带宽和CPU资源的约束，还要考虑传输时延及物理网络中可用资源大小，这是今后研究的重点和难点。本文从限制地理位置与不限制地理位置两个方面对多种虚拟网络映射算法进行了简要分析，并指明了今后进一步的研究发展方向。

[1] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.OpenFlow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008.

[2] CHOWDHURY N M M K, BOUTABA R. Network virtualization: state of the art and research challenges[J]. IEEE Communieations Magazine, 2009, 47(7):20-26.

[3] CHOWDHURY M, BOUTABA R. A survey of network virtualization[J]. Computer Networks, 2010, 54(5):862-876.

[4] 姜明，王保进，吴春明,等.网络虚拟化与虚拟网映射算法研究[J].电子学报,2011,39(6):1315-1320.

[5] 温涛，虞红芳，李乐民.网络虚拟化的过去、现在和未来[J].中兴通讯技术,2014,20(3):2-7.

[6] SHAMSI J, BROCKMEYER M. QoSMap: QoS aware mapping of virtual networks for resiliency and efficiency[A]. Proceedings of the IEEE GLOBECOM Workshop[C]. Washington, DC, USA, 2007: 1-6.

[7] BETORO J F, HEESELBACH X, FISCHER A, et al. Optimal mapping of virtual networks with hidden hops[J]. Telecommunication Systems, 2013, 52(3): 1-10.

[8] Yu Minlan, YI Y, REXFORD J, et al. Rethinking virtual network embedding: substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008,38(2):17-29.

[9] Zhang Sheng, Qian Zhuzhong, Wu Jie, et al. Virtual network embedding with opportunistic resource sharing[C]. IEEE Transactions on Parallel and Distributed Systems, 2014: 816-827.

[10] BUTT N F, CHOWDHURY N M M K, BOUTABA R. Topology awareness and reoptimization mechanism for virtual network embedding[C]. Networking, 2010: 27-39.

[11] Feng Min, Zhang Lei, Zhu Xiaomin, et al. Topology-aware virtual network embedding through the degree[C]. National Doctoral Academic Forum on Information and Communications Technology 2013, IET, 2013: 1-6.

[12] Qing Sude, Liao Jianxin, Wang Jingyu, et al. Hybrid virtual network embedding with K-core decomposition and time-oriented priority[C]. Proceedings of IEEE International Conference on Communications, 2012: 2695-2699.

[13] 桂燕兴，沈苏彬，毛燕琴.基于SDN的虚拟映射技术的研究与实现[J].微型机与应用,2015,34(13):69-76.

2017-05-17)

张鑫(1993-)，通信作者，男，硕士研究生，主要研究方向：软件定义网络与网络虚拟化。E-mail：zhangxin9312@163.com。

贾莹莹(1992-)，女，硕士研究生，主要研究方向：下一代网络、无线传感器网络。

王晓璇(1993-)，女，硕士研究生，主要研究方向：下一代网络、无线传感器网络。

Research on virtual network embedding problems based on SDN

Zhang Xin1,2, Jia Yingying1,2, Wang Xiaoxuan1,2

(1. Key Lab of Broadband Wireless Communication and Sensor Network Technology, Nanjing University of Posts and Telecommunications, Ministry of Education, Nanjing 210003, China; 2. Jiangsu Key Lab of Wireless Communication, Nanjing 210003, China)

Traditional IP network architecture is not adaptive to the increasing number of network services and applications ,and then a new type of network architecture is introduced, which is software defined network. It enables data plane and control plane to separate, and has central control,open interfaces,and programmable features. This paper studies the virtual network embedding problem based on the network architecture, that is, how to map virtual network requests with constraints to the underlying physical network provided by traditional telecommunication operators. Firstly, the definition and goal of the virtual network embedding problem are given. Then, a variety of classical mapping algorithms are classified and compared with each other. Finally, the future virtual network embedding algorithms’ suggestions and improvements are offered.

software defined network; virtual network embedding; network virtualization; mapping algorithm

TP393

A

10.19358/j.issn.1674- 7720.2017.22.004

张鑫，贾莹莹，王晓璇.基于SDN的虚拟网络映射问题研究综述J.微型机与应用，2017,36(22)：11-14.