论文部分内容阅读
三十年来,各种各样的网络技术不断发展,使得因特网能够支持很广泛的应用,现已成为全球商业运行、多媒体业务、信息交换等的重要基础设施。但是因特网的成功和普遍性也带来一些问题,其普遍化和集中化的趋势要求网络具有灵活性,能够进行网络结构变化,但因特网现有网络构架和协议难以满足这一要求。网络虚拟化是解决因特网这一瓶颈的有效方式。虚拟网络环境能够促进共存异质网络结构的部署实施,不受上述因特网本身固有的限制。本文针对网络虚拟化中的资源分配问题——虚拟网络映射问题做了研究,主要解决以下三种虚拟网络映射问题:(1)动态虚拟网络映射(Dynamic Virtual Network Embedding: DVNE))问题:采取根据当前网络状态,最优映射当前虚拟网络的方式,提出渐进贪婪动态虚拟网络映射算法(Progressively Greedy VNE Algorithm: PG-DVNE)。在映射过程中,首先建立数学模型实现点边协调映射,进而松弛模型的整数约束条件使得模型在多项式时间内可解,但这种松弛严重削弱虚拟网络点边协调映射,通过添加约束增强虚拟网络结点映射和边映射的协调性,然后运用渐进贪婪的思想求解模型,最终得到虚拟网络映射结果和优化目标值。仿真表明,此算法在虚拟请求业务接收比例,网络收益以及网络收益和网络开销之比这三方面有很好的性能和优势。(2)静态虚拟网络映射(Static Virtual Networks Embedding : SVNE)问题:首先设计数学模型,进而提出基于拉格朗日松弛(Lagrange Relaxation : LR)的LR-SVNE算法和基于贪婪分解(Greedy Decomposition :GD)的GD-SVNE算法。LR-SVNE算法首先对模型中的难约束条件进行拉格朗日松弛,然后通过计算上下界的方式逼近问题的最优解,降低了时间复杂度,有很好的收敛性;GD-SVNE算法将多个虚拟网络按照所需资源从大到小排序,运用贪婪分解的思想将问题分解为多个子问题,每个子问题转变为单个虚拟网络映射问题,运用渐进贪婪动态虚拟网络映射算法(PG-DVNE)中映射每一个虚拟网络的方法进行单个虚拟网络的映射,此算法大大降低了时间复杂度,网络开销与原模型最优目标值接近,在网络规模和数量较大时更具有优势。(3)支持业务量疏导的虚拟网络映射(Virtual Network Embedding with Traffic Grooming: VNETG)问题:文中提出数学模型对VNETG问题进行描述,通过求解此模型将不同虚拟网络的链路进行捆绑,能够最大限度地映射多个支持细粒度业务的虚拟网络,同时最小化网络开销;此外,文中提出基于拓扑合并的映射算法(Topology Combination based VNETG Algorithm: TC-VNETG),算法首先将多个支持细粒度业务的虚拟网络合并成一个虚拟网络,然后运用PG-DVNE算法中映射一个虚拟网络的方法对合并后的虚拟网络进行映射,此算法巧妙地实现了不同虚拟网络之间的结点资源和光路共享。当虚拟网络数目较小时,TC-VNETG算法求解的网络开销比求解VNETG模型略大;当虚拟网络数目较大时,TC-VNETG算法求解的网络开销比求解VNETG模型略小。与求解原模型相比,TC-VNETG算法大大降低了时间复杂度。