基于openflow网络的虚拟网络映射研究

徐冬冬,郑淑丽,曹 敏,樊玉琦

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)



基于openflow网络的虚拟网络映射研究

徐冬冬,郑淑丽,曹 敏,樊玉琦

(合肥工业大学 计算机与信息学院,安徽 合肥 230009)

基于多个openflow网络自治域提出各域共同合作完成虚拟网络映射,由于各域公开的信息有限,传统的单域映射方法不适用于虚拟网络跨域映射,文章提出一种竞价机制的跨域虚拟网络映射框架(bidding multi-domain virtual network mapping,B-MDVNM),在框架内针对虚拟节点映射采用启发式均衡算法(balancing heuristic algorithm,BHA),并通过仿真实验和现有的虚拟节点映射算法从效率、开销、性能等方面进行对比来验证BHA的有效性。

虚拟网络;跨域映射;openflow网络域;B-MDVNM框架;BHA算法;有效性

网络虚拟化技术支持多个虚拟网络(virtual network,VN)共享物理网络资源[1],VN映射作为网络虚拟化的关键,其目标是为每个VN中的虚拟节点和虚拟链路在底层网络中寻找满足映射约束的物理节点和物理链路。软件定义网络(software defined network,SDN)是一种新兴的控制与转发分离并直接可编程的网络架构,openflow网络作为SDN的原型被提出主要由openflow交换机和控制器2个部分组成[2]。单个openflow自治域由1个控制器、1个或多个openflow交换机和若干主机组成。控制器承载本域内的控制资源,并且根据VN请求和域内所有的相关资源,设计映射算法提供VN映射结果。openflow交换机承载转发资源,通过运行openflow协议和控制器进行通信。VN请求共享底层网络资源,openflow网络可以对不同的VN请求设计不同的映射算法。由于openflow网络具有强大的可编程能力,VN可以在被映射到的openflow网络域中运行自定义协议(IP或非IP协议)[3]。openflow网络基础设施提供商(infrastructure provider,InP)为VN请求提供所需的资源。目前,对于单一自治域,文献[4-9]对其有研究,上述单域VN映射方案都是需要知道整个网络拓扑结构以及资源、带宽等信息,然而在实际中,由于客观因素的限制(单一InP无法完成的)需要多个InP共同合作才能满足VN映射需求,所以单域VN映射无法适用于跨域映射部署。

目前已有的跨域VN映射方法分为两类：① 分布式。分布式跨域VN映射方法通过VN请求与InP、InP与InP之间的资源协商来实现,需要获取全局网络拓扑结构。优点是满足InP的资源协调,具有良好扩展性。缺点是在协商过程中会引起额外的传输代价和资源消耗,缺乏全局网络信息的掌握,难以得到跨域VN映射最优解。② 集中式。集中式方法[10-13]在VN请求和InP之间引入虚拟网络提供商(virtual network provider,VNP)或者映射管理器作为协调VN请求和InP匹配映射过程,以最小化映射开销为目标求解跨域VN映射。综上所述,集中式方法相对于分布式方法对全局信息掌握相对容易,简化了VN请求和InP之间资源匹配的过程，集中式方法较容易实现。

本文针对跨域映射提出一种集中式的基于竞价机制跨域VN映射框架(B-MDVNM),针对虚拟节点映射提出启发式均衡算法(balancing heuristic algorithmy,BHA),根据算法设计相应的模拟仿真实验，与现有的虚拟节点映射算法从效率、开销、负载等方面进行对比来验证BHA的有效性。

1 基于openflow网络跨域映射模型

VN请求用有权无向图为Gv=(Nv,Lv),Nv表示虚拟节点集合,Lv表示虚拟链路集合。底层openflow网络基础设施由m个openflow网络InP(简称OFInP)提供。图1所示为一个实例,VN请求中,V1,V2,V3∈Nv表示虚拟节点类型,而矩形中的数字表示该虚拟节点所需的资源量,连接两节点的线段为虚拟链路。而底层网络由3个OFInP组成,每个OFInP都有一个控制器(controller),该控制器中记录本域可提供的虚拟节点资源、域内网络拓扑信息等。比如OFInP1中为V1、V2、V3提供的资源量为20、5、5。

根据图1可知，单个OFInP域内虚拟节点资源不足，无法满足VN请求,此时需要多个InP共同提供虚拟资源来为VN请求提供服务。3个域共同参与了VN映射,其中V1映射至OFInP1域内,而V2映射至OFInP2域内,V3映射至OFInP3域内。节点U、V、W、X、Y是每个域的边界节点(border nodes),边界节点属于OFInP的物理节点集合,负责域之间的连接。虚拟网络请求跨域映射过程分为虚拟节点映射和跨域链路映射2个步骤,即两阶段映射[14-15]。当虚拟节点映射完成后,根据链路资源约束进行跨域路径映射,选择合适的跨域路径。由图1可以看出,VN请求链路映射至跨域路径V、X、Y相连的链路。本文主要研究虚拟节点映射过程。

图1 基于openflow网络跨域映射模型

2 基于竞价的跨域VN映射框架

在保护OFInP的内部网络拓扑结构隐私安全的前提上,考虑到决策者需要一定程度的全局视角,在OFInP与VN请求之间加入管理中心(supervisor),B-MDVNM框架如图2所示。

图2 B-MDVNM框架

图2中具体步骤如下:

(1) VN请求发送至信息处理中心,处理中心记录VN请求的节点以及链路信息。

(2) 各个OFInP中的控制器(controller)将本域所能提供的节点资源信息和节点资源单价发送给信息处理中心。例如OFInP1向管理中心递交内容为:可提供虚拟节点V1、V2、V3,资源量分别为20、5、5,资源单价为12。

(3) 处理中心对各OFInP发送的信息和VN请求进行分析制定竞价结果表(bidding results table)。

(4) 管理中心根据算法计算最优虚拟节点映射结果。从图2中可知最优映射结果由3个最优的局部映射结果组成，分别为:V1映射至OFInP1;V2映射至OFInP2;V3映射至OFInP3;而映射的总价格为415。

(5) 将映射结果发送至OFInP,再根据映射结果各OFInP接受VN请求中虚拟节点的映射。

3 启发式均衡算法

3.1 算法步骤

BHA得到的结果是I满足R的最优映射结果(optimal mapping results,MR)。MR由若干个最优的局部映射结果(part of the mapping results,PMR)组成。

输入:I、R。

输出:PMR集合(即MR)。

算法具体步骤如下:

(1) 判断R能否映射至I,判断公式如下:

(1)

若无法满足判断公式则说明当前I中的节点资源无法满足R的节点需求,算法结束；若满足，则R一定可以映射,转步骤(2)。

(2) 设Vf表示已完成映射节点集,Va表示待映射节点集,初始Va=VR,Vf=∅。设k为PMR集合长度,初始k=0。

(3) fori=1 to m，根据R、Ii计算V(Ii,R)，计算公式如下:

(2)

同时记录L(V(Ii,R))并选择该值最大的V(Ii,R)作为本次循环的最优局部映射结果,该公式的策略在于虚拟节点映射至最少的OFInP内,目的是尽可能减少跨域开销,即优先选取可以提供最多类型虚拟节点的OFInP域作为VN请求的映射域。若出现多组L(V(Ii,R))的值相同,则需要比较Ii的均衡系数δ,δ的计算公式为:

(3)

再优先选取δ较大的Ii,k=k+1,并更新PMR集,公式如下:

(4)

(5) 由于R有部分节点被映射需要更新R的节点信息,移除已经被映射的节点。同时更新Ii的资源信息,公式如下:

(5)

(6) 若Vf=VR,Va=∅,则表示R的节点全部完成映射,跳出该循环。若Va≠∅,说明R的节点并未全部映射,回到步骤(3),计算下一个PMRk。

(7) 算法结束,记录映射结果PMR集合,映射工作完成时间为T,I集合中各OFInP的剩余资源以及PMR的长度u=k。

3.2 评价指标

为了提高底层OFInP的资源使用率,尽可能降低映射开销,并且保证各个OFInP的负载均衡,参照文献[1]引入4个性能指标作为参照。

(1) 完成VN请求集的映射的总时间T。

(2) 完成VN请求集的映射的总开销,本文以总的开销报价的形式表示,公式如下:

其中,Bp为跨域开销报价;α、β分别为OFInP的节点资源开销权重和跨域开销权重。

(3) 在相同底层网络资源状况下,高效的映射算法能够接受更多的VN请求,VN请求接受率η定义如下:

(4) 用I的剩余资源和的极差来反映当前底层网络的负载情况,极差τ定义如下:

4 算法仿真

4.1 仿真环境

仿真实验使用配置为3 GB内存,32位Win7操作系统,Intel core2 T9550处理器的计算机进行上述评估,实验代码用C++语言编写,使用Visual Studio 2010进行编程,实验中物理网络及虚拟网络拓扑都采用GT-ITM工具随机生成。

实验的预设变量信息如下:预设整个底层网络由5个不同的OFInP组成,虚拟节点种类设置为s=8,VN请求数设为n=1 000。每个OFInP对于每种虚拟结点提供的资源r服从均匀分布[0,max],资源单价p服从[10,20]的均匀分布,每个OFInP的控制资源信息集中于管理中心形成统一的资源表。VN请求虚拟节点数服从[1,s]上的均匀分布,其中每个节点需求资源r服从[0,20]的均匀分布。节点资源开销权重α和跨域开销权重β均设置为1,跨域开销Bp设置为300。

通过改变max的值,将本文提出的BHA和不加入均衡系数比较的BHA(简称NOBC-BHA)以及二元整数规划求最小节点映射开销算法(binary integer programming minimize node mapping cost,BIP)[12]分别进行节点映射仿真实验,记录评价指标。

4.2 仿真结果及分析

仿真结果如图3～图7所示。

(1) 从图3得到BHA的平均映射时间比BIP低9.3%,比NOBC-BHA低3.7%。由图4可以看出，当max≥7 000时,由于底层网络资源充裕,VN请求映射成功率为100%,而max<7 000时,底层网络资源有限,BHA的映射成功率稍高于NOBC-BHA和BIP。可以看出BHA算法效率明显要高于BIP,稍高于NOBC-BHA。

图3 VN请求平均映射时间

图4 VN请求映射成功率

图5 VN请求总映射价格

图6 OFInP集剩余资源极差

(2) 从图5可以看出BHA的平均映射总价比BIO算法低18.5%,比NOBC-BHA低5.5%。因为BHA要求VN请求映射至最少的OFInP内,可使跨域开销最低,并且引入均衡系数的比较使VN请求映射至价格较低的OFInP内。由图6可以看出，VN请求映射完成后，BHA的底层网络资源极差最低,而BIP会优先使VN请求映射至报价较低的OFInP中,造成低价的OFInP资源消耗较大,负载较高,而报价较高的OFInP会长时间处在空闲状态,产生局部负载偏高的现象。

图7 一个VN请求平均处理时间

(3) 从图7可以看出BHA的算法执行时间低于NOBC-BHA和BIP。这是因为BIP采用了优先选取最低报价的OFInP作为映射目标的策略,所以计算报价的时间开销较大,BIP的一个VN请求平均处理时间为3.74 ms。虽然NOBC-BHA比BHA缺少计算均衡系数这一步骤,但是当底层网络资源不足时需要多次循环计算局部最优映射子集,而BHA只需比较均衡系数即可得到局部最优映射子集。NOBC-BHA的一个VN请求平均处理时间为3.32 ms,而BHA只有3.03 ms。比BIP降低了23.4%,比NOBC-BHA降低了9.6%。

5 结 论

本文对基于openflow网络跨域的虚拟网络映射进行了研究。由于多域环境下各域不公开网络拓扑等详细信息且各域的资源处于动态变化的情况下,针对VN请求跨域映射问题提出一种竞价机制的跨域虚拟网络映射框架,并且在虚拟节点映射问题上提出一种启发式均衡算法。模拟实验结果表明，本文提出的算法在高效快速地满足多域下VN请求可靠需求的同时,仍能达到较低的映射开销和底层网络各域之间的负载均衡。

在完成虚拟节点映射工作后,需在跨域链路上进行跨域链路映射,今后应在现有的工作基础上进一步研究跨域链路映射的问题。

[1] 程祥,张忠宝,苏森,等.虚拟网络映射问题研究综述[J].通信学报,2011,32(10):143-151.

[2] MCKEOWN N,ANDERSON T,BALAKRISHNAN H,et al.Openflow:enabling innovation in campus networks[J].ACM SIGCOMM Computer Communication Review,2008,38(2):69-74.

[3] BAVIER A,FEAMSTER N,HUANG M,et al.In VINI veritas:realistic and controlled network experimentation [C]//Proceedings of the ACM SIGCOMM.Pisa,Italy,2006:3-14.

[4] 李文,吴春明,陈健,等.物理节点可重复映射的虚拟网映射算法[J].电子与信息学报,2011,33(4):908-914.

[5] CHENG X,SU S,ZHANG Z B,et al.Virtual network embedding through topology-aware node ranking[J].ACM SIGCOMM Computer Communication Review,2011,41(2):39-47.

[6] YU M L,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.

[7] CHOWDHURY N M MK,RAHMAN M R,BOUTABA R.Virtual networkembedding with coordinated node and link mapping[C]//2009 IEEE INFOCOM.28th International Conference on Computer Conmunicoations,Rio de Janeiro:IEEE,2009:783-791.

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

[9] 程祥,张忠宝,苏森,等.基于粒子群优化的虚拟网络映射算法[J].电子学报,2011,39(10):2240-2244.

[10] HOUIDI I,LOUATI W,ZEGHLACHE D,et al.Virtual resource description and clustering for virtual network discovery[C]//2009 IEEE International Conference on Commupications Workshops.D resden:IEEE,2009:1-6.

[11] HOUIDI I,LOUATI W,AMEUR W B,et al.Virtual network provisioning across multiple substrate networks[J].Computer Networks,2011,55(4):1011-1023.

[12] DIETRICH D,RIZK A,PAPADIMITRIOU P.Multi-domain virtual network embedding with limited information disclosure[C]//Prceedings of the 2013 IFIP Networking Conference.Brooklyn:IEEE,2013:1-9.

[13] 肖蔼玲,王颖,孟洛明,等.基于知识描述和遗传算法的跨域虚拟网络映射[J].软件学报,2014,25(10):2189-2205.

[14] 徐鹏,李勇,金德鹏.改进的两阶段虚拟网映射算法[J].计算机工程,2012,38(5):79-82.

[15] YU M,YI Y,REXFORD J,et al.Rethinking virtual network embedding:substrate support for path splitti-ng and migration[J].Computer Communication Review,2008,38(2):17-29.

(责任编辑 张 镅)

Multi-domain virtual network mapping based on openflow network

XU Dongdong,ZHENG Shuli,CAO Min,FAN Yuqi

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

In this paper, the multi-domain cooperation to complete the virtual network mapping is put forward based on the multiple openflow network autonomous domain. Because of the limited disclosed information, the traditional single domain mapping method is not applicable to multi-domain virtual network mapping. Therefore, the bidding multi-domain virtual network mapping(B-MDVNM) framework is proposed in which the balancing heuristic algorithm(BHA) is applied for the virtual nodes mapping. Finally, the simulation and the comparison between BHA and the existing virtual nodes mapping algorithm in view of the efficiency, overhead and performance are conducted to verify the effectiveness of the BHA.

virtual network; multi-domain mapping; openflow domain; bidding multi-domain virtual network mapping(B-MDVNM) framework; balancing heuristic algorithm(BHA); effectiveness

2015-05-20；

2015-08-18

安徽省自然科学基金资助项目(1508085MF115)

徐冬冬(1991-),男,安徽合肥人,合肥工业大学硕士生;

郑淑丽(1974-),女,安徽蚌埠人,博士,合肥工业大学副教授,硕士生导师.

10.3969/j.issn.1003-5060.2016.10.011

TP393

A

1003-5060(2016)10-1352-05