英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
一阶段多分布式位置感知和节点排序值辅助虚拟网络映射算法
第一部分 介绍
现在的通信网络应用一刀切的方法为所有的终端用户提供服务，却不顾具体的垂直服务需求。然而，这种设计方法不能提供不同的服务并满足爆炸性的数据通信需求。因此，下一代网络必须研发新技术以满足多样化的垂直服务需求。目前，研究人员已就网络虚拟化是下一代网络特别是即将到来的5G虚拟化移动网络的一项关键技术达成一致。通过虚拟化，可以将不同的多样的用户化的虚拟网络需求高效无缝地分配到多样化的分散的物理网络中以提供不同的垂直服务（如一个需要高通信带宽的广播服务）。
在网络虚拟化环境中，传统的网络服务提供商被分离成两个独立的角色：基础设施提供商（InP）（如中国铁塔）和服务提供商（SP）（如中国移动，网易，腾讯）。这个分离计划目的是实现底层资源的最大化利用并提供不同的网络服务。独立的SP负责执行虚拟网络请求以满足终端用户不同的资源或功能需求。终端用户将为他们的虚拟网络请求服务付费。因此SP获益于终端用户。这些利益属于SP的映射收益。在这种商业模式下，SP向InP租用不同的底层物理网络资源（如CPU，节点储存，通信带宽）。所以，SP必须根据其与InP之间的合同条约向InP付费。InP将向提出租用请求的SP显示资源的部分或全部信息，如网络拓扑结构、资源数量。在本论文中，我们研究SP知道InP的所有可租赁的资源信息的情况。由于InP在与SP合同到期后更新其资源信息，对于InP来说，向SP展示其可租赁的资源信息是可行的。总之，对SP来说，在他们租用的底层物理网络上映射更多的虚拟网络需求以获取更多的映射收益以及最大化利用租用的底层资源至关重要。随着虚拟网络请求和容量的增加，SPs需要从InP那里租用多的底层资源，因此SPs将会向InP支付更多的收益。因此，InP将赚取更多的映射收益。
从这些事实中，我们发现对SPs和InP来说有映射算法非常重要。这些映射算法有助于根据终端用户具体的虚拟网络请求服务以最佳方式满足虚拟网络请求。在文献中将虚拟网络映射到底层物理网络的问题因而叫做虚拟网络映射（VNE）。因此，这些映射算法叫做虚拟网络映射算法。
从2008年开始，研究人员提出了多样的虚拟网络映射算法以解决VNE问题。近年来，许多调查已经在具体的虚拟网络映射算法中实施。鉴于VNE的NP-困难问题属性，研究人员试图提出可行的映射算法。在文献中，可行的映射算法包括贪婪节点映射策略和最短物理路径映射、基于映射的ELECTRE方法、线性混合整数算法、线性列生成辅助算法、拓扑驱动和网络资源联合映射、线性候选集辅助整数算法以及其他启发式算法。然而，大多数的先前的算法集中于在两个分开的阶段（分离节点和链路映射）完成每个虚拟网络的映射。一些映射算法使用混合整数线性算法方法或博弈论或子图同构，将对每个虚拟网络的映射在一个映射阶段内完成。这种映射算法计算时间长，而且这些算法将每个物理网络映射到一个集中的物理网络中。这样未来虚拟网络的实现不会被提升。尽管CAN-A证明了在多项式时间内执行虚拟网络映射，但是它在一个集中的物理网络执行虚拟网络的映射，所以不会提升实际的网络实现。在实际的网络环境中，每个虚拟网络必须被映射到多样化分散的物理网络上。每个物理网络的物理节点在地域上被分布到不同的位置上。这种类型的虚拟网络映射问题被称为多样化分布式VNE。尽管近年来一些映射算法已经被提出，但是它们都是两阶段映射算法而且耗费时间长，会导致局部底层资源过负载和虚拟网络低映射率问题。混合整数线性算法具有大计算复杂度。尽管确保了准确的虚拟网络映射的解决方案，但是不能提升实际网络环境下的时间敏感服务（如网上游戏服务）。
基于上述背景，我们提出了一个位置感知和节点排序值辅助的映射算法（简称LANRVA-VNE）以解决多样的分散的VNE问题。我们原始的映射目标是尽可能多的容纳虚拟网络，因而将InP和SP的映射收益最大化。我们首先建立了正式的多样化分布的VNE问题模型。然后，我们详细描述了提出的LANRVA-VNE算法。LANRVA-VNE能够在一个映射阶段内将虚拟网络请求映射到多样的分散的物理网络中。在执行映射前，LANRVA-VNE将根据虚拟网络节点的位置请求或识别，为所有虚拟节点建立候选节点集。对于任一虚拟节点M，LANRVA-VNE将利用我们的计算好的节点排序值，使用迭代算法对所有候选的物理节点排序。在运行虚拟网络映射时，运用贪婪节点和最小中间节点优先的最短路径映射方法。LANRVA-VNE考虑了CPU、节点存储、预定位置、通信带宽、最大化虚拟链路允许中间节点和链路延迟作为虚拟网络节点-链路的约束。大多数以前的VNE算法在映射虚拟网络请求时仅仅将CPU和通信带宽作为约束。为了进一步突出LANRVA-VNE的效率，我们进行了评估工作。主要的评估结果以图显示，展示了LANRVA-VNE算法将虚拟网络接受率在典型的两阶段映射算法（如VNE-NTANRC-S、RW-SP、ViNE-SP）上显著提高了至少10%。其他性能指标（如收入成本比）也被绘制出来以加强LANRVA-VNE算法的效率。
本论文其余内容的安排如下。第二部分描述正式的多样化的分散的VNE问题模型。在第三部分详细描述LANRVA-VNE算法。第四部分是进行的评估工作。最后，总结本论文。
第二部分 正式的多个分布的VNE问题模型
- 正式的多个分布的VNE问题模型
在VNE研究领域，大多数研究者应用图论建立物理网络和虚拟网络模型。在多个分布的VNE 问题模型中仍使用图论建立分布的物理网络和虚拟网络模型。独立的InP拥有的整个底层物理网络（ ）由|N|个地理上分散的物理网络组成。第i个物理网络（i=1,2,3,hellip;|N|）用权重图
表示。 代表了第i个物理网络中所有底层物理节点。 代表了第i个物理网络中所有底层物理链路。 代表了第i个物理网络中所有物理元素属性，具体见表1。在图1中，我们也绘制了由两个在地理上分散的物理网络（SN1和SN2）。由InP预留的连接分散的物理网络的物理链路，被设定为在长距离通信方面有足够的通信带宽。每个独立的物理网络中可用的通信带宽指链路上的数字。可用的CPU和节点存储指矩形中的数字。为了便于说明，没有绘制预留的网络元素，比如物理节点位置。
表1 第i 个物理网络物理元素属性
|
物理节点，CPU属性 |
|
|
物理节点，存储属性 |
|
|
物理节点，位置需求属性 |
Loc(m),x,y坐标 |
|
物理带宽属性 |
|
|
链路mn传播延时属性 |
|
|
的物理链路集合 |
|
|
的物理链路集合 |
|
|
中所有从m到n的直接路径 |
|
|
中的一个路径选择 |
图1 一个多个分布式VNE和两个虚拟网络映射的例子
同样地，我们用 建立每个虚拟网络请求模型。 代表虚拟网络中的所有虚拟节点。 指虚拟网络中的所有虚拟链路。 指所有虚拟元素属性，具体见表2。我们在图1中画了两个不同的虚拟网络请求。通信带宽请求指链路上的数字，CPU和节点存储指矩形中的数字。为了便于说明，图1省略了预留位置、最大允许中间物理节点和最大允许虚拟链路传播延时。
表2 虚拟网络元素属性
|
虚拟节点，CPU请求属性 |
|
|
虚拟节点，存储需求属性 |
|
|
虚拟节点，预留位置请求 |
Loc(M) |
|
虚拟链路，带宽请求属性 |
|
|
虚拟链路，允许传播延时 |
|
|
M的最大允许距离偏差 |
LR(M) |
|
MN的最大允许中间节点 |
IN(MN) |
对于介绍整个物理网络和虚拟网络请求模型，我们决定描述虚拟网络映射到整个底层网络上。关于虚拟网络的映射，两个映射阶段通常包括：第一节点映射过程和后续链路嵌入过程。两个映射过程展示如下。
⑴ 节点映射过程
为了完成节点映射，使用唯一的节点映射函数完成所有虚拟网络节点的映射，该函数如下： 。
对于所有满足要求的节点约束有：
（1）
在表达式1 中，必须满足虚拟网络的所有虚拟节点约束（本论文中要考虑CPU、节点存储和节点位置）。否则，这个虚拟网络将被拒绝。例如，图1中，在满足所有节点资源和功能约束的条件下，VN1的虚拟节点a,b,c被映射至物理节点A,C,B。至于VN2，所有虚拟节点成功地被映射到d →B, e →H, f →J, g →D。同时，VN2的所有节点约束都被满足。
⑵ 链路映射过程
在后续链路过程中，我们通过唯一的链路映射算法 进行对所有虚拟链网络虚拟链路的链路映射。在此链路映射过程中，为了不影响虚拟网络的体验质量（QoE），通常不允许路径分裂和链路干扰。对所有满足条件的链路约束有：
(2)
表达式2中任一虚拟网络链路的所有虚拟网络链路约束（本论文为通信带宽需求、最大虚拟链路允许中间节点和链路传播延时请求）必须被满足，否则，虚拟网络将被拒绝。例如，在满足所有链路资源和功能约束的条件下，VN1中的虚拟链路ab被映射到物理路径ABC上（图1）。虚拟链路bc被映射到物理路径CB上。至于VN2，它所有的虚拟链路都被成功映射为：gd → DCB, ge → DCIH, gf → DJ。所有链路（资源和功能）约束也被满足。
以上两个阶段成功完成后，此虚拟网络映射完成。在VNE研究中大多数映射算法在两个独立的过程中实行虚拟网络的映射。首先执行节点映射过程，然后进行后续链路映射过程。两个过程没有或部分并列存在。因此，使用这种映射方法在大多数情况下无法保证映射质量。因而要求提出一个阶段的映射算法，将节点和链路映射结合到一个阶段中并提高虚拟网络映射质量。另外，必须将虚拟网络映射执行时间最小化。我们必须避免高耗费时间的映射情况。我们试图把虚拟网络映射提升到未来动态且实时的虚拟网络服务的实现。
B. 多样化分布式VNE的主要性能指标
为了评价多样化分布式VNE算法，我们在这一部分用公式表示主要的性能指标。首先是SP实现接受一个虚拟网络赚取的映射收益。
（3）
其中，T指被映射的虚拟网络的使用周期。我们用公式表示 的每一部分的收益（表达式4）。它不是一个非线性函数，等效于所有的虚拟CPU、节点存储和虚拟通信带宽。表达式中使用权重（alpha;，beta;和gamma;）来平衡不同的虚拟网络节点和链路约束。
（4）
虽然表达式3和4 表明了多少映射收益可以被赚取，但是不衡量CPU、存储和带宽资源是没有意义的。我们用表达式5 表示虚拟网络每个单元的消耗。与表达式4一样，权重因子用来平衡不同的资源。 记录含有虚拟链路MN的底层路径mn的跳数。本论文中，术语“跳”与术语“中间节点”含义相同。
(5)
(6)
与表达式3类似，我们制定表达式6。这个表达式能使我们在虚拟网络的生命周期内计算被接受的虚拟网络消耗物理资源的量。它是虚拟网络映射收益减去虚拟网络映射消耗的结果，与映射虚拟网络得到的网络收益有关。本论文中，我们不将其他收益与消耗如能量消耗增加到网络收益的计算中。所以，评估LANRVA-VNE的主要指标是虚拟网络映射收益和映射消耗。
在网络虚拟化研究中，虚拟网络接受率（将在第4部分用图表示）是评价不同VNE算法映射能力的重要性能指标。节点存储利用率、链路通信带宽利用率和虚拟网络映射使用时间也在第4部分用图说明。但是我们不在本论文中介绍并详细说明这些性能指标，而详细说明LANRVA-VNE算法并强调其性能效率。在我们最新发表的调查中我们详细说明了VNE的性能指标。任何感兴趣的读者都可以参考。
第三部分 LANRVA-VNE的具体细节
我们在这个部分详细说明LANRVA-VNE/为了更好地理解这个算法的细节，我们将使用这一算法执行一个已给出的虚拟网络的映射。
- 为所有虚拟网络虚拟节点建立候选集
接收到从从终端用户发来的虚拟网络请求时， ，我们将首先为给出的虚拟网络 的所有虚拟节点建立候选物理节点集合。
对于任一被选择的虚拟节点M，它将被提供一个所需的节点位置， ，以及最大允许的距离偏差LR(M)。对整个物理网络 中的任一物理节点m，有其位置为 。这样我们建立表达式7。记录虚拟节点M和物理节点m之间的欧氏距离。如果满足表达式7，我们将进一步依据CPU和节点存储需求比较m和M。如果m预留有足够的CPU和节点存储资源去容纳虚拟网络节点M，我们将选择节点m作为虚拟网络节点M的一个候选节点。至于整个物理网络 的所有其他节点，我们将选择合适的候选物理节点组成虚拟网络节点M的候选节点集。
对于 中的其他（|N|-1）个虚拟节点，我们重复以上过程（|N|-1）次。总计，所有虚拟网络节点的候选
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[237295]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
