一种带扰动的虚拟数据中心网络嵌入算法

摘要

本文主要针对多路径网络中的虚拟数据中心嵌入问题进行了分析解决，主要贡献在于首次针对多根树形网络上的虚拟数据中心嵌入问题提出了一种局部最优的解决方案，并首次提出了一种可应用于一般网络的启发式虚拟数据中心嵌入算法。
　　本文首先将虚拟数据中心网络的嵌入问题划分为两个子问题，即虚拟机的放置方案和通信流量的路由方案。本文基于对通信带宽的约束建立了相关的线性规划，并对原线性规划进行了对偶及处理，再借助于穷举搜索给出的虚拟机放置方案，提出了多根树形网络中虚拟数据中心网络嵌入的一种通用思路，即基于线性规划的穷举搜索方法。通过对线性规划目标函数的设置，算法提供了虚拟数据中心嵌入问题的一种局部最优的解决方案。
　　为了降低基于线性规划的穷举搜索算法的复杂度，本文又提出一种带扰动的启发式算法。其主要按照分布放置虚拟机的思路，在每一次虚拟机配置方案作出更新后，对整个网络链路的拥塞情况作出检查并通过扰动消除拥塞。据此本文分别提出了基于负载均衡的多路径路由扰动算法和基于单路径路由的扰动算法。其后，本文又将多根树形网络中的扰动算法拓展至一般网络中，并应用于几种典型的数据中心网络中。
　　本文对几种嵌入算法进行了实验仿真，涵盖了静态仿真和动态仿真两种不同的仿真模式以及不同的基层网络拓扑。仿真结果显示，本文所提出的负载均衡的多路径路由启发式扰动算法，能在大大降低基于线性规划的穷举搜索的时间复杂度的前提下，得到接近局部最优的算法性能，在嵌入效果和算法复杂度之间提供了折中选择。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题研究背景

1.2 国内外研究现状

1.3 本文主要贡献与内容

第二章 问题描述

2.1 虚拟数据中心请求模型

2.2 基层数据中心网络结构

2.3嵌入问题描述

2.4 本章小结

第三章 基于线性规划的穷举搜索算法

3.1 虚拟机的分配

3.2 通信流量的路由

3.3 整体算法

3.4 本章小结

第四章 带扰动的启发式嵌入算法

4.1 负载均衡的多路径扰动算法

4.2 单路径扰动算法

4.3 本章小结

第五章 扰动算法在一般网络中的拓展

5.1 一般网络中的多路径扰动算法

5.2 一般网络的单路径扰动算法

5.3 典型数据中心网络中的嵌入

5.4 本章小结

第六章 仿真实验及结果分析

6.1 静态仿真

6.2 动态仿真

6.3 本章小结

第七章 全文总结与展望

7.1 全文内容总结

7.2 后续工作展望

参考文献

致谢

攻读硕士学位期间发表学术论文情况