面向谷歌云数据集的虚拟网络映射算法研究

摘要

网络虚拟化作为未来网络的基本特征之一，将网络服务提供与基础设施提供两个功能分开，依据用户业务需求提供合适的网络服务。其核心问题之一是虚拟网络映射问题，即为带有节点和链路资源约束条件的虚拟网络请求分配底层网络资源。若能合理地最优化利用基础设施资源，便能为基础设施提供商带来巨大的利益，因此，虚拟网络映射问题在近年来也得到了广泛的关注。然而，目前针对虚拟网络映射算法的研究皆使用GT-ITM工具来产生网络拓扑而开展模拟评估，并没有考虑真实网络环境的复杂性，因此并没有对在不同规模网络环境下的算法取舍做出一个极其有说服力的结论。此外，现有的虚拟网络映射算法都存在着一定的局限性，特别是当网络环境下存在大量以Batch形式到达的请求时，应用目前普遍采用的虚拟网络映射算法都会大幅降低虚拟网络的映射性能，从而减少底层资源的收益。基于以上几点可见，针对虚拟网络映射算法的研究还需不断深入。
　　本文通过分析Google云数据中心于2014年11月所发布超过一亿条网络服务请求的400多GB的数据集，提炼网络请求的特征，为评估虚拟网络映射算法提供对真实网络环境下的网络服务请求进行建模。鉴于此前的研究中都没有对常用的虚拟网络映射算法的实际性能进行比较，本文设计实验比较两种基于整数规划的虚拟网络映射算法在不同规模的真实网络环境下的性能表现，旨在对每种算法在真实网络环境下的运算性能进行分析，并对企业在实际应用中虚拟网络映射算法的取舍进行一定指导作用。此外，本文在实验过程中所建立的网络服务请求预测模型对于后续相关的研究也起到了极大的启发性作用。
　　在另一方面，根据本文对Google云数据集的观察，在实际应用中，大量请求皆以Batch形式到达，而传统的虚拟网络映射算法在处理Batch到达的请求时都具有一定的局限性。因此，本文提出一种基于遗传算法的启发式算法——称之为VNE-NGA算法，着重解决Batch形式到达的网络服务请求。并通过理论推导和实验证明得出结论，这种算法在真实网络环境中，对虚拟请求的接收率和底层网络产生的长期收益皆远高于传统算法。

目录

声明

致谢

摘要

1．1 研究背景和目的

1．2 国内外研究现状

1．3 论文的研究贡献

1．4 论文的组织结构

2 相关知识和问题模型

2．1 算法分类

2．2 问题模型

2．2．1 网络拓扑

2．2．2 映射目标

2．3 虚拟网络映射问题目前的主流解法

2．4 本章小结

3 数据集分析

3．1 数据集来源

3．2 数据清洗

3．3 数据分析

3．4 误差产生

3．5 本章小结

4 传统虚拟网络映射算法性能比较

4．1 VNE-USP算法

4．2 VNE-OMS算法

4．3 实验环境

4．4 实验结果

4．5 本章小结

5 基于遗传算法的资源优化映射算法

5．1 算法设计思想

5．2 VNE-NGA启发式算法

5．3 实验环境

5．4 实验结果

5．5 本章小结

6．1 论文总结

6．2 未来展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集