基于GPU的SDN网络并行业务量工程算法研究

发布时间：2020-11-19 17:06

　　 业务量工程(Traffic Engineering)能够通过为业务选择合理的网络路由来达到充分利用网络资源、提高网络性能、满足Qos需求等目的。在SDN网络中,集中式的SDN控制器能够在全局拓扑上进行业务量工程,提高业务量工程的优化效果。然而,由于互联网应用的快速增加,短时间内会有大量业务到达SDN网络,同时,SDN网络的规模也相应增大,这要求SDN控制器能在短时间内在大网络拓扑上为大量业务计算路由,业务量工程的计算面临着时间上的挑战。所以,为了缩短SDN控制器的计算时间,本文利用GPU的强大并行计算能力来加速业务量工程算法。针对SDN IP网络,本文首先将业务量工程问题建模成一个带链路容量约束的MILP模型。为了求解这个模型,本文设计了两种并行算法GA-PTEA(Genetic Algorithm Based Parallel Traffic Engineering Algorithm)和LR-PTEA(Lagrange Relaxing Based Parallel Traffic Engineering Algorithm)。其中,GA-PTEA将原来的业务量工程模型简化为基于备选路径的业务量工程模型,利用并行的遗传算法来求解业务量工程问题,并行加速比可达到10倍以上。LR-PTEA则采用了拉格朗日松弛的方法,首先通过松弛链路容量约束,将业务量工程问题分解为一批业务的最短路径计算问题,然后设计了基于GPU的并行算法来加速最短路的计算。LR-PTEA使用次梯度下降方法来求解拉格朗日对偶问题,为了加快次梯度算法的收敛速度,LR-PTEA采用了高效的次梯度步长更新方法,同时,LR-PTEA在求解对偶问题的过程中采用了快速的路径调整策略来获得对原问题目标函数的可行解。本文的实验发现基于GPU的LR-PTEA并行算法可以在短时间内得到业务量工程问题的优化解,与串行算法LR-STEA(Lagrange Relaxing Based Serial Traffic Engineering Algorithm)相比,加速比可达到10倍以上。在SDN弹性光网络中,首先,为了简化频谱分配问题,本文采用分层图模型将弹性光网络中的频谱分配问题转化为路由选择问题。其次,为了优化弹性光网络中业务的路由代价,减少资源使用,降低阻塞率,本文设计了TESAA(Traffic Engineering and Spectrum Allocate Algrithm)优化算法。最后,为了缩短SDN控制器的计算时间,我们对TESAA进行并行加速,分别针对无权图和带权图设计了基于GPU的并行路由算法。实验发现TESAA可以大大减小路由的代价、节省网络资源和有效降低业务的阻塞率,基于GPU的并行算法PTESAA(Parallel TESAA)与串行算法STESAA(Serial TESAA)相比,加速比可达到10倍以上。
【学位单位】：电子科技大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP393.0
【文章目录】：
摘要
abstract
第一章 绪论
    1.1 研究背景与意义
    1.2 国内外研究现状
        1.2.1 SDNIP网络下业务量工程算法的研究现状
        1.2.2 SDN弹性光网络下业务量工程算法的研究现状
    1.3 论文内容及结构安排
第二章 GPU硬件结构与CUDA编程模式
    2.1 CPU与GPU
        2.1.1 CPU与GPU区别
        2.1.2 CPU+GPU异构计算模型
    2.2 GPU硬件架构
        2.2.1 流处理器
        2.2.2 线程束（Warp）
        2.2.3 存储结构
        2.2.4 流多处理器细节
        2.2.5 执行模型
    2.3 CUDA编程模式
        2.3.1 CUDA软件线程组织
        2.3.2 kernel函数
        2.3.3 CUDA线程同步
        2.3.4 CUDA流并行
    2.4 本章总结
第三章 SDNIP网络下的并行业务量工程算法研究
    3.1 引言
    3.2 网络模型和问题建模
        3.2.1 网络模型
        3.2.2 问题建模
    3.3 基于遗传算法的业务量工程算法
        3.3.1 备选路模型
        3.3.2 遗传算法设计
            3.3.2.1 染色体结构
            3.3.2.2 初始可行解的生成
            3.3.2.3 评价与排序
            3.3.2.4 交叉
            3.3.2.5 变异
            3.3.2.6 终止条件
        3.3.3 基于GPU的并行遗传算法设计
            3.3.3.1 并行评价算法设计
            3.3.3.2 并行排序,变异与交叉
    3.4 基于拉格朗日的优化算法设计
        3.4.1 基于拉格朗日松弛的模型
        3.4.2 基于GPU的并行路由计算
        3.4.3 链路权重更新
            3.4.3.1 权重更新步长
            3.4.3.2 随机更新策略
        3.4.4 路径调整
        3.4.5 终止条件
    3.5 仿真实验分析
        3.5.1 仿真介绍
        3.5.2 目标函数比较
        3.5.3 算法时间比较
        3.5.4 算法收敛性
    3.6 本章总结
第四章 SDN弹性光网络下的并行业务量工程算法研究
    4.1 引言
    4.2 分层图模型
    4.3 分层图模型下的业务量工程算法
    4.4 无权图情况下的GPU算法设计
        4.4.1 相同速率业务的并行
        4.4.2 不同速率间业务的并行
        4.4.3 GPU上的kernel设计
    4.5 带权图情况下的GPU算法设计
        4.5.1 带跳数限制的最短路算法
        4.5.2 相同速率业务的动态规划算法并行
        4.5.3 不同速率间业务的并行
        4.5.4 GPU上的kernel设计
    4.6 实验仿真分析
        4.6.1 对比算法
        4.6.2 实验设置
        4.6.3 无权图下的仿真结果
            4.6.3.1 路由跳数优化结果分析
            4.6.3.2 时间分析
            4.6.3.3 阻塞率分析
        4.6.4 带权图下的仿真结果
            4.6.4.1 路由代价优化结果分析
            4.6.4.2 时间分析
    4.7 本章总结
第五章 全文总结与展望
    5.1 全文总结
    5.2 后续工作展望
致谢
参考文献
攻读硕士学位期间取得的成果

【相似文献】

相关期刊论文 前10条

1 王超逸;;关于网络分层信息泄露点快速检测仿真[J];计算机仿真;2018年06期

2 侯凌燕;;网络分层级算法在公路网络中的应用[J];北京信息科技大学学报(自然科学版);2012年06期

3 杨冬;张宏科;宋飞;李世勇;;网络分层优先映射理论[J];中国科学:信息科学;2010年05期

4 李丽娟;樊林京;焦俊党;;基于核心企业的网络分层探究——以郑州宇通客车为例[J];农村经济与科技;2014年03期

5 黄和建;;GSM网900M/1800M网络分层研究[J];移动通信;2009年16期

6 刘彦婷;南作用;;从网络仿真看LTE网络分层结构部署[J];邮电设计技术;2015年10期

7 李明辉;夏靖波;陈才强;;基于网络分层谱系模型的综合评估方法[J];中南大学学报(自然科学版);2013年03期

8 宋鑫;SDH网络分层[J];北京电信科技;1994年02期

9 张明星;杨垚;程光权;刘忠;;目标网络分层描述与自修复机制研究[J];指挥控制与仿真;2016年06期

10 费孔鹤;;引入层的介绍[J];信息通信;2012年02期

相关硕士学位论文 前8条

1 张骞;基于GPU的SDN网络并行业务量工程算法研究[D];电子科技大学;2018年

2 侯杰;一个基于领域知识的复杂网络演化模型[D];哈尔滨工程大学;2014年

3 杜常数;面向DCI网络流量调度方案的设计与实现[D];哈尔滨工业大学;2017年

4 张贝;基于物理分层结构的大规模Ad Hoc网络分层协议的研究[D];西安电子科技大学;2008年

5 刘海红;基于复杂网络统计特性的非线性时间序列分析方法研究[D];济南大学;2017年

6 郭鹏飞;光网络核心节点交换矩阵与管控技术研究[D];北京邮电大学;2014年

7 徐一鸣;水下无线传感器网络覆盖控制策略与算法研究[D];杭州电子科技大学;2017年

8 仇亚骏;面向数据中心的软件定义光网络资源调度研究[D];北京邮电大学;2017年

本文编号：2890237