（信息与通信工程专业论文）网络虚拟化中资源分配算法研究.pdf

r e s e a r c h e si nr e s o u r c ea l l o c a t i o na l g o r i t h mi nn e t w o r k s v i r t u a li z a t i o n b y x u y u e y a n g b e ( h u n a ni n s i t u t eo fs c i e n c ea n dt e c h n o l o g y ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n i n f o r m a t i o na n dc o m m u n i c a t i o ne n g i n e e r i n g i nt h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r p r o f e s s o rl u 0j u a n m a y ，2 0 1 1 88洲9川509iiiii 帆y 、 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：织皂朋日期：0 0 f 年占月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：普量奄 导师签名：弓i 柏 日期：o o i 绰石月f 日 日期： 沙f 厂年稠e l 硕f j 学位论文 摘要 i n t e r n e t 使人们获取和交换信息的方式变得便捷，同时i n t e r n e t 的发展也面临挑 战。当前i n t e r n e t 的体系结构存在许多缺点，由于i n t e r n e t 由多个运营商共同提供， 使i n t e r n e t 体系结构的变革难以实现，i n t e r n e t 的发展陷入僵局。通过网络虚拟化， i n t e r n e t 能够有效克服僵化问题。网络虚拟化使将来的i n t e r n e t 体系结构多元化为一 系列相互独立的虚拟网络，这些虚拟网络共享基础设施提供者的资源，并支持多 种网络体系结构、实验和业务。资源分配是网络虚拟化中的一个基本问题，有效 的资源分配能够提高基础设施提供者的物理资源利用率，并降低服务提供者租用 资源所带来的成本。因此，设计有效的资源分配算法具有重要的意义。 首先，对集中式和分布式两类资源分配算法进行了分析。针对基于拓扑分割 的资源分配算法产生的拓扑稀疏问题，提出了一种优化拓扑紧密度的资源分配算 法a r m a ( a na d v a n c er e s o u r c em a p p i n ga l g o r i t h m ) 。该算法基于拓扑分割思想， 利用中心协调者和物理节点的相互配合获得节省带宽的资源分配结果。a r m a 包 括三个部分：星型虚拟网络资源分配算法s m a ( s t a rm a p p i n ga l g o r i t h m ) 、中心协 调者接收数据算法c r d a ( c e n t r a l c o o r d i n a t o rr e c e i v i n gd a t aa l g o r i t h m ) 和物理节 点接收数据算法s r d a ( s u b s t r a t e n o d e sr e c e i v i n gd a t aa l g o r i t h m ) 。s m a 对某个 星型虚拟网络进行资源分配，然后将分配结果和占用物理链路的数目告知中心协 调者，中心协调者利用c r d a 算法比较并选择最节省带宽资源的结果，同时将该 结果告知各个物理节点，物理节点通过s r d a 算法更新其他物理节点的空闲资源 信息，并准备对下一个星型虚拟网络进行资源分配。仿真实验表明，a r m a 算法 在牺牲一定时延的情况下，能够减少通信量以及维护虚拟网络拓扑结构在物理网 络上的紧密度。 为了维护物理节点的负载平衡以提高资源的利用率，在节点迁移的基础上本 文提出了一种主动式的动态资源分配算法。该算法通过平均节点负载差异度来衡 量当前物理节点上的负载分布状况，并通过和物理网络容忍的负载差异度相比较 来估计当前负载偏离正常值的程度。在动态资源分配的过程中，该算法利用节点 迁移将负载从忙碌物理节点转移到空闲物理节点以实现负载均衡，并考虑了节点 迁移对物理链路带宽，虚拟链路时延的影响。仿真实验表明，该算法对虚拟链路 时延和物理链路带宽的影响较小，能够有效地维护物理节点的负载均衡。 关键词：网络虚拟化；资源分配；资源利用率；负载均衡 i i 网络虚拟化巾资源分配算法研究 a b s t r a c t i n t e r n e tf a c i l i t a t e s a c h i e v i n g a n d e x c h a n g i n gi n f o r m a t i o n ，h o w e v e r ，t h e d e v e l o p m e n to fi n t e r n e tf a c e sc h a l l e n g e t h ec u r r e n ti n t e r n e ti sp l a g u e dw i t ha n u m b e ro fm a n yf u n d a m e n t a ll i m i t a t i o n s i ti sh a r dt or a d i c a lc h a n g et h ea r c h i t e c t u r e d u et oi t s m u l t i p r o v i d e rn a t u r e ，a n da s ar e s u l t ，t h ei n t e r n e ti si no s s i f i c a t i o n t h r o u g hn e t w o r kv i r t u a l i z a t i o n ，i n t e r n e tc a ne f f e c t i v eo v e r c o m et h eo s s i f i c a t i o na n d m a k et h ea r c h i t e c t u r ee v o l u t i o n a r y n e t w o r kv i r t u a l i z a t i o nd i v e r s i f i e st h ef u t u r e i n t e r n e ta r c h i t e c t u r ei n t os e p a r a t ev i r t u a ln e t w o r k s ( v n ) t h ev n sc a ns i m u l t a n e o u s s u p p o r tm u l t i p l en e t w o r ka r c h i t e c t u r e s ，e x p e r i m e n t sa n ds e r v i c e so v e ras h a r e d s u b s t r a t en e t w o r k af u n d a m e n t a lp r o b l e mi ni n s t a n t i a t i o no fv i r t u a ln e t w o r k s ( v n s ) i sa no p t i m a la l l o c a t i o n m a p p i n go fr e s o u r c e s e f f e c t i v er e s o u r c ea l l o c a t i o na l g o r i t h m c a ni m p r o v et h er e s o u r c eu t i l i z a t i o no fi n f r a s t r u c t u r ep r o v i d e ra n dr e d u c et h ec o s t s o r e s e a r c ho nl o a db a l a n c es c h e m e sh a sg r e a ts i g n i f i c a n c e f i r s t l y ，t h i sp a p e ra n a l y z e dc e n t r a lr e s o u r c ea l l o c a t i o na l g o r i t h ma n dd i s t r i b u t e d r e s o u r c ea l l o c a t i o na l g o r i t h m a i m st or e s o l v et h ep r o b l e mo ft o p o l o g ys p a r s i t yi n r e s o u r c ea l l o c a t i o na l g o r i t h mb a s e do nv nd e c o m p o s i t i o n ，t h i sp a p e rp r o p o s e da n a d v a n c e dr e s o u r c ea l l o c a t i o na l g o r i t h m ( a r m a ) t om a i n t a i nt h ec o m p a c t n e s so f v i r t u a ln e t w o r k t o p o l o g y i ns u b s t r a t en e t w o r k t h e a l g o r i t h m b a s eo nv n d e c o m p o s i t i o na n do b t a i nt h er e s u l tt h a tu s el e a s tb a n d w i d t hv i ac o o p e r a t i o no f s u b s t r a t e sa n dc e n t r a l 。c o o r d i n a t o r a r m ac o n s i s t so f t h r e ea l g o r i t h m s ：s t a rm a p p i n g a l g o r i t h m ( s m a ) ，c e n t r a l - c o o r d i n a t o rr e c e i v i n gd a t aa l g o r i t h m ( c r d a ) a n d s u b s t r a t e - n o d e sr e c e i v i n gd a t aa l g o r i t h m ( s r d a ) s m aa l l o c a t e sr e s o u r c ef o r c e r t a i ns t a rv i r t u a ln e t w o r k ，a n dt h e ns e n d st h er e s u l ta n dt h ea m o u n to fs u b s t r a t e 1 i n k sc o n s u m e di nt o c e n t r a l c o o r d i n a t o r t h r o u g hc r d a c e n t r a l c o o r d i n a t o r c o m p a r e sa n dc h o o s e st h er e s u l t t h a tc o n s u m e st h el e a s ts u b s t r a t el i n k sa sf i n a l l y r e s u l t ，t h e ns e n dt h ef i n a l l yr e s u l tt oa l ls u b s t r a t e sn o d e s i ns r d a t h es u b s t r a t en o d e u p d a t e sf r e er e s o u r c ei n f o r m a t i o na b o u to t h e rs u b s t r a t e ，a n dt h e nr e a d yt oa l l o c a t e r e s o u r c ef o rn e x ts t a rv i r t u a l n e t w o r k f i n a l l y , s i m u l a t i o nr e s u l t ss h o wt h a tt h e a l g o r i t h mc a no b t a i nb e t t e rd e l a yp e r f o r m a n c e ，f e wm e s s a g ev o l u m ea n ds u b s t r a t e l i n kc o n s u m p t i o n s t om a i n t a i nl o a db a l a n c ei ns u b s t r a t e n o d e s ，t h i sp a p e rp r o p o s ea na c t i v e d y n a m i c a l l yr e s o u r c ea l l o c a t i o na l g o r i t h mb a s e do nv i r t u a ln o d el i v em i g r a t i o n t h e i i i 硕i 二学位论文 a l g o r i t h me s t i m a t e st h el o a dd i s t r i b u t i o ni n a l ls u b s t r a t en o d e sv i at h ea v e r a g el o a d d i v e r g e n c ed e g r e e ，a n dc o m p a r e si tw i t ht h et o l e r a n td i v e r g e n c ed e g r e eo fs u b s t r a t e n e t w o r kt od e t e r m i n ew h e t h e ra d ju s tr e s o u r c ea l l o c a t i o n d u r i n ga d ju s t i n gr e s o u r c e a l l o c a t i o n ，t h ea l g o r i t h ms h i f tl o a df r o mb u s yn o d e st of r e en o d e sb yv i r t u a ln o d el i v e m i g r a t i o nt om a i n t a i nl o a db a l a n c e ，a n dt h ei m p a c to fm i g r a t i o no nb a n d w i d t hi n s u b s t r a t el i n k sa n dd e l a yi nv i r t u a ll i n k si sa l s ot a k e ni n t oa c c o u n t s i m u l a t i o nr e s u l t s h o w st h ea l g o r i t h mc a ne f f e c t i v eb a l a n c el o a di ns u b s t r a t en o d e s ，a n di m p a c to n b a n d w i d t ha n dd e l a yi ss l i g h t k e yw o r d s ：n e t w o r kv i r t u a l i z a t i o n ；r e s o u r c ea l l o c a t i o n ；r e s o u r c eu t i l i z a t i o n ；l o a d b a l a n c e i v 网络虚拟化中资源分配算法研究 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引一v i i 附表索引v i i i 第l 章绪论1 1 1 引言1 1 2 网络虚拟化的定义1 1 3 网络虚拟化的主要特点2 1 4 网络虚拟化的基本组成2 1 5 选题背景及意义3 1 6 本文组织结构4 第2 章相关工作研究5 2 1 网络虚拟化中的资源分配一5 2 1 1 虚拟网络的构造过程5 2 1 2 虚拟网络资源分配6 2 2 典型的资源分配算法一8 2 2 1 集中式资源分配算法一8 2 2 2 分布式的资源分配算法1 3 2 2 3 小结l5 第3 章一种优化的星型网络虚拟化资源分配算法1 7 3 1a r m a 的提出17 3 1 1 设计背景17 3 1 2 问题描述和优化目标1 8 3 2 拓扑分割过程2 0 3 3 资源分配通信协议2 0 3 4 优化的资源分配算法a r m a 2 1 3 4 1 星型虚拟网络资源分配算法s m a 2 2 3 4 2 中心协调者接收数据算法c r d a 一2 6 3 4 3 物理节点接收数据算法s r d a 2 6 3 5 实验模拟及性能分析2 7 v 硕一l 学位论文 3 。5 1 仿真平台设计以及仿真参数2 7 3 5 2t i 分析2 8 3 5 3 通信量分析一2 9 3 5 4 时延分析3 0 3 6 代价分析3 0 3 7 小结3l 第4 章网络虚拟化中动态资源分配算法研究3 2 4 1 设计背景一3 2 4 2 问题描述和网络模型3 3 4 2 1问题描述3 3 4 2 2 网络模型：一3 5 4 3 算法设计3 6 4 3 1 选择目标宿主3 7 4 3 2 调整虚拟链路3 8 4 4 仿真实验4 0 4 4 1 九和0 取值分析4 0 4 4 2 带宽和时延分析4 l 4 4 3 物理节点负载分析4 2 4 5 小结4 3 总结和展望4 4 参考文献一4 6 附录a 攻读硕士期间发表的论文5 1 附录b ( 攻读硕士期间参与的项目列表) 5 2 网络虚拟化中资源分配算浃研究 插图索引 图1 1 网络虚拟化场景图3 图2 1 虚拟网络构造过程5 图2 2 资源分配过程一6 图2 3 物理网络一7 图2 4 虚拟网络服务请求要构造的网络7 图2 5 资源分配结果7 图2 6 星型骨干拓扑资源分配过程1 0 图2 7 支持链路分割的资源分配结果1 1 图2 8 支持链路迁移的资源分配结果1l 图2 9 自组织模型15 图3 1 虚拟网络请求包含的拓扑结构1 9 图3 2 资源分配结果l 19 图3 3 资源分配结果2 1 9 图3 4a r m a 时序图2 2 图3 5b r i t e 的输出格式2 8 图3 6t i 值对比2 9 图3 7 通信量对比2 9 图3 8 时延对比3 0 图4 1 物理网络3 4 图4 2 物理网络调整前3 4 图4 3 物理网络调整后3 4 图4 4 调整前一3 9 图4 5 调整后3 9 图4 6 负载差异度取值分布4 0 图4 7 闲忙门限值对v n 重配置率的影响一4 1 图4 8 调整前后虚拟链路时延对比4 1 图4 9 调整前后物理链路空闲带宽变化4 2 图4 1 0 平均负载差异度变化趋势4 2 v i i 硕l 学位论文 附表索引 表2 1 资源分配算法综合比较1 6 v i i i 硕上学位论文 1 1 引言 第1 章绪论 i n t e r n e t 触及社会的各个领域，改变了人们工作和生活的方式，正是由于 i n t e r n e t 巨大的规模，阻碍了i n t e r n e t 的进一步发展。巨大的规模使i n t e r n e t 拥有 多个提供者，而变革i n t e r n e t 的体系结构，必须在多个提供者之间达成一致，但 是由于各方利益的原因，统一的意见难以达成，i n t e r n e t 的发展也受到了阻碍。网 络虚拟化能够推进i n t e r n e t 的进一步发展n 门3 。 网络虚拟化将物理网络的资源抽象为虚拟资源如虚拟节点、虚拟链路等，然 后将虚拟节点和虚拟链路组成相互隔离虚拟网络，在这些虚拟网络上可以部署特 定应用所要求的体系结构，所以网络虚拟化不是使用另一个新的体系结构代替现 有i n t e r n e t 的体系结构，而是提供一个新的网络体系结构可以部署的平台。网络 虚拟化还会使新服务的部署更加快捷，对服务的管理更加完善。总之，网络虚拟 化与传统的网络技术相比，体系结构的灵活性、可扩展性更具有优势。由于网络 虚拟化具有极大的发展潜力，欧美各国开展了多个网络虚拟化项目如 p l a n e t l a b h l 、v i n i 跖1 和4 w a r d 1 的研究，在思科等主流网络设备中，也提供了对 网络虚拟化的支持。但是网络虚拟化在资源分配，虚拟网络的管理，i n p s 的接入 控制和使用策略等方面还存在巨大的挑战，实现网络虚拟化技术的大规模应用有 待进一步深入的研究。 1 2 网络虚拟化的定义 网络虚拟化是多元化i n t e r n e t 体系结构的组成部分，它支持来自不同服务提 供者的异构网络体系结构共存，并使得这些网络体系结构可以共享由多个基层设 施提供者管理的物理基底( p h y s i c a ls u b s t r a t e ) n 刮。网络虚拟化将服务提供者 s p s ( s e r v i c ep r o v i d e r s ) 从基础设施提供者i n p s ( i n f r a s t r u c t u r ep r o v i d e r s ) 中分离出 来，为i n t e r n e t 的演进和改变带来了灵活性。网络虚拟化并不是一个新的概念， 在大部分计算机网络中它以一种有限的形式被实现为v p n 。v p n 能够实现在一个 共同的基础设施上承载多个虚拟网络，但是v p n 却存在以下问题n 引： ( 1 ) 所有的虚拟网络运用相同的技术和协议栈。 ( 2 ) 虚拟网络之间并不是真正的隔离。 ( 3 ) 基础设施提供者和服务提供者没有完全隔离，有时候是同一个实体。 通过提供独立可编程的虚拟网络，网络虚拟化在v p n 的基础上获得进一步发 网络虚拟化中资源分配算法研究 展。在网络虚拟化中，建立虚拟网络不一定基于i p 技术，任何一种网络体系结构 原则上都可以用来建立虚拟网络；另外网络虚拟化具有操作多个提供者场景的能 力并能隐藏物理基础设施的具体细节如不同管理域；最后在网络虚拟化中，虚拟 网络是完全隔离的。 1 3 网络虚拟化的主要特点 网络虚拟化这种分离思想称为c a b o 1 ( c o n c u r r e n ta r c h i t e c t u r e sa r eb e t t e r t h a no n e ) ，意思是多个平行的体系结构优于一个单一的体系结构。网络虚拟化支 持多个平行体系结构共存的能力，使其具有以下优点： ( 1 ) 新应用部署更加便捷。实现i n p s 和s p s 的分离之后，s p 部署一种基于新 网络体系结构的应用，只需从i n p s 租用虚拟设施并构建一个新虚拟网络即可，这 比通过多个i s p s 之间协作完成部署新应用的方式更加快捷。 ( 2 ) s p s 应用的服务质量更好。s p s 能够控制端到端通信中涉及到的所有虚拟 结点和虚拟链路，因而可以保障应用的服务质量。同时网络虚拟化支持多种异构 体系结构共存，因此可以根据不同应用的特点选择最优的网络体系结构来构建虚 拟网络。 ( 3 ) 计费更精确。在网络虚拟中，一项服务完全由s p s 来提供，s p s 可以准确 地控制用户获得的服务等级和记录用户获得的服务数量，从而进行相应的计费。 ( 4 ) 网络技术测试更容易。当前测试网络技术的方式存在投资大、不准确的 缺点。在运用网络虚拟化技术后，可建立一个单独的虚拟网络来评估网络技术， 这种方式简便、灵活，而且投资小。 1 4 网络虚拟化的基本组成 网络虚拟化将传统的i n t e r n e t 服务提供者( i s p s ) 分离为基础设施提供者i n p s 和服务提供者s p s 。i n p s 负责部署和管理物理资源，并对这些物理资源进行虚拟 化，形成虚拟的资源池，然后通过可编程的接口将这些虚拟资源提供给用户。s p s 租用一个或者多个i n p s 的资源，并通过对租用的资源进行编程来创建虚拟网络。 s p s 也可以将其租用的资源再转租给其他s p s ，以充当虚拟的i n p s 。 i n p s 对物理资源进行虚拟化的过程主要包括物理链路虚拟化和物理节点虚拟 化。物理链路虚拟化能够在一条共享的物理链路上支持多条相互隔离的虚拟链路 传输。每条虚拟链路可以通过标签、波长等技术来标示。物理链路虚拟化已经广 泛存在当今网络技术中如a t m 、m p l s 等。物理节点虚拟化在一个物理节点上抽 象出多个虚拟的节点，每个虚拟节点拥有一部分物理节点的资源如c p u 、存储等。 思科等主流网络设备制造商已经在其主要的路由产品中提供了对节点虚拟化的支 持。s p s 利用这些虚拟节点和虚拟链路便可以组成与物理网络功能相同的虚拟网 2 硕j j 学位论文 络。如图1 1 ，在一个物理节点上承载着属于不同虚拟网络的多个虚拟节点，在 一条物理链路上承载着不同虚拟网络的多条虚拟链路，多个虚拟网络共享着物理 网络的基础设施，它们可以使用不同的体系结构，运行不同的网络协议和应用。 图1 1 网络虚拟化场景图 对于网络虚拟化的体系结构，文献 12 为网络虚拟化定义了一种面向服务的 商业模式，并在此基础上进一步提出了网络虚拟化的体系结构。在这种体系结构 中，能够动态地发现、使用和组合不同层次的服务；文献 1 3 】提出了一种基于q o s 的虚拟网络体系结构，为了满足虚拟网络不同q o s 的要求，该体系结构在每个路 由器中将流量的q o s 分成若干个等级，并从其中选择最适合的等级分配给各个虚 拟网络；作者在文献 1 4 】中提出了一种网络虚拟化的资源管理体系结构，该体系 结构采用多域管理机制，每个管理单元负责相应域的资源分配，所以该体系结构 能够获得平行分配资源的能力。 1 5 选题背景及意义 网络虚拟化是i n t e r n e t 的发展趋势，在学术界和工业界受到了广泛的关注， 与现有i n t e r n e t 体系结构相比，网络虚拟化使将来的i n t e r n e t 更具开放性，灵活性 和可拓展性。但是网络虚拟化技术的发展面临资源分配问题的挑战，具体原因如 下1 5 1 6 1 ： ( 1 ) 资源分配算法本身的复杂性。在物理网络上，为虚拟网络找到最优的资 源分配结果是一个n p 难问题。 ( 2 ) 从i n p s 的角度来说，资源分配算法必须有效使用资源。i n p s 的物理资源 是有限的，所以资源分配算法必须能够提高物理资源的利用率，使i n p s 可以满足 更多的虚拟网络服务请求，以获得最大利润。另一方面资源分配算法要有利于物 理节点和物理链路上的负载平衡，避免造成网络拥塞，影响虚拟网络的性能。 ( 3 ) 从服务提供者s p s 的角度来说，资源分配算法要具有自适应性。随着s p s 的应用拓展和收缩，它所要求的资源也应增多或减少。实时地调整资源分配，可 以减少s p s 租用i n p s 资源的成本。 网络虚拟化中资源分配算法研究 综上所述，资源分配算法的设计不仅十分复杂，而且关系到i n p s 和s p s 各方 的利益，所以研究有效的资源分配算法对促进网络虚拟化技术的发展和实际应用 具有重要意义。本文主要针对网络虚拟化中的资源分配问题，在研究已有资源分 配算法的基础上，提出了一种优化的资源分配算法和一种动态的资源分配算法。 具体工作内容如下： 1 介绍了网络虚拟化的相关概念，选题背景及意义；分析了网络虚拟化中的 资源分配问题，对当前的资源分配算法进行了分类比较，并总结了每类相关研究 的缺点和优点。 2 基于拓扑分割思想，提出了一种提高带宽利用率的资源分配算法，该算法 主要包括星型虚拟网络资源分配算法s m a ，中心协调者数据接收算法c r d a 和 物理节点数据接收算法s r d a ；并设计了用于中心协调者和物理节点协作完成资 源分配的通信协议，最后对整个算法进行了仿真分析。 3 提出了物理网络容忍负载差异度、平均负载差异度、虚拟节点权重因子和 综合影响因子的概念，基于这四个主要的概念，设计了一种动态资源分配算法， 该算法主要包括目标宿主选择阶段和虚拟链路调整阶段，并对整个算法进行了仿 真分析。 1 6 本文组织结构 全文共分4 章，各章内容安排如下： 第1 章概述网络虚拟化的相关概念、选题背景以及本文的主要工作。 第2 章首先介绍了网络虚拟化中的资源分配问题，然后对典型的资源分配算 法进行分类比较，最后对每类相关研究的缺点和优点进行了分析。 第3 章针对资源分配过程中有效利用物理资源的要求，提出了一种基于拓扑 分割的资源分配算法。对该算法的s m a ，c d r a ，s r d a 进行了详细研究和论述， 最后通过仿真分析了该算法的性能。 第4 章首先分析了动态资源分配算法设计难点，然后提出了物理网络容忍的 负载差异度，平均负载差异度，虚拟节点权重因子和综合影响因子四个概念，并 基于这些概念设计了一种动态的资源分配算法，最后通过仿真分析了该算法的性 能。 最后对全文进行了总结，同时针对论文存在的问题，提出了一些建设性的意 见，以供进一步研究。 4 硕l ：学位论文 第2 章相关工作研究 资源分配是网络虚拟化中的一个基本问题。有效的资源分配有利于提高i n p s 物理资源的利用率，节约s p s 租用资源所带来的成本。本章首先介绍网络虚拟化 中的资源分配问题，接着分析当前典型的资源分配算法，最后对这些算法进行了 比较，为后续章节的研究奠定基础。 2 1 网络虚拟化中的资源分配 2 1 1 虚拟网络的构造过程 创建一个虚拟网络要经历物理资源虚拟化，资源描述，资源发现，资源分配 和资源管理六个阶段，1 7 3 ，整个过程如图2 1 所示。资源虚拟化阶段i n p s 要对大 规模的物理资源进行抽象，形成虚拟资源池。i n p s 对物理资源的抽象往往是多个 层次的，例如目前业界提出的资源模型中就出现了虚拟机、集群、虚拟数据中心 “ 等若干层次分明的资源抽象。资源抽象为网络虚拟化定义了操作的对象和粒度， 是网络虚拟化的基础。资源发现主要完成收集当前可用的虚拟资源，这些虚拟资 源可能来自一个或者多个i n p s 。资源描述是对虚拟资源进行描述的方法，由于网 络资源是多种多样的，所以必须采取灵活的方式对虚拟资源进行描述，便于发现 和采用。资源分配是按照s p s 需要构造的虚拟网络的资源约束条件、拓扑结构， 选择合适的虚拟资源构造虚拟网络的过程。在对虚拟网络进行初始的资源分配后， j 虚拟资源管理能够基于虚拟网络生命周期内的资源需求变化而调整资源分配，也 能够对虚拟资源进行维护等。 图2 1 虚拟网络构造过程1 7 1 网络虚拟化中资源分配算法研究 2 1 2 虚拟网络资源分曲己 网络虚拟化中的资源分配( 映射) 是指i n p s 在接受了s p s 的服务请求r e q 之后， 根据请求构造的虚拟网络的拓扑结构和资源约束条件，从i n p s 物理网络中选择合 适的虚拟资源来构造该虚拟网络的过程。 g s ( f ，y s ，e s ，j r s ) = 矿s ，e s ，尺，l s ( f ) ，尺，( r ) ( 2 1 ) g v ( f ，y ，e v ，j r v ) = 矿( f ) ，e v ( f ) ，r n ”( i ) ，r ，( f ) ( 2 2 ) m a r n ( 行v ) = ，1 5 ，l v v v ( o ，玎s 矿s ( 2 3 ) m a e t ( 1 v ) = p ，。ee v , p e s ( 2 4 ) 图2 2 资源分配过程 下面采用图论的方式对资源分配进行描述。式( 2 1 ) 表示i n p s 的物理网络 ( s u b s t r a t en e t w o r k ) ，v 5 ( v e r t i c e s ) 是物理节点集合，e 8 ( e d g e s ) 是物理链路集合。群( f ) 表示t 时刻物理节点的空闲资源向量，群( f ) 表示t 时刻物理链路空闲资源向量。 式( 2 2 ) 表示第i 个r e q 请求构造的虚拟网络，简称虚拟网络。v 9 ( f ) 表示虚拟网络 的虚拟节点集，e ”( f ) 表示虚拟网络的虚拟链路集，蟛( f ) 表示虚拟节点的资源需求 向量，群( f ) 表示虚拟链路的资源需求向量。整个资源分配过程从形式上又可以分 为虚拟节点资源分配和虚拟链路资源分配两个过程。虚拟节点资源分配是对于虚 拟网络中的每个虚拟节点刀，从物理网络中选择空闲资源数目大于或等于其资源 需求的物理节点n 。来承载该虚拟节点的过程，如式( 2 3 ) ，本文将该物理节点甩。称 为虚拟节点r ，的宿主。虚拟链路资源分配是对于虚拟网络中的每条虚拟链路，一 从物理网络中选择空闲资源数目大于或等于其资源需求物理路径尸来承载该虚拟 链路的过程，该物理路径可能包括一条或者多条物理链路，如式( 2 4 ) 。在实际资 源分配的过程中，节点资源分配和链路资源分配并不是两个相互独立的过程，如 果将整个过程资源分配问题分裂为节点资源分配和链路资源分配，先后解决，将 得不到最优的结果h 引。整个资源分配的过程如图2 2 所示。 6 硕卜学位论文 定义l ：物理路径带宽，乞，= m i n ( e 咖) ，e p ，e 为组成p 的物理链路，为 物理链路e 所具有空闲带宽。 下面将用一个具体的例子对资源分配进行说明。假设一张成物理网络g 5 ( t ) 如图2 3 所示。物理节点集合v 5 = a ，b ，c ，d ) ，物理链路集合e 5 = l a b ，l b c ， l a d ，物理节点空闲资源向量r s n ( t ) = 6 ，12 ，9 ，6 ) ，物理链路空闲资源向量 r 8 l ( t ) = 8 ，1 0 ，7 。第i 个服务请求要构造的虚拟网络g ”( t ) 如图2 4 所示，虚拟节 点集合v 7 = a 1 ，b 1 ，c 1 ) ，虚拟链路集合e v = l a l b l ，l b l c l ，虚拟节点资源需求 向量r v n ( t ) = 3 ，4 ，3 ) ，虚拟链路资源需求向量r i ( t ) = 4 ，3 ) 。在图2 5 中，i n p s 根据虚拟网络的拓扑，节点和链路的资源约束，选择物理节点a ，b 和c 分别承 载的虚拟节点a 1 ，b l ，c 1 ，选择物理链路l a b ，l b c 分别承载虚拟链路l a l b l ， l b i c i ，并组合成虚拟网络。 图2 3 物理网络 c ，、j l a l b i ，一、l b l c l，一、 i ，一一一一一一一i 、j 一一一一一一一j a lb1c 1 ( ) 虚拟节点 一虚拟链路 图2 4 虚拟网络服务请求要构造的网络 4 、， 图2 5 资源分配结果 7 c 网络虚拟化中资源分配算法研究 2 2 典型的资源分配算法 2 2 1 集中式资源分配算法 在集中式资源分配算法中，资源分配的计算主要由i n p s 的一个中心实体完 成。该中心实体要实时地掌握所有物理节点、物理链路的空闲资源信息，以便为 要构造的虚拟节点和虚拟链路选择合适的宿主。并且要实时地掌握物理网络的拓 扑信息，为此中心实体可能会周期地探询每个物理节点和每条物理链路，以便能 够实时的掌握物理节点和物理链路的状态( 如加入，退出，故障等) 。集中式资 源分配又可以分为静态和动态两类，下文将详细介绍这两类算法的相关研究。 2 2 1 1 静态的集中式资源分配算法 静态的资源分配算法是指为虚拟网络进