虚拟网络映射算法研究与实现

作     者：胡德栋 

作者单位：北京邮电大学 

学位级别：硕士

导师姓名：杨震

授予年度：2020年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：虚拟网络映射 快速高效映射 启发式算法 链路负载均衡 

摘      要：虚拟网络映射在过去的十年间是一个热点话题,其主要是将虚拟网络按照要求映射到底层网络上。这是一个NP-hard问题,以往的研究往往会对虚拟映射施加很多约束或者仅仅使用简单的启发式方法来获取一个相对较优的解。在传统的研究中,二阶段独立的算法由于两个阶段的分离,解空间受限制,往往会出现请求接收率偏低的情况。二阶段协调算法对运行时间方面的优化还不能完全满足实时性要求高的场合。除此之外,一阶段的算法往往有着复杂的计算,通常会带来更多的运行时间。为了解决传统研究中的接收率低、耗时多的问题,我们提出了两个高效的虚拟映射算法,分别是RCRGF算法和AEF算法。RCRGF算法是一阶段算法,该算法在映射之前会进行预处理操作,将虚拟网络进行减边,使得虚拟网络变成树形结构,然后基于BFS使用空间换时间策略来完成一阶段的映射。AEF算法是二阶段协调算法,其使用一些创新的策略提高了多个评估指标的性能,同时基于邻近映射来改善代价收益比,使用与底层网络剩余带宽成反比的评估函数找到使得底层网络资源尽可能均衡的路径。在两个算法中都引入了映射规则,该规则通过提前预判被映射的底层节点是否合适,从而避免映射到无效的底层节点上,使得候选节点集合缩小,加快了映射速度。本文的两个算法的主要目标是为了尽可能加快映射速度,同时保证其他评估指标的高效性。在设计和实现算法后,对两个算法的时间复杂度给出了公式说明和证明。RCRGF算法的时间复杂度是O（|NS|2*log（|NS|））,AEF 算法的时间复杂度是O（|Ns|2*|NV|*（log（|NS|）+|NV））,这在理论上说明了算法的可行性。在仿真实验测试中,可以看出我们算法基本上在映射时间方面比大多数其他算法有更明显的优势,同时也能保证更高的性能。