2014, Vol. 25
2. 中国西安卫星测控中心 喀什卫星测控站, 新疆 喀什 844000
2. China Xi'an Satellite Control Center, Kashi Satellite Station, Kashi 844000, China
网络虚拟化技术被视为解决网络僵化问题的重要途径[1,2],该技术支持多个虚拟网络(virtual network,简称VN)彼此隔离地共享物理网络资源.利用网络虚拟化技术,服务提供商(service provider,简称SP)可以通过向虚拟网络用户(VN user)提供多样化的网络服务来获得收益,基础设施提供商(infrastructure provider,简称InP)可以通过提高自身的资源利用率来减少运营成本和设备开销.
虚拟网络映射是网络虚拟化的关键,其目标是在物理网络中为VN的虚拟节点和虚拟链路分别找到满足其映射约束的物理节点和物理路径.目前,研究人员已经对单一自治域(单域)场景下的VN映射进行了诸多有益的探索[3, 4, 5, 6, 7, 8, 9],即,在获悉单个自治域内全部物理网络信息的前提下提供VN的映射方案.然而在实际中,由于客观因素的限制(如资源类型、价格等),往往需要多个InP的共同合作来完成VN映射.由于各InP不会公开其内部网络的详细信息,故单域映射方法不适用于VN的跨域部署,于是,学者们开始研究跨域映射问题[10, 11, 12, 13, 14, 15, 16, 17, 18, 19].
已有的跨域VN映射方法可以分为两类:分布式和集中式.
· 分布式的跨域VN映射[13,14]通过SP与InP及InP与InP间的资源协商来实现,能够充分尊重SP和InP双方的意愿且有良好的可扩展性.但分布式方法在协商过程中会引起额外的网络传输代价,又由于缺乏对全局信息的掌握,故并不能得到跨域VN映射的最优解;
· 而集中式方法在SP和InP间引入虚拟网络提供商(virtual network provider,简称VNP)[20],简化了SP与InP的供需匹配过程,并以最小化映射开销为目标为VN求解跨域映射方案.
集中式跨域VN映射包括如下3个阶段:
1) 资源匹配阶段,在收到SP发来的VN请求后,VNP将请求中对虚拟资源的映射约束与各InP公开的物理网络信息进行匹配,得到每个虚拟资源的匹配集合;
2) VN划分阶段,VNP以最小化映射开销为目标,为每个虚拟资源从其匹配集合中选择最适合的映射目标,选择结果会将VN划分为多个虚拟子网,并确定映射每个虚拟子网的InP,至此,跨域VN映射已化归为多个单一自治域场景下的VN映射;
3) 虚拟子网映射阶段,VNP将各虚拟子网请求转发给相应的InP,各InP可采用已有的单域映射方法[3, 4, 5, 6, 7, 8, 9]求解虚拟子网映射.
然而对于跨域映射的前两个阶段,目前的研究还存在一些不足:
· 基于概念群集技术,已有的资源匹配算法[10, 11, 12]按相似性对物理网络可提供的虚拟资源进行分类,生成概念分类树,再利用概念分类树完成资源匹配.虽然这类方法的资源匹配效率较高,但却限制了VN user对映射约束的表达形式,使映射约束只能描述为合取式,而不能表达蕴含、非等较为复杂的语义.另一方面,数值属性在概念群集技术中是按取值区间分类的[21],容易导致资源匹配结果不精确,影响后续VN划分阶段的效率和性能.因此,如何对VN user多样化映射约束的表达及精确数值属性的匹配提供支持,是资源匹配阶段需要解决的问题;
· 对于VN划分问题,Houidi等人[15]第一次从理论上证明了该问题是NP难的,并基于边界节点间全连接的物理网络拓扑提出了VN划分的确切式和启发式算法.Dietrich等人[17]则以InP公开边界节点的相关信息为前提,给出了一种确切式VN划分算法.与Houidi等人的方法相比,该方法虽然建立了更加准确的问题模型且有效减少了跨域VN映射的开销,但却增加了求解VN划分的时间复杂度,使该方法很难完成对较大规模VN划分的计算.因此,如何高效地对VN划分进行近似求解,是一个亟待解决的问题.
本文针对上述集中式跨域VN映射的资源匹配和VN划分两个阶段中存在的问题,分别提供了解决方案.本文的贡献主要包括:
1) 基于OWL知识描述和SWRL查询工具设计了一种资源匹配算法,该算法可支持VN user多样化的映射约束表达以及精确的数值属性匹配,提高了资源匹配过程的实用性;
2) 提出了一种基于遗传算法的VN划分算法.该算法将VN划分方案以矩阵形式编码,从多个初始解开始进行迭代搜索,逐步逼近全局最优解;
3) 设计并实现了本文VN划分算法的仿真实验,从效率、性能和稳定性这3个方面验证了该算法的优势,并总结了算法中参数的设置原则.
本文第1节对跨域VN映射中的资源匹配和VN划分问题进行数学描述.第2节设计资源描述知识库和资源匹配算法.第3节提出基于遗传算法的VN划分算法.第4节通过仿真实验验证本文给出的VN划分算法的有效性.第5节和第6节讨论相关工作并总结全文.
1 问题描述VNP是跨域VN映射的核心角色,其任务是根据VN请求中的映射约束和各InP公开的物理网络信息,将VN划分为多个虚拟子网并指派给相应InP完成映射,故资源匹配和VN划分是VNP的工作重点.本节首先介绍跨域VN映射中VNP可获取的物理网络信息,在此基础上给出资源匹配和VN划分的数学描述.
1.1 VNP可获取的物理网络信息VNP对物理网络信息(substrate network information,简称SNI)的可见度是其进行资源匹配和VN划分的重要依据.实际上,只有得到全部的物理网络信息,VNP才能计算出最优的VN划分方案.考虑到InP不可能公开其全部物理网络信息(网络拓扑及资源),与Dietrich等人[17]相同,本文参考现有云计算平台(如Amazon EC2)中InP公开计算资源信息的方式,假设在网络虚拟化环境下,InP会将其物理资源抽象为多种虚拟资源类型.虚拟资源的属性用二元组(属性名,属性值)表示.所有属性取值都相同的虚拟资源被分为一类,例如,将有相同节点功能、操作系统、虚拟化环境及地理区域的虚拟节点资源视为同一类型的虚拟节点.如图 1所示,InP向VNP公开的是其所在自治域可提供的虚拟资源类型及相应资源类型的价格信息,该信息存放于资源描述知识库(resource description knowledge base)中,用于对资源匹配算法(matching algorithm)及VN划分算法(partitioning algorithm)提供支持.此外,VNP还可以从互联网交换点[22]及peering数据库[23]公开的信息中获取边界节点间的拓扑信息及连接开销信息(P_node information),以支持VN划分算法.
 | Fig. 1 VNP’s working mechanism in multi-domain VN embedding图 1 跨域VN映射中VNP的工作机制 |
需要特别说明的是:在资源匹配算法中,对虚拟节点的匹配,即找到满足其映射约束的虚拟节点类型;对虚拟链路的匹配,则是要找到一条物理路径,使该路径上的每条物理链路都能满足该虚拟链路的映射约束.考虑到在不能掌握全部物理网络信息的条件下,VNP无法对虚拟链路进行有效的匹配,因此,本文的资源匹配主要是对虚拟节点匹配;对虚拟链路的匹配是在生成VN划分方案后,由各虚拟子网的指定InP负责完成.故资源描述知识库中的虚拟资源类型只包括虚拟节点类型,并不涉及虚拟链路类型.
图 1所示中虚线以下的部分展示了VNP可获取的物理网络信息,可以看出,整个物理网络由3个自治域及其相互连接构成.各域内的正方形代表该域可提供的虚拟节点类型,以不同字母区分,正方形上的数字代表该虚拟节点类型的单价.各域内的正五边形代表该域的边界节点,正五边形间的连线表示边界节点间的连接关系,连线上的数字代表相应边界节点间建立连接的单位开销.一个InP可提供多种虚拟节点类型,一种虚拟节点类型可由多个InP提供,如InP1可提供的虚拟节点类型有a,b,f,其中,a还可由InP2提供.对于同一虚拟节点类型,各InP可有不同报价,如对虚拟节点类型a,InP1和InP2的单价分别是5和6.同域的不同边界节点有不同的域间连接和连接开销,如InP1的p1可与InP3连接且单价为9,p2可与InP2连接且单价为10.
1.2 资源匹配的问题描述如图 1所示,资源匹配是指VNP根据VN请求中对虚拟节点的映射约束(mapping constraint)及资源描述知识库中的信息,通过一定的资源匹配算法得到每个虚拟节点的可映射范围,即,可提供满足映射约束的虚拟节点类型的InP集合,称该集合为匹配集(match set).
将各InP能够提供的所有虚拟节点类型记为全集U,虚拟节点类型的全部属性记为集合A,其中的每种属性AiÎA可以有不同的取值Aij,其取值集合记为V(Ai)={Ai1,Ai2,…}.虚拟节点类型TÎU的属性Ai的取值记为Value(T,Ai).根据Ai取值的不同对U进行划分,可以得到多个子集Uij:
Uij={T|Value(T,Ai)=Aij,TÎU}.
虚拟节点v的映射约束mcv可表达为一个由非、合取、析取、蕴含及等价符号连接的逻辑表达式,其中的每个原子式是虚拟资源类型的一种属性,故由上式可将每个原子式对应到一个Uij.考虑到逻辑运算中的交、并、补分别对应集合运算中的合取、析取、非,而蕴含和等价则可通过非、合取、析取的转换得到,故可将mcv的逻辑表达式看作对多个Uij进行一系列的交、并、补,其运算结果Uv中的每个元素都满足mcv:
Uv={T|satisfy(T,mcv),TÎU}.
将物理网络中全部InP组成的集合记为INP,InPiÎINP可提供的全部虚拟节点类型组成的集合记为PVT(InPi),则虚拟节点v的匹配集可表示为
MatchSet(v)={InPi|PVT(InPi)ÇUv¹Æ,InPiÎINP}.
1.3 虚拟网络划分的问题描述如图 1所示,VN划分是指VNP以降低跨域VN映射的开销为目标,根据资源匹配得到的匹配集、资源描述知识库中虚拟资源类型的价格信息以及边界节点的相关信息,将VN请求划分为多个虚拟子网,形成VN的划分方案(partition scheme).
跨域VN映射的开销(cost)由3部分组成:节点映射开销(NODEcost)、域间链路映射开销(LINKcost)和域内链路映射开销.其中,域内链路映射开销依赖于InP内部具体的网络信息.由于在实际中InP不会完全公开其网络信息,且域内链路映射开销远小于域间链路映射开销[17],故本文在计算跨域VN映射开销时忽略了域内链路开销,即:Cost=NODEcost+LINKcost.
由第1.1节可知:当一个自治域中的虚拟节点与另一个自治域中的虚拟节点间需要建立虚拟链路时,选择不同的边界节点会产生不同的LINKcost.因此,VN划分方案中不仅要为每个虚拟节点指明承担其映射的InP,还要指明通过相应InP中的哪个边界节点完成域间连接.本文将虚拟节点v的匹配集MatchSet(v)扩展为由该集合中的InP包含的所有边界节点组成的集合MatchSet¢(v).需要说明的是,边界节点并不承担具体的虚拟节点映射.本文在提到将一个虚拟节点映射到一个边界节点上时,指的是在VN划分阶段,将该虚拟节点划分到该边界节点所在的InP,后续虚拟节点映射由该InP完成,且相关虚拟链路映射要使用该边界节点与其他InP建立连接.
将边界节点组成的物理网络抽象表示为一个有权无向图,记为GS=(NS,ES),其中,NS为边界节点集合,ES为边界节点间的物理链路组成的集合.对连接边界节点u,v的物理链路lS(u,v)ÎES,其单位开销用cost(lS)表示.同样地,将虚拟网络请求表示为一个有权无向图,记为GV=(NV,EV),其中,NV为虚拟节点集合,EV为虚拟链路集合.虚拟节点nvÎNV的节点能力约束用c(nv)表示.对连接虚拟节点m,n的虚拟链路lv(m,n)ÎEV,其带宽约束用bw(lv)表示.VN划分可理解为以最小化跨域VN映射开销为目标,找到以下两个映射:
其中,Path(i¢,j¢)示GS中边界节点i¢和j¢之间的无环路径组成的集合.fn表示虚拟节点映射,即把虚拟节点映射到其匹配集中的某个边界节点上;fl表示虚拟链路映射,即:当VN中虚拟链路lv(i,j)的两个端点i,j分别映射到边界节点i¢,j¢上时,为完成VN划分,lv(i,j)必须映射到Path(i¢,j¢)中的路径上.
2 资源描述知识库及资源匹配算法作为VN划分的必要准备,资源匹配的结果必须精确,从而为VN划分提供可靠依据,以提高VN划分的效率和性能.本节首先用OWL语言[24]为物理网络提供的虚拟资源创建资源描述知识库,再利用SWRL[25]查询语言规范VN user的映射约束,最后利用SWRL查询工具实现资源匹配算法.
2.1 资源描述知识库由前一节的分析可知:在网络虚拟化环境下,对虚拟资源的描述可由虚拟资源的类型和属性来表达.这是一种典型的“概念-属性”知识描述体系,故可用OWL语言为其创建相应的资源描述知识库.本节先给出资源描述知识库的概念模型,包括概念关系(如图 2所示)和属性层次结构(如图 3所示),再基于概念模型创建资源描述知识库的具体内容.
 | Fig. 2 Concept relationship of resource description knowledge base图 2 资源描述知识库的概念关系 |
 | Fig. 3 Attribute hierarchical structure of resource description knowledge base图 3 资源描述知识库的属性层次结构 |
如图 2所示,概念模型中的概念关系可描述为:一个InP可提供多种虚拟节点类型(virtual node type),一种虚拟节点类型也可由多个InP提供.一种虚拟节点类型可有多个可枚举属性(eAttribute)和多个数值属性(nAttribute).可枚举属性对应可枚举的概念,可被泛化为多个子概念,用于表示具体的可枚举属性;数值属性对应于一个具体数值,采用Double表示.图 2给出了3种常见的可枚举概念:节点功能类型(function type)、操作系统类型(OS type)和虚拟化环境类型(VE type).另外,概念模型中还有一个特殊概念称为候选集(candidate set),这是一个临时保存资源匹配结果的变量,一个候选集可包含多个InP.
概念模型中的属性层次结构如图 3所示,其中,可枚举属性(eAttribute)被泛化为3种:节点功能类型(functionType)、操作系统类型(osType)和虚拟化环境类型(veType).数值属性(nAttribute)被泛化为6种:节点最大能力(maxCap,可用主频、内存大小等指标衡量)、节点可靠性(reliability,可用平均故障恢复时间、平均无故障时间等指标衡量)和4个用于表达节点地理位置的属性,包括最大经度(maxLon)、最小经度(minLon)、最大纬度(maxLat)和最小纬度(minLat).
图 3中还给出了每个属性的定义域(domain)和值域(range),具体含义参见文献[24].
图 2和图 3的灰色部分是可配置的,即,VNP可根据需要对概念或属性进行添加或删除操作.其中,Enumeration泛化出的子概念应与eAttribute泛化出的子属性一一对应,即,子属性的值域应指向对应的子概念.由于Double无需泛化,故由nAttribute泛化出的子属性的值域均指向Double.应该明确的是:概念模型是资源匹配的基础,VN user要根据概念模型来表达映射约束,InP要根据概念模型来发布物理网络信息.
进一步地,基于上述概念模型来创建资源描述知识库的具体内容.在跨域VN映射中,知识库的创建过程即InP将可提供的虚拟节点类型以实例的形式发布到知识库中,并创建各实例间属性关系的过程.对创建好的知识库可进行两类修改:VNP对概念模型的修改和InP对知识的修改.对概念模型的修改必须通知所有InP和VN user,修改代价较大,应尽量避免;对知识的修改仅涉及提出修改的InP和VNP,对其他InP和所有VN user都是透明的,修改代价较小,InP可根据自身情况较为自由地修改已发布的虚拟节点类型信息.
图 4给出了一个资源描述知识库的例子,该知识库包含1个可枚举属性和4个表示地理位置信息的数值属性.图 4的左侧部分展示了各InP间的连接关系以及各InP可提供的虚拟节点类型,右侧部分以表格的形式给出了各虚拟节点类型的属性值.
 | Fig. 4 An example of resource description knowledge base图 4 一个资源描述知识库的例子 |
若要利用上述资源描述知识库进行资源匹配,必须对VN user提出的映射约束加以规范.本节采用SWRL查询语言规范VN user对映射约束的表达形式.表 1给出了本节使用的SWRL内置函数.
|
Table 1 Built-In functions of SWRL 表 1 SWRL的内置函数 |
这里结合图 4中的资源描述知识库,给出一个用SWRL查询语言规范映射约束的例子.VN user的映射约束为“某虚拟节点N的操作系统类型是Mac或Linux,且N的最大经度小于125,最小纬度大于20”.为增强该映射约束的可读性,将其分为3部分:
· stm1:osType(?b,Mac)|osType(?b,Linux)
· stm2:lessThan(maxLon(?b),125)&greaterThan(minLat(?b),20)
· stm3:InP(?a)&VirtualNodeType(?b)&provide(?a,?b)&(stm1&stm2)=>Candidate Set(?a)
其中,stm1描述了N对操作系统类型的约束,stm2描述了N对地理位置的约束.将stm1和stm2带入stm3可以得到N的完整映射约束.stm3可直观地理解为:若a是一个InP,b是N请求的一种虚拟节点类型,且a可以提供b,同时b能够满足stm1和stm2的约束,则a属于N的候选集Candidate Set(N).调用SWRL查询工具可得到最终的匹配结果:Candidate Set(N)={InP2,InP4,InP5}.
2.2.2 资源匹配算法流程如图 5所示,资源匹配算法的输入是VN请求中指定的一组映射约束,每个映射约束对应VN请求中的一个虚拟节点,输出是各虚拟节点的匹配集.算法共包括4步:第1步,从输入的映射约束中读取虚拟节点i的映射约束(i=1,2,…,m,m为VN请求中虚拟节点数目);第2步,调用SWRL查询工具,在资源描述知识库的支持下对虚拟节点i的映射约束进行匹配,将满足条件的InP放入候选集(candidate set)中;第3步,将候选集中的元素放入虚拟节点i的匹配集中;第4步,置空候选集.以上4步循环执行,直到将所有映射约束处理完毕.候选集用于临时保存资源匹配结果,初始时应置为空集.
 | Fig. 5 Algorithm flow for resource matching图 5 资源匹配算法的流程 |
本节基于OWL语言为物理网络提供的虚拟资源创建了资源描述知识库,并利用SWRL工具设计了资源匹配算法.其中,资源描述知识库的概念模型规定了映射约束中可以使用的术语,SWRL查询语言明确了映射约束的逻辑形式.相比于已有算法,本节的资源匹配算法支持VN user在概念模型和SWRL查询语言规范的范围内表达多样化的映射约束,且无需对映射约束进行逻辑范式转化即可完成匹配.此外,本节算法还能支持精确的数值属性匹配,避免了采用概念群集技术带来的数值属性模糊匹配问题.
理论上,本节算法的时间复杂度为O(n)(n为各InP可提供的虚拟节点类型总数),高于Houidi等人[10]算法的时间复杂度O(lgn).但一方面,SWRL查询工具优化了算法的查询部分,故实践中其复杂度接近O(lgn),若能利用缓存中常用映射约束的匹配结果,则还可进一步提高算法效率;另一方面,后续VN划分问题属于NP问题,其时间消耗远大于资源匹配阶段,故从跨域VN映射的整体过程来看,资源匹配阶段并非影响全局效率的瓶颈.综上,本节资源匹配算法的效率是可以接受的.
3 基于遗传算法的虚拟网络划分算法本节首先给出基于遗传算法的VN划分算法(GA-partition)的变量定义和目标函数的计算方法,然后介绍算法流程和3种遗传算子,最后证明算法的两个重要性质.
3.1 变量定义及目标函数将VN请求的每一个可行划分方案表示为一个矩阵PMmxn,其中,m为VN请求中虚拟节点的数目,n为物理网络中边界节点的数目.元素PM[i][j]的取值代表虚拟节点i与边界节点j之间的映射关系.
· PM[i][j]=1,表示jÎMatchSet¢(i)且fn(i)=j;
· PM[i][j]=0,表示jÎMatchSet¢(i)但fn(i)¹j;
· PM[i][j]=-1,表示jÏMatchSet¢(i).
因此,对于特定的PM矩阵,有唯一的划分方案与之对应.
同时,一个合法的PM矩阵必须满足以下条件:
1) 若jÎMatchSet¢(i),则PM[i][j]=1或PM[i][j]=0;
2) 若jÏMatchSet¢(i),则PM[i][j]=-1;
3) PM的每一行有且仅有一个元素可被赋值为1(每个虚拟节点都将映射到唯一的边界节点上).
对于特定的虚拟网络和物理网络,在完成资源匹配后,便确定了PM矩阵中值为-1的元素,其他元素则暂时赋0.对于一个划分方案,若fn(i)=j,则将PM[i][j]的值由0改为1,故划分方案也对应唯一的PM矩阵.综上,合法的PM矩阵与可行的VN划分方案一一对应.又由于PM矩阵的构建过程即遗传算法的编码过程,故该过程满足完备性、健全性和非冗余性[26].以图 1中的VN划分方案为例,该方案可矩阵表示为表 2的形式.
|
|
Table 2 VN partition scheme expressed as a matrix 表 2 VN划分方案的矩阵表示 |
VN划分的求解目标是找到使映射开销最小的VN划分方案,其目标函数f可表示为
Min:f(PMmxn,TMmxm,CAP1xm,VNCmxn,PMCnxn).
f中5个参数的具体含义如下:
1) PMmxn:虚拟节点与边界节点的映射关系矩阵;
2) TMmxn:VN请求的流量矩阵,TM[i][j]表示虚拟节点i与虚拟节点j之间的带宽约束,参见文献[17,27];
3) CAP1xm:虚拟节点的能力约束矩阵,存放VN请求中所有虚拟节点的节点能力约束;
4) VNCmxn:虚拟节点映射的最小单位开销矩阵.令InPj表示边界节点j所属的InP,若InPjÎMatchSet(i),则InPj可提供至少一个满足i映射约束的虚拟节点类型,VNC[i][j]取这些虚拟节点类型的单位开销的最小值.若InPjÏMatchSet(i),则VNC[i][j]取无穷大;
5) PMCnxn:边界节点间连接的最小单位开销矩阵.PMC[i][j]取边界节点i,j间所有路径的单位开销的最小值,可由弗洛伊德算法计算得到.同时,弗洛伊德算法还能得到任意两个边界节点间单位开销最小的路径,可用于提供虚拟链路的域间映射方案.
为便于表示,在介绍目标函数的计算方法之前,先定义运算符“Ä”:
节点映射开销可表示为
,其中,
即虚拟节点i映射到相应边界节点的单位开销.域间链路映射开销可表示为
,其中,
若fn(i)=i,则k=i¢时,PM[i][k]=1,PM[i][k]Äk=i¢;否则,PM[i][k]Äk=0. 故u=i¢,表示虚拟节点i映射到的边界节点.同理,v表示虚拟节点j映射到的边界节点.计算可得,图 1中VN划分方案的NODEcost和LINKcost分别为89和53,故Cost为142.
首先,依据遗传算法相关文献[26,28],解释遗传算法中几个重要概念在本文中的含义:
· 个体:一个可行的VN划分方案(一个PM矩阵)称为一个个体;
· 基因:一个虚拟节点称为一个基因;
· 基因性状:一个虚拟节点与全部边界节点的映射关系(PM矩阵中的一行)称为该基因的性状;
· 种群:由一组个体形成的集合称为种群.
GA-partition算法流程如下:
1. 随机生成一组个体,由这组个体形成一个种群,记为PM_SET;
2. 对PM_SET中的个体两两进行交叉运算,并将得到的新个体加入PM_SET,对其扩充;
3. 对扩充后PM_SET中的个体进行变异运算;
4. 对PM_SET中的个体进行选择运算,淘汰一部分个体;
5. 评估PM_SET,看其是否满足算法终止条件:若满足,则算法终止,输出PM_SET中令目标函数最优的解,并结合弗洛伊德算法得到的单位开销最小的路径形成划分方案;若不满足,则跳至步骤2.
GA-partition算法的终止条件如下:
算法的终止由迭代次数k来控制.在一次迭代完成后,对当前迭代次数i进行判断:若i小于k,则算法继续;若i大于或等于k,则取出前k次迭代中每次迭代的最优解,形成最优解集合s={si-k+1,si-k+2,…,si}.若k次迭代中第1次迭代的最优解与s中的最优解相等,即si-k+1=min(s),则表明算法经k-1次迭代后未找到比si-k+1更优的解,算法终止;若si-k+1>min(s),则表明算法在k-1次迭代内找到了比si-k+1更优的解,算法继续执行.
3.2.2 GA-partition算法的3种算子1. 交叉算子
交叉运算的目的是由两个个体PM1(父亲)和PM2(母亲)得到一个新个体PM3(孩子),让PM3既具备PM1的基因性状,也具备PM2的基因性状.交叉运算的操作可以描述为:将PM1和PM2的基因进行随机分割,并分别选择部分基因性状遗传给PM3,具体的公式表达如下:
对m个基因,随机生成一个全排列,记为cj(j=1,2,…,m):
1) 若m是奇数,则变异操作为
2) 若m是偶数,则变异操作为
2. 选择算子
选择运算的目的是基于种群中个体适应度及淘汰概率的定义,淘汰种群中适应度较低的个体.本文采用基于排序的方法来定义适应度函数,即PM_SET中所有个体的目标函数按降序排列,将每个个体的适应度s定义为该个体在序列中的位置.淘汰概率函数P(s)是适应度的函数.参考遗传算法的相关文献[26,28],本文设计淘汰概率的原则主要有:
1) 保证适应度最高的个体不被淘汰;
2) 适应度高的个体被淘汰的概率小;
3) 种群数目保持稳定(保证算法在执行过程中不会因为种群数目增加而降低搜索效率,也不会因为种群数目减少而降低优化程度).
基于以上原则,将P(s)定义为
其中,k为种群数目(k>1),N为自然数.P(s)可以满足:
1) P(k)=0,保证适应度最高的个体不被淘汰;
2) P(s)为单调递减函数,使适应度高的个体被淘汰的概率小;
3) 设x为经选择运算后种群中被淘汰个体的数目,则x的期望可以表示为
即,选择运算可淘汰1/3的个体.考虑到每两个个体的交叉运算可生成一个新个体,故经交叉运算后种群数目会变为原来的3/2.故,本文对P(s)的定义可使种群数目保持稳定.
3. 变异算子
变异运算的目的是扩大GA-partition算法的搜索范围,以避免算法过早陷入局部最优.变异运算由变异概率p控制,其操作可描述为随机选择个体的一个基因,并随机生成一个新的基因性状替代原基因性状.对种群中适应度最高的个体不进行变异运算.
3.3 算法性质证明性质1. GA-partition算法是可以终止的.
证明:采用反证法证明.设算法不可终止,即,算法会一直迭代下去.考虑经过第i次迭代后算法没有终止,则由第3.2.1节中算法的终止条件可知,si-k+1>min(si-k+1,si-k+2,…,si),设min(si-k+1,si-k+2,…,si)=sj,i-k+2≤j≤i.又由算法不可终止可知,算法在第j+k-1次迭代后也不会终止,因此,同样有s(j)>min(sj,sj+1,…,sj+k-1),此时,又可以找到一个比s(j)更优的解.以此类推,由于迭代一直进行,可以找到无数个可行解,而可行解的数量是有限的,故矛盾.
性质2. GA-partition算法的搜索空间包含整个解空间.
证明:性质2即证在不考虑变异的情况下,任意给定初始种群,解空间中的任意个体都能以一定概率被搜索到.以下证明中的“可以”均是概率意义上的.
假设虚拟节点数目为i,且i为奇数(偶数同理).对任意的可行解s,s有i个基因及相应的基因性状.从任意初始种群开始,交叉运算可生成s的第1个基因性状,下次交叉运算又可以在保留s第1个基因性状的基础上生成s的第2个基因性状.以此类推,可以搜索到可行解s1,s1具有s的第1至第(i-1)/2个性状.同理,可以搜索到可行解s2,s2具有s的第(i+1)/2至第i-1个基因性状.此时,可以将s1和s2进行交叉运算,保留s中的前i-1个基因性状,并生成s中第i个基因性状.得证.
4 仿真实验本节仿真实验的目的包括如下3个方面:
1) 将本文提出的基于遗传算法的VN划分算法(GA-partition)与Dietrich等人[17]的基于边界节点信息的确切式VN划分算法(LID-partition)以及Houidi等人[15]的不公开边界节点信息的确切式VN划分算法(NID-partition)和其启发式算法(NID-partition-h)在效率(算法执行时间)和性能(解的最优性)上进行比较;
2) 在不同的物理网络拓扑下分析GA-partition的稳定性;
3) 分析GA-partition中3个重要参数(即迭代次数、种群数目、变异概率)对算法效率和性能的影响,并讨论参数的设置原则.
仿真实验使用配置为4GB内存、64位Win8操作系统、Intel i5处理器的计算机进行上述评估,实验代码使用Java语言编写,虚拟机版本为jdk1.6.实验中物理网络及虚拟网络拓扑都采用GT-ITM[29]工具随机生成,并利用MATLAB工具对实验结果进行分析.
4.1 算法效率和性能考虑到若使用边界节点连接比较稀疏的物理网络拓扑,则在应用NID-partition时必须将不存在连接关系的边界节点间的链路开销设为无穷大,使一些虚拟网络用NID-partition无法找到划分方案,不便于NID-partition与其他算法进行性能比较.因此,为保证NID-partition对任意VN请求都存在划分的可行解,本节实验中使用全连接的物理网络拓扑.但应该指出的是,全连接的物理网络在实际中并不具备代表性,后续的第4.2节将讨论GA-partition在不同物理网络拓扑下的效率和性能.
随机生成分为10个自治域的物理网络,每个自治域中有2个边界节点,边界节点间为全连接,共190条链路.链路单位开销服从[1,10]的均匀分布.随机生成2 000个VN,VN中虚拟节点数目服从[1,8]的均匀分布,虚拟节点间以50%的概率连接.本节比较4种VN划分算法在不同VN划分问题规模下的效率和性能.VN划分的问题规模(以下简称问题规模)即虚拟节点数目与虚拟节点候选集中元素数目的乘积.本节将每个虚拟节点匹配集的元素个数固定为2(即,每个虚拟节点有4个可映射的边界节点).将GA-partition算法中的相关参数依次设定为:迭代次数为30,种群数目为200,变异概率为0.1.
· 首先,比较4种VN划分算法的运行效率.
本文用平均划分时间来衡量算法的运行效率,即,算法完成一个VN划分需要的平均计算时间.图 6的左图展示了随VN请求中虚拟节点数目的增加,4种VN划分算法在平均划分时间上的差异,图 6的右图为左图中GA-partition和NID-partition-h的放大图,可以看出:
 | Fig. 6 Comparison of four VN partitioning algorithms in efficiency图 6 4种VN划分算法的效率比较 |
1) LID-partition和NID-partition的平均划分时间随着问题规模的增大呈指数增长,当虚拟节点较多时,可用性较差;而GA-partition和NID-partition-h的平均划分时间则随虚拟节点数目的增多呈近似线性增长,在问题规模较大时,也能在可接受的时间内完成划分.文献[15]的实验结果也展示了NID- partition和NID-partition-h的平均划分时间随着问题规模的增加分别呈指数和近似线性增长,与本文的实验结果一致;
2) 在问题规模较大时,LID-partition的平均划分时间比NID-partition要长.其原因在于:与NID-partition相比,LID-partition的二元整数规划中还涉及对虚拟链路的划分,其二元变量的数目比NID-partition要多;
3) 当虚拟节点数目小于4时,GA-partition和NID-partition-h的平均划分时间都小于50ms,数量级较小,实验数据受算法外部环境因素(如CPU进程调度、磁盘读写速率等)影响较大,两种方法互有优劣;但当虚拟节点数目较大时,GA-partition基本上优于NID-partition-h.
· 其次,比较4种VN划分算法的性能.本文用额外映射开销来衡量算法性能.额外映射开销越小,表明算法的性能越好.LID-partition的额外映射开销为0(最优解),故将其作为性能比较的基准.
设Cost(M)表示算法M的映射开销,则其额外映射开销extraCost(M)按如下方式计算:
extraCost(M)=[Cost(M)-Cost(LID-partition)]/Cost(LID-partition).
由图 7的左图可以看出:相比于NID-partition和NID-partition-h,GA-partition大幅提高了VN划分的性能,即使在问题规模较大时,也能将平均额外映射开销控制在5%以内,另外两种算法则超过了10%.此外,随着问题规模的增大,GA-partition的平均额外映射开销逐渐增加,而NID-partition和NID-partition-h的平均额外映射开销没有显著变化.其原因在于,后两种算法的最优化瓶颈是未公开边界节点信息.
 | Fig. 7 Comparison of four VN partitioning algorithms in performance图 7 4种VN划分算法的性能比较 |
进一步地,考察边界节点信息对性能的影响.使物理链路的单位开销服从[1,20]的均匀分布,以增加链路单位开销的差异.此时,两个边界节点间的最小开销路径就可能不是直连链路,而是经其他边界节点中继的物理路径.公开边界节点信息的算法(LID-partition和GA-partition)会使用边界节点间的最小开销路径来优化划分方案,而不公开边界节点信息的算法(NID-partition和NID-partition-h)仍使用直连链路进行划分.如图 7中右图所示,边界节点信息对GA-partition的影响不大,而NID-partition和NID-partition-h的性能则有明显下降.
4. 2GA-partition算法的稳定性本节在不同物理网络拓扑上对GA-partition的稳定性进行验证.令物理网络中自治域的数目及自治域中边界节点的数目保持不变,调整边界节点间的连接概率生成3个物理网络拓扑,链路数分别是44,102,190.链路单位开销服从[1,10]的均匀分布.虚拟网络的生成与第4.1节相同.图 8展示了GA-partition在上述3个拓扑上的效率和性能.可以看出:GA-partition的效率和性能并没有受物理网络拓扑变化的影响,稳定性较好.
 | Fig. 8 Efficiency and performance of GA-partition in different substrate topology图 8 不同物理网络拓扑下GA-partition的效率和性能 |
本节讨论迭代次数、种群数目和变异概率对GA-partition算法的性能、效率和稳定性的影响,并总结其设置原则.随机生成10个自治域,每个自治域中有2个边界节点,共44条链路,链路的单位开销服从[1,10]的均匀分布.虚拟网络的生成与第4.1节相同.
首先,将变异概率固定为0.1,讨论种群数目(范围:50~500)和迭代次数(范围:10~50)对GA-partition算法效率的影响.
由图 9可以看出,虽然增加迭代次数和种群数目消耗了更多的计算时间,但却可以提高GA-partition的性能.具体来说:图 9的左图表明,GA-partition的效率与迭代次数和种群数目呈近似线性关系;而图 9的右图表明,GA-partition的性能与迭代次数和种群数目虽然没有明显的函数关系,但可以看出呈现如下的一些趋势:
(1) 当种群数目超过200时,可以保证平均额外映射开销小于2%;而当种群数目达到300后,再继续增加种群数目,平均额外映射开销没有明显变化;
(2) 当种群数目为50时,随着迭代次数的增加,平均额外映射开销显著减少;
(3) 随种群数目的增多,迭代次数对平均额外映射开销的影响逐渐减小.
然后,将迭代次数和种群数目分别固定为10和200(由图 9可知,此时算法在效率和性能上都有较好的表现),讨论变异概率(范围:0~0.5)对GA-partition效率和性能的影响.
 | Fig. 9 Effects of populations and iterations on the efficiency and performance of GA-partition图 9 种群数目和迭代次数对GA-partition效率和性能的影响 |
由图 10的左图可以看出,变异概率对GA-partition效率的影响是近似线性的.而变异概率对GA-partition性能的影响则相对复杂,这是因为变异概率如果太小,则容易陷入局部最优;如果太大,则容易因种群搜索的跳跃性太大而损失最优解.由图 10的右图可知,变异概率在[0.1,0.2]内算法的性能最好.
 | Fig. 10 Effects of mutation probability on the efficiency and performance of GA-partition图 10 变异概率对GA-partition效率和性能的影响 |
进一步地,考察变异概率为0.1和0.2时GA-partition的性能.图 11中展示了2 000个VN在两种变异概率下的额外映射开销.
 | Fig. 11 Comparison of GA-partition’s performance in two different mutation probabilities图 11 两种变异概率下GA-partition的性能比较 |
可以看出:在两种变异概率下,本文算法对绝大部分VN都可以得到较优的划分方案(额外映射开销在10%以内).但由于遗传算法随机搜索的本质,实验结果中也存在一些极端情况(个别VN划分方案的额外映射开销大于100%).当变异概率为0.1时,极端情况较少出现;当变异概率为0.2时略有增加.计算可得:当变异概率为0.1时,2 000个VN额外映射开销的方差约为0.031;而当变异概率为0.2时的方差约为0.043.此外,虽然两种变异概率下的平均额外映射开销基本一致(如图 10所示),但由图 11可以看出:当变异概率为0.1时,算法的稳定性更好.故在平均额外映射开销相同的情况下,应选择较小的变异概率以提高稳定性.
5 相关工作在获悉单个自治域内全部物理网络信息的前提下,Chowdhury等人[5]提出了一种同阶段的单域VN映射算法,以提高VN接受率和均衡网络负载为目标,利用混合整数规划,同时求出映射虚拟节点和虚拟链路的优化解. Fajjari等人[6]基于蚁群算法提出了一种单域VN映射方法,以降低映射开销和提高VN接受率为目标,提高了InP的长期运营收益.Cheng等人[7]基于粒子群算法设计的单域VN映射方法,显著提高了InP的长期运营收益. Huang等人[8]利用多目标负载均衡的粒子群算法,优化了单域VN映射中节点和链路的负载平衡.Guo等人[9]建立了多目标优化模型,并采用粒子群方法统一分配节点和链路资源,提高了单域VN映射的成功率和物理资源的利用率.
然而,物理网络往往被天然地分为多个自治域,这些自治域可提供的虚拟资源种类和价格都不尽相同.为满足VN请求中对虚拟资源的映射约束并尽可能地降低映射开销,必须通过跨域映射来完成VN部署.
已有的跨域VN映射方法可分为两类:分布式和集中式.典型的分布式跨域映射方法包括:Chowdhury等人[13]提出的基于策略的分布式域间映射框架,并提供地域分级寻址机制和位置感知分发协议为该框架提供支持;Houidi等人[30]提出的分布式虚拟网络映射算法,并基于多Agent技术来确保节点间的通信和同步;Zaheer等人[14]设计的V-Mart机制,该机制不仅为InP提供了公平的资源发布平台,也为SP提供了客户驱动的VN划分方法.与分布式方法不同,集中式跨域映射方法强调在VNP的统一协调下完成跨域映射中的资源匹配和VN划分.
对于资源匹配,Houidi等人[10]提供了基于XML语言的虚拟资源描述模式,并利用概念群集技术将虚拟资源按相似性进行层级分类,再基于得到的概念分类树给出资源匹配算法.以该方法为基础,Lv等人[11]提出了基于VN的服务特点对虚拟资源分类的方法,避免了盲目搜索;Medhioub等人[12]提出了基于重要性及使用频率对虚拟资源分类的方法,提高了资源匹配的效率,并克服了概念分类树难以扩展的缺点.
对于VN划分,Houidi等人[15]基于全连接的物理拓扑,给出了VN划分的确切式和启发式算法;Dietrich等人[17]以InP公开边界节点的相关信息为前提,利用二元整数规划为VN划分问题提供了一种更切合实际的确切式算法;Zhang等人[19]提出了一种分层线性规划模型,并基于对模型的分解设计了VN划分算法.
本文主要研究集中式跨域VN映射中的资源匹配和VN划分问题.与上述方法不同,本文基于OWL知识描述和SWRL查询工具来完成资源匹配,并使用遗传算法求解VN划分.本文方法可与已有单域VN映射方法[3, 4, 5, 6, 7, 8, 9]结合使用来完成跨域VN映射,即:在VN划分阶段首先使用本文方法得到划分方案,将VN划分为多个虚拟子网,使跨域VN映射转化为多个单域VN映射;然后,在虚拟子网映射阶段使用文献[3, 4, 5, 6, 7, 8, 9]的方法求解单域VN映射.
6 结束语跨域虚拟网络映射是网络虚拟化领域的一个研究重点.本文对集中式跨域虚拟网络映射的两个重要阶段(资源匹配和虚拟网络划分)中存在的问题分别进行了研究,提出:(1) 一种基于OWL知识描述和SWRL查询工具的资源匹配算法,与已有资源匹配工作相比,本文算法能够支持VN user表达多样化的映射约束以及精确的数值属性匹配;(2) 一种基于遗传算法的VN划分算法(GA-partition),并通过理论分析证明了GA-partition算法是可以终止的,且算法的搜索空间包含整个解空间.仿真实验结果表明:GA-partition算法大幅提高了VN划分的求解效率,且算法的输出结果与最优解的误差可控制在5%以内.
未来工作主要从以下3个方面进行:(1) 设计高效的资源信息管理机制,将物理网络的即时性信息(如物理资源的占用情况、可用能力信息等)引入到资源匹配中,提高资源匹配结果的准确性和有效性;(2) 采用自适应的遗传算法动态调整变异概率和选择概率,进一步提高VN划分的性能;(3) 综合考虑其他优化目标(如,功耗或负载平衡等),对本文方法加以完善.
| [1] | Anderson T, Peterson L, Shenker S, Turner J. Overcoming the Internet impasse through virtualization. Computer, 2005,38(4): 34-41 . |
| [2] | Feamster N, Gao L, Rexford J. How to lease the Internet in your spare time. ACM SIGCOMM Computer Communication Review, 2007,37(1):61-64 . |
| [3] | Yu M, Yi Y, Rexford J, Chiang M. Rethinking virtual network embedding: Substrate support for path splitting and migration. ACM SIGCOMM Computer Communication Review, 2008,38(2):17-29 . |
| [4] | Lischka J, Karl H. A virtual network mapping algorithm based on subgraph isomorphism detection. In: Proc. of the 1st ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures. 2009. 81-88 . |
| [5] | Chowdhury N, Rahman M, Boutaba R. Vineyard: Virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans. on Networking, 2012,20(1):206-219 . |
| [6] | Fajjari I, Aitsaadi N, Pujolle G, Zimmermann H. VNE-AC: Virtual network embedding algorithm based on ant colony metaheuristic. In: Proc. of the 2011 IEEE Int’l Conf. on Communications. 2011. 1-6 . |
| [7] | Cheng X, Zhang ZB, Su S, Yang FC. Virtual network embedding based on particle swarm optimization. Acta Electronica Sinica, 2011,39(10):2240-2244 (in Chinese with English abstract). |
| [8] | Huang BB, Lin RH, Peng K, Zou H, Yang FC. Load-Balancing based on particle swarm optimization in virtual network mapping. Journal of Electronics & Information Technology, 2013,35(7):1753-1759 (in Chinese with English abstract). |
| [9] | Guo ZE, Xue HW, Dai YQ. A multi-objective particle swarm optimization based virtual network embedding algorithm. Journal of National University of Defense Technology, 2013,35(5):163-167 (in Chinese with English abstract). |
| [10] | Houidi I, Louati W, Zeghlache D, Baucke S. Virtual resource description and clustering for virtual network discovery. In: Proc. of the IEEE Int’l Conf. on Communications Workshop on Communications. 2009. 1-6 . |
| [11] | Lv B, Wang Z, Huang T, Chen J, Liu Y. Virtual resource organization and virtual network embedding across multiple domains. In: Proc. of the 2010 Int’l Conf. on Multimedia Information Networking and Security. 2010. 725-728 . |
| [12] | Medhioub H, Houidi I, Louati W Zeghlache D. Design, implementation and evaluation of virtual resource description and clustering framework. In: Proc. of the 2011 IEEE Int’l Conf. on Advanced Information Networking and Applications. 2011. 83-89 . |
| [13] | Chowdhury M, Samuel F, Boutaba R. PolyViNE: Policy-Based virtual network embedding across multiple domains. In: Proc. of the 2nd ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures. 2010. 49-56 . |
| [14] | Zaheer F, Xiao J, Boutaba R. Multi-Provider service negotiation and contracting in network virtualization. In: Proc. of the 2010 IEEE/IFIP Network Operations and Management Symp. 2010. 471-478 . |
| [15] | Houidi I, Louati W, Bean-Ameur W, Zeghlache D. Virtual network provisioning across multiple substrate networks. Computer Networks, 2011,55(4):1011-1023 . |
| [16] | Werle C, Bless R, Papadimitriou P, Houidi I, Louati W, Zeghlache D, Mathy L. Building virtual networks across multiple domains. ACM SIGCOMM Computer Communication Review, 2011,41(4):412-413 . |
| [17] | Dietrich D, Rizk A, Papadimitriou P. Multi-Domain virtual network embedding with limited information disclosure. In: Proc. of the IFIP Networking Conf. 2013. 1-9. http://www.ikt.uni-hannover.de/lavinet.html?&L=1 |
| [18] | Dietrich D, Rizk A, Papadimitriou P. AutoEmbed: Automated multi-provider virtual network embedding. ACM SIGCOMM Computer Communication Review, 2013,43(4):465-466 . |
| [19] | Zhang M, Wu C, Wang B, Jiang M. Research on mapping method of logical carrying network across multiple domains. Journal on Communications, 2012,33(8):200-207 (in Chinese with English abstract). |
| [20] | Schaffrath G, Werle C, Papadimitriou P, Feldmann A, Bless R, Greenhalgh A, Wundsam A, Kind M, Maennel O, Mathy L. Network virtualization architecture: Proposal and initial prototype. In: Proc. of the 1st ACM Workshop on Virtualized Infrastructure Systems and Architectures. 2009. 63-72 . |
| [21] | Michalski R, Stepp R. Automated construction of classifications: Conceptual clustering versus numerical taxonomy. IEEE Trans. on Pattern Analysis and Machine Intelligence, 1983,5(4):396-410 . |
| [22] | DE-CIX. https://www.de-cix.net/ |
| [23] | PeeringDB. http://www.peeringdb.com/ |
| [24] | OWL. http://www.w3.org/TR/owl-features/ |
| [25] | SWRL. http://www.w3.org/Submission/SWRL/ |
| [26] | Han RF. Principle of Genetic Algorithm and Applications. Beijing: The Publishing House of Ordnance Industry, 2009 (in Chinese). |
| [27] | Wang C, Wolf T. Virtual network mapping with traffic matrices. In: Proc. of the 7th ACM/IEEE Symp. on Architectures for Networking and Communications Systems. 2011. 225-226 . |
| [28] | Holland JH. Adaptation in Natural and Artificial Systems. Cambridge: MIT Press, 1992. |
| [29] | GT-ITM. http://www.cc.gatech.edu/projects/gtitm/ |
| [30] | Houidi I, Louati W, Zeghlache D. A distributed virtual network mapping algorithm. In: Proc. of the IEEE Int’l Conf. on Communications. 2008. 5634-5640 . |
| [7] | 程祥,张忠宝,苏森,杨放春.基于粒子群优化的虚拟网络映射算法.电子学报,2011,39(10):2240-2244. |
| [8] | 黄彬彬,林荣恒,彭凯,邹华,杨放春.基于粒子群优化的负载均衡的虚拟网络映射.电子与信息学报,2013,35(7):1753-1759. |
| [9] | 郭智恩,薛海伟,戴一奇.一种基于多目标微粒群优化的虚拟网络映射方法.国防科技大学学报,2013,35(5):163-167. |
| [19] | 张旻,吴春明,王滨,姜明.跨域逻辑承载网映射方法研究.通信学报,2012,33(8):200-207. |
| [26] | 韩瑞锋.遗传算法原理与应用实例.北京:兵器工业出版社,2009. |