异构网络测试床拓扑映射算法研究

发布时间：2018-06-25 16:58

本文选题：异构网络测试床 + 拓扑映射　；参考：《解放军信息工程大学》2014年硕士论文

【摘要】：网络测试床是测试验证网络协议、服务及分布式系统的重要基础设施。融合了多种模拟仿真手段的异构网络测试床是网络测试床中非常重要的一类。为虚拟网络高效地分配硬件资源是网络测试床中的一个关键问题,称为拓扑映射问题。拓扑映射的性能和效率直接影响了网络测试床的规模和效益,因此具有重要的研究意义。本文以降低算法时间开销、提高请求接受率和资源利用效率为主要目标,对异构网络测试床中的拓扑映射算法进行了专门研究。首先,建立了异构网络测试床中的拓扑映射模型,选取了拓扑映射算法评价指标和测试方法,并据此构建了仿真实验环境；然后,基于虚拟网络粗化和映射方案修正思想提出了一种多层拓扑映射算法框架；最后,分别研究框架中的3个主要问题,提出3种算法。本文完成的主要工作和取得的研究成果包括：1)提出了多层拓扑映射算法框架。该框架以同时保证映射质量和降低拓扑映射时间开销为目标,基于虚拟网络粗化和映射方案修正思想,采用多层粗化／修正模式,将一次拓扑映射分为粗化阶段、映射阶段和细化阶段,分别完成虚拟网络逐层粗化、映射粗化后的虚拟网络求得初始映射方案、逐层细化和修正映射方案得到最终映射方案。2)研究粗化阶段的虚拟网络粗化问题,提出了一种底层资源感知算法。通过分析底层网络可用资源和虚拟网络拓扑结构对虚拟网络粗化问题影响,在基于节点配对的贪心算法的基础上,引入了多节点合并策略,设计了底层资源感知的链路排序函数和节点合并条件。仿真实验表明,相对于简单虚拟网络粗化算法,该算法可大幅提升了较高负载条件下的虚拟网络粗化质量。3)研究细化阶段的拓扑映射修正问题,提出了一种基于变邻域搜索的启发式算法。该算法针对贪心算法易陷入局部最优的问题,设计了一种映射方案的可变邻居结构,引入了变邻域搜索过程,并融合了模拟退火算法的解接受策略。仿真实验表明,该算法可有效提高修正后拓扑映射方案的质量。4)研究映射阶段的拓扑映射问题,提出了一种基于分布估计的启发式算法。针对映射阶段输入规模较低而映射质量要求较高的特点,引入元启发式方法中求解质量较高的分布估计算法,设计了拓扑映射方案的编码方式和拓扑映射问题的分布估计概率模型。仿真实验表明,在多层拓扑映射框架下组合上述3个算法,可在小幅度提升映射质量的同时,大幅降低了拓扑映射时间。
[Abstract]:The network test bed is an important infrastructure for testing and verifying network protocols, services and distributed systems. Heterogeneous network test bed, which combines many simulation methods, is a very important class of network test bed. Efficient allocation of hardware resources for virtual networks is a key problem in the network test bed, called topology mapping. The performance and efficiency of topology mapping directly affect the scale and efficiency of the network test bed, so it has important research significance. In order to reduce the time cost of the algorithm, improve the request acceptance rate and resource utilization efficiency, the topology mapping algorithm in the heterogeneous network test bed is studied in this paper. Firstly, the topology mapping model in heterogeneous network test bed is established, the evaluation index and test method of topology mapping algorithm are selected, and the simulation experimental environment is constructed. Based on the concepts of virtual network coarsening and mapping scheme modification, a multi-layer topology mapping algorithm framework is proposed. Finally, three main problems in the framework are studied and three algorithms are proposed. The main work and research results in this paper include: 1) A multi-layer topology mapping algorithm framework is proposed. The framework aims to ensure the mapping quality and reduce the time cost of topological mapping at the same time. Based on the coarsening of virtual network and the modification of mapping scheme, the primary topology mapping is divided into coarse stage by adopting multi-layer coarsening / modifying mode. In the mapping stage and the refinement stage, the virtual network layer by layer coarsening is completed, and the initial mapping scheme is obtained by the mapping coarsening virtual network. Layer by layer thinning and modifying mapping scheme to get the final mapping scheme .2) the coarsening problem of virtual network in coarsening stage is studied and a low-level resource awareness algorithm is proposed. By analyzing the influence of the available resources of the underlying network and the topology structure of the virtual network on the coarsening of the virtual network, a multi-node merging strategy is introduced on the basis of the greedy algorithm based on the node pairing. The link sort function and node merging condition are designed. Simulation results show that compared with simple virtual network coarsening algorithm, this algorithm can greatly improve the coarsening quality of virtual network under high load. A heuristic algorithm based on variable neighborhood search is proposed. Aiming at the problem that greedy algorithm is prone to local optimization, a variable neighbor structure of mapping scheme is designed, variable neighborhood search process is introduced, and the solution acceptance strategy of simulated annealing algorithm is fused. Simulation results show that the proposed algorithm can effectively improve the quality of the modified topology mapping scheme. (4) A heuristic algorithm based on distribution estimation is proposed to study the topology mapping problem in the mapping stage. In view of the characteristics of low input scale and high mapping quality in the mapping stage, a meta-heuristic method is introduced to solve the high quality distribution estimation algorithm. The coding method of topological mapping scheme and the probability model of distribution estimation for topological mapping problem are designed. The simulation results show that the combination of the above three algorithms under the framework of multi-layer topology mapping can greatly reduce the mapping time while improving the mapping quality by a small margin.
【学位授予单位】：解放军信息工程大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.06

【相似文献】